2:37 p.m.
Hello,
this is what I found when analysing phonemes bias in pwgen - I haven`t forwarded this to
upstream yet. Comments appreciated.
Analysis of CVE-2013-4441
-------------------------
pwgen [1] has been reported to generate biases pronounceable passwords - issue which was
assigned CVE-2013-4441.
See original report: http://www.openwall.com/lists/oss-security/2012/01/22/6
The bias that was reported does not concern probability distribution of characters in
pronounceable passwords (for example
https://www.miknet.net/security/how-random-password-generators-can-fail/ analysis is
completely irrelevant), since they naturally must have some bias towards vowels to be
pronounceable. The bias is rather in the overall distribution of passwords: given set of N
pronounceable passwords generated by pwgen, certain passwords have substantially more
occurrences (original report mentions they are as much as 137 times more likely to be
generated than they should be).
l
To illustrate the bias, I disabled the length check and recompiled it to generate 2
character pronounceable passwords. I generated 10 million of them and counted their
occurrences, along with increase/decrease with respect to expected count (see attached).
From the stats it is clear that bigrams starting with a vowel followed by a consonant are
73% less likely to be generated then expected. On the other hand, diphthongs starting with
a vowel are whopping 850% more likely to be generated.
The code makes use of structure elements, which contains characters or diphthongs along
with flags:
struct pw_element elements[] = {
{ "a", VOWEL },
{ "ae", VOWEL | DIPTHONG },
{ "ah", VOWEL | DIPTHONG },
{ "ai", VOWEL | DIPTHONG },
{ "b", CONSONANT },
...
Looking at the code (pwgen-2.06/pw_phonemes.c), there are several places which contribute
to the bias:
if (should_be == CONSONANT) {
should_be = VOWEL;
} else { /* should_be == VOWEL */
if ((prev & VOWEL) ||
(flags & DIPTHONG) ||
(pw_number(10) > 3))
should_be = CONSONANT;
else
should_be = VOWEL;
}
Variable should_be indicates whether the character which is being added is a VOWEL or
CONSONANT. In case it is VOWEL, then there is a possibility variable should_be will be
again assigned a VOWEL. This means pairs like oo, ae, ai, ie can possibly be generated if
program flow goes through this branch. Bad news is, that pairs like oo, ae, ai, ie etc.
are also diphthongs, which means there are two ways of generating them and higher
likelihood they will end up in password.
72: should_be = pw_number(2) ? VOWEL : CONSONANT;
This is where should_be is initialized before the first character of password is
generated. Since there are less vowels than consonants, yet the initialization split the
change 50:50, for odd-length passwords there is a heavy bias towards generating a
vowel-starting password.
Another bias comes from the fact that diphthongs are essentially treated as single
characters, and since they are of length 2, they are more likely to stay in the password
before it is cut-off at max size. This bias not accounted for in any way. Also this bias
towards diphthongs and above mentioned condition creates another bias: digrams starting
with vowel are less likely (-73 %) than digrams starting with consonant (-8 %).
To even out the bias, I removed diphthongs ah, oh and qu, removed complicated condition
and added dice throw to even out diphthong bias (patch and stats attached). Bias with
patch is much lower (85 % for vowel diphthongs to -48 % for consonant diphthongs) and
perhaps fixes the CVE. But here comes the catch - the patch actually decreases security of
pwgen. By removing three diphthongs and removing the weird conditional allowing two vowels
in a row, it effectively decreases the number of password that can possibly be generated.
Just for digraphs it decreases the password space from 229 to 209. For longer passwords
this grows fast and surpasses the bias in generated passwords by magnitude.
For fun I also generated 10 milion of pronounceable digraphs (yeah!) with apg [2] - stats
attached. Manpage claims it is based on NIST`s FIPS-181 standard, and it's bias seems
much smoother, but not too small either. In fact it might be interesting to conduct
thorough research whether pwgen's passwords are more biased than apg's.
For completeness, there are methods for generating pronounceable password with provably no
bias (I think [3] is an example, but unfortunately seems patented).
TL;DR
The algorithm in pwgen will inherently produce biased passwords. The fix to mitigate bias
will inevitably decrease password space by magnitudes, which lowers the security much more
than improves by removing the bias. Also apg password generator based on FIPS-181 has
comparably big bias, so it is debatable whether CVE-2013-4441 should be valid at all.
[1] http://sourceforge.net/projects/pwgen/
[2] http://www.adel.nursat.kz/apg/
[3] http://www.google.com/patents/US5588056
--
Jan Rusnacko, Red Hat Product Security
--
Jan Rusnacko, Fedora Security Team