[Cfrg] Hardware requirements for elliptic curves
Joppe Bos <joppe.bos@nxp.com> Tue, 02 September 2014 11:43 UTC
Return-Path: <joppe.bos@nxp.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 DC7531A0258 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 04:43:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-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 6lAWdfX7ZdUT for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 04:43:22 -0700 (PDT)
Received: from emea01-db3-obe.outbound.protection.outlook.com (mail-db3lrp0084.outbound.protection.outlook.com [213.199.154.84]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 521831A0243 for <cfrg@irtf.org>; Tue, 2 Sep 2014 04:43:21 -0700 (PDT)
Received: from AMSPR04MB518.eurprd04.prod.outlook.com (10.242.20.156) by AMSPR04MB520.eurprd04.prod.outlook.com (10.242.20.28) with Microsoft SMTP Server (TLS) id 15.0.1019.16; Tue, 2 Sep 2014 11:43:19 +0000
Received: from AMSPR04MB518.eurprd04.prod.outlook.com ([10.242.20.156]) by AMSPR04MB518.eurprd04.prod.outlook.com ([10.242.20.156]) with mapi id 15.00.1015.018; Tue, 2 Sep 2014 11:43:19 +0000
From: Joppe Bos <joppe.bos@nxp.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Hardware requirements for elliptic curves
Thread-Index: Ac/GowOhGhCyElEYRWKcODdE4M7FSA==
Date: Tue, 02 Sep 2014 11:43:19 +0000
Message-ID: <85d1c59362684615b0beeea1c2a48dd8@AMSPR04MB518.eurprd04.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [78.110.199.13]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 0322B4EDE1
x-forefront-antispam-report: SFV:NSPM; SFS:(189002)(199003)(107046002)(31966008)(87936001)(107886001)(2656002)(81342001)(15975445006)(19580395003)(83322001)(74662001)(74502001)(92566001)(83072002)(85852003)(77982001)(46102001)(106356001)(74316001)(105586002)(76576001)(229853001)(110136001)(79102001)(2351001)(76482001)(85306004)(95666004)(19300405004)(4396001)(15202345003)(33646002)(90102001)(99396002)(64706001)(19617315012)(19625215002)(81542001)(50986999)(66066001)(20776003)(21056001)(108616004)(80022001)(101416001)(99936001)(54356999)(2501002)(86362001)(16236675004)(24736002); DIR:OUT; SFP:; SCL:1; SRVR:AMSPR04MB520; H:AMSPR04MB518.eurprd04.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_0064_01CFC6B3.D659D1D0"
MIME-Version: 1.0
X-OriginatorOrg: nxp.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/gwBHQQrEBRXj5juBfBw83NApz3Y
Subject: [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: Tue, 02 Sep 2014 11:43:25 -0000
The current discussion around the requirements, and the performance aspects, have mainly been approached from a software implementation point of view. As one of the authors of the NUMS curves, I have been responsible for this as well. With this message I would like to provide a hardware perspective: more specifically, I would like to put forward some requirements which are concerned with hardware specific attacks. The current discussion is focused around deciding upon a set of requirements in order to select new elliptic curves for usage in the TLS protocol. However, this choice of curves can potentially have a significant impact on the choice of the new "standard" elliptic curves used in a broader setting. This is why a different (i.e. hardware) point of view might be a relevant addition in the current discussion. In the hardware setting, when implementing curve based cryptography, one often has access to a generic modular multiplication (hardware) implementation on a secure crypto co-processor. In this scenario, the performance of a multiplication modulo a random prime is identical to the performance of multiplication modulo a prime of a special shape. Not only does the usage of specially shaped moduli not increase performance, it makes it a lot harder to use a set of common counter-measures against certain types of side-channel attacks (a requirement for meeting certain standards such as Common Criteria and EMVCo). For example, scalar blinding is a technique in which one adds a random multiple of the group order to the scalar. If the prime p (in the definition of the finite field F_p) has a special shape, then this shape carries (largely) over to the order of the elliptic curve (by the Hasse-Weil bound). It is known that one can take advantage of this special shape and attack schemes that apply scalar blinding (e.g. see <https://eprint.iacr.org/2014/191.pdf> https://eprint.iacr.org/2014/191.pdf and the references therein). Therefore, (also) specifying curves defined over random prime fields (more precisely, an elliptic curve defined over the finite field F_p where p is a random prime) would be a preferable additional design requirement from a hardware point of view. We will need to support prime order Weierstrass curves in the future since we will need to keep supporting the NIST curves. Adding dedicated support for curve arithmetic in different curve models (Edwards / Montgomery) would increase the code size which in turn increases maintenance effort. Furthermore, since Edwards / Montgomery curves cannot have prime order, this requires changes to the current implementations in order to avoid small-subgroup attacks. It is unclear (and an interesting question) if implementing the more efficient group law on these different curve models is worth the increase in code size, since the potential speedup is expected to be between a factor one and two. Supporting Edwards / Montgomery curves in their corresponding Weierstrass form has no advantage from a performance point of view and adds complexity due to the composite group order. In conclusion, we think the current ongoing discussion about the requirements needed for selecting new elliptic curves is very important. 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. From a hardware perspective, defining elliptic curves over primes of a special shape has no positive performance effect and even rules out using some common countermeasures to guard against types of side-channel attacks. We have a strong preference for prime-order Weierstrass curves defined over random primes. If this is not an option and if different curve models are proposed then also providing such a curve defined over a random prime field would be preferable. In this latter setting, it is not clear if we would adapt the implementations to the curve model or transform to Weierstrass form. I hope this additional point of view is useful and will lead to further discussion. Joppe Bos
- [Cfrg] Hardware requirements for elliptic curves Joppe Bos
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Michael Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Johannes Merkle
- Re: [Cfrg] Hardware requirements for elliptic cur… Michael Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Andy Lutomirski
- Re: [Cfrg] Hardware requirements for elliptic cur… Robert Ransom
- Re: [Cfrg] Hardware requirements for elliptic cur… Lochter, Manfred
- Re: [Cfrg] Hardware requirements for elliptic cur… Johannes Merkle
- Re: [Cfrg] Hardware requirements for elliptic cur… Wieland.Fischer
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Watson Ladd
- Re: [Cfrg] Hardware requirements for elliptic cur… Patrick Georgi
- Re: [Cfrg] Hardware requirements for elliptic cur… Paul Lambert
- Re: [Cfrg] Hardware requirements for elliptic cur… Torsten Schuetze
- Re: [Cfrg] Hardware requirements for elliptic cur… Torsten Schuetze
- Re: [Cfrg] Hardware requirements for elliptic cur… Andy Lutomirski
- Re: [Cfrg] Hardware requirements for elliptic cur… Mike Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Torsten Schuetze
- Re: [Cfrg] Hardware requirements for elliptic cur… Watson Ladd
- Re: [Cfrg] Hardware requirements for elliptic cur… Mike Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Lochter, Manfred
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Dirk Feldhusen
- Re: [Cfrg] Hardware requirements for elliptic cur… Lochter, Manfred
- Re: [Cfrg] Hardware requirements for elliptic cur… Ilari Liusvaara
- Re: [Cfrg] Hardware requirements for elliptic cur… Watson Ladd
- Re: [Cfrg] Hardware requirements for elliptic cur… Peter Gutmann
- [Cfrg] Trusting government certifications of cryp… D. J. Bernstein
- Re: [Cfrg] Trusting government certifications of … David Jacobson
- Re: [Cfrg] Trusting government certifications of … Torsten Schütze
- Re: [Cfrg] Trusting government certifications of … Watson Ladd
- Re: [Cfrg] Trusting government certifications of … Dirk Feldhusen
- Re: [Cfrg] Trusting government certifications of … Michael Hamburg
- Re: [Cfrg] Trusting government certifications of … Dirk Feldhusen
- Re: [Cfrg] Trusting government certifications of … Lochter, Manfred
- Re: [Cfrg] Trusting government certifications of … Mike Hamburg
- Re: [Cfrg] Primes vs. hardware side channels David Leon Gil
- [Cfrg] Primes vs. hardware side channels D. J. Bernstein
- Re: [Cfrg] Primes vs. hardware side channels Alyssa Rowan