Post-quantum signatures, priced

Why the hash-based options lost

I wanted SLH-DSA to work. It rests on hash functions alone, so it survives even if lattices turn out to be broken, and its 32-byte public key is charming. It fails here twice over.

The header is the harder failure. A 128f signature is 22,784 bytes once base64'd into a structured-fields value, and most servers cap total request headers around 8KB, so the crawl would start collecting 431s instead of pages. The latency is the other one: 2.65 seconds of single-threaded work per signature is not something to put in front of an HTTP request, and a Worker bills CPU time.

Stateful hash-based signatures (LMS, XMSS) fix the size problem and introduce a worse one. Reusing a one-time index is total key compromise, and a Worker isolate is close to the worst place to keep a monotonic counter. I would need a Durable Object doing nothing but handing out indices, and a single replay would end the key. ML-DSA-44 is the only candidate that survives contact with the constraints.

Shipping it without a codepoint

Here is the part that made this cheap. The IANA HTTP Signature Algorithms registry has exactly six entries, and every one of them is classical. Cloudflare's Web Bot Auth verifier accepts Ed25519 only and ignores other key types in your directory. An ML-DSA-only signature would be a header nobody on the internet checks.

But Signature-Input and Signature are structured-fields Dictionaries. A second label appends rather than replaces, so both signatures ride the same request over the same covered components:

Signature-Input: sig1=("@authority" "signature-agent");created=1785186311;
                   keyid="091z_BcIsuIgfzzKCKOie6JcSkz7UhVlbiakxjV5E8o";alg="ed25519";tag="web-bot-auth",
                 sig2=("@authority" "signature-agent");created=1785186311;
                   keyid="rn-mldsa-2026-07-27";alg="ml-dsa-44";tag="web-bot-auth"

A verifier that only knows Ed25519 reads sig1 and skips the label it does not recognise. Nothing breaks, and the cost of ignoring sig2 is zero. That property is what makes it defensible to ship an algorithm the registry has not blessed. The token ml-dsa-44 is this site's spelling, chosen to match the registry's existing convention so it slots in if a real registration lands, and /bot says plainly that you should verify sig1 and ignore sig2.

The public key is published under the same JWKS as an AKP key per RFC 9964, which standardised ML-DSA for JOSE and COSE in May 2026. So the key format is a real standard even though the wire token is not:

What it costs in production

About 8.6ms of CPU and 3,228 bytes of request header per signed fetch, plus 11.96KB gzip of lattice code in the Worker bundle, which is the price of carrying an implementation the runtime should be providing. Zero bytes reach a browser, because this is a server-to-server signature and no page loads it. The /around crawl signs roughly 21 origins per refresh, so a full cycle gains around 180ms of CPU on a cached background path.

Two of those three costs are temporary. When workerd gains native ML-DSA, the bundle cost goes to zero and the signing cost drops to whatever the native bar in the panel above showed you. The 3,228 bytes of header stay forever. That asymmetry is the argument for migrating on the size budget now and letting the speed sort itself out.

One implementation detail worth stealing: ML-DSA-44 keygen expands a 32-byte seed into a 2,560-byte secret key and costs about 1.4ms. Worker isolates outlive a request, so the expanded key is derived once and cached in module scope, keyed by the raw secret so a rotation inside a live isolate re-derives instead of signing with a retired key.

The objection I think is right

The strongest reading of this page is that it is theatre. Nothing verifies sig2. Signatures have no harvest-now-decrypt-later exposure, so there is no clock forcing the migration. By that argument the honest move was to write the analysis and ship nothing.

I mostly agree, and it is why sig2 is second rather than first, why a missing key degrades to Ed25519 alone instead of failing the request, and why /bot tells verifiers to ignore it. What I get in exchange is a migration already paid for and measured, on a surface where being wrong costs a crawl rather than a login. When the registry does land a codepoint, the remaining work is renaming a string.

What would change my mind: a receiving server rejecting requests because the extra 3.2KB pushes headers past its limit, or a verifier that chokes on a dictionary label it does not know. Either result would mean a second label is not free after all, and sig2 would come straight back out. The crawl logs are where that would show up first.

What actually happened: retired after 19 days

Neither of those things went wrong. No server rejected the headers, and no verifier choked on the extra label. The prediction above was accurate, but it was aimed in the wrong direction, because it priced the cost to other people and treated the cost to this site as a settled line item: 8.58ms, listed once, in a table.

The number that mattered was 8.58ms multiplied by fan-out, against a per-invocation budget. This site runs on the Workers free plan, which allows 10ms of CPU per request. So one signature spent most of a request's entire budget, and every surface that signs more than once had already blown it:

Both of those were dark and neither said so. The playlist scrape catches a failed track embed per track and degrades that one track to no cover, so 21 signatures timing out rendered as a tracklist that had quietly stopped showing album art. On /lens it was louder but no better attributed: sampling production logs on 2026-08-15, 31 of 51 requests died exceededCpu, nearly all of them /lens/fetch and /lens/tools.

Removing sig2 took the scrape from 379ms of CPU to 95ms, measured on the same 21-track playlist. The key is out of the JWKS too, because publishing a key nothing signs with is the dangling-pointer problem this site refuses elsewhere.

The honest reading is that the objection above was right for a reason it did not name. Shipping the migration early was cheap to build and the build was never the risk. What it cost was a recurring tax on every outbound request, on the one axis a free-tier Worker has least of, and the page that measured the tax in isolation is the same page that missed it in aggregate. A per-request cost is only a number once you know how many requests, and how much budget.

None of this changes the sizing argument, which is the part worth keeping. The 3,228 bytes are still permanent, the speed is still temporary, and when workerd ships native ML-DSA the CPU objection evaporates and sig2 can come back with no code to write beyond deleting this section. Until then the migration is measured, documented, and turned off.

Then the runtime caught up

That last paragraph made a prediction, and on 2026-10-01 I got to check it. Cloudflare has put ML-KEM and ML-DSA into WebCrypto on Workers. They run on BoringSSL, and each Worker opts in with the webcrypto_modern_algorithms compatibility flag (the announcement). This site already pins a workerd build from 2026-09-26 that carries both, so I measured it on the same M3 Max that drew the JavaScript bars.

Signing got 72 times faster, and the header didn't lose a single byte. That's the asymmetry this page bet on in July. Natively, one ML-DSA-44 signature costs about as much as 10 Ed25519 signatures (11.3µs each on the same rig), where the JavaScript version cost as much as 170.

Here is the table that retired sig2, repriced:

On the laptop, one signature takes about 1% of a 10ms request budget, and the worst fan-out on the site would sign everything it needs in about a third of a single budget. Hold that projection loosely; production priced it at 3 times that.

How I checked it

A 72x speedup deserves a control, so I ran three.

Without the flag, the same runtime refuses outright: Unrecognized key generation algorithm "ML-DSA-44" requested. With it, a key shaped like the one still sitting in this site's secrets (a bare 32-byte seed in an AKP JWK, with no public half) imports and signs. And Node 26's WebCrypto, which runs on OpenSSL instead of BoringSSL, verifies workerd's signature and rejects it the moment one byte of the signed base changes.

A Worker's clock only advances across I/O, so a Worker can't time its own crypto. The timings are wall-clock from outside instead: 2,000 signatures inside one request, minus an empty request so the dispatch cost cancels, median of 9 runs. The browser button above times yours the same way.

What it leaves open

The objection I think is right survives intact. Nothing on the internet verifies sig2, the IANA registry still lists six classical algorithms, and every signed request would still carry 3.2KB more header for a signature with no harvest-now clock behind it.

The retirement section also promised sig2 could return "with no code to write." That was wrong. The library left with the label, so bringing it back means a compatibility flag on the whole Worker plus a signing path through crypto.subtle. It's a small change, and a real one.

What production said

Those were laptop numbers, and production bills CPU on different hardware, under a clamp that tightens with load. That is exactly where this page went wrong the first time. So before sig2 came back, I deployed it at 0% beside the live version and pinned six /lens scans to it, each against a fresh origin so no cache could skip the signing.

Signing everything cost 10ms a scan, about 0.33ms a signature, which is 3 times the laptop figure. August's lesson applied a second time: the per-signature price was right, but the price that mattered was that number on production's CPU, multiplied by fan-out.

So sig2 now rides on the requests that are this crawler's identity (the page being scanned, /around, the playlist) and skips the 28 discovery probes and the robots.txt reads that only look around. That costs about 2ms a scan, inside the noise between two runs of the live version.

The flag carries its own risk, since Cloudflare gates it "while the specification is still moving." If the API breaks, this site loses the second label and nothing else: any ML-DSA failure drops sig2, logs once, and sig1 ships alone.

In July this page priced three costs: CPU, bundle size, and header bytes. Two belonged to the runtime, and the runtime has now paid them. The 3,228 bytes belong to FIPS 204, so they're the only number left to decide on. That's the rule I'd hand anyone timing a post-quantum migration: decide on the sizes, because the speeds come down on someone else's schedule.

shipped · the understanding check is part of the page, not a gate