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

When someone collects lots of RSA public modulus, the first thing 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 device

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;

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

• Fyi, the Lenstra et al. paper was published with the title Public Keys for whatever reason. – Maeher Jan 2 at 10:02
• "Why don't we generate the primes in different bit domains" - how would you choose which 'bit domain' to use? With more bad randomness? – user253751 Jan 2 at 19:19
• @user253751 can slightly decrease the number of collisions. Of course, the most important is good randomness. However, the recent finding is devastating. – kelalaka Jan 2 at 19:22
• In your "recent" list, you might want to add also the work of researchers at Kudelski from 2018, with 210k broken keys out of 340M RSA keys. – Lery Jan 6 at 13:20
• @Lery thanks. added. This amount is really big. – kelalaka Jan 6 at 13:45

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.

• The option "write a fresh random 256-bit seed in every device during production" is good, but not entirely without drawbacks: how do we make sure that no one knows that value, and convince others of that? Perhaps the best of both worlds would be to use a good internal TRNG (most security devices have one) and an externally-fed seed. – fgrieu Jan 2 at 7:16
• @fgrieu do you know information about the cost of a good internal TRNG? – kelalaka Jan 2 at 10:14
• Of course, if an adversary ever finds the state of the DRBG (after many side channel or even fault injection attacks, for instance) then having just one initial seed becomes troublesome fast. RNG's are hard to attack though, having no input and the functions are relatively easy to construct from side channel resistant functions, with or without hw support... – Maarten Bodewes Jan 2 at 10:37
• @kelalaka: a 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, testing and associated contribution to lowering yield included. Costs are NRE. But I can't recommend a device that's readily purchasable and connected to a PC. – fgrieu Jan 2 at 11:04
• @fgrieu TRNGs add more than marginal cost if you want them to be robust against temperature variations, and environmental effects. The power not withstanding, they can be a significant cost driver. – b degnan Jan 3 at 12:40

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.

• There is another form of mitigation that doesn't add entropy, and that is to mix in a lot of identifying information into your seeding pool. IP addresses, MAC addresses, total disk file size, current time, current process id, screen resolution(s), kernel version, etc, etc. None of these are secret and thus add no extra entropy against an attacker targeting you, but they can decrease the odds of having the same low entropy state as someone else and end up with the same prime numbers. – orlp Jan 5 at 13:13

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.