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
