Paper 2025/2291

Key Recovery Attacks on ZIP Ciphers: Application to ZIP-AES and ZIP-GIFT

Abstract

The construction of building beyond-birthday-bound secure pseudorandom functions (PRFs) from the Xor-sum of 2 pseudorandom permutations (PRPs) has been known since EUROCRYPT 1998. However, the first concrete instance was only published recently at FSE 2022: the low-latency PRF Orthros. Subsequently, at ASIACRYPT 2024, Flórez-Gutiérrez et al. proposed the general framework of ZIP ciphers, where a block cipher $E_{1} \circ E_{0}$ is used to construct the PRF $E_{0} \oplus E_{1}^{-1}$. They propose the PRF ZIP-AES, as the Xor-sum of 5 AES encryption rounds and 5 decryption rounds. They discuss differential, linear, and integral distinguishers for this construction, but provide no concrete key recovery attacks. Furthermore, they propose ZIP-GIFT as a 64-bit PRF but leave cryptanalysis as future work. In this work, we provide the first third-party analysis of ZIP-AES and ZIP-GIFT. We investigate the challenges of applying classical cryptanalytic techniques to ZIP ciphers and discuss several adaptations needed for key recovery attacks in this setting. We show differential, linear, and integral key recovery attacks for both PRFs. In particular, we adapt integral key recovery techniques for ZIP ciphers, and show how to extend differential characteristics by some rounds for key recovery using truncated differential distinguishers. Our analysis deepens the understanding of the security of ZIP ciphers but does not threaten the security claims.