| > You're letting your intuition about "usable randomness" run roughshod
| > over the formal definition of entropy. Taking bits out of the PRNG
| > *does* reduce its entropy.
|
| By how much exactly? I'd say, _under the hypothesis that the one-way
| function can't be broken and other attacks fail_, exactly zero; in the
| real world, maybe a little more. But in
| /usr/src/linux/drivers/char/random.c I see that the extract_entropy()
| function, directly called by the exported kernel interface
| get_random_bytes(), states:
|
| if (r->entropy_count / 8 >= nbytes)
| r->entropy_count -= nbytes*8;
| else
| r->entropy_count = 0;
|
| ...which appears to assume that the pool's entropy (the upper bound of
| which is POOLBITS, defined equal to 4096) drops by a figure equal to the
| number of bits that are extracted (nbytes*8). This would only make sense
| if those bits weren't passed through one-way hashing.
The argument you are making is that because the one-way function isn't
reversible, generating values from the pool using it doesn't decrease its
"computational" entropy. (Its mathematical entropy is certainly depleted,
since that doesn't involve computational difficulty. But we'll grant that
that doesn't matter.)
The problem with this argument is that it gives you no information about the
unpredictablity of the random numbers generated. Here's an algorithm based
on your argument:
Pool: bits[512]
initializePool()
{ Fill Pool with 512 random bits; }
getRandom() : bits[160]
{ return(SHA(bits));
}
By your argument, seeing the result of a call to getRandom() does not reduce
the effective entropy of the pool at all; it remains random. We certainly
believe that applying SHA to a random collection of bits produces a random
value. So, indeed, the result of getRandom() is ... random. It's also
constant.
Granted, no one would implement a random number generator this way. But
*why*? What is it you have to change to make this correct? Why? Can you
prove it? Just saying "you have to change the pool after every call"
won't work:
getRandom() : bits[160]
{ Rotate bits left by 1 bit;
return(SHA(bits));
}
This (seems to) generated 512 random values, then repeats. Just what *is*
good enough?
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
