[Lwip] Fwd: (initial triage - final disposition with rev-02) Re: Fwd: Review of draft-ietf-lwig-curve-representations-00 by crypto review panel

Rene Struik <rstruik.ext@gmail.com> Tue, 11 December 2018 14:43 UTC

Return-Path: <rstruik.ext@gmail.com>
X-Original-To: lwip@ietfa.amsl.com
Delivered-To: lwip@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 9366B126F72 for <lwip@ietfa.amsl.com>; Tue, 11 Dec 2018 06:43:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id euR7hX67Qq1d for <lwip@ietfa.amsl.com>; Tue, 11 Dec 2018 06:42:57 -0800 (PST)
Received: from mail-it1-x12c.google.com (mail-it1-x12c.google.com [IPv6:2607:f8b0:4864:20::12c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5F8E8124BF6 for <lwip@ietf.org>; Tue, 11 Dec 2018 06:42:57 -0800 (PST)
Received: by mail-it1-x12c.google.com with SMTP id h193so4115548ita.5 for <lwip@ietf.org>; Tue, 11 Dec 2018 06:42:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:references:to:from:message-id:date:user-agent:mime-version :in-reply-to:content-language; bh=EdVsITVQCmeA4yU9cFs/zrSFhtBCZ3jvdVCGLZr9BpM=; b=I8G3YaaoCube7mqfaxI/pv56PIAc6y6FfU2odl43wXxGcZBb0i51eQMUYyme4TCBvZ Mu3uP5Oqs95IfTE7DZlZU3/TbcbiHphRpmQ1Qdq6wUtvWlIt31XijaFAggpR+FSB2DRX M3EzmcZQjzGBP+UU5aW8M10UzYwn0JI3dcWhslKZJ13Ytew+uR2yLYxlVRaS3Jd2Jhpf Wh91ydGF605Qc+b91vo4so7JIXQLLQHiDrxKHFqBddSw62c4hRtq19ElEisgeR167zNb y2+XXiIlDs94M1fsvFSSA5xYD6BaUPItqDYn1+6tzhnBNgfpo3HQ6JCmoMUkKXQ83Pkq +jOQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:references:to:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=EdVsITVQCmeA4yU9cFs/zrSFhtBCZ3jvdVCGLZr9BpM=; b=jmjrURZfDJyWSz5gMj4gn1j9XNl+4VqZNjeqHTjWOdGYI1gsDcrCnQ1mgEf3iBL7Fa R1eELymN+wxhjTKlr6jRrkvdlz8E9XVCBRXA/Wof+gCImvx0kPRft9Y2xwl1YfDmt5/F qSAFJDkIcYsjS51mXjHisTaFIg2LciE2WDPIOK+R/P0t7VwkrVG7zzIOSHU66YpKN9NR LJes1rm4NycWGQPZCnk8pFxwpwhEhTetkBtlh04f7Sy0TX73WdiFtUe0a5ssRjIw/Fnf ZA1SgAo1YRu5u0NMj349F4Ssgf4uDNF1Qn/S2QyEerBtK/opLIxwl6Jjx+eN+IXwt6JB p1vg==
X-Gm-Message-State: AA+aEWYYELGwQV77T9euB6c4Ehtha8jpYDloPQUXv9UWJDr7GIGrlyDW Df3ZQPQPkqQShhvf3Db63lG5RWTv
X-Google-Smtp-Source: AFSGD/VzQvpiQOslFOYiMEUf14LPLpM+qaiIiIs+1BI1FVvyq2aHiRXrjqrpAk5HQs0EcedAcQlHOA==
X-Received: by 2002:a05:660c:250:: with SMTP id t16mr2283457itk.78.1544539376404; Tue, 11 Dec 2018 06:42:56 -0800 (PST)
Received: from ?IPv6:2607:fea8:69f:f5eb:fc5f:12b:d173:619a? ([2607:fea8:69f:f5eb:fc5f:12b:d173:619a]) by smtp.gmail.com with ESMTPSA id 81sm1358407itz.15.2018. for <lwip@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 11 Dec 2018 06:42:55 -0800 (PST)
References: <43616fce-d62a-f663-1feb-778e556b0676@gmail.com>
To: "lwip@ietf.org" <lwip@ietf.org>
From: Rene Struik <rstruik.ext@gmail.com>
X-Forwarded-Message-Id: <43616fce-d62a-f663-1feb-778e556b0676@gmail.com>
Message-ID: <6d81297f-6da9-98f2-3ef4-5ca1354d4048@gmail.com>
Date: Tue, 11 Dec 2018 09:42:53 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.3.3
MIME-Version: 1.0
In-Reply-To: <43616fce-d62a-f663-1feb-778e556b0676@gmail.com>
Content-Type: multipart/alternative; boundary="------------5570C2744FEDAF6B2C8F65A9"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/lwip/60_NLbxk4m_Y5r-_z67JsrU40z4>
Subject: [Lwip] Fwd: (initial triage - final disposition with rev-02) Re: Fwd: Review of draft-ietf-lwig-curve-representations-00 by crypto review panel
X-BeenThere: lwip@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Lightweight IP stack. Official mailing list for IETF LWIG Working Group." <lwip.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/lwip>, <mailto:lwip-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/lwip/>
List-Post: <mailto:lwip@ietf.org>
List-Help: <mailto:lwip-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/lwip>, <mailto:lwip-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 11 Dec 2018 14:43:01 -0000

Now to mailing address "lwip@ietf.org". (I do not understand why "LWIG" 
has an "lwip" mailing address.)

-------- Forwarded Message --------
Subject: 	(initial triage - final disposition with rev-02) Re: Fwd: 
Review of draft-ietf-lwig-curve-representations-00 by crypto review panel
Date: 	Tue, 11 Dec 2018 09:36:53 -0500
From: 	Rene Struik <rstruik.ext@gmail.com>
To: 	Mohit Sethi M <mohit.m.sethi@ericsson.com>, smyshsv@gmail.com 
<smyshsv@gmail.com>, lwig@ietf.org

Hi Stanislav:

Thanks for your review.

Some brief initial feedback now; final disposition will be with rev02. 
(One my "to dos prior to 2018-end" is to add test vectors to a draft-02 
version that I have had on my machine since Nov 15th. That version also 
includes some minor editorial massaging.)

BTW - all calculations (including isogenies) were done in Sage and 
write-up is based on an extensive LaTeX document with curve 
constructions for personal use. I will double-check everything prior to 
releasing rev-02.

On 12/11/2018 7:46 AM, Mohit Sethi M wrote:
> Hi all,
> We have received the following detailed review of 
> draft-ietf-lwig-curve-representations from Stanislav Smyshlyaev on 
> behalf of the Crypto Review Panel.
> Thank you Stanislav for the excellent review. It would be great if the 
> authors can address his feedback and submit a new version.
> Please feel free to chime in if you have any additional feedback on 
> this document at this stage.
> Zhen and Mohit
> -------- Forwarded Message --------
> Subject: 	Review of draft-ietf-lwig-curve-representations-00 by crypto 
> review panel
> Date: 	Tue, 11 Dec 2018 07:50:11 +0200
> From: 	Stanislav V. Smyshlyaev <smyshsv@gmail.com>
> To: 	Mohit Sethi M <mohit.m.sethi@ericsson.com>, Suresh@kaloom.com 
> <Suresh@kaloom.com>, zhencao.ietf@gmail.com <zhencao.ietf@gmail.com>, 
> Alexey Melnikov <aamelnikov@fastmail.fm>
> Good afternoon,
> Please find below the review of the document made on behalf of Crypto 
> Review Panel.
> I'll be happy to discuss all questions raised in the review directly 
> via e-mail: smyshsv@gmail.com <mailto:smyshsv@gmail.com>
> Document: draft-ietf-lwig-curve-representations-00
> Reviewer: Stanislav Smyshlyaev
> Review Date: 2018-11-26
> Summary: Revision needed
> The document “Alternative Elliptic Curve Representations” contains 
> procedures and formulae of representing Montgomery curves and 
> (twisted) Edwards curves in short Weierstrass form.
> The reviewer believes that the document is very helpful and can be 
> used by developers implementing ECC operations in real-world 
> applications.
> The reviewer has verified all decimal numbers (and hexadecimal 
> numbers, where they are provided in the draft) and does not have any 
> concerns besides the following ones.
> Since some of the concerns seem to be important enough for the overall 
> document, the reviewer recommends to send an updated version of the 
> draft to Crypto Review Panel for a new review.
> The review was made for draft-ietf-lwig-curve-representations-00. 
> During the review process an updated version 
> draft-ietf-lwig-curve-representations-01 was published – some comments 
> about the -01 version can be found in the end of the current review.
> Comments:
> 1) Section C.2: The mapping from Weierstrass curves to Montgomery 
> curves is not defined in the current version. The mapping from 
> Weierstrass to Montgomery cannot usually be described as shortly as 
> others, but maybe it could still be useful here. For example, the root 
> of x^3+ax+b in Fp could be provided explicitly.

RS>> True: although I am not sure how useful this is, this could be 
done. One of the issues is that a Weierstrass curves with a point of 
order two does not automatically lead to a Montgomery curve. Having to 
spell out those conditions may make life really hard for non-specialists 
and obscure the main message. My main point was to try and exemplify how 
the different curve models are sometimes the "same animal, in disguise", 
which could be helpful, e.g., when implementing Ed25519 and Curve225519 
on a small device or when one wishes to reuse an existing HW 
implementation of short Weierstrass curves. <<RS

> 2) It would be better to stress in Appendix C.1 that formulae provided 
> there do not allow to get parameter a of the twisted Edwards 
> curve equal to 1 or -1. In Appendix D.2 additional constant c is used 
> that helps to obtain the curve with a equal to -1 (this fact by the 
> way implies that the phrase “Here, we used the mapping of Appendix 
> C.1” is inaccurate).
RS>> I did indeed use the isomorphism from E{a,d} to E_{1,d/a}, for a a 
square in GF(q), as well.<<RS
> 2a) Section D.2: The formulae (u,v) -> (c*u/v, (u-1)/(u+1)) lead to an 
> error. It is not clear why it is needed to multiply by the constant c.
RS>> Hmm. I copied this from LaTeX source based on checked Sage 
calculations. I will double check all of this once more (also 
elsewhere). <<RS
> 2b) Section D.3: The Montgomery curve Curve25519 doesn’t correspond to 
> Twisted Edwards curve Edwards25519 because of (A+2)/B = (486662+2)/1 
> != -1.
RS>> It does correspond to this, since I added the "c" multiplication in 
the x-coordinate, since c^2=-(A+2)/B. See your point under your point 2) 
above. <<RS
> 2c) If one uses the formula from C.1 for Montgomery to Edwards mapping 
> (a:=(A+2)/B and d:=(A-2)/B), she obtains that d for Edwards25519 is 
> equal to 486660 but not the value of d which is provided in D.3.
RS>> It does correspond to this, for the same reason as above under your 
point 2b) above. <<RS
> 3) Section E.1: The isomorphic mapping between W_{a,b} and W_{a',b'} 
> should be defined as a’:=a*s^4 and b’:=b*s^6, instead of a:=a'*s^4 and 
> b:=b'*s^6. Otherwise the mapping is defined incorrectly and the test 
> vectors from F.3 are incorrect.
RS>> This is often confusing (initially also to me). However, I do think 
this is correct, but will of course double check my Sage code.<<RS
> 4) It seems that the formula for lambda in case Q:=2P for Montgomery 
> curve is wrong. According to 
> http://hyperelliptic.org/EFD/g1p/auto-montgom.html and to 
> https://eprint.iacr.org/2017/212.pdf (page 4) it should be: lambda = 
> (3*x1^2 + 2*A*x1 + 1)/(2*B*y1). So you need to add “B” as a factor in 
> the denominator.
RS>> This small editorial glitch was corrected in version 01. <<RS
> 5) in Appendix D.2 it would be better to stress explicitly that we 
> work with projective coordinates, otherwise the formulae do not have 
> to be correct.

RS>>I did separate out the points of order one and two to make the 
rational mappings always work. Did I miss something here? <<RS

> Editorial comments:
> a) It seems that the text will be easier to read if the formulae for 
> group law are provided in the following form (for example, for 
> Weierstrass):
>    x = lambda^2 – x1 – x2
>    y = lambda * ... (at a new line, but with “and”)
>    lambda = ... (again at a new line)
> b) In reviewer’s opinion, the text will be easier to read if different 
> symbols for coordinates of different forms of a curve are used. For 
> example, (x,y) for Weierstrass, (X,Y) for Montgomery and (u,v) for 
> Edwards. And it would be better to use the same symbols in different 
> parts of the document (now (u,v) is used for Montgomery in A.2 and 
> (x,y) for Montgomery in B.2).
RS>> Agreed. I will do this for version 02. <<RS
> c) The term “short Weierstrass form” is widely used in publications as 
> is. The draft, however, has two variants of it – “short” Weierstrass 
> form and short-Weierstrass form. It seems that one (commonly used) 
> variant would be better to use.
> d) The reviewer recommends to use only “GF(p)” everywhere in document 
> instead of “GF(q)” together with “GF(p)”. For example, now in C.1 – 
> GF(q) and GF(p) in D.1.
RS>> I would like to keep this as is, just in case at some point in the 
future, someone wishes to specify a curve over GF(q), where q=p^2, for 
example (whether this is FourQ or a curve used for isogeny-based key 
agreement. <<RS
> Additional clarifications might be useful:
> Also the reviewer believes that it will be useful to write additional 
> clarifications in D.2 on “can be implemented via integer-only 
> arithmetic as a shift of (p+A)/3 for the isomorphic mapping and a 
> shift of -(p+A)/3 for its inverse” regarding the need of using the mod 
> operation for transformation.
RS>> If I parse this comment correctly: indeed one may need to add or 
subtract the modulus p (but does not need to implement GF(p) arithmetic 
otherwise for this conversion). <<RS
> ###### draft-ietf-lwig-curve-representations-01:
> The concerns 1, 2, 2a, 2b, 2c, 4 and 5 for 00 version are still valid 
> for version -01. The concern 3 has been addressed.
> Additional question for draft-ietf-lwig-curve-representations-01: 
> appendices C.1 and C.2 contain information about properties that help 
> to recover y-coordinates of a multiple point if one uses Montgomery 
> ladder. This information may not be needed in the draft, since the 
> ladder itself is not described there.

RS>> I do think the recovery of the y-coordinate is useful, e.g., if one 
wishes to implement Ed25519 using an extension of the Montgomery ladder 
for Curve25519 (Example 4.2 in rev-01 document). This could be 
especially useful for constrained devices (and, in my opinion, should 
have been part of RFC 7748). <<RS

> Best regards,
> Stanislav Smyshlyaev

email:rstruik.ext@gmail.com  | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363