Improved Square Attack On Zodiac And Equivalence Of Impossible Differential And Zero Correlation

Zodiac cipher is a Feistel structure block cipher which is designed by some Korean experts.It supports 3 master key lengths which are called Zodiac-128, Zodiac-192 and Zodiac-256,respectively. It has been analyzed by a lot of experts until now and the most efficient result is the impossible differential cryptanalysis of Zodiac published by Mohsen Shakiba and other Iran experts in 2009. As one of the most efficient cryptanalysis of AES, square attack has not got ideal result on Zodiac and it is even invalid on Zodiac-128, which urges us to improve the square attack on Zodiac.We utilize a 9-round distinguisher of Zodiac in this paper, and we add 2 rounds before this distinguisher and 5 rounds after, thus we analyze the full-round Zodiac. We guess 4 bytes less than previous square attack. Through analyzing 232 plaintexts, the time complexity decreases to 2157.25 full-round encryptions, which is 2-32.75 of previous time complexity.Zero correlation linear cryptanalysis has provided powerful tool to analyze block ciphers and new guarantee on the security of block ciphers. There are some similarities between them. Impossible differential cryptanalysis utilizes zero-probability differentials and zero correlation linear cryptanalysis utilizes zero-colleration linear approximations. Since these basic ideas are similar, naturally we focus on whether there are certain equivalent relations between them, including whether there exists same round distinguisher and how con-vert one kind of distinguisher to the other one. In this paper we discuss the equivalence between the distinguishers of the two cryptanalysis of block ci-phers and simplified the conditions of the equivalence. We have to consider the whole round function to analyze the equivalence before, but now we can only analyze the F-function, which sharply decrease the time complexity. We only need to find a permutation matrix F that satisfies F=H·FT·H-1 or F=H·(FT)-1·H-1(F expresses the matrix representation of F-function, FT expresses the matrix representation of F-function in zero correlation crypt-analysis), thus we can get the equivalence between impossible differential dis-tinguishers and zero correlation distinguishers. According to the equivalence we can convert an impossible differential distinguisher(zero correlation dis-tinguisher) into an zero correlation distinguisher(mpossible differential distin-guisher), what’s more, they are same round.