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

Dan Brown <> Wed, 26 November 2014 20:54 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id BBDF61A1B5F for <>; Wed, 26 Nov 2014 12:54:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 2y-COH5t7n_l for <>; Wed, 26 Nov 2014 12:54:23 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id C67091A1B47 for <>; Wed, 26 Nov 2014 12:54:22 -0800 (PST)
Received: from ([]) by with ESMTP/TLS/AES128-SHA; 26 Nov 2014 15:54:17 -0500
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0174.001; Wed, 26 Nov 2014 15:54:16 -0500
From: Dan Brown <>
To: "''" <>
Thread-Topic: [Cfrg] Preliminary disclosure on twist security ...
Thread-Index: AdAJieU4Ye2dd7TATPKiXX6WalzfrwAMWVyAAAkAiPD//9xbAIAAQ9Cg///ZOgCAAErXgA==
Date: Wed, 26 Nov 2014 20:54:16 +0000
Message-ID: <>
References: <> <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_018D_01D00991.3B156470"
MIME-Version: 1.0
Cc: "''" <>, "''" <>
Subject: Re: [Cfrg] Preliminary disclosure on twist security ...
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 26 Nov 2014 20:54:24 -0000

> -----Original Message-----
> From: Michael Hamburg []
> 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,