Re: [Cfrg] Hardware requirements for elliptic curves

Johannes Merkle <johannes.merkle@secunet.com> Fri, 05 September 2014 11:34 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 6CAEE1A06D6 for <cfrg@ietfa.amsl.com>; Fri, 5 Sep 2014 04:34:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.568
X-Spam-Level:
X-Spam-Status: No, score=-0.568 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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 FS_acVmiCy9r for <cfrg@ietfa.amsl.com>; Fri, 5 Sep 2014 04:34:45 -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 B913C1A06CA for <cfrg@irtf.org>; Fri, 5 Sep 2014 04:34:44 -0700 (PDT)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id E849F1A008F; Fri, 5 Sep 2014 13:34:38 +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 hLVSsr0wBoiI; Fri, 5 Sep 2014 13:34:33 +0200 (CEST)
Received: from mail-essen-01.secunet.de (unknown [10.53.40.204]) by a.mx.secunet.com (Postfix) with ESMTP id BDBF41A007A; Fri, 5 Sep 2014 13:34:33 +0200 (CEST)
Received: from [10.208.1.76] (10.208.1.76) by mail-essen-01.secunet.de (10.53.40.204) with Microsoft SMTP Server (TLS) id 14.3.195.1; Fri, 5 Sep 2014 13:34:37 +0200
Message-ID: <54099FCC.6050200@secunet.com>
Date: Fri, 5 Sep 2014 13:34:36 +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: Michael Hamburg <mike@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> <BDA5BE29-5F19-44B2-8C3D-8D5E1784B022@shiftleft.org>
In-Reply-To: <BDA5BE29-5F19-44B2-8C3D-8D5E1784B022@shiftleft.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
X-Originating-IP: [10.208.1.76]
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/AskcfrfIyfJKh9ODdH9-8xaP_Cg
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:34:47 -0000

Michael Hamburg wrote on 04.09.2014 17:21:
> 
>> 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.

I am not at all a hardware expert. But we just had a meeting of the ECC Brainpool, where several hardware vendors are
represented. What I understood is that they do not want to specialize their hardware to minimize their investment while
being fully flexible (algorithm agile). Remember that multipliers are also needed for RSA where the numbers do not have
a special shape. Furthermore, I guess that new implementations can be built easier based on existing ones.

> 
> 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 point is that flexible (non-specialized) hardware multipliers do not take advantage of specialized primes.
Specialized multipliers are certainly possible but are less agile w.r.t algorithms / curves. Flexibility is particularly
important due to the long development / certification cycles and the tremendous costs involved.


-- 
Johannes