On the need for multipermutations: Cryptanalysis of MD4 and SAFER

Cryptographic primitives are usually based on a network with boxes. At EUROCRYPT'94, Schnorr and the author of this paper claimed that all boxes should be multipermutations. Here, we investigate a few combinatorial properties of multipermutations. We argue that boxes which fail to be multipermutations can open the way to unsuspected attacks. We illustrate this statement with two examples.Firstly, we show how to construct collisions to MD4 restricted to its first two rounds. This allows one to forge digests close to each other using the full compression function of MD4. Secondly, we show that variants of SAFER are subject to attack faster than exhaustive search in 6.1% cases. This attack can be implemented if we decrease the number of rounds from 6 to 4.