Re: monitoring entropy

Colin Plumb (colin@nyx.net)
Tue, 14 Oct 1997 22:27:11 -0600 (MDT)


Ingo Molnar wrote:
> eg. attacker sees some new user prepares a pgp run (you can just trigger
> this when 'atime' of the pgp binary changes, and make it automatic ...),
> then start a 'pool draining attack' (which is just a tight loop, doesnt
> show up in populated systems).

So? Merely *reading* /dev/urandom doesn't reduce the entropy of the
returned results at all. It's just that there is a (very hard to compute)
correlation between previously read data and subsequent results.
An attacker has to take that data and grind on it with computers far
in advance of anything presently available, and then the attacker can
guess your PGP private key.

It would be a heck of a lot easier for the attacker to just factor the
public key.

/dev/random blocks before the point at which it's even theoretically
possible to predict based on correlations with previous output.

If you just read the data and throw it away, there's nothing to correlate
with and no reduction in entropy at all.

> no need to spy, just run some tight loop and read /dev/urandom, this
> decreases randomness. Those few events here and there adding a few bits to
> the pool should not be a problem for some brute-force (assuming limited
> number of really random bits) attack ... me thinks.

See above. You have to read lots of it and then compute, and then based
on what you have read, you can predict. The output of /dev/random this
instant depends on every sampled input event back through the first
time you created an /etc/random-seed file.

Entropy is predictability. /dev/random's entropy estimate is based on
a worst-case assumption: all reads are going straight to an attacker with
infinite computational power available. It blocks before producing
any output predictable to *that* attacker. A less powerful attacker
will have a harder time of it.

> i was talking about limiting _output_. I dont see how this could influence
> entropy adding speed in any way.

Unless we make /dev/urandom blocking too, which seems like a bad idea
to me.

-- 
	-Colin