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

From: Nigel Smart <[email-masked]>
Date: Sat, 28 Jun 2014 17:58:16 +0100

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
-- 
Prof. Nigel P. Smart         | Tel +44 (0)117 9545163
Computer Science Department, | Fax +44 (0)117 9545208
Woodland Road,               | Email [email-masked]
Bristol, BS8 1UB, UK         | http://www.cs.bris.ac.uk~nigel

---

From: Watson Ladd <[email-masked]>
Date: Sat, 28 Jun 2014 10:01:33 -0700

> in this respect, the above choices of p would be even worse.

Simple solution: write constant time software. The principal of side
channel attacks being established, one simply eliminates them all.

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 28 Jun 2014 18:30:45 +0100

On 28/06/2014 18:01, Watson Ladd wrote:

> Simple solution: write constant time software. The principal of
> side channel attacks being established, one simply eliminates them
> all.

And, of course, it would be remiss of me not to point out that all the
good Curve25519 implementations are both fast and constant-time, the
curve having been specified with the constant-time Montgomery ladder
in mind in the first place. This is actually an area where 25519 wins big.

(It should also be pointed out that constant-time over Weierstrass
curves is possible, with enough care; see Langley/Möller/Kasper's
implementation contributed to OpenSSL. I have yet to see any
implementation capable of doing such a feat with arbitrary curves.)

As far as code quality and reuse is concerned, what we've learned from
things like Heartbleed I think is that "many eyes make bugs shallow"
is only true when the eyes actually _look_ at the code. I don't think
monoculture is to blame (we could just as easily have 10 bad
implementations as 1), just complacency and a lack of sufficient
auditing. I'd be much happier with a few implementations that everyone
looks at very closely than many which aren't as well-audited.

- -- 
/akr

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 28 Jun 2014 13:06:20 -0700

> So unifying in this respect would be a bad idea IMHO.

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.