A Study Of Problems In Impossible Differential Cryptanalysis

Impossible differential cryptanalysis is a kind of variation of differential crypt-analysis. While ordinary differential cryptanalysis tracks differences that propagatethrough the cipher with greater than expected probability, impossible differential crypt-analysis exploits differences that are impossible at some intermediate state of the ci-pher algorithm. Due to its simple cryptanalysis process and effectiveness to manyblock ciphers, impossible differential cryptanalysis received much attention. AfterKnudsen and Biham raised the idea of the attack, a lot of good cryptanalysis re-sults have been published, including attacks of famous block ciphers such as AESand IDEA.In this paper, we systematically reanalyzed the rationales and process of impos-sible differential cryptanalysis, and summarized the state-of-the-art of researches onit. Inspired by U-method, we proposed a new method of automatically retrieving theimpossible differential characteristics of block ciphers, and applied it on many popu-lar block ciphers and structures. Furthermore, by using the techniques of impossibledifferential attack, we reanalyzed the FOX block cipher. We found a 2-round pseudo-randomness distinguisher and a 3-round strong pseudorandomness distinguisher, so asto prove that 3-round and 4-round is the necessary condition for Lai-Massey structureto achieve the pseudorandomness and strong pseudorandomness. We also found a 4-round impossible differential characteristic. By using it, an adversary can attack 5, 6and 7-round FOX64 with 269, 2133 and 2197 encryptions respectively. which improvedthe best known attacks by a factor of 240.4. This attack can be extended to 5-roundFOX128 with 2133 encryptions.