Messages in this thread | | | Date | Wed, 15 Oct 1997 08:55:35 -0600 (MDT) | From | Colin Plumb <> | Subject | Re: monitoring entropy |
| |
> Ingo Molnar wrote: > if by 'current time' you mean the cycle counter, the value of it is pretty > much predictable. It adds no real entropy to the pool. Thus you over and > over again sample the pool, thus you will be able to follow its state > more or less reliably.
I agree, it doesn't add any entropy to the pool at all. (Well, only a tiny amount. It's added in the hope that it will, but no credit is given.) It perturbs the state, though, so that a (nearly) infinite stream of reads won't return repeating data. that's the main purpose.
The protection comes from using a one-way hash. The contents of the pool are *secret*. Any given hashing operation, taking 512 bytes of input and returning 10 bytes of output, returns no easily expressible information about the contents of the pool. (For any given output, there are about 2^4016 pool states which could generate it.) The information returned is only in the most abstract information-theoretic sense. By repeating the read 52 times, you would gain enough information about the pool (4160 bits) to theoretically derive its "hidden" state, but it is not remotely computationally feasible to do so. Reading more than 52 times doesn't help, even 2^52 times. You still have to invert a truly hideous function and derive its 4096-bit input.
That is the cryptogrpahic problem which the security of /dev/urandom depends on, and it's a very difficult problem.
> the basic problem is that attackers are allowed to sample the pool at > unlimited speed. Provided that even a mediocre P5 can handle thousands of > read() requests per second, the information 'flux' should not be > underestimated.
The important thing is that it's information only in a Shannon sense. Once you pass 4096 bits of output, it's theoretically possible to derive the hidden internal state. It's just not remotely practicable. It's like deriving the key to a cipher from the cipher output. Even with a huge amount of output, a good cipher prevents you deriving the key.
A hash function is very much like a cipher, with the output being the ciphertext and the data hashed being the key.
> This is just like those timing based DES attacks (delta-attacks), even > (limited!) timing information gives away too much of internal state. Such > unlimited output IMO basically gives away the whole internal pool.
Please explain how. Let's make it simpler. Start with a pool of all zero bits. Then I'll add n bits of entropy, for any n you like less then 4096. Please explain how to derive anything about the internal pool with less than 2^n operations. (You may assume that reading the pool is free. You may also ignore the timestamp-adding effect of reading and change the perturbation of the pool by adding the hash back in to any other reasonable perturbation you like. Inputting a word of all zero is one possibility, or incrementing the last word in the pool, or incrementing the initial vector used for hashing.)
>> Not at all. First of all, notice what I said... just reading the pool is >> completely *harmless* unless you *do* something with the data that is read.
> oh yes, an attacker does.
Okay. It just wasn't clear that you were assuming this. For a while I thought you were under the misapprehension that as the entropy in the pool decreased towards zero, the output started approximating a constant function.
> it's not 'reading once an MD5 hash'. It's 'reading it unlimited times'. Do > you consider this safe, especially as victims use the very same interface > to get 'random data' as well?
Yes, I do consider it safe. (BTW, it's an SHA hash, but no matter.) -- -Colin
| |