Re: [TLS] Twist security for brainpoolp256r1

[Manuel Pégourié-Gonnard <[e-mail]>]

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.