Higher Order Integral Cryptanalysis of Zodiac

This paper mainly focuses on the security of Zodiac against integral cryptanalysis. Firstly, a systematic method is given to extend an integral distinguisher of Feistel ciphers with PS or SP round functions into a higher order integral distinguisher. Secondly, this method is applied to Zodiac, and a full-round (16-round) integral distinguisher is given. Taking the properties of the linear transformation into consideration, it is showed that extending an integral distinguisher into a higher order one can be reduced into decomposition of linear spaces into direct sums. At last, some key-recovery attacks against full round Zodiac are applied using distinguishers with 15-/13round, respectively.