Weak Keys in Network Devices - Mind your RNG!


Random numbers are essential in various applications, from cryptography to numerical simulations and internet lotteries. However, generating good random numbers on a computer is a difficult task. Using an inappropriate random number generator (RNG) can have dramatic effects on the security provided by cryptosystems. This is common knowledge.

However Nadia Heninger and her coworkers show in a recent article [1] that a surprisingly high fraction of the cryptographic keys used to secure the Internet are weak and that the problem can be traced back to inappropriate random number generation.

These researchers used the Amazon cloud computing platform to perform an internet wide scanning of IP addresses to identify computers accepting HTTPS and SSH connections, and found approximately 53 million of them (for exact numbers, refer to [1]). After this scan, they wrote software to connect to these hosts and retrieve their public keys. They managed to collect a total of approximately 22 million keys.

Although this sample may seem large, it is not really when you compare it with the size of the key space. Because of this, Heninger did not expect to find repeated keys. It turned out however that approximately 60% of the keys were served more than once by the scanned computers. There can be a legitimate explanation for this: a key belonging to a large organization can be made available by several computers with different IP addresses. After removing these from the sample, the researchers still retained about 5.6% of vulnerable keys, which can be attributed to two classes of problems:

  1. Default keys: Out of these keys, a vast majority (5.3%) were actually default keys preconfigured by the vendor in the firmware of the device. They were identified by comparison with an Internet database of default keys. The use of such a key should of course be considered as a vulnerability.
  2. Low entropy keys: The remaining vulnerable keys (0.3%) can be traced back to entropy problem during key generation. To understand this, one should remember that most network devices (switches, routers, servers) are not equipped with a True Random Number Generator (TRNG). They use a software Pseudo Random Number Generator (PRNG), which collects entropy from various sources, such as human input events or disk and network timings. Unfortunately, human input entropy is not available on unattended devices. The researchers also noted that entropy from disk or network timings become available only relatively late in the boot process. They showed that it can take up to 60 seconds after start up for the system to gather enough entropy. If keys are generated before this, they will have low entropy.

An RSA public key (e,N) consists of an exponent e and a modulus N. The modulus is the product of two randomly chosen prime numbers p and, q. If p and q are known, it is straightforward to derive the private key. However, if they are unknown, one must factor N into p and q, which requires intensive computing resources. However, let’s assume that two keys with modulus N1 and N2 share one of the factors: N1 = p1 x q and N2 = p2 x q. In this case, finding the greatest common divisor of N1 and N2, which is q, is sufficient to factor these two moduli. The task of finding the greatest common divisor of two 1024-bit integers is much simpler than factoring and can be done in microseconds…

This well known vulnerability of RSA can be exploited in the context of low entropy keys. Poor random number generation can indeed lead to multiple keys sharing one of their factors. Heninger found that more than 60’000 keys (approximately 0.5%) they had collected could be factored in this way.

In some cases, the researchers were able to identify the devices which served the weak keys. They found “vulnerable devices from 27 manufacturers. These include enterprise-grade routers from Cisco; server management cards from Dell, Hewlett-Packard, and IBM; VPN devices; building security systems; network attached storage devices; and several kinds of consumer routers and VoIP products [1].”

At the beginning of the year, Lenstra and his colleagues conducted a similar study on PGP keys X.509 certificates they had collected and obtained similar results [2]. These investigations remind us of the difficulty of producing good random numbers. Using a TRNG is the best way to solve this problem. Most security devices – ie devices developed for security functions – actually follow this advice. The problem that Heninger and her colleagues have uncovered seems to be related to network devices with security functionality added in a second thought and which don’t hold all their promises.

>> Download Heninger’s article


[1] Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J. A.: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. https://factorable.net/weakkeys12.conference.pdf

[2] Lenstra, A.K., Hughes, J.P., Augier, M., Bos, J.W., Kleinjung, T., Wachter, C.: Ron was wrong, Whit is right. http://eprint.iacr.org/2012/064

ID Quantique SA | Chemin de la Marbrerie 3 | 1227 Carouge - Genève | Switzerland | T +41 22 301 83 71 | F +41 22 301 83 79 | info@idquantique.com