[Cryptography] TRNG related review: rngd and /dev/random

[Bill Cox]

On Thu, Jan 21, 2016 at 3:12 AM, Neuhaus Stephan (neut) <neut at zhaw.ch>
wrote:

> On 2016-01-20 02:37, Bill Cox wrote:
> > - If entropy is trickled in, and an attacker who knows the initial state
> > of the entropy pool (which is a file on disk) and all the public keys of
> > all pairs generated from /dev/random, she can easily guess all the
> > private keys
>
> What you seem to be saying is that someone who knows the initial state
> of the generator and all of the bits that go into the generator can,
> also knowing its source code, move it forward to predict the bits that
> come out of the generator.
>
> If that's the kind of adversary you're looking at, what model would
> defend against it?
>
> If you're saying that one of the weaknesses in /dev/random is that if
> randomness is "trickled in" at too slow a rate, then the output might be
> predictable, then that does not seem to be specific to /dev/random.
>
> Fun,
>
> Stephan
>

This is a well known simple attack.  I'll explain in more detail.

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?

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.

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.

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.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160121/a082dbf7/attachment.html>