Analysis of CVE-2013-4441: pwgen Phonemes mode has heavy bias and is enabled by default

[joat]

Who's the decision authority on stuff like this, where an issue is more
politics than security?

- Tim


On Sun, Jul 27, 2014 at 3:39 PM, Jan Rusnacko <jrusnack at redhat.com> wrote:

> 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 at lists.fedoraproject.org
> https://lists.fedoraproject.org/mailman/listinfo/security-team
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.fedoraproject.org/pipermail/security-team/attachments/20140728/e607a2e7/attachment-0001.html>