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

[Adam Langley <[e-mail]>]

On Tue, Jan 27, 2015 at 10:15 AM, Rene Struik <[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]>
> <[e-mail]>  To: [e-mail] <[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 [e-mail]://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>


-- 
Adam Langley [e-mail] https://www.imperialviolet.org