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


_______________________________________________
security-team mailing list
security-team@lists.fedoraproject.org
https://lists.fedoraproject.org/mailman/listinfo/security-team