Messages in this thread | | | Date | Wed, 15 Oct 1997 15:22:45 -0400 | From | "Theodore Y. Ts'o" <> | Subject | Re: 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
| |