Re: [Cfrg] Mishandling twist attacks

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.

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.

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. 

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. 

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