Ensuring High-Quality Randomness in Cryptographic Key Generation

Henry Corrigan-Gibbs, Wendy Mu, and Dan Boneh
Stanford University

Bryan Ford
Yale University

20th ACM Conference on Computer and Communications Security (CCS)
November 4-8, 2013, Berlin, Germany


The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an entropy authority into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public-key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values. Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a 2.1× slowdown over conventional RSA key generation and it incurs a 4.4× slowdown over conventional EC-DSA key generation.

Conference Paper: PDF

Extended and Corrected Version: Abstract PDF

This material is based upon work supported by the Defense Advanced Research Agency (DARPA) and SPAWAR Systems Center Pacific, Contracts No. N66001-11-C-4018 and N66001-11-C-4022. This work was also supported by NSF and a Google faculty award.