mailing list archives
Re: pwgen: non-uniform distribution of passwords
From: Solar Designer <solar () openwall com>
Date: Tue, 17 Jan 2012 23:51:31 +0400
On Tue, Jan 17, 2012 at 02:01:38PM +0400, Solar Designer wrote:
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%
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).
It was just pointed out to me off-list that the man page for pwgen
specifically mentions that this kind of passwords "should not be used in
places where the password could be attacked via an off-line brute-force
attack." I had missed that detail or at least I did not recall it.
This kind of documentation certainly mitigates the problem to some extent.
Yet I think this gives users the perception that only the keyspace is
smaller, not that the generated passwords are distributed non-uniformly.
In fact, most users would not even think of the latter risk.
The passwords look much stronger than they actually are, and I think
this is a problem. They look like almost random sequences of 8
characters, whereas the level of security for 6% to 20% of them is
similar to that of dictionary words with minor mangling.
Sure, there's a trade-off, but non-uniform distribution didn't have to
be part of it. That's an implementation shortcoming.
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