Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2

Christof Beierle (1) , Patrick Derbez (2, 3, 4, 5) , Gregor Leander (1) , Gaëtan Leurent (6) , Håvard Raddum (7) , Yann Rotella (8, 9, 3, 10) , David Rupprecht (1) , Lukas Stennes (1)

1 RUB - Ruhr University Bochum = Ruhr-Universität Bochum
2 UR - Université de Rennes
3 CNRS - Centre National de la Recherche Scientifique
4 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires
5 EMSEC - Embedded Security and Cryptography / Sécurité cryptographie embarquée
6 COSMIQ - Cryptologie symétrique, cryptologie fondée sur les codes et information quantique
7 UiB - Department of Informatics [Bergen]
8 Université Paris-Saclay
9 UVSQ - Université de Versailles Saint-Quentin-en-Yvelines
10 LMV - Laboratoire de Mathématiques de Versailles

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time $2^{40}$ GEA-1 evaluations and using 44.5 GiB of memory. The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design. In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time $2^{45.1}$ GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

Mots clés: GPRS Encryption; Stream Cipher; Algebraic attacks; GEA

Domaines: Cryptographie et sécurité [cs.CR]

Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, et al.. Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2. EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Oct 2021, Zagreb, Croatia. pp.155-183, ⟨10.1007/978-3-030-77886-6_6⟩. ⟨hal-03529373⟩