Security Position Statement: Quantum Computers and EMV® Chip Cryptography

EMV-SWG-NJ28r2 EMVCo Position Statement on Quantum Computers and EMV® Chip Cryptography November 2019 Introduction and Overview There are concerns that by the end of the next decade quantum computers might be able to break today's cryptography. The EMV Security Working Group considers that these concerns are overstated and relate more to the confidentiality of long term secrets (e.g. military, commercial or even personal information that would still be sensitive in 30 years' time) rather than to breaking EMV cryptography which primarily relates to real-time authentication. In the event that quantum computers are built that can break EMV cryptography then the EMV Security Working Group considers that it might be possible to introduce post quantum cryptography into EMV in a timely fashion. The remainder of this note provides a summary of EMV cryptographic risks and a summary of progress regarding post quantum cryptography and quantum computing. EMV Public Key Cryptography EMV uses public key cryptography for local authentication of a card to a terminal. As the world moves increasingly online such local authentication becomes optional but is still depended upon for fast low value transactions such as transit or for business continuity (e.g. communications failure). This local card authentication relies on the authenticity of a payment system public key installed in the terminal. If such a payment system key is broken then fake cards could be produced that can locally authenticate to terminals, but they would not successfully authenticate online to the issuer. In addition EMV also uses public key cryptography for local PIN encryption between the terminal and the card during cardholder verification using offline PIN. In this case, rather than transmitting the PIN to the card unencrypted (which is allowed by EMV) the PIN is encrypted under the card's public key. If a fraudster could eavesdrop an encrypted PIN and is able to break the card public key using a quantum computer then they would be able to retrospectively recover the plaintext PIN that was entered by the cardholder. EMV Chip Enhanced updates the public key cryptography in EMV Chip by including elliptic curve cryptography (ECC) for local card authentication and local PIN encryption using NIST curves P-256 and P-521 with hash functions SHA-256 and SHA-512 respectively. Against non-quantum attacks this EMV® is a registered trademark in the U.S. and other countries and an unregistered trademark elsewhere. The EMV trademark is owned by EMVCo. Copyright © 2019 EMVCo, LLC. All rights reserved. EMV-SWG-NJ28r2 represents security levels of 128-bits and 256-bits respectively (the equivalent of 3,072 bit RSA and 15,360 bit RSA). EMV Symmetric Cryptography EMV Chip specifies the use of 2-key Triple DES or AES for authentication of the card by the issuer and for secure messaging. 2-key Triple DES has a key length of 112 bits whilst AES supports key lengths of 128, 192 and 256 bits. If the symmetric keys of a card were to be broken then this would soon be detected by the issuer (ATC mismatches or cardholder complaint) and the issuer can then block the card. Quantum Computers Theoretically a large scale quantum computer would be able to break today's public key cryptography and weaken (but not break) today's symmetric cryptography. • Shor's algorithm is currently the only proposed algorithm for breaking public key cryptography (RSA and ECC). Although in theory 256-bit ECC would be slightly easier to break than 2048-bit RSA (see [ANSI] and [BSI]), each would still require a quantum computer with millions of fault-tolerant qubits running for many hours. • Grover's algorithm is in essence an enhanced search mechanism that it is claimed could halve the bit strength of a symmetric key. Thus a simple precaution for the protection of long-life sensitive data would be to double the key length (i.e. use AES256 instead of AES128). However analysis of the implementation details of Grover's algorithm has shown that it would not be so effective and that the bit-strength of AES128 might at worst be reduced to 106-bits. This would still provide adequate protection for EMV online authentication (see [NIST FAQ] and [G&M]). To date the biggest quantum computer is Google's Bristlecone which has 72 qubits, but this is not fault-tolerant as is needed to implement Shor's or Grover's algorithm. Furthermore there are claims that even the modest factorisations performed by quantum computers using Shor's algorithm (e.g. 15=3x5) did not actually implement Shor's algorithm without using prior knowledge of the result. To successfully attack crypto systems a quantum computer will need millions of qubits able to sustain the necessary level of qubit coherence and fault-tolerance for the duration of the processing. EMVCo will monitor progress in quantum computing carefully. Post Quantum Cryptography NIST is running a programme to find suitable cryptographic algorithms that will not be theoretically vulnerable to quantum computers (see [NIST PQC]). The end result will be a standard of Post Quantum Crypto algorithms due to be published around 2024. Most candidates appear to have worse performance than ECC but could be considered for inclusion in EMV Chip in the future if a candidate emerges with sufficient performance. EMV® is a registered trademark in the U.S. and other countries and an unregistered trademark elsewhere. The EMV trademark is owned by EMVCo. Copyright © 2019 EMVCo, LLC. All rights reserved. References [G&M] [ANSI] [BSI] [NAP] [NIST PQC] [NIST FAQ] [Phys Org] EMV-SWG-NJ28r2 Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes", Gheorghiu and Mosca, February 2019. https://arxiv.org/pdf/1902.02332.pdf Quantum Computing Risks to the Financial Services Industry, ASC X9 IR 01-2019 Entwicklungsstand Quantencomputer, BSI Project 283, 2017 Quantum Computing: Progress and Prospects (2019), National Academic Press NIST Post Quantum Crypto Standardisation, https://csrc.nist.gov/events/2019/second-pqc-standardization-conference NIST FAQ at https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/faqs #008 https://phys.org/news/2014-11-largest-factored-quantum-device.html See also the EMVCo Position on the NSA Statement on Post Quantum Cryptography and Suite B “Cryptography Today”, (March 2016). EMV® is a registered trademark in the U.S. and other countries and an unregistered trademark elsewhere. The EMV trademark is owned by EMVCo. Copyright © 2019 EMVCo, LLC. All rights reserved.