Paper 2012/113

On the Collision and Preimage Security of MDC-4 in the Ideal Cipher Model

Bart Mennink


We present the first collision and preimage security analysis of MDC-4, a 24 years old construction for transforming an n-bit block cipher into a 2n-bit hash function. We start with the MDC-4 compression function based on two independent block ciphers, and prove that any adversary with query access to the underlying block ciphers requires at least 2^{5n/8} queries (asymptotically) to find a collision, and at least 2^{5n/4} queries to find a preimage. These results then directly carry over to the MDC-4 hash function design. Next, we consider MDC-4 based on one single block cipher, and confirm that the collision bound carries over to the single block cipher setting. In case of preimage resistance we present a more negative result: for a target image with the same left and right half, a MDC-4 preimage in the single block cipher setting can be found in approximately 2^n queries. Yet, restricted to target images with different left and right halves, the preimage security bound of 2^{5n/4} queries is nevertheless retained.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. To appear in Designs, Codes and Cryptography
MDC-4double block lengthhash functioncollision resistancepreimage resistance.
Contact author(s)
bart mennink @ esat kuleuven be
2013-04-02: last of 2 revisions
2012-02-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bart Mennink},
      title = {On the Collision and Preimage Security of MDC-4 in the Ideal Cipher Model},
      howpublished = {Cryptology ePrint Archive, Paper 2012/113},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.