Post-quantum VPN fragmentation MTU: why tunnels fail

Post-quantum VPN fragmentation is the MTU problem you get when a quantum-resistant key exchange such as ML-KEM makes handshake messages bigger than the largest packet a network path can carry. IP then splits those messages into fragments, and firewalls, NAT devices or carrier equipment that drop fragments can stop the tunnel from ever being established.

This matters most for operators of OT and critical infrastructure. Their site-to-site and remote-access links often cross carrier networks, cellular backhaul and older middleboxes that nobody has reconfigured in years. The cryptography may be fine and the tunnel can still fail, purely because of packet size. This article explains where the extra bytes come from, how the IKEv2 standards deal with them, and how to diagnose a tunnel that won’t come up.

Why do post-quantum public keys and ciphertexts cause packet fragmentation?

Post-quantum key encapsulation sends public keys and ciphertexts that run to more than a kilobyte, and a single handshake message carrying one of them, plus protocol headers, can easily go over a 1,500-byte Ethernet MTU. Anything above the path MTU gets fragmented at the IP layer.

Classical Diffie-Hellman over elliptic curves made this easy to ignore. In IKEv2, defined in RFC 7296, the first exchange (IKE_SA_INIT) carries security association proposals, a nonce, NAT detection notifications and a key exchange payload. With an elliptic curve key share, that whole message usually fits in a few hundred bytes. RFC 7383 notes that most IKEv2 messages stay below several hundred bytes. The exception was IKE_AUTH, which can reach several kilobytes when certificate chains are sent.

A KEM such as ML-KEM, standardised by NIST in FIPS 203, works differently from Diffie-Hellman. The initiator sends an encapsulation key and the responder sends back a ciphertext. Both are large, and both have to go out in the opening exchanges, before any encrypted channel exists. As a result, the unprotected first message now carries most of the size problem, where in the past only the later certificate exchange did.

IKEv2 runs over UDP, which has no segmentation of its own. When a UDP datagram is bigger than the path MTU, IP splits it. Only the first fragment carries the UDP header. Every fragment has to arrive, and the receiving host must reassemble them, before IKE ever sees the message.

How large are ML-KEM-768 and ML-KEM-1024 keys compared with ECDH keys?

An ML-KEM-768 public key is 1,184 bytes and its ciphertext is 1,088 bytes. ML-KEM-1024 uses 1,568 bytes for both. Elliptic curve public keys are 32 to 56 bytes, so the post-quantum values are more than twenty times larger.

A few practical conclusions follow from these numbers. An ML-KEM-768 key share by itself takes up most of a standard 1,500-byte frame. Add the IPv4 and UDP headers, the IKE header, proposals for several transforms, a nonce and the NAT detection payloads, and an IKE_SA_INIT request carrying ML-KEM-768 sits right at the edge. It is likely to go over on any path with a reduced MTU, such as PPPoE, cellular, GRE or MPLS overlays, or a link already inside another tunnel. An ML-KEM-1024 public key is bigger than the payload space of a 1,500-byte frame, so a single message carrying it is always fragmented at the IP layer.

In a hybrid design, which the IETF and most national guidance favour during the transition, the classical exchange still happens as well. It adds only a few dozen bytes, but it doesn’t take anything away.

How does IKEv2 fragmentation handle large post-quantum key exchange messages?

IKEv2 splits large messages itself under RFC 7383, so every piece fits inside the path MTU. That only works for encrypted messages, though, which is why RFC 9242 adds an intermediate exchange to carry the post-quantum key share after IKE_SA_INIT.

RFC 7383: fragmentation at the IKE layer

RFC 7383, published in November 2014, lets IKE peers advertise support with an IKE_FRAGMENTATION_SUPPORTED notification in IKE_SA_INIT. Once both sides support it, a large message is split into chunks. Each chunk is encrypted and authenticated separately and sent as its own UDP datagram, so no IP fragmentation happens. Because the receiver checks the integrity of each fragment, forged fragments can’t fill up its reassembly buffer.

The limitation that matters for post-quantum deployments is that only messages containing an Encrypted payload can be fragmented this way. IKE_SA_INIT is sent before any keys exist, so it can’t use this mechanism.

RFC 9242 and RFC 9370: moving ML-KEM out of IKE_SA_INIT

RFC 9242 defines the IKE_INTERMEDIATE exchange, which runs after IKE_SA_INIT and before IKE_AUTH. Its messages are already protected by keys from the classical exchange, so RFC 7383 fragmentation applies to them. RFC 9370 (Multiple Key Exchanges in IKEv2) uses that exchange to carry extra key exchanges. The ML-KEM specification from the IETF IPSECME Working Group (draft-ietf-ipsecme-ikev2-mlkem) is a profile of RFC 9370. Its guidance is direct: if a post-quantum KEM does not fit inside IKE_SA_INIT without causing IP fragmentation, run it afterwards as an additional key exchange.

In practice the flow looks like this. IKE_SA_INIT carries a small elliptic curve key share. ML-KEM then runs in an IKE_INTERMEDIATE exchange, fragmented by IKE if needed. IKE_AUTH follows as normal. Child SA rekeys can carry ML-KEM in CREATE_CHILD_SA or IKE_FOLLOWUP_KE exchanges, which are also encrypted and can be fragmented.

Where ML-KEM-1024 fits

Writing about the ML-KEM-1024 identifier in the first working group version of the draft, author Panos Kampanakis says it “SHOULD NOT be used in IKE_SA_INIT messages which could exceed typical network MTUs and cannot be IKEv2 fragmented.” Later revisions allow any ML-KEM parameter set in IKE_SA_INIT, but only when reliable transport (TCP encapsulation under RFC 9329) is used or a sufficient path MTU is guaranteed.

Why do firewalls drop fragmented UDP 500 and 4500 packets during tunnel setup?

Firewalls and NAT devices drop fragments because only the first fragment carries the UDP port numbers that their rules match on, and because holding partial datagrams for reassembly costs memory and has been used in attacks. Many devices simply discard fragments, either by default or through an operator’s choice.

RFC 7383 itself sets out the problem. Its author, Valery Smyslov, writes: “The problem is that some network devices, specifically some NAT boxes, do not allow IP fragments to pass through.” The RFC adds that people deploying IKE found more and more ISPs using equipment that drops IP fragments, in breach of the NAT requirement in RFC 4787. It also notes that many operators filter all IPv6 fragments, and that discarding them is the default on many firewalls.

The evidence it cites is concrete:

• 10% of 502 IPv6-enabled probes did not receive packets fragmented to the 1,280-byte minimum MTU during any given trial period (RFC 7383, November 2014, citing the BLACKHOLES study).

RFC 8900 (BCP 230, September 2020) explains why operators choose stateless middleboxes for price and performance reasons, and why those boxes may discard fragments entirely. Its authors warn that “the designer should be aware that fragmented packets may result in black holes.”

Three things specific to IKE make this worse:

• Port-based rules miss non-first fragments. A rule that allows UDP 500 and UDP 4500 between two peer addresses can’t identify a trailing fragment, because that fragment has no UDP header. Unless the device reassembles traffic or explicitly allows fragments from the peer, the trailing pieces get dropped.
• The port changes partway through setup. When NAT is detected, IKEv2 switches from UDP 500 to UDP 4500 after IKE_SA_INIT. An IKE_INTERMEDIATE exchange carrying ML-KEM therefore travels on a different port, and can take a different policy path, from the small first exchange that succeeded.
• The failure is silent. A dropped fragment generates no ICMP error. The initiator only sees retransmissions with no reply.

How do you troubleshoot a post-quantum tunnel that will not come up?

Work out where the exchange stops and how big the messages were at that point. Then confirm fragmentation support, check where ML-KEM is negotiated, and test the path directly. Most failures turn out to be a size problem that has nothing to do with the cryptography.

A diagnostic sequence that isolates the cause

1. Find the last exchange that completed. In the IKE logs, see whether the initiator is retransmitting IKE_SA_INIT, IKE_INTERMEDIATE or IKE_AUTH. RFC 7383 itself treats “no complete response after several retransmissions” as a sign of IP fragmentation trouble.
2. Run a classical-only control test. Bring the tunnel up with the same peers and policy but without the post-quantum transform. If that works, routing, authentication and port policy are fine, and message size is the main suspect.
3. Capture on both sides at the same time. Fragments that leave the initiator but never reach the responder point to the path. Fragments that arrive but get no answer point to the responder’s host firewall or its reassembly limits. RFC 7383 recommends that a receiver’s reassembly buffer per message not exceed 64 KB, and a limit set too low will also reject legitimate peers.
4. Check where ML-KEM sits. If the ML-KEM key share is in IKE_SA_INIT, move it to an additional key exchange in IKE_INTERMEDIATE as RFC 9242 and RFC 9370 describe. Confirm that both peers send IKE_FRAGMENTATION_SUPPORTED and the intermediate exchange notification.
5. Measure the path MTU. Send probes with the Don’t Fragment bit set and increasing sizes between the two public addresses, over the same transport the tunnel uses. Then lower the IKE fragment size below the measured value, leaving room for any outer encapsulation.
6. Fix policy, not just packets. Where you control the firewalls, allow fragments from the specific peer addresses, or enable reassembly on UDP 500 and 4500. Where a carrier sits in between, IKE-level fragmentation or TCP encapsulation (RFC 9329) is the dependable route.
7. Watch the rekeys, not just the first setup. A tunnel that comes up and then drops at the first Child SA rekey often has a CREATE_CHILD_SA or IKE_FOLLOWUP_KE message that wasn’t fragmented.

Does a post-quantum handshake change the MTU for tunnel traffic?

No. The larger keys only affect the handshake. Once the session keys exist, the per-packet overhead of encrypted traffic depends on the encapsulation and the symmetric cipher, not on the KEM.

That means a tunnel that came up cleanly won’t suddenly start black-holing large application packets because ML-KEM was added. Ordinary encapsulation overhead and TCP MSS clamping still need the same attention as before. What does change is how often the larger handshake runs. A design that renews keys frequently makes the reliability of the handshake path a constant requirement. For example, Quantum Network’s QPN gateway combines a classical and an ML-KEM part into one session key and renews both handshakes every two minutes. On any design like that, make sure the path between gateways passes handshake-sized packets reliably before you depend on it for OT traffic.