Paper 2012/113

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

Bart Mennink

Abstract

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.

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

BibTeX

@misc{cryptoeprint:2012/113,
      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{https://eprint.iacr.org/2012/113}},
      url = {https://eprint.iacr.org/2012/113}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.