<div dir="ltr"><p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">D. J. Bernstein has proposed an attack on RNG schemes that use a hash algorithm to combine output from several entropy sources. (<i>2014.02.05: Entropy Attacks!,</i> on The cr.yp.to blog) I believe his attack can be thwarted by using a key-stretching hash to combine the outputs. </p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">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. </p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">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. </p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Assuming the system under attack has a trusted timer or real-time clock, the system software can set the work level parameter of the combining hash to be on the order of the maximum time that should be needed to interrogate the final entropy source (the potential rogue) after output has been received from all other entropy sources. If the measured time exceeds a reasonable margin above what is expected, the system should fail safe by refusing to accept the RNG outputs. Alternatively, the system can measure the time interval between obtaining the first and last RNG’s data and set its key stretching work factor based on this time interval.  </p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">In particular, Intel’s RDRAND is implemented as a CPU instruction, so almost no time should elapse between the penultimate entropy source's data being obtained and the needed RDRAND instructions being completed. Thus a fairly small key stretching work parameter, even a few milliseconds, should suffice to detect a CPU with an RDRAND that attempts to implement Bernstein's attack.</p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Arguably a CPU chip with a cooked RNG instruction could suspend its timers while possible RNG outputs are being tested, though it would have to know when the critical output was being requested, otherwise the timer interference might be detected. (At some point we must recognize that an all-knowing CPU with lots of covert firmware designed around our software can defeat any security scheme.) Other timing sources are possible. Common, inexpensive external real time clock ICs, such as the DS1302, provide timing to one second resolution. An available GPIO pin could be used to charge a small capacitor with a resistor in parallel and then measure its voltage decay for a rough time check. </p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">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. (<i>Stealthy Dopant-Level Hardware Trojan</i>s 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.</p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">The key stretching defense is particularly well suited to the difficult case of a black box device needing random data at first start up, when, typically, its secret keys are generated. A tens of seconds delay during first boot would seem a reasonable trade off for enhanced security. The Bernstein attack would then take several minutes, a delay that would be easy to notice. A similar argument applies to systems that generate one time a high quality seed for a deterministic RNG which will then be used to meet all future randomness requirements.</p><div><br></div><div>Arnold Reinhold</div><br>On Saturday, February 1, 2014 9:51:14 PM UTC-5, D. J. Bernstein wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">The conventional wisdom is that hashing more entropy sources can't hurt:
<br>if H is any modern cryptographic hash function then H(x,y,z) is at least
<br>as good a random number as H(x,y), no matter how awful z is. So we pile
<br>one source on top of another, hashing them all together and hoping that
<br>at least one of them is good.
<br>
<br>But what if z comes from a malicious source that can snoop on x and y?
<br>For example, imagine a malicious "secure randomness" USB device that's
<br>actually spying on all your other randomness sources through various
<br>side channels, or---worse---imagine RDRAND microcode that's looking at
<br>the randomness pool that it's about to be hashed into. I should note
<br>that none of the attacks described below rely on tampering with x or y,
<br>or otherwise modifying data outside the malicious entropy source; you
<br>can't stop these attacks by double-checking the integrity of data.
<br>
<br>...</blockquote></div>