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

[Ilari Liusvaara <[e-mail]>]

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