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

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

Oh cripes. yup. That is what you get writing messages on ML-DSA while
trying to wrestle ML-KEM into your code.


On Thu, Aug 29, 2024 at 1:00 PM Deirdre Connolly <[e-mail]>
wrote:

> 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]
>>
>