Subject: Signature Crypto Algorithm Details

From: Justin Richer <[email-masked]>
Date: Fri, 14 Jan 2022 11:39:15 -0500

Hi all,

In the Signatures draft, we’ve got a bunch of strictly-defined algorithms for people to be able to use out of the box. Crypto primitives are often parameterized, giving a lot of flexibility and choice. The idea here though is that if you’re pulling something out of the named algorithm registry, you wouldn’t have choices to make about how to apply it. (You can, as always, go off and do your own algorithm within your own ecosystem without using the registry values.)

In any event, two elliptic curve algorithms have caught my attention the last couple weeks and I am looking to drum up feedback. First, Edwards curve algorithms, specifically ed25519. It’s been requested by a number of people out there that we add this, so I’ve been working out what parameters we’d need within the spec text to make it interoperable. From early implementations and feedback, we’ve settled on a PureEdDSA algorithm with no pre-hash of the message input, since that seems to be the most common and accepted version of this. We’re preparing text to add this to the draft, and I’m looking to confirm that choice if anyone has any strong feelings on the matter.

Second, the ECDSA algorithm that we define over curve P256 has its own snag that we didn’t realize: the signature in the mathematical model is two separate numbers, r and s. We need to encode a single value, and all the libraries that I used take the approach that you just concatenate the two into a single 64-byte array and call that the signature. However some implementors have gotten back to me that their libraries use an alternative method of encoding, using ASN.1 to wrap the two integers into an ASN.1 structure. A quick survey shows that this is supported on many libraries, but it does have the drawback of pulling in explicit ASN.1 into the signature definition where it isn’t needed elsewhere. I’m currently leaning towards more carefully defining the concatenation approach, similar to what JOSE uses in this case, but I am seeking feedback on this choice.

I know that this is a question more for the security/crypto crowd, and we’ll be reaching out there as well for sure, but I wanted to get a feel for any preference within this community that would be implementing and dealing with this spec on the other side. What do your libraries support for ECDSA and EdDSA inputs and outputs? Do you have a strong feeling on either of these choices?

Thanks,
 — Justin

---

From: Tim Bray <[email-masked]>
Date: Fri, 14 Jan 2022 08:57:27 -0800

>From the point of view of a person who occasionally needs to use public-key
crypto without having a grad-school level of understanding of
hashing algorithm and key lengths and so on, ed25519 in particular has been
very welcome. To use it, you don't have to make any decisions about crypto
parameters of which you lack a deep understanding.  If you look at the
ed25519 libraries in popular programming languages, the calls are
MakeKeyPair, Sign, Verify, Encrypt, and Decrypt; both the key and signature
are opaque short byte sequences.   In particular, to use this stuff, you
don't have to think about PKIX and X509 and so on.

For these reasons, and because the keys and sigs are short, I'm pretty sure
that ed25119 is going to get a lot of adoption in new systems and
protocols. So I'd encourage your draft to preserve these iikable
elliptic-curve features and definitely not require any ASN.1 arcana or
decisions about hashing.

On Fri, Jan 14, 2022 at 8:42 AM Justin Richer <[email-masked]> wrote:

> Hi all,
>
> In the Signatures draft, we’ve got a bunch of strictly-defined algorithms
> for people to be able to use out of the box. Crypto primitives are often
> parameterized, giving a lot of flexibility and choice. The idea here though
> is that if you’re pulling something out of the named algorithm registry,
> you wouldn’t have choices to make about how to apply it. (You can, as
> always, go off and do your own algorithm within your own ecosystem without
> using the registry values.)
>
> In any event, two elliptic curve algorithms have caught my attention the
> last couple weeks and I am looking to drum up feedback. First, Edwards
> curve algorithms, specifically ed25519. It’s been requested by a number of
> people out there that we add this, so I’ve been working out what parameters
> we’d need within the spec text to make it interoperable. From early
> implementations and feedback, we’ve settled on a PureEdDSA algorithm with
> no pre-hash of the message input, since that seems to be the most common
> and accepted version of this. We’re preparing text to add this to the
> draft, and I’m looking to confirm that choice if anyone has any strong
> feelings on the matter.
>
> Second, the ECDSA algorithm that we define over curve P256 has its own
> snag that we didn’t realize: the signature in the mathematical model is two
> separate numbers, r and s. We need to encode a single value, and all the
> libraries that I used take the approach that you just concatenate the two
> into a single 64-byte array and call that the signature. However some
> implementors have gotten back to me that their libraries use an alternative
> method of encoding, using ASN.1 to wrap the two integers into an ASN.1
> structure. A quick survey shows that this is supported on many libraries,
> but it does have the drawback of pulling in explicit ASN.1 into the
> signature definition where it isn’t needed elsewhere. I’m currently leaning
> towards more carefully defining the concatenation approach, similar to what
> JOSE uses in this case, but I am seeking feedback on this choice.
>
> I know that this is a question more for the security/crypto crowd, and
> we’ll be reaching out there as well for sure, but I wanted to get a feel
> for any preference within this community that would be implementing and
> dealing with this spec on the other side. What do your libraries support
> for ECDSA and EdDSA inputs and outputs? Do you have a strong feeling on
> either of these choices?
>
> Thanks,
>  — Justin
>

---

From: Henry Story <[email-masked]>
Date: Fri, 14 Jan 2022 19:01:21 +0100

> On 14. Jan 2022, at 17:57, Tim Bray <[email-masked]> wrote:
> 
> From the point of view of a person who occasionally needs to use public-key crypto without having a grad-school level of understanding of hashing algorithm and key lengths and so on, ed25519 in particular has been very welcome. To use it, you don't have to make any decisions about crypto parameters of which you lack a deep understanding.  If you look at the ed25519 libraries in popular programming languages, the calls are MakeKeyPair, Sign, Verify, Encrypt, and Decrypt; both the key and signature are opaque short byte sequences.   In particular, to use this stuff, you don't have to think about PKIX and X509 and so on.
> 
> For these reasons, and because the keys and sigs are short, I'm pretty sure that ed25119 is going to get a lot of adoption in new systems and protocols. So I'd encourage your draft to preserve these iikable elliptic-curve features and definitely not require any ASN.1 arcana or decisions about hashing.

( I also prefer my key data to be in plain text rather than Base64 encoded binary ASN.1
which just makes crypto feel like dark magic.)

I got ed25519 to work in Java easily, but I think it is missing in the WebCrypto API in
the browser. At least that is what my initial research suggested.

https://github.com/httpwg/http-extensions/issues/1509#issuecomment-1009913760

It would make a big difference if it were available in the browsers by default I think.
Perhaps someone can relay that to the right folks?

Henry

---

From: Tim Bray <[email-masked]>
Date: Fri, 14 Jan 2022 10:21:38 -0800

> the browser. At least that is what my initial research suggested.

FWIW, here are my explorations of how to interchange ed25519 keys in Java &
Go: https://www.tbray.org/ongoing/When/202x/2021/04/19/PKI-Detective

> >> In the Signatures draft, we’ve got a bunch of strictly-defined
> algorithms for people to be able to use out of the box. Crypto primitives
> are often parameterized, giving a lot of flexibility and choice. The idea
> here though is that if you’re pulling something out of the named algorithm
> registry, you wouldn’t have choices to make about how to apply it. (You
> can, as always, go off and do your own algorithm within your own ecosystem
> without using the registry values.)
> >>
> >> In any event, two elliptic curve algorithms have caught my attention
> the last couple weeks and I am looking to drum up feedback. First, Edwards

---

From: Brian Campbell <[email-masked]>
Date: Fri, 14 Jan 2022 13:58:45 -0700

I'd +1 the r and s concatenation approach.

-- 
_CONFIDENTIALITY NOTICE: This email may contain confidential and privileged 
material for the sole use of the intended recipient(s). Any review, use, 
distribution or disclosure by others is strictly prohibited.  If you have 
received this communication in error, please notify the sender immediately 
by e-mail and delete the message and any file attachments from your 
computer. Thank you._

---

From: Justin Richer <[email-masked]>
Date: Wed, 26 Jan 2022 12:18:41 -0500

All, I’ve added a PR to clarify the ECDSA signature encoding process as well as add EdDSA support, as described below and discussed on this thread. Please take a look:

https://github.com/httpwg/http-extensions/pull/1899 <https://github.com/httpwg/http-extensions/pull/1899>

Another small change here is added text on nondeterministic signature algorithms, and what that means for verifying the examples and in practice.

 — Justin

> On Jan 14, 2022, at 11:39 AM, Justin Richer <[email-masked]> wrote:
> 
> Hi all,
>