Re: [Cfrg] Hardware requirements for elliptic curves

Michael Hamburg <mike@shiftleft.org> Thu, 04 September 2014 15:21 UTC

Return-Path: <mike@shiftleft.org>
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 CB46E1A87B8 for <cfrg@ietfa.amsl.com>; Thu, 4 Sep 2014 08:21:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 4.255
X-Spam-Level: ****
X-Spam-Status: No, score=4.255 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, 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 E3znQf2tBc3h for <cfrg@ietfa.amsl.com>; Thu, 4 Sep 2014 08:21:52 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9B6D11A88DD for <cfrg@irtf.org>; Thu, 4 Sep 2014 08:21:52 -0700 (PDT)
Received: from [192.168.1.135] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 35D553AA27; Thu, 4 Sep 2014 08:19:11 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1409843951; bh=1elI5b1fPWPkLN+L8coZ9YyjE74S2x1Nc6zUxdq9DO4=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=K8pnA2teT+qiUQgkdVhDhDvZK0Sqg+Jgb7DJxHPr4Ae76zlYtrOVTZ6UJoR7gbod/ ZaBjY+n2c86W6O11cLvIMvJaRVh5AWu7mCic+Ww/zPyZwu3TnkyVA1hs6dXSFwUNtg iTukrLuCPo21ZJ5A74dvNGYlRlB3USw+EQTEz23c=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1973.6\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <54086138.6070205@secunet.com>
Date: Thu, 4 Sep 2014 08:21:50 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <BDA5BE29-5F19-44B2-8C3D-8D5E1784B022@shiftleft.org>
References: <85d1c59362684615b0beeea1c2a48dd8@AMSPR04MB518.eurprd04.prod.outlook.com> <828996e7-465b-4c92-b91c-b5604365f986@email.android.com> <12A4E7B4-8303-449F-A04B-8366BBC5B1E3@shiftleft.org> <54086138.6070205@secunet.com>
To: Johannes Merkle <johannes.merkle@secunet.com>
X-Mailer: Apple Mail (2.1973.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/_PhE0tbhQjnpBrl7rh1riP5rEQk
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: Thu, 04 Sep 2014 15:21:58 -0000

> On Sep 4, 2014, at 5:55 AM, Johannes Merkle <johannes.merkle@secunet.com>; wrote:
> 
> Michael Hamburg wrote on 02.09.2014 18:31:
>> I agree with Alyssa that hardware performance isn’t our concern here.
> 
> I disagree with this oversimplification. Currently, the fraction of TLS implementations based on HW is relatively
> small but not negligible. And in the future it will increase:
> 
> 1. Heartbleed has shown that it is dangerous to keep private keys in software. Hopefully, this lesson has been learned.
> 
> 2. There are security critical infrastructures emerging, where TLS will be used with hardware crypto
> implementations. Examples are car2car and car2X, health care infrastructures, smart meter,
> e-government communications services.
> 
> 3. In the foreseeable future, we will see a huge number of constrained devices in the IoT potentially deploying TLS
> (e.g. for home automation, sensor networks).
> 
> Furthermore, other IETF protocols are well within the scope of our effort. (As Kenny wrote in his announcement of the
> current effort "We regard this as a major work item for CFRG and one where CFRG can provide real value to the TLS WG
> and the IETF more widely.") For IPSec, there is indeed a significant number of implementations based on smart cards or
> small HW crypto modules (for instance from my employer).
> 
> 
> -- 
> Johannes

You know what?  I spoke too soon on this, and you changed my mind.  Hardware does matter, even though it isn’t the main focus of this research group.

But I still don’t understand why hardware favors short Weierstrass curves or random primes.  Short Weierstrass really doesn’t seem simpler than Edwards to me.  It’s slower, less regular, and doesn’t parallelize as well (if you have high perf hardware).  It wants a halve() operation for best performance in addition to add/sub/mul, and you can’t just use one unified formula for everything if you’re complexity constrained.  The cofactor is potentially an issue, but you can just wipe out the cofactor first and then check against the identity.

And random primes aren’t better either: they’re still much slower than special primes in hardware, and it’s more complex to invert mod them (more complex Fermat’s Little Theorem, or have to implement EGCD), and you can’t switch between Barrett and Montgomery reduction as easily.  From Joppe Bos' email, it sounds like primes make one blinding technique more effective.  But if you suddenly have double the performance budget (from a faster prime) can you not do even better?

The hardware I’ve seen uses Montgomery reduction.  If everyone else does this too, it might be a minor strike against 2^big - small primes.  Other hardware folks: how do you do your reductions?  And how much of a pain would it be to switch to 2^big - small?  Am I missing something about short Weierstrass, cofactor problems or special primes?

Cheers,
— Mike