Poor Random Number Generation Makes 1 in Every 172 RSA Certificates Vulnerable

Research report by firm KeyFactor shows many IoT and network devices are using weak digital certificates that make them vulnerable to attack. Researchers Jonathan Kilgallin and Ross Vasko analyzed 75 million RSA certificates and found 1 in 172 keys share a factor with another, which means they can be easily cracked.

Indeed, if two keys share a common factor, this can be known by calculating their greatest common divisor (GCD). This in turns enables calculating the rest of the divisors of those keys. Since calculating the GCD is rather easy, this approach may be scaled to a large number of public keys that are publicly available on the Internet. In other words, mining public keys and calculating the GCD of pairs of them opens the way to easily breaking them if a common factor is found.

This result, and the possibility of launching an attack to break RSA key leveraging it, was already known, although it was not considered to be a major concern in practice:

Despite the large number of keys broken by this attack previously, it is still unlikely that a key that has been properly generated with a sufficient amount of entropy could be broken with this technique.

Kilgallin and Vasko have now shown the assumption that keys are generated with enough entropy is not verified in a worryingly high number of cases. Specifically, this seems to happen specifically with IoT appliances, which may not easily have enough entropy available to generate keys with a high level of randomness.

With modest resources, we were able to obtain hundreds of millions of RSA keys used to protect real-world traffic on the Internet. Using a single cloud-hosted virtual machine and a well-studied algorithm, over 1 in 200 certificates using these keys can be compromised in a matter of days.

There are a number of additional reasons that make IoT devices specifically prone to this kind of attack, besides the lack of sufficient entropy. One such reason is the probability of succeeding in this kind of attack grows with the number of certificate pairs available to analysis, which has drastically increased due to the growth of the IoT market. Additionally, IoT devices are harder to patch, which makes it more likely to find vulnerabilities in devices that are no longer actively supported.

Although KeyFactor researchers focused on RSA, their results could be extensible to other algorithms relying on random number generation, such as Elliptic-Curve Cryptography (ECC), they say.

It is not the first time concern about IoT security is raised, with the latest disclosed vulnerability affecting a vast class of IoT devices being only week old. Kilgallin and Vasko's work bring again the focus on the importance of using security best practices from the inception of a project and to include support for timely updating both software and cryptography in IoT devices.