Subject: Re: [Lwip] Fwd: I-D Action: draft-ietf-lwig-curve-representations-04.txt

From: Mohit Sethi M <[email-masked]>
Date: Mon, 13 May 2019 11:46:57 +0000

Hi Rene,

In Section 1, the draft says:

 Montgomery curve, and of points of Edwards25519, a so-called twisted
   Edwards curve, which are both specified in [RFC7748<https://tools.ietf.org/html/rfc7748>]

What about referencing RFC 8032: https://tools.ietf.org/html/rfc8032?

A lot of normative parts are currently in the appendix. Wouldn't it make sense to move them into the actual document body. I looked at RFC 7748 for example and it defines Curve25519 in the main body: https://tools.ietf.org/html/rfc7748#section-6.1. It is good to keep the example computations in  Appendix E.3 and Appendix G.3, see Appendix K as the document currently does.

In Section 5, wouldn't it make sense to mention that while re-using the same code base has advantages, it can also negatively affect the performance in terms of the computation time?

--Mohit

On 4/19/19 5:50 PM, Rene Struik wrote:

Dear colleagues:

I slightly updated the draft. Main changes: (technical) I added COSE parm requests (Section8.4-8.6); (editorial) some tiny word-smything and addition of two more references.

Of course, more references are possible, but - apart from that - I think the document is technically ready.

FYI - Stanislav Smyshlyaev and Vasily Nikolaev did kindly review the previous version of this draft and verified all numbers, formulas, etc. Their main editorial comment was that the document could use more references. {I will see whether I can find more references, or perhaps I should see if I can post a full technical paper on all kinds of curve formulas,, tricks, etc. This will take some time, though. This should not stop proceeding with this, imho.}

Best regards, Rene

-------- Forwarded Message --------
Subject:        [Lwip] I-D Action: draft-ietf-lwig-curve-representations-04.txt
Date:   Fri, 19 Apr 2019 07:33:44 -0700
From:   [email-masked]<mailto:[email-masked]>
Reply-To:       [email-masked]<mailto:[email-masked]>
To:     [email-masked]<mailto:[email-masked]>
CC:     [email-masked]<mailto:[email-masked]>

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Light-Weight Implementation Guidance WG of the IETF.

Title : Alternative Elliptic Curve Representations
Author : Rene Struik
Filename : draft-ietf-lwig-curve-representations-04.txt
Pages : 61
Date : 2019-04-19

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.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-04
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-04

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-ietf-lwig-curve-representations-04

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

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

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

---

From: Rene Struik <[email-masked]>
Date: Mon, 13 May 2019 09:42:06 -0400

Hi Mohit:

Thanks for your comments. Please see my feedback below.

Best regards, Rene

On 5/13/2019 7:46 AM, Mohit Sethi M wrote:
>>     Edwards curve, which are both specified in [RFC7748  <https://tools.ietf.org/html/rfc7748>]
> What about referencing RFC 8032: https://tools.ietf.org/html/rfc8032 
> <https://tools.ietf.org/html/rfc8032>?

RS>> The draft does reference RFC 8032. However, the curve Edwards25519 
is specified in RFC 7748 (see Section 4.1, p. 4). Admittedly, the naming 
is somewhat confusing, since Edwards25519 refers to the curve and 
Ed25519 to the signature scheme (but the confusing naming already 
existed). <<RS

> A lot of normative parts are currently in the appendix. Wouldn't it 
> make sense to move them into the actual document body. I looked at RFC 
> 7748 for example and it defines Curve25519 in the main body: 
> https://tools.ietf.org/html/rfc7748#section-6.1 
> <https://tools.ietf.org/html/rfc7748#section-6.1>. It is good to keep 
> the example computations in  Appendix E.3 and Appendix G.3, see 
> Appendix K as the document currently does.
>
RS>> This may indeed be possible, although I do not see right away how 
much this buys. The main message of the draft is in Section 3 (which 
explains how switching between different representations works), and in 
Section 4 (which explains how this could be used to either reuse code or 
reuse already existing specifications); the remainder being just "knobs 
and bolts".

Virtually all the appendices is background material on curves, finite 
fields, mappings, representations, etc. (with the exception of Appendix 
E, G, H, and K -- which does the switching for Curve25519 "cousins").

Let me rethink the organizational suggestion. Main objective I would 
have is that is one were to produce another curve, say, "mohit2519" and 
use this to specify another key agreement scheme "m2519" or signature 
scheme "sethi2519", one could simply specify the domain parameters in 
Weierstrass form and the corresponding versions in Montgomery and 
Edwards form, and representations, all reusing definitions in the 
current draft, and be done with this as a 2-page document. (Reason why 
the draft has so many appendices is that I am not aware of any 
technical/academic paper that concisely describes this material [the 
draft arose from my desire to set the record straight here.)

As an example, the Russian schemes defined in [1], could be defined as 
instantiations of the current draft and existing generic signature and 
Diffie-Hellman schemes, in the following form:

#Russia:  [Cfrg] Curve Parameters for Russian standardization (Stanislav 
V. Smyshlyaev, January 30, 2015); RFC 7836 [1]
#classification: id-tc26-gost-3410-12-512-paramSetA; OID=1.2.643.7.1.2.1.2.1
namedcurve="RussiaWei512a"
type="Wei"
p=2^512-569; Fp=GF(p);
a=-3; 
b=12190580024266230156189424758340094075514844064736231252208772337825397464478540423418981074322718899427039088997221609947354520590448683948135300824418144
a=Fp(a); b=Fp(b); E=EllipticCurve(Fp,[a,b]);
h=1; 
n=13407807929942597099574024998205846127479365820592393377723561443721764030073449232318290585817636498049628612556596899500625279906416653993875474742293109
tr=97744483583712349266929640403245629889151353128602905529915952558174263790419;
Gx=Fp(3); 
Gy=Fp(6128567132159368375550676650534153371826708807906353132296049546866464545472607119134529221703336921516405107369028606191097747738367571924466694236795556);
G=E(Gx,Gy);
Zn=GF(n)

Ref: [1] RFC 7836 - Guidelines on the Cryptographic Algorithms to 
Accompany the Usage of Standards GOST R 34.10-2012 and GOST R 34.11-2012 
(March 2016)

<<RS

> In Section 5, wouldn't it make sense to mention that while re-using 
> the same code base has advantages, it can also negatively affect the 
> performance in terms of the computation time?
>
RS>> The main benefits of the curve model "switches" are (a) code reuse 
and (b) reuse of existing specification. As to code reuse, the 
computational effect depends on how one does accounting and whether or 
not one takes implementation attacks into account (see also Section 6, 
first para of p. 9).

FYI - Weierstrass curves and twisted Edwards curves have roughly the 
same "point doubling" cost, while the "point addition" costs are not 
that far off (in so-called mixed Jacobian coordinates, the ratio is 
~1.25) -- all in terms of finite field multiplications and finite field 
squarings (and counting naively). Since "point doubling" generally 
happens more frequently than "point addition", the overall cost 
differential is somewhere in the interval [1.00 - 1.25]. While the prime 
number shape may affect modular reduction cost and tilt the overall cost 
somewhat, I do not know of any public info on how real-world 
implementations really compare.

If you have any suggestion on how to do a fair computational cost 
comparison, please let me know. (Right now, I do not know how to do so, 
without only providing the naive finite field comparison above -- which 
could be misleading for real-world implementations, esp. with 
constrained devices without trusted hardware.)

<<RS

--Mohit

>> I slightly updated the draft. Main changes: (technical) I added COSE 
>> parm requests (Section8.4-8.6); (editorial) some tiny word-smything 
>> and addition of two more references.
>>
>> FYI - Stanislav Smyshlyaev and Vasily Nikolaev did kindly review the 
>> previous version of this draft and verified all numbers, formulas, 
>> etc. Their main editorial comment was that the document could use 
>> more references. {I will see whether I can find more references, or 
>> perhaps I should see if I can post a full technical paper on all 
>> kinds of curve formulas,, tricks, etc. This will take some time, 
>> though. This should not stop proceeding with this, imho.}
>>
>> Best regards, Rene
>>
>>
>>
>> Subject: 	[Lwip] I-D Action: 
>> draft-ietf-lwig-curve-representations-04.txt
>> From: 	[email-masked]
>> Reply-To: 	[email-masked]
>> To: 	[email-masked]
>> CC: 	[email-masked]
>>
>>
>>
>>
>> [email-masked]
>> [email-masked]

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

---

From: Rene Struik <[email-masked]>
Date: Mon, 13 May 2019 09:53:39 -0400

in my previous response, I referenced RFC 7836, but did not copy the 
correct snippet. This is corrected below. (It is only an illustration, 
so not that important. However, it should be correct, of course.). My 
apologies.

On 5/13/2019 9:42 AM, Rene Struik wrote:
> RS>> The draft does reference RFC 8032. However, the curve 
> Edwards25519 is specified in RFC 7748 (see Section 4.1, p. 4). 
> Admittedly, the naming is somewhat confusing, since Edwards25519 
> refers to the curve and Ed25519 to the signature scheme (but the 
> confusing naming already existed). <<RS
>
>> make sense to move them into the actual document body. I looked at 
>> RFC 7748 for example and it defines Curve25519 in the main body: 
> explains how switching between different representations works), and 
> in Section 4 (which explains how this could be used to either reuse 
> code or reuse already existing specifications); the remainder being 
> just "knobs and bolts".
>
> fields, mappings, representations, etc. (with the exception of 
> Appendix E, G, H, and K -- which does the switching for Curve25519 
> "cousins").
>
> have is that is one were to produce another curve, say, "mohit2519" 
> and use this to specify another key agreement scheme "m2519" or 
> signature scheme "sethi2519", one could simply specify the domain 
> parameters in Weierstrass form and the corresponding versions in 
> Montgomery and Edwards form, and representations, all reusing 
> definitions in the current draft, and be done with this as a 2-page 
> document. (Reason why the draft has so many appendices is that I am 
> not aware of any technical/academic paper that concisely describes 
> this material [the draft arose from my desire to set the record 
> straight here.)
>
> #Russia:  [Cfrg] Curve Parameters for Russian standardization 
> (Stanislav V. Smyshlyaev, January 30, 2015), RFC 7836 [1]
> #classification: id-tc26-gost-3410-2012-256-paramSetA; 
> OID=1.2.643.7.1.2.1.1.1
> namedcurve="RussiatEd256"
> type="tEd"
> p=2^256-617; Fp=GF(p)
> #Wei: aa=(3-A^2)/(3*B^2); bb=(2*A^3-9*A)/(27*B^3);
> aa=87789765485885808793369751294406841171614589925193456909855962166505018127157
> bb=18713751737015403763890503457318596560459867796169830279162511461744901002515
> GGx=Fp(65987350182584560790308640619586834712105545126269759365406768962453298326056)
> GGy=Fp(22855189202984962870421402504110399293152235382908105741749987405721320435292)
> aa=Fp(aa); bb=Fp(bb); E=EllipticCurve(Fp,[aa,bb]);
> #tEd:
> a=1
> d=2724414110474605931834268501164757645998726878473076809432604223414351675387
> a=Fp(a); d=Fp(d);
> Gx=Fp(13); 
> Gy=Fp(43779144989398987843428779166090436406934195821915183574454224403186176950503);
> #Mont: AA=2*(a+d)/(a-d); BB=4/(a-d);
> A=Fp(77708437198656856547901205427399062199001375716101406879613034791099442163334)
> B=Fp(77708437198656856547901205427399062199001375716101406879613034791099442163336)
> u=Fp(92146305408514047021764629781018839776217875356491594589642772615438293166627)
> v=Fp(24902344914088187528377430753722665806365988052905594051427533894712657880405)
> #common parms:
> h=4; 
> n=28948022309329048855892746252171976963338560298092253442512153408785530358887
> h1=4; 
> n1=28948022309329048855892746252171976963296432034728028577216638595171034460773
> tr=-84256526728449730591029627228991796228
> GG=E(GGx,GGy);
> Zn=GF(n)
>
> Accompany the Usage of Standards GOST R 34.10-2012 and GOST R 
> 34.11-2012 (March 2016)
>
> <<RS
>
> RS>> The main benefits of the curve model "switches" are (a) code 
> reuse and (b) reuse of existing specification. As to code reuse, the 
> ~1.25) -- all in terms of finite field multiplications and finite 
> field squarings (and counting naively). Since "point doubling" 
> generally happens more frequently than "point addition", the overall 
> cost differential is somewhere in the interval [1.00 - 1.25]. While 
> the prime number shape may affect modular reduction cost and tilt the 
> overall cost somewhat, I do not know of any public info on how 
> real-world implementations really compare.
>
> comparison, please let me know. (Right now, I do not know how to do 
> so, without only providing the naive finite field comparison above -- 
> which could be misleading for real-world implementations, esp. with 
> email:[email-masked]  | Skype: rstruik