[Cryptography] Auditing rngs

[John Kelsey]

It seems like it should be relatively straightforward to do a cut and choose style audit on a random bit generator.  However, the functionality you would need for this would also be a hell of an attack point, so it's a mixed bag.

Imagine you have an HSM that has its own entropy source.  We want to have it do something that requires randomness, say generate an RSA key.  So we do the following:

HSM:  

a.  Generate two entropy strings from its hardware entropy source, each estimated to have 512 bits of entropy.  Call these E1 and E2.

b.  Output the SHA256 hash of each, call them H1 = hash(E1) and H2 = hash(E2). 

c.  Input two additional input strings, each estimated to have 256 bits of entropy--call them A1 and A2.

d.  Using HMAC DRBG, instantiate drbg1 from E1 with personalization string A1, and drbg2 from E2 with personalization string A2.  

e.  Use each drbg to generate its own new RSA keypair.  Output keypair1 (from drbg1) and keypair2 (from drbg2).

f.  The user now knows H1, H2, A1, A2, keypair1, keypair2.  He challenges either keypair1 or keypair2.  Suppose he challenges keypair1.  Then the HSM reveals E1, and the user can redo all the computations needed to derive keypair1.  If he gets the same answer, he has some reason to trust keypair2.

You can imagine redoing this process many times to get more assurance.  However, it requires building a "leak the entropy input of my drbg" functionality into your HSM, which has some pretty obvious bad potential uses.  (Lots of security proofs have a call the attacker can make to compromise the secret state to model leakage, but normally you don't actually build that functionality into your module!)

Comments

--John