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
2:39 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
6:24 a.m.
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(a)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(a)lists.fedoraproject.org
https://lists.fedoraproject.org/mailman/listinfo/security-team
9:36 a.m.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
On Mon, Jul 28, 2014 at 07:24:10AM -0400, joat wrote:
Who's the decision authority on stuff like this, where an issue
is more
politics than security?
If upstream doesn't want to incorporate the fix then we can ask the packager to push a
patch to fix it. We can also go to FESCo and ask.
In this particular case I believe we need to have someone review the CVE. I'll do
that now.
- -- Eric
- --------------------------------------------------
Eric "Sparks" Christensen
Fedora Project
sparks(a)fedoraproject.org - sparks(a)redhat.com
097C 82C3 52DF C64A 50C2 E3A3 8076 ABDE 024B B3D1
- --------------------------------------------------
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
iQGcBAEBCgAGBQJT1l/NAAoJEB/kgVGp2CYv3bMMAIpVxjJ+kaXglh50/m3u0i1D
YR4NeBZZAHKPJSD1JHa0FaHsjkXWkYErEY1G8VVbLk7K8vleUZpVIo37ieB3IHN5
P31T2NC7/Z3f3ysHKfoTd4cvE55PZTIQBybJ6rGFVyxeeksu2aLGcFpmR3GWEHXp
ggQXTWqFZqIySadOxXMBjK4gns2iQ7DesNO0M53FSwG2NNIE1iBWGkVUjq+n616k
ouqHrNvDEKUDX2uUoKDYgiUm+F0SocbPUZ4TqVZifO9FJwV9aKJHFXQ4jh3xWVEJ
+C2Kcy0fPd18mOpa/Ir/lt7yUCO9vHCjzo5CBSOqo+7+Rdc43EOTTD3RDT+Cct9s
Eamjwi8pfSLEmKsEyv37o2ZV3F97oGG169+UCWWpvLHsHVMCE2pd3EiALR/D0suR
V/8b1N0q6DJpz7+XWUWBbD3/JATQlkhxF2Y4ljgJxwHhCYSpbIIYndlmn+YTWu4r
KzBetUb904sajOHtJKtJ9AYsVsshSVvkzx5QGb6dtA==
=IDsc
-----END PGP SIGNATURE-----
3560
days inactive
3561
days old
security-team@lists.fedoraproject.org
3 comments
4 participants
participants (4)
-
Eric Christensen -
Jan Rusnacko -
Jan Rusnacko -
joat