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

Michael Hamburg <mike@shiftleft.org> Wed, 26 November 2014 19:49 UTC

Return-Path: <mike@shiftleft.org>
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 4C7FA1A1B4A for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 11:49:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 4.855
X-Spam-Level: ****
X-Spam-Status: No, score=4.855 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, J_CHICKENPOX_22=0.6, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
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 kw6JQSfIFJR7 for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 11:49:32 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9BD131A19EF for <cfrg@irtf.org>; Wed, 26 Nov 2014 11:49:32 -0800 (PST)
Received: from [10.184.148.249] (unknown [209.36.6.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 4CF6A3ABAF; Wed, 26 Nov 2014 11:47:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1417031271; bh=V/xtwwzGrJbNCPyrQ37AyiUNoe5CwV9Z51hdf81YyAY=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=hGM4NILBszY9w4ckkacR8zcfNZMqIneyk0ynTF+MVUturelpKf8MxDGNRUpzmBI9h avEeo8ViS8ZV8dYzEhhXK4Ydc4FRSB16ebmSxnL6aMmmUT3Dngl6Ix6YCcr3vk4VDp PNNLQcInPdeZoJOUnQEUxgNCX6kdn/5dJLXIey2w=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.1 \(1993\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5D0763F@XMB116CNC.rim.net>
Date: Wed, 26 Nov 2014 11:49:28 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <0B11050B-31BF-458A-91EE-7F12AC36E3E2@shiftleft.org>
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>
To: Dan Brown <dbrown@certicom.com>
X-Mailer: Apple Mail (2.1993)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/IEbANixcX595k-nVUKedcz651ys
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 19:49:34 -0000

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 <dbrown@certicom.com>; wrote:
> 
> 
>> -----Original Message-----
>> From: Watson Ladd
>>> 
>>> 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?
>> 
>> 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.
>> 
> [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?
> 
> 
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg