Does MD5 generate 128 independent bits?

Question

I heard that there are 128 stochastically independent bits in an MD5 output. Is that true?

If so, are there any citations or proofs for that?

Answer 1

No, there are expressions relating input values which demonstrate extremely strong correlations between output bits. The output bits of of MD5 are not independent, particularly if the party supplying the input to MD5 chooses for them not to be.

These correlations are sufficiently powerful to enable the generation of completely identical output values rapidly on ordinary desktop systems. This would otherwise require a challenging amount of work (2^64), were MD5 an ideal random function.

Consider this visualization of an MD5 collision. Observe that even towards the end of the computation, near the output, the differences (red and green colors) have been largely confined to long vertical columns (which correspond directly to the output bits). Even after just one input block, a change to 3 input bits results in no change at all in 125/128 output bits rather than the 64/128 that would be expected by chance alone.

Answer 2

"Stochastically independent bits in an MD5 output" must be stated with some definition of what enters MD5. It is trivial to generate, by trial and error, MD5 inputs that generate MD5 output which right two bits are equal (hash incremental inputs, keep the ones matching that condition).

A more appropriate rephrasing of the question would be: is an adversary unable to perform a procedure that can distinguish, with odds better than 1/2

• n MD5 hashes of n distinct messages she chooses, except for a fixed unknown 128-bit random string at some fixed, agreed-upon point in the messages;

• n random 128-bit strings returned instead of the MD5 hashes in a similar experiment.

For input of less than 448 bit (which insures that there is a single MD5 round), at least the design rationale of MD5 is such that the answer to this rephrased question should be: YES (implying, in particular, that bits of MD5 are stochastically independent in this setup). The four internal rounds of the MD5 round function form a reversible block cipher with 512 bits key (padded message), 128 bit input (initial state), 128 bit output (before combination with the state). Any distinguisher on the output of MD5 (in our restricted setup) directly turns into a related-key weakness of that block cipher. If the MD5 block cipher was perfect, we could answer a conclusive YES.

The block cipher in MD5 may be far from perfect, but at least it is fairly decent. So at least, the adversary will face a though job.

Even better: it is implausible that the block cipher in MD5 could be broken without knowledge of its internal structure. It conclusively follows that any statistical test designed independently of MD5 will fail in our experiment! This illustrate the point that passing any standard statistical test is a very poor indication of the quality of a random number generator.

Answer 3

This depends on your input. If your input is random and at least of the output size, I would expect the output bits to be approximately independent. (There might not be a full independence, as likely some of the 2¹²⁸ combinations are not possible at all, while others occur more often, but the remaining dependence would be quite difficult to measure at all in our lifetime.)

Of course, if you consider only a quite small input domain, in the extreme case only two different inputs, there are only two different output values (of size 128 bits), and here you of course will be able to measure quite strong dependencies between the bits.

(This is the case for every cryptographic hash function, nothing MD5-specific here. Also, no proofs, sorry.)

Answer 4

Straight from a Google search:

http://www.ariadne.ac.uk/issue17/biblink/

MD5 refers to a type of hash function, i.e. a function that takes a variable length input and returns a fixed length output. The MD5 algorithm produces a digest of 128 stochastically independent bits that have no calculable relation to the original input, for this reason it is known as a 'message-digest' or 'checksum'.

http://mail-archives.apache.org/mod_mbox/httpd-dev/200009.mbox/%3C98.a792e2c.26fd89c9@aol.com%3E

MD5 is nothing but a 'one way' checksum applied to a block of data. The 128 stochastically independent bits the algo spits out have no calculable relation to the original input but they DO make for a good transport checksum even if you don't care about users.