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
-
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},
url = {https://eprint.iacr.org/2012/113}
}
