Help! Quantum Computers are threatening our payments!

Introduction

Modern cryptography has been used to enable secure communications between individuals or servers, even if these entities do not share any pre-established secret. The cryptographic primitives allow kickstarting a secure channel primarily to deliver two main functionalities: protected channel establishment (known as key establishment) and authentication of digital information/parties (by the use of digital signatures). Once the channel is established, it can use other cryptographic primitives to secure communications over the Internet, provide the root of trust for secure transactions in the digital economy, and keep data private by encrypting it.

Quantum computing and its threats

The emergence of quantum computing poses a major threat to modern cryptographic primitives, which are based on modular arithmetic, whereby even the computationally hard problems that constitute the strength of these ciphers could be solved in reasonable time.

Quantum computing threats to asymmetric cryptography

The asymmetric cryptographic primitives we use today for digital signatures and key exchange will no longer be strong enough to keep data secret once a sufficiently powerful quantum computer can be built. The core cryptographic technologieslike RSA, and elliptic curve cryptographyno longer will be trustworthy.

RSA and elliptic curve cryptography primitives are built on complex mathematical problems such as integer factorization and computing discrete logarithms, which can only be solved if knowledge of some secret data is available typically a very large number. Without these numbers, it is impossible to reverse-engineer encrypted data or create a fraudulent digital signature. These numbers are what we know as cryptographic keys. For instance, the RSA algorithm [1] uses pairs of huge prime numbers to generate public and private keys. The public key can be used to create a mathematical challenge that can only be solved by someone who holds the private key. Attempting to guess the answer, by way of a brute-force search, would take thousands of years using contemporary computers. Unlike their classical counterparts, quantum computers can solve these mathematical problems incredibly quickly.

Quantum computing does not threaten symmetric cryptography

Quantum computing does not pose a fatal threat to symmetric cryptography such as AES, which uses different mathematics than its asymmetric counterparts. It is generally believed that if the key length is doubled, the symmetric cryptographic algorithms remain safe, even under quantum computer attacks.

Quantum computing threat triggered post-quantum cryptography research to design and develop post-quantum algorithms that can withstand quantum computing attacks.

Recent Analysis of quantum computing threats & predictions

23 December 2022, a group of Chinese searchers published a paper [6], they estimated possible to challenge RSA 2048 with only 372 physical qubits with their solution based on the Shor algorithm. Later, Fujitsu published an article [7] evaluating this breakthrough and concluding that quantum computing doesn’t pose an immediate threat yet to existing cryptographic methods. However, this threat is real and is coming closer every day. They estimate necessary to rely on 10,000 qubits with a 104-day long calculation to challenge RSA 2048.

Additionally, we identified in another blog delineated in claims the breaking of a RSA -2048 key. From studying the existing state of the art, we can identify the approximate estimations of quantum resources required to break popular cryptosystems as delineated in Table 1. Each listed algorithm in Table 1 is equivalent to 128 bits of security against classical adversaries.

Table 1. Estimates of quantum resources required to break popular cryptosystems [11]

Read this if you want to know more on these attacks:

From the existing work [11], we identified these asymmetric cryptographic primitives Discrete Logarithm (DL) over the NIST P-256 elliptic curve, RSA with 3072-bit modulus, and symmetric cryptographic primitives AES with a 128-bit key. These asymmetric and symmetric primitives are considered to have 128 bits of security against classical adversaries [12]. As seen in Table 1, the resources (size and time) required to break these cryptosystems are not the same. This has implications for how quickly these asymmetric and symmetric cryptographic primitives become vulnerable to attacks as quantum computers grow in size. For symmetric cryptosystems, Grover’s search does not have as much advantage over classical asymmetric cryptographic primitives as Shor’s algorithm. Hence breaking AES on a quantum computer is estimated to be extremely time-consuming and expensive compared to attacking vulnerable asymmetric cryptosystems with quantum computers. This study has been analyzed in the work [12], to break AES-128 requires a quantum computer 22 orders of magnitude larger than for breaking RSA. Furthermore, it is evaluated, that such a computer will take one year to break AES-128 compared to only one day to break an asymmetric algorithm. For asymmetric cryptographic primitives, there are smaller but still significant differences between the quantum resources required to break Elliptic curve cryptosystems, and RSA. RSA requires about 10 times the quantum memory of elliptic curve primitives, potentially extending its usefulness by several years [11].

To provide valid alternatives to the algorithms under threat, the NIST launched a Post-Quantum Cryptography (PQC) standardization challenge. On August 24, 2023, 3 PQC solutions were selected to be drafts for further standardization.

Latest status of NIST recommended post-quantum cryptographic (PQC) standards

On August 24, 2023,  the National Institute of Standards and Technology (NIST) released drafts of three post-quantum cryptographic (PQC) standards called ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism Standard - FIPS203) [2], ML-DSA (Module-Lattice-Based Digital Signature Standard – FIPS 204) [3], and SLH-DSA (Stateless Hash-Based Digital Signature Standard – FIPS 205) [4] standards. In addition to these standards, NIST is expected to release a standard draft for FALCON [5] later in 2024.

Table 2. Impact of Shor’s and Grover’s algorithms on Classical cryptographic primitives [13]

For symmetric cryptographic primitive AES, we can double the size of the security level to secure against quantum threats. However, all currently used asymmetric cryptography is not secure against quantum threats. Thus, there is a mandatory need to replace the classical asymmetric cryptographic primitives with the post-quantum cryptographic primitives. For example, we can replace asymmetric key exchange primitives DH and ECDH with ML-KEM (FIPS203), asymmetric signature schemes RSA, DSA, and ECDSA primitives with PQC primitives ML-DSA (FIPS 204), or SLH-DSA (FIPS 205).

The maturity in post-quantum research has led to the formulation of various post-quantum cryptographic algorithms, the standardization of post-quantum algorithms by various standardization bodies worldwide [14], industry adoption of post-quantum technology [14], and the development of open-source post-quantum libraries [14].

Overview of usage of cryptography in payments

Cryptography is the keystone of payments. The security for both card and card-less payments relies on cryptography to ensure data integrity, confidentiality, and non-repudiation. Now where do we rely on asymmetric cryptography?

In-store Card Payments:

Our physical card contains RSA or Elliptic Curve-based asymmetric cryptographic-based certificates, which are used to perform offline transactions. The terminal will accept the transaction without requesting on the fly your bank to validate the card. This can be achieved by cryptographic signature verification based on asymmetric RSA 2048 key size. In case the terminal goes online, request your bank to validate the transaction. The validation at the bank end is also based on cryptographic evidence mainly using symmetric cryptographic primitive AES 256 key size.

E-commerce Payments

In e-commerce transactions, security is provided by the TLS mechanism. TLS uses a combination of symmetric and asymmetric cryptographic primitives, as this provides a good compromise between performance and security when transmitting data securely. Following the NIST recommendation [8], the asymmetric cryptographic primitive RSA 2048 key size is the most used in the industry. For instance, EMV 3DS specification recommends RSA 2048 asymmetric cryptographic primitive key size [9] or above.

Disruptions in The Payment system

Today’s payment systems are heavily dependent on traditional cryptographic security protocols such as RSA 2048 and AES 256 to secure data and communications. As you deliberate, some years from now, quantum processors could expose the financial system to new forms of cyber-attacks, threatening any payment transaction as we know it today.

In its most recent global risks report, the World Economic Forum listed the cyber threat of quantum computing as one of the major emerging global technological risks [10]. This situation has called for collective action, including the development of new encryption standards capable of protecting financial services IT systems.

Harvest now, decrypt later

Presently functional quantum computers are not yet available, but the security threat is immediate and needs to be urgently addressed. Already, malicious actors can intercept and store confidential, classically encrypted data to decrypt it later when quantum computers become powerful enough to do so. This means that data stored or transmitted today are exposed to “harvest now, decrypt later” attacks by a future quantum computer.

To overcome these threats, we rely on Post-Quantum Cryptographic standards. However, PQC cryptographic primitives require big key sizes, and signature sizes, using significantly more memory and costly runtime in comparison with classical cryptographic schemes.

“How to start migration towards quantum-resistant solutions with current infrastructure” – you can read this in our second blog

References:

[1] R. Rivest, A. Shamir, L. Adleman. A method for obtaining digital for signatures and public-Key cryptosystems. ACM Commun. 1978, 21, 120-126.

[2] NIST. Module-lattice-based key-encapsulation mechanism standard. Available at https://csrc.nist.gov/pubs/fips/203/ipd .

[3] NIST. Module-lattice-based digital signature standard. Available at https://csrc.nist.gov/pubs/fips/204/ipd .

[4] NIST. Stateless hash-based digital signature standard. Available at https://csrc.nist.gov/pubs/fips/205/ipd .

[5] T. Prest, P.-A. Fouque, J. Hoffstein, P. Kirchner, et.al. FALCON. Technical report, National Institute of Standards and Technology, 2022. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 .

[6] B. Yan, Z. Tan, S. Wei, H. Jiang, et.al. Factoring integers with sublinear resources on a superconducting quantum processor. Available at https://arxiv.org/pdf/2212.12372.pdf

[7] Fujitsu. Available at https://www.fujitsu.com/global/about/resources/news/press-releases/2023/0123-01.html , Jan 23, 2023.

[8] NIST. Recommendation for Key Management, Jan. 2015 Available at https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57Pt3r1.pdf .

[9] EMV 3-D Secure. SDK Specification Version 2.2.0, Dec. 2018. Available at https://docs.3dsecure.io/3dsv2/_downloads/1810d5fa627b67a20136e12f8bde32b2/EMVCo_3DS_SDKSpec_v220.pdf .

[10] World Economic Forum (WEF) (2022): The Global Risks Report 2022, 17th edition. Available at https://www3.weforum.org/docs/WEF_The_Global_Risks_Report_2022.pdf .

[11] K. F. Hasan, L. Simpson, M. A. R. Baef, C. Islam, et. al. Framework for Migrating to Post-Quantum Cryptography: Security Dependency Analysis and Case Studies. IEEE Access. Available at https://arxiv.org/ftp/arxiv/papers/2307/2307.06520.pdf

[12] V. Gheorghiu and M. Mosca. Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes, 2019. Available at https://arxiv.org/abs/1902.02332 .

[13] S. Li, Y. Chen, L. Chen, and et. Al. Post-Quantum Security: Opportunities and Challenges. 2023. Available at https://www.mdpi.com/1424-8220/23/21/8744 .

[14] C. Balamurugan, K. Singh, G. Ganesan, M. Rajarajan. Post-Quantum and Code-Based Cryptography-Some Prospective Research Directions, 2021. Available at https://www.mdpi.com/2410-387X/5/4/38 .