Paper 2022/733

Breaking the quadratic barrier: Quantum cryptanalysis of Milenage, telecommunications’ cryptographic backbone

Vincent Ulitzsch, Technische Universität Berlin
Jean-Pierre Seifert, Technische Universität Berlin
Abstract

The potential advent of large-scale quantum computers in the near future poses a threat to contemporary cryptography. Without doubt, one of the most active and ubiquitous usage of cryptography is currently present in the very vibrant field of cellular networks, i.e., 3G, 4G, 5G and 6G, which is already in the planning phase. The entire cryptography of cellular networks is centered around seven secret-key algorithms $f1,\ldots, f_5, f_1^{*}, f5^{*}$, aggregated into an "authentication and key agreement" algorithm set. Still, 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. On the other hand, the only threat to secret-key algorithms would stem from the famous Grover quantum search algorithm, which admits a general square root speedup of all oracle based search problems, thus resulting in an effectively halved key length of the above algorithms. However, various recent works have presented quantum attacks on secret key cryptography that result in more than a quadratic speedup. These attacks call for a re-evaluation of quantum security considerations for cellular networks, encompassing a quantum cryptanalysis of the secret-key primitives used in cellular security. In this paper, we conduct such a quantum cryptanalysis for the Milenage algorithm set, the prevalent instantiation of the seven secret-key algorithms that underpin cellular security. Building upon recent quantum cryptanalytic results, we show attacks that go beyond a quadratic speedup. Concretely, we provide for all Milenage algorithms various quantum attack scenarios, including exponential speedups distinguishable by different quantum attack models. The presented attacks include a polynomial time quantum existential forgery attack, assuming an attacker has access to a superposition oracle of Milenage and key recovery attacks that reduce the security margin beyond the quadratic speedup of Grover. Our results do not constitute an immediate quantum break of the Milenage algorithms, but they do provide strong evidence against choosing Milenage as the cryptographic primitive underpinning the security of quantum resistant telecommunication networks.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Quantum cryptanalysis Milenage Cellular network AKA protocol Post-quantum cryptography 5G 6G
Contact author(s)
vincent @ sect tu-berlin de
jean-pierre seifert @ tu-berlin de
History
2022-06-13: revised
2022-06-08: received
See all versions
Short URL
https://ia.cr/2022/733
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.