Impossible Differential Attack On Feistel-2 Construction

Feistel construction is first presented by M. Luby and C. Rackoff in their paper’How to construct pseudorandom permutations from pseudorandom functions’[7] in 1988. Feistel construction is a method that used to build 2n-bit pseudo-random permutation by n-bit psuedo-randomfunction. In that paper, it used 3 or 4 rounds of Feistel network and used the pseudorandom functions as its round functions to build the pseudorandom permutations. The advan-tage of Feistel construction is that its structure to encryption and decryption is the same, in this way, we do not need to rewrite the decryption algorithm, so we save resource.I learn the method that used in the paper: ’meet-in-the-middle attacks on generic feistel constructions’[5] and’The security of Feistel ciphers with six rounds or less’[1]. They use the impossible differential method to attack the Feistel-2 construction. I use the five-round impossible differential characteristic (0, α)â†' (0, α) to analyze the six-round Feistel-2 construction, when k = n. In my analysis, I also use the method referenced in the paper:’Improved key recovery attacks on reduced-round AES in the single-key setting’[7]. The method is to use the information to squeeze the wrong key out. I also use the time-space trade-off method to reduce the time complexity. I store the input and output difference of the sixth round functuin in advance. In this way, the attack to six-round of Feistel-2 construction only needs 0.7×n×23n/4 plaintexts, and its time complexity is 0.7×n×23n/4 encryptions, its space comlpexity is 23n/4+2n/2+1 n/2-bit.Then.I use this method to attack the seven-round Feistel-2 construction when k=3n/2.The data complexity of this attack is 0.7×n×23n/4 plaintexts. The time complexity is 0.1×n×25n/4 seven-round encryptions. The space Complexity is 23n/4+3×2n/2 n/2-bit.I also use this method to attack the eight-round Feistel-2 construction when k = 2n.The data complexity of this attack is 0.7×n×23n/4 plaintexts.The time complexity is 0.7/4×n×27n/4 eight-round encryptions.The space complexity is 23n/4+2n/2+2 n/2-bit.