PQConnect: Automated Post-Quantum End-to-End Tunnels

PQConnect: Automated Post-Quantum End-to-End Tunnels

Speakers: Daniel J. Bernstein, Professor, University of Illinois Chicago (presenting joint work with Tanya Longa and Bian)

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=fH07jnNMfI4

Overview

This talk introduces PQConnect, an innovative system designed to establish automated, end-to-end post-quantum secure tunnels for all network traffic originating from a host. Developed as joint work by Daniel J. Bernstein, Tanya Longa, and Bian, PQConnect addresses the critical and looming threat posed by quantum computers to current cryptographic standards, particularly TLS (Transport Layer Security). The project aims to accelerate the deployment of Post-Quantum Cryptography (PQC) on the internet by providing a solution that requires no application modifications or prior peer-specific configuration, a significant departure from traditional VPNs.

The core problem PQConnect tackles is the "harvest now, decrypt later" strategy employed by large-scale adversaries, who are currently collecting encrypted internet traffic with the anticipation of decrypting it with a future quantum computer. While some progress has been made in PQC integration (e.g., Cloudflare's 34% PQC connections), universal deployment remains a distant goal due to the complexity of updating countless applications and protocols. PQConnect offers a practical, immediate, and scalable approach to secure communications against quantum threats, making it a vital contribution to network security in the quantum era.

Background

▶ Watch: The urgent problem: Pre-quantum TLS and data collection (2:15)

The current state of internet security, particularly regarding TLS, is fraught with vulnerabilities. The presenter highlighted a "gruesome" list of TLS CVEs, citing recent examples like a Nginx vulnerability (CVE not specified, but mentioned as allowing client authentication bypass via TLS session tickets) and a VH updater flaw enabling man-in-the-middle attacks due to improper certificate validation. These examples underscore the immense complexity and inherent fragility of deploying TLS correctly across a vast ecosystem of protocols and applications. Many applications still lack any TLS protection, leaving significant portions of internet traffic exposed.

Beyond these immediate vulnerabilities, the overarching "elephant in the room" is the reliance on pre-quantum cryptography for the vast majority of current TLS deployments. The Snowden revelations of 2013 confirmed that state-level actors are actively collecting encrypted internet traffic, anticipating the future development of quantum computers capable of breaking current cryptographic algorithms. This "harvest now, decrypt later" threat necessitates an urgent transition to Post-Quantum Cryptography (PQC). While some entities like Cloudflare have begun integrating PQC into their TLS stacks, reporting around 34% of their connections using PQC libraries, this represents only a fraction of global internet traffic and is limited to connections directly with their servers, not universal end-to-end protection.

Existing solutions like VPNs offer a partial answer by tunneling traffic. VPNs provide a significant software engineering advantage: they can protect all applications on a machine without requiring modifications to those applications. Some VPNs, such as Mulvad and Rosenpass (using classic McEliece and Kyber) and OpenVPN (using Streamlined NTRU Prime), have already begun integrating PQC. However, traditional VPNs typically present two major limitations: they often function as proxies, providing protection only from the client to the proxy server, leaving traffic beyond the proxy unprotected (not end-to-end); and they generally require pre-configuration to communicate with known, specific endpoints, making them unsuitable for arbitrary, on-the-fly peer discovery for end-to-end tunnels. This gap – the need for automatic, end-to-end post-quantum protection without prior configuration or application changes – is precisely what PQConnect aims to fill.

Key Findings

▶ Watch: The challenge: Universal PQC without application updates (3:30)

PQConnect introduces several key innovations that collectively enable its unique value proposition: automated, end-to-end post-quantum secure tunnels without the need for application modification or prior peer configuration.

The most significant finding is the novel DNS-based peer discovery mechanism. Instead of requiring clients to be pre-configured with server information or to send out-of-band requests, PQConnect leverages DNS CNAME records to advertise server support for PQC and convey essential cryptographic material. When a PQConnect-enabled client performs a standard DNS query for a server that supports PQConnect, the DNS response includes a CNAME record containing a "magic number" (PQ1) indicating PQC support, followed by a base32 encoded hash of the server's long-term public key. This allows clients to discover PQC-capable servers and their public keys passively, without generating additional network requests or imposing overhead on non-PQConnect clients, which simply ignore the extra CNAME information.

Another critical finding is the efficient routing of traffic through the PQConnect client. To protect all application traffic without modification, PQConnect intercepts application-level DNS queries (e.g., getaddrinfo). When a PQC-enabled server is identified via its DNS CNAME record, PQConnect modifies the DNS response to return a local IP address instead of the server's actual IP. This local IP is routed internally to the PQConnect client, which then establishes an end-to-end post-quantum tunnel to the actual server. This network address translation (NAT)-like approach ensures that all TCP/UDP connections initiated by applications are automatically funneled through the PQConnect tunnel, providing transparent protection.

The system employs a hybrid post-quantum and pre-quantum key exchange protocol, offering robust security guarantees. By combining established pre-quantum schemes with emerging PQC candidates, PQConnect ensures that the security of the tunnel is at least as strong as the best available classic cryptography, even if the PQC schemes are later found to be vulnerable. The handshake message has been formally modeled in Tamarind and proven to possess critical security properties, providing a high level of assurance in its cryptographic design.

Finally, PQConnect incorporates features to protect against physical server attacks. Recognizing that server compromise could lead to the exposure of cryptographic keys, the system ensures that ephemeral key material is erased after at most two minutes. This aggressive key erasure policy significantly limits the window of opportunity for attackers to recover session keys and decrypt past traffic, even if they gain physical access to a server. This design choice enhances the forward secrecy properties of the tunnels against sophisticated adversaries.

Technical Deep Dive

▶ Watch: VPNs: Application-agnostic PQC with end-to-end limitations (3:50)

PQConnect operates as a sophisticated tunneling application that transparently secures network traffic using post-quantum cryptography. Its architecture integrates several components to achieve its goals: DNS-based peer discovery, dynamic traffic interception, and a robust hybrid key exchange protocol.

The foundation of PQConnect's automation lies in its DNS-based peer discovery. When a client application resolves a hostname, the PQConnect client intercepts the DNS query. If the target server supports PQConnect, its DNS records will include a specially crafted CNAME record. For example, a query for www.pqconnect.net might return:

www.pqconnect.net CNAME PQ1.abcd...xyz.pqconnect.net

PQ1.abcd...xyz.pqconnect.net A 192.0.2.1

In this structure:

• PQ1 serves as a magic number, signaling to PQConnect clients that the server supports the protocol.
• abcd...xyz represents a base32 encoded hash of the server's long-term public key. This hash acts as a unique identifier and a public key commitment for the server.

A PQConnect-enabled client, recognizing the PQ1 prefix, extracts the public key hash. This allows the client to identify PQC-capable servers and retrieve their public key information without sending any additional network requests beyond the initial DNS lookup. Non-PQConnect clients simply follow the CNAME chain to the final A record, ignoring the PQC-specific information, ensuring backward compatibility and minimal overhead.

Once a PQC-capable server is discovered, PQConnect needs to ensure that all subsequent application traffic to that server is routed through its secure tunnel. This is achieved through a clever traffic interception and routing mechanism. When an application makes a system call like getaddrinfo to resolve a hostname, the PQConnect client intercepts this call. If the hostname corresponds to a PQConnect-enabled server, instead of returning the server's actual public IP address (e.g., 192.0.2.1), PQConnect returns a local, loopback-like IP address (e.g., 127.0.0.X). The application, unaware of this substitution, then attempts to establish a TCP connection to this local IP address. The PQConnect client, listening on this local IP, transparently captures the connection, initiates a post-quantum handshake with the actual remote server, and then tunnels the application's traffic. This effectively acts as a transparent Network Address Translation (NAT) layer at the client, redirecting all relevant application traffic through the secure tunnel without any application-level modifications.

The key exchange protocol is a critical component, designed for robustness against both classical and quantum adversaries. PQConnect employs a hybrid key exchange that combines multiple cryptographic primitives. As illustrated in the talk, the key exchange leverages a layered approach, where secrets derived from outer schemes protect inner schemes. The specific schemes utilized by PQConnect include:

• Kyber-1024: A lattice-based PQC key encapsulation mechanism (KEM), providing protection against quantum attacks on key exchange.
• McEliece-348864: A code-based PQC KEM, offering an alternative PQC primitive for diversity and robustness.
• X25519: A pre-quantum elliptic curve Diffie-Hellman (ECDH) key exchange, ensuring security against classical attacks and providing a fallback in case PQC schemes are compromised.
• AES-256-GCM: A symmetric encryption algorithm used for authenticated encryption of the tunnel traffic.

This hybrid approach ensures that the security of the overall tunnel is not solely dependent on the unproven resilience of a single PQC primitive. If any one of the PQC schemes were to be broken by a quantum computer, the presence of other PQC schemes and the classical X25519 ensures that the communication remains protected at least to the level of the strongest unbroken scheme. The entire handshake message structure has been formally modeled using the Tamarind protocol verifier, allowing for rigorous mathematical proofs of its security properties, including authenticity and confidentiality.

To address the practical concerns of large public keys associated with some PQC schemes (like McEliece), PQConnect implements efficient key caching. Once a client obtains a server's long-term public key (via the DNS hash and an initial handshake), it caches this key. This significantly reduces the frequency with which clients need to request and process large public keys, improving performance and minimizing network overhead for subsequent connections to the same server.

Finally, PQConnect incorporates a strong defense against physical server compromise through ephemeral key erasure. All session keys and other sensitive ephemeral cryptographic material are actively erased from memory after a maximum of two minutes of use. This ensures that even if an adversary gains physical access to a server and extracts its memory contents, the window for recovering active session keys to decrypt past traffic is extremely limited, enhancing forward secrecy.

Demo / Proof of Concept

▶ Watch: Introducing PQConnect: End-to-end, automatic post-quantum tunnels (5:30)

While the talk itself did not feature a live, interactive demonstration, the presenter confirmed the existence and accessibility of a functional implementation of PQConnect. The project is publicly available, allowing interested parties to download, run, and explore its capabilities. The presenter directed the audience to www.pqconnect.net for access to the software, paper, and documentation. This publicly available implementation serves as a robust proof of concept, demonstrating that the automated, end-to-end post-quantum tunneling mechanism is not merely theoretical but has been successfully engineered and deployed. The website itself, www.pqconnect.net, likely utilizes PQConnect for its own secure communication, providing a real-world example of its functionality. Furthermore, the mention of a ZULIP server indicates an active developer community and ongoing project development, inviting feedback and contributions from the security community.

Defensive Implications

▶ Watch: How PQConnect uses DNS for server advertisement and discovery (6:40)

PQConnect offers several critical defensive implications for individuals, organizations, and the broader internet ecosystem grappling with the transition to post-quantum cryptography:

1. Accelerated PQC Deployment: The most significant defensive benefit is PQConnect's ability to rapidly deploy post-quantum cryptography without requiring changes to existing applications. This bypasses the immense logistical challenge of updating countless software packages, libraries, and protocols, offering an immediate pathway to protect against the "harvest now, decrypt later" threat. Defenders can deploy PQConnect at the host level (client and server) and instantly secure all application traffic.

1. True End-to-End Post-Quantum Security: Unlike many proxy-based VPN solutions, PQConnect provides genuine end-to-end encryption from the client host to the server host. This eliminates the vulnerability window where traffic might be decrypted and re-encrypted at an intermediate proxy, significantly enhancing the overall security posture against man-in-the-middle attacks and data exposure at transit points.

1. Automatic Peer Discovery and Configuration: The DNS-based peer discovery mechanism simplifies the deployment and management of secure connections. Defenders do not need to pre-configure VPN tunnels for every server or peer, reducing operational overhead and the potential for configuration errors. This automation makes it practical to secure communications with arbitrary, previously unknown endpoints.

1. Hybrid Cryptographic Resilience: By implementing a hybrid key exchange combining multiple PQC schemes (Kyber, McEliece) with a robust pre-quantum scheme (X25519), PQConnect provides a layered defense. This approach offers resilience against potential future breaks in any single PQC candidate, ensuring that the security of the tunnel is maintained at the highest possible level available, even as PQC research evolves.

1. Mitigation of Physical Server Attacks: The aggressive key erasure policy (keys erased within two minutes) directly addresses the threat of physical server compromise. This feature significantly limits the utility of extracted memory contents for decrypting past traffic, enhancing forward secrecy and protecting sensitive data even in highly adversarial environments.

1. Highlighting DNS Security Importance: While PQConnect offers robust cryptographic protection, its authenticity model critically depends on the security of the underlying DNS infrastructure. As noted in the Q&A, if an attacker can control DNS records for a server, they could potentially impersonate that server, just as they could obtain a fraudulent TLS certificate. This underscores the imperative for robust DNS security measures, such as DNSSEC, and the adoption of secure DNS transport protocols like DNS over TLS (DoT), DNS over HTTPS (DoH), or even DNS over PQConnect itself, to ensure the integrity of the peer discovery process. Defenders must ensure their DNS infrastructure is adequately protected.

1. Future-Proofing Communications: By enabling PQC now, organizations can begin to future-proof their communications against the anticipated advent of cryptographically relevant quantum computers. This proactive stance is crucial for protecting long-lived sensitive data that must remain confidential for decades.

Key Takeaways

• Automated End-to-End PQC Tunnels: PQConnect establishes post-quantum secure tunnels automatically between client and server, providing end-to-end protection for all application traffic without requiring modifications to applications.
• DNS-Based Peer Discovery: It innovatively leverages standard DNS CNAME records to advertise server support for PQC and convey public key hashes, enabling passive and efficient peer discovery without additional network requests.
• Transparent Traffic Routing: PQConnect intercepts application DNS queries and redirects connections to local addresses, transparently routing all traffic through the secure post-quantum tunnel.
• Robust Hybrid Key Exchange: The system employs a hybrid cryptographic handshake combining Kyber-1024, McEliece-348864, and X25519, formally verified with Tamarind, to ensure resilience against both classical and quantum attacks.
• Enhanced Physical Security: Ephemeral session keys are aggressively erased from memory within two minutes, significantly limiting the window for adversaries to decrypt past traffic even if a server is physically compromised.
• Critical Dependency on DNS Security: The authenticity of PQConnect's tunnels relies on the security of the underlying DNS infrastructure; robust DNSSEC and secure DNS transport protocols are essential for full protection.

About the Speaker(s)

The talk on PQConnect was presented by Daniel J. Bernstein, a distinguished Professor at the University of Illinois Chicago. Professor Bernstein is a highly respected figure in the fields of cryptography, computer security, and number theory, known for his significant contributions to cryptographic primitives and security protocols. His work often focuses on practical and efficient cryptographic solutions. He presented this work as a joint effort with Tanya Longa and Bian, whose specific affiliations were not detailed in the transcript but who are integral to the PQConnect project. His expertise in designing and analyzing secure systems is evident in the robust and innovative architecture of PQConnect, which addresses a critical challenge in the evolution of internet security.