### Re: [Cfrg] Mishandling twist attacks

Watson Ladd <watsonbladd@gmail.com> Thu, 15 January 2015 18:26 UTC

Return-Path: <watsonbladd@gmail.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 A586C1B2FEC
for <cfrg@ietfa.amsl.com>; Thu, 15 Jan 2015 10:26:31 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -2

X-Spam-Level:

X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9,
DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1,
FREEMAIL_FROM=0.001, 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 DC9kbewjKSh0 for <cfrg@ietfa.amsl.com>;
Thu, 15 Jan 2015 10:26:28 -0800 (PST)

Received: from mail-yh0-x231.google.com (mail-yh0-x231.google.com
[IPv6:2607:f8b0:4002:c01::231])
(using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id CA8E21B2FC3
for <cfrg@irtf.org>; Thu, 15 Jan 2015 10:26:27 -0800 (PST)

Received: by mail-yh0-f49.google.com with SMTP id f10so8058372yha.8
for <cfrg@irtf.org>; Thu, 15 Jan 2015 10:26:27 -0800 (PST)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type:content-transfer-encoding;
bh=tVgbVuNBHQ0Wg2XPLJKhXj7qfXzHrrvJsftIi6I/vjo=;
b=Y0UyGm5hkDYVSdVWaT5R6mf6GMHhUkIXUhffEzKMd1MMWUwtaYbZsuE4lT6aQcIgVe
HVtYr7gPB4WbYDmHzVnt+JrhMpzXHJjEMoo34Nu39LbWUFzXGaPc7KN5Gs0pHqjlccDK
nxU7AqRooB7YOnSmmzpt0CJMdbQRiC9dEk8hK/nqI9ASFgcg8IzbVGXaProuJyBp4G92
BKNBQctjm8/+IepfsFzrpVN2GoXVp+RLSxNDvomE9h7u/0Cp8xAE6px4iDjKcjixUfoG
AhhrECw9NUGwraK1nK5AVncXXrf9xMMBEQqhseNZf4gBCt4BMpbH1a+sGO1JQPcjVISo
tXrg==

MIME-Version: 1.0

X-Received: by 10.170.161.2 with SMTP id c2mr7736640ykd.28.1421346386146; Thu,
15 Jan 2015 10:26:26 -0800 (PST)

Received: by 10.170.207.6 with HTTP; Thu, 15 Jan 2015 10:26:26 -0800 (PST)

In-Reply-To: <201501151712.27564.manfred.lochter@bsi.bund.de>

References: <20141201223720.12122.qmail@cr.yp.to>
<201501141444.45855.manfred.lochter@bsi.bund.de>
<CACsn0ckPnydBtjGiVCS0B_3=r8CeSKaDVTx6FgxT1CWCPBMMRA@mail.gmail.com>
<201501151712.27564.manfred.lochter@bsi.bund.de>

Date: Thu, 15 Jan 2015 10:26:26 -0800

Message-ID: <CACsn0cnS8fGeAKYU=Sit=J+--P-XKrXUtYLupjE7dt=Adme=pQ@mail.gmail.com>

From: Watson Ladd <watsonbladd@gmail.com>

To: "Lochter, Manfred" <manfred.lochter@bsi.bund.de>

Content-Type: text/plain; charset=UTF-8

Content-Transfer-Encoding: quoted-printable

Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/R_D-Z9khY5wBcqCFAJsZNjtajJE>

Cc: "cfrg@irtf.org" <cfrg@irtf.org>, "D. J. Bernstein" <djb@cr.yp.to>

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: Thu, 15 Jan 2015 18:26:31 -0000

On Thu, Jan 15, 2015 at 8:12 AM, Lochter, Manfred <manfred.lochter@bsi.bund.de> wrote: > Watson, > > I think we have a communication problem. At least I do not see any relation > between my remarks and your replies. For details please see below. > > Manfred Yes, you are correct: I was thinking of lattice attacks on signatures as instances of Bleichenbacher HNP solution. > > > > > __________ ursprüngliche Nachricht __________ > > Von: Watson Ladd <watsonbladd@gmail.com> > Datum: Mittwoch, 14. Januar 2015, 16:55:40 > An: "Lochter, Manfred" <manfred.lochter@bsi.bund.de> > Kopie: "cfrg@irtf.org" <cfrg@irtf.org>, "D. J. Bernstein" <djb@cr.yp.to> > Betr.: Re: [Cfrg] Mishandling twist attacks > >> On Wed, Jan 14, 2015 at 5:44 AM, Lochter, Manfred >> >> <manfred.lochter@bsi.bund.de> wrote: >> > Here we still seem to disagree, Dan. >> > >> > When we talked about this topic during RWC I had the impression that you >> > were only adressing DH and not signatures. Now I rechecked your >> > contribution and would like to make some comments: >> > >> > For signatures setting any bit may allow lattice-attacks. Do you have a >> > proof for your claim that "Setting the high bit of such a long nonce is >> > also perfectly safe."? I would be glad to have a look at it if you >> > provide a source. >> >> Remember how the Bleichenbacher attack actually works, and what the >> countermeasure recommended in standards is. >> >> The Bleichenbacher attack relies on the bias caused by reducing a >> number uniformly in the range [0, 2^n) modulo p, where p >> is close to 2^n. The bias is approximately 1/2^(n-log(p)). When n is >> about 2 log p, this becomes negligible. >> >> Adding the high bit means taking numbers in the range [2^(n-1), 2^n). >> The bias is now 1/2^(n-1-log(p)), which is still small. > > Watson, it is interesting that you mention Bleichenbacher's attack in reply on > my contribution that is dealing with securely randomized ephemeral keys. > > I did not even mention the generation of unbiased (mod group order) ephemeral > keys. Of course Dan's method gives keys that are sufficiently equally > distributed mod group order. > > But this is not my topic here. I was discussing Dan's proposal for blinding > ephemeral keys in the range 1..q-1 by adding a multiple of q and then setting > the msb to 1. > This may lead to lattice attacks as e.g. described by > Smart-Nguyen-Shparlinski. (Literature references are given in my posting from > October, 8, 2014.) > > You might also want to check Bleichenbachers talk during the rump session of > Crypto 2005 http://www.iacr.org/conferences/crypto2005/rumpSchedule.html I'm familiar with both of these sources. And both rely on being able to rewrite the equation describing how the nonce is generated to create an instance of the hidden number problem that's easy to solve. What I don't see is how you propose to do that for an ephemeral scalar generated by selecting x in [0, 2^(2\log q-1)) and using x+2^(2\log q). Knowing that we can subtract 2^(2\log q) modulo q, and then get x generated as a random number in [0, 2^(2\log q-1)) isn't enough to solve the hidden number problem; x is almost uniformly distributed modulo q. (If we know the bit for x in [0, q), then the range after subtracting is [0, q/2) which is enough) If we're talking about purely exponent randomization, rather than generation of nonces for signatures, then for 2^255-19 for instance, a product with a number of the form (2^254+z), z smaller, will be less than 2^510 and greater than 2^509-19*2^254. The need to have the high bit set doesn't substantially reduce the randomization. (Yes, this doesn't always do it: with a bit more analysis one can calculate the exact range of multipliers required) > >> >> > I' m not blaming the high bit, as you state, but the unnecessary tweak of >> > the nonce. The same effect can easily be achived by using dummy >> > operations. >> > >> > In addition this method does not make an implementors life easier. In >> > real world applications users will forget the additional bit and make >> > their implementations vulnerable to Timing Attacks. >> >> Implementors can also use powering computations that are constant >> time. The countermeasures you describe are frequently not implemented, >> and in many cases can be bypassed by cache-based attacks examining >> data flow, for instance. It's also not clear that they are necessary: >> the Montgomery ladder is extremely performant and has a uniform flow >> of operations. Comb based methods with protection can be trickier. > > Actually I'm not describing a countermeasure but discussing a proposed > countermeasure which I believe is dangerous. And I'm also stating that a full > ladder is better than adding an extra bit. What is your point exactly? My point is that DJB has always recommended the full Montgomery ladder, isn't talking about signatures in this message, and when he is talking about signatures, has a countermeasure that seems to me works. What do you think the proposal he's discussing is, and why do you think it's vulnerable? It's different from the ones attacked in the papers you mention, in ways that make those attacks not apply. In particular his proposal for signatures is to generated double length nonces, and then either set the high bit or use a possibly length revealing algorithm for scalar multiplication. This isn't affected by lattice based attacks. >> >> (For use in signatures, one would likely need to add on y coordinate >> reconstruction and an isogeny: the formulas for reconstruction exist >> out there, but I've not found a good source yet.) >> >> > The necessary length of nonces depends on the stucture of the underlying >> > prime field and of the order of the chosen group order. Whilst for NIST >> > curves 32 bits seem to be OK, for general n-bit curves over special prime >> > fields n bits of blinding are necessary. This blinding length is then not >> > "an extra long nonce" but the minimum-length nonce to withstand SCA. >> >> You appear to be confusing two issues: generation of signature nonces >> and computing scalar multiples securely. Using a double-length nonce >> solves the secure generation problem. When it comes to computing >> scalar multiples, blinding of the scalar involves adding a random >> multiple of the >> prime. Of course, when this is a nonce used in a signature, produced >> by reducing a double length nonce, adding back a random multiple might >> as well be using the original nonce. > > Again: I'm talking about Dan's proposal. You brought in Bleichenbacher which > is a different topic. But please do not blame me for mixing up things. >> >> In particular, the length of extra bits required for Bleichenbacher >> defense is largely independent of the prime. The claimed superiority >> of random primes for blinding is in doubt: several people have pointed >> to papers breaking this protection unless we use 256, not 32 extra >> bits. Certainly for the NIST primes 32 bits extra will not randomize >> significant blocks of bits. > > Again: I am not talking about the Bleichenbacher-bias-attack! > If 32 for NIST are sufficient is an implementation issue. As a minimum 32 are > needed. The situation is different for primes like the 25519 prime, where the > gap between 1s is much larger. Consequently curves over these fields need > more randomisation. In principle I do not see which part of my statement you > think is incorrect. Who is several people and what exactly did they say? One NIST prime is = 2^256 -2^224 + 2^192 + 2^96-1. Adding a 32 bit multiple of this prime doesn't obscure bits between the 96th and 32nd bit. This seems to be what https://www.nics.uma.es/pub/acns2011/files/ppt/2-2.pdf exploits, for instance. http://link.springer.com/article/10.1007/s13389-014-0081-y#page-1 seems to exploit similarly small degrees of randomization, even on SPA protected devices. >> >> > I admit, that for some implementations (depending on hardware used, and >> > other factors) your method may still allow faster implementations than >> > random prime curves with maximum necessary nonce length. >> > >> > However implementation security may not be improved: >> > >> > (a) Users will change to shorter nonces to become even faster. They be >> > then use a too short nonce. >> > (b) Even if the curves support constant-time ladders, there is no >> > guarantee that users will implement these ladders. >> >> One can use a uniform nonce in [0, p), obtained by rejection sampling. >> I don't see how this issue doesn't also apply to random primes. > > There is no connection between my statement and my comment. >> >> Yes, implementors in the pay of the NSA or BND can always make >> "mistakes". However, we've described the constant-time ladder in the >> draft and explained why it should be used. When it comes to >> signatures, I expect that a similar amount of attention will be paid. > > And other implementors will also make mistakes. Anyhow: What do you want to > imply here? I'm not implying anything. I don't see how random primes improve the issue, or why the countermeasures you are bringing up are better than the ones proposed by DJB. In particular, why wouldn't users of random prime curves reduce nonce size and disable countermeasure to timing attacks for the same reasons they would on Curve25519? > > My whole posting is dealing with Dan's proposal for signatures (!). It is not > connected to any of your papers. >> >> Sincerely, >> Watson Ladd >> >> > Manfred >> > >> > >> > >> > >> > >> > >> > >> > __________ ursprüngliche Nachricht __________ >> > >> > Von: "D. J. Bernstein" <djb@cr.yp.to> >> > Datum: Montag, 1. Dezember 2014, 23:37:20 >> > An: cfrg@irtf.org >> > Kopie: >> > Betr.: Re: [Cfrg] Mishandling twist attacks >> > >> >> 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 >> >> >> >> _______________________________________________ >> >> Cfrg mailing list >> >> Cfrg@irtf.org >> >> http://www.irtf.org/mailman/listinfo/cfrg >> > >> > -- >> > 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: manfred.lochter@bsi.bund.de >> > Internet: >> > www.bsi.bund.de >> > www.bsi-fuer-buerger.de >> > >> > _______________________________________________ >> > Cfrg mailing list >> > Cfrg@irtf.org >> > http://www.irtf.org/mailman/listinfo/cfrg > > -- > 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: manfred.lochter@bsi.bund.de > Internet: > www.bsi.bund.de > www.bsi-fuer-buerger.de -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin

- [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Michael Hamburg
- Re: [Cfrg] Mishandling twist attacks Alyssa Rowan
- Re: [Cfrg] Mishandling twist attacks Watson Ladd
- Re: [Cfrg] Mishandling twist attacks Samuel Neves
- Re: [Cfrg] Mishandling twist attacks David Leon Gil
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Ilari Liusvaara
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks Watson Ladd
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks Watson Ladd