Re: [Cfrg] Hardware requirements for elliptic curves

Mike Hamburg <mike@shiftleft.org> Fri, 12 September 2014 03:12 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 44E0C1A02FC for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 20:12:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.502
X-Spam-Level: ***
X-Spam-Status: No, score=3.502 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DATE_IN_FUTURE_06_12=1.947, 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 ILf_vBedjZi7 for <cfrg@ietfa.amsl.com>; Thu, 11 Sep 2014 20:12:02 -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 1DE101A02F8 for <cfrg@irtf.org>; Thu, 11 Sep 2014 20:12:01 -0700 (PDT)
Received: from [192.168.1.102] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 9FA673AA12; Thu, 11 Sep 2014 20:08:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1410491331; bh=tlA62qtN/8+6V+ZTDRbq3anjNwqUVsQURmFnhzdGFM0=; h=Date:From:To:Subject:References:In-Reply-To:From; b=KqnyUT+S1euB5jhYla2qcKbxe63Ish0evsf3AX+IfusyMZFzJODYLFupZ38i5OPHe 5UBH8L1BipDOPjiWq3uejEtfTwMXa1361VH/EWWfwPM26hAVqA1DFuPkABEDa2JVug Q/IARabshNqLBGWYWlHfJZR6AiQOHtaUj9QIfItE=
Message-ID: <5412C6EE.8000405@shiftleft.org>
Date: Fri, 12 Sep 2014 03:11:58 -0700
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Torsten Schuetze <torsten.schuetze@gmx.net>, "cfrg@irtf.org" <cfrg@irtf.org>
References: <5411E4BB.3010000@gmx.net>
In-Reply-To: <5411E4BB.3010000@gmx.net>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ZZ4wbrt7vtWGApmz8xzPq-w68NE
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, 12 Sep 2014 03:12:03 -0000

On 9/11/2014 11:06 AM, Torsten Schuetze wrote:
> On Sep 11, 2014 09:22:53 -0700 Mike Hamburg <mike at shiftleft.org>
> wrote:
>
>> 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.
This is interesting but fairly far afield, so I might rather continue 
this part of the thread offlist.
>> 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.
The adversarial model of most crypto software these days is that the 
attacker is running on the same machine as you, as an unprivileged user, 
and through timing channels he can see enough of your data access and 
control flow patterns that they had better not correlate with secret 
data.  This is at least true for OpenSSL (it fails sometimes, though), 
Curve25519 (NaCl, Donna), Goldilocks, and MS NUMS.
>> 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
Right, of course.  And by "power", I meant to include EM, the attacks 
and defenses being very similar in nature.

Thanks for the info,
-- Mike