[CFRG] Prehashing in EdDSA vs ML-KEM

[Phillip Hallam-Baker <[e-mail]>]

There is a lot of confusion among implementers of ML-KEM and the difference
between the 'pure' and 'prehash' versions. While working on my
implementation, I am now convinced we just got it wrong in Ed25519 and
Ed448 which do things differently.

The protocol concern here is binding the message digest to the signature.
This is an issue that Butler Lampson and Ron Rivest have told me is
essential and I consider essential and why would we even have an argument
over whether a digest substitution attack is a concern. It just is.

As a side bar, let me also point out that semantic substitution is also a
legitimate concern and that might well mean that we end up making some
different choices in protocol designs.

As a protocol designer, there are two use cases of interest. One is where I
get to pick the content digest without restriction and the other is where
the choice is made for me because the content is already digested at the
point I am generating the signature. Often this is because it is being
digested for multiple purposes, in the DARE construction I use in the Mesh,
I digest the content of every envelope with SHA-2-512 or SHA-3-512 and I
use that digest to construct the Merkle tree over the message sequence and
as an input to the signature.


The objective of ML-KEM is to prevent a digest substitution attack by
binding the digest algorithm to the message digest. What it is doing in
effect is to create a manifest, prefixing a flag saying 'manifest' and
signing that with ML-DSA-Internal.

The objective of ML-DSA PURE is to allow direct access to ML-DSA-Internal
to sign messages when the content hasn't been prehashed already. People
have suggested quite a few purposes for this but the only purpose I see a
good argument for is to create *more expressive* manifest formats.


For example, let us say we are signing a JPG, we probably want to say we
are signing a JPG and the principled way to do that in JOSE or COSE would
be to build a manifest with the content digest, content digest algorithm
and content type.

[Yes, I am aware that you could use context for this but a much better use
for that is to declare your manifest format]

In the DARE construction, I am just updating the code so the signature is
over the envelope content digest AND the Merkle tree head. So one signature
does both.


OK so what went wrong in Ed25519 and Ed448? Problem was we were focused on
the security of the signature and NOT how it fits into other protocols. And
as a result we don't actually have a functional scheme for signing content
that was already digested with a specific hash.

What seems to have happened in practice is that instead of accepting the
hash choices picked by EdDSA, the implementers have done hash-then-sign in
the exact same manner as for RSA and passed the result in to be signed by a
random choice of Pre or pure.

So it appears that we probably have protocols that have effectively broken
uses of EdDSA. There is no viable attack right now but this is something we
should fix.

Certificates are probably the exception because we care enough about those
to make sure we get them right.


One approach is to update the RFC so that it matches the functionality of
ML-DSA. I think we should do that regardless simply to ease deployment of
both. We are going to be having this issue come up again and again.

A new rev to the RFC gives us an opportunity to tell people the correct and
safe way to deal with content that has already been hashed with a specific
digest. But the problem there is EdDSA has already made its way into a lot
of crypto APIs and it will take years for any update to make its way out.

So we need to look at using manifests for all content signatures. And that
is actually the better way to go because we can address multiple
substitution attacks, not just the one least likely to be attempted. And we
can do things like binding in notary and encryption witness values and
doing all sorts of other useful stuff.