# Different padding rules for Merkle–Damgård and Keccak/sponge function

We learned that length padding was used in Merkle–Damgård where after padding with zeros another block is added that contains the initial length of the input. This is supposed to prevent same hash values for the different inputs $x \ne x0..0$.

Then again for Keccak we learned it is possible to use simple padding (e.g. add $10..0$). Why is that possible for sponge functions? Isn't it still possible to find two different inputs that will be padded to the same value and then deliver the same hash?

-
The Keccak padding is actually 10*1, I think. – otus Jul 23 '14 at 20:27
Okay, we were taught there are multiple possible padding schemes. But my question remains the same. If one message is the suffix of another, how can they be destinguished after padding? – CGFoX Jul 23 '14 at 20:29
... by their length and probably also by what they start with. $\;$ – Ricky Demer Jul 24 '14 at 2:59

Actually, the Merkle–Damgård construction also specifies a padding bit after the message. The length is there the ensure that a padded message cannot be the suffix of a different longer message. A collision at the prefix leads to a collision in both messages.

With a padding bit, a singe byte message 0x30 vs a 2 byte message 0x30 0x00 are padded to 0x30 0x80 and 0x30 0x00 0x80, ensuring the compression function input is not the same for that block, even without the message length at the end of the padding.

The sponge construction does not require the same message suffix protection because of the way it mixes the input into the state. The size of the state as well as how much data is mixed/squeezed (block size) determine the chance of both a state collision as well as an output collision.

### Example collision over multiple blocks

Here we have a toy hash function with a 48-bit block size and 48-bit internal state size. It has no length padding, but does use a single bit padding after the message. The hash is not secure, and suffers from a collision between "THIS IS NOT " and "ENACT ", which are unpadded 2 block and 1 block inputs to the compression function:

Message 1 "THIS IS NOT A TEST!", length 19 bytes (152 bits):

initial value     Block 1 "THIS I"  Block 2 "S NOT "
0x67452301AB89    0x544849532049    0x53204E4F5420

** state collision here **

Block 3 "A TEST"  Block 4 "!" and padding bit
0x412054455354    0x218000000000

Hash Output
0xFE25B6A1C8C0


Message 2 "ENACT A TEST!", length 13 bytes (104 bits):

initial value     Block 1 "ENACT "
0x67452301AB89    0x544849532049

** state collision here **

Block 2 "A TEST"  Block 3 "!" and padding bit
0x412054455354    0x218000000000

Hash Output
0xFE25B6A1C8C0


Because the last 2 input blocks are the same and (since the padding is the same), the state collision at the unpadded prefixes causes a collision in the outputs.

We modify the hash function to add the length; we save the final 2 bytes of space for the length, for a 65535 bit message length limit:

Message 1 "THIS IS NOT A TEST", length 19 bytes (152 bits):

initial value     Block 1 "THIS I"  Block 2 "S NOT "
0x67452301AB89    0x544849532049    0x53204E4F5420

** state collision here **

Block 3 "A TEST"  Block 4 "!" and padding bit and length
0x412054455354    0x218000000098

Hash Output
0x7F266204EDAF


Message 2 "ENACT A TEST", length 13 bytes (104 bits):

initial value     Block 1 "ENACT "
0x67452301AB89    0x544849532049

** state collision here **

Block 2 "A TEST"  Block 3 "!" and padding bit and length
0x412054455354    0x218000000068

Hash Output
0xE7D693B5011B


Once the length is added to the padding, it prevents this from happening in the output, even though there is a state collision. As above, the padding bit 1 prevents near identical messages with different lengths of trailing 0 bits from being processed the same way in the compression function, which will cause a collision at the block level.

Keccak uses a much larger state and block size, say 1600-bits and 1088-bits (for a 256-bit hash). The chance of an internal state collision is much less than the security provided by the hash size, so a length is not required. Not having a length padding also simplifies implementations, since you do not need to keep track of the data you are processing. The padding bit 1 is still required for the same reason as an MD hash. The final padding bit (in 10*1) is required to prevent identical messages from causing a collision when the sponge rate is different, this would not be required if the rate was fixed.

For most MD hashes, the state and output are the same, with a larger block size, this means the chance of a state collision is most likely higher than the specified security level of the hash, hence the strengthening by adding the length.

-
Hm, I don't think I completely understand. If I have to messages that are identical, but one is shorter than the other. And then after the padding they look the same. How can any hash function possible calculate different hash values for that? – CGFoX Jul 23 '14 at 20:31
@CGFoX: you can't have two distinct messages that pad into the same. For example, if one message (in binary) was 101101 and the other was 10110100, the first would pad to 101101100000, and the second would pad to 101101001000 -- they don't look the same. – poncho Jul 23 '14 at 22:05
@CGFoX I will edit my answer with an example – Richie Frame Jul 24 '14 at 1:40

Isn't it still possible to find two different inputs that will be padded to the same value and then deliver the same hash?

Well, no, it isn't. Given a padded message (that is, padded by adding a 1 bit, and then as many 0 bits as needed to fill it out to a multiple of the internal block size), we can unambiguously recover the original message -- by stripping off all the zeros, and the last 1.

So, why does Merkle-Damgard insert the length the message length into the last block, while Keccak doesn't? Well, remember that Merkle-Damgard has a relatively small internal state. I suspect that they were worried about someone finding a fixed point for the compression function; that is, if we were at state $S_i$, and we found a message block $M$ such that $S_{i+1} = Compress_M( S_i ) = S_i$, then we can generate a collision by either inserting or not inserting the message block $M$ right there. And, it's easy to find such state/message block pairs -- what's tough is finding previous message blocks that would take us to state $S_i$. However, they appear to be reluctant to rely on the hardness of that problem -- hence they void the attack by inserting the message length in the final block.

Now, sponge hash functions have much larger internal states, and so the worry about finding a duplicate such as above is much less.

-
No, we can't just strip off al zeros and the last 1. Because what if the input already has an apropriate length, but still ends with a 1 and zeros? How would you know which digits belong to the padding and which to the original message? – CGFoX Jul 23 '14 at 20:25
@CGFoX: we always add precisely one 1, and then add zeros; if the input ended with a '1' bit (or '0x01' byte), we'll still pad by adding a '1' bit (or, if we're dealing with bytes, an 0x80 0x00 0x00 ... 0x00 pattern) – poncho Jul 23 '14 at 20:29
Oh ok, so even if a message has the appropriate length we still add a 1 and then as many zeros as needed? Then why is it not possible to do that for Merkle-Damgard? – CGFoX Jul 23 '14 at 20:33
@CGFoX: it is (and, in fact, they do -- they just add a length field as well). However, I believe that the original MD designers may have been afraid that wasn't sufficient -- that if somewhere were to find a fixed point, then it would allow a collision (and the length field would invalidate that). – poncho Jul 23 '14 at 22:03