Substitution-permutation networks resistant to differential and linear cryptanalysis

In this paper we examine a class of product ciphers referred to as substitution-permutation networks. We investigate the resistance of these cryptographic networks to two important attacks: differential cryptanalysis and linear cryptanalysis. In particular, we develop upper bounds on the differential characteristic probability and on the probability of a linear approximation as a function of the number of rounds of substitutions. Further, it is shown that using large S-boxes with good diffusion characteristics and replacing the permutation between rounds by an appropriate linear transformation is effective in improving the cipher security in relation to these two attacks.This work was supported by the Natural Sciences and Engineering Research Council of Canada and the Telecommunications Research Institute of Ontario, and was presented at the rump session of CRYPTO '93. Howard Heys is now with Electrical Engineering, Faculty of Engineering and Applied Science, Memorial University of Newfoundland, St. John's, Newfoundland, Canada A1B 3X5.