[Cryptography] Auditing rngs

[ianG]

On 22/01/14 00:33 AM, John Kelsey wrote:
> 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.  


It seems to me that all you are proving is that the box is correctly
creating keys.  I suspect that any internal attack is likely to be based
on feeding the special RN sequence into the key creation, so this isn't
really addressing the thing we are most worried about.

Is there an attack that is more plausible that doesn't change the RNs?

I guess what I would view as the best attack would be to change the RNG
to be a cryptographically secured PRNG, seeded with the time, serial
number, nonce and some magic only known to NSA.  Reseeded every second.
 Time and nonce to be put into the certificate as delivered.

(Likely there is self-testing on the device and in the interface
software that covers the same area.  Not that this achieves the same
purpose, but it is also possible that this self-testing could do what
you describe already.)

So the defence seems simple to me:  take the RNG out of the HSM, and
then we can do things like verify if the keys are created nicely.


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


That is the general concept, the HSM is for public key operations on a
high value key-pair.  But it is harder to implement than it is to sell.
 There are these difficulties that I've come across (and I'm no more
than a skeptical observer):

a.  the interface requires pretty tight software to drive it, and
especially for low-frequency, high-value operations such as root key
creation, there can be a mismatch between the quality of the software
and the importance of the task.

b.  backups!  Once these high value keys are created, there needs to be
a process to recover.  Lost/broken HSMs?  No problems, we'll just buy 3
instead of 1.  Ah, now, how do we get the high value key from HSM 1 to
HSM 2 ... which has to be done before hand....  HSMs have this ability
but it's also fraught as above.

c.  Storing the HSM is a difficulty.  Storing the other 2 as well.

d.  Something goes wrong ... and we don't have the skills to figure it
out.  Only the purchased software can drive the HSM, and that's too hard
to figure out.  The people who set it all up are long gone, the company
who sold the HSM is sold to another and the salesman wants to solve your
problem by selling you another better type.  Problems of this nature are
things like serial numbers changing, variations in the HSMs, batteries
going flat coz they sat on the shelf for 5 years, water damage, fans
gumming up, host hardware needing to change and having incompatible
specs, even the size of the new machine can impact, etc etc.

On the whole, I think I understand the attitude of many that get into
the HSM compliance trap, just about get the thing up and going, and stop
doing anything because of the energy involved.  The solution is more
painful than the problem it is trying to solve.



iang