Re: [Cfrg] Hardware requirements for elliptic curves

Michael Hamburg <mike@shiftleft.org> Tue, 02 September 2014 16:32 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 7FE961A046C for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 09:32:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 Lkyi6YZDkovF for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 09:32:00 -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 105D21A0412 for <cfrg@irtf.org>; Tue, 2 Sep 2014 09:32:00 -0700 (PDT)
Received: from [192.168.1.135] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 6E1B03AA12; Tue, 2 Sep 2014 09:29:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1409675366; bh=uLDhpI4xJai/owIyqPQRKktfUn2CxASAq5o/JcbJdm4=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=D0A6hcGFMUSXB6RaXOpP9Ro5NbRYyjyHezjeJY1ZaMa9oE2tI0+Uzr6NQ7jV6LtDO 0hct9KLw3G6qg21rcMywHFEuuacmwbpor7QE6b1k4WyjwHE0jgf0fAJUxfyZ4Estm+ bzZQ64OeYV99sglhvZDcyMj7W6RUC+CzFH0+YMFk=
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: <828996e7-465b-4c92-b91c-b5604365f986@email.android.com>
Date: Tue, 2 Sep 2014 09:31:56 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <12A4E7B4-8303-449F-A04B-8366BBC5B1E3@shiftleft.org>
References: <85d1c59362684615b0beeea1c2a48dd8@AMSPR04MB518.eurprd04.prod.outlook.com> <828996e7-465b-4c92-b91c-b5604365f986@email.android.com>
To: Alyssa Rowan <akr@akr.io>
X-Mailer: Apple Mail (2.1973.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/UupiOH6GbJuOR5pmqYTvIeU-zUU
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: Tue, 02 Sep 2014 16:32:01 -0000

I agree with Alyssa that hardware performance isn’t our concern here.

However, I’m curious about Joppe Bos’ assertion that random primes are just as fast and more secure in hardware.  What kind of hardware are you thinking about?  Some kind of residue number system?  Or a bit-at-a-time reduction system?

I have some limited experience in crypto hardware design, in particular working with a hardware modulo multiplier.  If I recall correctly, adding support for a handful of the NIST primes (192, 224, 256 and 384 maybe?) cost about 10% area overhead in our lightweight design, for double the performance.

That said, this hardware used a Montgomery reduction, so the same support would have required more work for a 2^big-small prime.  But I’m sure it can still be done.

— Mike

> On Sep 2, 2014, at 6:05 AM, Alyssa Rowan <akr@akr.io>; wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> On 2 September 2014 12:43:19 BST, Joppe Bos <joppe.bos@nxp.com>; wrote:
>> 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.
> 
> Thank you; an interesting perspective, if I may say so.
> 
> Of course, there's more than one way to do it. Vendors seem to use a variety of techniques for side-channel countermeasures, and other techniques prefer different environments.
> 
> For example, balanced dual-rail logic and smaller constant-time/power implementations (along with an awful lot of dead junk gates, for reasons I can't quite fathom but that may be a poor attempt at DFA countermeasures?).
> 
> Or several other implementations from multiple vendors that are actually based on either specialised microcontrollers or commodity CPUs with specialised firmware, resulting in what may be more accurately characterised as a constrained/specialised software implementation: I think this may be the overall general approach that is the most flexible, modular and reusable, which may be why it's the most favoured approach by most other smart card & HSM vendors, from what I've seen?
> 
> Random primes have unfortunate software performance, including constrained performance.
> 
> We are not concerned with EMV "security" here in CFRG at all, but with making suggestions for *internet* protocols.
> 
> I think it would be a mistake to allow old hardware implementations to (yet again) needlessly overshadow improved software ones: the majority of implementations on the internet will invariably be software. I feel we are being asked for new recommendations here, not old ones, but of course, that's only my perspective.
> 
> - --
> /akr
> -----BEGIN PGP SIGNATURE-----
> Version: APG v1.1.1
> 
> iQI3BAEBCgAhBQJUBcCnGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE
> jtkWi2t6o9sQAJpzXq7NOEzN8GMtwLI5tleXrlrNKDaJnAjVnV3Um8jMjXQR7EKS
> pVUKMykomMhRvTAqfAQGWPBNIij9kRV5nT+3k+LYy6R1uuhS7Bdk3qV7DEEhmi06
> shBK0uW2nic7PiXfwNpBBfrDPdLC2V035dLYD/uRtGPxWg69O4har82sjsIa7Bpm
> ACnZwGxkgn1Mqem6IitSu6zs3XbnBTRVHvD3ttoi7gG5vD9MrQOCsHcWsqvkYIuD
> 6E8N1ioL+5Yv4KhpVmv7NseP4Vl/anXYm5PEXyqVkcZlXtoaDXfJMbZAlolSCiPq
> oaS4yGsGJV+g1HRMUr080jtlNuJKz3QiQqka91stvz83/fMIYhB3Y9Gy7z/0ojMF
> GbKgkt9u31G4srPioFkDZjYPng7RQpwQz0Js3hWje3IVGiG0igEx1MlDrlCuIvlf
> t2DBoxm61FCv+uRbZjXcZI7t/2orAB+5U75jx7yy9rO4WDcZx+QPEa1r3utQ1gBm
> p48lc2NlDsxF7lQUPvpsmtnboYa7yISMefV+rLHX1hf+mgDMd1f9Wm/Dv3t8p53l
> L0rFx0hPv9Lk4Kx/U21QZBa3rNldGyR9V+asBQz65G2C027rWv2K1mrzFMQwphfq
> xJubu9iKqT/JTzk0brRQCd9tY3ljLSW8Y0v9y4enCb5Z015tFno2oIlm
> =Fk5G
> -----END PGP SIGNATURE-----
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg