Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 74

Since E ( D ) tends toward a constant, it is negligible compared to α N . Since V ( D ) tends

toward a constant, this probability tends toward zero.

To summarize, when using a hash function which hashes down to n bits, brute
force attacks have the following complexities.

Preimage attacks (first and second preimage attacks) have complexity 2 n .
Collision attacks have complexity 2 2 .

3.3 A Dedicated Attack on MD4

The birthday paradox provides a generic way to attack hash functions in order to forge
collisions. These generic attacks are always possible, and their complexity depends on
the output size. For MD5, the output hash length is of 128 bits, so birthday-paradox-
based attacks have a complexity of the order of 2 64 . The ideal goal of conventional
cryptographic primitives is to have no better attacks.

However, the particular design of some primitives may lead to some dedicated
attacks. Here we exhibit an attack of this type against a simplified version of MD4.

MD4 is a hash function which is similar to MD5, but with the following differ-
ences. 4

MD4 has three rounds (instead of four for MD5).

f 2 is defined by
f 2 ( b ( b AND c )OR( c AND d )OR( d AND b )

which is the majority function.
The output of the transformation box does not add b any more.

, c , d ) =

The MD4 permutations are defined as follows.

0123456789101112131415
0123456789101112131415

σ 1 =

012 3 456 7 89101112131415
0481215913261014 3 7 1115

σ 2 =

0123456789 0 1 2 3 4 5
0841221061419 5 13 3 11 7 15

σ 3 =

This means, e.g., that σ 2 (8) = 2. The constants k i , j actually do not depend on j and

are defined by

k 1 = 0 , k 2 = , k 3 =

5a827999 6ed9eba1

4

MD4 was presented at the CRYPTO'90 conference. See Ref. [156].