Study Group: Real world attacks on bad randomness.

This week’s study group was held on Tuesday 30^th October. Gaven and Stefan presented two papers introducing real world attacks on bad randomness. The talks were based on the following papers:

• Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices by Nadia Heninge, Zakir Durumeric, Eric Wustrow, J. Alex Halderman.

• Ronwas wrong, Whit is right by Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung and Christophe Wachter.

Security often depends on keys being chosen uniformly at random, thus randomness is critical for crypto. Long studies have been done in this area and it would be expected that modern operating systems and server software generate random numbers securely. Both papers test that proposition empirically by examining the public keys in use on the Internet. 

In Ps and Qs the authors conduct a wide survey of two of the most important cryptographic protocols TLS and SSH collecting 5.8 million unique TLS certificates from 12.8 million hosts and 6.2 million unique SSH host keys from 10.2 million hosts. Their results give “a macroscopic perspective of the universe of keys”. Then they analyze this dataset to find evidence related to inadequate randomness and find that at least 5.57% of TLS hosts and 9.60% of SSH hosts use the same keys as other hosts in an apparently vulnerable manner.

They also compute the private keys for 64,000 (0.50%) of the TLS hosts and 108,000 (1.06%) of the SSH hosts from their data by exploiting known weaknesses of RSA and DSA when used with insufficient randomness. For RSA, distinct moduli that share exactly one prime factor will result in public keys that appear distinct but their private keys can be computed by calculating the greatest common divisor (GCD). Their algorithm computes the GCDs of all pairs of 11 million distinct public RSA moduli in less than 2 hours and they are able to obtain the private keys for 0.50% of TLS hosts and 0.03% of SSH hosts. For DSA, if a key is used to sign two different messages using the same ephemeral key, an attacker can compute the signer’s long-term private key. Their SSH data contained DSA signatures with the same ephemeral keys during signing. This feature resulted in successful computing of the private keys for 1.6% of SSH DSA hosts.

An investigation on hundreds of vulnerable hosts showed that nearly all served information identifying them as headless or embedded systems. These kinds of devices usually generate keys automatically during the first boot and they may have limited entropy sources compared to traditional personal computers. The investigation also showed that the examination of clusters of hosts that shared a key or factor links them with a manufacturer or device model. They conclude that the problems are caused by specific defective implementations that generate keys without having collected sufficient entropy. They finally identify vulnerable hardware and software from 54 manufacturers.

In the same paper the authors explore the root causes of these vulnerabilities by investigating popular open-source software components from the population of vulnerable devices. Based on the aforementioned devices it is clear that none implementation was solely responsible for the vulnerabilities. All the examined software packages relied on /dev/urandom to produce cryptographic keys. Linux’s random number generator can present a boot-time entropy hole which causes urandom to produce deterministic output under conditions that can occur in headless and embedded devices. Experiments with OpenSSL and Dropbear SSH showed that repeated output from the system random number generator can lead to repeated long-term keys and also to factorable RSA keys and repeated DSA ephemeral keys.

The authors also provide some recommendations for developers of operating systems, cryptographic libraries and applications, for device manufacturers, certificate authorities, end users and the security and cryptography communities. Their conclusion states that the margin of safety is slimmer than we might prefer but there is no reason to doubt the security of most keys generated interactively by users on traditional personal computers.

To OS developers it is suggested to make sure the operating system maintains a secure PRNG that refuses to return data until it has been seeded with a minimum amount of randomness and is continually seeded with fresh entropy collected during operation. The operating system should also provide an interface to indicate how much entropy it has mixed into its PRNG, so that applications can gauge whether the state is sufficiently secure for their needs. Generally speaking cryptographic libraries should default to using the most secure mechanisms available. So, library developers should use RSA and DSA defensively. Also, if the OS provides a mechanism to flag that the entropy it has collected is insufficient for cryptographic use, they should do not proceed with key generation.

Application developers are advised to generate keys on first use not during installation or first boot. Developers should avoid working around low-entropy states by ignoring or disabling such warnings (with extremely dangerous results) and they must frequently add entropy from the operating system.

Device makers should tend to generate fresh keys on the device after sufficient randomness has been collected or to force users to upload their own keys. They should avoid factory-default keys or certificates. Embedded (or headless) device makers should make sure that effective entropy sources are present, and that these are being collected in advance of cryptographic operations. Devices should be initialized with truly random seeds at the factory. Device makers should test cryptographic randomness on the completed device and use hardware random number generators when possible.

Cryptographic keys and certificates that were included in the device or were automatically generated at first boot, should be manually regenerated by end users. Security and crypto researchers should be aware that the fact that all major OSs now provide cryptographic RNGs might lead experts to assume that any entropy problems that still occur are the fault of developers taking foolish shortcuts. The paper suggests otherwise: entropy-related vulnerabilities can result from complex interaction between hardware, operating systems, applications and cryptographic primitives.

The second paper brings the same alarming results. Despite the fact that numerous studies have been conducted to assess the state of the current public key infrastructure, several problems have been identified that are related to the way certificates are used. A worrisome finding is that among the 4.7 million distinct 1024-bit RSA moduli that were originally collected by the authors, 12720 have a single large prime factor in common. In a set of 11.4 million RSA moduli, 26965 are vulnerable, including ten 2048-bit ones. When exploited, it could affect the expectation of security that the public key infrastructure is intended to achieve. For the needs of the current experiment the authors collected as many openly accessible public keys as possible from the web, resulting in a set of 11.7 million public keys contains 6.4 million distinct RSA moduli. The remainder is almost evenly split between ElGamal keys and DSA keys, plus a single ECDSA key. All keys were checked for consistency such as compositeness, primality and (sub)group membership tests.

The assumption that entropy of the output distribution (of standardized RSA key generation) is always almost maximal and the outputs are hard to factor if factoring in general is hard, sometimes fails. The findings reveal that duplication of keys is more frequent in the collected set than in sets described in other works. More seriously, authors discovered 12934 different RSA moduli that offer no security.

They conclude that systems such as RSA that require multiple secrets during key-setup, are more affected by the difficulty to generate proper random values than systems that require a single secret. For RSA multiple secrets can be avoided, for instance by using moduli pq for k-bit primes p chosen such that q = [(22k−1 + p − (22k−1 mod p))/p] is prime.