Re: [TLS] On Curve25519 and other possibilities (e.g. ietf256p, ietf384p, ietf521p,

[Andrey Jivsov <[e-mail]>]

On 06/28/2014 09:58 AM, Nigel Smart wrote:
> Hi
>
>> One way to attempt to unify the diverse world of ECC curves is to focus
>> on the underlying field, as opposed the curve itself. Consider Fp
>> operations with p=2^255-19 or p=2^256-189. In other words, for
>> n={256,384,512}, chose the closest C: p=2^n-C is a prime and make this p
>> "MUST". People who demand random primes will have to play along and
>> accept less "randomness" in their curves.
>
> Alas there could be some issues with primes close to powers of two.
> See our recent side channel attacks on EC-DSA with the Eurovision
> titles on ePrint "Just a Little Bit" etc. Such a p forces the
> group order to also be close to a power of two (by Hasse's Theorem).
>
> Whilst these papers show there are problems with the NIST choices
> in this respect, the above choices of p would be even worse.
>
> So unifying in this respect would be a bad idea IMHO.
>
> Nigel

The paper https://eprint.iacr.org/2014/434.pdf describes a technique to 
recover the bits of a secret intermediate value used in the ECDSA 
algorithm. These bits are in the high half of the large integer. This 
improved method works when EC order is close to 2^n, which is the case 
with F(p): p=2^n-C due to the relationship between the two per Hasse 
theorem.

A random p will have high half of its bits random, and this will deny 
such an enhanced side-channel attack. A generalized pseudo-mersenne 
prime should help as well.

The exploited side channel in the paper is provided by the ECDSA 
algorithm, through the ECC field scalar multiplication. In other words, 
we are not talking about a side channel in an implementation of an F(p) 
being exploited.

IMO fixing the p will help with high-quality implementations of F(p).

What this p is, is the question to answer based on pros and cons. p that 
allows faster operations is inevitably less secure because the 
Pollard-rho on the ECC is faster with such a p. A safest p cannot save 
an ECC implementation from side-channel bugs.