Re: [Cfrg] Mishandling twist attacks

[Watson Ladd <[e-mail]>]

On Wed, Jan 14, 2015 at 5:44 AM, Lochter, Manfred
<[e-mail]> 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.

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

(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.

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.

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

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.

Sincerely,
Watson Ladd

>
> Manfred
>
>
>
>
>
>
>
> __________ ursprüngliche Nachricht __________
>
> Von:            "D. J. Bernstein" <[e-mail]>
> Datum:  Montag, 1. Dezember 2014, 23:37:20
> An:             [e-mail]
> 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
>> [e-mail]
>> 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: [phone] 5643
> Telefax: [phone] 5643
> E-Mail: [e-mail]
> Internet:
> www.bsi.bund.de
> www.bsi-fuer-buerger.de
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin