On Constructing Impossible Differential Distinguishers

Impossible differential cryptanalysis is one of the most powerful attacks against blockcipher, and the key step of this cryptanalysis is to find out the longest impossible differentials.The length of impossible differentials can also be treated as a measurement against impossibledifferential cryptanalysis. This paper works on constructing impossible differentials for blockcipher structures, and our main contribution includes:1. This paper studies the impossible differential property for SP structures. For the first time,we provide a necessary and sufficient condition of the existence of impossible differentials in SPstructure, then we provide a method to search out all impossible differentials in SPN, by whichwe can find the longest impossible differentials in SP structure. As a special example, we provethat impossible diffentials in AES can not exceed4rounds, and we prove that if the SP structureemploies MDS matrix as the P layer, we can never find impossible differentials longer than2rounds. This paper is helpful in measuring the immunity against impossible cryptanalysis for SPstructure.2. We study on the impossible differential properties for some popular generalized Feistelstructures. We provide the longest impossible differentials for m-dataline Skipjack-likestructure, CAST256-like structure and MARS-like structure. Compare with the existed results,our results improve2, m1and m1rounds for each structure respectively. Besides, westudy on the impossible differential properties for New-Structure I~IV, and we provide14rounds, infinite rounds,16rounds and19rounds impossible differentials for these structuresrepectively. Our investigation enriches the security results of generalized Feistel structures.3We propose the solution-tag method to find impossible differentials of generalized Feistelstructures. This method has no restrict on neither the overall structure nor the round function,compare with traditional methods, we can find longer impossible differentials of somewell-known block cipher structures with SP round functions. Later, we point that there exsitsdifferential-linear conjugation relationships between overall structures, by this property, thesolution-tag method can be used to find zero-corollaries for some block cipher structures.4. We analyze the security of VGF2structure, which was proposed in Inscrypt2009, wepointed that there exists1-probability differential in arbitrary rounds VGF2, also we proved thatthere exists impossible differential for arbitrary rounds VGF2. Sequentially, we launch areal-time ciphertext-only attack on the full round block cipher VGF2, this attack can obtain halfbits of the plaintext without calculate the key. And we further find a collision for VGF2-basedCBC-like MAC within264MAC operations and successful rate reaches0.392. We also launcha universal forgery attack on VGF2-based CBC-like MAC, in the attack, we need2128times MAC operations and the successful rate reaches1.5. This paper investigates impossible properties of FOX-like structure. And prove that thereexist new4rounds impossible differentials in FOX-like structure, which do not depend on thestrength of the round function or the orthomorphic permutation. Also, we provide the method forfinding5rounds impossible differentials in FOX-like structure with SP-based round function.