Re: [Cfrg] Preliminary disclosure on twist security ...

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Michael Hamburg [mailto:[e-mail]]
> 
> So, I’m not a lawyer, and I haven’t read the full patent, but the applicability of
> the quoted claims seems like a stretch to me.
> 
> In the case of a full elliptic curve implementation, the group G that’s actually
> implemented is only the points on the elliptic curve, having order hr in your
> notation.  The formulas will usually be completely wrong for the twist, and
> they of course won’t handle general points in F_p^2.  So it doesn’t make sense
> to say that the author implemented a subgroup S of E(F_p^2) with order rr’, or
> hh’rr’, or anything like that, or that it was “selected” or “utilised" for key
> agreement.  In this case, twist security isn’t very important anyway, because if
> you don’t do a curve membership check (possibly as part of decompression)
> you’ll get the wrong answer and will be exposed to attack.
> 
> In the case of an x-only implementation like X25519, where twist security
> matters, an algorithm like the Montgomery ladder does not implement a
> group at all.  Instead it implements only a powering/scalarmul map on the
> Kummer surface of the curve union its twist, and again not anything like a large
> subgroup of E(F_p^2).
> 

Well, you raise some interesting arguments.

In patent terms, using twist secure curves, and x-only, can be argued, as I do below, to be additional elements, over and above what's in Claim 59.  In patent law, adding elements does not escape coverage. A turbo charger on a car does _not_ make inapplicable any patents on seatbelts user in the car.  Of course, if non-obvious, useful, etc., additional elements can be used for a new patent.  The additional elements here are efficiency: avoiding the use of the big curve E(F_p^2), yet achieving some similar, and in sense equivalent.

So, for the x-only Montgomery ladder, would you say it's not even implementing Diffie-Hellman?   That seems a stretch to me, but I'll elaborate on my notion of equivalence.

I'd argue that the x-only Montgomery ladder without any check on x, is equivalent to ECDH over E(F_p^2), with an automatic check for points that are not of order hr or h'r' (i.e. the check is that x is in F_p, and is implicit), and further the representation of points is ambiguous, in that (x,y) and (x,-y) are treated identically.  Yes, you're right that a full E(F_p^2) implementation, say uncompressed, would need to some traditional public key validation, and in that regard, the x-only Montgomery without checking x also adds to security by obviating that additional check in a naïve E(F_p^2) implementation.  However, it's the twist security that still protecting you from the remaining invalid x, by a mechanism similar to what is described in Claim 59. (So, maybe a more appropriate metaphor than the one above would be an automatic seatbelt instead of a turbocharger.)

Side question: Is not twist security also helpful some forms of compressed ECDH in addition to laddered ECDH, since a false square y computed in decompression of invalid x, corresponds to a point on the twist E'(F_p), which, yes, does have a different equation than E(F_p), but also has order h'r'.  In other, the twist E' and E are isomorphic, with the h'r' points on E'(F_p) mapping to an h'r' sized subgroup of E(F_p^2) under the isomorphism, right?  

You also said the formulas will be completely wrong.  Well, many addition formulas are identical for E and E' ... and working over E, they are the same, up to the fact that whether you are handling F_p and F_p^2 coordinates.  The latter is addressed under the equivalence, and explains why the Montgomery works so nicely, even working over F_p when y should really be in F_p^2.

Best regards,

Dan