Re: [TLS] Twist security for brainpoolp256r1

[Johannes Merkle <[e-mail]>]

>>>  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.
> 
> 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?

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.


> 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.    

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