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

From: Dan Brown <[email-masked]>
Date: Wed, 26 Nov 2014 15:50:59 +0000

Not sure why this first appeared as blank, sorry about that.  I've pasted
the text below for a 2nd try:

> -----Original Message-----
> From: Dan Brown

RFC 3979 "strongly encourages" a "preliminary disclosure" for any technology

being "seriously considered".

I am not sure which of this RG list or if 
http://www.ietf.org/ipr/file-disclosure.html is the correct place to make
such 
a preliminary disclosure. The RG list is more convenient for me, so here it 
goes.

Upon review today, I noticed that US Patent 6,563,928 B1, Claim 59,
supported 
in interpretation by reference to the patent specification's Column 5, lines

37-46 (which describes the case Zp*, but carries over, per the claim, to the

elliptic curve case) seems to anticipate some aspects of twist security that

are, arguably, exactly those aspects critical to avoiding an attack.  As
such, 
the patent holder may try to assert this against implementations of twist 
security.   Accordingly, I am disclosing this possibility.

Best regards,

Dan

---

From: Watson Ladd <[email-masked]>
Date: Wed, 26 Nov 2014 07:55:21 -0800

The patent in question is US6563928.

The claim cited reads as follows:

"53. A method of establishing a session key for encryption of data
between a pair of correspondents comprising the steps of one of said
correspondents selecting a finite group G, establishing a subgroup S
having an order q of the group G, determining an element α of the
subgroup S to generate greater than a predetermined number of the q
elements of the subgroup S and utilising said element α to generate a
session key at said one correspondent."

"59: 58. A method according to claim 53 wherein said order of said
subgroup is of the form utilising an integral number of a product of a
plurality of large primes.
59. A method according to claim 58 wherein the order of said subgroup
is of the form nrr′ where n, r and r′ are each integers and r and r′
are each prime numbers."

This doesn't appear to have anything to do that directly with twist
security. It does appear to cover the algorithm Microsoft proposed for
dealing with points of low order on NUMS curves in claim 15.  The
claim above would seem to cover any implementation of discrete
logarithm based cryptography that uses subgroup membership checks as a
means to ensure contributory behavior.

Sincerely,
Watson Ladd

2014-11-26 7:35 GMT-08:00 Dan Brown <[email-masked]>:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 26 Nov 2014 15:55:57 +0000

On 26 November 2014 15:50:59 GMT+00:00, Dan Brown <[email-masked]> wrote:
>Not sure why this first appeared as blank, sorry about that.

Blame S/MIME. :)

>US Patent 6,563,928 B1

Priority date 18 May 1995, so (disregarding for a moment its validity, applicability or otherwise) it expires in less than six months: is that correct?

- --
/akr

---

From: Dan Brown <[email-masked]>
Date: Wed, 26 Nov 2014 16:49:54 +0000

> From: Watson Ladd 
> "53. A method of establishing a session key for encryption of data between a
> pair of correspondents comprising the steps of one of said correspondents
> selecting a finite group G, establishing a subgroup S having an order q of the
> group G, determining an element α of the subgroup S to generate greater than
> a predetermined number of the q elements of the subgroup S and utilising said
> element α to generate a session key at said one correspondent."
> 
> "59: 58. A method according to claim 53 wherein said order of said subgroup is
> of the form utilising an integral number of a product of a plurality of large
> primes.
> 59. A method according to claim 58 wherein the order of said subgroup is of
> the form nrr′ where n, r and r′ are each integers and r and r′ are each prime
> numbers."
> 
> This doesn't appear to have anything to do that directly with twist security. 

Well, this is what I was thinking:

Let F_p be the underlying field.

Let E be the twist-secure curve, with size #E(F_p) = hr, where h is a small cofactor and r a large prime.  Its twist E' has size h'r' where h' to the another small cofactor and r' is another large prime.

Now G be the group of F_p^2 rational points, which is a group of size hh'rr', right?  Then let S be the subgroup with of G of size q = rr'.

Let alpha be the element of S used to generate the yet smaller subgroup of size, i.e. the conventional DH prime-order subgroup of E(F_p).  Now alpha generates r elements, which is greater than a predetermined number, e.g. 2^250.

This means putting n =1 in Claim 59.

Best regards,

Dan

---

From: Dan Brown <[email-masked]>
Date: Wed, 26 Nov 2014 17:13:23 +0000

> From: Alyssa Rowan

> >US Patent 6,563,928 B1
>
> Priority date 18 May 1995, so (disregarding for a moment its validity,
> applicability or otherwise) it expires in less than six months: is that 
> correct?
>
I think so, because it seems to be a continuation, not a continuation-in-part, 
but I am not expert in the area.  Another remotely possible wrinkle is the 
date when the US dropped 17-year-after-issue term rule: I'm guessing that the 
20-year-after-filing rule is the only term applicable here, because the US 
filing date is after the US rule change (but the GB filing date (?) is 
before).

Anyway, I had the feeling that the CFRG might be able to recommend a curve 
with twist-security within 6 months, so it seemed to right to mention this.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 26 Nov 2014 10:05:32 -0800

On Wed, Nov 26, 2014 at 8:49 AM, Dan Brown <[email-masked]> wrote:
> Now G be the group of F_p^2 rational points, which is a group of size hh'rr', right?

Nope: Take t=p+1-hr. t is the trace of a matrix with determinant p,
say diagonal with \alpha and \beta as eigenvalues. |G| = p^2+1-t_2,
where t_2=\apha^2+\beta^2. Using Viete's formulas, or maybe Newton's,
we write t^2-2p=t_2. So the order of |G| is p^2+2p+1-(p+1-hr)^2. It's
not hh'rr'.

I may have made a typo in the above: check Silverman for the exact details.

>Then let S be the subgroup with of G of size q = rr'.
>

---

From: Dan Brown <[email-masked]>
Date: Wed, 26 Nov 2014 19:12:08 +0000

> > Let E be the twist-secure curve, with size #E(F_p) = hr, where h is a 
> > small
> cofactor and r a large prime.  Its twist E' has size h'r' where h' to the 
> another
> small cofactor and r' is another large prime.
> >
> > Now G be the group of F_p^2 rational points, which is a group of size 
> > hh'rr',
> right?
>
> Nope: Take t=p+1-hr. t is the trace of a matrix with determinant p, say 
> diagonal
> with \alpha and \beta as eigenvalues. |G| = p^2+1-t_2, where
> t_2=\apha^2+\beta^2. Using Viete's formulas, or maybe Newton's, we write
> t^2-2p=t_2. So the order of |G| is p^2+2p+1-(p+1-hr)^2. It's not hh'rr'.
>
[DB] Ok, as a sanity check, I just checked the Blake--Seroussi--Smart book. 
The order of G is p^2 + 2p + 1 - t^2, just as say.  But this equals (p+1)-t^2 
= (p+1-t)(p+1+t) = (hr)(h'r'), as I claimed, right?

My original reasoning was as follows. If x corresponds to a point outside 
E(F_p), then there exists y in F_p^2, with (x,y) on E(F_p^2), and the same 
addition law applies to this curve - it has the same equation - so surely 
(x,y) would have an order dividing h'r'.  This led me to conclude that 
E(F_p^2) has subgroups of order r and r', and being abelian, has a subgroup of 
order rr'.  I had thought all this part of the twist security story.

Indeed, when I inquired earlier this year about the risk associated not 
rejecting such x, I remember some people answering that this should be as 
secure as doing ECDH in E(F_p^2).

Or, am I really misunderstanding twist security?

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 26 Nov 2014 11:49:28 -0800

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

— Mike

> On Nov 26, 2014, at 11:12 AM, Dan Brown <[email-masked]> wrote:
> 
>

---

From: Dan Brown <[email-masked]>
Date: Wed, 26 Nov 2014 20:54:16 +0000

> From: Michael Hamburg [mailto:[email-masked]]
> 
> 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

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 26 Nov 2014 13:41:43 -0800

> On Nov 26, 2014, at 12:54 PM, Dan Brown <[email-masked]> wrote:
> 
> 
> 

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

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.

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

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

> Dan

Cheers,
— Mike