[Cryptography] Entropy Attacks!

John Kelsey crypto.jmk at gmail.com
Fri Feb 21 00:56:06 EST 2014

[I'm responding to a somewhat old message, because I think this is an interesting idea worth thinking more about]

> On Feb 9, 2014, at 3:36 PM, Arnold Reinhold <agr at me.com> wrote:
> D. J. Bernstein has proposed an attack on RNG schemes that use a hash algorithm to combine output from several entropy sources. (2014.02.05: Entropy Attacks!, on The cr.yp.to blog) I believe his attack can be thwarted by using a key-stretching hash to combine the outputs. 
> Bernstein showed that, under certain circumstances, one specially crafted rouge entropy source can control, to a limited extent, the final output of the combining RNG. To successfully mount the Bernstein attack, the rogue entropy source must be the last entropy source polled and must know the system under attack’s combining scheme and all outputs the system obtained from the other entropy sources. The rogue RNG then internally repeats the combining hash function many times until it finds a random bit stream to output that, when hashed with the previous entropy outputs, produces a final RNG output value with the desired characteristics. 

Yes.  This attack comes up with trying to generate mutually agreed on random numbers, too.  If Alice and Bob agree to send each other random numbers and then hash them together to get a shared random, and Alice wants to control the low bit of the resulting random number, she waits till she sees Bob's random number and then tries a few (on average two, I think) random numbers till she gets a random number R[a] such that low bit of hash(R[a] || R[b]) == 1.  The work for this attack is exponential in the number of bits controled, so it's not going to be easy to control more than a small number of output bits in this way.  

In that context, one solution is to get each participant to first commit to their random number, and only open the commitments (reveal the random numbers) when they've seen everyone's commitments.  We've thought about this a bit w.r.t. potential attacks on the NIST beacon.  (For example, we define the random result of each beacon message as the hash of the whole beacon value, including signature, because the signature is done by a crypto token which won't export its signature key to the host machine.  An attacker who takes over the host machine running the beacon can only try to control output bits via brute force as quickly as the token will produce signatures, and can't move that brute force search off to the cloud or something.)

However, I have a hard time seeing how this works as a realistic attack on an RNG.  For the attack to make sense, I have to have code running inside your system which controls one entropy source, and can see all the other entropy sources, and which can duplicate everything your OS's RNG is doing in order to exert control over a couple bits of your RNG output.  It sure seems like once I've got code running with that kind of access, I can do a lot nastier things to you, like leak your keys (or your RNG seeds) via some subliminal channel.  In general, once I've got my code where it's reading all your RNG inputs, I think I've pretty much won. 
> If the combining hash is a key stretcher with a work parameter set high enough, it will not be possible for the rouge RNG to perform the many tries needed to find an acceptable output without imposing a large, easily detected delay. For simple hashes, especial ones crafted for fast hardware performance like the SHA families, it may be possible for the rouge RNG to make the necessary trials fast enough to avoid notice. But if a key-stretching hash is employed that uses enough CPU and memory resources, such as scrypt or HEKS, it will be infeasible, both physically and economically, to hide enough computation power inside the rouge RNG to do the repeated hash trials many times faster than system under attack, even if the rouge RNG is part of the system’s CPU chip. 

I think there is benefit in using some kind of key stretching algorithm for this, but it's not to resist this kind of super powerful attacker.  Rather, it's to survive a situation where you are starting up your RNG with  a marginal amount of entropy.  If your attacker can't do more than 2^{80} work to recover your seed, and you have only 60 bits of entropy, then a 2^{20} iterated hash will move the attack just out of reach.  (Note: you ought never to *design* a system to seed your DRBG with a marginal amount of entropy, but this sort of technique could buy you a few extra bits of safety margin in case you end up with a marginal amount of entropy despite your best efforts.)  

In general, for the kind of attack on a PRNG or DRBG where you are trying to guess the inputs, you get about 90% of the right intuitions for the attack by thinking about password cracking attacks.  Salt (IP or ethernet addresses) is a win for resisting this kind of attack, for example--it adds no additional entropy, but it forces the attacker to rerun his attack on each new instance of your RNG.  Similarly, making the mapping from entropy input to RNG seed computationally expensive buys you a little extra security.  

And, just as with password hashing, if you have a weak password (insufficient input entropy), all this added benefit is inadequate.  By contrast, if you have a strong password (enough input entropy), neither of these steps is all that valuable.  Salt and high iteration counts are only really very important for marginal passwords (marginal amounts of input entropy).  Of course, most users are lucky to get to a marginal password in the face of modern password cracking techniques.  

> While placing a key stretcher in the RNG chain may seem overkill to just thwart the Bernstein entropy combiner attack, an attack which demands somewhat far fetched preconditions, using a key stretching hash can also mitigate the type of attack proposed by Georg T. Becker. et. al. (Stealthy Dopant-Level Hardware Trojans http://people.umass.edu/gbecker/BeckerChes13.pdf ) An attacker using the Becker technique will reduce the effective state space of the RNG being cooked. The cooked state space must be small enough to allow a brute force search of possible RNG states, but not so small as to risk detection. Applying a high work factor key stretcher to the output of a Beckerized RNG would make the state space search far more expensive and possibly force the attacker to shrink the effective state space enough to allow detection.

Yes, this is a variant of the entropy guessing attack.  

The obvious problem with making initializing the RNG computationally expensive is that people really don't like waiting for their RNG to be ready to generate random bits.  (Note the pressure *not* to make /dev/urandom block when it doesn't have enough input entropy.  For that matter, note the use of /dev/urandom for crypto products and libraries that should know better.)  

I wonder if you might even make some RNGs worse, in practice, by doing this.  If my system has to have a working RNG ten seconds after startup, I can either:

a.  Collect entropy for 10 seconds and seed my RNG.
b.  Collect entropy for 10-T seconds and then run my key stretching algorithm for T seconds.

Suppose we are getting 8 bits of entropy per second, and I set T=5 (so I run my key stretching function for 5 seconds).  I now am seeding with 40 bits of entropy, and running for five seconds maybe I'm putting another 25 bits of security into the system, but I am losing more by not incorporating the other 5 seconds' worth of entropy in.  

We could incorprate late-arriving entropy into the RNG at the end of the key stretching algorithm, but that kills its value for blocking the attack you were describing above.  

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140221/6011d7ad/attachment.html>

More information about the cryptography mailing list