Paper 2022/733
Breaking the quadratic barrier: Quantum cryptanalysis of Milenage, telecommunications’ cryptographic backbone
Abstract
The potential advent of large-scale quantum computers in the near future poses a threat to contemporary cryptography. One ubiquitous usage of cryptography is currently present in the vibrant field of cellular networks. The cryptography of cellular networks is centered around seven secret-key algorithms $f_1, \ldots, f_5, f_1^{*}, f_5^{*}$, aggregated into an authentication and key agreement algorithm set. Still, to the best of our knowledge, these secret key algorithms have not yet been subject to quantum cryptanalysis. Instead, many quantum security considerations for telecommunication networks argue that the threat posed by quantum computers is restricted to public-key cryptography. However, various recent works have presented quantum attacks on secret key cryptography that exploit quantum period finding to achieve more than a quadratic speedup compared to the best known classical attacks. Motivated by this quantum threat to symmetric cryptography, this paper presents a quantum cryptanalysis for the Milenage algorithm set, the prevalent instantiation of the seven secret-key $f_1, \ldots, f_5, f_1^{*}, f_5^{*}$ algorithms that underpin cellular security. Building upon recent quantum cryptanalytic results, we show attacks that go beyond a quadratic speedup. Concretely, we provide quantum attack scenarios for all Milenage algorithms, including exponential speedups when the attacker is allowed to issue superposition queries. Our results do not constitute a quantum break of the Milenage algorithms, but they do show that Milenage suffers from structural weaknesses making it susceptible to quantum attacks.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Quantum cryptanalysisMilenageCellular networkAKA protocolPost-quantum cryptography5G6G
- Contact author(s)
-
vincent @ sect tu-berlin de
jean-pierre seifert @ tu-berlin de - History
- 2023-05-25: last of 2 revisions
- 2022-06-08: received
- See all versions
- Short URL
- https://ia.cr/2022/733
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/733, author = {Vincent Ulitzsch and Jean-Pierre Seifert}, title = {Breaking the quadratic barrier: Quantum cryptanalysis of Milenage, telecommunications’ cryptographic backbone}, howpublished = {Cryptology ePrint Archive, Paper 2022/733}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/733}}, url = {https://eprint.iacr.org/2022/733} }