Re: [TLS] Twist security for brainpoolp256r1

Oleg Gryb <oleg_gryb@yahoo.com> Tue, 11 November 2014 20:11 UTC

Return-Path: <oleg_gryb@yahoo.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8864C1A0231 for <tls@ietfa.amsl.com>; Tue, 11 Nov 2014 12:11:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.695
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FX8ZK6uuqON2 for <tls@ietfa.amsl.com>; Tue, 11 Nov 2014 12:11:20 -0800 (PST)
Received: from nm40-vm2.bullet.mail.bf1.yahoo.com (nm40-vm2.bullet.mail.bf1.yahoo.com [72.30.239.210]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8868F1A01CB for <tls@ietf.org>; Tue, 11 Nov 2014 12:11:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; 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; d=yahoo.com; b=WzekA/JJYAM/l9ucSmgw56jdPwC3eiPymjpHkCsDisW963iAYaMEynPg4/CHj7/pBlk+ZVsL/qt7pEgwjN2gwce0Klzjf8nIroZi+UrFvpxX6kUHH5CQUlTHr8Pq0xFXxiK/AoGTvayKQAX9E8AS5jPqCBKhk0/D3vYjriGpmJIgdauAen/Sud2LHxqByKgu5eTta2BGQGGDDD0sRtbG/icloZN9ApO0kf302A9sSGupTHAhuiRC7qszJt2CXtgAMQvJGkqqdvQpjQK/cqKAH06Yy82c5aeSPrkaE/zTg6eH5bjcQhnef2sPiWiTkObUEOAi23JBLFmJmNPFQQxJHQ==;
Received: from [98.139.215.140] by nm40.bullet.mail.bf1.yahoo.com with NNFMP; 11 Nov 2014 20:11:19 -0000
Received: from [98.139.212.235] by tm11.bullet.mail.bf1.yahoo.com with NNFMP; 11 Nov 2014 20:11:19 -0000
Received: from [127.0.0.1] by omp1044.mail.bf1.yahoo.com with NNFMP; 11 Nov 2014 20:11:19 -0000
X-Yahoo-Newman-Property: ymail-3
X-Yahoo-Newman-Id: 642885.76008.bm@omp1044.mail.bf1.yahoo.com
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 76.13.26.142; Tue, 11 Nov 2014 20:11:19 +0000
Date: Tue, 11 Nov 2014 20:11:16 +0000
From: Oleg Gryb <oleg_gryb@yahoo.com>
To: Johannes Merkle <johannes.merkle@secunet.com>, Oleg Gryb <oleg@gryb.info>, "tls@ietf.org" <tls@ietf.org>
Message-ID: <1437313076.601391.1415736676771.JavaMail.yahoo@jws106117.mail.bf1.yahoo.com>
In-Reply-To: <54625A39.70700@secunet.com>
References: <54625A39.70700@secunet.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/VaK6hasRCQ84A1-lp4sChpLAdc8
Subject: Re: [TLS] Twist security for brainpoolp256r1
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Oleg Gryb <oleg@gryb.info>
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=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 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?

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