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

[Rene Struik <[e-mail]>]

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:
>
> 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 
> <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

> 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: 	[e-mail]
>> Reply-To: 	[e-mail]
>> To: 	[e-mail]
>> CC: 	[e-mail]
>>
>>
>>
>>
>> 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
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/lwip
>>
>> _______________________________________________
>> Lwip mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/lwip


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]