Re: [TLS] Twist security for brainpoolp256r1

[Oleg Gryb <[e-mail]>]

----- Original Message -----
> From: Johannes Merkle <[e-mail]>
> To: Oleg Gryb <[e-mail]>; "[e-mail]" <[e-mail]>
> 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
> 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.

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.


> > -- 
> Johannes
>