The impact of quantum computing on real-world security: A 5G case study

This paper analyzes the threat quantum computing poses to 5G security and proposes a novel, multi-phase migration strategy that leverages the system's backward compatibility to ensure a smooth transition to post-quantum cryptography for 3G, 4G, and 5G networks.

The Gist

Imagine the world of mobile phones (5G) as a massive, high-speed train system. For decades, this system has relied on a specific type of lock and key to keep passengers' conversations and data safe from thieves.

This paper, written by an expert named Chris Mitchell, is a warning label and a repair manual. It says: "A new kind of master thief is coming (Quantum Computers) who can pick our current locks in seconds. We need to upgrade our security before they arrive, but we have to do it without stopping the trains."

Here is the breakdown of the problem and the solution, using simple analogies.

1. The Threat: The "Magic Lockpick"

Currently, 5G security relies on two types of locks:

• The Secret Key (Symmetric): A shared password between your phone and the network.
• The Public Key (Asymmetric): A lock that anyone can use to send you a message, but only you have the key to open.

The Problem:

• Shor's Algorithm (The Master Key): A future quantum computer will be able to break the "Public Key" locks instantly. It's like having a master key that opens every safe in the bank in one second.
• Grover's Algorithm (The Speedster): This makes breaking "Secret Key" passwords much faster. A password that would take a normal computer 10,000 years to guess might take a quantum computer just a few days.

The Risk:
If a bad actor records your encrypted phone calls or data today, they can store it. When the quantum computers arrive in the future, they can unlock all that old data. This is called "Harvest Now, Decrypt Later."

2. The Weak Spots in 5G

The paper analyzes the 5G system and finds two main weak points:

• The Master Key (The USIM Card): Your phone has a tiny chip (USIM) with a secret 128-bit key. Currently, this is strong enough for normal computers. But a quantum computer could crack a 128-bit key by turning it into a 64-bit problem (which is weak). If they crack this one key, they can impersonate you, clone your SIM card, and listen to your calls.
• The Identity Lock (The SUPI): To protect your real identity, 5G encrypts it using a public key (like an elliptic curve). If a quantum computer breaks this, your permanent identity is exposed, and people can track you even if you think you are anonymous.

3. The Solution: A Phased Renovation

You can't just rip out the tracks of a moving train. The author proposes a three-step renovation plan to upgrade the security without breaking the system.

Phase 1: The "Secret Key" Upgrade (Do this Now!)

• The Analogy: Imagine your house has a 128-bit lock. Instead of replacing the whole door, we just swap the key inside the lock for a 256-bit key (a much bigger, more complex key).
• How it works:
  • We change the rules so that new SIM cards come with these super-strong 256-bit keys.
  • The old 128-bit keys can stay on old cards for a while (backward compatibility).
  • Why it's easy: This only requires changing the database at the phone company (the "Home Network") and issuing new SIM cards. Your phone doesn't need to change.
  • Result: Even if a quantum computer comes, it would take so much energy to crack a 256-bit key that it wouldn't be worth the effort.

Phase 2: The "Traffic" Upgrade (Do this later)

• The Analogy: Now that the master key is strong, we need to make sure the actual messages (voice and data) traveling on the train are also protected by the stronger locks.
• How it works:
  • Currently, the system takes a big 256-bit key and chops it in half (truncates it) to make a 128-bit key for the actual data encryption. We need to stop chopping it and use the full 256-bit strength.
  • This requires updating the software in your phone and the cell towers.
  • Why it's safe: Because we did Phase 1 first, the foundation is already strong. This step just tightens the bolts on the doors.

Phase 3: The "Identity" Upgrade (Do this when ready)

• The Analogy: The lock on your front door (your identity) is currently an old-style padlock. We need to replace it with a high-tech biometric scanner that quantum computers can't hack.
• How it works:
  • We need to update the standards to use "Post-Quantum" encryption algorithms (new types of math that quantum computers can't break).
  • This is waiting on global standards (like NIST) to finish testing new algorithms. Once they are ready, we swap the old public-key encryption for the new, quantum-proof ones.

The Big Picture

The author's main message is don't panic, but act now.

• The Good News: We don't need to throw away 5G or build a new system from scratch. The 5G system was actually designed with a little bit of "wiggle room" (backward compatibility) that allows us to slide in these stronger keys easily.
• The Strategy:
  1. Immediately: Start issuing SIM cards with 256-bit keys.
  2. Soon: Update the standards to use new, quantum-proof identity locks.
  3. Later: Update the phones and towers to use the full strength of those new keys.

By following this plan, the 5G network will be ready for the "Quantum Era" without causing chaos, ensuring that your calls, texts, and data remain private for the future.

Technical Summary

1. Problem Statement

The paper addresses the vulnerability of 5G mobile telecommunications security to the advent of large-scale, general-purpose quantum computers (the "Post-Quantum" or PQ era). While 5G systems are currently being deployed globally, their cryptographic foundations rely on algorithms that are susceptible to quantum attacks:

• Symmetric Cryptography: 5G relies on a 128-bit long-term secret key ($K$) stored on the USIM (Universal Subscriber Identity Module). While Grover's algorithm theoretically only halves the effective security of symmetric keys (reducing a 128-bit key to 64-bit security), the paper argues that $2^{64}$ operations are within the realm of feasibility for a determined adversary with quantum capabilities.
• Asymmetric Cryptography: 5G uses elliptic curve cryptography (ECIES) to protect the permanent user identity (SUPI) during transmission. Shor's algorithm renders these schemes insecure, allowing an attacker to derive the private key from the public key, breaking user identity confidentiality.
• Consequences: If these keys are compromised, an attacker could:
  • Decrypt past and future intercepted traffic (if challenge-response pairs are stored).
  • Perform "Man-in-the-Middle" attacks to manipulate signaling and data.
  • Clone USIMs for fraud.
  • Track user identities (IMSI catching).

2. Methodology

The author employs a structured analytical approach:

1. System Analysis: A detailed review of the 3GPP Release 15 (R15) 5G security specifications, focusing on the Authentication and Key Agreement (AKA) protocol, key derivation hierarchies, and mobile identity confidentiality mechanisms.
2. Vulnerability Assessment: Applying the theoretical impacts of Shor's and Grover's algorithms to specific components of the 5G architecture to determine the "breaking point" of the system.
3. Backward Compatibility Evaluation: Analyzing the existing design features of 5G (and its predecessors 3G/4G) to identify "migration paths" that allow for security upgrades without requiring a complete overhaul of deployed infrastructure or USIM hardware.
4. Phased Recommendation Formulation: Proposing a multi-stage transition strategy that leverages existing system flexibility to migrate from 128-bit to 256-bit security and from vulnerable asymmetric schemes to Post-Quantum Cryptography (PQC).

3. Key Contributions

The paper's primary contribution is a practical, phased roadmap for upgrading 5G security to be quantum-resistant, specifically leveraging the backward compatibility features of the 3GPP standards.

A. Identification of Critical Weaknesses

• The 128-bit Root: The entire 5G security hierarchy is anchored by the 128-bit USIM key $K$. Even though derived keys (like $K_{SEAF}$) are 256 bits, they are derived from $K$. If $K$ is broken via Grover's algorithm, the entire session is compromised.
• Identity Protection Failure: The reliance on standard ECIES for SUPI protection means that if the home network's private key is broken via Shor's algorithm, the privacy of millions of subscribers is instantly compromised.
• Standard Compliance Paradox: The paper notes that current implementations might technically violate standards in the PQ era because the mathematical properties required of the key derivation functions ($f_1$–$f_5$) would no longer hold against quantum attacks.

B. The Phased Migration Strategy

The author proposes a three-part solution that minimizes disruption:

Phase 1: Symmetric Key Upgrade (Immediate/Short-term)

• Action: Update standards to allow (and eventually mandate) 256-bit long-term secret keys ($K$) in newly issued USIMs.
• Mechanism: This requires changes only to the USIM and the Authentication Credential Repository and Processing Function (ARPF) in the home network.
• Benefit: No changes to mobile handsets or the radio access network are needed. The existing interface between the USIM and the Mobile Equipment (ME) remains unchanged because the USIM can still output the legacy 128-bit keys ($CK, IK$) derived from the new 256-bit master key.
• Result: This effectively neutralizes the threat of Grover's algorithm against the root key, as a 256-bit key reduced by Grover's algorithm remains at 128-bit security (which is considered secure).

Phase 2: Symmetric Key Usage Upgrade (Medium-term)

• Action: Evolve the system to utilize the full 256-bit strength of the derived keys.
• Mechanism: Currently, 256-bit intermediate keys are truncated to 128 bits for use in encryption and integrity algorithms. Phase 2 involves defining new algorithms that accept 256-bit keys and removing the truncation step.
• Benefit: This can be implemented in handsets and network infrastructure without changing the USIM or ARPF, leveraging the 256-bit keys already established in Phase 1.

Phase 3: Asymmetric Cryptography Upgrade (Long-term)

• Action: Replace ECIES with Post-Quantum Cryptography (PQC) algorithms for protecting the SUPI.
• Mechanism: Once NIST or other bodies standardize PQC algorithms (e.g., lattice-based schemes), the 5G standard should be updated to include these as the default or mandatory scheme for identity encryption.
• Result: Prevents the compromise of user identity privacy even if Shor's algorithm becomes viable.

4. Results and Findings

• Feasibility: The paper concludes that a smooth migration to a PQ-secure 5G system is technically feasible and does not require a "forklift" upgrade of the global telecommunications infrastructure.
• Risk Mitigation: Implementing Phase 1 (256-bit USIM keys) significantly reduces the risk. Even if an attacker intercepts an AKA challenge-response pair, the computational cost to derive a 256-bit key via Grover's algorithm ($2^{128}$ operations) is currently and foreseeably infeasible.
• Scope of Impact:
  • Symmetric: The threat is manageable through key length expansion.
  • Asymmetric: The threat is severe for user privacy but manageable through algorithm substitution. The compromise of a home network's private key would revert security to 4G levels (vulnerable to IMSI catchers) but would not necessarily allow decryption of all traffic if application-layer encryption (e.g., TLS) is used.

5. Significance

• Strategic Planning: The paper provides a critical timeline for 3GPP, network operators, and device manufacturers to act before 5G is fully entrenched. Waiting until quantum computers are available is too late due to the long lifecycle of mobile infrastructure (10+ years).
• Cost Efficiency: By exploiting the "backward compatibility" of the 5G AKA protocol (specifically the ability of the USIM to derive keys for the ME), the paper demonstrates that the most critical security upgrade (moving to 256-bit root keys) can be achieved with minimal hardware changes (only USIM and ARPF updates).
• Standardization Guidance: The paper directly influences the 3GPP standards process, suggesting specific updates to TS 33.105 and TS 33.501 to accommodate 256-bit keys and PQC algorithms, ensuring that future 5G deployments are "future-proof."
• Broader Applicability: The methodology used to analyze 5G serves as a template for reviewing other critical infrastructure systems reliant on cryptography, highlighting the need for early, phased migration strategies.

In conclusion, Mitchell argues that while the quantum threat is real, the specific design of 5G allows for a simple, low-cost, and phased migration to quantum resistance, provided that stakeholders act now to update standards and deploy 256-bit keys in new USIMs.