Re: [Cfrg] Hardware requirements for elliptic curves

"Lochter, Manfred" <manfred.lochter@bsi.bund.de> Fri, 05 September 2014 10:58 UTC

Return-Path: <manfred.lochter@bsi.bund.de>
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 E496E1A0690 for <cfrg@ietfa.amsl.com>; Fri, 5 Sep 2014 03:58:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.217
X-Spam-Level:
X-Spam-Status: No, score=-7.217 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HELO_EQ_DE=0.35, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.668, UNPARSEABLE_RELAY=0.001] 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 qTQ6KfJ83_ZI for <cfrg@ietfa.amsl.com>; Fri, 5 Sep 2014 03:58:39 -0700 (PDT)
Received: from m3-bn.bund.de (m3-bn.bund.de [77.87.228.75]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 755EA1A064D for <cfrg@irtf.org>; Fri, 5 Sep 2014 03:58:39 -0700 (PDT)
Received: from m3.mfw.bn.ivbb.bund.de (localhost.mfw.bn.ivbb.bund.de [127.0.0.1]) by m3-bn.bund.de (8.14.3/8.14.3) with ESMTP id s85AwZh4024414 for <cfrg@irtf.org>; Fri, 5 Sep 2014 12:58:35 +0200 (CEST)
Received: (from localhost) by m3.mfw.bn.ivbb.bund.de (MSCAN) id 5/m3.mfw.bn.ivbb.bund.de/smtp-gw/mscan; Fri Sep 5 12:58:35 2014
X-P350-Id: 204cba622494e8d0
X-Virus-Scanned: by amavisd-new at bsi.bund.de
From: "Lochter, Manfred" <manfred.lochter@bsi.bund.de>
Organization: BSI Bonn
To: rransom.8774@gmail.com
Date: Fri, 5 Sep 2014 12:58:11 +0200
User-Agent: KMail/1.9.10 (enterprise35 20140205.23bb19c)
References: <85d1c59362684615b0beeea1c2a48dd8@AMSPR04MB518.eurprd04.prod.outlook.com> <CABqy+srrwTKpKZXp1rDxinNeOWrC_ha2BzSyfdg+n6pQ8X65iQ@mail.gmail.com> <54097A2B.6090104@secunet.com>
In-Reply-To: <54097A2B.6090104@secunet.com>
X-KMail-QuotePrefix: >
MIME-Version: 1.0
Content-Type: Text/Plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Message-ID: <201409051258.14045.manfred.lochter@bsi.bund.de>
X-AntiVirus: checked by Avira MailGate (version: 3.2.1.26; AVE: 8.3.24.22; VDF: 7.11.170.236; host: sgasmtp2.bsi.de); id=25309-Q8fgXY
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/QTenY9b1kO1VZU9nLZM__JHLb6A
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Hardware requirements for elliptic curves
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, 05 Sep 2014 11:08:00 -0000

Robert Ransom wrote on 05.09.2014 05:18:
> On 9/2/14, Joppe Bos <joppe.bos@nxp.com>; wrote:
> 
>> Selecting new curves in a transparent fashion, which are more secure
>> compared to the current set of standardized curves by NIST, is the right
>> thing to do.
> 
> I don't see why you are presupposing that new curves must be selected
> -- surely the IETF should not rule out the use of previously chosen
> curves such as Curve25519 and the ‘Brainpool’ curves merely because
> they have multiple independent, interoperable implementations.  In
> particular, the rest of your message argues for a set of curves which
> (a) are defined over random-prime-order coordinate fields, and (b)
> have prime order, and the Brainpool curves satisfy both of those
> criteria *and* are already implemented.

I agree that there are sets of established curve parameters and that the use 
of these curves in IETF protocols should not be prohibited by the selection 
of new curves by the IETF. 

There are people who propose that for each security level (i.e. 128 bit, 192 
bit, 256 bit) one curve should be chosen and be used by everyone. To me this 
seems to be a dangerous approach. I admit that today most cryptographers 
believe that hypothetical future attacks on elliptic curves will be generic.  
But no one can rule out the possibility of new efficient attacks on special 
classes of elliptic curves. (Think of the Satoh-Araki-Smart attack on 
anomalous curves.)

Therefore I believe that protocols should offer a wide flexibility in choosing 
(and changing) elliptic curves.


> 
> (I'll leave the question of whether those properties are as desirable
> in hardware implementations as you claim they are to people who have
> studied those, but having prime order is the most important security
> risk of the NSA curves in software implementations, so I don't see why
> you are criticizing those curves' security in the same message in
> which you propose retaining that security risk in newly chosen
> curves.)

See also RFC 6989! Indeed, using curve types that require a (small) cofactor 
introduces an additional risk.
> 
> Perhaps you don't consider the Brainpool curves to have been chosen
> ‘in a transparent fashion’?  If that is your concern, I'm sure that
> someone from the Brainpool consortium would be interested in
> commenting on exactly how transparent their process was.

As I was the editor of the Brainpool paper I would like to take the 
opportunity to elaborate on the Brainpool process: The open Brainpool group 
consists of members from academia, industry and government. Its major goal is 
to promote the usage of ECC as well as to enhance the security of 
ECC-implementations. 
Around 2004 we identified industry demand for additional  standardized curve 
parameters. We spent several meetings to solicit and select criteria that 
these curves should fulfill. These criteria were selected taking into account
	mathematical security
	security against side-channel attacks
	avoidance of implementation errors. 
Scientists participating include Gerhard Frey, Johannes Buchmann, Tanja Lange 
and Elisabeth Oswald, to name some. 
We also believed that the curve generation should be verifiable. Thus we came 
up with a construction process based on the X.9.62 standard. We based this 
fully rigid process on the two natural constants e and pi.
Details can be found in 
http://www.ecc-brainpool.org/download/Domain-parameters.pdf
At the ECC 2005 conference we invited the international ECC-community to 
comment on this paper, but received no comments. Since 2005 the Brainpool 
curves became widely used.
As a next step we successfully initiated standardization of the Brainpool 
curves for IETF use (RFC 5639, 6954, 7027). 
 
> 
> 
> Additionally, you're raising the issue that new curves should be
> chosen ‘in a transparent fashion’.  Since you are one of the authors
> of <https://eprint.iacr.org/2014/130>;, which ‘select[s] new curves’,
> would you, and the rest of Microsoft Research, be willing to publish
> all of your internal communications and records (e-mails, memoranda,
> meeting notes, phone conversations, etc.) regarding that paper and
> your efforts to promote adoption of the curves, algorithms, and
> software described in that paper?  That would allow people who share
> your concern about the transparency of the selection process to
> seriously consider the curves specified in your paper.
> 
> (I don't consider transparency of the selection process to be nearly
> as important as other criteria such as cross-platform performance,
> efficiency of constrained implementations, support for simple
> algorithms, support for efficient, simple constant-time
> sum-of-scalar-multiple algorithms, and the availability of multiple
> independent, interoperable implementations, all of which argue against
> the curves specified in that paper.  But you, and other members of
> Microsoft Research, have raised ‘transparency’ as a concern, and other
> people may indeed consider transparency to be important.)

Personally I believe that it is impossible to have a process that is accepted 
as transparent and rigid by everyone and at every point in time. To give an 
example: Only recently we have been implicitely  criticized for not using 
Keccak in the Brainpool curve generation process. But Keccak  was not even 
available in 2005. From my perspective this observation underlines the 
necessity of standards  allowing for a flexible use of curves. 
> 
> 
> Robert Ransom
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>

Manfred




Lochter, Manfred
--------------------------------------------
Bundesamt für Sicherheit in der Informationstechnik (BSI)
Referat K21
Godesberger Allee 185 -189
53175 Bonn

Postfach 20 03 63
53133 Bonn

Telefon: +49 (0)228 99 9582 5643
Telefax: +49 (0)228 99 10 9582 5643
E-Mail: manfred.lochter@bsi.bund.de
Internet:
www.bsi.bund.de
www.bsi-fuer-buerger.de