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

[Benjamin Kaduk <[e-mail]>]

On Tue, Jul 13, 2021 at 02:37:07PM +0100, Neil Madden wrote:
> On 13 Jul 2021, at 12:29, Ilari Liusvaara <[e-mail]> wrote:
> > 
> > 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.
> 
> 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:

Yes, that is generally true.  But...

> “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> ).
> 
> > 
> > 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.
> 
> 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.

> > 
> > 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).
> > 
> Agreed.

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