[Cfrg] (technical flaws to be corrected in next version of the draft) Fwd: Re: Adoption of draft-agl-cfrgcurve-00 as a RG document

[Rene Struik <[e-mail]>]

Dear colleagues:

It seems that draft-agl-cfrgcurve-00 contains a few technical flaws, 
including:
a) Section 9, p. 10:
The Montgomery ladder works on projective points of the form (X:Y:Z), or 
(X::Z) {if the Y-coordinate is deleted}, where x=X/Z, y=Y/Z, and where 
the point at infinity is (1::0).
If so, one has Q-Q'=(x1::z1)=(u::1), Q'=(x2::z2)=(1::0) {the point at 
infinity}, and Q=(x3::z3)=(u::1).
With the draft, one mistakenly has (x2::z2)=(0::1), i.e., the 
representation of the affine point (0,0) of order two. In that case 
Montgomery Adds results in (u::1) + (0::1) = (4::4u^3)~ (1:: u^3). So, 
the procedure outputs on input Q:=(u::1) and scalar k=1, the incorrect 
output R:=(1::u^3) (with x-coordinate u^{-3}), rather than simply u.
b) Section 9, p. 10:
The Montgomery ladder should produce, on input Q=(x1::z1) and scalar k, 
the output R:=kQ=(x2::z2), which can be mapped to an affine point with 
x-coordinate x2/z2.
With the draft, one mistakenly takes 1/z2 = z2^{p-1}, whereas this 
should obviously be z2^{p-2} (if z2 is nonzero).
c) Section 9, p. 10:
The Montgomery ladder does not produce the output R=kQ for each input Q 
and scalar k, since, e.g., (after correcting the flaw identified in #a 
above), one can end up with the unidentified string projective point 
(0::0) in some cases. So, one should clarify what the input/output 
behavior of the Montgomery ladder is more clearly. {Does this work for 
all Montgomery curves, e.g., also when the curve y^2 = x^3 + A x^2 + x 
for which A^2 <>4?, etc.}
d) Section 9.1, p. 11:
With the draft, the output of the Diffie-Hellman protocol, as presented, 
succumbs to the small subgroup attack (e.g., DH(f,0)=0), no matter the 
value of f contributed by A).
e) Section 9.1, p. 11:
With the draft one has some annoying editorial glitches, including
-- "Alice then transmits K_A=DH(f,9) to Bob, where 9 is the number 9" 
should most likely read "Alice then transmits K_A=DH(f,g) to Bob, where 
g is the number 9".
-- "Alice computes DH(f,DH(g,9))" should read "Alice computes 
DH(f,K_B)"; etc., and vice-versa for Bob.
f) Section 9, pp. 9-11:
-- With the draft, the first part of Section 9 (till Section 9.1) is 
about scalar multiplication and probably deserves a separate subsection 
to that effect.
-- With the draft, not sure why scalar multiplication ineptly uses the 
acronym "DH" (as in DH(s,u). I would strongly suggest avoiding any 
language that could put people on the wrong footing, due to connotations 
ubiquitous in the crypto literature.
-- With the draft, one seems to introduce lots of new variables to 
denote objects (e.g., why not use scalar k, point G, Q, DH key K= a Qb, 
co-factor h, etc., if one wants to cross a message most effectively)?
-- With the draft, outsiders who are not necessarily be versed in 
cryptography would have a hard time following/verifying esoteric 
language and certainly would not be familiar with "quadratic 
extensions", "projection maps ... extended, so". I would suggest that 
clarity of language is key here.

Notes: Andrey Jivsov noted error #b above. I tried to retrace other 
errors to cut-and-paste errors from 
draft-turner-thecurve25519function-01, but that original draft also 
contains these errors (despite mentioned review by Tanja Lange, 
according to acknowledgements). The turner draft does contain an 
implicit reference to flaw #d above, although in nebulous terms 
("contributory behavior").

For now, I refrain from other comments, but hope that we at least get 
the technical details right. (I was hoping that the adoption call would 
end with someone else noticing the errors above, but did not see this 
(except for #b above), so reluctantly go to the CFRG list to mention 
some of this here. [I have my private thoughts about how many people 
actually read the entire draft...].)

Best regards, Rene

-------- Forwarded Message --------
Subject: 	Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
Date: 	Sat, 24 Jan 2015 17:57:25 +0000
From: 	Alexey Melnikov <[e-mail]>
To: 	[e-mail] <[e-mail]>



Dear CFRG participants,

On 05/01/2015 19:15, Alexey Melnikov wrote:
> This message starts 2 weeks adoption call (ending on January 19th
> 2015) on:
>
> https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml
>
> as the starting point for the CFRG document which describes an
> algorithm for safe curve parameter generation for a particular
> security level and also recommends a specific curve (2^255-19) for the
> 128-bit security level.
>
> Please reply to this message or directly to CFRG chairs, stating
> whether you support (or not) adoption of this document. If you do not
> support adoption of this document, please state whether you support
> adoption of any alternative document or whether you want a particular
> change be made to the document before adoption.
>
> Chairs ask not to reiterate previously expressed technical opinions or
> arguments. But clarifying questions on the adoption call are welcome.
>
> While making your decision, please keep in mind
>
> http://www.ietf.org/mail-archive/web/cfrg/current/msg05813.html
Thank you for all the constructive feedback.

Chairs have reviewed responses to this message (both public and some
private) and can confirm that there is rough consensus for adopting
draft-agl-cfrgcurve-00 as a RG document. Some people supported the
document with conditions that some changes would (or would not) be done
to it, although the majority of people supported it unconditionally.
Some people who objected to the document being adopted asked about
changes that were also asked by people who supported the document, so we
are hoping that a future revision of the draft might become acceptable
even to them.

Chairs are asking Adam to republish draft-agl-cfrgcurve-00 as
draft-irtf-cfrg-curves-00. Chairs are in the process of discussing who
would be editors of the CFRG document.

Best Regards,
Alexey,
On behalf of CFRG chairs.
>
> Alexey,
> On behalf of CFRG chairs.
>
> P.S. Editors of draft-black-rpgecc-01 and
> draft-turner-thecurve25519function-01 can become co-editors of the
> adopted document, if they choose to do so. Email chairs directly if
> you are willing or not willing to do so.

_______________________________________________
Cfrg mailing list
[e-mail]
http://www.irtf.org/mailman/listinfo/cfrg