Counting Signatures: What One Agent Request Carries When Signatures Grow

Everyone who has looked at post-quantum signatures has seen the headline comparison: today's elliptic-curve signatures weigh in at roughly 64 bytes, and ML-DSA signatures, the new standard from Federal Information Processing Standard (FIPS) 204, range from roughly 2,400 to 4,600 bytes. The comparison is true and almost useless on its own, because nobody sends one signature. A single request from an AI agent to a tool can carry a handful of signatures and public keys, some made months ago and some made a millisecond ago, some sent once per connection and some sent with every call, each squeezing through a different limit on the way. This guide teaches a simple counting method, applies it to one realistic agent request, and shows which limit is likely to break first when the signatures grow.

One request, many signatures

Think of a parcel crossing a border. The parcel itself is small, but it travels with paperwork: a shipping label, a customs form, a proof of payment, maybe a certificate of origin. If every form suddenly had to be printed on a sheet fifty times larger, the parcel would not change, yet the envelope would stop fitting through the slot. Post-quantum signatures do the same thing to network requests. The data an agent wants to send barely changes; the paperwork around it grows.

Picture a concrete case. An AI agent, a program that uses a language model to decide what to do and then acts through tools, needs to look up a customer's open orders. It calls an order-lookup tool over the Model Context Protocol (MCP), the common standard for how agents discover and call tools, which runs over ordinary Hypertext Transfer Protocol Secure (HTTPS) web requests. That one call can involve several distinct pieces of signed paperwork: the certificates that prove the tool server's identity, a signature made during the connection's opening handshake, an access token that proves the agent is allowed to call the tool, and in some designs a fresh proof that the agent holds a particular key or a signature over the request itself.

A digital signature, for this purpose, is a short block of data that lets anyone holding the signer's public key check that a specific message came from the signer and was not altered. Each piece of paperwork above contains at least one. Today they are all small enough that nobody thinks about them. The question this guide asks is practical: if every one of them moved to ML-DSA, how many bytes would actually travel, how often, and where would they first hit a wall?

It is worth being clear about why this question can be answered calmly. Breaking a signature is only useful at the moment someone checks it: a forger has to fool a verifier in real time. Unlike recorded encrypted traffic, old signatures cannot be harvested today and abused later in the same way. That gives teams time to plan the signature move rather than rush it. The time is best spent on exactly this kind of counting, because the failures it prevents are mundane, not cryptographic: a request too large for a buffer, a token too large for a cookie, a handshake that suddenly needs an extra round trip.

The counting method

The method has five steps, and none of them needs any mathematics beyond multiplication. First, count: list every signature and every public key that travels with the request. Public keys matter because a verifier needs one to check a signature, and sometimes the key travels alongside it. Second, size: look up how many bytes each one becomes after the change. For ML-DSA the standard publishes exact figures: ML-DSA-44 has a 1,312-byte public key and a 2,420-byte signature, ML-DSA-65 has 1,952 and 3,309 bytes, and ML-DSA-87 has 2,592 and 4,627 bytes.

Third, encode: many signatures travel as text, not raw bytes. Web tokens and headers use an encoding called base64url, which turns every three bytes into four printable characters, so sizes grow by a third. So the 3,309 bytes of an ML-DSA-65 signature turn into 4,412 characters of text. Fourth, repeat: note how often each item travels. Some go once per connection, some go with every single request, and some are created fresh each time. Fifth, compare: find the smallest limit on the path that the item must squeeze through, such as a maximum header size in a web server or the amount of data a network connection sends before pausing for an acknowledgement.

The method sounds obvious, which is exactly why it is useful. Most surprises in signature migrations come from skipping one of the five steps: forgetting the public key that rides along, forgetting the one-third growth from encoding, or forgetting that something small once per connection is now large on every call.

Inside the handshake: five signatures and two keys

Start where every HTTPS call starts: the handshake, the opening exchange in which the client checks the server's identity and the two agree on encryption keys. Cloudflare, which operates one of the largest networks on the internet, has published a careful count. On a first visit to a typical website, the server sends five signatures and two public keys. The certificate authority, the trusted organisation that vouches for identities, signs an intermediate certificate; the intermediate signs the website's own leaf certificate; the leaf's key signs a summary of the handshake itself to prove the server really holds that key; and two more signatures are Signed Certificate Timestamps, receipts from public Certificate Transparency logs showing the certificate was publicly recorded.

Cloudflare calculated that moving all of those to ML-DSA-44, the smallest ML-DSA option, adds about 15 kilobytes to the handshake. That number matters because of a network rule called the initial congestion window. When a connection starts, the sender transmits only a limited amount of data, about ten full packets or roughly 14.6 kilobytes under the common standard, before waiting for the other side to acknowledge receipt. Cloudflare observed a steep drop in performance once the extra data passes about 10 kilobytes, because the handshake then needs an extra round trip, and estimated that adding 9 kilobytes would slow the handshake by about 15 percent.

Two details soften the picture. First, only one of the five signatures, the one over the handshake summary, is created live; the others are made ahead of time, when certificates are issued and logged. Slow signing would only hurt that one. Second, the handshake happens once per connection. A long-lived connection that carries hundreds of requests pays the cost once. That is why reusing connections is the single most effective habit when signatures grow, and why proposals such as Merkle Tree Certificates, which would replace all but the handshake signature with a proof under 800 bytes in the common case, are being actively explored.

Agents add one twist that ordinary browsing rarely has. Many agent platforms use mutual authentication, where the agent also proves its identity with a certificate of its own, so that the tool server can check who is calling before any token is read. In that design the agent sends its own chain and its own live signature as well, roughly doubling the handshake paperwork. The census has to include both directions, and the agent's side may run on a smaller, older runtime than the server's.

The token that rides along on every call

Now the part that is easy to miss. After the handshake, the agent has to prove it is allowed to use the tool. The MCP specification says the client must send its access token in the Authorization header of every HTTP request, even when the requests are part of the same session. An access token is a small signed document, very often a JSON Web Token (JWT), that says who it was issued to, what it permits and when it expires; the issuer signs it so that the tool can check it without phoning home. Since May 2026 there is a published standard, RFC 9964, for using ML-DSA signatures in exactly these JSON-based tokens.

Apply the counting method. A token is three pieces of base64url text joined by dots: a short header, the payload of claims, and the signature. With an elliptic-curve signature, the signature part is 86 characters. With ML-DSA-65 it becomes 4,412 characters; with ML-DSA-44, 3,227; with ML-DSA-87, 6,170. Add the header and claims, typically a few hundred characters, and an ML-DSA-65 token lands at roughly five thousand characters. And unlike the handshake, it does not travel once per connection. It travels on every call.

That is where the limits start to bite, because web software has long assumed headers are small. A cookie, the browser's little storage slot that is often used to carry session tokens, is only guaranteed 4,096 bytes by the standard that governs cookies, so an ML-DSA-65 token simply does not fit in one. Common web servers cap a single header line: Nginx by default refuses a header that does not fit in an 8-kilobyte buffer, and Apache's default limit is 8,190 bytes per header field. Node.js, the runtime behind a great deal of agent and tool code, by default caps all request headers together at 16 kilobytes.

There is one more quiet effect. Version 2 of HTTP compresses headers by remembering recently sent ones in a table, so a repeated header can be replaced by a short reference. That table starts at 4,096 bytes, and the compression standard says an entry larger than the table cannot be stored; trying to add one simply empties the table. A five-thousand-character token therefore cannot be remembered and is sent in full on every request. Some software already declines to remember authorization headers for security reasons, but either way the conclusion is the same: plan for the whole token on every call.

Tokens also travel to places that are not part of the request at all. Gateways copy them into logs, tracing systems record headers to help debug slow calls, and analytics pipelines store request metadata. Many of those systems truncate long fields or reject oversized records. A token that suddenly grows fivefold can break log parsing or, worse, be cut in half in a way that hides which credential was used. The census should therefore include every system that stores or inspects headers, not only the ones that verify them.

Signatures made live: proofs and request signatures

A plain access token is a bearer token: whoever holds it can use it, which is convenient and risky in equal measure, because a stolen token works for the thief too. Two increasingly popular designs fix that by adding a signature made fresh for each request, and each one changes the count.

The first is Demonstrating Proof of Possession, known as DPoP and defined in RFC 9449. With DPoP the client sends, alongside the token, a short proof: another signed token, created for this specific request, showing that the sender holds a particular private key. The proof's header includes the client's public key itself, so the receiver can check it. In the census, that is one live signature plus one public key per request. With ML-DSA-65, the key alone becomes about 2,600 characters of base64url and the signature another 4,412.

The second is HTTP Message Signatures, a standard way to sign the parts of a request so that the receiver knows exactly who sent it. Cloudflare's Web Bot Auth uses it so that automated agents and crawlers can identify themselves to websites: each request carries a Signature header made with an Ed25519 key, today about 88 characters. Moved to ML-DSA-44, that header would carry roughly 3,200 characters on every request.

This is where the difference between made-ahead and made-live signatures stops being academic. A made-ahead signature, such as a certificate or a token reused for an hour, costs bytes but almost no computing time per request. A made-live signature costs bytes and a signing operation every time. ML-DSA signing is fast, so for most systems the bytes are the larger concern, but the distinction decides where to look first: the items that are both live and repeated on every call are the ones that grow the fastest.

Live signatures also depend on where the signing key lives. A key stored in software can sign as quickly as the processor allows. A key held in dedicated hardware, such as a hardware security module, a smart card or a device's secure chip, signs only as fast as that hardware can, and only if the hardware supports the new algorithm at all. Before a design adds a live post-quantum signature to every request, it is worth checking the hardware vendor's published algorithm list rather than assuming support.

Adding it up for one agent call

Put the pieces together for a single tool call that uses an access token and a DPoP proof, and count only the two signed headers. The figures below are simple arithmetic from the published sizes, assuming a few hundred characters of ordinary claims in each token; real tokens vary.

With today's elliptic-curve signatures, the two headers together are typically around a kilobyte or two. With ML-DSA-44, the access token is about 3,700 characters and the proof about 5,300, roughly 9 kilobytes together. With ML-DSA-65, the token is about 5,000 characters and the proof about 7,300, roughly 12 kilobytes. With ML-DSA-87, the strongest option and the one required for United States national security systems under the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), the token is about 6,800 characters and the proof about 10,000, roughly 17 kilobytes, which is already above Node.js's default 16-kilobyte limit for all request headers before a single other header is counted.

None of those totals is enormous for a modern network, and that is the honest point. The risk is not that agents become slow; it is that requests start failing at boundaries nobody remembered existed, with error messages like 'header too large' or 'request header fields too large', on some paths and not others. A proxy with an old limit, a gateway that copies tokens into cookies, a logging pipeline that truncates long fields: each is a place where a working system can break the day a larger key is issued.

The failures are also uneven in time. Tokens are usually issued by an identity provider, a separate service that the agent's team may not control. The day that provider switches its signing key to ML-DSA, every token it issues grows at once, across every agent and tool that relies on it. Systems that were tested only with today's small tokens can go from healthy to failing in a single key rotation, which is exactly why the census belongs before that day rather than after it.

Notice, too, what the arithmetic leaves out. Real requests also carry cookies, tracing identifiers, content types and assorted custom headers, all sharing the same total limits. The two signed headers are the part that grows; everything else is already using some of the room.

What actually helps

The good news is that each step of the counting method suggests its own remedy. Count fewer: reuse connections so that the handshake's signatures are paid once per connection rather than once per call; prefer designs where a token is exchanged once for a short session; and watch proposals such as Merkle Tree Certificates that cut the number of signatures in a handshake. Size smaller: choose the smallest parameter set your policy allows. ML-DSA-44 sits in security category 2, a level defined by how hard it is to find a collision in the SHA-256 hash function, and is a reasonable default for many commercial uses, while ML-DSA-87 is for settings that require the top category.

Encode with care: do not stuff large tokens into cookies, where the guaranteed space is only 4,096 bytes; send them in a header or keep them on the server and give the browser a short reference. Repeat less: where the design allows, avoid signing every request when signing every session would do. Compare early: raise limits deliberately, in configuration, with a recorded reason, rather than waiting for errors in production. And test with realistically large tokens and keys now, in staging, before any issuer switches algorithms.

Be careful with doubling. During the transition some designs carry both a classical and a post-quantum signature, either as two separate signatures or as one composite signature that combines them. That is a sensible hedge for long-lived identities, but it adds the classical bytes on top of the post-quantum ones, so it belongs where the hedge is needed rather than on every request by default.

Finally, keep the comparison honest by measuring rather than estimating once the first real tokens exist. The arithmetic here assumes typical claim sizes; a token with many group memberships, long scopes or nested delegation details can be much larger before any signature is added. A simple test that sends the largest realistic token through every hop, and records which component rejects it, is worth more than any table, because it finds the limits nobody wrote down.

• Reuse connections so handshake signatures are paid once, not per call.
• Pick the smallest parameter set your policy accepts.
• Keep large tokens out of cookies.
• Raise header limits on purpose, and write down why.
• Test with full-size post-quantum tokens and keys before any issuer switches.

What this means for AI agents and the people who run them

Agents feel signature growth before most other software, for three reasons. They fan out: one user request can trigger many tool calls, and the MCP rule that every request carries its token turns a per-request cost into a per-task multiplier. They delegate: when an agent acts for a user, systems often exchange one token for another that records both the user and the acting agent, using a delegation field defined in the token-exchange standard, RFC 8693, and every exchange issues a newly signed token. And they increasingly identify themselves cryptographically, through request signatures such as Web Bot Auth, which adds a live signature to every request.

So the people who build and run agents should do the census before the issuers do the switch. List the signed headers each agent sends. Measure their sizes today. Multiply by the post-quantum sizes and compare with every limit between the agent and the tool: the agent's own HTTP client, the gateway, the proxy, the tool server, the logging system. Ask identity providers and model providers which signature algorithms they plan to issue, and when. Watch for AI coding assistants that copy old examples storing tokens in cookies or hard-coding small header limits.

It also helps to give each agent a simple header budget, the way teams give a web page a weight budget: a written maximum for the total size of signed headers per request, checked automatically in testing. When a new identity provider, a new delegation step or a new request-signing scheme is added, the budget forces the question of what it costs before it ships. Agents that call many tools through a shared gateway benefit most, because one budget at the gateway protects every tool behind it.

None of this argues against moving to ML-DSA. Forging today's signatures requires a quantum computer at the moment of the attack, so there is time to do this calmly. The argument is for counting first, so that the move is a configuration change instead of an outage.

Glossary

ML-DSA

Module-Lattice-Based Digital Signature Algorithm, the FIPS 204 post-quantum signature standard, in sizes 44, 65 and 87.

JSON Web Token (JWT)

A compact signed document, written as base64url text, that carries claims such as who a token was issued to and what it allows.

Base64url

A way of writing bytes as letters, digits and two symbols; every 3 bytes become 4 characters.

Bearer token

An access token that works for whoever presents it, like a ticket rather than an ID card.

DPoP

Demonstrating Proof of Possession, a design in which each request carries a fresh signed proof that the sender holds a specific key.

HTTP Message Signatures

A standard for signing parts of an HTTP request so the receiver can verify who sent it.

Initial congestion window

The amount of data a new connection sends before waiting for acknowledgement, about ten packets by default.

Signed Certificate Timestamp

A signed receipt from a public log showing that a certificate was recorded.

Security category

A strength level from 1 to 5 defined by comparison with breaking a well-known symmetric cipher or hash function.

Further reading

1. FIPS 204: Module-Lattice-Based Digital Signature Standard (NIST)
2. State of the post-quantum Internet in 2025 (Cloudflare)
3. Model Context Protocol: Authorization (2025-06-18)
4. RFC 9449: OAuth 2.0 Demonstrating Proof of Possession (DPoP)
5. RFC 7541: HPACK, Header Compression for HTTP/2
6. RFC 6265: HTTP State Management Mechanism (cookies)