Re: [Cfrg] Hardware requirements for elliptic curves

Torsten Schuetze <torsten.schuetze@gmx.net> Thu, 11 September 2014 18:13 UTC

Return-Path: <torsten.schuetze@gmx.net>
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 4F0ED1A00E7 for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 11:13:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.552
X-Spam-Level:
X-Spam-Status: No, score=-3.552 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-1.652, 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 uhWj13rceNBk for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 11:13:13 -0700 (PDT)
Received: from mout.gmx.net (mout.gmx.net [212.227.17.22]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A09231A9106 for <cfrg@irtf.org>; Thu, 11 Sep 2014 11:06:36 -0700 (PDT)
Received: from [192.168.0.12] ([109.192.91.63]) by mail.gmx.com (mrgmx103) with ESMTPSA (Nemesis) id 0MSuYT-1XtG1P1kmL-00RncV; Thu, 11 Sep 2014 20:06:34 +0200
Message-ID: <5411E4BB.3010000@gmx.net>
Date: Thu, 11 Sep 2014 20:06:51 +0200
From: Torsten Schuetze <torsten.schuetze@gmx.net>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.1.1
MIME-Version: 1.0
To: cfrg@irtf.org, Mike Hamburg <mike@shiftleft.org>
In-Reply-To: <CALCETrWWoQJn58nJucvC1YM_3gi_hZvzY5c-QbA19huMOabyYQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Provags-ID: V03:K0:PjB9JPTsS/y02iAzbnw2yOTpn2gudO+fXCvj34ucCJY0d/XgY15 tVwlSgjLZ6m8BC6Vso9aUPdokoRi6ldhHTJ6uhxvB1SESfeymAk7Tyzm8z7GNptZiP7fO2T rVVQmpwBE8wuZoWDjEl+tHesz8GaFt+QtPCwn9aWSo97YsdJApfZ9imhChsD5Kemw2yVY9S fB0QnVUp/kQXpl39X8OMg==
X-UI-Out-Filterresults: notjunk:1;
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/zLtODV2KF8Y3GRJ6vTSypibgxcI
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, 11 Sep 2014 18:13:15 -0000

On Sep 11, 2014 09:22:53 -0700 Mike Hamburg <mike at shiftleft.org>
wrote:

>> On Sep 11, 2014, at 7:58, Andy Lutomirski <luto at amacapital.net> wrote:
>>
>>
>> Can anyone explain why "random" primes are better for blinding?
>>
>> --Andy
>
> With an unstructured prime, adding a small random multiple of p or
> the group order q will change every bit of the addend.  With a
> sparse prime, it will not.  This makes blinding a less effective
> countermeasure when p is sparse.

Mike, thanks for explaining.

> Torsten, thanks for the description of smart card hardware and
> concerns. It was very educational. I expected something looking
> more like a specialized CPU, where a sparse prime reduction unit
> could be bolted on easily.

The only thing I know in this direction are FPGA proposals like
Güneysu:Paar:2008 CHES 2008 'Ultra High Performance ECC over NIST
Primes on Commercial FPGAs' and even Sasdrich:Güneysu:2014 ARC 2014
'Efficient ECC using Curve25519' which both use the specific DSPs on
the FPGAs.

These are both great papers with very good performance results. But
they show what I mean with flexibility: it is not easily possible to
use 'random' or unstructured primes or even use the original primes
with enough blinding (because the blinding disturbs the structure).

Some years ago, I was looking for a general GF(p) crypto coprocessor
on a FPGA (Car2X standardization, like IEEE 1609.2, but without NIST
primes). The only thing I came up with was Nele Mentens Phd, 2007
(Montgomery multiplication, coarsely integrated operand scanning) and
the CHES 2010 paper by N. Guillermin (RNS). Unfortunately, I could not
find direct comparisons of, say, Brainpool and NIST curves on these
architectures.

> You should keep in mind, though, that the curves being proposed are
> designed for security against local side channels as well as global
> ones. The submitted implementations are designed not to leak against
> an adversary who can see all memory addresses accessed and
> instructions executed, even without blinding.

It all depends on the adversarial model.

> That's a lot easier than power and fault defense, but we're not
> slacking on the software side either.

But you surely know from your company background Cryptography
Research that electromagnetic attacks in a template like fashion are
currently the most advanced attacks. And I don't see that one can
solve this issue without heavy blinding.

Torsten