The Collision Security of MDC-4

There are four somewhat classical double length block cipher based compression functions known:

MDC-2

,

MDC-4

,

Abreast-DM

, and

Tandem-DM

. They all have been developed over 20 years ago. In recent years, cryptographic research has put a focus on block cipher based hashing and found collision security results for three of them (

MDC-2

,

Abreast-DM

,

Tandem-DM

). In this paper, we add

MDC-4

, which is part of the IBM CLiC cryptographic module, to that list by showing that – ’instantiated’ using an ideal block cipher with 128 bit key/plaintext/ciphertext size – no adversary asking less than 2

74.76

queries can find a collision with probability greater than 1/2. This is the first result on the collision security of the hash function

MDC-4

.

The compression function

MDC-4

is created by interconnecting two

MDC-2

compression functions but only hashing one message block with them instead of two. The developers aim for

MDC-4

was to offer a higher security margin, when compared to

MDC-2

, but still being fast enough for practical purposes.

The

MDC-2

collision security proof of Steinberger (EUROCRYPT 2007) cannot be directly applied to

MDC-4

due to the structural differences. Although sharing many commonalities, our proof for

MDC-4

is much shorter and we claim that our presentation is also easier to grasp.