Differential cryptanalysis of Feistel ciphers and differentially uniform mappings

Anne Canteaut

BP 105
78153 Le Chesnay Cedex, France

Selected Areas on Cryptography, SAC'97 , pages 172-184, 1997.


In this paper we study the round permutations (or S-boxes) which provide to Feistel ciphers the best resistance against differential cryptanalysis. We prove that a Feistel cipher with any round keys and with at least 5 rounds resists any differential attack if its round permutation is differentially d-uniform for a small d. This improves an earlier result due to Nyberg and Knudsen which only held for independent and uniformly random round keys. We also give some necessary conditions for a mapping to be almost perfect nonlinear (i.e differentially 2-uniform).