Subject: [openpgp] Ed25519 and digest choices (issue 31)

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 21 May 2021 13:48:56 -0400

Over on https://gitlab.com/openpgp-wg/rfc4880bis/-/issues/31, jethrogb
writes:

> Appendix A contains an example for EdDSA. The example states that the
> hash function used is SHA2-256. The example also states that the curve
> used is 2b06010401da470f01, which is defined as “Ed25519” elsewhere in
> the draft. However, RFC 8032 specifies Ed25519 as an instantiation of
> EdDSA with specific parameters, one of which is that H is SHA2-512 and
> PH (in the ph case) is SHA2-512. Is it the intention that OpenPGP
> implements not Ed25519 but some other form of EdDSA? If yes, this
> should be called out explicitly in the text and it shouldn't be called
> Ed25519. If no, the example needs to be updated and it would probably
> be good to explicitly call out Ed25519ph in section 14.8.

How does the WG think this should be resolved?

I intend to sign this message with an EdDSA signature from a Curve25519
key, but it will likely use SHA2-256 as the OpenPGP digest choice (in
the EdDSA RFC 8032 framing, that would be the pre-hash "PH" parameter to
EdDSA).  This would mean that we are *not* using Ed25519ph, since
OpenPGP permits variance of the PH parameter.

One approach would be to clarify that OpenPGP signatures made with
Ed25519 SHOULD use SHA2-512 as the OpenPGP digest, which I believe would
align it with Ed25519ph.  But there would still be existing signatures
out there (like the one signing this message) which would use SHA2-256,
and it's hard to say that signature verifiers should reject those
signatures.

Alternately, maybe we should instead reframe OpenPGP's use of Ed25519 as
a "PureEdDSA" scheme that signs only the OpenPGP digest (not the signed
data directly).  That bypasses the "PH" parameter, but it also means
that any cryptanalsis that is applied to EdDSA isn't necessarily
applicable to OpenPGP, because we have this additional step involved.

Either way, it seems that we need to clarify the standard.

       --dkg

---

From: "brian m. carlson" <[email-masked]>
Date: Fri, 21 May 2021 20:18:02 +0000

> applicable to OpenPGP, because we have this additional step involved.

I would prefer this approach.  OpenPGP has traditionally allowed users
to use whatever digest they like with keys, even when the standards have
traditionally fixed a digest.  For example, DSA generally has specified
that either SHA-1 or SHA-2 has to be used and it has to be used with the
proper size q, but we've allowed RIPEMD-160 and SHA-256 with smaller q.

If, for example, we discover a weakness in SHA-512, it should be fine
to switch to SHA3-512 for signatures without problems.

I will admit that using multiple digests may require additional work for
cryptanalysis, but I suspect that if PureEdDSA is secure with arbitrary
messages and the hash function is collision resistant (both of which we
would reasonably expect), then this approach will likely be secure.  I
provide no proof of my conjecture, though.
-- 
brian m. carlson (he/him or they/them)
Houston, Texas, US

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 24 May 2021 11:58:41 -0400

> to switch to SHA3-512 for signatures without problems.

well, it's true that we could swap out PH(x) (the prehash function) but
if i'm understanding EdDSA correctly, we could *not* swap out H(x) (the
hash function), which is SHA-512(dom2(phflag,context)||x) for any
variant of Ed25519.

see https://datatracker.ietf.org/doc/html/rfc8032#section-5.1 for more
details about the EdDSA parameter choices for the three different
flavors of Ed25519.

If i'm understanding how OpenPGP uses Curve25519 for signatures
correctly, I don't think that the OpenPGP choice of digest has any
effect on H(x).  If it does, it's hard to say that we'll have dodged a
SHA-512 weakness entirely.

> provide no proof of my conjecture, though.

I have the same intuition as you, and the same lack of rigorous proof :P

  --dkg

---

From: Wiktor Kwapisiewicz <[email-masked]>
Date: Tue, 25 May 2021 09:37:22 +0200

Hi Daniel,
> Either way, it seems that we need to clarify the standard.

I agree. I've been working on a specific use case (decryption and
validation of messages when public parts of the key are unavailable) and
the amount of cryptographic agility here is, in my opinion, unwarranted.

>From what I can see SHA-256 is the most prevalent hash for ed25519
signed messages now but I see no problem in SHOULD'ing SHA-512 to align
with existing standards.

Kind regards,
Wiktor

---

From: Daniel Huigens <[email-masked]>
Date: Tue, 25 May 2021 10:59:39 +0000

Hi dkg,

I believe there's some confusion in the original issue.

https://datatracker.ietf.org/doc/html/rfc8032#section-5.1 says that:

   Ed25519 is EdDSA instantiated with:

   (...)

   |   PH(x)   | x (i.e., the identity function)     |

This is the function that the specification should (and I believe
tries to) reference. The OpenPGP specification indeed pre-hashes the
message as well, but this is irrelevant to (and comes before) RFC8032,
PH(x) is still x. There should be no need to reference PureEdDSA.

Best,
Daniel

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐

On Friday, May 21st, 2021 at 19:48, Daniel Kahn Gillmor <[email-masked]> wrote:

> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 26 May 2021 11:55:52 -0400

Hi Daniel--

> PH(x) is still x. There should be no need to reference PureEdDSA.

https://datatracker.ietf.org/doc/html/rfc8032#section-4 says:

   This document specifies parameters resulting in the HashEdDSA
   variants Ed25519ph and Ed448ph and the PureEdDSA variants Ed25519 and
   Ed448.

So the non-prehash variant named Ed25519 is indeed "PureEdDSA" -- but
it's being applied to something other than the user-visible "message" in
the OpenPGP context.  Maybe we don't need to reference PureEdDSA
explicitly, but the fact that "Ed25519" is often used as a shorthand for
the whole family of EdDSA mechanisms over curve 25519 introduces some
amount of ambiguity in the spec as it's currently written.

I welcome suggestions for text that clarifies this subtlety in the
draft.

        --dkg