[Lwip] Fwd: Review of draft-ietf-lwig-curve-representations-00 by crypto review panel

[Mohit Sethi M <[e-mail]>]

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 <[e-mail]><mailto:[e-mail]>
To:     Mohit Sethi M <[e-mail]><mailto:[e-mail]>, [e-mail]<mailto:[e-mail]> <[e-mail]><mailto:[e-mail]>, [e-mail]<mailto:[e-mail]> <[e-mail]><mailto:[e-mail]>, Alexey Melnikov <[e-mail]><mailto:[e-mail]>


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: [e-mail]<mailto:[e-mail]>


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.
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).
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.
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.
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.
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.
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.
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.

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).
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.

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.

###### 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.


Best regards,
Stanislav Smyshlyaev