Paper 2022/424

Refined Cryptanalysis of the GPRS Ciphers GEA-1 and GEA-2

Dor Amzaleg and Itai Dinur

Abstract

At EUROCRYPT~2021, Beierle et al. presented the first public analysis of the GPRS ciphers GEA-1 and GEA-2. They showed that although GEA-1 uses a 64-bit session key, it can be recovered with the knowledge of only 65 bits of keystream in time $2^{40}$ using $44$ GiB of memory. The attack exploits a weakness in the initialization process of the cipher that was presumably hidden intentionally by the designers to reduce its security. While no such weakness was found for GEA-2, the authors presented an attack on this cipher with time complexity of about $2^{45}$. The main practical obstacle is the required knowledge of 12800 bits of keystream used to encrypt a full GPRS frame. Variants of the attack are applicable (but more expensive) when given less consecutive keystream bits, or when the available keystream is fragmented (it contains no long consecutive block). In this paper, we improve and complement the previous analysis of GEA-1 and GEA-2. For GEA-1, we devise an attack in which the memory complexity is reduced by a factor of about $2^{13} = 8192$ from $44$ GiB to about 4 MiB, while the time complexity remains $2^{40}$. Our implementation recovers the GEA-1 session key in average time of 2.5~hours on a modern laptop. For GEA-2, we describe two attacks that complement the analysis of Beierle et al. The first attack obtains a linear tradeoff between the number of consecutive keystream bits available to the attacker (denoted by $\ell$) and the time complexity. It improves upon the previous attack in the range of (roughly) $\ell \leq 7000$. Specifically, for $\ell = 1100$ the complexity of our attack is about $2^{54}$, while the previous one is not faster than the $2^{64}$ brute force complexity. In case the available keystream is fragmented, our second attack reduces the memory complexity of the previous attack by a factor of $512$ from 32 GiB to 64 MiB with no time complexity penalty. Our attacks are based on new combinations of stream cipher cryptanalytic techniques and algorithmic techniques used in other contexts (such as solving the $k$-XOR problem).

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
CryptanalysisGPRSGEA-1GEA-2stream ciphersk-XOR
Contact author(s)
dinuri @ cs bgu ac il
History
2022-04-06: received
Short URL
https://ia.cr/2022/424
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/424,
      author = {Dor Amzaleg and Itai Dinur},
      title = {Refined Cryptanalysis of the GPRS Ciphers GEA-1 and GEA-2},
      howpublished = {Cryptology ePrint Archive, Paper 2022/424},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/424}},
      url = {https://eprint.iacr.org/2022/424}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.