I've been at Asiacrypt 2013 in Bangalore this week, and taking a bit of time out from going to the talks and checking out India I thought I'd write about Nadia Heninger (@nadiaheninger) and Tanja Lange's (@hyperelliptic) presentation on their research into factoring 1024-bit RSA keys. The paper can be found here, and there's a set of slides here. This discovery was presented first at the Crypto 2013 rump session.
The one sentence summary is that they were able to recover at least 184 of the 1024-bit RSA keys generated by a certified smartcard and used in a Taiwanese national database of digital certificates for citizens.
Other that the fact that they were able to this is quite alarming, the most important thing to note here is that they didn't need anything like the computing power of a special purpose cluster or a large botnet, or a highly optimised version of an implementation of the general number field sieve to factor those 1024-bit keys; the trick here is to exploit the randomness used to generate the keys themselves.
What's the problem with randomness?
To explain this it's necessary to go back to some research by Lenstra et al. (Crypto 2012) and Heninger et al. (Usenix 2012). An RSA moduli is a large integer that is the product of two large prime numbers, so if you're given a public RSA moduli and are able to find one of its prime factors, then you can get the corresponding private key. Obviously the size of the RSA modulus is chosen to be large enough such that this should be impossible to do (note: there seems to be a general recommendation at the moment to move away from 1024-bit RSA keys up to 2048-bit keys).
The critical observation made in the referenced research was that it's easy to check whether two RSA moduli share the same prime factor (and to find that factor). So if you have a set of RSA public keys, it turns out that using the greatest common divisor (GCD) algorithm it is relatively cheap to check for the presence of any shared factors and if found, recover the private keys.
On paper this shouldn't ever be a concern, as all our prime factors should be chosen uniformly at random, and so the chance of any two being the same should be vanishingly small. However, this is not always the case---some devices appear to have entropy problems with their random number generation that result in some factors being generated more frequently. Heninger et al. were able to retrieve private RSA keys for 0.5% of TLS hosts and 0.03% of SSH hosts on the Internet, and Lenstra et al. managed to recover 12720 keys from 4.7 million moduli.
The underlying problem appears to stem from entropy shortfalls in the random number generation methods used in devices that are typically either headless or embedded. I'd highly recommend checking out both papers for more detail.
Going further than finding shared primes
The research team here initially tried to find shared factors within the smartcard signature dataset, and were able to recover 103 private keys. What differentiates this particular attack is that Bernstein et al. were able to factor a further 81 keys by looking in more detail at the particular properties of the flawed random number generation.
The authors hypothesise that in this instance it appears that the shared factors are likely to arise because of a glitchy hardware random number generator. By inspecting the shared primes, the authors observed that the rng seems to create primes that have a particular structure, for instance containing repeated binary patterns (e.g. "001001001001" or simply "00000000").
The trick used here was to use the observed patterns as a profile for trying to guess additional primes that are not shared with any other moduli but do closely match one of the observed patterns, and then to simply use trial division across the remaining unattacked moduli in the dataset to see if the guessed prime factor actually is a match. There's not really space to go into detail here, but the authors then go a step further and use Coppersmith's method to find more prime factors of a particular form, getting us up to the final value of 184 recovered private keys.
One interesting aspect to this is that these smartcards passed both FIPS and Common Criteria certification, and so one might wonder why and how this randomness issue managed to sneak by the evaluation processes. According to the authors the Taiwan government department responsible has initiated the task of issuing replacement cards.
Finally, this is another example of how the lack of quality randomness can spectacularly screw otherwise perfectly secure crypto up. Random number generation is a key element of a large number of currently used protocols, and so it remains to be seen how large this particular attack surface actually is (for instance, see Nadia's Asiacrypt rump session talk on ECC), especially given the certification issue here and the ongoing discussion about Dual_EC_DRBG.
Much more detailed info on this particular attack can be found here and for a look at the problem of bad randomness producing weak keys in general, check out factorable.net---both sites are well worth a read.
No comments:
Post a Comment