Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

Nadia Heninger, Zakir Durumeric, Eric Wustrow, J. Alex Halderman

To appear in Proceedings of the 21st USENIX Security Symposium, August 2012.

Abstract

RSA and DSA can fail catastrophically when used with malfunctioning random number generators, but the extent to which these problems arise in practice has never been comprehensively studied at Internet scale. We perform the largest ever network survey of TLS and SSH servers and present evidence that vulnerable keys are surprisingly widespread. We find that 0.75% of TLS certificates share keys due to insufficient entropy during key generation, and we suspect that another 1.70% come from the same faulty implementations and may be susceptible to com- promise. Even more alarmingly, we are able to obtain RSA private keys for 0.50% of TLS hosts and 0.03% of SSH hosts, because their public keys shared nontrivial common factors due to entropy problems, and DSA private keys for 1.03% of SSH hosts, because of insufficient signature randomness. We cluster and investigate the vulnerable hosts, finding that the vast majority appear to be headless or embedded devices. In experiments with three software components commonly used by these devices, we are able to reproduce the vulnerabilities and identify specific software behaviors that induce them, including a boot-time entropy hole in the Linux random number generator. Finally, we suggest defenses and draw lessons for developers, users, and the security community.

Download

Download the conference version or the more detailed extended version.

Bibtex

@InProceedings{weakkeys12,
  author = {Nadia Heninger and Zakir Durumeric and Eric Wustrow and J. Alex Halderman},
  title = {Mining Your {P}s and {Q}s: {D}etection of Widespread Weak Keys in Network Devices},
  booktitle = {Proceedings of the 21st {USENIX} Security Symposium},
  month = aug,
  year = 2012
}