Re: [Cfrg] ECC reboot

Michael Hamburg <mike@shiftleft.org> Thu, 23 October 2014 20:14 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 09D431ACFEF for <cfrg@ietfa.amsl.com>; Thu, 23 Oct 2014 13:14:09 -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 Q9JJTppK12U5 for <cfrg@ietfa.amsl.com>; Thu, 23 Oct 2014 13:14:06 -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 9A6741A0861 for <cfrg@irtf.org>; Thu, 23 Oct 2014 13:14:06 -0700 (PDT)
Received: from [10.184.148.249] (unknown [209.36.6.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 60BA63AA13; Thu, 23 Oct 2014 13:11:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1414095101; bh=NWLP00PAinYZLYKhiJCLdvHvN5QR5lgKEdigrLDin+E=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=b51NpydGAoxHJsaL24Y3LM9DDRrjMJhduCZCyfBo9d+IrvpVS7QQ1bnJpsW1iYSAQ zvgPyZuTCRLaeLywuD/+AYzWeh2GVihtTsnbVBmF3e8Hp91jD8Oh+sDwbjnCvErw/7 05IpEGv3HR3kK5p8CtBntzrF5cI7Xh/YjzJjZ64Q=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1990.1\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CALCETrVicR0hj3oi1xCwfG9Z0n0PpBsrCCW7AGBo_-tpxcq3Rw@mail.gmail.com>
Date: Thu, 23 Oct 2014 13:14:05 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <0317470A-AA6A-44FA-A831-81CB93204C78@shiftleft.org>
References: <D065A817.30406%kenny.paterson@rhul.ac.uk> <54400E9F.5020905@akr.io> <CAMm+LwhVKBfcfrXUKmVXKsiAMRSTV+ws+u07grmxkfnR2oYJoQ@mail.gmail.com> <5218FD35-E00A-413F-ACCB-AA9B99DEF48B@shiftleft.org> <m3r3y6z3z8.fsf@carbon.jhcloos.org> <CA+Vbu7x4Y_=JZ9Ydp=U5QnJokL28QMQnV4XUn9S6+CUZR9ozEw@mail.gmail.com> <5444D89F.5080407@comodo.com> <90C609A5-ECB2-4FDC-9669-5830F3463D2B@akr.io> <5448DBE2.10107@comodo.com> <CACsn0cne95adtTbCf6WyAZGyCSyLXo5L0302rm7238yHAsE5EQ@mail.gmail.com> <54493DB1.5070204@akr.io> <CALCETrWjR4ROJJFBTo-zAVUg6t50ppm0O_fd=gf2tCr8-evDwg@mail.gmail.com> <CAMm+Lwi-X5_Bh-dwe54uzratLzpds=719F=hzpATCME4wDqxhA@mail.gmail.com> <CALCETrVicR0hj3oi1xCwfG9Z0n0PpBsrCCW7AGBo_-tpxcq3Rw@mail.gmail.com>
To: Andy Lutomirski <luto@amacapital.net>
X-Mailer: Apple Mail (2.1990.1)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/C0CtQXFPdt7oyiGDBJfR7m6-m0A
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] ECC reboot
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, 23 Oct 2014 20:14:09 -0000

> On Oct 23, 2014, at 11:22 AM, Andy Lutomirski <luto@amacapital.net> wrote:
> 
> On Thu, Oct 23, 2014 at 11:17 AM, Phillip Hallam-Baker
> <phill@hallambaker.com> wrote:
>> 
>> 
>> On Thu, Oct 23, 2014 at 1:49 PM, Andy Lutomirski <luto@amacapital.net>
>> wrote:
>>> 
>>> On Thu, Oct 23, 2014 at 10:41 AM, Alyssa Rowan <akr@akr.io> wrote:
>>>>> How long do you think it would take to make an HSM that supports
>>>>> our choice?
>>>> 
>>>> Depends: from what I've seen a few HSMs are flexible enough to run
>>>> whatever we choose. (I'll refrain from discussion of specific vendors:
>>>> it is for them to speak up if they wish.)
>>> 
>>> This seems like a good time to point out that Intel SGX is coming
>>> soon.  With SGX, some performance-critical HSM applications could be
>>> replaced with hardware-assisted secure *software* enclaves on
>>> supported Intel chips.
>>> 
>>> For this application, the relevant factors will be software speed
>>> (because it's just x86 software), freedom from timing attacks, and
>>> freedom from secrets being leaked in memory access patterns.
>>> 
>>> Some users might require certification, but there will be no
>>> additional hardware development effort whatsoever to add new curves.
>> 
>> 
>> And the AVX-512 extensions provide 512 bit native registers.
>> 
> 
> I feel like you're arguing against a straw man here.  Unless I
> misunderstand, the fastest implementations of 512-bit curves don't fit
> in 512-bit registers either.
> 
> Ed448-goldilocks, on the other hand, might.  Mike?

We don’t actually have alternative implementation of NUMS p512, so it’s hard to conclusively say that a 9x57 implementation will be faster, but it seems reasonably likely.

Goldilocks should work well in 512-bit registers.  If Intel has single-cycle PMUL[U]DQ on 512 bits, that will become the largest multiplier on the chip: 8x32x32 -> 8x64 compared to the 64x64->128 scalar multiplier.  The ARM NEON Karatsuba implementation should translate pretty well to that primitive, but the devil is in the details.

On the other hand, Broadwell is slated to introduce ADCX/ADOX scalar carry-handling primitives which should mitigate some of the carry handling issues for packed NUMSp512 math.  It probably won’t be as big a difference as AVX-512, but it’s something.

@PHB: How much experience do you have actually implementing elliptic curves or similar primitives?  You have an awful lot to say about why 512 will be fast in the long run, and I’m curious where that comes from.  Is it “just common sense”, or have you done experiments?

— Mike

>> I don't think it very likely we can persuade any chip vendor to lay down
>> extra signal lines for 521 bits and if they did a 1024 bit data path we
>> would be looking at using all of it, not just 9 extra bits.
> 
> Wait, what?  Are you suggesting using primes closer to 1024 bits?
> That seems even more excessive that 512 or 521 bits.
> 
> --Andy
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg