On the need for multipermutations: cryptanalysis of MD4 and SAFER

Cryptographic primitives are usually based on a network with boxes. Schnorr and Vaudenay (1994) claimed that all boxes should be multipermutations. In this paper 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

Published in:
Second International Workshop on Fast Software Encryption, FSE '94, 1008, 286-297
Presented at:
Second International Workshop on Fast Software Encryption, FSE '94, Leuven, Belgium, 14-16 December 1994

 Record created 2007-01-18, last modified 2018-03-17

Download fulltextPS
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)