The GCD strikes back to RSA in 2019 - Good randomness is the only solution?

Question

When someone collects lots of RSA public modulus, the first thing that comes to mind is;

$$\text{GCD them all}$$

If you calculate the GCD of two different RSA modulus and if the result is not 1 then you find one of the factors. This has been actively studied in

1. 2012 - Heninger et. al Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

These researchers collected 5.8 million unique TLS certificates and 6.2 million unique SSH host keys. In the combined collection, there were 11 million distinct RSA moduli and they were able to factor 16,717 distinct public keys. I.e. breaking 23,576 (.4%) of their TLS certificates and 1,013 (.02%) of the RSA SSH host keys.

2. 2012 - Lenstra et. al Ron was wrong, Whit is right

They collected 6.2 million digital certificates across the Internet they found that approximately 4.3% of these certificates fully share their RSA modulus with another.

3. 2013 Bernstein et. al, Factoring RSA keys from certified smart cards: Coppersmith in the wild

The researchers investigate Taiwan’s national “Citizen Digital Certificate” database that contains more than two million RSA modulus. They have efficiently factored 184 distinct RSA keys. They are noticed that some of the primes occur more than was like p110 occurs 46-times. The reason was the flawed random-number generators in some of the smart cards.

4. 2016 - Hasting et.al, Weak keys remain widespread in network devices

To see the response of the vendors and end-users, the authors examined 81 million distinct RSA keys and were able to factor 313,000 keys (.37%). They see that a significant number of new devices from Huawei, D-Link, and ADTRAN was vulnerable.

5. 2016 Barbulescu at. al RSA Weak Public Keys available on the Internet

They crawled GitHub SSH-RSA keys between 22 December 2015 and 7 January 2016. They were only factor 1 with 512-bit. They also analyzed a ransomware database that contains 2048-bit RSA that contains none weakness.

From raw X.509 certificates collected during 2012, they tested 26177420 1024 bit RSA keys tested, 63502 (0.25%) keys were found to be factorized.

6. 2018 - N. Amiet and Y. Romailler, researchers from Kudelski, Reaping and breaking keys at scale: when crypto meets big data.

They collected 340M RSA keys and 210k are broken. 1 key out of 1600 is vulnerable to batch-gcd by written by Chapel.

And recently;

7. 2019 - Researchers at KeyFactor Factoring RSA Keys in the IoT Era

They scraped 75 million RSA certificates from the Internet between 2015 and 2017, a total of 250,000 could be completely broken. That is 1 in 172 shares a factor.

One solution to prevent the common factor is a public database. That is downloadable so that one can test their new modulus with the GCD. Of course, such a database has another issue. The reason that causes the same prime generation, the randomness process, can be exploited by some attackers. In any case, the attackers can scrape their database as researchers.

Questions:

1. Can A good random number generator solve this issue if we consider we are using RSA-2048 and let say we need 1 billion RSA modulus?

2. What is the probability that we can select a prime at least twice if we only consider 1024-bit numbers?

3. Why don't we generate the primes in different bit domains like 1024,1025,1026,1027-bit,...

Answer 1

The solution is simply to make sure that you have good randomness. At the size of the numbers we are considering, the probability of a repeat when using good randomness is extremely small. To make this clear, there are well over $2^{1000}$ prime numbers of length 1024. The probability of a repeat at any reasonable number of primes chosen, when using true randomness, is so small that it's not worth considering. To be more exact, if we generate $t = 2^{50}$ random primes of length 1024 (this is 1,000 trillion), then the probability of a repetition is smaller than $\frac{t^2}{2^{1000}} = 2^{-900}$.

True randomness isn't that helpful, so the NIST recommendation is to take a random seed for your PRG at double the length of the bit security you are looking for. So, assume RSA-2048 is 128-bit security (it's actually a bit lower by estimates, but let's ignore that detail for here). Then, you should be using a 256-bit truly random seed, and using that in a PRG based on something like AES-256. In this case, the chance of getting a repetition is still essentially 0, even if thousands of trillions of keys are generated. Again, to be more exact, the probability would be upper bound by $\frac{t^2}{2^{256}} = \frac{2^{100}}{2^{256}} = 2^{-156}$.

The main challenge is how to make sure that good randomness is used. It's much cheaper and easier to generate identical devices on a factory line that have nothing unique. In this case, each device needs to generate its keys by itself later, and the easiest thing again is for it to use its own internal state. This doesn't work. The best option is to write a fresh random 256-bit seed in every device during production (in a factory, it's not a problem at all to have a machine with a true random generator that can generate the seeds that are written to the devices). If this isn't done, then there needs to be some way of securely delivering a good seed to the device. It's possible to "add in" any entropy that can be generated locally as well, but this cannot be the primary source.

Answer 2

Obviously, good entropy is the Right Solution, however there is a mitigation possible that would help somewhat even with marginal entropy.

The issue occurs if we have two different keys with the same $p$ but different $q$s; if that happens, then a third party with both public keys can factor both. What we can do is try to avoid this situation (even if entropy might not be great).

So, what we can do is take the entropy that we have, and use it to seed a (cryptographically secure) random number generator. Then, we use the output of the RNG to select the prime $p$, and then (without reseeding the CSRNG) use more output to select the prime $q$.

If we have two different devices with poor entropy (and so have the same entropy state), they'll select identical $p$ and $q$ values, and thus select the same RSA key (except they might pick different $e$ values; that is unimportant). This is obviously not ideal; however a third party cannot use the public keys to factor either.

Now, this idea doesn't give all the benefits of having a good entropy source; one device could decrypt anything destined for the other; even if you trust both devices, if two devices have the same RSA key, and the adversary breaks into one, he also obtains the private key for the other device. In addition, if the adversary knows the details of the device, and is able to guess the original entropy sample, he can recompute the private key (by simulating the original private key generation process). However, it is better than nothing by mitigating most purely passive attacks (and does not conflict with the task of creating a better entropy sources)

Also note that the NIST approved methods of RSA key generation (FIPS 186-4) already do this.

Answer 3

^{(Comments to Yehuda Lindell's answer turned to answer per request)}

The option to "write a fresh random 256-bit seed in every device during production" is good, in that it avoids the need for a reliable TRNG in the device. But it is not entirely without drawbacks: how do we make sure that no one knows that value, and convince others of that? Perhaps we should also use an internal TRNG (most security devices have one).

An internal TRNG adds little to the marginal cost of even a high-end high-security Smart Card IC like this or this. I guess much less than one thousandth of Euro, factory-testing and associated contribution to lowering yield included. There are sizable NRE costs, though: the TRNG hardware and associated software needs to be designed, tested, perhaps certified.

Back to the question, and also stealing a good idea from poncho's answer:

1. Yes, a good random number generator can solve the issue of common factors in RSA moduli. The safest could be generating all prime factors of an RSA modulus using the same CSPRNG with a large state (say, 512-bit), which is enough to ensure with near mathematical certainty that GCD attacks will fail. And seed that at each key generated, from
   • at least 256-bit of an internal TRNG (including supervising software to catch accidental or adversarially-induced faults);
   • and a secret at least 256-bit random seed fed at factory;
   • and perhaps, a key generation counter.
2. With this method, the mathematical probability of duplicate factor is infinitesimal, see Yehuda Lindell's answer. The leading concerns would be uncaught software mistake, backdoor, and hardware malfunction, accidental or from deliberate attack.
3. Using different modulus bit sizes would only slightly reduce the probability of shared primes. On the other hand it would seriously increase the complexity, thus probability of uncaught implementation error, and cost of development and validation. By Murphy's law, there will be issues (of interoperability, or worse). This is a solution to the wrong issue, and seems a bad idea overall. KISS.

Answer 4

GCD only works if you have multiple different keys that share a prime. If the entire key is identical then GCD doesn't help you.

The duplicate primes problem is normally a result of a random number generator with two characteristics.

1. The random number is initially poorly seeded.
2. During the key generation process the random number generator is subject to an outside influence that makes it's behavior non-deterministic.

If the random number generator is only seeded once and only used for the key generation process then the chances of generating two distinct keys that share a prime is negligible.

The linux kernel PRNGs are re-seeded as new "entropy" comes in. They are also a shared resource, which can be called upon to generate random numbers for multiple purposes. I suspect other operating systems are similar but I don't have direct knowledge.

The problem is developers want to deploy a standard system image, but they want each deployed system to have it's own key(s). So they write a script that generates the system's key(s) on first boot. The system has little, but not zero external influence and so it becomes feasible for two devices to boot up with their RNGs initially in sync, but later diverging.

There are a number of ways to avoid this problem any one of the below would do it, but it would be a sensible "defence in depth" strategy to do more than one.

1. Do not use the operating system RNG directly for RSA key generation. Use a good quality CSPRNG that is seeded from the operating system only at the start of the key generation process, is not re-seeded afterwards and is not used for anything else while the RSA key is being generated.
2. Include hardware random number generation and make sure it is active and has supplied sufficient entropy before RSA key generation starts.
3. Program each device with unique seed data at the factory and feed that data into the rng before key generation. If the device supports a "factory reset" option, then take steps to ensure that a new seed is used after the factory reset.

Answer 5

Just had an idea that seems too simple to work...

You have a random number generator that given a seed, generates random numbers r1, r2, r3 etc. We use this to generate primes p1, p2, p3 etc. and combine them into keys (p1, p2), (p3, p4) etc. We are in trouble if two parties generate keys with one, but not two common primes. We suspect this is only possible if two parties use the exact same algorithm and a bad seed.

Here’s what we do: We generate primes until we find a prime of the form 6k+1 followed by a prime of the form 6k-1. If everyone follows this method, we can’t have one common prime, it must be two. If another party doesn’t follow the rule, the chance of a match is divided by 4. I assume this can be improved.

PS. A possible attack if two devices have identical keys: Assume that by sheer coincidence some important router at the NSA and my home router have identical keys. If an attacker finds out, and finds me, they could for say $1,000 get my router, I don’t care. Now with the actual hardware in their hands they might be able to crack my key - my cheap home router might allow an admin to access the public key in some way.