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

From: Johannes Merkle <[email-masked]>
Date: Fri, 4 Jul 2014 16:59:37 +0200

Alyssa Rowan wrote on 27.06.2014 08:46:
> Brainpool has already generated a set of 'random' primes, but random primes are extremely slow to implement - and
> in the case of Brainpool, the 256-bit curve has extremely unfortunate lack of twist security, so any implementation
> that tries to skip validation is in really big trouble.

Why should anyone try to skip validation? In order to improve performance by less than 1%?

-- 
Johannes

---

From: Watson Ladd <[email-masked]>
Date: Fri, 4 Jul 2014 08:15:32 -0700

> Why should anyone try to skip validation? In order to improve performance by less than 1%?

Implementations frequently expose an API where validation is separate
from group operations, and people
just forget to make the call sometimes.

Furthermore, with anything other than a compressed format it's not
just twist security, but any security that failure of point validation
harms.
I send point on a curve with smooth order, and extract the key. I send
point on curve with small order, and dictate the key, etc.

Twist security matters for Joyce-Briers ladders only, as far as I know
on Weierstrass curves. Other formulas use the y coordinates.

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

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

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 04 Jul 2014 14:09:11 -0700

> just forget to make the call sometimes.

However, point validation, or validation of an element in a DH group 
(http://tools.ietf.org/html/rfc6989#section-2.2) is a common requirement 
for a crypto implementation. FIPS 140-2 crypto module algorithm 
validation includes point validation testing 
(http://csrc.nist.gov/groups/STM/cavp/documents/dss2/ecdsa2vs.pdf 
requires tests from Section A.4.2 of ANSI X9.62)

An implementation that doesn't do required EC point checks may have 
other flaws at higher levels. Replacing a low-level crypto primitive 
with a stronger one does not necessarily make the entire stack secure. 
Some may argue that this obscures the results of a security audit.

In reality all we are talking about is plugging (x,y) in the curve 
equation and checking that the two sides match. As was pointed out, when 
compression is used, this check is "forced".

> point on curve with small order, and dictate the key, etc.

It would be good to list what does twist security mean for TLS. 
http://safecurves.cr.yp.to/twist.html references the paper that uses an 
ElGamal decryption oracle. The attack will reveal the decryption scalar.

How does this translate to TLS? I assume we are talking about ECDH only.

Regarding dictating the key, it seems that a (corrupt) peer can always 
limit his private key to a small value and thus dictate the shared 
secret to be close to another peer's public key.

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 7 Jul 2014 14:48:53 +0200

> on Weierstrass curves. Other formulas use the y coordinates.

Exactly, and as DJB points out, the Joyce-Briers ladder "requires 19 field operations per bit, many more field
operations than standard addition chains for short Weierstrass curves" [1]. Therefore, "twist security" is irrelevant
for Weierstrass curves unless someone decides to implement the Joyce-Briers ladder despite of its inferior performance.

I was objecting to Alyssa's statement "in the case of Brainpool, the 256-bit curve has extremely unfortunate lack of
twist security", which, IMHO, grossly exaggerates the importance of twist security. Lack of "twist security" is an issue
for Weierstrass curves only in circumstances where implementors choose an unusual technique and screw up one essential
part.

[1] http://safecurves.cr.yp.to/ladder.html
-- 
Johannes

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 07 Jul 2014 14:14:10 +0100

Well, yes - combined with an unusual ladder choice (which one might choose for constant-time, albeit not the best choice now) and a critical but easily-overlooked omission.

I appreciate there's not much we can do about implementers screwing up badly - but if we do have two primitives of about equal value and one fails catastrophically to a simple mistake that another does not, then as a matter of defence in depth, I'd generally prefer the more resilient one?

So it is with Brainpool: its twist security is poof (by pure chance) so such a mistake would be more hazardous than is typical. How likely that mistake would be is another matter, and I accept your point there that it'd be a rare decision and hopefully would be noticed in any review.

I still don't think Brainpool's fast enough to drive adoption, next to competition like 25519 and the Microsoft curves.

On 4 July 2014 15:59:37 BST, Johannes Merkle <[email-masked]> wrote:

>> in the case of Brainpool, the 256-bit curve has extremely unfortunate lack of twist security, so any implementation that tries to skip validation is in really big trouble.

- --
/akr

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 7 Jul 2014 18:00:05 +0200

Alyssa Rowan wrote on 07.07.2014 15:14:
> Well, yes - combined with an unusual ladder choice (which one might choose for constant-time, albeit not the best
> choice now) and a critical but easily-overlooked omission.
> 
> I appreciate there's not much we can do about implementers screwing up badly - but if we do have two primitives of
> about equal value and one fails catastrophically to a simple mistake that another does not, then as a matter of
> defence in depth, I'd generally prefer the more resilient one?
> 
> So it is with Brainpool: its twist security is poof (by pure chance) so such a mistake would be more hazardous than
> is typical. How likely that mistake would be is another matter, and I accept your point there that it'd be a rare
> decision and hopefully would be noticed in any review.
> 

In this discussion, it is important to focus on the most essential arguments. "Twist security" is not among them, as
it only applies to very special cases and poor implementations. Montgomery and Edwards curves have other potential
problems due the non-trivial co-factor, so there is always something a sloppy implementor can screw up.

Computational performance is a valid argument, and where performance is your main criteria, your may go for special
primes and non-Weierstrass curves; but there are sufficient circumstances, where performance is not the principal
criteria. IMHO, it is wise to maintain curves with different properties to accommodate different demands.

-- 
Johannes

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Mon, 7 Jul 2014 12:08:12 -0400

On Jul 7, 2014, at 12:00 , Johannes Merkle <[email-masked]> wrote:
>> ......I appreciate there's not much we can do about implementers screwing up badly - but if we do have two primitives of about equal value and one fails catastrophically to a simple mistake that another does not, then as a matter of defense in depth, I'd generally prefer the more resilient one?.....
> In this discussion, it is important to focus on the most essential arguments. "Twist security" is not among them, as it only applies to very special cases and poor implementations. Montgomery and Edwards curves have other potential problems due the non-trivial co-factor, so there is always something a sloppy implementor can screw up.
> 
> Computational performance is a valid argument, and where performance is your main criteria, your may go for special primes and non-Weierstrass curves; but there are sufficient circumstances, where performance is not the principal criteria. IMHO, it is wise to maintain curves with different properties to accommodate different demands.

+1