Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / MDC-4; double block length; hash function; collision resistance; preimage resistance.

Publication Info: To appear in Designs, Codes and Cryptography

Date: received 29 Feb 2012, last revised 2 Apr 2013

Contact author: bart mennink at esat kuleuven be

Available formats: PDF | BibTeX Citation

Version: 20130402:174358 (All versions of this report)

Discussion forum: Show discussion | Start new discussion