Re: [Cfrg] Hardware requirements for elliptic curves

Mike Hamburg <mike@shiftleft.org> Thu, 11 September 2014 16:22 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 85C841A89C4 for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 09:22:58 -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 jIXxlWMfCYjf for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 09:22:57 -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 B37FE1ABC0F for <cfrg@irtf.org>; Thu, 11 Sep 2014 09:22:56 -0700 (PDT)
Received: from [10.251.11.38] (unknown [166.170.36.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 386AD3AA12; Thu, 11 Sep 2014 09:19:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1410452388; bh=0Xx37ysTRAau50qf8mhh9OWJBHo697FzS+43ZY562W4=; h=References:In-Reply-To:Cc:From:Subject:Date:To:From; b=dESY+gnOvxWhpTFY0JQeOL/q/B+R3oE8Ffp281HaHMwL4UkjZjA5wi1jmgzl9PPJf cmJeX8AQqPy1ku7kJI8vhzVIFDHCqoxjj8bkze1vntnqSS/1RQF7dr/AZbfL1hXj0l X3E5D1XJKErffVvE76x6a3wdUNEz34oG45Tze8Wc=
References: <12A4E7B4-8303-449F-A04B-8366BBC5B1E3@shiftleft.org> <5411569F.6080102@gmx.net> <CALCETrWWoQJn58nJucvC1YM_3gi_hZvzY5c-QbA19huMOabyYQ@mail.gmail.com>
In-Reply-To: <CALCETrWWoQJn58nJucvC1YM_3gi_hZvzY5c-QbA19huMOabyYQ@mail.gmail.com>
Mime-Version: 1.0 (1.0)
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=us-ascii
Message-Id: <BD2A885F-09F1-4FED-9141-2A7D643A7B01@shiftleft.org>
X-Mailer: iPhone Mail (11D257)
From: Mike Hamburg <mike@shiftleft.org>
Date: Thu, 11 Sep 2014 09:22:53 -0700
To: Andy Lutomirski <luto@amacapital.net>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/k-zlkVQb8DfWybHX1Flf6WiaLe0
Cc: "cfrg@irtf.org" <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, 11 Sep 2014 16:22:59 -0000


Sent from my phone.  Please excuse brevity and typos.

> On Sep 11, 2014, at 7:58, Andy Lutomirski <luto@amacapital.net> wrote:
> 
> On Thu, Sep 11, 2014 at 1:00 AM, Torsten Schuetze
> <torsten.schuetze@gmx.net> wrote:
>> 
>> Let's now come to the flexibility issue: In our company we must be
>> able to work with hitherto unknown domain parameters, i.e., arbitrary
>> random primes. The only thing we can assume is that the curves are
>> Brainpool like. Beyond that, the curves are part of the crypto setup.
>> This is a hard requirement of the government agency, Federal Office of
>> Information Security in our case, and is required by some (not all)
>> other nations as part of the crypto customization.
> 
> What's the actual issue here?  Presumably this means that your device
> will work just as well on e.g. GP(2^255-19) as on any other prime of
> similar size.  It won't be faster the way that software implementation
> can be faster, but that doesn't seem like it will cause a problem.
> 
>> 
>> Besides that we have to use different curves (all in short Weierstrass
>> form, not different curve types as Montgomery etc.) for signature and
>> ECDH. Additional measures are taken, for example, for ECDH such that
>> an attacker cannot easily learn the domain parameters from the data on
>> the wire (point compression not for the sake of saving bandwidth,
>> additional symmetric schemes).
>> 
>> As a company representative I could relax and say that we are not
>> affected by standardization of Edwards-, Montgomery- or even Brainpool
>> curves as we have to use Brainpool-like curves. But my concerns go a
>> step further: I'm afraid that we as a crypto community are heading
>> for the wrong direction. We need flexibility, i.e., no curves with a
>> very special structure, especially no curves with a specific prime
>> structure as NIST-primes or other proposed primes.
> 
> CFRG and/or IETF aren't about to give you flexibility no matter what
> curves are chosen.  All signs point to choosing a very small number of
> curves.
> 
> Why is this a problem?  If you need to support arbitrary curves,
> you'll do this regardless.
> 
> If, on the other hand, you were implementing, e.g., a CFRG-recommended
> Edwards-coordinate cryptosystem, could you convert to Weierstrass
> coordinates and then use your hardware?  Obviously you can't
> interoperate with someone expecting Edwards coordinates if you do
> this, but if you need a specific wire format for some compliance
> reason, then you can't interoperate with anyone who doesn't use that
> wire format regardless.  Nonetheless, I think you could convert the
> format and still have your hardware work fine.
> 
> 
>> The last statement was common consensus at the recent Brainpool
>> meeting. Other discussed features were not that unanimously. Most of
>> the participants could live with twist-secure curves, less favorable
>> would be the neglection of the property b non-square mod p (because of
>> distinguished point attacks), even less favorable the cofactor
>> question. But it seems to me that all these specific questions can be
>> solved, but the random primes issue is a remaining one. All three
>> participating hardware manufactures (two smart card manufacturers, NXP
>> and Infineon, and one HSM manufacturer) stated that they currently use
>> (and will use) random primes in their coprocessors.
> 
> Can anyone explain why "random" primes are better for blinding?  Keep
> in mind that, from the point of view of an attacker, no common ECC
> protocol uses a random prime; they just use primes without much
> interesting structure.  The adversary knows the prime.
> 
> --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. 

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. 

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. That's a lot easier than power and fault defense, but we're not slacking on the software side either.

-- Mike




> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg