Re: [TLS] Twist security for brainpoolp256r1

Oleg Gryb <> Tue, 11 November 2014 20:11 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 8864C1A0231 for <>; Tue, 11 Nov 2014 12:11:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.695
X-Spam-Status: No, score=-0.695 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.594, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id FX8ZK6uuqON2 for <>; Tue, 11 Nov 2014 12:11:20 -0800 (PST)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 8868F1A01CB for <>; Tue, 11 Nov 2014 12:11:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=s2048; t=1415736679; bh=gzci818qRjv0xM/NgSkaiEsxLN1RHtx7yAZYXJRcc7c=; h=Date:From:Reply-To:To:In-Reply-To:References:Subject:From:Subject; b=MfVeCgZQAFJ/2uoaAkxcVLt1mUURZqiR3PJDQ/wOndAmRM7ZD6yNuDH3J2EFZU6zqrmJyND/9/0aixlWGbD/uGwVVTNj+RUiSZ2PUFfxxLKH2J5A9sGCkThCI2IonGV2S8+/ERrV17SHFNu3niCLbf+GVRiOOW3AdP8HRm6OhWZ6hg2HgGVV9//juX1Zcc6nyHk53/lks3mGJtZLx/6INU5RWlzpCRMm7UzxK6mjFz/S40VtwLWvfNw6epqvbld37LoD1PaUv/utJtr3SpUyOALYr4gGyEMk8u1yyLHb3sffGXInzILPJR7cDq4m2mFi52AiwXSEDAl0XaTfG/pxig==
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s2048;; b=WzekA/JJYAM/l9ucSmgw56jdPwC3eiPymjpHkCsDisW963iAYaMEynPg4/CHj7/pBlk+ZVsL/qt7pEgwjN2gwce0Klzjf8nIroZi+UrFvpxX6kUHH5CQUlTHr8Pq0xFXxiK/AoGTvayKQAX9E8AS5jPqCBKhk0/D3vYjriGpmJIgdauAen/Sud2LHxqByKgu5eTta2BGQGGDDD0sRtbG/icloZN9ApO0kf302A9sSGupTHAhuiRC7qszJt2CXtgAMQvJGkqqdvQpjQK/cqKAH06Yy82c5aeSPrkaE/zTg6eH5bjcQhnef2sPiWiTkObUEOAi23JBLFmJmNPFQQxJHQ==;
Received: from [] by with NNFMP; 11 Nov 2014 20:11:19 -0000
Received: from [] by with NNFMP; 11 Nov 2014 20:11:19 -0000
Received: from [] by with NNFMP; 11 Nov 2014 20:11:19 -0000
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: HryRX8UVM1nX1Sz_gCn9phuX.jd_v15XQrWFLuuTr7AuDFpax5sk5K5WcF2Ec.e qEY.MAqWNYNwG2ZcL0QH3DU3uRs5JaEsa9JMds6BR7TyP6BfGnmPoSRIuUq4VEGhKWYDEROSxoxc B0JDy5bjpSoB7mKbYIsfZls92o48BeJuQtv15TIbSBPYegt.skxIZaw_fIC..zRW3wVWd5PjtT5m 0qcQe5qd3yavqquGTM55UQxkPq5vtzVRGOn2LIWQdif0uk78RsIwv.MlMajrZfjGimExw7kyBwX7 8KJut6rbvt_gsv2.LJPzssFAYbhssK87QF7IVdDbAL7XLR1CS8TS6lnvJRQY9N9sm2M7c787TxH3 i.K9kNLRVxtoT4Snq_sD_1YEkW53G06u7eESOwuPmHL9hbRWAepyQqEOXI.cwwksF8GoFA2K1rL2 s4Yns0rvrtz0PLF6cxp7BDBftSK5_1FVP3jIdnDWcadaknkiDtZ7bP5frkyhFfHxlFk6t6HUvKLA 0iO6kzVQhN.IggdrLrcJ1Hy9COEKRGvpr7kVxV.IPgXheSGQQetModfplZDP9idyE4SI-
Received: by; Tue, 11 Nov 2014 20:11:19 +0000
Date: Tue, 11 Nov 2014 20:11:16 +0000
From: Oleg Gryb <>
To: Johannes Merkle <>, Oleg Gryb <>, "" <>
Message-ID: <>
In-Reply-To: <>
References: <>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
Subject: Re: [TLS] Twist security for brainpoolp256r1
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Oleg Gryb <>
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 11 Nov 2014 20:11:22 -0000

>>  I was going through SafeCurves pages recently and wanted to ask a question 
> about brainpoolP256r1's twist security.
>>  According to this research,, 
> <>  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?

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

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