Re: RSA and random number generation

[coderman <coderman () gmail com>]

On Thu, Feb 23, 2012 at 10:50 AM, Georgi Guninski <guninski () guninski com> wrote:
> ...
> if i understood the paper correctly they broke some rsa keys because
> they shared a prime $p$ (the rsa keys are different, shared rsa
> keys might be explained by the debian random fiasco or the like bugs).
>
> i would suspect it is quite unlikely entropy/seed to explain the above
> scenario - the odds appear small to me.

see 
https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

"""
How could this happen?

It wasn't obvious at first how these types of entropy problems might
result in keys that could be factored. We'll explain now for the
geekier readers.

Here's one way a programmer might generate an RSA modulus:

prng.seed(seed)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
N = p*q

If the pseudorandom number generator is seeded with a predictable
value, then that would likely result in different devices generating
the same modulus N, but we would not expect a good pseudorandom number
generator to produce different moduli that share a single factor.

However, some implementations add additional randomness between
generating the primes p and q, with the intention of increasing
security:

prng.seed(seed)
p = prng.generate_random_prime()
prng.add_randomness(bits)
q = prng.generate_random_prime()
N = p*q

If the initial seed to the pseudorandom number generator is generated
with low entropy, this could result in multiple devices generating
different moduli which share the prime factor p and have different
second factors q. Then both moduli can be easily factored by computing
their GCD: p = gcd(N1, N2).

OpenSSL's RSA key generation functions this way: each time random bits
are produced from the entropy pool to generate the primes p and q, the
current time in seconds is added to the entropy pool. Many, but not
all, of the vulnerable keys were generated by OpenSSL and OpenSSH,
which calls OpenSSL's RSA key generation code.
"""

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/