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

in hexadecimal. Rotations α i , j depend on i and j mod 4 only and are defined as follows.

j mod 4

i 0 1 2 3

1 3 7 11 19

2 3 5 9 13

3 3 9 11 15

For instance, α 3 , 6 = 11.

In the dedicated attack we simplify MD4 by suppressing the final round, so that
we have two rounds instead of three. This example is meant to be illustrative only since
this does not lead to any attack against the full MD4 itself.

A useful building block for information diffusion in conventional cryptographic
primitives is the notion of multipermutation . 5 Intuitively, a multipermutation is a func-
tion with multiple inputs and multiple outputs with the property that modifying one
or several inputs of the function has the influence of modifying a maximal number
of outputs from the computation. Concretely, if a function f has p inputs and q out-
puts, modifying r inputs must have the influence of modifying at least q

− r + 1

outputs. For instance, if p = q = 4, modifying r inputs leads to modifying at least

5 r outputs. The linear transform M of MixColumns in the Advanced Encryp-

tion Standard (AES) has this property. If p

−

= q = 2, modifying r inputs leads to

modifying at least 3 − r outputs. The mixing box M of CS-CIPHER has this prop-

erty. If p = 3 and q = 1, modifying r = 1 input must lead to the modification of

the output. The f 1 and f 2 functions of MD4 do not have this property as shown

below.

Indeed, we observe that we can control modifications on a single input of f 1

or f 2 as follows. For any a , the function f 1 (11 ··· 1 , a , · ) is a constant equal to a .

The functions f 1 (00 ··· 0 , · , a ) and f 1 ( · , a , a ) have the same property. Similarly, the

functions f 2 ( a a ) have the same property. From these

properties we deduce that for any transformation box in the second round, if the main
input is 0, if the key input is

, a , · ), f 2 ( a , · , a ), and f 2 ( · , a ,

k 2 (the constant of the second round), and if two out of
the three other registers are 0, then the output remains 0.

−

σ 1 of the first round is in fact the identity permutation: the key
values are used in their original ordering. Therefore, provided that x 0 ,...,

The permutation

x 11 are fixed,
it is easy to choose x 12 , x 13 , and x 14 so that the content of the A , C , and D registers are
all 0 (see Fig. 3.8a).

5

Multipermutations were first proposed by Claus Schnorr and Serge Vaudenay (Ref. [162]). A more complete
study is available in Ref. [179].