Subject: [Lwip] Iotdir early review of draft-ietf-lwig-curve-representations-08

From: Daniel Migault via Datatracker <[email-masked]>
Date: Fri, 25 Oct 2019 11:38:07 -0700

Reviewer: Daniel Migault
Review result: Almost Ready

Hi,

I have reviewed this document as part of the IoT directorate's
ongoing effort to review all IETF documents being processed by the
IESG.  These comments were written primarily for the benefit of the
internet area directors.  Document editors and WG chairs should treat
these comments just like any other last call comments.

The summary of the review is Almost Ready

Overall I believe the document is well written with a lot of useful
information. Though I have not carefully reviewed the annexes, I believe the
document could be re-organized to  provide more implementation details of
Wei25519 and its potentially the implementation of the isogeny between
Wei25519.-3 and Wei25519. Note that the latest point may depend on the
implementation status of NIST curves.

Please find my review, which I hope will help to move the document to be moved
forward.

Yours,
Daniel

Abstract

   This document specifies how to represent Montgomery curves and
   (twisted) Edwards curves as curves in short-Weierstrass form and
   illustrates how this can be used to carry out elliptic curve
   computations using existing implementations of, e.g., ECDSA and ECDH
   using NIST prime curves.

<mglt>
Overall I have the impression the document's intent is to define Wei25519 for
COSE. The current document is very well documented and nicely written on the
generic methodology used, that is using the Weierstrass models of curves using
other models that is in our case twisted-Edward/Montgomery curves. My reading
of the document is that it might benefit by being re-focused on Wei25519 and
provide the necessary details in the main body - that is not the annex to
implement: * Wei25519 - the domains parameters * the isogeny between
Wei25519.-3 and Wei25519 - as this is necessary for reusing NIST curve
implementation when a hard coded. That said, this depends on the implementation
status of NIST curves and may be left in the annex.

Specification is sufficient to assign code points which is sufficient with an
Informational status.

I would even have Wei25519 in the title. In my opinion the title is too generic
and the scope should be narrow down a bit. </mglt>

<mglt>
The document introduces some notations, I believe these notations should be
specified, and maybe use the same notation as RFC7748, if possible to avoid
that we have one notation per document. </mglt>

1.  Fostering Code Reuse with New Elliptic Curves

   It is well-known that elliptic curves can be represented using
   different curve models.

<mglt>
nits: It might be preferred to remain factual and simply say "Elliptic curves
can be represented using different models." </mglt>

   Recently, IETF standardized elliptic curves
   that are claimed to have better performance and improved robustness
   against "real world" attacks than curves represented in the
   traditional "short" Weierstrass model.

<mglt>
Not being a native english speaker, the sentence above may lead the reader to
think that Weierstrass representation is one reason for less robustness and
performance. If that were the case, the reader may wonder why do we want to
move to that representation.

I believe that before Montgomery or Edwards curves have been introduced curves
with Weierstrass model were widely deployed and implemented. </mglt>

   This document specifies an
   alternative representation of points of Curve25519, a so-called
   Montgomery curve, and of points of Edwards25519, a so-called twisted
   Edwards curve, which are both specified in [RFC7748], as points of a
   specific so-called "short" Weierstrass curve, called Wei25519.  We
   also define how to efficiently switch between these different
   representations.

<mglt>
I understand the switch can be performed in two ways, it might help the reader
to distinguish two scenario one with a being a parameter and one with a being
hard coded.

We may also briefly expose why Curve25519 cannot be "proxied" by Ed-to-Wei
followed by Wei25519. In which case Wei25519 would be an implementation detail.
This would justify the need to add code points for Wei25519. </mglt>

   Use of Wei25519 allows easy definition of new signature schemes and
   key agreement schemes already specified for traditional NIST prime
   curves, thereby allowing easy integration with existing
   specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4
   [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and fostering code
   reuse on platforms that already implement some of these schemes using
   elliptic curve arithmetic for curves in "short" Weierstrass form (see
   Appendix C.1).

<mglt>
Not being a cryptographer at all. I am wondering if the definition of "new"
signature scheme is correct. At least it sounds a dangerous slope. I think the
text wants to say it allows to re-use signature scheme defines for the NIST
curves using another curves Wei25519, namely ECDSA in our case. </mglt>

2.  Specification of Wei25519

   For the specification of Wei25519 and its relationship to Curve25519
   and Edwards25519, see Appendix E.

<mglt>
If we are defining Wei25519, it seems that at least the definition of Wei25519
needs to be part of the main draft. A deep explanation as well as other
information may be left in the annexe. I would thus probably recommend to add
the necessary domain parameters that are needed to instantiate Wei25519. </mglt>

   For further details and background
   information on elliptic curves, we refer to the other appendices.

   The use of Wei25519 allows reuse of existing generic code that
   implements short-Weierstrass curves, such as the NIST curve P-256, to
   also implement the CFRG curves Curve25519 and Edwards25519.  We also
   cater to reusing of existing code where some domain parameters may
   have been hardcoded, thereby widening the scope of applicability.  To
   this end, we specify the short-Weierstrass curves Wei25519.2 and
   Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p),
   respectively; see Appendix G.  (Here, p is the characteristic of the
   field over which these curves are defined.)

<mglt>
The text needs here a bit more more explanations. As I understood, we are not
simply changing the representation but also considering the constraint of the
NIST curves implementations. My understanding is that NIST curves have hard
coded a=-3, so we need to work around this with the isogeny. The construction
is, in my opinion, a bit different from what simple isomorphism. It might also
be good to have that overview stated in the introduction section.

Annexes are good, but the necessary information for an implementation may be
moved up to the main body.

</mglt>

3.  Use of Representation Switches

   The curve Wei25519.-3 (which has hardcoded domain parameter a=-3 (mod
   p)) is not isomorphic to the curve Wei25519, but is related in a
   slightly weaker sense: the curve Wei25519 is isogenous to the curve
   Wei25519.-3, where the mapping of Appendix G.2 is an isogeny of
   degree l=47 that maps the specified base point G of Wei25519 to the
   specified base point G' of Wei25519.-3 and where the so-called dual
   isogeny (which maps Wei25519.-3 to Wei25519) has the same degree
   l=47, but does not map G' to G, but to a fixed multiple hereof, where
   this multiple is l=47.  Consequently, a public-private key pair
   (k,R:=k*G) for Wei25519 corresponds to the public-private key pair
   (k, R':= k*G') for Wei25519.-3 (via the l-isogeny), whereas the
   public-private key pair (k, R':=k*G') corresponds to the public-
   private key pair (l*k, l*R=l*k*G) of Wei25519 (via the dual isogeny).
   (Note the extra scalar l=47 here.)

<mglt>
This is just a comment that ascii does not help reading 1=47... but there is no
much we can do. </mglt>

   Alternative curve representations can, therefore, be used in any
   cryptographic scheme that involves computations on public-private key
   pairs, where implementations may carry out computations on the
   corresponding object for the isomorphic or isogenous curve and
   convert the results back to the original curve (where, in case this
   involves an l-isogeny, one has to take into account the factor l).
   This includes use with elliptic-curve based signature schemes and key
   agreement and key transport schemes.

<mglt>I believe we should specify somewhere that changing the representation
does not ease the ECDLP for a given prime/curve</mglt>

4.  Examples

<mglt>
I do not believe these are example regarding the focus of the document. Of
course, the document could be more generic, but here we focus on 25519, so I
would rename Example as Implementation. Or move subsection to one level, that
is 4.1 -> 4. 4.2->5... </mglt>

8.  Security Considerations

   Elliptic curves are generally used as objects in a broader
   cryptographic scheme that may include processing steps that depend on
   the representation conventions used (such as with, e.g., key
   derivation following key establishment).  These schemes should
   (obviously) unambiguously specify fixed representations of each input
   and output (e.g., representing each elliptic curve point always in
   short-Weierstrass form and in uncompressed tight MSB/msb format).

<mglt>
I think it might be worth mentioning here that while the scheme used in this
document may be applied for other curves that 25519, not all modules are
isomorphic to Weierstrass. In addition not all Weierstrass representation can
be switched to a Montgomery representation. </mglt>

   To prevent cross-protocol attacks, private keys SHOULD only be used
   with one cryptographic scheme.  Private keys MUST NOT be reused
   between Ed25519 (as specified in [RFC8032]) and ECDSA25519 (as
   specified in Section 4.3).

   To prevent intra-protocol cross-instantiation attacks, ephemeral
   private keys MUST NOT be reused between instantiations of ECDSA25519.

---

From: Rene Struik <[email-masked]>
Date: Fri, 25 Oct 2019 16:26:13 -0400

Hi Daniel:

Thanks very much for your constructive review.

I provided brief feedback on some of your comments - see below (RS>> 
<<RS). Where I did not provide a comment yet, I will reflect on these 
later (and this may benefit from looking at the results from the pending 
SecDir review, once ready, at the same time).

Best regards, Rene

> that we have one notation per document. </mglt>

RS>> Elliptic-curve and Finite Field-related notation is introduced in 
Annex B, 
seehttps://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.appendix.B

This notation is well-aligned with conventions in ANSI, NIST, SECG, and 
BSI specifications. It is also in line with RFC 6090.

<<RS

> with Weierstrass model were widely deployed and implemented. </mglt>

RS>>  The reason to use the word "claimed" is that, from my perspective, 
it is unclear that the claim actually holds. {My opinion on the matter 
is irrelevant for this document, though.}

As to performance, this depends on implementation details, see, e.g., 
remarks on existing hardware implementations (see the forelast para of 
https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.section.6). 
As to robustness, see the second para of 
https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.section.8). 
As to different perspectives on performance vs. robustness, see also 
Item 1.3b of p. 77 of 
https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf. 
<https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf>

To my knowledge, Weierstrass curves, such as the NIST prime curves are 
still very much prevalent to-date (so "were widely deployed" is probably 
something that actually still is).

<<RS

> curves using another curves Wei25519, namely ECDSA in our case. </mglt>
RS>> New refers to a new instantiation, e.g., ECDSA with the Wei25519 
curve simply defines a new curve to be used with an existing generically 
specified ECDSA specification. <<RS
> does not ease the ECDLP for a given prime/curve</mglt>

RS>> This is a good observation. I captured this generally in the 
Security Considerations section (see first para of 
https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.section.8) 
and also reminded the reader of this when introducing each isomorphism 
discussed in the document. See 
https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.appendix.D, 
<https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.appendix.D> 
where I added this remark for the isomorphic mapping from twisted 
Edwards to Montgomey (Annex D.1, end of first para), Montgomery to 
Weierstrass (Annex D.2, end of first para). I did not repeat this for 
the twisted Edwards to Weierstrass mapping (Annex D.3) or with the 
low-degree isogenies (Annex F), but could certainly sprinkle this in 
there as well, if so desired.

<<RS

> be switched to a Montgomery representation. </mglt>

RS>> As you suggested above, not all curves can be expressed in Montgomery or twisted Edwards format (see also the 6th para of Appendix B.1:https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.appendix.B.1). This being said, all [non-binary] curves *are* isomorphic to one in short-Weierstrass format, so that the short-Weierstrass format can be thought of as a "catch all" representation format.
<<RS

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

---

From: Suresh Krishnan <[email-masked]>
Date: Fri, 25 Oct 2019 21:06:08 +0000

Thank you very much for the review Daniel. Greatly appreciated. I see that Rene has sent a partial response pending the Sec Dir review. I will add you into the loop when that comes in.

Regards
Suresh

> On Oct 25, 2019, at 2:38 PM, Daniel Migault via Datatracker <[email-masked]> wrote:
> 
> Reviewer: Daniel Migault

---

From: Daniel Migault <[email-masked]>
Date: Fri, 25 Oct 2019 20:32:49 -0400

Thanks for the brief feed back. Just as a side comment, when I am
suggesting some more information, I usually do not mean the information is
missing in the draft. I think the draft is pretty complete. It should be
taken as "while reading, I would have liked this information here", so just
take this as an indication. I am happy to review the next versions.

Regarding the notation, you are right, for some reason I thought that the
traditional way was to use G[a], but that does not seem correct, so that is
my mistake.

Yours,
Daniel

On Fri, Oct 25, 2019 at 4:26 PM Rene Struik <[email-masked]> wrote:

> <<RS). Where I did not provide a comment yet, I will reflect on these later
> (and this may benefit from looking at the results from the pending SecDir
> review, once ready, at the same time).
>
> Best regards, Rene
>
> Annex B, see
> https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.appendix.B
>
> it is unclear that the claim actually holds. {My opinion on the matter is
> irrelevant for this document, though.}
>
> As to different perspectives on performance vs. robustness, see also Item
> 1.3b of p. 77 of
> RS>> This is a good observation. I captured this generally in the Security
> Considerations section (see first para of
> where I added this remark for the isomorphic mapping from twisted Edwards
> to Montgomey (Annex D.1, end of first para), Montgomery to Weierstrass
> (Annex D.2, end of first para). I did not repeat this for the twisted
> Edwards to Weierstrass mapping (Annex D.3) or with the low-degree isogenies
> (Annex F), but could certainly sprinkle this in there as well, if so
> desired.
>
> <<RS
>
> 4.  Examples
>
> <mglt>
> RS>> As you suggested above, not all curves can be expressed in Montgomery or twisted Edwards format (see also the 6th para of Appendix B.1: https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-08.html#rfc.appendix.B.1). This being said, all [non-binary] curves *are* isomorphic to one in short-Weierstrass format, so that the short-Weierstrass format can be thought of as a "catch all" representation format.
> <<RS
>
> _______________________________________________
> Lwip mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lwip
>

---

From: "Chakrabarti, Samita" <[email-masked]>
Date: Mon, 28 Oct 2019 12:24:22 -0400

Hi Daniel,
Your review of the document is very much appreciated in order to move this
draft forward!
Since you already provided the review, please close the review request
assignment as completed.

Best regards,
-Samita

On Fri, Oct 25, 2019 at 2:38 PM Daniel Migault via Datatracker <
[email-masked]> wrote:

> IoT-DIR mailing list
> [email-masked]
> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_iot-2Ddir&d=DwICAg&c=udBTRvFvXC5Dhqg7UHpJlPps3mZ3LRxpb6__0PomBTQ&r=pWMzx7FsqijEJPyfMBfn-HJss-wVVTf0K5y-cxCTXL8&m=R9xgGynpGpZuri6EHdEishW9HbS2jbstDEFk6i38v8w&s=H5LPk8KFQpEY0jiHVeVBFFvDXAG_39OKXhO_tyizQUg&e=
>