<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div><br><br>Sent from my iPhone</div><div><br>On Feb 21, 2014, at 12:56 AM, John Kelsey <<a href="mailto:crypto.jmk@gmail.com">crypto.jmk@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>[I'm responding to a somewhat old message, because I think this is an interesting idea worth thinking more about]</div><div><br>On Feb 9, 2014, at 3:36 PM, Arnold Reinhold <<a href="mailto:agr@me.com">agr@me.com</a>> wrote:<br><br></div><blockquote type="cite"><div dir="ltr"><p style="margin-bottom: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">D. J. Bernstein has proposed an attack..,</p></div></blockquote><div>...</div><blockquote type="cite"><div><div dir="ltr">
<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 <a href="http://people.umass.edu/gbecker/BeckerChes13.pdf">http://people.umass.edu/gbecker/BeckerChes13.pdf</a> ) 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></div></div></blockquote><div><br></div>Yes, this is a variant of the entropy guessing attack. <br><div><br></div><div>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.) </div><div><br></div><div>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:</div><div><br></div><div>a. Collect entropy for 10 seconds and seed my RNG.</div><div>b. Collect entropy for 10-T seconds and then run my key stretching algorithm for T seconds.</div><div><br></div><div>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. </div></blockquote><div><br></div>There are a couple responses. First an engineering trade off, e.g. nine seconds of entropy gathering and one second of key stretching would get most of the benefits of both (72 bits from entropy gathering, 22 bits from key stretching).<div><br></div><div>Second, it's hard for me to see a use case where an added 10 or 20 seconds of processing when a box is powered up for the very first time is unacceptable. </div><div><br></div><div>Third, at some point we have to be willing to just say no, the constraints you put on your system in terms of available entropy sources and limits on start up time are incompatible with security requirements. </div><div><br><blockquote type="cite"><div><br></div><div>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. </div><div><br></div>
</blockquote>Again there are engineering trade offs here. You could start key stretching immediately on your fast source, e.g. RDrand as you suggested in you second post, and finally mix in the slower source(s) at second 9. </div><div><br></div><div>Arnold Reinhold</div></body></html>