[Cryptography] Auditing rngs

John Kelsey crypto.jmk at gmail.com
Tue Jan 21 16:33:31 EST 2014


On Jan 21, 2014, at 1:56 PM, dj at deadhat.com wrote:
...
> 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.

We're in the process of doing that.  But that doesn't give someone using the HSM any way to check that the internal RNG actually incorporated the additional input.  And what I'm describing here would probably not fit too well into a standard crypto module anyway, for several reasons.

Here's the problem I'm trying to solve:  From outside a device that's doing some crypto, it is impossible to determine whether the box is behaving according to spec or not w.r.t. a lot of crypto, because the box has secret values, like drbg states, keys, etc., inside which have to stay secret.  It's probably all but impossible to really be sure that a particular box is doing what you think it's doing, even with testing labs and code review and everything else we can throw at the problem.  If there is a hardware entropy source and a good drbg in the original design, an attacker can almost certainly tamper the design to produce random numbers that are predictable to an attacker.  Just chopping out all but 40 bits of the drbg's entropy would manage that nicely.  

So, how can we get the crypto box to do what we want, and verify that it did what it was supposed to?  The best answer I can see is to do some kind of cut and choose protocol:  Have the box behave according to the spec two or more times, commit to its answers, and then reveal all but one of its internal sets of values.  

So, we incorporate external input, and using this protocol, we can provide some evidence that the module incorporated that external input along with its own entropy string, and followed the spec it was supoosed to follow.  

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

On the other hand, hardware security modules often handle public key operations, and having one generate a high-value keypair is pretty sensible. If you were going to generate a high value keypair for some system, you would probably want it generated inside dedicated crypto hardware to decrease the chances of it leaking.  

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

This would not be something you would want in a general purpose crypto module at all.  Part of the protocol I am describing involves sending secret internal state values out of the module, which in general should just never ever be done.  But in this case, it's the best way I can see to prove to a skeptical user that the crypto module is actually doing what it is supposed to do. 

--John


More information about the cryptography mailing list