Re: [TLS] Twist security for brainpoolp256r1

Johannes Merkle <johannes.merkle@secunet.com> Wed, 12 November 2014 17:16 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 49F561A8AF5 for <tls@ietfa.amsl.com>; Wed, 12 Nov 2014 09:16:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.194
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Q0yZa30NNMSe for <tls@ietfa.amsl.com>; Wed, 12 Nov 2014 09:16:14 -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 337061A906A for <tls@ietf.org>; Wed, 12 Nov 2014 09:12:22 -0800 (PST)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id 35AB11A007A; Wed, 12 Nov 2014 18:12:13 +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 uECXc0CbByEp; Wed, 12 Nov 2014 18:12:04 +0100 (CET)
Received: from mail-essen-01.secunet.de (unknown [10.53.40.204]) by a.mx.secunet.com (Postfix) with ESMTP id A3A441A006C; Wed, 12 Nov 2014 18:12:04 +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; Wed, 12 Nov 2014 18:12:09 +0100
Message-ID: <546394E9.2010208@secunet.com>
Date: Wed, 12 Nov 2014 18:12:09 +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: <54625A39.70700@secunet.com> <1437313076.601391.1415736676771.JavaMail.yahoo@jws106117.mail.bf1.yahoo.com> <54637537.2010408@secunet.com>
In-Reply-To: <54637537.2010408@secunet.com>
Content-Type: text/plain; charset="UTF-8"
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/n528Nvahz8JeCSjtyFjXgsT9UMg
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: 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.
-- 
Johannes