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 understand the need for padding in MD5. But why do we append the message length to the padding?

I heard it strengthens the hash but how?

Please provide an example if possible and how it applies to this quote:

The inclusion of the length-block effectively encodes all messages such that no encoded input is the tail end of any other encoded input.

Why a message being the tail of another message is bad (if it is)?

share|improve this question
1  
Source: uow.edu.au/~jennie/CSCI971/hash1.pdf –  Jan Dec 8 '11 at 21:11
add comment

migrated from stackoverflow.com Dec 10 '11 at 14:20

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

3 Answers

up vote 10 down vote accepted

MD5, like other hash functions, uses the Merkle-Damgard construction. You take the message and break it up into fixed-size blocks. You start with an intialization vector (IV), which you feed into a compression function along with the first block. Take the output (it will be the same length as the IV), and feed it into the compression function along with the second message block, and so on.

Call the compression function $c$ and the "raw" (unpadded) hash function $h$, we have $$ \begin{align*} h(ZABCD) &= c(h(ZABC), D) \\&= c(c(h(ZAB), C), D) \\&= c(c(c(h(ZA), B), C), D) \\&= c(c(c(c(h(Z), A), B), C), D) \\&= c(c(c(c(c(I,Z), A), B), C), D)\end{align*}$$ with a fixed initialization vector $I$ (each letter represents a block).

Different hash functions use different compression functions. The goal is to prove that we can find a collision in the hash function only if we can find a collision in the compression function (the next step would be to argue that finding a collision in the compression function is extremely difficult).

How would this argument work? We could restate our goal as follows:

If you give me two messages that cause a collision in the hash function, I can find two pairs of inputs for the compression function that cause a collision.

Here's how I do meet this goal: I take the two messages you give me, and split them into blocks. Then I find the right-most block that the two messages don't have in common. For example, if the first message (after padding) has blocks $ZABCD$ and the second has blocks $XKCD$, then third block from the right is different ($B$ vs. $K$).

Since $h(ZABCD) = h(XKCD)$, I check to see if $h(ZABC) = h(XKC)$. If not, I have my collision:

$$ h(ZABCD) = c(h(ZABC), D) = c(h(XKC), D) = h(XKCD). $$

On the other hand, if $h(ZABC) = h(XKC)$, this isn't really a collision for $c$, since the input values are the same. So I go back a block and see if $h(ZAB) = h(XK)$, and do the same thing. If they are not equal, I have a collision: $c(h(ZAB), C) = c(h(XK), C)$. If they are equal, I go back another block.

But now that $B \neq K$, I don't need to worry about whether or not $h(ZA) = h(X)$. I know that $c(h(ZA), B) = c(h(X), K)$ (because $h(ZAB) = h(XK))$, and since $B$ and $K$ are distinct, this is a collision – different inputs, same output.

I can go through this processes for any pair of inputs that generate a hash function collision in order to find a pair of inputs that cause a compression function collision. QED, right?

But wait!
What if when I go from right-to-left, I run out of blocks before I find two that are different? Then the argument breaks. So for the argument to work, I need my padding scheme to ensure that one (padded) message is never the tail end of another.

share|improve this answer
    
I will assume that i understand what your saying, but your assuming that we were able to obtain 2 messages with the same hash, and if we were able to achieve that then why would we need to further prove that the compression function if bad ? what would that give us or prove, what's your point ? –  AB Najjar Dec 9 '11 at 23:08
1  
No, if one message is the tail end of another, they won't necessarily collide. I don't know how the IV was chosen (my first guess would be someone chose it randomly), but the compression function for MD5 is a Davies–Meyer construction; see (en.wikipedia.org/wiki/One-way_compression_function); the internal H, G, F, I functions are actually implementing a block cipher. So I suspect that if you want to learn the motivation for these functions, you'd have to study the construction of block ciphers. Modern crypto generally follows this pattern: build complex things from simple ones. –  Seth Dec 10 '11 at 4:19
3  
@fgrieu I think the point is that we want to avoid ABCD to hash to the same thing as XYZABCD (each letter being one block), when the internal state after hashing XYZ is the initialization vector again. This would be the "running out of blocks" mentioned there. The simple 10000... padding would do nothing here, it just helps against the simplest appending attacks. –  Paŭlo Ebermann Dec 10 '11 at 16:37
2  
@fgrieu (Both @Paŭlo and @Paulo work to ping me ... just use whatever the auto-completion proposes, or what is more easy for you to type.) I think this depends on the definition of collision for a compression function - if every $c(x_1,y_1) = c(x_2,y_2)$ with $(x_1, y_1) \neq (x_2, y_2)$ counts, then there really must be some collision in $c$ (or a "tail-of-message" with a preimage to $I$, as mentioned before). And this seems to be the idea of the proof in the answer. (Of course there must exist some collisions, the problem is just how to find them.) –  Paŭlo Ebermann Dec 10 '11 at 18:40
1  
Got it. If we consider a collision in the full hash, the length allows to exhibit a collision on $c$ [as in $c(x_i,y_i) = c(x_j,y_j)$ with $(x_i, y_i) \neq (x_j, y_j)$], including in the branch of the demonstration where we consider messages of different length (that collision must exist in the last block). Without the length in the padding, it could be that in the longer message, $x_0$ was hit at some point, and we can only exhibit $c(x_i, y_i) = x_0$; which would be a devastating blow to $c$, but not a collision. –  fgrieu Dec 11 '11 at 7:13
show 8 more comments

The Merkle–Damgård hash construction customarily pads the message $M$ to be hashed with a single bit set to 1, a minimal number of bit(s) set to 0, and the representation of the length of the message in binary over some fixed number of bits. The padded message is then formed of a number of blocks $B_i$. The hash is computed by repeatedly applying a compression function $C$: $(X,B)\rightarrow C(X,B)$, giving $$H(M)=C(C(..C(C(IV,B_0),B_1)..B_{k-2}),B_{k-1})$$

Question is: Why pad with the length? Is not that redundant with the bit(s) added before?

Having the length in the padding allows a simple security proof: full hash collision between two known distinct messages allows exhibiting a collision in the underlying compression function $C$, that is exhibiting $X,B,X',B'$ with $C(X,B)=C(X',B')$ and $(X,B)\ne (X',B')$.

The proof sketch goes:

  1. if the distinct colliding messages are of different length, then a collision in $C$ occurs in the last block: we know $B_{k-1},B'_{k-1}$ are distinct since they contain the length;
  2. if the distinct colliding messages are of the same length, then there is a well defined rightmost block where the padded messages differ, and when we scan for a collision in $C$ from the right of the padded message up to that block, we exhibit a collision.

Without the length in the padding, we can still have a security proof, but with stronger hypothesis on $C$: full hash collision between two known distinct messages allows exhibiting either a collision in $C$ as above, or exhibiting a pre-image for the $IV$ constant given in the definition of the hash, that is exhibiting $X,B$ with $C(X,B)=IV$. The proof is more complex: we must subdivide case 1 depending on if the messages have the same padded length, or not; in the negative further subdivide depending on if the shortest padded message matches the end of the longest one, or not; in the affirmative, we do not get a collision, but rather a preimage of $IV$.

This later proof is quite tight. Without length in the padding, and with the IV replaced by a constant of unknown origin, an explicit attack is possible, as follows. Consider a hash variant similar to MD5 or SHA-256, with these two differences:

  • length is removed from the padding (which becomes: a single bit set to 1, then just enough bit(s) set to 0 in order to fill the final 512-bit block);
  • the $IV$ is some random-looking value (rather than made from increasing hex digits in MD5, or the fractional part of the square root of the first 8 primes in SHA-256).

The compression function $C$ used in MD5 and SHA-256 is of the form $$(X,K)\rightarrow C(X,K)=X\oplus E(X,K)$$ where $\oplus$ is a variant of addition (with a few carries suppressed), and $X\rightarrow E(X,K)$ is a reversible block cipher with key $K$.

Who defined the $IV$ could have chosen a secret 512-bit $K$, computed $IV = E^{-1}(0,K)$, which insures $IV=C(IV,K)$, and thus allows insertion of $K$ at the beginning of any message, without changing the hash.

Summary: the length allows a simpler and tighter security proof. As far as I can tell, it is not indispensable, provided that the compression function $C$ is preimage-resistant, and the $IV$ is chosen without reference to $C$.

[This new answer has nothing to do with my earlier attempt, and is strongly inspired by Seth's earlier answer]

share|improve this answer
    
Nice summary of the comments to the other answer, thanks. –  Paŭlo Ebermann Dec 11 '11 at 14:02
    
Well written, and addresses points I should I have mentioned. –  Seth Dec 11 '11 at 20:56
add comment

There is a beautiful characterization for the collision preserving padding rule of any Merkle–Damgård-construction: the padding rule should be suffix free. See the 2009 paper Characterizing Padding Rules of MD Hash Functions Preserving Collision Security by Mridul Nandi for more details.

The length of the message, as it turns out to be, is the simplest form of padding which is suffix free. The proof in the paper is self contained and very easy to understand, so I am not putting forward the sketch of the proof.

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.