Re: [Cfrg] Progress on curve recommendations for TLS WG

Johannes Merkle <johannes.merkle@secunet.com> Fri, 15 August 2014 11:12 UTC

Return-Path: <Johannes.Merkle@secunet.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 199281A8A35 for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 04:12:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.268
X-Spam-Level:
X-Spam-Status: No, score=-3.268 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.668] 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 uw7jM4ecRXgZ for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 04:12:22 -0700 (PDT)
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 4DEF71A09D7 for <cfrg@irtf.org>; Fri, 15 Aug 2014 04:12:21 -0700 (PDT)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id 7CF231A0079 for <cfrg@irtf.org>; Fri, 15 Aug 2014 13:12:16 +0200 (CEST)
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 wwUzs5ARs9rr for <cfrg@irtf.org>; Fri, 15 Aug 2014 13:12:11 +0200 (CEST)
Received: from mail-essen-01.secunet.de (unknown [10.53.40.204]) by a.mx.secunet.com (Postfix) with ESMTP id 9C6041A0071 for <cfrg@irtf.org>; Fri, 15 Aug 2014 13:12:11 +0200 (CEST)
Received: from [172.16.40.201] (172.16.40.201) by mail-essen-01.secunet.de (10.53.40.204) with Microsoft SMTP Server (TLS) id 14.3.195.1; Fri, 15 Aug 2014 13:12:14 +0200
Message-ID: <53EDEB0D.9040304@secunet.com>
Date: Fri, 15 Aug 2014 13:12:13 +0200
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: <cfrg@irtf.org>
References: <20140801013659.11640.qmail@cr.yp.to>
In-Reply-To: <20140801013659.11640.qmail@cr.yp.to>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Originating-IP: [172.16.40.201]
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/tjL-m-SCUHz1gQ9TDbKf7hnuHjE
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 15 Aug 2014 11:12:25 -0000

D. J. Bernstein wrote on 01.08.2014 03:36:
> However, the following recent analysis shows that the Brainpool curves,
> which were advertised as "generated in a systematic and comprehensive
> way" covering several different security levels, actually gave the curve
> generator the flexibility to secretly choose from among more than
> 1000000 curves for any particular prime:
> 
>    http://safecurves.cr.yp.to/bada55.html
>    http://safecurves.cr.yp.to/bada55/bada55-20140722.pdf

This statement is so skewed and misleading that I can not refrain from commenting:

- In this analysis, a significant part of this flexibility comes from the choice of the hash function. Specifically, the
BADA55 curves were generated using one of the numerous version of Keccak. However, Keccak wasn't even invented at the
time the Brainpool curves were generated.

 - The method used to generate the coefficients of the Brainpool curves was taken from ANSI X9.62 (including the use of
SHA-1), which was - at least at that time - the only reference for a method for pseudo-random curve generation. There is
only the slight deviation that the second coefficient was computed in exactly the same way as the first one, while ANSI
X9.62 computes the fraction of these, but this straightforward simplification does not introduce significant flexibility.

- Pi and e are by far the most prominent mathematical constants, while cosinus(1) (used in that analysis) is quite
arbitrarily chosen. Expressing Pi as 4*arctan(1) doesn't change this fact.

It is perfectly OK to point out that the Brainpool curves do not allow optimal performance, or that Montgomery and
Edwards curves allow simplified arithmetic. But it is not ok to imply that the Brainpool curves could potentially have
been designed with a backdoor built in. This suggestion is completely unjustified, misleading and gives a false color.

-- 
Johannes