[lkml]   [1997]   [Oct]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: monitoring entropy
OK, let me try to explain some of these issues.

First of all, consider how the MD5 or SHA hash function works. (We're
using SHA, not MD5, but at a high level they have the same interface).
It takes some large amount of data, in blocks of 64 bytes, and produces
16 (or in the SHA 20) bytes of hash output.

Since the size of the input type is much larger than the output type,
there will of course be many cases where two input texts, X and X'
produce the same MD5 or SHA checksum. The design criteria of a crypto
checksum like MD5 or SHA is this:

* Given some input text X, there is no method better than brute
force guessing of finding another input text X' which
has MD5/SHA checksum as X. (Where brute force guessing
will take 2**64 tries for MD5, and 2**80 tries for SHA.)

* Given some MD5/SHA checksum C, there is no method better than
brute force guessing of finding some input text X where
f(X) == C.

Since it is considered extremely hard (2**64 is a very large number),
all you need to do in order to "prove" that MD5 is broken is to present
two input texts which hash to the same MD5 value.

Now, we're not using SHA in a traditional way a crypto checksum gets
used, though. Here, we have a pool which contains 4096 bits. At the
simplest level (taking out all of the other design tricks which makes
life *harder*), Each time we want to extract 40 bits of entropy, we
compute the hash of the entire pool, which for SHA is 80 bits. We then
fold the result in half using XOR, and so we only end up revealing 40
bits of information about the actual hash value of the pool. The
original hash value is then mixed into the pool using a Generalized
Feedback Shift Register.

Now then, "breaking" the generator involves trying to figure out the
internal state of the entropy pool given only the output from the random
number generator. To analyze the worst case, we assume that we're not
getting any additional input into the entropy pool from interrupts, etc.

Obviously, if you only know 40 bits of information generated from a
single extract operation, there's not enough information to deduce the
state of the 4096 bit pool. And even with MD5, no one has managed how
to devise an algorithm which can find a *single* candidate input text
which when hashed produces a particular hash value. Here, the attacker
only knows half the information of the hash value, and it doesn't matter
if the attacker can find some particular input text value; the attack
has the find the *right* input text value which corresponds to the
entropy pool.

Hence, even if someone were to announce that they had broken MD5 or SHA,
they still would not have necessarily broken the random number
generator, even if you give them the simplest version of the problem
with a lobotimized random number generator as described above.

Obviously, someone wouldn't have a prayer of even trying to break the
output of the random number generator unless they had obtained at least
4096 bits. That's simply a matter of phyics --- or in this case,
mathematics. But that's assuming that the mixing and hashing process
was "perfect" in that each time it revealed 40 bits of new information
about the original hash pool state.

Hence, this is almost certainly much, much harder than doing a
traditional cryptoanlysis on a cipher key. A brute force attack would
involve trying every single permutation of the original 4096 entropy
pool to see if you can find the one which generates the random stream.
This would take on average 2**2048 tries, which is a very, very, very,
large number. It may be possible to find a correlation attack which
would take less time, but certainly no one has derived one to date, and
doing so would require a theoretical breakthrough that would render SHA
useless as a cryptographic hash function. (In fact, it would probably
require several theoretical breakthroughs, of which the first one would
render SHA useless.) While this could happen, I suspect it is fairly
unlikely that it will.

- Ted

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