Impossible Differential Cryptanalysis on Feistel Ciphers with SP and SPS Round Functions

摘要

Impossible differential cryptanalysis is well known to be effective in analyzing the security of block ciphers. Known result shows that there always exists 5-round impossible differentials of a Feistel cipher with bijective round function. However, if more details of the round function are known, the result could be improved. This paper mainly studies the impossible differentials of Feistel ciphers with both SP and SPS round functions where the linear transformation P is defined over (F_2)~(n×n)). For Feistel ciphers with SP round functions, any column of P {direct +} P~(-1) whose Hamming weight is greater than 1 corresponds to some 6-round impossible differentials. The existence of some 7-round impossible differentials can be determined by counting the times that 1 appears at some special positions of P and P~(-1). Some 8-round impossible differentials can be found by computing the rank of some sub-matrix of P. Impossible differentials of Camellia found by these techniques are well consistent with previously known results. For Feistel ciphers with SPS round functions, by determining the rank of some sub-matrix of P, 6-round impossible differentials can be found, which improves the results on E2 by one round. These results tell that when designing a Feistel cipher with SP or SPS round function where the diffusion layer is selected from (F_2)~(n×n)), the linear transformation should be chosen carefully to make the cipher secure against impossible differential cryptanalysis.