Subject: [COSE] draft-ietf-cose-rfc8152bis-algs-06: Incompatible encoding of EdDSA public keys

From: Andrew Kozlik <[email-masked]>
Date: Thu, 27 Feb 2020 16:14:01 +0100

Hello everyone,

I encountered a bug in libfido2 (
https://github.com/Yubico/libfido2/issues/136), which leads me to propose
some changes in COSE encoding of EdDSA public keys. Here is the problem:

The standard encoding of EdDSA public keys as defined in
https://tools.ietf.org/html/rfc8032#section-5.1.2 encodes the y-coordinate
and the sign of the x-coordinate of the EC point as the public key. COSE on
the other hand encodes only the x-coordinate as the public key, see
https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.2.
There are two problems with this discrepancy:

1. As far as I know, all libraries support only the standard RFC 8032
encoding of public EdDSA keys. Computing the y-coordinate from the
x-coordinate and vice versa is not straightforward, because it involves
some multi-precision modular arithmetic, making it very problematic to use
the COSE format for anyone who is not well versed in the mathematics of
ECC. Even if libraries were to support both encodings in the future, it
would cause a lot of pointless confusion to developers.

2. There is no way to determine the sign of the y-coordinate from knowing
only the x-coordinate. Thus when verifying a signature, one has to try both
signs for the y-coordinate of the public key and accept the signature if
either of the two signature verifications passes.

To resolve these issues, I propose the following changes:

1. In Table 18,
https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1,
the key type of Ed25519 and Ed448 keys should be changed to EC2.

2. In Section 7.1.1,
https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1.1,
the 'x' parameter of EC2 keys should be allowed to contain either the sign
bit or the value of the x-coordinate for the EC point. In addition there
should be a requirement stating that if the 'x' or 'y' parameter is present
in the structure, then at least one of them MUST be of CBOR type bstr.

Cheers,
Andrew Kozlik

---

From: Neil Madden <[email-masked]>
Date: Thu, 27 Feb 2020 16:23:27 +0000

This seems to be an unfortunate choice (mistake?) in RFC 8152. The OKP key type for JOSE (https://tools.ietf.org/html/rfc8037#section-2 <https://tools.ietf.org/html/rfc8037#section-2>) uses the "x" field for the public key (however encoded), so for EdDSA keys the "x" field in an OKP is actually the encoded form specified in RFC 8032: a y-coordinate and the sign bit of the x-coordinate.

IMO the OKP key type in JOSE is a bit of a mess. It would have been better to define separate key types for Montgomery x-only public keys vs EdDSA keys, or else otherwise call that field "pub" or something less likely to be misinterpreted. I'm not sure trying to cram Edwards curves into the EC2 key type makes things any better and may break assumptions in code about EC2 keys always being used for Weierstrass-form curves only.

I think it would be best to either register an errata against RFC 8152 (and fix in the draft) that brings the COSE OKP type into alignment with JOSE and state that the "x" field for EdDSA keys is the RFC 8032 encoded form. Or otherwise define an entirely new key type and deprecate the use of OKP for EdDSA keys.

> On 27 Feb 2020, at 15:14, Andrew Kozlik <andrew.kozlik=[email-masked]> wrote:
> 
> Hello everyone,
> 
> I encountered a bug in libfido2 (https://github.com/Yubico/libfido2/issues/136 <https://github.com/Yubico/libfido2/issues/136>), which leads me to propose some changes in COSE encoding of EdDSA public keys. Here is the problem: 
> 
> The standard encoding of EdDSA public keys as defined in https://tools.ietf.org/html/rfc8032#section-5.1.2 <https://tools.ietf.org/html/rfc8032#section-5.1..2> encodes the y-coordinate and the sign of the x-coordinate of the EC point as the public key. COSE on the other hand encodes only the x-coordinate as the public key, see https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.2 <https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.2>. There are two problems with this discrepancy:
> 
> 1. As far as I know, all libraries support only the standard RFC 8032 encoding of public EdDSA keys. Computing the y-coordinate from the x-coordinate and vice versa is not straightforward, because it involves some multi-precision modular arithmetic, making it very problematic to use the COSE format for anyone who is not well versed in the mathematics of ECC. Even if libraries were to support both encodings in the future, it would cause a lot of pointless confusion to developers.
> 
> 2. There is no way to determine the sign of the y-coordinate from knowing only the x-coordinate. Thus when verifying a signature, one has to try both signs for the y-coordinate of the public key and accept the signature if either of the two signature verifications passes.
> 
> 1. In Table 18, https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1 <https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1>, the key type of Ed25519 and Ed448 keys should be changed to EC2.
> 
> 2. In Section 7.1.1, https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1.1 <https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1.1>, the 'x' parameter of EC2 keys should be allowed to contain either the sign bit or the value of the x-coordinate for the EC point. In addition there should be a requirement stating that if the 'x' or 'y' parameter is present in the structure, then at least one of them MUST be of CBOR type bstr.
> 
> Cheers,
> Andrew Kozlik
> _______________________________________________
> COSE mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cose

---

From: Jim Schaad <[email-masked]>
Date: Fri, 28 Feb 2020 10:24:46 -0800

This would seem to be more of an issue of what the text label in the OKP key
type is.  I have no problems with changing this is the COSE document as the
text label is completely arbitrary.   On the other hand, keeping the
correspondence to what is in the JOSE draft also seems to be of importance.
It would be easy to make the change and have a note that dealt with the
differences however.

Andrew, I completely disagree with you that there are two fields are the
result of encoding a public key in the EdDSA draft.  Section 5.1.2 makes it
clear that when you are finished you only have an integer value of 32
octets.  There is no separate sign bit so changing it to EC2 would be
completely inappropriate.     If you look at the examples in section 7 you
will see that the Public Key is clearly just a single 32 octet value with no
place for a sign bit.

I believe that the correct result that has been implemented for both JOSE
and COSE is to take encoding that is specified in RFC 8152 and use that as
the public key.  I know that I compared all of my code with the text vectors
in RFC 8152 so that I will be shocked if this is not true.  If this is not
clear in either document then we need to change that text.

Jim

From: COSE <[email-masked]> On Behalf Of Neil Madden
Sent: Thursday, February 27, 2020 8:23 AM
To: Andrew Kozlik <andrew.kozlik=[email-masked]>
Cc: cose <[email-masked]>
Subject: Re: [COSE] draft-ietf-cose-rfc8152bis-algs-06: Incompatible
encoding of EdDSA public keys

This seems to be an unfortunate choice (mistake?) in RFC 8152. The OKP key
type for JOSE (https://tools.ietf.org/html/rfc8037#section-2) uses the "x"
field for the public key (however encoded), so for EdDSA keys the "x" field
in an OKP is actually the encoded form specified in RFC 8032: a y-coordinate
and the sign bit of the x-coordinate.

IMO the OKP key type in JOSE is a bit of a mess. It would have been better
to define separate key types for Montgomery x-only public keys vs EdDSA
keys, or else otherwise call that field "pub" or something less likely to be
misinterpreted. I'm not sure trying to cram Edwards curves into the EC2 key
type makes things any better and may break assumptions in code about EC2
keys always being used for Weierstrass-form curves only.

I think it would be best to either register an errata against RFC 8152 (and
fix in the draft) that brings the COSE OKP type into alignment with JOSE and
state that the "x" field for EdDSA keys is the RFC 8032 encoded form. Or
otherwise define an entirely new key type and deprecate the use of OKP for
EdDSA keys.

On 27 Feb 2020, at 15:14, Andrew Kozlik
<andrew.kozlik=[email-masked]
<mailto:andrew.kozlik=[email-masked]> > wrote:

Hello everyone,

I encountered a bug in libfido2
(https://github.com/Yubico/libfido2/issues/136), which leads me to propose
some changes in COSE encoding of EdDSA public keys. Here is the problem: 

The standard encoding of EdDSA public keys as defined in
https://tools.ietf.org/html/rfc8032#section-5.1.2
<https://tools.ietf.org/html/rfc8032#section-5.1..2>  encodes the
y-coordinate and the sign of the x-coordinate of the EC point as the public
key. COSE on the other hand encodes only the x-coordinate as the public key,
see
https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.2.
There are two problems with this discrepancy:

1. As far as I know, all libraries support only the standard RFC 8032
encoding of public EdDSA keys. Computing the y-coordinate from the
x-coordinate and vice versa is not straightforward, because it involves some
multi-precision modular arithmetic, making it very problematic to use the
COSE format for anyone who is not well versed in the mathematics of ECC.
Even if libraries were to support both encodings in the future, it would
cause a lot of pointless confusion to developers.

1. In Table 18,

2. In Section 7.1.1,
https://tools.ietf.org/html/draft-ietf-cose-rfc8152bis-algs-06#section-7.1.1
, the 'x' parameter of EC2 keys should be allowed to contain either the sign
bit or the value of the x-coordinate for the EC point. In addition there
should be a requirement stating that if the 'x' or 'y' parameter is present
in the structure, then at least one of them MUST be of CBOR type bstr.

Cheers,

Andrew Kozlik

_______________________________________________
COSE mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/cose

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 29 Feb 2020 11:52:25 +0200

> clear in either document then we need to change that text.
 
I am not sure I agree.

The correct interpretation for JOSE is to take the contents of "x"
field, base64url decode it, and stuff the result raw into Ed25519
signing/verification (as defined by RFC 8032) as an octet string
(and "d" is base64url decoded and stuffed raw into Ed25519 signing).

I can take the keypair test vector from RFC 8037 and stuff it into
program that definitely takes the above interpretation (I wrote it)
and it both passes key consistency check and passes signature self-
verify check.

Now, the same program also supports COSE keys. When coding that support,
I assumed that COSE way is straightforward port of JOSE (encode
constants as integers, encode base64url'd string as raw bstr), and thus
the code just stuffs whatever is in "x" field raw into Ed25519 signing/
verification (as defined by RFC 8032) as an octet string (and "d" is
another bstr and stuffed raw into Ed25519 signing as octet string).

Now RFC 8152 says:

"This contains the x-coordinate for the EC point.  The octet string
represents a little-endian encoding of x."

Which is just plain wrong for Ed25519 and Ed448. As the public key is
encoding of y coordinate together with sign bit of x coordinate. And
even that COSE should not be concerned with: It should treat RFC 8032
public keys as octet strings.

And even for X25519 and X448, it is not quite correct, because the
X25519 and X448 public keys are not integers, they are octet strings
(which happen to be little-endian encoding of x coordinate of an
elliptic-curve point).

Now, it is possible to recover the y coordinate of Ed25519 and Ed448
keys from the x coordinate, but the algorithm is fairly slow (due to
calculating the lth multiple), and I do not think it has ever been
implemented.

What I think all COSE implementations of EdDSA do is to stuff the
bstr x raw into RFC 8032 EdDSA implementations as octet string (that is
definitely what my code is doing).

-Ilari

---

From: Andrew Kozlik <[email-masked]>
Date: Sat, 29 Feb 2020 12:32:28 +0100

Neil and Ilari, thank you for your feedback, you have identified the
problem correctly. Based on all of the responses I see that the intention
was to define the OKP key type in COSE to be compatible with the JOSE
definition, which is something that I wholeheartedly support. I therefore
retract my initial proposal of changing the key type to EC2.

Clearly then, the COSE definition of OKP which is currently given in RFC
8152 is completely wrong for Ed25519 and Ed448 and needs to be fixed. Neil,
I don't think it's necessary to define a separate type for x-only public
keys. Changing the name of the 'x' parameter to something more generic like
'pub' would make a lot of sense though, especially seeing as it got Jim so
terribly confused.

Andrew