Re: [Cfrg] draft-irtf-cfrg-curves-07

[Adam Langley <[e-mail]>]

On Mon, Aug 31, 2015 at 4:39 PM, Ronald Harvey <[e-mail]> wrote:
> In Section 5.1, the second input u-coordinate for each of "X25519" and
> "X448" are, to my computations, not on the curve. These are the values
> beginning e5210f1278 and 0fbcc2f993cd56d, respectively.  I believe
> that this makes 'any valid implementation' unable to compute the
> answer, as only implementations which use an x-only algorithm could
> possibly find the expected new u.  If it was intentional, then it
> should probably be noted that these are limited in scope.

X25519 and X448, as defined, are functions from (byte[32], byte[32])
to byte[32] (or byte[56] for X448). As such, they are defined for all
inputs.

Although it is the case that one only expects points on a curve to be
generated and transmitted etc, partial implementations present at
least a fingerprinting issue. Since all the field functions can be
shared, and the Montgomery ladder is small, I think the assumption is
that implementations will use it. You can certainly still reuse
generator tables in Edwards form for calculating multiples of the base
point without any issues.

> When using other than x-only ladder for doing ECDH on these curves, is
> there a recommended procedure for running the (twisted) Edwards point
> multiply when starting from an 'invalid' u?  Most square root
> procedures will fail to return an answer when y^2 is not square.

(Completely shooting from the hip: the twist of curve25519 will also
be bi-rationally equivalent to a twisted Edwards curve. Some of the
Edwards formulas don't depend on d and so you might be able to compute
on that curve with the same formulae. Still, that seems more complex
and worse than using the ladder.)

> Regarding the Monte Carlo tests, it seems likely that a k which gets
> turned into a u will not always be on the curve, thus making it
> impossible also to use the tests with an Edwards (or other x-y)
> implementation.  Perhaps both k and u should be the result of the
> function after each iteration, ensuring a valid u as input; or k could
> be computed from the new u, e.g.

Are the "Monte Carlo" tests the iterated ones? If so, then I think it
might actually work out (by accident). The initial values are on the
curve and thus so will the outputs of the function be. So I think that
all the values will be on the curve? (Those tests were intended to
shake out any arithmetic errors in implementations rather than
anything else.)


Cheers

AGL

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