Re: [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]>]

Hi Adam:

Thanks for the quick feedback and willingness to accommodate my 
suggestions to improve the draft.

I will revisit your email later. However, just another brief process note:
I would like to strongly suggest first re-publishing your individual 
internet draft draft-agl-cfrgcurve-00, but now as 
draft-irtf-cfrg-curve-00 (i.e., verbatim copy, except change of title 
and submission date) and only then make changes to the resulting 
document. As I said in my previous process note (Jan 5, 2015, 4.42pm 
EST), this allows easy to keep track of evolution over time.

Please forgive me my "rigid" approach here, but the "rigid curve 
selection criteria" we started out with seem to have to apply to the 
processes of this (somewhat dysfunctional) IRTF group as well. I hope 
you appreciate this; this is not a personal criticism. BTW - this 
republication suggestion is precisely what Alexey Melnikov suggested in 
his Sat Jan 24, 2015 adoption email.

Best regards, Rene

On 1/27/2015 7:16 PM, Adam Langley wrote:
> On Tue, Jan 27, 2015 at 10:15 AM, Rene Struik <[e-mail] 
> <mailto:[e-mail]>> wrote:
>
>     It seems that draft-agl-cfrgcurve-00 contains a few technical
>     flaws, including:
>
>
> Thank you very much for this. It prompted me to make some changes that 
> I've been planning.
>
>     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.
>
>
> You are quite correct. I've fixed this.
>
>     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).
>
>
> I had fixed this on GitHub after Andrey's note and it'll be in 
> draft-irtf-cfrg-curves-00.
>
>     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.}
>
>
> The curve25519 function is defined as a function from ([32]byte, 
> [32]byte) -> [32]byte. As such, it does have a defined behaviour when 
> the resulting point is (0::0) as it'll output all zero bytes. Although 
> the draft was written with the possibility in mind that we might 
> define several curves, my estimation at the moment if that the CFRG 
> won't actually do that. Things might turn out differently but, for the 
> moment, I'm changing the document to be more curve25519 specific 
> rather than specifying the Montgomery ladder more generally.
>
>     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).
>
>
> It's certainly possible to extract the value of the scalar mod the 
> cofactor from curve25519, but the scalar construction ensures that 
> value is zero. I've made a note about the "non-contributory" behaviour 
> of curve25519 in the draft.
>
>     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.
>
>
> Both fixed, thanks.
>
>     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.
>
>
> I've split the scalar-mult function into its own section and moved the 
> DH bits into a separate one.
>
>     -- 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.
>
>
> That's my screwup. The scalar-mult function was called "curve25519" 
> and I changed it to DH in anticipation that more curves might be 
> defined. Since I get the feeling that won't happen now, I've switched 
> back to calling it "curve25519".
>
>     -- 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)?
>
>
> This is still an open issue as I have it now. In order to be 
> consistent, I've called the coordinates on the Montgomery curve (u, v) 
> and those on the (twisted) Edwards (x, y). We need to figure out 
> whether the existing specification for generating curves is called for 
> if we're not going to have any others. If not, then we could have 
> (x,y)  for the Montgomery curve and at least be a little more 
> consistent. I have, at least, make the scalar be 'k'.
>
>     -- 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.
>
>
> I agree and have removed that language.
>
>     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]>
>     <mailto:[e-mail]>
>     To: 	[e-mail] <mailto:[e-mail]> <[e-mail]>
>     <mailto:[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]  <mailto:[e-mail]>
>     http://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>
>     _______________________________________________
>     Cfrg mailing list
>     [e-mail] <mailto:[e-mail]>
>     http://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>
> -- 
> Adam Langley [e-mail] <mailto:[e-mail]> 
> https://www.imperialviolet.org


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