Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Aug 26 '11 at 11:17

This question came from our site for professional and enthusiast programmers.

add comment

4 Answers 4

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
This does only give some "assertions" about this independence, no proofs, sadly. –  Paŭlo Ebermann Aug 26 '11 at 16:23
add comment

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 2128 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.)

share|improve this answer
    
Hmm, if the input is "random and at least of the output size" even the identity function achieves independence among the output bits. Is that a reasonable constraint for any useful interpretation of the question? The other extreme of two inputs seems like a better interpretation for crypto.se. An adversarial environment probably needs to be concerned with the worst case. –  Marsh Ray Aug 26 '11 at 17:39
    
@Marsh: This is a good point ... I'm not sure what would be a better definition of independent bits in the output. Do you have a proposal? Stochastic independence is always measured over some probability space. –  Paŭlo Ebermann Aug 26 '11 at 17:48
    
I'm far from an expert on this topic, but it seems to me that MD5 is completely deterministic, so when does it even make sense to ask about its stochastic properties? E.g., maybe in an attack context we could state something in terms of the absence of any (tractable) expression to constrain the input domain only slightly but that significantly modifies the distribution of some expression made from the output (or output and input) bits. –  Marsh Ray Aug 26 '11 at 18:30
    
All cryptographic algorithms are deterministic (if we include any seeds/states of PRNGs into the input), yet still people assert that output bits of certain functions are independent (see the answer by RustyTheBoyRobot). Stochastic properties are only seen compared to some random distribution of the input space. (I'm also not an expert here, though.) –  Paŭlo Ebermann Aug 26 '11 at 18:46
add comment

"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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.