Post-Quantum Cryptography in January 2024

Post-Quantum Cryptography (PQC) gets a fair bit of attention, but it can be difficult to quickly grasp what the current state in the industry is. In this post, I'll try to summarize where we are as of January 2024, as best as I can tell.

But beware: I'm neither a physicist nor a cryptographer, just an accidental infosec nerd of very little brain (thinking of things that seem very thingish) so you pretty much get what you paid for.

Number of Qubits

Rather than using binary digits ("bits"), quantum computers use "qubits"¹, which are said to exist in a coherent superposition of two states -- until measured, at which point they collapse into a classical (i.e., binary) state. In addition, quantum entanglement ("spooky action at a distance") allows for increased information storage and can be used in, for example, Quantum Key Exchange protocols in Quantum Key Distribution (QKD).

Thing is, maintaining qubit coherence (i.e., their quantum mechanical properties and behavior) has proven to be tricky. Only recently have companies been able to produce quantum computers with more than just a few individual qubits: In 2006, 12 qubits was all we got, and the 50 qubits IBM presented in 2017 remained coherent for only 90 microseconds. But it looks like progress is consistently being made:

Timeline graph of
Quantum Computing Capability of Time as # of qubits
by year, showing data points: 1998:3, 2000:7, 2005:8,
2006:12, 2011:14, 2017:50, 2018:72, 2020:76, 2021:127,
2022:433, 2023:1121 — Google "Bristlecone": 72 qubits; USTC Jiuzhang: 76 qubits; IBM Eagle: 127 qubits; IBM Osprey: 433 qubits; Atom Computing: 1,180 qubits

The latest accomplishments are the IBM Condor (1,121 qubits) and the Atom Computing atomic array (1,180 qubits), both towards the end of 2023, showing an increasing acceleration in the number of qubits.²

Q-Day

The term "Q-Day" refers the day when cryptographically relevant quantum computers (CRQCs) can break common (classic) cryptographic protocols using quantum algorithms.

Star Trek's 'Q' as a Mariachi with a trumpet on
the Enterprise's bridge

In a nutshell, we consider symmetric key cryptography to be largely quantum safe: Grover's algorithm reduces the time to break an N-bit hash from 2ⁿ to 2^n/2 iterations, but does not provide exponential speedup: doubling the key size will still increase the key space the algorithm has to search and thus the time to break the key at the same ratio as in a classical algorithm. In other words, we move to, say, 512-bit or 1024-bit keys and we should be fine.

Asymmetric key cryptography, however, is subject to Shor's algorithm for factorization, which would break e.g., RSA and Diffie-Hellman (including Elliptic Curve Diffie-Hellman or ECDH). But here the question is: how many qubits do you need before you can practically break RSA? The answer is... not straight forward.

On the one hand, you have plain old big-O notation considerations based on the runtime of Shor's algorithm and a number of very loose, hand-waving "experts say" statements³, estimating the number at around 4,000 qubits. The problem here is that those estimates are based on perfectly stable qubits, which isn't realistic at all -- at least not today: those pesky qubits tend to interfere, suffer from quantum noise, and rapidly lose their quantum properties.⁴

Using logical qubits on top of multiple physical qubits can improve stability, add error detection and fault tolerance. To practically break RSA, you would then need many (many!) more physical qubits to provide the required number of logical (i.e., usable and stable) qubits. And for that, you again get completely wild estimates that range from a cool (Dr. Evil pinky-in-mouth) 1 billion qubits (apparently in here, 2012) across Google's 20 million estimate (2019) to a "researchers say it might take 1 million" (2023)⁵.

But here, too, we can see a trend: the estimates are shrinking dramatically, just as the number of possible qubits per quantum computer increases dramatically. Q-Day is found at the intersection of these two lines, and it's widely estimated to fall within the next 5 to 10 years, which aligns with the NSA guidance that aims to have all National Security Systems to be quantum-resistant by 2035.^6 7

Post-Quantum Cryptography

In order to protect our data against cryptanalytic attacks using quantum computers, we therefor need new algorithms that cannot be broken even using such quantum algorithms as those mentioned above. For this, NIST has been working on Post-Quantum Cryptography Standardization efforts that began in 2016, and which converged on several distinct approaches, including:

After several rounds of submissions (and a fair bit of nerdy Star Wars references) we're now at a point where several new algorithms have been selected for standardization:

Hybrid Specifications

Ok, so as of January 2024, the standards are just about to be finalized, and nobody expects any surprises or dramatic changes; RFCs are not yet published and Q-Day still looks to be a few years out - so what's the rush?

Well, if you look at the predicted timeline, then you should note that this places a particular attack vector straight into most organizations' threat model: Harvest Now, Decrypt Later. That is, capable adversaries may already passively collect data encrypted using classic algorithms even though they currently can't decrypt them, but with the expectation that within a few year's time, they will be able to. And there's a lot of data crossing the wires that will still be valuable even in 10 years time, including PII, financial information, and even difficult to rotate encryption keys or other secrets.

The good thing is that we don't need to implement fully quantum-resistant algorithms everywhere right now if we can implement parts of our common asymmetric cryptography protocols with a hybrid approach: if we perform the Key Exchange using a combination of a classic and a post-quantum algorithm, then we can continue to use a classic symmetric algorithm such as AES with a sufficient key length for the actual data encryption.

By using a combination, we ensure that an attacker has to be able to break both, and any concerns around possible implementation errors of a not-quite-yet standardized, new post-quantum algorithm won't lead to fatal failure modes. For this we now have additional IETF drafts: Hybrid key exchange in TLS 1.3 and X25519Kyber768Draft00 hybrid post-quantum key agreement⁸, which several parties in the industry have already begun to implement to help stem the Harvest Now Decrypt Later problem until the complete standards and RFCs are eventually finalized.

Who's Doing PQC?

Ok, so who is actually ahead of the curve and has implemented either X25519Kyber768Draft00 or any other hybrid solution? Let's take a look:

👉 Google announced in August 2023 that Chrome would support X25519Kyber768 starting with Chrome 116. This is enabled via an experimental flag (#enable-tls13-kyber); at the same time, Google's servers now also support this key exchange algorithm in both TCP and QUIC.

👉 Microsoft Edge, being Chrome based, also supports this flag. However, Edge also offers a flag called edge-post-quantum-kyber which promises to "Enable Kyber768 + NIST-P384 TLS Kyber Confidentiality", which then should show you "P384Kyber" as the Key Exchange. This test page then shows a successful connection using ecdsap256-p384_kyber768.

👉 In September 2023, Cloudflare announced that they had enabled X25519+Kyber for general availability, meaning as of today most sites fronted by Cloudflare should support a quantum-resistant connection.

👉 Mozilla just added support for X25519Kyber768Draft00 (aka xyber768d00) in Firefox Nightly on 2024-01-18, although I can't find a good tracking ticket for this (1871629 seems a bit slim on details). To enable this feature, you need to set security.tls.enable_kyber in about:config.

👉 OpenSSH 9.0 (released on 2022-04-08), enabled Streamlined NTRU Prime + x25519 Key Exchange (sntrup761x25519-sha512@openssh.com) by default.

👉 Signal is using "Post-Quantum Extended Diffie-Hellman” (PQXDH) since 2023-09-19. I imagine that this will (if it hasn't already) also flow into WhatsApp and Google Rich Communication Services (RCS).

👉 Amazon added ECDH+Kyber hybrid key exchanges to their s2n-tls and s2n-quic implementations and is now using those in AWS KMS.

👉 Amazon also uses ECDH+Kyber hybrid key exchanges (e.g., ecdh-nistp256-kyber-512r3-sha256-d00@openquantumsafe.org etc.) in their AWS Transfer Family through the use of the OpenQuantumSafe OpenSSH fork.

In addition to the above, common libraries or toolkits that include support for post-quantum cryptography, including hybrid key exchanges include:

Who's not doing PQC?

I was unable to determine the current status or any public plans announced by Apple for macOS, Safari etc. I wouldn't be surprised if they were actively adding support and slide it into one of the next releases, but with Apple's secrecy you never know.⁹

Similarly, I did not find any specific plans from Facebook / Meta indicating their PQC plans (although back in 2016, they provided the 2016 Internet Defense Prize to researchers for their work on a Post-Quantum Key Exchange named "A New Hope" -- the Star Wars references just keep coming).

Interestingly, both Baidu and Alibaba shut down their quantum computing research facilities late last year, with Baidu "donating" theirs to the Beijing Academy of Quantum Information Sciences, while Alibaba "donated" their lab and equipment to Zhejiang University. (Both of these institutions are largely government funded or operated, which is why I took the liberty of adding scare quotes here.)

What does using PQC look like today?

Browsers

Ok, let's take a look. As noted above, we can already use PQC today. For Chrome, simply toggle #enable-tls13-kyber to true in chrome://flags:

Then, head on over to www.google.com or a Cloudflare-fronted website, such as e.g., pq.cloudflareresearch.com. In your developer tools (View->Developer->Developer Tools), you should now be able to view the key exchange algorithm used under the "Security" tab as X25519Kyber768Draft00 -- hooray!

For Firefox Nightly with about:config -> security.tls.enable_kyber set to true, that looks like this:

If you want to look at the packets on the wire, your good friend Wireshark can also already identify these key exchange algorithms for you:

OpenSSH

If you have OpenSSH >= 9.0, no action is needed -- the power of defaults! You get a quantum-resistant key exchange for free:

$ ssh -Q kex
[...]
curve25519-sha256
curve25519-sha256@libssh.org
sntrup761x25519-sha512@openssh.com
$ ssh -v server
[...]
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: sntrup761x25519-sha512@openssh.com
debug1: kex: host key algorithm: ssh-ed25519
[...]

Conclusion

Well, and there we are. As best as I can tell, this is where things stand as of the end of January 2024. The standardization efforts for post-quantum cryptographic algorithms is nearing the end, and we don't expect any major surprises here. The industry is (somewhat carefully) adopting hybrid key exchanges from internet drafts before the standardization process has finished, so as to mitigate the Harvest Now, Decrypt Later attack vector.

Government and industry consensus appears to be largely that "Q-Day" is still several years out, primarily because of the difficulty of creating quantum computers with stable qubits, although it seems rather difficult to get reasonable estimates on that. All estimates, however, appear to be dramatically falling, while practical capabilities are increasing.

If you're working in the industry, it's probably high time that you sort out your own post-quantum roadmap. Adopting developing implementations will require you to keep up to date with software providers and not run old and unsupported releases; for your internal infrastructure, you want to focus on cryptographic agility so that you can swap in PQC ciphers and protocols as they mature. And time is starting to run out...

[1] I'm not even going to try to properly explain any of this; there are much better blog posts that can help you understand this, although Wikipedia is of course also a pretty good starting point.

[2] In 2022, D-Wave and the Jülich Supercomputing Center announced a quantum computer with more than 5,000 qubits. However, this computer is a quantum annealer, which doesn't lend itself to general-purpose computing such as performed using quantum gates and circuits.

[3] I can't pinpoint where the original estimate comes from exactly, but most articles seem to cite either 4,000 or 4,099 qubits as necessary to break 2048-RSA:

[4] Qubit coherence times are all over the map, it seems, and depend on the type of qubit used. On the one hand, you get electron charge qubits with 0.1 millisecond coherence times, on the other you have an YB⁺ Ion qubit with > 1h coherence time. Atom Computing's announcement in October 2023 claimed 40 seconds coherence time...

[5] Google's paper uses a ratio of 1 logical qubit to 1,568 physical qubits. And then there's this paper that made the rounds last year, claiming an algorithm capable of breaking 2048-RSA using 372 physical qubits. (See also)

[6] Now some might suspect that the NSA has advanced well beyond the industry and that those timelines are not reflective of their capabilities. I don't think I buy this: at this time, the US Government is very strongly invested in public sector cloud infrastructure, and I don't know whether they could risk leaving significant branches of the government vulnerable.

[7] It's worth noting that the EU appears to be is trailing the US with regards to both preparedness statements, migrations strategies, and standardization efforts themselves. Of course other countries are looking at NIST and the public discussion around standardization, but ENISA and even EU member states' Cybersecurity agencies (such as e.g., the German Bundesamt für Sicherheit in der Informationstechnik) are only providing limited guidance (e.g., BSI's recommendations or ENISA's 2021 report).

Signs of Triviality