For Merkle-Damgård hashing, MD-compliant padding is defined as any padding scheme satisfying:

  1. $M$ is a prefix of $\text{Pad}(M)$
  2. $|M_1|=|M_2|\Rightarrow |\text{Pad}(M_1)|=|\text{Pad}(M_2)|$
  3. $|M_1|\neq |M_2|\Rightarrow $ last blocks of $\text{Pad}(M_1)$ and $\text{Pad}(M_2)$ differ

Some of these are more obviously necessary than others. I can see how different length messages having the last padding block could lead to collisions, for example. However, I'm struggling to see why all three of these are needed specifically though, so am looking for a quick example of an attack possible for each of the three cases where one of these is missing.

I know also that attacks are possible when any padded message is a suffix of another. Which of the three conditions prevents this, and why not include this as a condition directly?


1 Answer 1

  1. This is necessary since we want the padding at the end for performance reasons. We don't place it in the beginning or the middle since we may not have the means to process all the data. The end is the logical place.

  2. and 3. can be seen as an equivalence relation on the size of the messages. The padding is equal if their sizes are equal.

This is the core of the MD-strengthening ( length padding) due to the MOV attack ((see in Handbook of Applied Cryptography; Chapter 9, Example 9.23). The book is the first reference to this.

Therefore, 1. is for practical reasons, and 2-3 as for the countermeasure.

  • $\begingroup$ I'm reading requirement 2 as: "the paddings of equal-length messages are equal length", and this does not preclude random padding. I know a Menezes-Okamoto-Vanstone attack but it is not about MD-strengthening. $\endgroup$
    – fgrieu
    Commented May 11 at 16:39
  • $\begingroup$ @fgrieu you are right about 2. (edited) Yes the two MOV attacks conflict therefore needed a reference. It is first mentioned in the book as far as I know. $\endgroup$
    – kelalaka
    Commented May 11 at 17:03
  • $\begingroup$ I did not identify which MOV attack you are refering to. Chapter 9 of the HAC does not contain MOV in caps. $\endgroup$
    – fgrieu
    Commented May 11 at 17:11
  • 1
    $\begingroup$ @fgrieu A. Menezes, P. van Oorschot, and S. Vanstone (MOV) $\endgroup$
    – kelalaka
    Commented May 11 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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