Content for TR 33.841 Word version: 16.1.0

3.1 Definitions 3.2 Abbreviations 4.1 Introduction 4.2 Threats to asymmetric cryptography 4.3 Threats to symmetric cryptography 4.4 Threats to hash algorithms
...

0 Introduction p. 5

Quantum computing poses a long-term threat to information security. This may apply to some of the current protection measures in 5G systems. These threats are studied in the present document so as to ensure that 5G systems remain secure also in the future.

The threats will impact symmetric and asymmetric cryptographic algorithms in different ways. The present document focuses on symmetric cryptographic algorithms. In particular, it focuses on the implications of introducing 256 bit cryptographic keys and algorithms.

The study allows informed decisions on why, when, where, and how symmetric cryptographic algorithms used in 3GPP systems could be strengthened to counter the identified threats.

WHY: Commercial applications (e.g., critical infrastructure, financial, medical, and pharmaceutical) and government organizations may need enhanced protection for confidential information.

WHEN: This study establishes a timeline for the introduction of enhanced protection measures. It is currently not clear when, e.g., quantum computers may pose a realistic threat. The timeline may take into account the following factors:

the number of years that data that are sent protected in 5G (over the various interfaces) need to remain secure;
the number of years it will take to introduce 256-bit keys in the 5G system (standardization and deployment);
the number of years it takes to decrypt data protected with 128-bit keys, taking into account technological progress.

The study should also seek to align the security levels and timelines for introducing new asymmetric cryptographic algorithms with those for symmetric cryptographic algorithms in 5G. The reason is that the 5G system also makes use of asymmetric cryptographic algorithms, e.g. in network domain security, in untrusted non-3GPP access, and in 5G identity privacy, and it does not make sense to have different security levels for different types of algorithms in the same release of a 5G system.

WHERE: Not all parts of the 5G system may be affected in the same way. The study should therefore investigate the impacts on UE, gNB, and core network entities separately. As an example, the study may investigate whether encryption between the UE and a gNB in an operator network (where the cleartext is available to the operator in the gNB) and encryption between the UE and a core network entity in a slice are affected by the requirements in the same way.

HOW: The focus of this proposed new work will include, but will not be limited to, supporting 256-bit keys and algorithms, bolstering integrity protection by increasing the size of MAC-I in 5G networks, key derivation, AKA key generation, key distribution, key refresh, negotiation of the key size, and processing of confidential CP/UP/MP information.

1 Scope p. 7

The present document details the following:

An assessment of threats and potential countermeasures posed due to quantum computing and a resulting assessment of relevant countermeasures in the 5G system.
An assessment of the timelines for the introduction of any countermeasures, in particular the increase of key lengths to 256 bits. This includes an alignment with the timeline for strengthening asymmetric cryptographic algorithms used in 5G systems.
An assessment of which parts of the 5G system will be affected and in which way.
A Study of full entropy 256 bit keys in the 5G key hierarchy, beginning with the permanent pre-shared key. Including a study into modifying the derivation algorithms in order to derive child keys from the 256-bit master key instead of the 128-bit key.
A study to determine whether a longer MAC is appropriate for 5G.
A study of the coexistence of different size keys. In 3GPP networks, 256-bit keys in 5G will need to coexist with 128-bit keys in legacy networks or earlier 5G phases. This includes storage of keys and separate key derivation algorithms both on the UE and in the core network.
A study into the desired number of 256-bit algorithms, e.g. if two 256-bit AKA key generation algorithm sets are needed.
A study of the desired performance aspects for the new 256-bit algorithms taking into account software and hardware aspects.
A study of key size negotiation.
A study into whether the current methods for distribution and refresh of security keys are equally applicable to larger key sizes and can remain the same.
A study into the Encryption and integrity algorithms that could be needed. This includes 256-bit session/intermediate keys in 5G, may, in some cases, simply entail using larger-key versions of current algorithms, while in other cases new algorithms may need to be chosen altogether.
Recommendations for suitable requirements for the needed algorithms for use with 256-bit keys and ask ETSI SAGE to provide those algorithms.

2 References p. 7

The following documents contain provisions which, through reference in this text, constitute provisions of the present document.

References are either specific (identified by date of publication, edition number, version number, etc.) or non-specific.
For a specific reference, subsequent revisions do not apply.
For a non-specific reference, the latest version applies. In the case of a reference to a 3GPP document (including a GSM document), a non-specific reference implicitly refers to the latest version of that document in the same Release as the present document.

[1]

TR 21.905: "Vocabulary for 3GPP Specifications".

[2]

Markus Grassl, Brandon Langenberg, Martin Roettler, Rainer Steinwandt (2015): "Applying Grover's algorithm to AES: quantum resource estimates". https://arxiv.org/pdf/1512.04965.pdf

[3]

Vlad Gheorghiu, Michele Mosca (2017): "GRI quantum risk assessment report: A resource estimation framework for quantum attacks against cryptographic functions". http://globalriskinstitute.org/download/summary-report-3/

[4]

Scott Fluhrer (2017): "Reassessing Grover's Algorithm". https://eprint.iacr.org/2017/811.pdf

[5]

Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, John Schanck (2016): "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3". https://arxiv.org/pdf/1603.09383.pdf

[6]

Daniel J. Bernstein (2009): "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?" https://cr.yp.to/hash/collisioncost-20090517.pdf

[7]

NISTIR 8105 (2016): "Report on Post-Quantum Cryptography". https://csrc.nist.gov/publications/detail/nistir/8105/final

[8]

John M. Martinis (2015): "Qubit metrology for building a fault-tolerant quantum computer". https://www.nature.com/articles/npjqi20155.pdf

[9]

Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter: "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms". In Proc. ASIACRYPT 2017. https://www.microsoft.com/en-us/research/wp-content/uploads/2017/09/1706.06752.pdf

[10]

Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland: "Surface codes: Towards practical large-scale quantum computation". October 26, 2012. https://web.physics.ucsb.edu/~martinisgroup/papers/Fowler2012.pdf

[11]

Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt: "Applying Grover's algorithm to AES: quantum resource estimates". https://www.microsoft.com/en-us/research/wp-content/uploads/2016/04/1512.04965-1.pdf

[12]

MIT Technology Review, Practical Quantum Computers. https://www.technologyreview.com/s/603495/10-breakthrough-technologies-2017-practical-quantum-computers/

[13]

Thomas Häner, Martin Roetteler, and Krysta M. Svore: "Factoring using 2n+2 qubits with Toffoli based modular multiplication". Quantum Information and Computation, 18(7&8):673-684, 2017

[14]

TS 33.310: "Network Domain Security (NDS); Authentication Framework (AF)".

[15]

TS 33.210: "3G security; Network Domain Security (NDS); IP network layer security".

[16]

TS 33.501: "Security architecture and procedures for 5G system".

[17] Void

[18] Void

[19]

RFC 7515: "JSON Web Signature (JWS)".

[20] Void

[21] Void

[22] Void

[23]

RFC 7519: "JSON Web Tokens (JWT)".

[24]

TS 33.117: "Catalogue of general security assurance requirements".

[25]

NIST Special Publication 800-38B: "Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication".

[26]

NIST project on Post-Quantum Cryptography. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.

[27]

SOG-IS Crypto Evaluation Scheme: "Agreed Cryptographic Mechanisms". https://www.sogis.org/documents/cc/crypto/SOGIS-Agreed-Cryptographic-Mechanisms-1.1.pdf

[28]

Dustin Moody (2018): "Let's Get Ready to Rumble - The NIST PQC 'Competition'".

[29]

NIST (2016): "Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process". https://csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf

[30]

Mihir Bellare, Björn Tackmann (2017): "The Multi-User Security of Authenticated Encryption: AES-GCM in TLS 1.3".

[31]

draft-mcgrew-iv-gen "Generation of Deterministic Initialization Vectors (IVs) and Nonces".

[32]

Report ITU-R M.2410-0: "Minimum requirements related to technical performance for IMT-2020 radio interface(s)", 2017.

[33]

IEEE 802.15.4-2011: "IEEE Standard for Local and metropolitan area networks--Part 15.4: Low Rate Wireless Personal Area Networks (LR-WPANs)", 2011. https://standards.ieee.org/standard/802_15_4-2011.html

[34]

TS 33.220: "Generic Authentication Architecture (GAA); Generic Bootstrapping Architecture (GBA)".

[35]

RFC 5689: "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)".

[36]

TS 31.115: "Secured packet structure for (Universal) Subscriber Identity Module (U)SIM Toolkit applications".

[37]

ETSI TS 102 225: "Smart Cards; Secured packet structure for UICC based applications".

[38]

Improving the Biclique Cryptanalysis of AES, http://link.springer.com/chapter/10.1007/978-3-319-19962-7_3.

[39]

The ZUC-256 Stream Cipher, http://www.is.cas.cn/ztzl2016/zouchongzhi/201801/W020180416526664982687.pdf

[40]

ETSI TS 102 226: "Smart Cards; Remote APDU structure for UICC based applications".

[41]

GlobalPlatform: "Card Specification, Amendment B".

3 Definitions and abbreviations p. 9

3.1 Definitions p. 9

For the purposes of the present document, the terms and definitions given in TR 21.905 and the following apply. A term defined in the present document takes precedence over the definition of the same term, if any, in TR 21.905.

quantum computer:

a computer which makes use of quantum-mechanical effects

3.2 Abbreviations p. 9

For the purposes of the present document, the abbreviations given in TR 21.905 and the following apply. An abbreviation defined in the present document takes precedence over the definition of the same abbreviation, if any, in TR 21.905.

AKA

Authentication and Key Agreement

Ciphering Key

DHE

Diffie-Hellman Ephemeral

EAP

Extensible Authentication Protocol

ECDHE

Elliptic Curve Diffie-Hellman Ephemeral

ECIES

Elliptic Curve Integrated Encryption Scheme

GKDF

Generic Key Derivation Function

HKDF

HMAC-based Extract-and-Expand Key Derivation Function

Home Network

IKEv2

Internet Key Exchange version 2

IPX

IP Exchange

JSON

JavaScript Object Notation

KDF

Key Derivation Function

NAS

Non Access Stratum

NDS

Network Domain Security

OTA

Over The Air

RES

RESponse

RRC

Radio Resource Control

SBA

Service Based Architecture

SEAF

Security Anchor Function

SEPP

Security Edge Protection Proxy

SUCI

SUbscription Concealed Identifier

SUPI

SUbscription Permanent Identifier

TLS

Transport Layer Security

User Equipment

4 Threats posed by quantum computing and potential countermeasures p. 10

4.1 Introduction p. 10

A quantum computer is a computer which makes use of quantum-mechanical effects. These effects include superposition, which allows quantum bits (qubits) to exist in a combination of several states at once, and entanglement, which allows connections between separate quantum systems such that they cannot be described independently. There exist quantum algorithms that use these effects to solve certain cryptographic problems more efficiently than they could be solved on a classical computer. However, due to the reliance on physical effects quantum computing is inherently error prone, meaning that circuits for quantum algorithms require extra qubits for error correction. This quantum error correction means that the complexity of the quantum computer required to carry out certain quantum algorithms is greater in practice than in theory. With the advances in quantum computing, the security community feels it is important to start preparing our information security systems to be resilient to this potential threat.

Determining how to cost an attack with a quantum computer is difficult. The number of qubits needs be taken into account, along with the number of quantum gates in the circuit, and the number of sequential evaluations of the gates, called the depth of the circuit. Depth governs how long the calculation will take. With a gate-time of a few nano-seconds, a depth of around 250 would take one year to evaluate.

4.2 Threats to asymmetric cryptography p. 10

Shor's quantum algorithm for integer factorization runs in polynomial time on a quantum computer. As the security of RSA relies on the hardness of factorizing large integers, the system's security is terminally undermined by quantum computation. A variant of Shor's algorithm enables a quantum computer to calculate discrete logarithms in polynomial time, both over finite fields and elliptic curves. This variant renders several other public-key cryptosystems insecure, including Diffie-Hellman and Elliptic Curve Diffie-Hellman.

To counter the threat of quantum computing to asymmetric cryptography it is necessary to swap existing algorithms for new, quantum-resistant algorithms. However, it should be noted that all quantum-resistant key-exchange algorithms currently being considered are much less studied than traditional public key systems such as RSA and Diffie-Hellman. As such, a balance will need to be struck between countering the quantum threat and ensuring the use of stable and tested systems.

4.3 Threats to symmetric cryptography p. 11

Grover's search algorithm offers a theoretical quadratic speed-up on unstructured search problems. This is applicable to symmetric key cryptography as, with use of Grover's algorithm, the N-bit key for a cipher is recovered with O(2N/2) serial quantum operations.

The real speed up offered by Grover's algorithm is difficult to evaluate and depends on a variety of factors including the scheme being analysed, the precise functionality of a quantum computer and the necessity for error-correction codes. There has been limited analysis of the effect of Grover's algorithm on 128-bit block ciphers, but various papers [2] and [3] have calculated that, while the security of AES-128 would be reduced with the development of a quantum computer, it would not fall to 64 bits. However, there has not been any concrete study quantitatively examining the impact of quantum computing on stream ciphers. It should also be noted that Grover's algorithm does not parallelise efficiently, suggesting that the security assumptions to apply in this scenario may be different to those in classical computing. It may be more appropriate to consider attacks that run in bounded time, taking into account the likely capabilities of an attacker and the amount of likely parallelisation [4].

To counter this threat to symmetric cryptography from a quantum computer it would certainly suffice to double the key-size of an algorithm, thus doubling the number of bits of classical security. As discussed above there is an ongoing discussion as to whether this response is overly conservative, as the changes would have other business, interoperability and security consequences.

4.4 Threats to hash algorithms p. 11

Grover's algorithm also poses a threat to the security of hash algorithms. As for symmetric algorithms, the theoretical speed-up is quadratic, but it is difficult to evaluate this in a real world scenario. [5] estimates that a single pre-image attack on SHA-256 would take ~2166 operations, rather than the theoretical 2128. Looking at another measure of cryptographic hash security, there is no known quantum algorithm which finds collisions in general hash functions more efficiently than the most efficient classical algorithms [6].