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

[Michael Hamburg <[e-mail]>]

> On Nov 26, 2014, at 12:54 PM, Dan Brown <[e-mail]> wrote:
> 
> 
> 
>> -----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.)

So, this patent will require very tricky arguments, and you should consult a lawyer rather than relying on this analysis.  This is just how one *might* argue that twist-secure curves are not covered.

The Montgomery ladder mostly implements Diffie-Hellman over E(F(p)), not E(F_p^2).  It cannot represent or compute on the vast majority of elements of E(F_p^2).  The behavior of the twist is a side-effect.

Prime-field DH may be implemented over the full F*_p, or over a smaller (perhaps prime-order) subgroup.  Behavior that this patent describes where users intentionally use F*_p or a subgroup whose order is the product of large primes clearly does not apply here.  It’s only for cases where the users are trying to implement a prime- or nearly-prime-order subgroup S of F*_p that could apply, because users of twist-secure curves are definitely not intentionally working over E(F_p^2).

Even if the intent is to generate only a prime-order subgroup S of F*_p and to use the rest to deter small-subgroup attacks, there is an important difference from the patented material.  The F*_p DH case will actually use the full group F*_p, but the Kummer ECDH code implements only the union of E(F_p) and its twist.

That may be enough to prevent it from being covered, or it may not.  On the one hand, using different language to describe something doesn’t prevent it from being covered.  On the other hand, there really is a qualitative difference between an implementation of the full G = E(F_p^2) and just the curve+twist.  Furthermore, the language of (53) is very vague: it doesn’t specify that G or S is used in any way in the key generation, only alpha.  So one might say that it doesn’t matter whether the full G or S is implemented.  But if interpreted that broadly, it’s probably too vague to be valid.

> 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.

No, usually xy formulas assume that y^2 = f(x), not u f(x) for some quadratic nonresidue u.

> Best regards,
> 
> Dan

Cheers,
— Mike