full-disclosure - Re: RSA and random number generation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date: Thu, 23 Feb 2012 11:51:40 -0800
From: coderman <coderman@...il.com>
To: Georgi Guninski <guninski@...inski.com>
Cc: full-disclosure@...ts.grok.org.uk, Ramo <ramo@...dvikings.com>
Subject: Re: RSA and random number generation

On Thu, Feb 23, 2012 at 10:50 AM, Georgi Guninski <guninski@...inski.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/