Subject: [jose] COSE/JOSE elliptic curves and their relationship with key types

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 7 Jul 2021 14:20:59 -0700

Hi all,

I'd like to get some input from the WGs on the history and intent of the
relationship between elliptic curves and their corresponding key type(s).

At present, it seems that for every elliptic curve listed in the respective
COSE and JOSE registries
(https://www.iana.org/assignments/cose/cose.xhtml#elliptic-curves ,
https://www.iana.org/assignments/jose/jose.xhtml#web-key-elliptic-curve),
there is exactly one key type that is used for points on that curve.  For
example, the NIST curves P-256, P-384, and P-521 use key type EC (for JOSE)
and EC2 (for COSE), and the "CFRG curves" Ed25519, Ed448, X25519, and X448
use OKP.

There is not a huge amount of guidance in the foundational RFCs, but I'll
try to summarize the hints I found, below:

JOSE only had the NIST curves in RFC 7518, so all the original elliptic
curves used the "EC" key type.  The registry template for curves does not
include the "kty" value(s), but the template for key parameters does.  In
particular, the column heading has the formulation 'Used with "kty"
Value(s)' that admits more than one "kty" for a given parameter (and
indeed, "crv" us used with both "EC" and "OKP".  But this seems to only be
used in practice, at least so far, as just another means for scoping the
parameter name -- the aforementioned "crv" entries appear on separate lines
in the registry, with the implication that the "crv" parameter might have a
different interpretation depending on which "kty" value it was seen with.
RFC 8037 added the CFRG curves and the "OKP" key type, with description:

   A new key type (kty) value "OKP" (Octet Key Pair) is defined for
   public key algorithms that use octet strings as private and public
   keys.  It has the following parameters:
   [...]
   o  The parameter "crv" MUST be present and contain the subtype of the
      key (from the "JSON Web Elliptic Curve" registry).

   [...]

In particular, the "public key algorithms that use octet strings as private
and public keys" suggests (at least to me) that the document was written
with an assumption that a given public-key algorithm would have a single
way in which to represent public and private keys.

COSE has done things a bit differently than JOSE (and not just by changing
the "kty" name to "EC2"), in particular by having a "key type" column in
the registry for COSE Elliptic Curves.  I note that in the live registry
and in RFC 8152, the column heading is the singular "Key Type", but in RFC
8152 the description of this column is "This designates the key type(s)
that can be used with this curve" that apparently admits more than one.
draft-ietf-cose-rfc8152bis-algs does not have a description of the registry
in its IANA Considerations section to refer to for comparison.  There are
admonitions throughout RFC 8152 and the bis, that applications must check
that the curve and key type are consistent and reject a key if they are
not.  As written, that seems to allow a notion of "consistent" that is not
strictly 1:1, but all of the curves defined so far only have that 1:1
mapping, and trying to use any other "kty" for an existing curve would run
into interop problems with existing implementations that reject other "kty"
values for that curve.

Do we expect a strict relationship where each curve has exactly one "kty"
that it's used with?  If not, in what scenario(s) would there be multiple
"kty" values to use with a single curve?

Thanks,

Ben

---

From: Michael Richardson <[email-masked]>
Date: Wed, 07 Jul 2021 18:42:35 -0400

Benjamin Kaduk <[email-masked]> wrote:
    > As written, that seems to allow a notion of "consistent" that is not

It seems to me that we think it's always gonna be 1:1, but that we admit that
we can't predict the future, and so we are providing some extra rope.

It also seems that we might also be thinking that there might be other ways
to encode the keys (into bytes), but that mostly it is the case that we have
a single encoding that we stick to.

(Why did we call it "EC2". Huh)

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 12 Jul 2021 20:46:00 -0700

Hi Michael,

Thanks for sharing your thoughts.

> we can't predict the future, and so we are providing some extra rope.

There is of course a reason that I am asking the question.  I had hoped
to separate the initial batch of responses to the general question from the
specific case, so I didn't mention it in the initial note, but
draft-ietf-lwig-curve-representations registers the Wei25519 and Wei448
elliptic curves (the short-Weierstrass analogues of Curve25519 and
Curve448), and currently lists the key type for both as "EC2 or OKP".

To my knowledge, these curve (representation)s are not in wide use and
there is thus not a well-established single point representation to use
with them.  However, since the intent of the work is to expose the CFRG
curves' benefits to implementations tailored to short-Weierstrass curves,
which in turn would be likely to use the "EC2" representation in its
interfaces, it seems like if we were to pick a preferred representation it
would be "EC2".

> a single encoding that we stick to.

But for a protocol don't we kind of only want a single encoding anyway?

> (Why did we call it "EC2". Huh)

I feel like I used to know this, but am drawing a blank.  Maybe that there
are two coordinates included?

Thanks again,

Ben

---

From: Neil Madden <[email-masked]>
Date: Tue, 13 Jul 2021 07:56:55 +0100

My understanding is that single-coordinate representations (OKP) are safer because they reduce the scope for invalid curve attacks, but that they were patent-encumbered for many years. With a double-coordinate representation you have to carefully check that (x,y) satisfies the curve equation. With a single coordinate you instead calculate y from x using the curve equation (if you need it), so it can’t fail to satisfy it. IMO, that should be the preferred representation for any new curves. 

Note that if you want to be completely unambiguous then you typically want a single coordinate (x) plus a bit to say which of the two roots to use for the y-coordinate. RFC 8037 allows this by not committing to what “x” represents, but RFC 8152 for COSE says that the “x” field is the little-endian encoding of the x-coordinate specifically, so you might need a different type. (In fact, EdDSA public keys are the *y* coordinate plus a single bit to say which x-coordinate to use, so I think COSE is already breaking its own contract).

— Neil

> On 13 Jul 2021, at 04:46, Benjamin Kaduk <[email-masked]> wrote:
> 
> Hi Michael,
> 
> _______________________________________________
> jose mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/jose

-- 
ForgeRock values your Privacy <https://www.forgerock.com/your-privacy>

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 13 Jul 2021 14:12:47 +0300

> Curve448), and currently lists the key type for both as "EC2 or OKP".

To my knowledge, the goals of those curves are:

- Be compatible with devices with arbitrary-curve short-Weierstrass
  acceleration.
- Be compatible with legacy EC algorithms (e.g., ECDH, ECDSA). However,
  there are some nasty edge cases here.
- Use more efficient base fields and ladders where acceleration is not
  available.

> interfaces, it seems like if we were to pick a preferred representation it

There is well-established encoding for short-Weierstrass curves to bytes:
the secg encoding (there are both compressed and uncompressed variants).
However, These curves are intended to be worked with general-purpose
short-Weierstras implemenations, and COSE EC2 (and JOSE EC) are intended
for the same class, so EC2 is the correct choice, and allowing both
would just add more code.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 13 Jul 2021 14:29:54 +0300

On Tue, Jul 13, 2021 at 07:56:55AM +0100, Neil Madden wrote:
> My understanding is that single-coordinate representations (OKP) are
> safer because they reduce the scope for invalid curve attacks, but
> that they were patent-encumbered for many years. With a double-
> coordinate representation you have to carefully check that (x,y)
> satisfies the curve equation. With a single coordinate you instead
> calculate y from x using the curve equation (if you need it), so
> it can’t fail to satisfy it. IMO, that should be the preferred
> representation for any new curves. 

To actually eliminate invalid-curve attacks, one needs representation
that seamlessly switches between curve and its twist, in addition to
the curve being designed so that both it and its twist are strong
curves. AFAIK, pretty much the only application one can exploit this is
ECDH.

Just compressing is not enough: There are square root algorithms that
produce some bogus result if given number with no square root. I do
not know how such bogus y would interact with elliptic-curve
arithmetic, but it might not be good.

And while in general, it is preferred that key formats are defined as
octet strings, and thus mapped as OKP, in specific case of lwig-curves,
since those are short-weierstrass points intended to be used with
legacy algorithms, EC2 is much better match.

And thinking about future post-quantum algorithms, all the NISTPQC
stuff has octet string keys, so OKP would be correct match. However,
new algorithms are needed for PQC, especially for KEMs.

> Note that if you want to be completely unambiguous then you typically
> want a single coordinate (x) plus a bit to say which of the two roots
> to use for the y-coordinate. RFC 8037 allows this by not committing
> to what “x” represents, but RFC 8152 for COSE says that the “x” field
> is the little-endian encoding of the x-coordinate specifically, so
> you might need a different type. (In fact, EdDSA public keys are the
> *y* coordinate plus a single bit to say which x-coordinate to use,
> so I think COSE is already breaking its own contract).

Right, to actually get a curve point, you need x and sign bit of y
(with Edwards curves, one could alternatively use the more common
y coordinate and sign of x representation).

And on RFC 8152 saying it is little-endian encoding of x-coordinate,
that is just plain incorrect. And in fact, it has led to some
confusion. The whole idea of OKP is to abstract on encoding, making
it specific to subtype. In JOSE, there are currently two distinct
encodings that both use OKP type (and in future, there may be more).

-Ilari

---

From: Neil Madden <[email-masked]>
Date: Tue, 13 Jul 2021 14:37:07 +0100

> arithmetic, but it might not be good.

Sure, that’s why I said “reduce the scope” rather than eliminate. I would still say compressed/OKP representations are safer than uncompressed two-coordinate representations. As http://safecurves.cr.yp.to/twist.html <http://safecurves.cr.yp.to/twist.html> says:

“A protocol designer can help protect against [invalid curve attacks] by specifying point compression. An implementation that receives a compressed point, such as x and just one bit of y, will naturally detect invalid inputs when it reconstructs the missing coordinate.”

Although some square root algorithms may produce bad results for a non-square input, many will produce an error, which is preferable to no check being done at all (which has been the case in the past: http://blog.intothesymmetry.com/2017/03/critical-vulnerability-in-json-web.html <http://blog.intothesymmetry.com/2017/03/critical-vulnerability-in-json-web.html> ).

> legacy algorithms, EC2 is much better match.

But as you say, these existing implementations are going to work with secg encoding, not JWK. So in either case you have some translation to do.

> encodings that both use OKP type (and in future, there may be more).
Agreed.

— Neil

---

From: Michael Richardson <[email-masked]>
Date: Tue, 13 Jul 2021 12:06:17 -0400

Benjamin Kaduk <[email-masked]> wrote:
    >> It also seems that we might also be thinking that there might be other
    >> ways to encode the keys (into bytes), but that mostly it is the case
    >> that we have a single encoding that we stick to.

    > But for a protocol don't we kind of only want a single encoding anyway?

As the thread between Neil and Ilari shows, there were reasons to make
different choices.

My take, being intentionally not intimate with such issues, is that the best
encoding for using the key may not be the best encoding for transmitting the
key.   That the translation between the two forms might sometimes fail, and
so it's a protocol decision as to which to transmit, which to sign (in a
certificate), etc.
(And that this was the entire lwig-curves document's point)

    > I feel like I used to know this, but am drawing a blank.  Maybe that
    > there are two coordinates included?

I have always been blissfully ignorant.

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 21 Jul 2021 11:19:44 -0700

> Sure, that’s why I said “reduce the scope” rather than eliminate. I would still say compressed/OKP representations are safer than uncompressed two-coordinate representations. As http://safecurves.c…

Yes, that is generally true.  But...

> But as you say, these existing implementations are going to work with secg encoding, not JWK. So in either case you have some translation to do.

...there seems to be a qualitative difference between a translation that's
"encode a single bignum" vs a translation that's "do some curve arithmetic
to recover y".  Adding such new code to an implementation that doesn't
already have it seems like more risk than a fairly mechanical translation
of encoding.  If the implementation is already using secg encoding it
already ought to be checking that the provided point is on the curve.
Maybe it doesn't, but that's not exactly a new problem introduced by the
new curve.

> > encodings that both use OKP type (and in future, there may be more).

rfc8152bis-algs (currently in AUTH48) is somewhat better here, saying only
"(For X25519, internally it is a little-endian integer.)".  I'd be fairly
amenable to removing that sentence entirely, if there's WG support.

Thanks,

Ben

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 21 Jul 2021 11:21:59 -0700

> key.   That the translation between the two forms might sometimes fail, and

This sounds like you are in favor of allowing multiple "kty" values?

> (And that this was the entire lwig-curves document's point)

FWIW, my understanding is that if the translation fails then the point/key
is malformed anyway and should not be used.

-Ben

---

From: Michael Richardson <[email-masked]>
Date: Wed, 21 Jul 2021 18:47:55 -0400

> This sounds like you are in favor of allowing multiple "kty" values?

Uhm, I'm not sure I think that.
I think that I said that it could be that need to accomodate different
encodings.  I didn't think that they would both be present.

    > is malformed anyway and should not be used.

I guess translation fails, means there is a non-sense operation in the
middle, like divide-by-zero or infinity?  That is, it can be detected.

I agree that this is true for Ecliptic Point algorithms that we currently use.
It could be (I have no knowledge here) that this isn't always the case.
Could the translation fail, but result in what syntatically looks right, but
it just always fails to validate a signature?
Is that distinguishable from the case where Mallory toggles some bits?