Mining-Ps-Qs-Reading-Review

Name: Samuel Tay
UW Net ID: tays
Paper: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices
Authors: Nadia Heninger, Zakir Durumeric, Eric Wustrow, J. Alex Halderman

Paper Review

• Problem: RSA and DSA schemes require proper, cryptographically secure random number generators that rely on sufficient levels of entropy; when these requirements are not met, attackers can subvert these schemes to obtain private keys. At the time of writing, the extent of this problem in the wild was unknown, so the authors perform a large scale experiment across TLS and SSH servers.
• Approach: The authors' approach is to first perform an Internet-wide survey; specifically, they scan the public IPv4 address space to find hosts with either ports 443 (TLS) or 22 (SSH) open, initiate a handshake for the given protocol, and store the returned cert chain or host key in a database. This is all accomplished with bespoke software for each protocol, to process a high number of connections concurrently. Then they analyze this dataset in search of problems related to insufficient randomness.
• Conclusions: Their experiment uncovered a number of issues.
  • First, a sizeable proportion (5.6% of TLS hosts and 9.6% of SSH hosts) use the same keys as other hosts. Some of this is due to using manufacturer default keys, and others are due to malfunctions in the random number generators used.
  • Second, they are able to compute private keys for 64k TLS hosts and 108k SSH hosts! For RSA keys, they implement an algorithm to efficiently find GCDs of all distinct pairs of the public RSA moduli in the dataset; note that since the RSA modulus is a product of two primes, once you find a shared prime factor, you can easily divide to find the other prime factor, and of course once the factorization of the modulus is known, recovering the private key is trivial. For DSA keys, they found numerous DSA signatures that used the same ephemeral keys during signing, and there are known exploits in this case that allow recovering private keys.
  • They found that most of these hosts were headless or embedded systems, which isn't surprising since these devices are likely to have fewer entropy sources compared to traditional PCs.
  • Their final take is that fundamentally, RSA and DSA are secure schemes, but that the scheme is only as strong as its implementation. While most keys generated on traditional PCs are likely secure, when implementations rely on poor sources of randomness as is often the case in headless & embedded systems, security cannot be guaranteed.
• New ideas: The entire experiment was new; there was no internet-scale analysis of generated cryptographic keys before this. To make the experiment feasible required custom software that could handle processing a massive number of TLS connections, a custom SSH client to perform concurrent SSH handshakes, etc. Another line of research that I think was novel was the deep dive into the Linux entropy hole. I also thought it was a really great initiative to offer an online key-check service to allow testing keys for vulnerability; that's a good use of their dataset.
• Improvements: I honestly can't think of any. I thought this paper was pretty fantastic. They provided ample background information, thoroughly detailed their methodology, and offered practical advice for various audiences. (Although, throwing shade on the independent group of researchers concurrently working on the same thing was maybe a tad out of place. The critiques were valid I suppose, just seemed weird.)
• New directions: This was a really cool experiment. I wonder if they can build on some of their tooling to explore new venues, scanning for various other ports and protocols. Another direction, related to the advice for OS developers in section 7, is to come up with a rigorously defined API spec for RNG interfaces; perhaps one that enforces application users to always specify their required level of entropy and not let people shoot themselves in the foot.