Re: [Cfrg] Mishandling twist attacks

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Mon, 01 December 2014 09:38 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>
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 6DB351A1AA9 for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 01:38:21 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.501
X-Spam-Level:
X-Spam-Status: No, score=-0.501 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] 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 1XFe8Vew8Mqu for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 01:38:20 -0800 (PST)
Received: from emh04.mail.saunalahti.fi (emh04.mail.saunalahti.fi [62.142.5.110]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BFFB41A00E1 for <cfrg@irtf.org>; Mon, 1 Dec 2014 01:38:19 -0800 (PST)
Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi [88.112.44.140]) by emh04.mail.saunalahti.fi (Postfix) with ESMTP id 5CBF71A264B; Mon, 1 Dec 2014 11:38:17 +0200 (EET)
Date: Mon, 1 Dec 2014 11:38:17 +0200
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: Watson Ladd <watsonbladd@gmail.com>
Message-ID: <20141201093817.GA5369@LK-Perkele-VII>
References: <20141128014059.26622.qmail@cr.yp.to> <CACsn0cm4OBZX9RqV0nuT7547h+4e2_X3qgButJ+sdZDvG+65Ww@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <CACsn0cm4OBZX9RqV0nuT7547h+4e2_X3qgButJ+sdZDvG+65Ww@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/5qdY0SNep-cvUBBwZtVOa2MUv-0
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Mishandling twist attacks
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: Mon, 01 Dec 2014 09:38:21 -0000

On Fri, Nov 28, 2014 at 09:22:16AM -0800, Watson Ladd wrote:
> On Thu, Nov 27, 2014 at 5:40 PM, D. J. Bernstein <djb@cr.yp.to>; wrote:
> 
> >
> > For Curve25519, the twist cofactor divides the curve cofactor, and this
> > problem disappears. What the standards say to do, namely multiply by the
> > curve cofactor, is wrong for PinkBikeShed but correct for Curve25519.
> > The numerical details are spelled out in the "Small-subgroup attacks"
> > section of the Curve25519 paper.
> >
> > This wasn't my only reason for rejecting PinkBikeShed. The Curve25519
> > paper mentions a less important reason that allowed a much shorter
> > summary and that, as a historical matter, came first. I didn't bother
> > writing down a comprehensive critique of PinkBikeShed, and didn't
> > imagine that anyone would ever try to revive that curve.
> >
> > ---Dan
> 
> So if we add this requirement to have the curve have larger cofactor
> then the twist, then we still get E-521, and we will get Curve25519 at
> the low end. It seems to me like we should make this change to the
> generation method, and run it on 2^389-21 to get the intermediate size
> curve.

p=2^389-21, I got the following:


d=-5423:
Isogenous A: 21694   => a24=5424   (hamming: 5)   Transform: u=y^2/x^2
Trace: -23547479314797536958302370097870341395883202421886243703784
Cofactors: 4 and 4

Base point order: 
l=315216049571155833698232320801148910440637914163723573343592234103794473556217260483838597624428295927058495483380469
=2^387+O(2^192)

Smallest k such that l|p^k-1: (l-1)/2
Smallest k such that l'|p^k-1: (l'-1)/1
|D|: ~2^388.8
Estimated security: ~193.3

Base point (Least y, least x):
x=160184824201037515317245555585704883073517785386930765659808438542670241435277265556988296711827646433390758793724234
y=7
u=1260864198284623334792929283204595641762551656654894293374345388935863096687910739565256520156317300505812095689546827

Base point (rpgecc):
x=170804322239093707949130602656597319986126639581075264465402345120740704618385490579748076285548067049274053507624217
y=112208747348660010440461485720580635773713686011119895123348385652709827070576978616679662918030308385499173548944326
u=563185763117749471608453920883370391920123099397236109145115118464484481872631146356911850563253178351269924969126147



d=5424 (twist of previous):
Isogenous A: -21694  => a24=-5423  (hamming: 8)   Transform u=y^2/x^2
Trace: 23547479314797536958302370097870341395883202421886243703784
Cofactors: 4 and 4

Base point order: 
l=315216049571155833698232320801148910440637914163723573343580460364137074787738109298789662453730354325847552361528577
=2^387-O(2^192)

Smallest k such that l|p^k-1: (l-1)/1
Smallest k such that l'|p^k-1: (l'-1)/2
|D|: ~2^388.8
Estimated security: ~193.3

Base point (Least y, least x):
x=289071503382026803838222130853306808021454096751162077829619259082696022707255732386746573351122328749200804860611129
y=39
u=121938840228841861983263555678339183775720456268598329688176823798402549482317683365850466094064896825233143472994317

Base point (rpgecc):
x=154967135639069417030102433300225437427016077568302153608646752078495859574915806070734195256471555210704351661774493
y=386528499748825134645630797978789902631543437822324733831174382162482970539323383318004263033116065650371855521422332
u=863904929441083075748296283970356413257536404565364151832776905623802210399619240548188030128828579099870154430107596



Regarding  E-521 (d=-376014), it has order 2^519-O(2^258). Its
twist (d=376015) is the smallest d with l>2^519 and h'=4.



-Ilari