DNSSEC and post-quantum signatures: the size problem

Short answer: DNSSEC signs DNS answers with digital signatures, and the post-quantum signature schemes standardized so far produce much larger signatures than the classical ones DNSSEC uses today. A Verisign presentation gives typical sizes of 64 to 256 bytes for classical signatures, against 2,420 to 4,627 bytes for ML-DSA and 7,856 to 49,856 bytes for SLH-DSA. Researchers say DNS messages over UDP that exceed about 1,232 bytes are usually fragmented, which is unreliable, so the size gap is a real engineering problem.

What DNSSEC needs

A 2021 SIGCOMM paper, "Retrofitting Post-Quantum Cryptography in Internet Protocols: A Case Study of DNSSEC", says DNSSEC guarantees message integrity and authenticity for the Domain Name System. It says new post-quantum algorithms can have larger signatures or keys and often require more computational power, so existing algorithms cannot simply be replaced. It calls DNSSEC particularly challenging to transition because DNSSEC and its underlying transport protocols require small signatures and keys and efficient validation. The paper evaluated candidate signature algorithms from the third round of NIST's competition and says three of them partially meet DNSSEC's requirements, with adaptations still needed.

The 1,232-byte ceiling

A 2024 paper on the IACR ePrint archive, on post-quantum DNSSEC over UDP, explains the DNS size constraints. A DNS message over UDP, as originally standardized, was restricted to 512 bytes, and the ceiling was later raised to a theoretical 64 KB with the EDNS0 extension. But it says a message over UDP exceeding 1,232 bytes usually triggers IP fragmentation on most network links. It gives the derivation: 1,280, the IPv6 minimum MTU, minus 40 for the IPv6 header, minus 8 for the UDP header.

The paper says DNSSEC messages carrying post-quantum data will easily exceed 1,232 bytes and so be fragmented by the network. It says IP fragmentation is considered unreliable, since fragments may never arrive, and insecure, since fragments can be spoofed, and cites work reporting that up to 10 percent of resolvers fail to handle fragments correctly.

Falling back to TCP

The alternative the paper describes is TCP. When a response exceeds the resolver's advertised buffer size, the server sends a truncated response with the TC bit set, the resolver discards it and retries over TCP. The paper cites surveys finding that up to 11 percent of nameservers lack TCP support, and a report that TCP port 53 connections can be blocked by middle boxes. The SIGCOMM paper says that in the worst case, fragments can never be transmitted and a TCP connection cannot be established, so end users may not be able to visit a requested website.

Sizes compared

The Verisign presentation, "A post-quantum cryptography strategy for DNSSEC", is from a company that operates DNS infrastructure, so treat its recommendations as one operator's view. It says DNSSEC currently uses signature algorithms at risk from quantum computers, and that the standardized post-quantum signatures, ML-DSA in FIPS 204 and SLH-DSA in FIPS 205, have large signature sizes relative to DNSSEC's constraints. Its table gives typical sizes of 128 to 256 bytes for RSASHA256, 64 bytes for ECDSAP256SHA256, 2,420 to 4,627 bytes for ML-DSA and 7,856 to 49,856 bytes for SLH-DSA.

It adds that comparing packet size to signature size understates the challenge: a response can in some cases include up to three signatures, for an NSEC3 non-existence answer, and during key rollovers a response may carry signatures under both an old and a new key.

What the operator recommends

The presentation says NIST's additional signature call intends to standardize algorithms with smaller signatures, likely based on newer cryptographic assumptions. It advises not waiting for that effort before preparing, finding a way to deploy the currently standardized algorithms, and adopting a diversity strategy using at least one conservatively designed algorithm and at least one low-impact drop-in algorithm. These are recommendations from one organization, not a standard.

What this does not tell you

This article summarises three documents and does not describe how any DNS operator is deploying post-quantum signatures. The size and loss figures come from the cited papers and a presentation, and network behaviour varies.

FAQ

Why are post-quantum signatures a problem for DNSSEC?

They are much larger than classical ones, and DNS over UDP messages above about 1,232 bytes usually get fragmented.

How large are they?

A Verisign presentation gives 2,420 to 4,627 bytes for ML-DSA and 7,856 to 49,856 bytes for SLH-DSA, against 64 to 256 bytes for classical signatures.

Can TCP solve it?

The 2024 paper cites surveys finding that up to 11 percent of nameservers lack TCP support and that TCP port 53 can be blocked by middle boxes.

Is fragmentation safe?

The paper calls it unreliable and insecure, and cites work saying up to 10 percent of resolvers fail to handle fragments correctly.

Is there a fix?

These documents discuss options and recommendations. They do not describe a finished deployment.