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 distinguishable by different quantum attack models. 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.

Appendices

A List of Abbreviations

3GPP :

Third Generation Partnership Project

AK :

Anomity Key

AKA :

Authentication and Key Agreement

AMF :

Authentication Management Field

SQN :

Sequence Number

MAC :

Message Authentication Code

HN :

Home Network

MME :

Mobility Management Entity

BS :

Base Station

MS :

Mobile Station

LTE :

Long-Term Evolution

EAP :

Extensible Authentication Protocol

3GPP :

3rd Generation Partnership Project

B The AKA Protocol

The Milenage algorithm set’s main usage is the AKA protocol, used for authentication and session establishment in cellular networks as well as other cellular related applications, e.g., as a variant of the Extensible Authentication Protocol (EAP), the EAP-AKA.

In summary, the LTE-AKA protocol is a challenge-response protocol that allows the subscriber to authenticate themselves to the network. The AKA protocol also derives a session key $K_{ASME}$ that is used for encryption and integrity protection of communication at later points. The functions $f1, \dots , f4$ from the Milenage algorithm set serve to derive a MAC, an expected response to a challenge, and the confidentiality and integrity keys (commonly denoted as CK and IK), which are in turn used to derive session keys. The function f5 is used to derive an Anomity Key (AK). The AK serves to mask the SQN, where the purpose of the SQN itself is to prevent replay attacks.

The authentication procedure in the fifth generation (5G) of cellular networks add various security and privacy enhancements to the LTE-AKA protocol, but uses the functions $f1, \dots , f5$ in the same way. Given that the functions provide authentication and serve as a basis for later encryption and integrity protection, the security of cellular networks is completely contigent on the security of the functions $f1, \dots , f5$.

C Proof of the Hidden Period Required for the Quantum Slide Attack

To see why$F^{*}_{k}(b,x) = F_{k}((b,x),g(p_k(b,x)))$ indeed has the hidden period $(1, OP_c \oplus c_2)$, first observe that

$$\begin{aligned} f2'(E_K(x \oplus OP^{*}_c)) \oplus (x \oplus OP^{*}_c)= & {} E_K(f2'(x)) \oplus x, \end{aligned}$$

(1)

where we write $OP^{*}_c= OP_c \oplus c_2$ for the sake of brevity. To see why Eq. 1 holds, note that:

$$\begin{aligned}{} & {} f2'(E_K[x \oplus OP^{*}_c]) \oplus (x \oplus OP^{*}_c)\\= & {} E_K[E_K[E_K[x \oplus OP^{*}_c] \oplus OP^{*}_c] \oplus OP^{*}_c] \oplus OP^{*}_c\oplus (x \oplus OP^{*}_c) \\= & {} E_K[E_K[E_K[x \oplus OP^{*}_c] \oplus OP^{*}_c] \oplus OP^{*}_c] \oplus x \end{aligned}$$

and

$$\begin{aligned}{} & {} E_K(f2'(x)) \oplus x \\= & {} E_K[E_K[E_K[x \oplus OP^{*}_c] \oplus OP^{*}_c] \oplus OP^{*}_c] \oplus x \\= & {} f2'(E_K[x \oplus OP^{*}_c]) \oplus (x \oplus OP^{*}_c). \end{aligned}$$

Thus, it follows that $F^{*}_{k}(1,x) = F^{*}_{k}(0,x \oplus OP_c \oplus c_2)$ because

$$\begin{aligned} F^{*}_{k}(1,x)= & {} F_{k}((1,x),g(p_k(1,x))) \\= & {} F_{k}((1,x),g(x)) \\= & {} F_{k}((1,x),f_2'((x))) \\= & {} E_k(f_2'(x)) \oplus x \end{aligned}$$

and

$$\begin{aligned}{} & {} F^{*}_{k}(0,x \oplus OP_c \oplus c_2) \\= & {} F_{k}((0,x \oplus OP^{*}_c),g(p_k(0,x \oplus OP^{*}_c))) \\= & {} F_{k}((0,x \oplus OP^{*}_c),g(E_k(x \oplus OP^{*}_c))) \\= & {} f2'(E_k(x \oplus OP^{*}_c)) \oplus x \oplus OP^{*}_c\\= & {} E_k(f2'(x)) \oplus x, \end{aligned}$$

where the last step follows from Eq. 1.

D Proof of the Hidden Period Required for the Existential Forgery Attack

It remains to be shown that $f'$ as defined in Sect. 4.3 indeed has the hidden period $(1, rot^{-1}_{r1}(\alpha _{0}^{*} \oplus \alpha _1^{*}))$. To this end, we need to show that

$$f'(0, y) = f'(1, y \oplus rot^{-1}_{r1}(E_k[\alpha _0 \oplus OP_c] \oplus E_k[\alpha _1 \oplus OP_c])).$$

First, observe that by linearity of rotation it holds that

$$\begin{aligned}{} & {} f1_{K, OP_c}(x, y) \\= & {} E_K[E_K[x \oplus OP_C] \oplus rot_{r_1}(y \oplus OP_c) \oplus c_1] \oplus OP_c \\= & {} E_K[E_K[x \oplus OP_C] \oplus rot_{r_1}(y) \oplus rot_{r_1}(OP_c) \oplus c_1]\oplus OP_c. \end{aligned}$$

Thus, we have

$$\begin{aligned}&f'(0, y) = E_K[\alpha _{0}^{*} \oplus rot_{r1}(y) \oplus rot_{r1}(OP_c) \oplus c_1] \oplus OP_c, \end{aligned}$$

and

$$\begin{aligned}{} & {} f'(1, y \oplus rot^{-1}_{r}(\alpha _{0}^{*} \oplus \alpha _{1}^{*})) \\= & {} E_K[\alpha _{1}^{*} \oplus rot_{r_1}(y \oplus rot^{-1}_{r_1}(\alpha _{0}^{*} \oplus \alpha _{1}^{*})) \oplus rot_{r_1}(OP_c) \oplus c_1] \oplus \\{} & {} \ \ OP_c \\= & {} E_K[\alpha _{1}^{*} \oplus rot_{r_1}(y) \oplus rot_{r_1}(rot^{-1}_{r_1}(\alpha _{0}^{*} \oplus \alpha _{1}^{*})) \oplus \\{} & {} \ \ rot_{r_1}(OP_c) \oplus c_1] \oplus OP_c. \end{aligned}$$

Now, using $rot_{r_1}(rot^{-1}_{r_1}(x)) = x$ we can continue as

$$\begin{aligned}= & {} E_K[\alpha _{1}^{*} \oplus rot_{r_1}(y) \oplus \alpha _{0}^{*} \oplus \alpha _{1}^{*} \oplus rot_{r_1}(OP_c) \oplus c_1] \oplus OP_c \\= & {} E_K[rot_{r_1}(y) \oplus \alpha _{0}^{*} \oplus rot_{r_1}(OP_c) \oplus c_1] \oplus OP_c \\= & {} f'(0, y), \end{aligned}$$

which indeed yields $f'(0, y) = f'(1, y \oplus rot^{-1}_{r}(\alpha _{0}^{*} \oplus \alpha _{1}^{*}))$.