Re: [TLS] Twist security for brainpoolp256r1

Manuel Pégourié-Gonnard <mpg@polarssl.org> Thu, 13 November 2014 09:21 UTC

Return-Path: <mpg@polarssl.org>
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 75D941A6FB9 for <tls@ietfa.amsl.com>; Thu, 13 Nov 2014 01:21:35 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.397
X-Spam-Level:
X-Spam-Status: No, score=0.397 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HELO_MISMATCH_COM=0.553, HOST_EQ_NL=1.545, MIME_8BIT_HEADER=0.3, SPF_PASS=-0.001] autolearn=no
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 38Mu-93acqdQ for <tls@ietfa.amsl.com>; Thu, 13 Nov 2014 01:21:34 -0800 (PST)
Received: from vps2.offspark.com (vps2.brainspark.nl [141.138.204.106]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1B42A1A1BBB for <tls@ietf.org>; Thu, 13 Nov 2014 01:21:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=polarssl.org; s=exim; h=Subject:Content-Transfer-Encoding:Content-Type:In-Reply-To:References:To:MIME-Version:From:Date:Message-ID; bh=Tx9FlvVAFBZ2pL7lT3P3Oeb+4brv+Y3JAy7dffYPRkw=; b=E0d4GtDN9nulXoK4n7vEZtbU3U9Bj+dDkIYTJP2q1qSJyL5Tcoy+h5cfzIAK1pSAH6DJilwxnS9w6mZ0GNHcY0u9gZ2F90ZnXBDIY5Rbw66EJwu0ZRZS9EegsTf1zmfHZ5U0pe1AYeoqhcA4PO0jlWXafnmcDZArszswPJNllQ4=;
Received: from mna75-11-88-161-199-191.fbx.proxad.net ([88.161.199.191] helo=[192.168.0.12]) by vps2.offspark.com with esmtpsa (TLS1.2:DHE_RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <mpg@polarssl.org>) id 1Xoqah-0007eQ-Qa; Thu, 13 Nov 2014 10:21:24 +0100
Message-ID: <54647819.3020802@polarssl.org>
Date: Thu, 13 Nov 2014 10:21:29 +0100
From: =?windows-1252?Q?Manuel_P=E9gouri=E9-Gonnard?= <mpg@polarssl.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0
MIME-Version: 1.0
To: Oleg Gryb <oleg@gryb.info>, Johannes Merkle <johannes.merkle@secunet.com>, "tls@ietf.org" <tls@ietf.org>
References: <546394E9.2010208@secunet.com> <1821348128.254417.1415860521951.JavaMail.yahoo@jws10668.mail.bf1.yahoo.com>
In-Reply-To: <1821348128.254417.1415860521951.JavaMail.yahoo@jws10668.mail.bf1.yahoo.com>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
X-SA-Exim-Connect-IP: 88.161.199.191
X-SA-Exim-Mail-From: mpg@polarssl.org
X-SA-Exim-Version: 4.2.1 (built Mon, 26 Dec 2011 16:24:06 +0000)
X-SA-Exim-Scanned: Yes (on vps2.offspark.com)
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/SN0L3wSvbFazgkwJ1D1NSdJ3-DE
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: Thu, 13 Nov 2014 09:21:36 -0000

On 13/11/2014 07:35, Oleg Gryb wrote:
> Thanks, very helpful. Just to summarize yours and Manuel's notes in regard of
> quadratic non-residue, or non-quadratic twists (as they are called in other
> emails), they can be used as a source of malicious EC points to run
> invalid-curve attacks on the original curves, but since all implementations
> compliant with X9* standards including openssl must have point-on-curve
> validation, invalid-curve attacks and small-group attacks become irrelevant
> when it comes to brainpoool's openssl implementation.

The situation is actually a bit more complex. Here is a version that's still a
bit simplified but closer to the truth: let's say there are two kinds of
protocols (or curve representations):

1. Those who use both coordinates of the points.
2. Those who use only the x coordinate.

With the first type, an attacker can for the point to be on (almost) any curve
unless the implementation validates that the point lies on the intended curve.
Here it doesn't matter if the twist* is secure, this it's not easier for the
attacker to force a point on the twist than on any other curve, potentially much
weaker.

With the second type, the only curve other than the intended one that the
attacker can force is the twist*. So, if the twist happens to be secure, the
implementation can skip point validation: the attacker will not gain anything by
forcing you to use the twist.

* meaning what Johannes called the non-quadratic twist.

TLS currently is in the first category, which means twist security is not
relevant, because:
- either the implementation validates points (which it must),
- or the attacker can force *much* weaker curves than the twist.

> Note - small group
> attacks are not possible, because of a different reason: cofactor for all
> brainpool curves is equal to 1.
> 
Yes. While we're at it, let's note that the whole purpose of forcing another
curve is to do a small subgroup attack by picking a curve that does have small
subgroups.

> Efficiency is still an issue for me. Since curves such as NIST P-256 do have
> optimized EC arithmetic, but nothing like that is available for brainpool
> curves, it would be nice to know what the delta is. If it's up to 30%
> percent, I would probably ignore, if it's essentially more than that, I might
> need to re-consider my choice. If no quantitative data is available, I would
> probably need to write/run my own tests.
> 
Openssl has a "speed" command that should be helpful. I'd expect a difference
higher than 30%.

Manuel.