Breaking the Quadratic Barrier: Quantum Cryptanalysis of Milenage, Telecommunications’ Cryptographic Backbone

AuthorUlitzsch, Vincent Quentin; Seifert, Jean-Pierre
TypeConference Paper
AbstractThe 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 f1, . . . , f5, 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 f1, . . . , f5, 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 distinguishable by different quantum attack models. Our results do not constitute an immediate quantum break of the Milenage algorithms, but they do show that Milenage suffers from structural weaknesses making it susceptible to quantum attacks.
ConferenceInternational Workshop on Post-Quantum Cryptography 2023