Re: [TLS] Twist security for brainpoolp256r1

Johannes Merkle <johannes.merkle@secunet.com> Tue, 11 November 2014 18:49 UTC

Return-Path: <Johannes.Merkle@secunet.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 60AEC1A1A5E for <tls@ietfa.amsl.com>; Tue, 11 Nov 2014 10:49:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.295
X-Spam-Level:
X-Spam-Status: No, score=-1.295 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.594] 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 u1lrKQw2escL for <tls@ietfa.amsl.com>; Tue, 11 Nov 2014 10:49:41 -0800 (PST)
Received: from a.mx.secunet.com (a.mx.secunet.com [195.81.216.161]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C820B1A036A for <tls@ietf.org>; Tue, 11 Nov 2014 10:49:40 -0800 (PST)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id 083F51A007A; Tue, 11 Nov 2014 19:49:32 +0100 (CET)
X-Virus-Scanned: by secunet
Received: from a.mx.secunet.com ([127.0.0.1]) by localhost (a.mx.secunet.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id L2JNooWz4ERS; Tue, 11 Nov 2014 19:49:24 +0100 (CET)
Received: from mail-essen-01.secunet.de (unknown [10.53.40.204]) by a.mx.secunet.com (Postfix) with ESMTP id EF5461A006C; Tue, 11 Nov 2014 19:49:23 +0100 (CET)
Received: from [10.208.1.76] (10.208.1.76) by mail-essen-01.secunet.de (10.53.40.204) with Microsoft SMTP Server (TLS) id 14.3.210.2; Tue, 11 Nov 2014 19:49:30 +0100
Message-ID: <54625A39.70700@secunet.com>
Date: Tue, 11 Nov 2014 19:49:29 +0100
From: Johannes Merkle <johannes.merkle@secunet.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Oleg Gryb <oleg@gryb.info>, "tls@ietf.org" <tls@ietf.org>
References: <2116033100.449850.1415678543902.JavaMail.yahoo@jws106117.mail.bf1.yahoo.com>
In-Reply-To: <2116033100.449850.1415678543902.JavaMail.yahoo@jws106117.mail.bf1.yahoo.com>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7bit
X-Originating-IP: [10.208.1.76]
X-EXCLAIMER-MD-CONFIG: 2c86f778-e09b-4440-8b15-867914633a10
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/_fmycKZVagXs_xU1FpI07o5kAfo
Subject: Re: [TLS] Twist security for brainpoolp256r1
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
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 18:49:43 -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.

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


-- 
Johannes