RSA, Randomness and IoT
A new paper by researchers at KeyFactor shows how an extremely high number of RSA keys on the Internet can be completely broken, in very short time. Out of 75 million RSA certificates scraped from the Internet between 2015 and 2017, a whopping 250,000 could be completely broken. This means that any data protected by these keys is exposed, and any signing application using these keys is vulnerable. For example, if RSA signing is used to protect firmware updates to IoT devices, and that RSA key can be easily broken (as shown in this research), then attackers can install malicious firmware en masse on the IoT devices in question. This is extremely dangerous.
The fundamental question considered by KeyFactor is not new, and the same method was used to break RSA keys in the past in two papers ( Ron was wrong; Whit is right and Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Device). The difference here is that many more RSA keys were analyzed, with a focus on IoT devices. It turns out that the situation is much worse for IoT devices: first, they are much harder to patch, and second, they are more vulnerable within themselves. In order to understand why, we need to briefly review how this attack works.
RSA keys are generated by multiplying two very large prime numbers p and q together, in order to obtain a “public modulus” N = p*q. The problem of factoring N back into its prime factors p and q is very hard computationally, and practically infeasible for large enough numbers. However, if I have two such moduli N1 and N2, where N1 = p*q and N2 = p*r (that is, N1 and N2 have one of their prime factors p in common), then it is easy to find all of the prime factors p, q and r. This is the so-called GCD problem (greatest common divisor), and the algorithm devised by Euclid for this problem thousands of years ago is the one that is essentially still used today (with some optimizations).
Now, the security of RSA is based on the difficulty of finding these prime factors, given the public modulus. Thus, if two moduli have a common prime factor, both of those keys can be completely broken. The reason why this should not be an issue is that when generating RSA keys, the prime numbers are chosen at random. Since they are really big (e.g., over 300 digits each), the chance of the same prime number being chosen twice, even over all of the keys in the world for all time, is essentially zero. The chance that a meteorite will destroy earth in the near future is much higher! Despite the above, what the researchers at KeyFactor showed was that in the IoT world, a very high number of RSA keys indeed share the same prime factor (about 1 out every 172). Why is this the case?
The answer to this question is randomness! Theoretically, the task of choosing a large random number is easy. However, that is only the case if one has access to a strong random number generator. In practice, this is not always the case, and in particular, when considering IoT and other weak devices. Thus, the “random primes” chosen are far from random, and they repeat far more often than they should.
What is the conclusion from this? Primarily, it is important that we understand that strong random generation is absolutely essential, even when working with weak devices. If the device itself cannot generate randomness, then each device must be initialized at the factory with an independent fresh random seed that can be used to generate strong pseudorandomness (good cryptographic solutions exist for this). Beyond this, it just comes back to the fact that deploying cryptography well requires expertise, and working naively is very dangerous. The IoT world is especially dangerous since IoT devices are everywhere, and hacking into them can greatly compromise the new digital world that we live in.
Originally published at https://www.unboundtech.com on December 19, 2019.
