[LACNIC/Seguridad] Fwd: Lousy Random Numbers Cause Insecure Public Keys

[Fernando Gont]

FYI

-------- Original Message --------
Subject: 	Lousy Random Numbers Cause Insecure Public Keys
Date: 	Thu, 16 Feb 2012 12:51:51 GMT
From: 	<schneier>



There's some excellent research (paper
<http://eprint.iacr.org/2012/064.pdf>, news
<http://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html>
articles
<http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars>)
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.

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 /how/ 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.

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.

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.

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 Fortuna <http://en.wikipedia.org/wiki/Fortuna_PRNG>, from
/Cryptography Engineering/ <http://www.schneier.com/book-ce.html>.) 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.

>From the introduction to the paper <http://eprint.iacr.org/2012/064.pdf>:

    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.

And the conclusion:

    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....

------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <https://mail.lacnic.net/pipermail/seguridad/attachments/20120217/f07fc02e/attachment.html>