Re: Patch: new random pseudodevice

[Thor Lancelot Simon <tls%panix.com@localhost>]

On Fri, Dec 09, 2011 at 08:41:25AM +0200, Alan Barrett wrote:
> 
> I have this naive idea that trying to get out more than you put in
> is cheating, and I think it's fine for /dev/urandom to cheat, but I
> am not happy about /dev/random cheating.  Please could you explain
> where I have misunderstood.

You didn't misunderstand.  The people who designed the "entropy pool"
misunderstood.  In what sense are bits really ever "taken out"?  But,
back then, the whole idea was so new that being very conservative
about the "consumption" of entropy (consider what an amusing concept
that actually is) seemed like the safest thing to do.

Actually, it's not.  If there is some kind of correlation between the
bits you get from the pool now and the bits you got from the pool then,
the right answer is not to put more bits in and hope the correlation
gets worse; it is to correct the output function so that finding such
a correlation is actually cryptographically hard.  Before, bits were
"extracted" from the pool with a construct nobody had really studied,
and we counted every bit output as if it had been somehow "consumed".
Even though we didn't actually understand what "consumed" meant.

Also, all callers got bits directly (well, in some sense "directly",
given how the output function worked) from the same pool, so if there
was any such correlation, you could work on your random bits and --
potentially -- recover mine.

Now, we key a cipher-based construct (CTR_DRBG) that's specifically
designed for this purpose, key it separately for each caller, and
impose, instead of the old way of counting "bits consumed", the rule
that the total number of bits used to key the generator must be
equal to or less than the total number of bits we counted on input.

An attacker who can break AES might be able to predict the future
output of _one_ instance of the generator.  An attacker who can
break AES and recover the key and defeat the backtracking resistance
designed into CTR_DRBG *might* be able to recover the prior outputs
of the generator for that user.  An attacker who can do all these
things *and* recover earlier entropy-pool output from later
entropy-pool output (that is, do exactly what would have had to be
done to break the old design) can recover keys provided by the
generator to other users.  If he happens to know when exactly they
were produced (time is an input to the algorithm), etc.

Suffice to say I think the state of affairs is a lot better now than
it was before.  And note that at least one highly-thought-of modern
design for an entropy collector (Fortuna) doesn't even _try_ to
keep an "entropy estimate" -- the whole concept is pretty fuzzy
when you start trying to count how many bits you "took out".

Thor