Subject: [TLS] Twist security for brainpoolp256r1

From: Oleg Gryb <[email-masked]>
Date: Tue, 11 Nov 2014 04:02:23 +0000 (UTC)

Hi Daniel and TLS community,
I was going through SafeCurves pages recently and wanted to ask a question about brainpoolP256r1's twist security. According to this research http://safecurves.cr.yp.to/twist.html,,  a combined cost of attacks on brainpoolP256t1, which is a P256r1's "twist" is rather low. At the same time it's obvious that small-group-attack is not applicable, because "h=1" is a requirement for all brainpool curves including the one under consideration.
The other two "invalid-curve" attacks should be mitigated by openssl controls, since latter does have a point-on-the-curve validation (e,g. see EC_POINT_is_on_curve function and its usage in the latest openssl stable versions).
Given all that, can I consider the curve as secure? Are there any other attacks that I should consider before adopting the curve as a standard?
Thank you also for the wonderful research related to Curve25519 and Curve41417. They both seem to be perfect. I hope openssl community will adopt them soon.
Oleg

---

From: Johannes Merkle <[email-masked]>
Date: Tue, 11 Nov 2014 19:49:29 +0100

> I was going through SafeCurves pages recently and wanted to ask a question about brainpoolP256r1's twist security.
> According to this research http://safecurves.cr.yp.to/twist.html,, <http://safecurves.cr.yp.to/twist.html>  a combined
> cost of attacks on brainpoolP256t1, which is a P256r1's "twist" is rather low. At the same time it's obvious that
> small-group-attack is not applicable, because "h=1" is a requirement for all brainpool curves including the one under
> consideration.

This is a misunderstanding. The term "twist security" refers to non-quadratic twists (B/u)y^2=x^3+Ax^2+x, where u is a
non-square in F_p. RFC 5639 considers "quadratic twist", where u is a square in F_p. Quadratic twists are isomorphic to
the original curve and provide equivalent security. Therefore, brainpoolP256t1 is as secure as brainpoolP256r1. In
contrast, the non-quadratic twists of brainpoolP256r1 are not secure, because their group order does not have a large
enough prime factor, i.e., the cofactor is huge.

> 
> The other two "invalid-curve" attacks should be mitigated by openssl controls, since latter does have a
> point-on-the-curve validation (e,g. see EC_POINT_is_on_curve function and its usage in the latest openssl stable versions).
> 

Twist security is only relevant, if you use an arithmetic on the x-coordinate only (Brier-Joye ladder) and don't perform
point-on-the-curve validation. I am quite sure that openssl avoids both, i.e., computes on both coordinates and performs
point-on-the-curve validation. Therefore, twist security is irrelevant here.

x-coordinate arithmetic is generally quite slow for Weierstrass curves, and point-on-the-curve validation is mandated by
the relevant standards. Therefore, twist security should be hardly an issue anywhere.

-- 
Johannes

---

From: Oleg Gryb <[email-masked]>
Date: Tue, 11 Nov 2014 20:11:16 +0000 (UTC)

>>  According to this research http://safecurves.cr.yp.to/twist.html,, 
> <http://safecurves.cr.yp.to/twist.html>  a combined
>>  cost of attacks on brainpoolP256t1, which is a P256r1's 
> "twist" is rather low. At the same time it's obvious that
>>  small-group-attack is not applicable, because "h=1" is a 
> requirement for all brainpool curves including the one under
>>  consideration.
> 
> This is a misunderstanding. The term "twist security" refers to 
> non-quadratic twists (B/u)y^2=x^3+Ax^2+x, where u is a
> non-square in F_p. RFC 5639 considers "quadratic twist", where u is a 
> square in F_p. Quadratic twists are isomorphic to

> enough prime factor, i.e., the cofactor is huge.

Thanks for explaining all that, but I just want to clarify it a bit further.

What 2^44 means for the brainpoolP256t1 in DJB table?

brainpoolP256t1 False 2^44.5

Is it related to non-quadratic twists only, derived either from brainpoolP256r1 or brainpoolP256t1?

>> 
>>  The other two "invalid-curve" attacks should be mitigated by 
> openssl controls, since latter does have a
>>  point-on-the-curve validation (e,g. see EC_POINT_is_on_curve function and 
> its usage in the latest openssl stable versions).
>> 
> 
> Twist security is only relevant, if you use an arithmetic on the x-coordinate 
> only (Brier-Joye ladder) and don't perform
> point-on-the-curve validation. I am quite sure that openssl avoids both, i.e., 
> computes on both coordinates and performs
> x-coordinate arithmetic is generally quite slow for Weierstrass curves, and 
> point-on-the-curve validation is mandated by

In other words, I don't need to be concerned about "invalid-curve" attacks in any of openssl's ECC implementations, right?

The last question that I have is related to brainpool curves implementations in openssl. It looks like they are available only in version 1.0.2, which is a beta now and I would be hesitant to use beta in any production deployments, so what I tried was backporting the brainpoolP256r1 only from 1.0.2 to the latest stable 1.0.1j and it worked perfectly well. I was even able to statically compile my backported version with some open source web application servers, configured brainpoolP256r1 as a defualt and didn't see any problems with that.

My qs is - can you envision any other problems with this "backporting" approach? One thing that I was thinking about was a possible performance impact if there is any barinpool's specific optimization in 1.0.2. I've seen some signs of EC arithmentic's optimization for NIST P-256 in the latest stable version, but I didn't find anything like that for brainpool curves.    

Thanks for you answers. They were very helpful and encouraging. I hope that openssl community will not use the controversial NIST P-256 as a default in their future releases.  

> -- > Johannes

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 11 Nov 2014 22:55:07 +0100

> What 2^44 means for the brainpoolP256t1 in DJB table?
It's the cost of an attack for an attacker who can force you to accept a point
that is not on the curve but on its non-quadratic twist.

In the context of TLS (with the currently available curves and point formats)
what safecurves calls "twist security" is totally irrelevant: either the
implementation validates that points are on the curve, or you're vulnerable to
an invalid curve attack which is much more powerful than a twist attack.

Any decent implementation (which includes OpenSSL and some others) of ECC with
TLS will check that points belong on the intended curve.

> The last question that I have is related to brainpool curves implementations in openssl.

This question is more suited to the OpenSSL list, as it is specific to this
implementation. This list is about the protocol.

Manuel.

---

From: Oleg Gryb <[email-masked]>
Date: Tue, 11 Nov 2014 22:44:03 +0000 (UTC)

> It's the cost of an attack for an attacker who can force you to accept a 

> point

It answers my question, thanks.

> implementation. This list is about the protocol.

What about EC arithmetic optimization specific to a curve? Is it a kind of qs that is appropriate for this forum? If it is, probably somebody can provide pointers about optimizations that have been already implemented for the curve in the subject. I think, efficiency should be an important consideration of this protocol.

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 12 Nov 2014 15:56:55 +0100

> Is it related to non-quadratic twists only, derived either from brainpoolP256r1 or brainpoolP256t1?

As Manuel has explained its the security level of the non-quadratic twist. It is NOT the security of the quadratic
twists, which is the same as of the original brainpoolP256r1.

Background: All quadratic twists are isomorphic (equivalent) to each other. And each quadratic twist (i.e.
brainpoolP256t1 and brainpoolP256r1) has the same set of non-quadratic twists, which are also all equivalent to each
other (they are quadratic twists of each other). So we have two sets of curves: The quadratic twists of brainpoolP256r1
(which contains brainpoolP256t1) and the set of non-quadratic twists of brainpoolP256r1. Any curve from the former set
(including brainpoolP256t1) is as secure as brainpoolP256r1. And any curve from the second set (the non-quadratic
twists) have a group order that factors to moderately sized primes and are, thus, insecure.  But nobody would use the
non-quadratic twists, except potentially in an invalid-curve attack.

> In other words, I don't need to be concerned about "invalid-curve" attacks in any of openssl's ECC implementations, right?

If openssl uses a proper ECC implementation, yes. If not, you're in trouble anyway.

> My qs is - can you envision any other problems with this "backporting" approach? One thing that I was thinking about was a possible performance impact if there is any barinpool's specific optimizat…

My guess (and its nothing more than a guess) is that they just added the parameters and did not change the
implementation. If this holds true, your approach should work, provided that you properly transferred all relevant
parameters and identifiers.

But this is something, you need to confirm with the openssl developers.

-- 
Viele Grüße,
Johannes

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 12 Nov 2014 18:12:09 +0100

> non-quadratic twists, except potentially in an invalid-curve attack.

As Watson Ladd just pointed out to me, the terms "quadratic twists" and "non-quadratic twists" are not common in math
textbooks. For a curve in Weierstrass form E: y^2 = x^3 + a*x  + b mod p, the term twist denotes a curve  E': y^2 = x^3
+ v^2*a*x + v^3* b mod p.
 - If v is a quadratic residue, i.e., if there is a w with w^2 = v mod p, then E and E' are isomorphic mod p and thus
have equivalent security.
 - If v is a quadratic non-residue, E' is not isomorphic to E and the curve orders satisfy |E| + |E'| = p+2.
Text books often discuss only the case of quadratic non-residues (e.g. Blake, Seroussi, Smart).

In the case of the Brainpool curves, the twists mentioned in RFC 5639 are twists via a quadratic residue and have the
same security as the respective random curves.
-- 
Johannes

---

From: Oleg Gryb <[email-masked]>
Date: Thu, 13 Nov 2014 06:35:21 +0000 (UTC)

----- Original Message -----
> From: Johannes Merkle <[email-masked]>
> To: Oleg Gryb <[email-masked]>; "[email-masked]" <[email-masked]>
> Cc: 
> Sent: Wednesday, November 12, 2014 9:12 AM
> Subject: Re: [TLS] Twist security for brainpoolp256r1
> 
> As Watson Ladd just pointed out to me, the terms "quadratic twists" 
> and "non-quadratic twists" are not common in math

> same security as the respective random curves.

Thanks, very helpful. Just to summarize yours and Manuel's notes in regard of quadratic non-residue, or non-quadratic twists (as they are called in other emails), they can be used as a source of malicious EC points to run invalid-curve attacks on the original curves, but since all implementations  compliant with X9* standards including openssl must have point-on-curve validation, invalid-curve attacks and small-group attacks become irrelevant when it comes to brainpoool's openssl implementation. Note - small group attacks are not possible, because of a different reason: cofactor for all brainpool curves is equal to 1.     

Efficiency is still an issue for me. Since curves such as NIST P-256 do have optimized EC arithmetic, but nothing like that is available for brainpool curves, it would be nice to know what the delta is. If it's up to 30% percent, I would probably ignore, if it's essentially more than that, I might need to re-consider my choice. If no quantitative data is available, I would probably need to write/run my own tests.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 13 Nov 2014 10:21:29 +0100

On 13/11/2014 07:35, Oleg Gryb wrote:
> Thanks, very helpful. Just to summarize yours and Manuel's notes in regard of
> quadratic non-residue, or non-quadratic twists (as they are called in other
> emails), they can be used as a source of malicious EC points to run
> invalid-curve attacks on the original curves, but since all implementations
> compliant with X9* standards including openssl must have point-on-curve
> validation, invalid-curve attacks and small-group attacks become irrelevant
> when it comes to brainpoool's openssl implementation.

The situation is actually a bit more complex. Here is a version that's still a
bit simplified but closer to the truth: let's say there are two kinds of
protocols (or curve representations):

1. Those who use both coordinates of the points.
2. Those who use only the x coordinate.

With the first type, an attacker can for the point to be on (almost) any curve
unless the implementation validates that the point lies on the intended curve.
Here it doesn't matter if the twist* is secure, this it's not easier for the
attacker to force a point on the twist than on any other curve, potentially much
weaker.

With the second type, the only curve other than the intended one that the
attacker can force is the twist*. So, if the twist happens to be secure, the
implementation can skip point validation: the attacker will not gain anything by
forcing you to use the twist.

* meaning what Johannes called the non-quadratic twist.

TLS currently is in the first category, which means twist security is not
relevant, because:
- either the implementation validates points (which it must),
- or the attacker can force *much* weaker curves than the twist.

> Note - small group
> attacks are not possible, because of a different reason: cofactor for all
> brainpool curves is equal to 1.
> 
Yes. While we're at it, let's note that the whole purpose of forcing another
curve is to do a small subgroup attack by picking a curve that does have small
subgroups.

> Efficiency is still an issue for me. Since curves such as NIST P-256 do have
> optimized EC arithmetic, but nothing like that is available for brainpool
> curves, it would be nice to know what the delta is. If it's up to 30%
> percent, I would probably ignore, if it's essentially more than that, I might
> need to re-consider my choice. If no quantitative data is available, I would
> probably need to write/run my own tests.
> 
Openssl has a "speed" command that should be helpful. I'd expect a difference
higher than 30%.

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 13 Nov 2014 07:42:59 -0800

> 2. Those who use only the x coordinate.

The coordinates used on the wire do not determine the calculations
used by an implementation. An interoperable implementation of TLS
could use the Brier-Joyce ladder on x-coordinates only, and take a
randomly chosen square root for use as the y-coordinate, validating
signatures through a different method. This would be of interest in
certain side-channel attack scenarios, as the Brier-Joyce ladder is
easier to protect.

Most implementations don't do this, so the rest of your email is correct.

Sincerely,
Watson Ladd

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 13 Nov 2014 16:53:01 +0100

On 13/11/2014 16:42, Watson Ladd wrote:
> used by an implementation.

Sure. That's why I said that the above was still a bit simplified.

> An interoperable implementation of TLS
I hope that an implementer who knows this somewhat exotic option and chooses to
use it for its side-channel properties is also sufficiently knowledgeable and
security concious to properly validate points...

> Most implementations don't do this, so the rest of your email is correct.
Thank you.

Manuel.

---

From: Oleg Gryb <[email-masked]>
Date: Fri, 14 Nov 2014 22:46:13 +0000 (UTC)

----- Original Message -----
> From: Manuel Pégourié-Gonnard <[email-masked]>
> To: Oleg Gryb <[email-masked]>; Johannes Merkle <[email-masked]>; "[email-masked]" <[email-masked]>
> Cc: 
> Sent: Thursday, November 13, 2014 1:21 AM

> Openssl has a "speed" command that should be helpful. I'd expect a 

I had to change 'speed.c' in openssl to add barinpoolp256r1 (by default it simply not there). The difference for both ecdsa (signature) and ecdh (diffie-hellman-merkle key exchange) is less than 5%, so P-256 'optimization' in openssl is definitely overrated. I think, I'm good to go with Brainpool.

Doing 256 bit sign ecdsa's for 10s: 92012 256 bit ECDSA signs in 10.00s 
Doing 256 bit verify ecdsa(nistp256)'s for 10s: 26294 256 bit ECDSA verify in 10.00s
Doing 256 bit sign ecdsa's for 10s: 88745 256 bit ECDSA signs in 10.00s 
Doing 256 bit verify ecdsa(brainpoolP256r1)'s for 10s: 24939 256 bit ECDSA verify in 10.00s
256 bit ecdsa (nistp256)   0.0001s   0.0004s   9201.2   2629.4
256 bit ecdsa (brainpoolP256r1)   0.0001s   0.0004s   8874.5   2493.9

Doing 256 bit  ecdh(nistp256)'s for 10s: 31820 256-bit ECDH ops in 10.00s
Doing 256 bit  ecdh(brainpoolP256r1)'s for 10s: 29748 256-bit ECDH ops in 10.00s
256 bit ecdh (nistp256)   0.0003s   3182.0
256 bit ecdh (brainpoolP256r1)   0.0003s   2974.8

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 15 Nov 2014 08:05:56 +0200

On Fri, Nov 14, 2014 at 10:46:13PM +0000, Oleg Gryb wrote:
> I had to change 'speed.c' in openssl to add barinpoolp256r1 (by default
> it simply not there). The difference for both ecdsa (signature) and ecdh
> (diffie-hellman-merkle key exchange) is less than 5%, so P-256 'optimization'
> in openssl is definitely overrated. I think, I'm good to go with Brainpool.

I did some quick benchmarking locally. The new code does ~2.4x(!) the number
of ECDH/ECDSA (all area accelerated by similar factor) ops per second compared
to the old.

(Intel i7 Ivy Bridge, so AVX but no AVX2).

> 256 bit ecdh (brainpoolP256r1)   0.0003s   2974.8

- What OpenSSL version that is based on?
- What build options?
- What CPU?

Those number don't pass my sanity checks if I assume new OpenSSL code:
- Difference between special prime and random prime is too small,
  hinting bad implementation of special prime.
- Extrapolation from numbers I got gives unreasonably low CPU speed.
 
If I estimate based on numbers I got (which is probably off for pre-AVX
or AVX2), I would estimate new p256 has about 2.5x the performance of
Brainpool.

-Ilari

---

From: Alyssa Rowan <[email-masked]>
Date: Sat, 15 Nov 2014 08:50:35 +0000

On 14 November 2014 22:46:13 GMT+00:00, Oleg Gryb <[email-masked]>
wrote:

> I had to change 'speed.c' in openssl to add barinpoolp256r1 (by 
> default it simply not there). The difference for both ecdsa 
> (signature) and ecdh (diffie-hellman-merkle key exchange) is less 
> than 5%, so P-256 'optimization' in openssl is definitely
> overrated.

No, you just don't have the optimisation turned on: that's using the
old unoptimised generic prime routine.

If you're on 1.0.1, Configure/make depend/make it with flag
enable-ec_nistp_64_gcc_128 (if you're on x86-64) to use the agl/Emilia
Kasper optimised secp224r1/secp256r1/secp521r1 routines, because
they're not on by default.

Or try the 1.0.2 trunk for Intel's even faster AVX2 assembly routines.

You will need to make sure it's using the correct library version.

P256 can go at least twice as fast as that, and then some, and that
should be about what you're seeing.

Brainpool, unfortunately, just can't go that fast; the pseudo-random
primes don't have a structure which allows optimisation. But if a
generic multiplier is OK for your performance needs (like you're using
here, or if you have hardware which can do it well), Brainpool will be
okay.

- -- 
/akr.

---

From: Oleg Gryb <[email-masked]>
Date: Sat, 15 Nov 2014 16:30:40 +0000 (UTC)

----- Original Message -----
> From: Alyssa Rowan <[email-masked]>
> To: Oleg Gryb <[email-masked]>; Oleg Gryb <[email-masked]>; Manuel Pégourié-Gonnard <[email-masked]>; Johannes Merkle <[email-masked]>; "[email-masked]" <[email-masked]>
> Cc: 
> Sent: Saturday, November 15, 2014 12:50 AM

Thanks, it's very helpful and I'll try. Judging from multiple Linux forums it's recommended and its estimated speed increases is 2x for ECDHE, less so for ECDSA though. I'm wondering why no-ec_nistp_64_gcc_128 is still a default. Are there any indications that either multiplier algorithm or its openssl implementation are error prone?

---

From: Oleg Gryb <[email-masked]>
Date: Sat, 15 Nov 2014 19:14:37 +0000 (UTC)

----- Original Message -----
> From: Oleg Gryb <[email-masked]>
> To: Alyssa Rowan <[email-masked]>; Oleg Gryb <[email-masked]>; Manuel Pégourié-Gonnard <[email-masked]>; Johannes Merkle <[email-masked]>; "[email-masked]" <[email-masked]>
> Cc: 
> Sent: Saturday, November 15, 2014 8:30 AM
>>  To: Oleg Gryb <[email-masked]>; Oleg Gryb 
> <[email-masked]>; Manuel Pégourié-Gonnard <[email-masked]>; 
> Johannes Merkle <[email-masked]>; "[email-masked]" 
> <[email-masked]>
>>  Cc: 
> Thanks, it's very helpful and I'll try. Judging from multiple Linux 
> forums it's recommended and its estimated speed increases is 2x for ECDHE, 
> less so for ECDSA though. I'm wondering why no-ec_nistp_64_gcc_128 is still 
> a default. Are there any indications that either multiplier algorithm or its 
> openssl implementation are error prone?

Yet another thought that I believe, I've seen somewhere in a an EC discussion. If there is a shortcut that allows simplifying EC arithmetic significantly, doesn't it mean that an attacker might be in a very good position to eventually find a way of decreasing a cost of attack significantly as well?

I understand that this is just a "common sense" argument, but I think that it correlates well with EC's "spectral weakness" discussed by Dan Brown, DJB and others here: 
http://www.ietf.org/mail-archive/web/tls/current/msg10169.html