Yinuo Liu
Information Engineering University, Zhengzhou, China; State Key Laboratory of Cryptology, Beijing, China

Tian Tian
Information Engineering University, Zhengzhou, China

Jing Yang
Information Engineering University, Zhengzhou, China

Keywords: Multidimensional Linear Cryptanalysis, AEGIS, LOL, Rocca

Abstract

AEGIS is a family of authenticated encryption with associated data (AEAD) ciphers targeting highly efficient software implementations. Its main operation is the AES encryption round function, enabling it to leverage both strong cryptographic properties and efficient implementation. AEGIS includes the variants AEGIS-128, AEGIS-128L, and AEGIS-256, which target 128, 128, and 256 bits of security, respectively. AEGIS-128 was selected for the final portfolio of the CAESAR competition. In this paper, we perform multidimensional linear cryptanalysis of AEGIS. We first identify the reason for the inconsistency between byte and bit trails in AEGIS and propose an improved truncated model to derive the accurate minimum number of active S-boxes efficiently. Based on the resulting byte trails, we perform deep theoretical analysis of correlation propagation in AEGIS and derive linear approximations with high correlations. We also uncover structural properties that yield multiple equivalent but independent linear approximations. By combining them, we obtain multidimensional linear distinguishing attacks on AEGIS-128, AEGIS-256, and AEGIS-128L with complexities 2^126.46, 2^154.11, and 2^144.44, respectively. These results suggest that AEGIS-128 and AEGIS-256 do not meet their security claims. We also apply the improved truncated model to the AES-based stream cipher families LOL and Rocca, including a fast correlation attack on LOL-MINI that breaks its claimed security if one ignores the keystream-length restriction for a single key and IV.