Improved integral cryptanalysis of block cipher Zodiac

Abstract Integral cryptanalysis is a pivotal technique in symmetric-key cryptography. This paper enhances the integral key-recovery analysis of the Feistel-based cipher Zodiac by introducing a systematic framework for identifying optimal key recovery attack paths. This framework leverages the conversion relationship between zero-correlation linear and integral distinguishers, seamlessly integrating distinguisher construction with key recovery into a coherent process. During the key recovery phase, we apply the partial-sum technique to reduce computational complexity and adaptively adjust the number of distinguisher rounds to optimize performance. We reduce the computational complexity of the full-round attack on Zodiac-192 from $$2^{190}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>190</mml:mn> </mml:msup> </mml:math> to $$2^{87}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>87</mml:mn> </mml:msup> </mml:math> . Our analysis also identifies two 14-round integral distinguishers: the longest known for Zodiac. Interestingly, we identify that the optimal full-round key recovery is achieved by pairing the partial-sum technique with the 13-round distinguisher, not the longer 14-round one. This result clearly demonstrates that the longest distinguisher does not guarantee the most efficient key recovery attack. Also we performed a non-standard extension (adding one round) on Zodiac, achieving the first 17-round key recovery attack on Zodiac-192.