Subject: [Cfrg] Should Ed25519 use a pseudo-random generator point?

From: Bill Cox <[email-masked]>
Date: Sun, 25 Oct 2015 06:52:18 -0700

Sorry again for my arm-chair level of crypto knowledge.  I think the answer
is "no", especially given how far Ed25519 is along the standardization
path, but here's my arm-chair concern anyway.  Does using 4/5 as the X
coordinate of the generator have speed benefits or any other benefit?

I am concerned that using 4/5 as the X-coordinate might lead to an attack
someday.  I think this is _very_ unlikely, but is it worth worrying about?
Instead of using 4/5 for g's X coordinate, we could use SHA256(n), where n
is the smallest non-negative integer that puts g in the right group.

When we know the rational X coordinate of the generator point g, then we
can easily map any point m*g to m*h, where h is very to the origin.  On the
actual curve, not mod p, the point m*h would wrap around the curve
typically at most once, given any m < p.  While this seems to mean nothing
mod p, given floating-point representations of m*g on the curve, it is
easier to compute m without wrapping around the curve many times.  I am not
saying this implies anything about ECC security in any way, but it makes me
go "hmm..."

Given this lame geometric insight, and also how the NIST curves did not
offer any justification for how their generator points were derived, I am
concerned that there might be some weakness in ECC that can only be
exploited when we know the rational X-coordinate of the generator.  Is
there any harm in using a generator with a pseudo-random X coordinate?

Bill

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 25 Oct 2015 16:25:28 +0200

> coordinate of the generator have speed benefits or any other benefit?

I think it is y-coordinate that is 4/5? 

The reason it is y=4/5 is to enable the following trick:
- Compute xB on Edwards curve.
- Transform the point to Curve25519 point (faster than outputting
  the point).
- The answer will be Curve25519(x, 9).

u = (1 + y) / (1 - y) = (1 + 4/5) / (1 - 4/5) = 9

And scalar multiplication can be accelerated by precomputing some
point-dependent lookup tables. Those tables can be bit large, so
one would want to only keep one per curve.

The Edwards448 basepoint is chosen so that the corresponding trick
works with Edwards448 and Curve448 (the preimage just looks like
random jumble, there is only one valid y for that).

u = (y/x)^2 = ... = 5

Regarding security of basepoint choice, due to the way ECDH works,
if one basepoint of large prime order is weak, all such basepoints
are weak -> The whole curve is weak.

Nevertheless, some protocols need pseudorandom basepoints.
Specifically, those need two basepoints with unknown relation, because
those protocols have backdoor a'la DUAL_EC_DRBG: If you know x such
that P=xQ (where P and Q are the basepoints), the entiere security
disasppears.

While such protocols sound bad, sometimes using constructions of that
type is easier than making a secure protocol that works with one
stndard basepoint (however DUAL_EC_DRBG is not one of those cases,
since it is just horrible in other ways too).

-Ilari