Please stop hashing the public key first (or: ML-DSA's µ annoys me)

Erincandescent explains why signature schemes such as Ed25519 and ML-DSA hash the public key before the message, why that ordering blocks a useful optimisation for verifying one message against many candidate keys, and how the constructions could have been arranged differently.

A goal one might have when designing a signing algorithm is to prevent signing a message one has not seen.

Signing a message one hasn't seen might sound difficult at first, but most classical signature algorithms, as commonly used, sign a hash of the message, rather than the message itself. This kind of arrangement is necessitated by the fact that the underlying algorithms are only capable of signing messages of a limited size. You might not have seen the message, but you might have seen the hash of it, or another signature which encodes said hash. In many protocols, this lets you produce a valid signature on a message you've never seen. That's rarely a problem in practice, but it can be surprising, and it's a pitfall for the unsuspecting protocol designer.

More recent algorithms take steps to prevent this:

Ed25519 signs SHA-512(R || PubK || M) where R is functionally a random curve point, PubK is the public key, M is the message, and|| is the concatenation operator
ML-DSA signs SHAKE-256(SHAKE-256(PubK, 64) || 0x00 || len(ctx) || ctx || m, 64) (where ctx is a 0 to 255 byte context string)

This can complicate your signing code, particularly when dealing with HSMs or smart cards, but it doesn't require majorly reworking your signing process. Unfortunately, on the verification side things are less rosy.

The challenge

As a general rule of thumb, we should avoid touching the body of a signed message until we've verified the signature. Also as a general rule of thumb, cryptographic protocols where there are multiple signers put the signer's identity within said body (X.509, most JWT and CWT usages, SAML, I'm looking at all of you, but you're not the only ones).

This means the verification process ends up being

Gingerly parse the message
Dig through as much message as necessary to identify the signing key
Actually verify the message
Actually consume the message

Often (JWT, CWT and SAML again), there's either no key identifier present in the signed message, or it's permitted for multiple signing keys to share a key identifier<sup>†</sup>. This means that, if the issuer has multiple keys, you may have to do multiple trial-verifications to work out if the message is actually valid.

One nice property that all of these protocols have (except XML Digital Signatures, but nobody thinks XML Digital Signatures were a good idea) is that they carry the signing method in a header. So, with a traditional signing algorithm, you have the option of

Parsing the header
Identify algorithm and hence the hash algorithm
Hash the message
Gingerly parse the message
Dig through as much message as necessary to identify the signing key
Actually verify the message
Actually consume the message

This comes with two advantages:

After step 3, you can throw away the raw message, reducing memory usage
In step 6, you pay for the cost of verifying a signature for every attempted key rather than also the cost of re-hashing the message. In most cases messages are small and this cost is also small, but every little helps.

Unfortunately, it has the slight flaw that it doesn't work with either Ed25519 or ML-DSA as defined.

For ML-DSA, it would have been quite easy to re-arrange matters. If we instead computed SHAKE-256(0x00 || len(ctx) || ctx || m || SHAKE-256(PubK, 64), 64) (i.e. we put the public key hash in at the end), then we can hold our SHAKE-256 context around and copy it for each trial verification. We'd end up keeping just over 200 bytes of SHAKE-256 context around (instead of 64 bytes of output), but that's not too bad. Unfortunately, that's not the choice that was made and we'll just have to deal with it.

Ed25519 is slightly more challenging. If we reversed the hash computation to be SHA-512(M || R || PubK) instead, it would be vulnerable to length extension attacks (for any SHA-512(X) you can extend it into SHA-512(X || some predictable garbage || Y) for any arbitrary Y).

Fixing that when Ed25519 was published in 2011 would be somewhat tricky, though the easiest option without truncating the hash is just to sign SHA-512(SHA-512("ed25519 domain separation" || M || R || PubK)).

Since we don't have a time machine, it's all a bit academic. In 2026 you can just avoid the problem by using SHA-3, BLAKE2, a truncated SHA-2 variant, or any other modern hash function which isn't vulnerable to length extension attacks.

In the meantime I'll just sigh and hope we can reduce the number of signatures we pass around, given they're really becoming rather large and expensive.

† You may be thinking it somewhat defeats the purpose of having a key identifier if they aren't unique. I don't disagree!