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

Dan Brown <dbrown@certicom.com> Wed, 26 November 2014 19:12 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 5842B1A0125 for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 11:12:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.1
X-Spam-Level:
X-Spam-Status: No, score=0.1 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, J_CHICKENPOX_22=0.6] 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 k7AH9ueux6ny for <cfrg@ietfa.amsl.com>; Wed, 26 Nov 2014 11:12:16 -0800 (PST)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id F1AFB1A0179 for <cfrg@irtf.org>; Wed, 26 Nov 2014 11:12:15 -0800 (PST)
Received: from xct107cnc.rim.net ([10.65.161.207]) by mhs212cnc.rim.net with ESMTP/TLS/AES128-SHA; 26 Nov 2014 14:12:10 -0500
Received: from XCT114CNC.rim.net (10.65.161.214) by XCT107CNC.rim.net (10.65.161.207) with Microsoft SMTP Server (TLS) id 14.3.174.1; Wed, 26 Nov 2014 14:12:10 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT114CNC.rim.net ([::1]) with mapi id 14.03.0174.001; Wed, 26 Nov 2014 14:12:09 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'watsonbladd@gmail.com'" <watsonbladd@gmail.com>
Thread-Topic: [Cfrg] Preliminary disclosure on twist security ...
Thread-Index: AdAJieU4Ye2dd7TATPKiXX6WalzfrwAMWVyAAAkAiPD//9xbAIAAQ9Cg
Date: Wed, 26 Nov 2014 19:12:08 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5D0763F@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>
In-Reply-To: <CACsn0ckthZehQZkYyBBcCmHKrf-DsCk5s95Mr8_kQcNSD+7hPQ@mail.gmail.com>
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_0189_01D00982.F6F90DE0"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/uxNNN6BEQLl0Xi1u99nW3XIMFDI
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:12:17 -0000

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