Subject: Re: [Cfrg] Mishandling twist attacks

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 1 Dec 2014 11:38:17 +0200

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 <[email-masked]> 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

---

From: "Lochter, Manfred" <[email-masked]>
Date: Mon, 1 Dec 2014 17:35:48 +0100

_

>
> There's a long tradition of blaming the implementor for the resulting
> security failures: it's the implementor's fault for not writing
> constant-time code, for not checking for exceptional cases, etc.
>
> However, we've known for many years how to _change the crypto_ to avoid
> all of these implementation pitfalls. Specifically, we
>
>    
>
>    * always set the top bit of scalars so that an input-length-agnostic
>      variant of the Montgomery ladder doesn't create a timing leak.
>

On the other hand this countermeasure is quite dangerous, when applied during 
signature generation. It may leak parts of the ephemeral keys. Which in turn 
allows lattice attacks. (The most dangerous situation being SW which is used 
in an protected environment, where only timing attacks are seen as a 
danger. )

Manfred

-- 
Lochter, Manfred
--------------------------------------------
Bundesamt für Sicherheit in der Informationstechnik (BSI)
Referat K21
Godesberger Allee 185 -189
53175 Bonn

Postfach 20 03 63
53133 Bonn

Telefon: +49 (0)228 99 9582 5643
Telefax: +49 (0)228 99 10 9582 5643
E-Mail: [email-masked]
Internet:
www.bsi.bund.de
www.bsi-fuer-buerger.de

---

From: "D. J. Bernstein" <[email-masked]>
Date: 1 Dec 2014 22:37:20 -0000

Lochter, Manfred writes:
> On the other hand this countermeasure is quite dangerous, when applied
> during signature generation.

No. It's true that minimum-length signature nonces with the high bit set
are dangerous, but minimum-length signature nonces _without_ the high
bit set are _also_ dangerous, so blaming the high bit is unreasonable.

The best protection we know is to generate much longer nonces---such as
the 512-bit nonces in Ed25519. Then the system isn't broken by a timing
attack revealing the nonce length. Setting the high bit of such a long
nonce is also perfectly safe.

Of course, an implementor can still get in trouble by (1) reducing these
nonces and then (2) leaking the lengths of the reduced nonces through a
variable-time scalarmult method. So, as another line of defense, we also
choose curves that support simple, fast, constant-time ladders.

---Dan