<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Lousy Random Numbers Cause Insecure Public Keys</title>
<base href="http://www.schneier.com/blog/">
</head>
<body text="#000000" bgcolor="#ffffff">
FYI<br>
<br>
-------- Original Message --------
<table class="moz-email-headers-table" border="0" cellpadding="0"
cellspacing="0">
<tbody>
<tr>
<th nowrap="nowrap" valign="BASELINE" align="RIGHT">Subject: </th>
<td>Lousy Random Numbers Cause Insecure Public Keys</td>
</tr>
<tr>
<th nowrap="nowrap" valign="BASELINE" align="RIGHT">Date: </th>
<td>Thu, 16 Feb 2012 12:51:51 GMT</td>
</tr>
<tr>
<th nowrap="nowrap" valign="BASELINE" align="RIGHT">From: </th>
<td><schneier></td>
</tr>
</tbody>
</table>
<br>
<br>
<title>Lousy Random Numbers Cause Insecure Public Keys</title>
<base href="http://www.schneier.com/blog/">
<p>There's some excellent research (<a moz-do-not-send="true"
href="http://eprint.iacr.org/2012/064.pdf">paper</a>, <a
moz-do-not-send="true"
href="http://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html">news</a>
<a moz-do-not-send="true"
href="http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars">articles</a>)
surveying public keys in the wild. Basically, the researchers
found that a small fraction of them (27,000 out of 7.1 million, or
0.38%) share a common factor and are inherently weak. The
researchers can break those public keys, and anyone who duplicates
their research can as well.</p>
<p>The cause of this is almost certainly a lousy random number
generator used to create those public keys in the first place.
This shouldn't come as a surprise. One of the hardest parts of
cryptography is random number generation. It's really easy to
write a lousy random number generator, and it's not at all obvious
that it is lousy. Randomness is a non-functional requirement, and
unless you specifically test for it -- and know <i>how</i> to
test for it -- you're going to think your cryptosystem is working
just fine. (One of the reporters who called me about this story
said that the researchers told him about a real-world random
number generator that produced just seven different random
numbers.) So it's likely these weak keys are accidental.</p>
<p>It's certainly possible, though, that some random number
generators have been deliberately weakened. The obvious culprits
are national intelligence services like the NSA. I have no
evidence that this happened, but if I were in charge of weakening
cryptosystems in the real world, the first thing I would target is
random number generators. They're easy to weaken, and it's hard to
detect that you've done anything. Much safer than tweaking the
algorithms, which can be tested against known test vectors and
alternate implementations. But again, I'm just speculating here.</p>
<p>What is the security risk? There's some, but it's hard to know
how much. We can assume that the bad guys can replicate this
experiment and find the weak keys. But they're random, so it's
hard to know how to monetize this attack. Maybe the bad guys will
get lucky and one of the weak keys will lead to some obvious way
to steal money, or trade secrets, or national intelligence. Maybe.</p>
<p>And what happens now? My hope is that the researchers know which
implementations of public-key systems are susceptible to these bad
random numbers -- they didn't name names in the paper -- and
alerted them, and that those companies will fix their systems. (I
recommend my own <a moz-do-not-send="true"
href="http://en.wikipedia.org/wiki/Fortuna_PRNG">Fortuna</a>,
from <a moz-do-not-send="true"
href="http://www.schneier.com/book-ce.html"><i>Cryptography
Engineering</i></a>.) I hope that everyone who implements a
home-grown random number generator will rip it out and put in
something better. But I don't hold out much hope. Bad random
numbers have broken a lot of cryptosystems in the past, and will
continue to do so in the future.</p>
<p>From the introduction to the <a moz-do-not-send="true"
href="http://eprint.iacr.org/2012/064.pdf">paper</a>:</p>
<blockquote>In this paper we complement previous studies by
concentrating on computational and randomness properties of actual
public keys, issues that are usually taken for granted. Compared
to the collection of certificates considered in [12], where shared
RSA moduli are "not very frequent", we found a much higher
fraction of duplicates. More worrisome is that among the 4.7
million distinct 1024-bit RSA moduli that we had originally
collected, more than 12500 have a single prime factor in common.
That this happens may be crypto-folklore, but it was new to us,
and it does not seem to be a disappearing trend: in our current
collection of 7.1 million 1024-bit RSA moduli, almost 27000 are
vulnerable and 2048-bit RSA moduli are affected as well. When
exploited, it could act the expectation of security that the
public key infrastructure is intended to achieve.</blockquote>
<p>And the conclusion:</p>
<blockquote>We checked the computational properties of millions of
public keys that we collected on the web. The majority does not
seem to suffer from obvious weaknesses and can be expected to
provide the expected level of security. We found that on the order
of 0.003% of public keys is incorrect, which does not seem to be
unacceptable. We were surprised, however, by the extent to which
public keys are shared among unrelated parties. For ElGamal and
DSA sharing is rare, but for RSA the frequency of sharing may be a
cause for concern. What surprised us most is that many thousands
of 1024-bit RSA moduli, including thousands that are contained in
still valid X.509 certificates, offer no security at all. This may
indicate that proper seeding of random number generators is still
a problematic issue....</blockquote>
</body>
</html>