Beyond the handshake: where post-quantum work gets hard

The arrival of quantum computers that can break today’s public-key cryptography is no longer a hypothetical. The good news is that the cryptographic community has designed new algorithms meant to withstand those attacks, and we’ve shown in earlier posts how to swap them into the TLS handshake. But swapping algorithms in a laboratory or a single protocol is not the same as migrating the real Internet. The hard part of the post-quantum transition is not the math; it is everything around the math: authentication hierarchies, middleboxes, legacy protocols, and the sheer coordination required to move an entire ecosystem at once.

Authentication is the bottleneck

In TLS 1.3, confidentiality and integrity are relatively straightforward to make quantum-resistant: replace the key exchange with a post-quantum algorithm and the connection secret is safe, and the integrity protections hold because the algorithms are intractable on a quantum machine. Authentication is another story. There are three ways to authenticate in a TLS handshake:

  • A pre-shared key (PSK) derived from a previous, quantum-protected handshake — easily made post-quantum since the key itself comes from a secure run.
  • A Password-Authenticated Key Exchange (PAKE), such as OPAQUE or SPAKE, for handshake or post-handshake authentication.
  • Public certificates that assert identity — the dominant method in practice.

The first is trivial to secure. The second is theoretically solvable by swapping in post-quantum parameters, but it faces practical hurdles. The third is where the complexity lives. Certificate-based authentication is not one algorithm and one certificate; it is a chain of certificates starting from a root Certificate Authority (CA), passing through one or more intermediates, and ending at the leaf certificate of the party you are talking to. The whole system—root stores, CA membership programs, intermediate issuance, revocation via OCSP staples, and Certificate Transparency logs (SCTs)—is a tangle of policies, roles, and hardware security modules. In a typical TLS connection, the authentication step involves at least six signatures: one for the handshake, two in the certificate chain, and three more for the OCSP staple and SCTs. Of those last three, two are essentially patches for problems (revoked certs and rogue CAs) that were bolted on after the original design.

This is why post-quantum migration cannot be reduced to a code change in the TLS library. Updating the key exchange is simple; updating authentication means coordinating changes across CAs, browsers, operating systems, hardware vendors, and every server operator. And the question is worth asking: if we are already touching this system, should we keep the existing public-attestation model at all? The current PKI is notoriously difficult to maintain, update, revoke, model, and compose. The migration is a rare chance to reconsider—but even without redesigning the system, there are two classes of problems to solve:

  • Technical: Post-quantum signatures are larger and slower. Can they fit in handshakes? One idea is to cache intermediate certificates; another is to explore authentication without signatures altogether, as in KEMTLS.
  • Coordination: How do we sequence the upgrade across an interconnected system? What happens when some parties have moved and others have not? How do we revoke pre-quantum certificates cleanly?

PAKEs, DNSSEC, and other protocols lag behind

Password-based authentication has its own open questions. Most contemporary PAKEs rely on Diffie-Hellman assumptions that quantum computers can break. Some ideas for moving them to post-quantum settings exist, but they appear too inefficient to deploy. There is a saving grace, however: the notion of “quantum annoyance.” A quantum adversary attacking a PAKE must guess a password, solve a discrete logarithm for that guess, and only then check if the guess was correct. Each guess takes a full solve. With a large password space, this could slow a quantum attacker considerably, meaning current PAKE-based TLS may be safe for longer than other pieces of the stack. That is not a permanent reprieve, but it gives the ecosystem time.

TLS, however, is not the only protocol that matters. DNSSEC, WireGuard, SSH, and QUIC all need post-quantum transitions. DNSSEC is a particularly difficult case because the protocol struggles with large signatures and high verification costs. Research from SIDN Labs suggests that only Falcon-512 and Rainbow-I-CZ are suitable for DNSSEC among the signature schemes considered — and a recent attack on Rainbow has since undermined its viability. Alternatives are being explored:

  • SQISign, an isogeny-based signature scheme, could work if its verification time improves. As published, verification runs around 42 ms on a 3.40 GHz Intel Core i7-6700 (250 runs), slower than the classic P-384 curve. A more recent result brings it down to 25 ms.
  • MAYO, a different candidate, signs in about 2.50 million cycles and verifies in 1.3 million cycles on an Intel i5-8400H at 2.5 GHz.
  • Hash-based signatures, as suggested by Verisign, offer another route for zone signing.

Beyond DNSSEC, there are already proposals for post-quantum WireGuard and post-quantum SSH, but more work is needed to understand their real-world behavior. And through all of this, expect a lengthy hybrid period where classical and post-quantum algorithms run side by side. That hybrid mode is a hedge: if a post-quantum algorithm is broken, the classical algorithm still offers a floor of security. The details—single code point versus multiple, contingency planning—are still unresolved.

Learning from past failures

The hardest part of cryptography has always been the real world. Designing good algorithms is one thing; implementing and deploying them securely is notoriously error-prone. Flaws in security proofs, implementation bugs, constant-time failures, and side-channel attacks have all bitten us. For TLS 1.3, the community pushed back with rigorous verification of implementations and formal analysis of symbolic and computational models, work we have covered in prior posts on formal analysis with EasyCrypt and Jasmin. That level of scrutiny needs to become the default for post-quantum algorithms, not the exception.

Still missing on the verification front:

  • Guides that make formal analysis approachable for developers who do not speak the formal languages.
  • User-tested APIs for post-quantum primitives.
  • Clean integration of those APIs into protocol libraries.
  • Analysis of the boundaries between verified and unverified code.
  • Specification-level verification, for instance by embedding hacspec into IETF drafts.

Without that work, the post-quantum migration risks repeating the same security failures we have seen before. We want, as Ray Bradbury put it, better—not more of the same.

A post-quantum tunnel as a testbed

The challenges described above are long-term problems. In the shorter term, there is a concrete opportunity to push post-quantum cryptography into new corners of the network. Cloudflare Tunnel creates a secure, outbound-only connection between a customer’s services and Cloudflare’s edge through a lightweight connector. On the client side, WARP acts as a VPN that secures and accelerates HTTPS traffic. Adding post-quantum cryptography to both ends would create a server-to-client path—from a WARP client to a private network using Tunnel—that is secure against a quantum adversary.

The value is twofold. First, it gives us a real connection fully protected against quantum computers, which is worth having on its own. Second, it lets us measure the impact of post-quantum cryptography in a live environment, including on mobile devices, and produce practical guidance for migration. Tunnel uses QUIC in some configurations, and WARP is built on WireGuard, so this setup also offers a chance to experiment with post-quantum algorithms in protocols that have seen far less real-world testing than TLS. There is no full answer to the migration problem yet, but this is one way to start building the experience we will need.