When Good Randomness Goes Bad

When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography

Authors:
Thomas Ristenpart and Scott Yilek

Abstract:
Random number generators (RNGs) are consistently a weak link in the secure use of cryptography. Routine cryptographic operations such as encryption and signing can fail spectacularly given predictable or repeated randomness, even when using good long-lived key material. This has proved problematic in prior settings when RNG implementation bugs, poor design, or low-entropy sources have resulted in predictable randomness. We investigate a new way in which RNGs fail due to reuse of virtual machine (VM) snapshots. We exhibit such VM reset vulnerabilities in widely-used TLS clients and servers: the attacker takes advantage of (or forces) snapshot replay to compromise sessions or even expose a server's DSA signing key. Our next contribution is a backwards-compatible framework for hedging routine cryptographic operations against bad randomness, thereby mitigating the damage due to randomness failures. We apply our framework to the OpenSSL library and experimentally confirm that it has little overhead.

References:
Proceedings of Network and Distributed Security Symposium -- NDSS '10

Versions:
A version is available as a pdf

Slides:
Slides from talk at NDSS 2010 are available as a pdf

List of Updates:
March 23, 2010 -- put up proceedings version of paper