Re: [TLS] Twist security for brainpoolp256r1

Johannes Merkle <> Wed, 12 November 2014 17:16 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 49F561A8AF5 for <>; Wed, 12 Nov 2014 09:16:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.194
X-Spam-Status: No, score=-3.194 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.594] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Q0yZa30NNMSe for <>; Wed, 12 Nov 2014 09:16:14 -0800 (PST)
Received: from ( []) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 337061A906A for <>; Wed, 12 Nov 2014 09:12:22 -0800 (PST)
Received: from localhost (alg1 []) by (Postfix) with ESMTP id 35AB11A007A; Wed, 12 Nov 2014 18:12:13 +0100 (CET)
X-Virus-Scanned: by secunet
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with LMTP id uECXc0CbByEp; Wed, 12 Nov 2014 18:12:04 +0100 (CET)
Received: from (unknown []) by (Postfix) with ESMTP id A3A441A006C; Wed, 12 Nov 2014 18:12:04 +0100 (CET)
Received: from [] ( by ( with Microsoft SMTP Server (TLS) id; Wed, 12 Nov 2014 18:12:09 +0100
Message-ID: <>
Date: Wed, 12 Nov 2014 18:12:09 +0100
From: Johannes Merkle <>
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 <>, "" <>
References: <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Originating-IP: []
X-EXCLAIMER-MD-CONFIG: 2c86f778-e09b-4440-8b15-867914633a10
Subject: Re: [TLS] Twist security for brainpoolp256r1
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." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 12 Nov 2014 17:16:21 -0000

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

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.