[openpgp] Re: pure vs. pre-hash in FIPS 204 and 205

[Falko Strenzke <[e-mail]>]

I'll try to make clear where the misconception lies. This hopefully also 
answers Daniel's question in this regard. I'll give a (hopefully) 
consistent write up first, and further down I also give some inline 
comments to your message.

RFC 8032 specifies PureEdDSA and HashEdDSA. The latter is what I refer 
to as the pre-hash variant (and RFC 8032 with the formal internal name 
Ed25519ph, ph = "pre-hash"). I restrict the discussion to Ed25519, the 
case of Ed448 is analogous.

The two variants differ in how the message is processed and in the 
result of dom2(F, C).

The differences are that

- for PureEdDSA, we have dom2(F, C) = empty string and PH(M) = identity 
operation, i.e., no hashing happens before the signature operation,
- for HashEdDSA, we have F=1, dom2(F, C) is specified as an actual hash 
computation, and PH(M) is whatever hash function is used to pre-hash the 
message (i.e., typically being hashed on the protocol layer).

This means that for PureEdDSA, the message has to be input directly into 
the signature algorithm. If instead a hash of the message H(M) is input, 
then one specific advantage of the construction of EdDSA is missed, 
namely of not being vulnerable to general hash collision weaknesses in 
the underlying hash algorithms.

The quote from RFC 8032

The prehashing also makes the functions greatly more vulnerable to weaknesses in hash functions used. These variants SHOULD NOT be used.

of course applies to this very construction in RFC 9580, as there the 
hash of the message is input to the signing function, making it 
vulnerable to general collision weaknesses in the hash function used.

(From a security perspective, this is not relevant to v6 signatures due 
to the random salt in signatures, however. It fully applies to v4 
signatures, though).

To use PureEdDSA correctly, no hash of the message may be computed in 
the protocol. Instead, the full message would need to be input to the 
signature function. (I am not saying this should actually have been done 
in RFC 9580, as that doesn't seem to work well with OpenPGP.)

To put this very simple: when a specification of a signature scheme says 
"M" (the message), it is a security problem to replace it by "Hash(M)".

Accordingly, RFC 9580 is effectively using a pre-hash variant of EdDSA. 
However, differently than it is intended by RFC 8032. In order to do it 
compliant with RFC 8032, it would have to be done by using the HashEdDSA 
variant and providing the message hash from the protocol laver to the 
signature function as PH(M). By no means any double hashing occurs 
anywhere, as both you and Daniel have claimed. This probably the source 
of the misunderstanding, which happens when replacing the message M with 
Hash(M).

What theoretically results from the incorrect use of PureEdDSA to 
process a hash of the message, is a signature forgery vulnerability: If 
also correct use of PureEdDSA exists in parallel in a protocol, then it 
would be possible to exchange a message for its hash and still have 
valid signature. The internal domain separation of EdDSA is supposed to 
prevent this (quote from RFC 8032), but certainly requires that the 
message and a hash of it are never confused on the protocol layer:

    The schemes described in this document are designed to be resistant
    to mixing prehashes.  That is, it is infeasible to find a message
    that verifies using the same signature under another scheme, even if
    the original signed message was chosen.

As I wrote before, I don't think this problem really applies to OpenPGP, 
since if PureEdDSA with the message as direct input (i.e., correct use 
of PureEdDSA) should ever also be specified for OpenPGP, the scheme 
would receive a different algorithm ID. The algorithm ID then ensures 
the domain separation in OpenPGP's own digest computation.

Am 26.08.24 um 11:44 schrieb Justus Winter:
> Hi Falko :)
>
> Falko Strenzke<[e-mail]> writes:
>
>> I attribute this at least in part to a misunderstanding about the
>> variants “pure” vs. “pre-hash” in RFC 8032 (EdDSA) as well as FIPS 204
>> and 205. The idea is to use the pre-hash variant whenever the message
>> is first hashed and then input to the signature algorithm. As I had
>> mentioned on this list as well, this is done – formally – wrong in RFC
>> 9580, which specifies to use the pure variant of EdDSA to sign the
>> hash of the message.
> I continue to be puzzled by this assertion, but I want to make another
> effort to understand it.
>
> RFC8032 defines two variants: PureEdDSA and HashEdDSA.  They differ in
> the prehash parameter:
>
>     11.  A "prehash" function PH.  PureEdDSA means EdDSA where PH is the
>          identity function, i.e., PH(M) = M.  HashEdDSA means EdDSA where
>          PH generates a short output, no matter how long the message is;
>          for example, PH(M) = SHA-512(M).
>
> I'm convinced that OpenPGP uses the PureEdDSA variant, i.e.:
>
>    sig = PureEdDSA(Hash(OpenPGP_Hash_Stream))
>                    ^ This happens in OpenPGP
>
> The evidence I have gathered for that is:
>
> - Sequoia useshttps://docs.rs/nettle/latest/nettle/ed25519/fn.sign.html
> - This primitive is tested against the test vectors from
>    https://datatracker.ietf.org/doc/html/rfc8032#ref-ED25519-TEST-VECTORS
> - These test vectors are part of the test vectors for "Ed25519"
>    https://datatracker.ietf.org/doc/html/rfc8032#section-7.1
> - Ed25519 is EdDSA instantiated with: [...]
>    |   PH(x)   | x (i.e., the identity function)                       |
>    https://datatracker.ietf.org/doc/html/rfc8032#section-5.1
> -> "Ed25519" is PureEdDSA
> -> Sequoia uses PureEdDSA
> - Sequoia's v6 implementation agrees with all the other v6
>    implementations when using Ed25519-based binding signatures and data
>    signatures
>    https://tests.sequoia-pgp.org/v6.html#Detached_Sign-Verify_roundtrip_with_minimal_key_from_RFC9580
> -> OpenPGP as specified in RFC9580 uses PureEdDSA
Yes, certainly, RFC 9580 is specifying to use PureEdDSA. Only that 
PureEdDSA requires the input of M, and doesn't allow Hash(M) as input.
>
> On the other hand, if OpenPGP were to use the HashEdDSA variant, we'd
> compute:
>
>    sig = PureEdDSA(PH(Hash(OpenPGP_Hash_Stream)))
>                       ^ This happens in OpenPGP
>                    ^ This is the prehash in HashEdDSA
>
> Which seems not ideal.
This is the point of the misunderstanding. There is no double hashing. 
PH(OpenPGP_Hash_Stream) is the only hash that happens.
>
> Concluding, I'm pretty sure that OpenPGP uses PureEdDSA.  Since there is
> obviously some confusion, maybe it is not about what we are doing but
> what we are calling it.
>
> - Are you saying since arguably OpenPGP does pre-hashing, the overall
>    construction looks more like HashEdDSA, and therefore we should have
>    called it that?
There is no choice calling it this or that, as RFC 8032 specifies 
exactly how each variant is built. As I tried to show above, what RFC 
9580 does, is an incorrect use of PureEdDSA, because prior hashing of 
the message leads to a security degradation.
>
> - There is no "pre-hash" variant defined in RFC8032, so maybe that is a
>    FIPS term and the confusion arises because of that?

pre-hash = HashEdDSA, as I mentioned above.

Best regards,
Falko

>
>
> Best,
> Justus
-- 

*MTG AG*
Dr. Falko Strenzke

Phone: [phone]
E-Mail: [e-mail]
Web: mtg.de <https://www.mtg.de>

<https://www.linkedin.com/search/results/all/?fetchDeterministicClustersOnly=true&heroEntityKey=urn%3Ali%3Aorganization%3A13983133&keywords=mtg%20ag&origin=RICH_QUERY_SUGGESTION&position=0&searchId=d5bc71c3-97f7-4cae-83e7-e9e16d497dc2&sid=3S5&spellCorrectionEnabled=false> 

Follow us
------------------------------------------------------------------------
<https://360-german-security-alliance.de/> 
<https://www.itsa365.de/de-de/companies/m/mtg-ag>

MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
Commercial register: HRB 8901
Register Court: Amtsgericht Darmstadt
Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
Chairman of the Supervisory Board: Dr. Thomas Milde

This email may contain confidential and/or privileged information. If 
you are not the correct recipient or have received this email in error,
please inform the sender immediately and delete this email.Unauthorised 
copying or distribution of this email is not permitted.

Data protection information: Privacy policy 
<https://www.mtg.de/en/privacy-policy>