From Wikipedia, the free encyclopedia
Jump to: navigation, search

This is denoted as .

MD-compliant padding[edit]

As mentioned in the introduction, the padding scheme used in the Merkle–Damgård construction must be chosen carefully to ensure the security of the scheme. Mihir Bellare gives sufficient conditions for a padding scheme to possess to ensure that the MD construction is secure: the scheme must be "MD-compliant" (the original length-padding scheme used by Merkle is an example of MD-compliant padding).[1]:145 Conditions:

  • is a prefix of .
  • If then .
  • If then the last block of is different from the last block of .

With these conditions in place, we find a collision in the MD hash function exactly when we find a collision in the underlying compression function. Therefore, the Merkle–Damgård construction is provably secure when the underlying compression function is secure. [1]:147



  1. ^ a b c Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001