[CFRG] Re: Prehashing in EdDSA vs ML-KEM

[Deirdre Connolly <[e-mail]>]

I think all instances of 'ML-KEM' here are intended to be 'ML-DSA'

On Thu, Aug 29, 2024, 12:56 PM Phillip Hallam-Baker <[e-mail]>
wrote:

> 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.
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>