  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.1x slowdown over conventional RSA key
generation and it incurs a 4.4x slowdown over conventional EC-DSA key
generation.
