Revisiting PQ-WireGuard with Reinforcing KEMs

The 2026 IACR ePrint 2025/1758 (Hashimoto–Katsumata–Niot–Wiggers, AIST + PQShield) is one of two concurrent independent works that revisit Hülsing et al.'s 2021 PQ-WireGuard. The other is hybrid-wireguard (Lafourcade et al., USENIX Security 2025). They overlap on the diagnosis (Hülsing's design has security gaps and a memory problem) and diverge on the fix.

The starting problem: WireGuard's handshake must fit in a single UDP packet (~1232 B for IPv6). ml-kem alone would blow that budget — two ML-KEM ciphertexts run ~1.5 kB. Hülsing et al. solved the wire-size problem with a Classic McEliece long-term key plus a Saber-IND-CPA ephemeral. But Classic McEliece public keys are ~261 kB, so the server now has to hold ~261 kB of long-term key per client. For kernel-level WireGuard implementations with strict memory budgets, this is a real deployment blocker.

What the paper fixes

Three contributions: design, computational security, efficiency.

Design. Hülsing et al. translated WireGuard's "IK" Noise pattern to KEMs ad-hoc — choices about which values to absorb into the KDF, in what order, were made one-by-one. The PSK got absorbed twice because KEMs (unlike DH) don't authenticate the client in the first round, breaking WireGuard's DoS-protection model. The redesign systematically handles KEM public keys and ciphertexts, leading to a more uniform key schedule and only one PSK inclusion. The findings translate back to PQ Noise as a side benefit.

Computational security. Hülsing's computational proof was for basic key indistinguishability only; the symbolic proof covered more notions. The paper extends the computational model to match the symbolic one, fixes a subtle bug in the prior model around PSK handling in the post-specified-peer setting (their proof was incomplete), and adds explicit modelling of entity authentication including KCI and unknown-key-share resistance. They observe an explicit UKS attack on the original PQ-WireGuard when instantiated with general KEMs — analogous to the KEM re-encapsulation attack on Signal's PQXDH.

Efficiency. This is the main practical contribution. They introduce reinforcing KEMs (RKEM) — a primitive where a long-term public key pk_C can be "reinforced" by an ephemeral pk_e. The point: in PQ-WireGuard the ephemeral doesn't need to be as secure as the long-term, so running two independent KEMs in parallel (the naïve construction) is wasteful. They build Rebar, an ML-KEM-style lattice RKEM whose ciphertext is roughly 40% smaller than two ML-KEMs, with bit-dropping on the reinforcing public key and a generic FO-transform construction in QROM.

The result: long-term server PK shrinks from Classic McEliece's ~261 kB to roughly 1.4 kB, a 190–390× reduction. Handshake messages still fit in one UDP packet. The kernel-deployment story becomes plausible.

Concurrent work

The paper acknowledges Lafourcade et al. (USENIX 2025) as concurrent independent work. Both groups found the UKS attack and the KEM-binding issue. Their fixes diverge:

• Hashimoto et al. redesign the protocol around RKEM, eliminate the duplicated PSK absorption, and prove identity hiding under WireGuard's original assumption (peer public keys hidden from adversary)
• Lafourcade et al. (hybrid-wireguard) keep the symmetric two-KEM structure, hybridize WireGuard with PQ-WireGuard⋆ for transitional security, fix UKS by concatenating static public keys to PSK in H4, and prove identity hiding without the public-keys-hidden assumption (at the cost of public-key MAC operations during DoS-protection lookup)

Beguinet et al. independently constructed Maul, a similar 2KEM primitive with comparable ciphertext savings to Rebar, derived via a tailored FO transform.

Why this matters

crqc-timeline's April 2026 reassessment moved PQ migration from "soon" to "now." VPN protocols are early targets because long-lived sessions and store-now-decrypt-later attacks are real, and because WireGuard sits in the kernel of every modern Linux box. A PQ-WireGuard variant that doesn't blow up server memory is the difference between "research paper" and "deployable next year."

Cross-references: pq-wireguard, reinforcing-kem, hybrid-wireguard, ml-kem, post-quantum-cryptography, crqc-timeline, store-now-decrypt-later.