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

From: Alexey Melnikov <[email-masked]>
Date: Mon, 05 Nov 2018 10:41:56 +0000

Hi,
Can one of Crypto Panel members review this document?

Thank you,
Alexey

----- Original message -----
From: Mohit Sethi M <[email-masked]>
To: "[email-masked]" <[email-masked]>, Suresh Krishnan <[email-masked]>, Zhen Cao <[email-masked]>
Subject: Review of draft-ietf-lwig-curve-representations-00 by crypto review panel
Date: Sun, 4 Nov 2018 08:26:08 +0000

Hi Alexey,

We spoke today about the need for getting more reviews on a LWIG 
document titled "Alternative Elliptic Curve Representations": 
https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-00

The draft describes how to implement Ed25519, Curve25519 and NIST P-256 
with the same underlying implementation. Phillip Hallam-Baker also 
recently requested this on the SAAG list: 
https://mailarchive.ietf.org/arch/msg/saag/QM80DmA-3iEBxlh_VU5B5wOQnnA.

It would be great if someone from the crypto review panel could provide 
feedback on this draft. The draft is currently hosted in the LWIG 
working group and Zhen (in CC) is my co-chair, while Suresh (in CC) is 
the responsible area director.

Rene will also present the draft on Wednesday in LWIG in room Meeting 2 
between 11:20-12:20.

--Mohit

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 6 Nov 2018 18:45:16 +0700

Dear Alexey,

I’ll be happy to do it.

Since there are many numbers to check, and since it’s much better to be
done using independent implementations of elliptics, it will take some
time.

Will it be OK if I do it until the end of November?

Best regards,
Stanislav

пн, 5 нояб. 2018 г. в 17:42, Alexey Melnikov <[email-masked]>:

> To: "[email-masked]" <[email-masked]>, Suresh Krishnan <
> [email-masked]>, Zhen Cao <[email-masked]>
> _______________________________________________
> Crypto-panel mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/crypto-panel
>

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 08 Nov 2018 04:53:27 +0000

On Tue, Nov 6, 2018, at 11:45 AM, Stanislav V. Smyshlyaev wrote:
> Dear Alexey,
> 
> I’ll be happy to do it. 
> 
> Since there are many numbers to check, and since it’s much better to
> be done using independent implementations of elliptics, it will take
> some time.> 
Thank you. I am sure this will not be a problem!

> 
> Best regards,
> Stanislav
> 
> пн, 5 нояб. 2018 г. в 17:42, Alexey Melnikov <[email-masked]>:>> Hi,
>>  To: "[email-masked]" <[email-masked]>, Suresh
>>  Krishnan <[email-masked]>, Zhen Cao <[email-masked]>>>  Subject: Review of draft-ietf-lwig-curve-representations-00 by
>>  crypto review panel>>  Date: Sun, 4 Nov 2018 08:26:08 +0000
>> 
>>  Hi Alexey,
>> 
>> https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-00>> 
>>  The draft describes how to implement Ed25519, Curve25519 and
>>  NIST P-256>>  with the same underlying implementation. Phillip Hallam-Baker also>>  recently requested this on the SAAG list: 
>> https://mailarchive.ietf.org/arch/msg/saag/QM80DmA-3iEBxlh_VU5B5wOQnnA.>> 
>>  It would be great if someone from the crypto review panel could
>>  provide>>  feedback on this draft. The draft is currently hosted in the LWIG 
>>  working group and Zhen (in CC) is my co-chair, while Suresh (in
>>  CC) is>>  the responsible area director.
>> 
>>  Rene will also present the draft on Wednesday in LWIG in room
>>  Meeting 2>>  between 11:20-12:20.
>> 
>>  --Mohit
>>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 26 Nov 2018 14:47:18 +0300

Good afternoon,

Please find below the review of the document.

Of course, I'll be happy to discuss all questions raised in the review
directly via e-mail: [email-masked]

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