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

Dan Brown <dbrown@certicom.com> Wed, 26 November 2014 20:54 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BBDF61A1B5F for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 12:54:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 2y-COH5t7n_l for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 12:54:23 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id C67091A1B47 for <cfrg@irtf.org>; Wed, 26 Nov 2014 12:54:22 -0800 (PST)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs214cnc.rim.net with ESMTP/TLS/AES128-SHA; 26 Nov 2014 15:54:17 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0174.001; Wed, 26 Nov 2014 15:54:16 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'mike@shiftleft.org'" <mike@shiftleft.org>
Thread-Topic: [Cfrg] Preliminary disclosure on twist security ...
Thread-Index: AdAJieU4Ye2dd7TATPKiXX6WalzfrwAMWVyAAAkAiPD//9xbAIAAQ9Cg///ZOgCAAErXgA==
Date: Wed, 26 Nov 2014 20:54:16 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5D0775C@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5D072C5@XMB116CNC.rim.net> <CACsn0ck5vgB5qojL2o38Vb=mt9ZFNres+EVXBsBK=VRjrpwLzw@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5D0742B@XMB116CNC.rim.net> <CACsn0ckthZehQZkYyBBcCmHKrf-DsCk5s95Mr8_kQcNSD+7hPQ@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5D0763F@XMB116CNC.rim.net> <0B11050B-31BF-458A-91EE-7F12AC36E3E2@shiftleft.org>
In-Reply-To: <0B11050B-31BF-458A-91EE-7F12AC36E3E2@shiftleft.org>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_018D_01D00991.3B156470"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/h6Od_dzYGNhJQGsgwGlcn0ZZpDg
Cc: "'cfrg@irtf.org'" <cfrg@irtf.org>, "'djb@cr.yp.to'" <djb@cr.yp.to>
Subject: Re: [Cfrg] Preliminary disclosure on twist security ...
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 26 Nov 2014 20:54:24 -0000


> -----Original Message-----
> From: Michael Hamburg [mailto:mike@shiftleft.org]
> 
> 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