Marin Ivezic
A classical TLS 1.3 client sends a 32-byte X25519 public key in its key share. Under X25519MLKEM768, the hybrid group that Chrome and Cloudflare negotiate by default, that same field carries 1,216 bytes. Nothing about the protocol breaks. What changes is every number downstream of that field: how many packets the opening exchange occupies, whether the server’s reply fits in the initial congestion window, whether a firewall that quietly assumed a single-packet ClientHello still forwards it.
Post-quantum cryptography (PQC) is usually presented to network teams as an algorithm swap. On the wire it is a sizing change, and sizing changes are the kind of thing network engineers are already equipped to reason about. This article works one handshake budget end to end, then follows the same budget across four link types to show where it is absorbed and where it stops being viable.
The two byte budgets
A handshake spends bytes on two separate jobs, and they behave differently.
Key agreement. Both sides need a shared secret. ML-KEM, standardized as FIPS 203 and formerly named CRYSTALS-Kyber, is a key encapsulation mechanism: the client publishes an encapsulation key, the server uses it to produce a ciphertext plus a shared secret, and the client recovers the same secret from the ciphertext. One exchange, one key share each direction.
| Object | Size |
|---|---|
| X25519 public key | 32 B |
| ML-KEM-768 encapsulation key | 1,184 B |
| ML-KEM-768 ciphertext | 1,088 B |
| X25519MLKEM768 client share | 1,216 B |
| X25519MLKEM768 server share | 1,120 B |
The hybrid group concatenates both, so a break in either the classical or the post-quantum half still leaves the secret protected. That safety costs 32 bytes on top of the ML-KEM figures, which is a rounding error against the rest.
Authentication. This is where the budget actually goes. ML-DSA, standardized as FIPS 204 and formerly CRYSTALS-Dilithium, is the general-purpose signature scheme. SLH-DSA, FIPS 205 and formerly SPHINCS+, is the hash-based alternative. FN-DSA, formerly FALCON, is drafted as FIPS 206 and not yet final.
| Scheme | Signature | Public key |
|---|---|---|
| ECDSA P-256 | ~72 B | 64 B |
| RSA-2048 | 256 B | 270 B |
| ML-DSA-44 | 2,420 B | 1,312 B |
| ML-DSA-65 | 3,309 B | 1,952 B |
| ML-DSA-87 | 4,627 B | 2,592 B |
| SLH-DSA-128s | 7,856 B | 32 B |
| SLH-DSA-128f | 17,088 B | 32 B |
| FN-DSA-512 (draft) | ~666 B | 897 B |
Key agreement grows by roughly 1 KB each way and then stops. Authentication grows by a factor of thirty, and it multiplies, because a chain contains several signatures and several public keys. That asymmetry drives almost every decision later in this article.
Counting one handshake
The first flight is everything one side puts on the wire before it hears back. Its size decides how many packets you need, and the packet count decides how many round trips you pay.
The client’s first flight
A classical ClientHello runs a few hundred bytes and fits comfortably inside a single 1500-byte Ethernet frame. Add a 1,216-byte hybrid key share and the message clears 1,500 bytes on most stacks. The ClientHello now spans two TCP segments.
That’s legal, and it’s the single most common source of post-quantum interoperability failures reported so far. Some servers and inline devices were written on the assumption that the first message arrives whole, and they fail in ways that look like a network problem rather than a crypto problem: a hang, a reset, a fallback with no log entry. The bytes are fine. The assumption was wrong.
The server’s first flight
Take a two-certificate chain, leaf plus intermediate, with the root already in the client’s trust store, and sign everything with ML-DSA-44.
- Leaf certificate: 1,312 B of public key, plus a 2,420 B signature from the intermediate
- Intermediate certificate: 1,312 B of public key, plus a 2,420 B signature from the root
- CertificateVerify: 2,420 B
- ServerHello key share: 1,120 B
That’s 11,004 bytes of cryptographic material, and roughly 700 bytes of names, extensions and DER framing on top. Call it 11.7 KB. The equivalent ECDSA P-256 chain, with the same names and extensions, runs about 2.5 KB.
Now compare that against the initial congestion window. RFC 6928 sets it at ten segments, about 14,600 bytes at a 1,460-byte MSS. An 11.7 KB flight fits. The server sends it all, and the handshake completes in the same number of round trips as it did before.
Raise the parameter set to ML-DSA-65 and the same chain arithmetic yields 14,951 bytes of cryptographic material, roughly 15.7 KB with framing. That exceeds the window. The server sends ten packets, waits for an acknowledgement, then sends the rest, and the client pays one extra round trip before it can send a single byte of application data. Sign the chain with SLH-DSA-128s and the three signatures alone come to 23,568 bytes, which is two extra round trips.
Nothing failed in either case. The parameter choice moved the handshake from one round trip to three, and it did so through a mechanism that has nothing to do with cryptography.
The same flight over QUIC
QUIC tightens both constraints. Under RFC 9000 a client Initial datagram is padded to at least 1,200 bytes, and a server must not send more than three times the number of bytes it has received from an address it hasn’t yet validated. The rule exists to stop QUIC being used as a reflection amplifier.
Do the arithmetic. A hybrid ClientHello no longer fits one Initial, so the client sends about 2,400 bytes across two datagrams. Three times that is roughly 7,200 bytes. The server’s 11.7 KB flight doesn’t fit inside the budget, so the server sends what it can and stops until the client’s acknowledgement raises the ceiling. The larger client message partly funds its own reply, and it doesn’t fund all of it.
This is a good illustration of why “the algorithm is supported” isn’t a useful vendor answer. Support was never the question. The question is how many round trips the first exchange now costs on your paths, and that number is derivable from bytes.
The same handshake on four networks
Ethernet and Wi-Fi
On wired and modern wireless links, 11.7 KB is nothing. The extra milliseconds are below the noise floor of anything a user perceives, and the additional CPU cost is modest, because lattice arithmetic is fast on general-purpose hardware.
The residual risk here is compatibility rather than capacity. Deep packet inspection appliances, TLS-terminating load balancers, older VPN concentrators and intrusion detection systems all parse handshakes, and some of them have fixed buffers or size heuristics from an era when a ClientHello was 300 bytes. A device that drops or resets on a larger handshake produces exactly the same symptom as a routing fault, which is why these failures are expensive to diagnose and cheap to find in advance.
Cellular and VPN over cellular
The radio side is fine. Modern 4G and 5G bearers carry a 12 KB handshake without difficulty, and the added latency at good signal strength is small against the existing round-trip time.
The failure mode is fragmentation, and it’s specific to UDP-based protocols. An IKEv2 key exchange carrying an ML-KEM public key won’t fit in a single IKE_SA_INIT message, so the payload fragments at the IP layer. Plenty of carrier NATs and firewalls discard fragmented UDP as a matter of policy, and the tunnel then never establishes. The client retries, fragments again, and fails again.
The fix is protocol-level rather than transport-level. Three specifications matter: RFC 7383 defines IKEv2 fragmentation so the protocol splits its own messages rather than relying on IP; RFC 9242 adds the IKE_INTERMEDIATE exchange, which creates somewhere to put a large key that doesn’t fit in the initial exchange; RFC 9370 defines multiple key exchanges so a classical and a post-quantum method can be negotiated together. A VPN endpoint that implements all three works over cellular. One that implements none of them will fail, and the failure will look like a carrier problem.
Under packet loss the arithmetic gets worse in a way that’s easy to overlook. A larger flight is more packets, more packets means a higher probability that at least one is lost, and a lost handshake packet costs a full retransmission timeout on a link where the timeout is already long. Loss doesn’t degrade post-quantum handshakes and classical ones equally.
Satellite and other long links
A geostationary round trip runs roughly 550 ms. Nothing about a larger handshake breaks on such a link, and the extra round trip caused by an oversized first flight costs more than half a second before any application data moves. On a link where a session is established once and used for hours, that’s acceptable. On one where short sessions are set up repeatedly, it isn’t, and session resumption stops being an optimisation and becomes a requirement.
One operational detail deserves attention. Application and library handshake timeouts were often tuned against classical handshake durations, sometimes years ago. On a high-latency path with an extra round trip and one retransmission, a post-quantum handshake can exceed a timeout that has never fired before. Check those values before enabling anything.
LoRaWAN, and the limit case
LoRaWAN is where the arithmetic stops being an optimisation problem.
At the slowest EU868 data rate, the maximum application payload is 51 bytes. Devices in those sub-bands operate under a 1% duty cycle, meaning the radio may transmit for no more than 36 seconds in any rolling hour. A 51-byte frame at SF12 occupies roughly 2.5 seconds of airtime, so a device gets about 14 frames per hour.
Now push our 11.7 KB server flight through that channel. Ignore the client side, ignore all protocol framing, ignore retransmissions, and assume every frame arrives first time. That’s 230 frames, at 14 frames per hour, or roughly 17 hours to complete one handshake. The device would spend most of a day transmitting, drain a meaningful share of a battery designed to last a decade, and deliver a 20-byte sensor reading at the end of it.
Sigfox is worse, and in a direction that’s easy to miss. The uplink carries 12 bytes at up to 140 messages a day, so 11.7 KB would be about 975 messages, or a week. But the server’s flight travels downlink, and Sigfox downlink is 8 bytes and four messages a day, so the same flight becomes roughly 1,500 messages, or about a year. NB-IoT has real bandwidth and no hard frame ceiling, so the handshake completes, but the radio stays awake far longer than the power budget assumed.
We state this plainly to participants in our architecture sessions, because it’s the point at which planning has to change rather than tighten. Current post-quantum parameter sets cannot complete an interactive handshake over these radio technologies within their power and duty-cycle budgets. Anyone writing a policy that says “enable PQC everywhere by a fixed date” is writing a policy that will take a sensor fleet offline.
Design responses
Pay for authentication less often
Key agreement runs once per connection and costs about 1 KB. Authentication runs once per connection and costs ten. Reduce how often you pay the second one.
Session resumption is the largest single win, because a resumed TLS 1.3 session carries no certificate chain at all. Connection reuse and long-lived tunnels have the same effect. Client-side caching on its own does nothing, because a server sends the full chain on every new connection unless both ends negotiate the TLS Cached Information extension of RFC 7924, and few stacks implement it.
Certificate compression under RFC 8879 helps less than teams expect. Compression works on redundancy, and an ML-DSA signature is high-entropy output that compresses barely at all. The gains come from the repeated names and extensions in a chain, not from the bytes that grew.
Choose parameters by verification pattern
The right question isn’t which parameter set is strongest, it’s how often the signature is verified and under what constraints.
ML-DSA-44 is the sensible default for signatures verified inside an online handshake, because it’s the smallest standardized option and the size difference against ML-DSA-65 is worth two round trips on a constrained window. SLH-DSA is a poor fit inside a handshake and a good fit for long-lived roots and firmware images, where verification happens rarely, the signature travels with a large payload anyway, and the conservative hash-based security assumption is worth paying for. FN-DSA would relieve most of the pressure at 666 bytes per signature, and it isn’t standardized yet, so it can be planned for and not deployed.
Fix the transport before enabling the crypto
Most of what breaks is fixable in advance and cheaply. Raise internal MTUs where you control them. Enable IKEv2 fragmentation and the intermediate exchange on every VPN endpoint. Audit hardcoded buffer limits in applications that parse certificates. Review handshake timeouts and retransmission counts on high-latency paths. Confirm that inline inspection devices forward multi-packet ClientHellos and unfamiliar group identifiers.
Terminate constrained links at a gateway
Where a device can’t carry the handshake, move the handshake. A gateway holds the post-quantum session upstream and speaks a lightweight, existing scheme to the sensors below it. This concentrates trust in the gateway, which is a real cost and needs to be documented as a residual risk rather than glossed over. It also buys years, and the alternative on a 51-byte frame is nothing.
Keep a rollback path
Crypto-agility earns its keep the first week after a rollout, when one network segment starts failing and the cause isn’t clear yet. Being able to change the negotiated group by configuration, on a subset of endpoints, without a firmware cycle, is the difference between an afternoon and an outage.
Measure the right things
Median handshake latency on a healthy link hides everything discussed above. Instrument four numbers instead: bytes in each first flight, packets in each first flight, round trips to first application byte, and handshake completion rate under injected loss of one to five percent. Add power draw per handshake for anything battery-powered. Compare each figure against the classical baseline on the same path.
Where this fits in a migration plan
Most inventories are built by application. Migration sequencing needs a second axis, by link type, because the constraint that decides feasibility lives in the network rather than the application. Two services running identical code are a straightforward change on a data centre link and an open problem over a duty-cycled radio.
Practically, that means three passes over the estate. Group every connection by the path it traverses. For each path, calculate the first flight in bytes and compare it against the MTU, the congestion window and any fragmentation policy. Then sequence: high-bandwidth paths first because they’re low risk and build operational experience, UDP-based tunnels next because they need protocol work before they’ll function, constrained radio last, with an explicit decision recorded about what protects those devices in the interim.
Vendor readiness statements are worth reading with this in mind. Almost all of them state that an algorithm is supported. Very few state a first-flight byte count, a fragmentation behaviour, or a tested loss profile, which are the three things that determine whether the connection completes.
For migration methodology and the governance side of sequencing, pqcframework.org covers the programme structure this arithmetic feeds into, and PostQuantum.com carries deeper technical treatment of the algorithms themselves.
Engineers and architects who want to work through these budgets against their own topology, with the protocol specifications and the transport constraints handled together, will find that Quantum Academy’s Post-Quantum Cryptography Architect certification is built around exactly this kind of arithmetic. Programme details and the current cohort schedule are at quantumacademy.com/.