Security Position Statement: Quantum Computing and EMV Chip Cryptography

EMV-SWG-NM07r17c-public EMVCo Position Statement Quantum Computing and EMV® Chip Cryptography 8th March 2024 (published September 2024) This paper outlines the EMVCo Security Working Group (SWG) position regarding the threat posed by quantum computers to the cryptography that is intrinsic to the security of EMV® and in particular C-8 contactless. It is widely reported and anticipated in the popular media that quantum computers will soon be developed that are capable of breaking all forms of classical cryptography. However, the true landscape is more nuanced from a timeline perspective and also separates distinctly between asymmetric algorithms (such as RSA and ECC) and symmetric algorithms (such as AES). The SWG has reviewed and analysed relevant material from the wider cryptographic community in order to arrive at a more realistic position regarding the actual threat posed by quantum computers. Theoretically quantum computers would be able to solve some classes of problems that are not efficiently solvable by classical computers. If a quantum computer could be built to run Shor’s algorithm then it would be able to solve the class of problem that underpins RSA and ECC. In regards AES, Grover’s quantum algorithm is theoretically much faster than classical search for symmetric keys but is completely impractical and therefore is not a concern for EMV. This paper begins with a summary of the consequences of quantum computing for EMV chip cryptography and then provides two detailed sections, one on asymmetric cryptography and the other on symmetric cryptography. The paper ends with an appendix describing the foundational analysis by Zalka and a list of reference material. This paper builds on and updates the EMV position statement published in 2019. 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public Conclusions for EMV Chip Cryptography For asymmetric cryptography, it is Shor’s algorithm that is relevant. However multiple orders of magnitude improvements in quantum computer capability would be required for it to become a realistic threat. From an EMV payments perspective, asymmetric cryptography is only really necessary for offline working, which is becoming less relevant in a connected world. For symmetric cryptography, it is Grover’s algorithm that is relevant. However, all the analyses reviewed and conducted by the SWG, lead the SWG to conclude that Grover’s quantum algorithm requires more attack resources to recover an AES key than a classical attack. The choice of symmetric algorithm and key size is therefore driven by classical attack feasibility not by Grover and since AES-128 is considered immune to classical attack, it is also considered immune to quantum attack.1 • Consequently, the SWG supports AES-128 to be the entry level symmetric algorithm resistant to classical and quantum attack and being resource efficient is suitable for current and future use. The SWG believes that there is no need to recommend consideration of AES256 for quantum resistance, however it is allowed for contingency purposes. Hash functions such as SHA-256 are similarly not threatened by Quantum Computers. See NIST security level defined in section 4.A.5 of [1]. The SWG will monitor and support standards development of quantum resistant solutions in order to steer a path to maintain EMV as fit for purpose. The intention is to identify cost effective security solutions whose implementation timeline is commensurate with the quantum threat being realised, certainly ten years distant, and on current projections unlikely prior to 2040. Regarding EMV chip specifications use of asymmetric cryptography: • Breaking an asymmetric key is primarily a concern for environments that are normally offline. The ultimate protection would be to go online, but other mitigations may be available depending on performance, usability and economic constraints. • Breaking a Payment System or Issuer key would allow the production of fake cards used for fraudulent offline payments. However breaking an individual card key would only allow the cloning of that card, and this would be uneconomic for a fraudster. • From a C-8 contactless privacy perspective, an eavesdropper wanting to track an individual across transactions would need to break the ephemeral keys for every transaction. 1 Although 2-key Triple DES is legacy cryptography, it does enjoy a significant security margin against any potential quantum Grover attack albeit with a smaller margin than AES. 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public 1. Asymmetric (RSA/ECC) As regards the threat to public key cryptography, the performance gap between today’s quantum computers and that of cryptographically significant quantum computers is well understood by the cryptography community, and it is large. BSI [2] has published a chart depicting the performance gap, as has Sam Jaques of Waterloo University [3]. These assessments are based on published material regarding today’s quantum computers and the quantum computer requirements necessary to execute Shor’s algorithm for example. From these assessments, performance needs to improve by at least 5, and possibly 7 orders of magnitude before RSA-2048 for instance can be attacked. As an evidence point of this gap, Google’s Sycamore machine, (the same class of quantum computer as that being developed by IBM, Rigetti and now D-Wave) performs 20-30 gate operations before descending to useless noise, whereas over 2 billion sequential and error free gate operations are required to execute Shor’s algorithm [3] to break RSA-2048. In the arena of gauging when bad actors will have access to cryptographically significant quantum computers, hype abounds and there are prophecies ranging from “5 years” to “never” as to when this will happen. The extremes are typically driven by some sort of self-interest, but the reality is that no one knows the answer. In particular, the SWG is tracking the progress of IBM in this area as they have engineering credibility, a published road map and in our opinion are transparent in their communications on progress. The SWG believes that in order to support planning, an objective mechanism is required for forecasting when cryptographically significant quantum computers capable of attacking RSA/ECC may become available for use by bad actors. Consequently the SWG proposes, in line with some other commentators, that initially a Moore’s Law curve be used to estimate the growth rate of quantum computer performance towards achieving cryptographically significant quantum computers. This can be compared with actual achievements to indicate the rate at which the performance gap is being closed. The type of growth model and model parameters can be adjusted periodically should the initial hypotheses of exponential growth with performance doubling every 18 months not fit the accumulated data points. There is a performance gap which is an objective fact. The most optimistic projections suggest that the earliest date that a cryptographically significant quantum computer could be built would be around 2040. The most pessimistic projections are that such a computer will never be built. Until certain milestones are achieved the speed of development is difficult to ascertain. The SWG is monitoring the following milestones: • First fault-tolerant logical qubit • 1,000 entangled physical qubits • Multiple entangled fault-tolerant logical qubits • Factorization of small numbers such as 15 (without feeding in the period) • Identical qubit behaviour 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public 2. Symmetric (AES-128) The quantum threat to existing cryptographic symmetric algorithms is determined by the properties of Grover’s quantum unordered search algorithm. This SWG paper references two analyses of the strength of AES-128 against the threat of quantum computers. These analyses were performed by authorities on the subject: • NIST • Gheorghiu and Mosca et al Both analyses have relied on a seminal paper [4] by Zalka (see Appendix for a summary) which provides the definitive description of what quantum computers are capable of in the context of problems that have classically been solved by brute force “trial and error” searches for a distinguished element in a set, e.g. breaking AES-128 with one matching plaintext-ciphertext input pair by trying all the keys. Zalka’s paper asserts: Grover’s algorithm is optimal, at best square roots the number of search steps when compared to a conventional search algorithm and parallelises badly. The question to be answered is whether it is feasible for a nation state to recover an AES-128 key in one year using quantum computer technology? If a nation state cannot do this then it can be discounted as a payment system risk. 2.1 NIST analysis NIST is the authority leading the standardisation response to the quantum threat to cryptography with responsibility for collecting and sifting cryptographic opinion and then issuing robust standards on the basis of proposals from the global cryptographic community. On the back of their analysis NIST has declared that Grover’s algorithm will not reduce the cost of attack on AES-128 to below that of a classical attack. (This stance is supported publicly by at least two other government bodies the UK NCSC [10] and the German BSI [7].) It is implicit that this will be true for some decades. Obviously NIST has reserved the right to vary its advice depending on any new developments be they crypto-analytic or technological, but this is a normal caveat for all cryptographic assessments. The NIST stance is documented in the NIST PQC FAQ [5]: Q: To protect against the threat of quantum computers, should we double the key length for AES now? A: “…Based on such understanding, current applications can continue to use AES with key sizes 128, 192, or 256 bits. NIST will issue guidance regarding any transitions of symmetric key algorithms and hash functions to protect against threats from quantum computers when we can foresee a transition need. Until then, users should follow the recommendations and guidelines NIST has already issued. In particular, anything with less than 112 bits of classical security should not be used.” 2.2 Academic analysis Academic authors such as Gheorghiu and Mosca have published papers estimating in great detail the quantum resources required to attack AES-128. One of Gheorghiu and Mosca’s papers [6] indicates that a quantum attack on AES-128 requires 2101 steps not just 264 as expected for Grover. Their 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public papers further describe AES quantum circuits, the error correction overhead of a technology called surface code and projected running times. Their discussion is transparent, thoroughly scholarly and they conclude that, properly costed, to recover an AES-128 bit key by brute force using Grover’s algorithm in one year will require 280 quantum computers. The human race has never built 280 of anything, not even transistors, thus this number of quantum computers is infeasible regardless of economics. It is plausible that the analysis of Gheorghiu and Mosca will not be the last word on the circuit resources required to apply Grover’s algorithm to AES-128 and more economical designs will be discovered. However, improvements will be linear and not exponential, consequently the 280 estimate may come down by a few bits but there will be no dramatic decrease. 2.3 An EMV SWG analysis The SWG analysis is a simple worst-case example in the sense that it assumes that only 264 (π/4) quantum operations are required to break AES-128 and further assumes that a quantum computer can perform a trial AES encryption in as little as 1 nanosecond2. The following simple arithmetic calculates the number of years a single quantum computer would take to recover an AES-128 key by brute force with these assumptions: (0.000000001*264 *π/4) / (60*60*24*365) This is 459 years, beyond the cover time of any AES key used today. According to Zalka (see Appendix), to speed this up to one elapsed year would require 459 squared quantum computers working in parallel (a consequence of the bad parallelisation properties of Grover) i.e. 211,000 cryptographically significant quantum computers would be needed to recover an AES key in one year. It will be many decades before there are 211,000 cryptographically significant quantum computers, and even then this number is likely a huge underestimate. It is inconceivable that a full quantum AES call with error correction overhead will execute in less than 1 nanosecond. A reasonable assumption3 is that it will need thousands of quantum gates (individual logic steps) to execute a full AES encryption, each gate itself requiring >1ns execution time. In particular at least 2000 gates are on a critical path and must be executed as an unbroken sequential chain hence a quantum AES-128 call will take at least 2 micro-seconds. This places an attack of 264 calls absolutely beyond one machine by requiring 900,000+years, alternatively an attack duration of one year would require 800 billion quantum computers. Assuming quantum computers cost more than $100 a unit this is uneconomic even for a nation state. This rudimentary check aligns with the statements of NIST and of Gheorghiu and Mosca who in their detailed calculations have used tighter estimates of the complexity of Grover’s algorithm for N=2128, coupled with actual gate counts/gate speeds and error correction overheads. It is widely believed and endorsed by standardisation bodies that AES-128 is fit for purpose to protect sensitive data against crypto-analytic and classical computer based brute force attack for decades. The EMVCo SWG further believes (in line with standardisation bodies) that quantum computers do not pose a threat to AES-128 because of the ineffectiveness of quantum computer algorithms to outperform 2 A similar calculation is performed by BSI in [7]. 3 See also for example [8]. 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public classical attacks in terms of resource economy - as evidenced above. Consequently AES-128 is the EMV entry level backbone symmetric algorithm and key length for the decades ahead regardless of classical or quantum attack models, with AES-256 capability held in reserve for contingency. 2.4 Potential public EMV statement on AES Current analysis, in-line with that of NIST [5], indicates that AES-128 is resistant to both classical and quantum attacks for the foreseeable future. EMVCo does not see any need to deploy AES-256 to defend against any potential quantum computer threat. A principle of EMV security policy is that of crypto agility for contingency purposes. Accordingly, EMVCo strongly recommends that the hardware of new security components (e.g. HSMs) used for EMV payments has flexibility regarding symmetric encryption and so should support AES-128 and be capable of supporting AES-256. 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public Appendix - On Zalka’s paper In the context of Grover’s algorithm complexity is a measure of the worst-case relationship between the size of a problem and the resources required to solve the problem. The size of an unordered search problem is simply the number of elements that are candidates to be the desired target of the search. If there are N elements in total then classically in the worst-case, N functional trials are required to confirm the distinguished element uniquely satisfying some property. For example, using brute force to identify an AES-128 key that gives rise to a given candidate matching plaintextciphertext pair would, in the worst case, require 2128 trials as mentioned above. Christof Zalka’s 1999 paper on quantum unordered search algorithms [4] proves that the best possible quantum unordered search algorithm would asymptotically have a complexity of π√𝑁 divided by 4 functional trials (asymptotically means for very very big values of N). Grover’s algorithm also requires other steps than the functional trials, which are not captured in this formula. If the naive asymptotic complexity is applied to N=2128, then Grover’s algorithm would only require approximately 264 trial encryptions to identify an AES-128 key given a matching plaintext-ciphertext pair. Such an improvement over a classical trial and error search is truly astonishing. However, 264 AES trial encryptions on a single machine, even at Gigahertz speeds, would take decades/hundreds of years. The Grover search, to be useful, has to be performed using processors working in parallel. Zalka’s paper also proves that the optimal quantum algorithm, i.e. Grover, will not benefit from linear speed-up by the use of parallel processing, i.e. 100 processors running Grover will not solve a problem 100 times faster than a single Grover processor but instead the speed-up will be 10 i.e. the square root of the number of parallel processors. This complicates the analysis of not only how economically useful Grover’s algorithm will be, but specifically complicates the analysis of the impact of Grover’s algorithm on the strength of AES-128 in a world where cryptographically significant quantum computers exist and can be built routinely. 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 © 2024 EMVCo, LLC. All rights reserved. EMV-SWG-NM07r17c-public References [1] National Institute of Standards and Technology. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process, 2016. Call-for-proposals-final-dec-2016.pdf (nist.gov) [2] BSI - Federal Office for Information Security - Study: Development status of quantum computer version 2.0 (bund.de) [3] Quantum Landscape 2023 (sam-jaques.appspot.com) [4] C. Zalka. Grover’s quantum searching algorithm is optimal. https://arxiv.org/pdf/quant-ph/9711070.pdf [5] NIST PQC FAQ. Post-Quantum Cryptography | CSRC (nist.gov) [6] V. Gheorghiu, M. Mosca. Global Risk Institute. GRI Quantum Risk Assessment Report – Part 3: A Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions - Improvements - Global Risk Institute [7] BSI - Bundesamt für Sicherheit in der Informationstechnik - BSI TR-02102-1: "Cryptographic Mechanisms: Recommendations and Key Lengths" Version: 2023-1 [8] S. Jaques, M. Naehrig, M. Roetteler, F. Virdia. Implementing Grover oracles for quantum key search on AES and LowMC. https://eprint.iacr.org/2019/1146.pdf [9] E. Parker, M. Vermeer. RAND. Estimating the Energy Requirements to Operate a Cryptanalytically Relevant Quantum Computer (rand.org) [10] UK National Cyber Security Centre. Next steps in preparing for post-quantum cryptography - NCSC.GOV.UK 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 © 2024 EMVCo, LLC. All rights reserved.