Welcome to the resource topic for 2022/424
Title:
Refined Cryptanalysis of the GPRS Ciphers GEA-1 and GEA-2
Authors: Dor Amzaleg, 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).
ePrint: https://eprint.iacr.org/2022/424
Talk: https://www.youtube.com/watch?v=VYOPkIimmyU
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/227/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .