lkml.org 
[lkml]   [1997]   [Oct]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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

\
 
 \ /
  Last update: 2005-03-22 13:40    [W:0.029 / U:0.392 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site