pwgen: non-uniform distribution of passwords

[Solar Designer <solar@xxxxxxxxxxxx>]

Hi,

I never heard back from Ted on the below.  I am not complaining -
I understand that Ted is super busy with great stuff like ext4 - yet I
think it's time to bring this to oss-security (for distros) and to
Bugtraq (for end-users).  (Not really "to make this public" since the
issue was already discussed in public on john-users.)

Some highlights (excerpts from the longer message below):

"Time running (D:HH:MM) - Keyspace searched - Passwords cracked
0:00:02 - 0.0008% - 6.0%
0:01:00 - 0.025% - 19.5%
0:20:28 - 0.5% - 39.1%
1:16:24 - 1.0% - 47.1%
3:00:48 - 1.8% - 55.2%
3:21:44 - 2.3% - 59.4%
5:05:17 - 3.1% - 64.2%

6% of pwgen'ed passwords get cracked in 2 minutes.  This is with NTLM
hashes, which are obviously very fast.  For the MD5-based crypt(3),
NTLM's 2 minutes would translate to 2 days, and this would apply
per-salt, yet having 6% of passwords crackable in 2 days on a single CPU
core is probably unacceptable.

What might be worse is that 0.5% of passwords get cracked in 1 second
(NTLM).  This is approx. 20 minutes for MD5-based crypt(3) hashes, also
on one CPU core.  0.5% is small, but not negligible."

Additional notes for Bugtraq:

Now is a good time because a related issue was just brought up:

"gpw password generator giving short password at low rate"
http://www.openwall.com/lists/oss-security/2012/01/17/2

Oh, and while I am at it: beware of JavaScript password generators -
these are almost universally broken by design.

Not very closely related, but DragonFly BSD's password hashing is
ridiculous (non-portable and weaker than FreeBSD's).  I am gradually
bringing more attention to the problem in an attempt to get it
corrected (this posting is one such step):

http://www.openwall.com/lists/oss-security/2012/01/16/2

Alexander

----- Forwarded message from Solar Designer <solar@xxxxxxxxxxxx> -----

Date: Tue, 25 Jan 2011 17:51:43 +0300
From: Solar Designer <solar@xxxxxxxxxxxx>
To: Theodore Ts'o <tytso@xxxxxxx>
Subject: pwgen: non-uniform distribution of passwords

Hi Ted,

I did some testing of pwgen-2.06's "pronounceable" passwords, and I
think they might be weaker than you had expected (depends on what you
had expected, which I obviously don't know).

Specifically, not only the keyspace is significantly smaller than that
for "secure" passwords (which I'm sure you were aware of), but also the
distribution is highly non-uniform.  My guess is that this results from
different phonemes containing the same characters.  So certain
substrings can be produced in more than one way, and then some
characters turn out to be more probable than some others (especially as
it relates to their conditional probabilities given certain preceding
characters).

By generating a custom .chr file for John the Ripper based on a lot of
pwgen'ed passwords, I am able to crack further pwgen'ed passwords a lot
faster - possibly faster than you would have expected.  This is without
any custom programming yet, which could provide a further speedup (by
fully avoiding candidate passwords that couldn't possibly be generated).

Time running (D:HH:MM) - Keyspace searched - Passwords cracked
0:00:02 - 0.0008% - 6.0%
0:01:00 - 0.025% - 19.5%
0:20:28 - 0.5% - 39.1%
1:16:24 - 1.0% - 47.1%
3:00:48 - 1.8% - 55.2%
3:21:44 - 2.3% - 59.4%
5:05:17 - 3.1% - 64.2%

That is, 6% of pwgen'ed passwords get cracked in 2 minutes.  This is
with NTLM hashes, which are obviously very fast.  For the MD5-based
crypt(3), NTLM's 2 minutes would translate to 2 days, and this would
apply per-salt, yet having 6% of passwords crackable in 2 days on a
single CPU core is probably unacceptable - or at least not what users of
pwgen would reasonably expect (I think), unless they're explicitly told
about this.  On a quad-core, this is 6% in half a day.

What might be worse, but is not seen in the table above, is that 0.5%
of passwords get cracked in 1 second (NTLM).  This is approx. 20 minutes
for MD5-based crypt(3) hashes, also on one CPU core.  0.5% is small, but
not negligible.

The "keyspace searched" column above shows percentage of the full
{62 different, length 8} keyspace.  I'd also include percentages of the
smaller keyspace that corresponds to the pronounceable passwords only,
but its size is non-trivial to calculate, so I did not bother...

Additionally, there are over 2 thousand duplicates in just 1 million of
generated passwords.  Sounds like too many dupes.  Not what a user would
expect, I think.

More info on the attack:

http://www.openwall.com/lists/john-users/2010/11/17/7
http://www.openwall.com/lists/john-users/2010/11/22/5
http://www.openwall.com/lists/john-users/2010/11/28/1
http://www.openwall.com/lists/john-users/2010/12/06/1

The "secure" ("-s") passwords appear to be safe from this:

http://www.openwall.com/lists/john-users/2010/12/07/3

A reimplementation of pwgen in JavaScript shows even worse behavior:

http://www.openwall.com/lists/john-users/2010/12/07/4
http://www.openwall.com/lists/john-users/2010/12/21/5

Please let me know if you're going to address this in any way (code,
documentation, advisory - whatever) or not (that is, I'd appreciate a
response either way).

Thanks,

Alexander

----- End forwarded message -----