[Cfrg] Review of draft-ladd-safecurves

[Ilari Liusvaara <[e-mail]>]

Version: 743d3597a045fc6dd08b412d148d3f1a1e4cfd55
Date:   Wed Jan 15 17:26:58 2014 -0800


> Let p be a prime number. There is a unique field with p elements.
> Its elements can be represented as the set of integers {0, 1, ... p}.

Should that be {0, 1, ... p-1} ?

> To compute the additive inverse of a, one can compute (p-1)*a, and again
> take the remainder.

Won't p-a followed by remainder work?

> The remainder of this standard defines abelian groups in which for
> a fixed basepoint (denoted p), distinguishing between (g, [a]p, [b]p, [ab]p)
> with a, b picked uniformly at random from nonnegative integers less then
> the order, and (g, [a]g, [b]g, [c]g), is hard without spending prohibitive
> amounts of time. The time required is the square root of the order of g.

What's c? I presume uniform random nonnegative integer less that the order?

> On Montgomery curves, curves of the form y^2=x^3+a*x^2+x, the typical
> technique is to work over the Kummer variety instead, i.e. drop y
> coordinates for use in Diffie-Hellman. Let (X_1,Z_1), (X_2,Z_2),
> (X_3,Z_3) be coordinates such that X_1/Z_1, X_2/Z_2, X_3/Z_3 are the x
> coordinates of P, Q, and P+Q respectively. Then the equations

Is it P+Q or P-Q?

Also, reading the markup, the formulas below seem to use X1, Z1, etc...
when the above text talks of X_1, Z_1, etc...

> gives X_4/Z_4 as the x coordinate of [2]Q, and X_5/Z_5 as the x
> coordinate of P+[2]Q where a24=(a+2)/4.  If in calculating [n](X, Z),
> Z of the result is zero, this indicates that [n](X,Z) is the point
> at infinity, and so the result has x-coordinate 0.

P+[2]Q... The text below has P_1+P_0 appear in it? How those fit
together?

> 1: Intilize P_0=[1,0], and P_1=[x_P,1]
> 2: Iterate over the bits of n from most to least significant
> 2.1: If the bit is 0, let P_1=P_1+P_0, P_0=2P_0
> 2.2: If the bit is 1, let P_0=P_1+P_0, P_1=2P_1
> 3: Write [x_f, z_f]=P_0
> 4: If z_f is 0, return 0. Otherwise return x_f/z_f.

This section looked messed up in -03 HTML version. Can't easily tell
if you have done anything to it that would fix the formatting in
output.

Also, if one computes x_f/z_f as x_f*z_f^(p-2) mod p, then if z_f=0,
that produces 0 anyway.

> On (twisted) Edwards curves, curves of the form a*x^2+y^2=1+d*x^2y^2,
> a complete addition formula, which works for doubling as well, is
> given by representing points in projective coordinates. The formula
> for adding (X_1, Y_1, Z_1) to (X_2, Y_2, Z_2) is then

Then the formulas below have the X1 vs. X_1 thing.

Also, should doubling formula be given? Yes, straightforward substitution
works, but produces suboptimal algorithm without some manipulation.

> The Montgomery ladder algorithm from above will work with this addition
> and doubling, taking care to represent points as triples, and check that
> points lie on the curve going into and out of the routine. To convert

In what situations that check for points going out can fail. I know two:
- Buggy implementation
- Fault attack.

Others?

> Each curve is given by an equation and a basepoint, together with the
> order of the point and the cofactor.

One thing that could be useful would be listing low-order points (since
none of these curves has more than 8). Checking for those is needed
in some protocols.

I think explicit comparisions are much faster than multiplying 2 or 3
times and checking the result.

> Let (x,y) be a point on E(GF_p), where E is an Edwards curve or
> twisted Edwards curve. Let l=floor[log(p)/log(256)]+1. A point is
> represented as l bytes, l representing in big-endian radix 256 the
> minimal representative of [y] modulo p, and the top bit of the top
> byte set to equal the low bit of x. Because we have always ensured
> that there is extra room in l than is strictly required to represent
> y, we have room for the top bit to be set.

So the intention is that the top byte is always 0x00 or 0x80 for
all curves here, not just E448-Goldilocks (which is the only Edwards
curve here with bitlength multiple of 8)?

> Point encoding is clear in both cases. To decode a point on an Edwards
> curve with parameter d, one takes the y value and computes the
> valuex^2, then takes the square root. Methods for taking the square
> root are sadly highly prime-dependent, but [COHEN] contains a large
> number of options.

Perhaps add a note that if one relies on point decompression to check the
validity of input point, one has to check that the square root actually
exists. Many square root algorithms produce "interesting" results if one
tries to blindly take square roots that don't exist.

And using those "interesting" results might be much worse for security
than just enabling twist attack... 


-Ilari