Subject: [Cfrg] RFC 6090 correctness

From: Watson Ladd <[email-masked]>
Date: Sat, 15 Mar 2014 13:18:37 -0700

Dear all,

It is not obvious to me why the algorithm in appendix F.2 in RFC 6090
is correct. Why is u=0, v !=0 prohibited? In particular, given a
single y coordinate there are potentially three x coordinates in the
field with that y coordinate. When presented with two of these points,
the algorithm given then falls through to computing 2*P1, which isn't
the right answer.

Explicitly, on the curve y=(x-a)(x-b)(x-c) over any field of large
enough characteristic, adding (a,0,1) to (b,0,1) will not produce
(c,0,1), but rather the point at infinity as these are 2-torsion
points.

Sincerely,
Watson Ladd

---

From: Watson Ladd <[email-masked]>
Date: Sat, 15 Mar 2014 17:18:20 -0700

> (c,0,1), but rather the point at infinity as these are 2-torsion

For clarification, I meant addition as given in the RFC. The correct
answer is the third point, but the RFC gives the point at infinity.
Thanks to Tanja Lange for pointing this out.

---

From: Tanja Lange <[email-masked]>
Date: Sun, 16 Mar 2014 01:28:06 +0100

Dear all,
> > the algorithm given then falls through to computing 2*P1, which isn't
To phrase it stronger than Watson: The algorithm is wrong. It merges the
cases of adding (x1,y1) to (x2,y1) into the case of doubling (x1,y1).

The correct algorithm needs a different case distinction

if P1=infty
elif P2=infty 
elif P1=-P2
elif P1!=P2
else (which is the P1=P2) case

All the best
	Tanja

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 15 Mar 2014 17:44:54 -0700

Please note that RFC 6090 already has a bunch of errata; see <http://www.rfc-editor.org/errata_search.php?rfc=6090>. Maybe Watson and Tanja can coordinate on a concise statement of the current error and turn in a new errata. It would also be grand if people on the list went through the RFC with a finer-tooth comb than they did before it was published and report anything else.

There are enough errata that it feels like the RFC should be updated to deal with them all.

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Sat, 15 Mar 2014 18:42:10 -0700

> There are enough errata that it feels like the RFC should be updated to deal with them all.

I've submitted an erratum, but there are multiple possible fixes.
Furthermore, the nature of this error is significant: it may be
possible to exploit this mistake in implementations that slavishly
adhere to the RFC. One example of this causing security problems is in
Petersen commitments: ag+bh is usually computed by taking
(a-b)g+b(h+g) and so on recursively. If g and h are crafted so that
h+g results in 2g, not h+g, the commitment doesn't bind to any value
of b. Note that this doesn't require knowing the discrete log of g to
the base h, and in fact is compatible with some "nothing up my sleeve"
means of point generation.

Sincerely,
Watson Ladd
>
> --Paul Hoffman
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 15 Mar 2014 19:16:44 -0700

> I've submitted an erratum, but there are multiple possible fixes.

Given that, it would be good to have group review of the erratum: http://www.rfc-editor.org/errata_search.php?rfc=6090&eid=3920

--Paul Hoffman

---

From: Tanja Lange <[email-masked]>
Date: Sun, 16 Mar 2014 12:49:46 +0100

> There are enough errata that it feels like the RFC should be updated to deal with them all.
If there is an update I suggest to include Jacobi coordinates. They are
mentioned in 3.2 but not stated anywhere. This is the coordinate system
most implementations use (they often call it projective though). 

	Tanja