<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jan 21, 2016 at 3:12 AM, Neuhaus Stephan (neut) <span dir="ltr"><<a href="mailto:neut@zhaw.ch" target="_blank">neut@zhaw.ch</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 2016-01-20 02:37, Bill Cox wrote:<br>
> - If entropy is trickled in, and an attacker who knows the initial state<br>
> of the entropy pool (which is a file on disk) and all the public keys of<br>
> all pairs generated from /dev/random, she can easily guess all the<br>
> private keys<br>
<br>
</span>What you seem to be saying is that someone who knows the initial state<br>
of the generator and all of the bits that go into the generator can,<br>
also knowing its source code, move it forward to predict the bits that<br>
come out of the generator.<br>
<br>
If that's the kind of adversary you're looking at, what model would<br>
defend against it?<br>
<br>
If you're saying that one of the weaknesses in /dev/random is that if<br>
randomness is "trickled in" at too slow a rate, then the output might be<br>
predictable, then that does not seem to be specific to /dev/random.<br>
<br>
Fun,<br>
<br>
Stephan<br></blockquote><div><br></div><div>This is a well known simple attack.  I'll explain in more detail.</div><div><br></div><div>Initially, somehow, the attacker knows the state of the CPRNG.  From that point on, she only sees IVs and public keys, and may miss some of them now and then.  However, if zero new entropy is inserted into the CPRNG, it is trivial for the attacker to play the state forward and re-sync her version of the state.  This lets her figure out all the private keys.  Would you agree?</div><div><br></div><div>Now, suppose there is a very slow trickle of randomness into the CPRNG state, say one byte at most between the times that the attacker sees new IVs and public keys.  To re-sync, the attacker only needs to consider the 256 possible values that may have been added to the state, times the number of places where it might have been added between keys and IVs, and again play the CPRNG forward to re-sync.</div><div><br></div><div>In general, this attack works so long as the attacker continues to see the output, likely as a network eavesdropper, and so long as only small guessable amounts of randomness are added to the CPRNG state betwen outputs.  This is why you need to add an unguessable amount all at once, rather than trickling it in.</div><div><br></div><div>There seem to be popular TRNG ICs that only add at most one byte of true randomness to the CPRNG between reboots, so this is a real issue, especially since the initial state is pre-programmed secretly at the factory.</div><div><br></div><div>Bill</div></div></div></div>