[Cryptography] Auditing rngs

[dj at deadhat.com]

> 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.
>

It would be more straightforward to fix FIPS 140-2 and SP800-90 so that
there was conformant behavior defined for a raw access interface in
SP800-90 that didn't fall foul of the role based authentication required
by 140-2.

> 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:
>

Seriously? The last time someone tried asymmetric keys in a DRBG, it
didn't go so well. I'm certainly not building bignum hardware into any RNG
I design.


> 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
>

I can imagine this being a nightmare. How much code need validating to do
this, compared with validating the original RNG?