Catastrophic failure of Strip password generation.

2001-04-11T00:00:00
ID SECURITYVULNS:DOC:1493
Type securityvulns
Reporter Securityvulns
Modified 2001-04-11T00:00:00

Description

Executive summary: 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; see <http://www.zetetic.net/products.html> for details.

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.)

The Flaws

  • 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.

Credits

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

Cheers,

Thomas Roessler <roessler@does-not-exist.org>