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

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

The reason pure works for OpenPGP is that they don't sign the digest, they
sign a manifest (aka trailer) binding the digest to the digest algorithm.

So the rule is that IF you prehash your data, you MUST use a manifest.
ML-DSApre is one option for a manifest format, XML Signature JOSE and COSE
also define ways to specify manifests. If you are not using ML-DSApre for
the manifest, you should use ML-DSA Pure.

So given content <content> there are three options.

A) Signature = MLDSA (sk, content)
B) Signature = MLDSA (sk, Manifest (Digest(content), DigestAlg))
C) Signature = MLDSApre (sk, Digest(content), DigestAlg)


What you must not do is D) MLDS (sk, Digest(content)). If people think they
need to worry about Quantum Cryptanalysis and not worry about downgrade
attacks, well...

For EdDSA, the choices are

A) Signature = EdDSA (sk, content)
B) Signature = EdDSA (sk, Manifest (Digest(content), DigestAlg))
C) Signature = EdDSApre (sk, Digest(content)) WHERE Digest MUST be the one
specified.

I don't think C is remotely practical. I think implementations will end up
picking their own content digest. So either they use a manifest format or
it will end up failing.

This is probably an error that has been caught and avoided. But while we
are upgrading systems to ML-DSA, we should take the time to make sure EdDSA
was done right.



On Fri, Aug 30, 2024 at 4:10 AM Daniel Huigens <[e-mail]>
wrote:

> Hi Phillip,
>
> On Thursday, August 29th, 2024 at 18:55, Phillip Hallam-Baker wrote:
>
> There is a lot of confusion among implementers of [ML-DSA] 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.
>
>
> I personally think a lot of the confusion comes from assumptions people
> are making about what the pure and prehash versions are meant to be used
> for, that contradict what's actually stated in the specs (both FIPS 204 and
> RFC 8032).
>
> The objective of [HashML-DSA] 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.
>
>
> That's not quite what FIPS 204 says, in fact it almost says the opposite:
>
> > If the content is not hashed at the application level, the pre-hash
> version of ML-DSA signing may be used.
>
> which also implies that if the content *has* been hashed at the
> application level, the pure version of ML-DSA should (or must?) be used.
>
> For binding the hash algorithm that was used to the (pure) ML-DSA
> signature, the context parameter could be used as you suggested in the
> OpenPGP thread, so using HashML-DSA isn't actually necessary for that. And
> the spec also says:
>
> > In general, the “pure” ML-DSA version is preferred.
>
> This is similar to RFC 8032, by the way, which says:
>
> > The Ed25519ph and Ed448ph variants are prehashed.  This is mainly
> > useful for interoperation with legacy APIs, since in most of the
> > cases, either the amount of data signed is not large or the protocol
> > is in the position to do digesting in ways better than just
> > prehashing (e.g., tree hashing or splitting the data).  The
> > prehashing also makes the functions greatly more vulnerable to
> > weaknesses in hash functions used.  These variants SHOULD NOT be
> > used.
> > (...)
> > In summary, if a high 128-bit security level is enough, use of
> > Ed25519 is RECOMMENDED; otherwise, Ed448 is RECOMMENDED.
>
> In other words, it is recommended that the protocol preprocesses the data
> in some way if necessary (although preferably by tree hashing or chunking,
> in the eyes of this text) and then uses PureEdDSA, rather than using
> HashEdDSA.
>
> For Ed448, the context parameter can be used to prevent domain confusion,
> same as for ML-DSA. Pure Ed25519 unfortunately doesn't have a context
> parameter, so in that case protocols/applications need to be careful not to
> reuse a key for signing both content and hash digests, but that's usually
> not a huge ask.
>
>
> So, even though I think it's a bit confusing that both FIPS 204 and RFC
> 8032 introduce variants that they then recommend not to be used, I don't
> think there's any huge issue here that needs fixing.
>
> Best,
> Daniel
>
>
> ---
>
> Daniel Huigens
> Cryptography Team Lead
> Proton AG
>
>