Paper 2021/819

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

Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, Yann Rotella, David Rupprecht, and Lukas Stennes

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2021
DOI
10.1007/978-3-030-77886-6_6
Keywords
GPRS EncryptionStream CipherAlgebraic attacksGEA
Contact author(s)
christof beierle @ rub de
patrick derbez @ irisa fr
gregor leander @ rub de
gaetan leurent @ inria fr
haavardr @ simula no
yann rotella @ uvsq fr
david rupprecht @ rub de
lukas stennes @ rub de
History
2021-06-16: received
Short URL
https://ia.cr/2021/819
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/819,
      author = {Christof Beierle and Patrick Derbez and Gregor Leander and Gaëtan Leurent and Håvard Raddum and Yann Rotella and David Rupprecht and Lukas Stennes},
      title = {Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2},
      howpublished = {Cryptology ePrint Archive, Paper 2021/819},
      year = {2021},
      doi = {10.1007/978-3-030-77886-6_6},
      note = {\url{https://eprint.iacr.org/2021/819}},
      url = {https://eprint.iacr.org/2021/819}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.