Quantum Computing Threat

Full Title or Meme

Successful Quantum Computing creates an existential threat to existing cryptographic algorithms since quantum computing algorithms exist to crack traditionally intractable problems like factoring the multiplication of two large primes used in RSA.

Context

Public key cryptography relies on certain mathematical problems that are very hard to solve, such as factoring large numbers that are the product of large prime numbers or finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point. If you know the private key components, you can sign the document or decrypt the data. If you don't have the private key and cannot solve the math, you cannot sign the document or decrypt the data.

Problems

• Good summary by some of the giants in the field have determined that Artificial Intelligence adds to the growing threat from Quantum computing to make breaks even more probable in 2024.
• Many systems exist which depend on existing public key technology. Some of these are embedded in hardware that cannot be changed once deployed.
• Existing signatures or encrypted files will continue to need to be processed for many years to come. Certificate keys have a life time of up to 25 years.
• The approval process for new cryptographic algorithms takes many years of standardization and test to be sure that the work effort to brake them is sufficiently high.
• Most of the challenges to the Quantum Computing Threat are to be found in the current reliance on Public Key Cryptography for protecting the internet. See that page for more details on this particular threat.

Solutions

Public Key Cryptography has many benefits over Secret Key Cryptography, the effort to create new algorithm to preserve the current PK protocols is underway now triggers for deprecation of RSA and some EC have already been set to the publication of new QR standards by NIST. It is now expected that the RSA and EC algorithms will be accepted by the government until 2035. These dates are subject to revision.

Here is a good summary of the solutions from Cloudflare.

Post Quantum Cryptography

This section details current efforts to address the threat to existing computing and networking infrastructures with most recent at the top of the list.

• Some of the post quantum data fields are very much longer than was the case for RSA and EC. See the wiki page on TLS for the issues that still need to be addressed there. 2024-05
• Past transitions from one crypto framework to another have been ad hoc and uncovered challenges caused by a lack of foresight into the challenges. Many deployments using cryptography have been optimized with different layers of the deployment handling different parts of the workload. As is usual with such optimizations, agility is severely reduced. It is unclear where such framework could or should be designed, academia has not considered agility an interesting problem. The US government is not engaged in creating a network of cloud providers might be willing to create some sort of framework that would address their issue. Industry tends to let the smaller players provider cryptographic solutions which are not optimized for their users.

  ...there is a glaring gap in the mix: our cryptography does not come with frameworks that prepare us for and facilitate transition. Without comprehensive frameworks, this manual effort to make a transition becomes an overwhelming challenge, and one that tens of thousands of organizations worldwide, even with security savvy operations teams, struggle to put into practice.

• Design choices for post-quantum TLS 2024-03-30 Eric Rescorla. Until recently, CTO Firefox, now just another guy on the Internet.
• NIST Releases First 3 Finalized Post-Quantum Encryption Standards 2024-08-13
• H.R.7535 - Quantum Computing Cybersecurity Preparedness Act (2022-12-21) requires OMB to get plans in place one year after NIST creates a new set of standards.
• NSA Releases Future Quantum-Resistant (QR) Algorithm Requirements for National Security Systems released 2022-09-07 and existing RSA and EC algorithms will be deprecated automatically when new specs for CRYSTALS-Kyber and CRYSTALS-Dilitium are released.
• Announcing the Commercial National Security Algorithm Suite 2.0
• NIST Selects Post-Quantum Algorithms for Standardization (2022-07-13)
• NIST Announces First Four Quantum-Resistant Cryptographic Algorithms US agency reveals the first group of winners from its six-year competition. (2022-07-05)

  The four algorithms contribute to NIST’s ongoing post-quantum cryptographic standard and will be finalized in roughly two years. They are available on NIST’s website, and are referred to as Crystals-Kyber, Crystals-Dilithium, Falcon and SPHINCS+.

• CRYSTALS = The "Cryptographic Suite for Algebraic Lattices" (CRYSTALS) encompasses two cryptographic primitives: Kyber, an IND-CCA2-secure key-encapsulation mechanism (KEM); and Dilithium, a strongly EUF-CMA-secure digital signature algorithm. Both algorithms are based on hard problems over module lattices, are designed to withstand attacks by large quantum computers, and have been submitted to the NIST post-quantum cryptography project.
• Quantum-safe cryptography fundamentals, current developments and recommendations Federal Office for Information Security (2021-10)
• Post-Quantum Encryption: A Q&A With NIST’s Matt Scholl 2021-10-27
• Crypto Agility: Considerations for Migrating to Post-Quantum Cryptographic Algorithms NCCoE 21-06-05 cue on 2021-07-07
• Getting Ready for Post-Quantum Cryptography: NIST 2021-04-28 - Exploring Challenges Associated with Adopting and Using Post-Quantum Cryptographic Algorithms
• MIGRATION TO POST-QUANTUM Cryptography William Barker, Murugiah Souppaya NIST 2021-06
• "Report on Post-Quantum Cryptography"
• ImperialViolet: Post-quantum confidentiality for TLS (2018-04-11)

Post Quantum Status

• The Commercial National Security Algorithm Suite 2.0 and Quantum Computing FAQ 2024-06
• The state of the post-quantum Internet The state as determined by CloudFlare on 2024-03-05 basically says that we need to have PQC deployed by EOY 24 for TLS and code-signing, which means that the first users can be expected on the date to find support from the services.
• Post-Quantum Cryptography for Engineers IETF 2023-08-30 draft-ietf-pquip-pqc-engineers-00
• Migration to Post-Quantum Cryptography The National Cybersecurity Center of Excellence (NCCoE) (Preliminary Draft 2023)
• Post-quantum cryptography is too damn big. 2024-03-22 "there has not been enough discussion about how what NIST has standardized is simply not good enough to deploy on the public web in most cases."
• Mastodon picked P
• Apple picked pq3 - PQ3 is the first messaging protocol to achieve what Apple calls “Level 3 security.”
• NSA site is updated from time to time

Post Quantum Browsers

Several browsers have started incorporating support for PQC in 2024.

• Google Chrome: Google Chrome has taken a significant step by adding support for a hybrid post-quantum cryptographic algorithm. Specifically, it now supports the X25519Kyber768 algorithm. This marks a crucial milestone as it’s the first algorithm to be supported by commonly used clients (browsers) and servers. Additionally, Google has announced that they are rolling out support for X25519Kyber768 to their servers as well.
• Cloudflare: Cloudflare, a major content delivery network and security provider, has made strides in securing connections with post-quantum cryptography. Nearly two percent of all TLS 1.3 connections established with Cloudflare are now secured using post-quantum cryptography. They anticipate double-digit adoption by the end of 2024. Cloudflare also introduced a post-quantum secure connection for their Cloudflare Tunnel service.
• Apple: In February 2024, Apple announced that it will secure its iMessage platform with post-quantum cryptography before the end of the year. This move reflects the growing awareness of the quantum threat and the need to transition to more resilient cryptographic methods.
• Let’s Encrypt’s Stance: Let’s Encrypt, like other publicly trusted certificate authorities, adheres to the CA/B Forum baseline requirements. Currently, these requirements do not permit the issuance of post-quantum key types. Any official testing by Let’s Encrypt would need to occur in untrusted environments, such as their staging environment. The challenge lies in the lack of consensus on post-quantum algorithms. NIST aims to standardize at least three digital signature algorithms, which could be used for certificates. Additionally, new key encapsulation methods are being explored. The exact mix of classical and post-quantum crypto remains uncertain. Therefore, Let’s Encrypt awaits a clearer roadmap before diving into PQ certificate issuance.
• Algorithm Uncertainty: The DigiCert guide suggests generating an eXtended Merkle Signature Scheme root, a Dilithium intermediate (NIST’s intent for standardization), and a Rainbow leaf certificate (a NIST PQC round 3 finalist, albeit with security concerns). While a Let’s Encrypt staging environment for PQ testing would be valuable, it’s essential to resolve algorithm choices before implementation.

References

Other Material

• For more information on Quantum Information Theory see that page in this wiki.
• It is likely that this threat was known to the NSA in Summer 2015 based on their action on Suite B.