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

[Daniel Migault <[e-mail]>]

Hi,

I expected to provide additional comments after the IETF but I happened to
be sick last week which explains the slow response. I apology for it.

The document seems to me very clear and nicely written.  This version
addresses my earlier comments.

Some nits:

In the Introduction

I think it would be nice to specify that the document provides guideline to
do similar work for 448 curves or if it also specifies Wei448.
>From the current text it seems not.

A nit the sentence "This document ... " is pretty long and it maybe would
be clearer to say "This document specifies Wei25519, an alternative ...."
but that is very personal ;-)

ECDSA25519 is also not mentioned at all in the introduction. It seems to me
important to position it briefly. More specifically, - at least this is my
understanding of it -  Wei25519 was motivated to enable the implementation
of Montgomery curve Curve25519 operations, re-using implementations for the
NIST curves while ECDSA25519 enables the implementation of ECDSA
with Montgomery curve Curve25519. This seems to me slightly different.

just before section 10.2.1:  s/scheme scheme/scheme

I have the impression section 4.1 - 4.4 are more than Examples ;-)

Yours,
Daniel

On Mon, Jul 20, 2020 at 9:54 AM Daniel Migault <daniel.migault=
[e-mail]> wrote:

> Hi Rene,
>
> Thank you for the feed back - I am just back from vacation. As far as I
> remember, my comments mostly concerned some clarifications and should not
> be seen as preventing the document to move forward - especially for an
> early review. I did appreciated the way you handled the comments and
> believe your are the best person to  know and decide how to handle these
> comments.
>
> I have not reviewed the latest version, but I can commit to review the
> draft in August. I hope that does not prevent the document to be moved
> forward.
>
> Yours,
> Daniel
> ------------------------------
> *From:* Rene Struik <[e-mail]>
> *Sent:* Tuesday, July 14, 2020 1:43 PM
> *To:* Daniel Migault <[e-mail]>; Iot-dir@ietf..org <
> [e-mail]>
> *Cc:* [e-mail] <[e-mail]>;
> [e-mail] <
> [e-mail]>
> *Subject:* Re: Iotdir early review of
> draft-ietf-lwig-curve-representations-08
>
> Hi Daniel:
>
> It has been a while that you provided your early IoTDir review comments. I
> do not know whether such early reviews are a gate keeper for sealing off
> the lwig curve draft. Nevertheless, it may be good to know if you are
> reasonably happy for this to move forward.
>
> For some details on how I tried to take your comments into account, please
> see my March 10th email below, where the mailing list link is
> https://mailarchive.ietf.org/arch/msg/lwip/KbJDWtpenYPNDuzVI05ZR4XGLhY/
>
> For the current draft, see
> https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/
>
> I am looking forward hearing back from you..
>
> Best regards, Rene
>
> On 2020-03-10 12:01 p.m., Rene Struik wrote:
>
> Hi Daniel:
>
> I tried to take into account your comments with
> draft-ietf-lwig-curve-representations-09.
>
> I will send out a separate email to the list highlighting main changes.
>
> Below, I will explain how I tried and accommodate your previous comments
> on the 08-draft, now that the new draft is out.
>
> Important note:
> Based on offline communications with SecDir people, I did include
> Curve448-related material with the 09 version. I tried to do this in a way
> that would create the least editorial upheaval and would not take away from
> the main objectives of the document: to this end, I only introduced
> Curve448-related material in Section 4.4 [thereby avoiding having to
> sprinkle in curve448-related language in each section and blurring the
> message of the document]. The only other sections where Curve448 plays a
> role is IANA Section 10 and the appendices that give the parameters and
> test vectors for the Curve448 family members. {Note: I probably should have
> added a note on ECDSA448 in the security consideration section, though (I
> made a note on this and will fix).}
>
> On 10/25/2019 4:26 PM, Rene Struik wrote:
>
> 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
>
> On 10/25/2019 2:38 PM, Daniel Migault via Datatracker wrote:
>
> 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>
>
> RS>> Elliptic-curve and Finite Field-related notation is introduced in
> Annex B, see
> https://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
>
> RS1>> I did revisit notational convention, also based on reviewing the
> draft NIST SP 800-186 and draft FIPS Pub 186-5 documents (out for public
> review Oct 31, 2019 till Jan 29, 2020; closed now). Based on this, I
> slightly edited Appendix B (backgrounder on curve terminology and finite
> fields). I did decide not to align with some recent cfrg notation, since -
> frankly - I believe it is a mess and the only outlier w.r.t. ANSI, NIST,
> SECG,and BSI specs. <<RS1
>
> 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>
>
> 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
> <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
> <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
>
> RS1>> I kept the language as is, based on assessment above. <<RS1
>
>    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>
>
> 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
>
> RS1>> I tried and accommodate this with the following text in Section 4.3
> (with [...] deleted from this email):
>
> FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and can
> be instantiated not just with the NIST prime curves, but also with other
> Weierstrass curves (that satisfy additional cryptographic criteria). In
> particular, one can instantiate this scheme with the Weierstrass curve
> Wei25519 and the hash function SHA-256 [FIPS-180-4], [...]
>
> We denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with
> curve Wei25519, where the signature (r,s) is represented as the
> right-concatenation of the integers r and s, each represented as fixed-size
> strings with tight MSB/msb ordering (see Appendix I).
>
> <<RS1
>
> 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>
>
> RS1>>  I reflected on this and investigated the impact on the integrity
> and editorial cohesion of the document. Main problem with moving the actual
> domain parameters of Wei25519 to the main body is that one still would have
> to understand where these come from, thereby requiring a look at the
> mappings from Montgomery to Weierstrass curves and vice-versa (Annex D),
> their instantiation in this particular case (Annex E), where for isogenies
> one would have to delve into Annex F (general informative text) and Annex G
> (instantiation in this particular case). With the added Curve448-related
> material, this would become even messier, esp. since - in Annex M.3 - I had
> to add a note that some parameters in RFC7748 and some mappings in there
> are actually incorrect. Since the main body focuses on benefit of switching
> between different curve models, even if one does not care about a
> particular curve in question, I thought it best to stick to emphasizing
> that point (see Section 3 - Use of Representation Switches) and not drive
> potential readers away with long parameter lists and minutiae in the main
> body. If there is one thing I would like to stick with readers of the
> draft, it is how representation switches work in general and how these
> could help in code reuse of specification reuse.
>
> <<RS1
>
> 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>
>
> RS1>> Agreed. However, lots of variables already have a connotation, so
> sticking to l (length or degree) seemed best. <<RS1
>
>    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>
>
> 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
> <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
>
> RS1>> If you feel I should add more than I did with rev-09 already, please
> let me know and I can sprinkle this in. <<RS1
>
> 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>
>
> RS1>> I kept the header "examples" in (sorry), since these are examples of
> how representation switches can be used to define what in Section 4.4 I
> call "offspring protocols". That is only a section heading, though. <<RS1
>
> 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>
>
> 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
>
> RS1>> As explained above. <<RS1
>
>    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.
>
>
>
>
> --
> email: [e-mail] | Skype: rstruik
> cell: [phone] | US: [phone]
>
>
> --
> email: [e-mail] | Skype: rstruik
> cell: [phone] | US: [phone]
>
>
> --
> email: [e-mail] | Skype: rstruik
> cell: [phone] | US: [phone]
>
> _______________________________________________
> Lwip mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/lwip
>


-- 
Daniel Migault
Ericsson