Re: pwgen: non-uniform distribution of passwords

[Solar Designer <solar () openwall com>]

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

Alexander