Subject: [Lwip] draft-ietf-lwig-curve-representations-13

From: Göran Selander <[email-masked]>
Date: Fri, 6 Nov 2020 16:19:33 +0000

Hi,

Apologies for cross-posting LWIG and COSE. I had a brief look at draft-ietf-lwig-curve-representations-13 and noticed it registers a lot of new COSE (and JOSE, PKIX, and CMS) algorithms. Has this draft been discussed in COSE (JOSE/CURDLE)? If not, perhaps it should be before being progressed?

  *   The draft needs to manage the overlap with NIST SP 800-186, which should be referenced and mappings, name of curves, etc. aligned. The draft defines Wei25519 and Wei448. It is unclear if these are identical to W-25519, W-448 as defined in NIST SP 800-186. We probably would not want two slightly different definitions and/or names, multiple COSE code points, etc.

  *   The draft registers the COSE algorithm "ECDSA25519" as "ECDSA with SHA-256 and curve Wei25519". That is not how the other COSE signature algorithms work. They work like PKIX where the curve is given by the public key. Also, why cannot W-25519 be used with the existing ES256 signature algorithm?

  *   The draft registers the COSE algorithm "ECDH25519". There are no COSE ECDH algorithms for P-256, why is an ECDH algorithm for W-25519 be needed?

Other questions. I may have missed it, but

  *   is it described what are the expected security properties of ECDSA25519 (including mapping) compared to Ed25519? For example w.r.t. side channel attacks?

  *   has any performance measurements been made comparing ECDSA25519 (including mapping) and Ed25519?

  *   similar questions on security and performance with Wei25519.-3 instead of Wei25519. If I understand right, the former mapping is not reversible, but could benefit from optimized code with hardcoded domain parameters.

  *   ANSI X9.62-2005 was withdrawn in 2015 and is behind a paywall, is this reference necessary?

Göran

---

From: Rene Struik <[email-masked]>
Date: Fri, 6 Nov 2020 14:37:01 -0500

Hi Goran:

Please find below some brief feedback on your note:
- the naming wei25519 has been around since the first draft (Nov 13, 
2017, i.e., 3 years minus 1 week ago), see [1]. NIST indeed produced two 
draft documents, viz. Draft NIST SP 800-186 and Draft FIPS Pub 186-5 (on 
October 31, 2019), which generated lots of (to my knowledge still 
unresolved) comments during public review. It is hard to refer to that 
document, since it is only a draft and unfortunately has quite a few errors.
- earlier versions of the lwig draft have received reviews by the crypto 
review panel (Stanislavslav Smyshlyaev), iotdir early-review (Daniel 
Migault); the sections on COSE/JOSE code point assignments resulted from 
a phone call and various email exchanges with Jim Schaad; the section on 
PKIX/CMS was suggested during IETF Last-Call secdir-review (Russ 
Housley) and reviewed by him. The document had IETF Last-Call Aug 24, 
2020. See, e.g., the status pages [1].
- ECDSA has been around since 1999, has been widely standardized, and 
has seen lots of analysis, where ECDSA25519 is simply yet another 
instantiation. Signature generation and verification times for 
ECDSA25519 should be similar to those of Ed25519 (since timing is 
dominated by scalar multiplication, where one could simply use 
Montgomery arithmetic [3]). In my personal view, ECDSA25519 may be more 
secure than Ed25519 (if only because it is non-deterministic, see 
Security section [6]); similar side-channel care has to be taken in 
either case.
  - As mentioned in the draft, one can easily switch between Wei25519 
and Curve25519 (which requires a single field addition or subtraction 
only, i.e., <.01%, see Appendix E.2 [7]). As mentioned in the draft, one 
could use Wei25519.-3 with an existing generic implementation that 
hardcodes the domain parameter a=-3, but needs to compute an isogeny and 
dual isogeny for this (adding 5-10% cost, see Appendix G.2 [8]]) and a 
~9.5kB table (see Section 5.3 [4]). However, if one already has generic 
hardware support, one may still have a significant win (see Section 6 [5]).
- The isogeny for Wei25519.-3 has odd degree l=47, which is co-prime 
with the order of the curve, so is in fact invertible. With Wei448.-3, 
the isogeny has degree l=2, so is not invertible; however, this does not 
really matter, since it is invertible with correctly generated 
public-private key pairs (which have prime/odd order) and the factor two 
is absorbed with co-factor ECDH, where h=4 then.

I hope this helps.

(*) For ease of tracking, it would help if iana related comments are 
flagged in the subject line (e.g., include (iana) in the beginning hereof).

Best regards, Rene

Ref with hyperlinks:
[1] 
https://datatracker.ietf.org/doc/html/draft-struik-lwig-curve-representations-00
[2] https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/
[3] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-4.3
[4] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-5.3
[5] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-6
[6] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-8
[7] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-E.2
[8] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-G.2

On 2020-11-06 11:19 a.m., Göran Selander wrote:
>
> Hi,
>
> Apologies for cross-posting LWIG and COSE. I had a brief look at 
> draft-ietf-lwig-curve-representations-13 and noticed it registers a 
> lot of new COSE(andJOSE, PKIX, and CMS)algorithms.Has this draft been 
> discussed in COSE(JOSE/CURDLE)? If not, perhaps it should be before 
> being progressed?
>
>   * The draft needs to manage the overlap with NIST SP 800-186, which
>     should be referenced and mappings, name of curves, etc. aligned.
>     The draft defines Wei25519 and Wei448. It is unclear if these are
>     identical to W-25519, W-448 as defined in NIST SP 800-186. We
>     probably would not want two slightly different definitions and/or
>     names, multiple COSE code points, etc.
>
>   * The draft registers the COSE algorithm "ECDSA25519" as "ECDSA with
>     SHA-256 and curve Wei25519". That is not how the other COSE
>     signature algorithms work. They work like PKIX where the curve is
>     given by the public key. Also, why cannot W-25519 be used with the
>     existing ES256 signature algorithm?
>
>   * The draft registers the COSE algorithm "ECDH25519". There are no
>     COSE ECDH algorithms for P-256, why is anECDH algorithm for
>     W-25519 be needed?
>
>   * is it described what are the expected security properties of
>     ECDSA25519(including mapping) compared to Ed25519? For example
>     w.r.t. side channel attacks?
>
>   * has any performance measurements been made comparing
>     ECDSA25519(including mapping) and Ed25519?
>
>   * similar questions on security and performance with Wei25519.-3
>     instead of Wei25519. If I understand right, the former mapping is
>     not reversible, but could benefit from optimized code with
>     hardcoded domain parameters.
>
> _______________________________________________
> COSE mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cose

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: John Mattsson <[email-masked]>
Date: Fri, 6 Nov 2020 22:04:34 +0000

Hi,

I looked through this draft again. I think it is a very good draft and I think it will be a solution to some of the problems IoT devices have with Ed25519. I will bring up this draft for discussion in the LAKE WG at IETF 109.

I find it strange that the IANA registration has not been coordinated with COSE WG at all. I am a bit surprised to see IANA registrations for COSE/JOSE/PKIX/CMS at all in a LWIG draft (is that in charter?). If LWIG wants to register new algorithms, I think LWIG at a minimum should coordinate with COSE WG and other groups. I think this draft should be presented at the next COSE WG meeting.

I support registration of W-25519 and W-448 curves as long they agree with NIST. I would like answers to the questions why ECDSA25519 and ECDH25519 are needed at all. There is no ECDSAP256 and no ECDHP256, so why are specific algorithm registration needed for W-25519?  It makes no sense to me that a special signature registration is needed for COSE but not for PKIX? If PKIX can use ecdsa-with-SHA256 why cannot COSE use ES256?

I don't think ANSI X9.62 is an acceptable normative reference. NIST just removed the normative reference to ANSI X9.62 in SP 186-5.

Cheers,
John

From: COSE <[email-masked]> on behalf of Rene Struik <[email-masked]>
Date: Friday, 6 November 2020 at 20:37
To: Göran Selander <goran.selander=[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [COSE] draft-ietf-lwig-curve-representations-13

Hi Goran:

Please find below some brief feedback on your note:
- the naming wei25519 has been around since the first draft (Nov 13, 2017, i.e., 3 years minus 1 week ago), see [1]. NIST indeed produced two draft documents, viz. Draft NIST SP 800-186 and Draft FIPS Pub 186-5 (on October 31, 2019), which generated lots of (to my knowledge still unresolved) comments during public review. It is hard to refer to that document, since it is only a draft and unfortunately has quite a few errors.
- earlier versions of the lwig draft have received reviews by the crypto review panel (Stanislavslav Smyshlyaev), iotdir early-review (Daniel Migault); the sections on COSE/JOSE code point assignments resulted from a phone call and various email exchanges with Jim Schaad; the section on PKIX/CMS was suggested during IETF Last-Call secdir-review (Russ Housley) and reviewed by him. The document had IETF Last-Call Aug 24, 2020. See, e.g., the status pages [1].
- ECDSA has been around since 1999, has been widely standardized, and has seen lots of analysis, where ECDSA25519 is simply yet another instantiation. Signature generation and verification times for ECDSA25519 should be similar to those of Ed25519 (since timing is dominated by scalar multiplication, where one could simply use Montgomery arithmetic [3]). In my personal view, ECDSA25519 may be more secure than Ed25519 (if only because it is non-deterministic, see Security section [6]); similar side-channel care has to be taken in either case.
 - As mentioned in the draft, one can easily switch between Wei25519 and Curve25519 (which requires a single field addition or subtraction only, i.e., <.01%, see Appendix E.2 [7]). As mentioned in the draft, one could use Wei25519.-3 with an existing generic implementation that hardcodes the domain parameter a=-3, but needs to compute an isogeny and dual isogeny for this (adding 5-10% cost, see Appendix G.2 [8]]) and a ~9.5kB table (see Section 5.3 [4]). However, if one already has generic hardware support, one may still have a significant win (see Section 6 [5]).
- The isogeny for Wei25519.-3 has odd degree l=47, which is co-prime with the order of the curve, so is in fact invertible. With Wei448.-3, the isogeny has degree l=2, so is not invertible; however, this does not really matter, since it is invertible with correctly generated public-private key pairs (which have prime/odd order) and the factor two is absorbed with co-factor ECDH, where h=4 then.

I hope this helps.

(*) For ease of tracking, it would help if iana related comments are flagged in the subject line (e.g., include (iana) in the beginning hereof).

Best regards, Rene

Ref with hyperlinks:
[1] https://datatracker.ietf.org/doc/html/draft-struik-lwig-curve-representations-00
[2] https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/
[3] https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-4.3
[4] https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-5.3
[5] https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-6
[6] https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-8
[7] https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-E.2
[8] https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-G.2

1.       The draft needs to manage the overlap with NIST SP 800-186, which should be referenced and mappings, name of curves, etc. aligned. The draft defines Wei25519 and Wei448. It is unclear if these are identical to W-25519, W-448 as defined in NIST SP 800-186. We probably would not want two slightly different definitions and/or names, multiple COSE code points, etc.

1.       The draft registers the COSE algorithm "ECDSA25519" as "ECDSA with SHA-256 and curve Wei25519". That is not how the other COSE signature algorithms work. They work like PKIX where the curve is given by the public key. Also, why cannot W-25519 be used with the existing ES256 signature algorithm?

2.       The draft registers the COSE algorithm "ECDH25519". There are no COSE ECDH algorithms for P-256, why is an ECDH algorithm for W-25519 be needed?

2.       is it described what are the expected security properties of ECDSA25519 (including mapping) compared to Ed25519? For example w.r.t. side channel attacks?

3.       has any performance measurements been made comparing ECDSA25519 (including mapping) and Ed25519?

4.       similar questions on security and performance with Wei25519.-3 instead of Wei25519. If I understand right, the former mapping is not reversible, but could benefit from optimized code with hardcoded domain parameters.

5.       ANSI X9.62-2005 was withdrawn in 2015 and is behind a paywall, is this reference necessary?

Göran

COSE mailing list

[email-masked]<mailto:[email-masked]>

--

email: [email-masked]<mailto:[email-masked]> | Skype: rstruik

-->

---

From: Mohit Sethi M <[email-masked]>
Date: Tue, 10 Nov 2020 08:39:58 +0000

Hi John,

As a co-chair of the LWIG working group, I am happy that you find this draft from LWIG "very good" and believe that it could help solve "some of the problems IoT devices have with Ed25519".

The IANA registrations of this draft have been reviewed by experts such as Russ Housley and Jim Schaad in the past. We had also received a confirmation from IANA (Sabrina Tanamal) that the JOSE expert has approved the corresponding registrations.

It for the designated experts of various registries to decide wheter some registrations need coordination with other working groups.That being said, more reviews are always welcome (even at this late stage). I am sure Rene can present an update for the COSE working group during IETF 109. Note that the draft has already cleared the IETF last call and the authors/chairs would like to finish this soon(ish).

--Mohit

On 11/7/20 12:04 AM, John Mattsson wrote:

Hi,

Cheers,
John

From: COSE <[email-masked]><mailto:[email-masked]> on behalf of Rene Struik <[email-masked]><mailto:[email-masked]>
Date: Friday, 6 November 2020 at 20:37
To: Göran Selander <goran.selander=[email-masked]><mailto:goran.selander=[email-masked]>, "[email-masked]"<mailto:[email-masked]> <[email-masked]><mailto:[email-masked]>, "[email-masked]"<mailto:[email-masked]> <[email-masked]><mailto:[email-masked]>
Subject: Re: [COSE] draft-ietf-lwig-curve-representations-13

Hi Goran:

I hope this helps.

Best regards, Rene

Ref with hyperlinks:

Göran

COSE mailing list

--

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

---

From: John Mattsson <[email-masked]>
Date: Tue, 10 Nov 2020 12:26:49 +0000

Hi,
While any working group can register algorithms for COSE, I find it disappointing that nobody took 10 seconds to send an email to COSE before Göran did. I did not at all expect LWIG to standardize new curves and register them. When I reviewed the draft some time ago it only contained formulas to enable use of existing implementations. Ben sent an email to CFRG to a couple of month ago, but as the abstract has not been updated since the -00 version, I did not read it again.
- The draft tries to register a lot of low values (-1, -2, -9, -24, -48, -49) in the COSE registries which it obviously cannot as the draft is informational, and the registrations require standards action.
- If a new ECDSA25519 registration is needed for COSE, it should be needed for PKIX as well. My understanding is that ES256 and ecdsa-with-SHA256 are the same.
- I really do not want to repeat the mess with secp256r/prime256v1/P-256 where different SDOs standardized different names for the same curve.
- IETF curve definition and OID and IANA registrations of curve25519 in Weirstrass form should absolutely be coordinated with NIST. The last thing anybody want is two identifiers for the same curve, or even worse, two slightly different versions of curve25519 in Weirstrass form. Looking at draft-ietf-lwig-curve-representations-13 and NIST.SP.800-186-draft it looks like the y-coordinate of G is different for Wei25519 and W-25519...
Cheers,
John

From: Mohit Sethi M <mohit.m.sethi=[email-masked]>
Date: Tuesday, 10 November 2020 at 09:40
To: John Mattsson <[email-masked]>, Rene Struik <[email-masked]>, Göran Selander <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Lwip] [COSE] draft-ietf-lwig-curve-representations-13

Hi John,

--Mohit

Hi,

Cheers,
John

Hi Goran:

I hope this helps.

Best regards, Rene

Ref with hyperlinks:

Göran

COSE mailing list

--

Lwip mailing list

---

From: Mohit Sethi M <[email-masked]>
Date: Tue, 10 Nov 2020 13:52:20 +0000

Hi John,

These are all valid points and I am sure the authors will address them.

Regarding the process of IANA registrations, RFC 8126 (https://tools.ietf.org/html/rfc8126#section-5.2) notes:

   The designated expert is responsible for coordinating the appropriate
   review of an assignment request.

As you can see from the document history https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/history/ :

2020-10-20
12      Sabrina Tanamal IANA Experts State changed to Expert Reviews OK from Reviews assigned
2020-10-20
12      Sabrina Tanamal IANA Review state changed to IANA OK - Actions Needed from IANA - Not OK
2020-09-08
12      Sabrina Tanamal IANA Experts State changed to Reviews assigned
2020-09-08
12      (System)        IANA Review state changed to IANA - Not OK from IANA - Review Needed

we were made to believe that the registrations are OK. Göran is one of the designated experts for the COSE registries and has brought forward the potential issues to the COSE working group. So the process works (albeit its not perfect).

Your feedback asking us to better coordinate with the COSE working group is very much appreciated and we in LWIG will try to ensure this in the future.

--Mohit

On 11/10/20 2:26 PM, John Mattsson wrote:
Hi,

From: Mohit Sethi M <mohit.m.sethi=[email-masked]><mailto:mohit.m.sethi=[email-masked]>
Date: Tuesday, 10 November 2020 at 09:40
To: John Mattsson <[email-masked]><mailto:[email-masked]>, Rene Struik <[email-masked]><mailto:[email-masked]>, Göran Selander <[email-masked]><mailto:[email-masked]>, "[email-masked]"<mailto:[email-masked]> <[email-masked]><mailto:[email-masked]>, "[email-masked]"<mailto:[email-masked]> <[email-masked]><mailto:[email-masked]>
Subject: Re: [Lwip] [COSE] draft-ietf-lwig-curve-representations-13

Hi John,

--Mohit

Hi,

Cheers,
John

Hi Goran:

I hope this helps.

Best regards, Rene

Ref with hyperlinks:

Göran

COSE mailing list

--

Lwip mailing list