Re: [Cfrg] ed448goldilocks vs. numsp384t1 and numsp512t1

Michael Hamburg <mike@shiftleft.org> Tue, 21 October 2014 17: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 F13A81A1A27 for <cfrg@ietfa.amsl.com>; Tue, 21 Oct 2014 10:12:34 -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 oWhCN5OnNRO8 for <cfrg@ietfa.amsl.com>; Tue, 21 Oct 2014 10:12:34 -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 3ACD01A1A37 for <cfrg@irtf.org>; Tue, 21 Oct 2014 10:11:59 -0700 (PDT)
Received: from [192.168.1.129] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 13E453AA49; Tue, 21 Oct 2014 10:09:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1413911382; bh=RkhqXq2fNxI45BXPozqZUL5P+XHY/h7EWMMZ70GICak=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=Kan8YakIaH8vpfrba1IM9mVJVY+0BFzF1XkalV5HtxZyS/NKm9tAqHiRRtD9KtylL /AeLWpLSLsdEGKZiYG4mlLdGIgXMnF4c4v9NntfP9zYrfAGdRsC6Xth9oKzOqc8Y0C 2VFrIuFtuTht7VbPDFV8LKlYivBJOsmeYtlP2GSI=
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: <20141021110910.GA17139@LK-Perkele-VII>
Date: Tue, 21 Oct 2014 10:11:55 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <5883529A-6CB0-4251-ADB6-9E47AA6C2507@shiftleft.org>
References: <ACC414D4-6651-42C7-B0EF-8E381EE9A0B9@shiftleft.org> <20141018203017.23023.qmail@cr.yp.to> <20141020212441.GA23673@LK-Perkele-VII> <45033A8A-0702-480B-86D7-78CB9A93359B@shiftleft.org> <20141021110910.GA17139@LK-Perkele-VII>
To: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
X-Mailer: Apple Mail (2.1990.1)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/v9eNoKmEl_bMhz-HNgHX0_MZ5O0
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] ed448goldilocks vs. numsp384t1 and numsp512t1
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, 21 Oct 2014 17:12:35 -0000

> On Oct 21, 2014, at 4:09 AM, Ilari Liusvaara <ilari.liusvaara@elisanet.fi> wrote:
> 
> On Mon, Oct 20, 2014 at 03:48:48PM -0700, Michael Hamburg wrote:
>> 
>> On Oct 20, 2014, at 2:24 PM, Ilari Liusvaara <ilari.liusvaara@elisanet.fi> wrote:
>>> 
>>> On Sat, Oct 18, 2014 at 08:30:17PM -0000, D. J. Bernstein wrote:
>> 
>>>> Also signature verification:
>>>> 
>>>>   624000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
>>>>   729152 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
>>>>  1320000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.
>>> 
>>> Here Ed448 seems to be slightly slow for some reason.
>>> 
>>> I would have estimated (on very dubious grounds) ~680k.
>> 
>> For verification, Goldilocks has to decompress and ECCLib doesn’t,
>> which costs almost 10%.
> 
> Signature verification uses double-sclar multiply, right?
> 
> Is your ds multiply constant-time? Because the one in ECClib
> apparently isn't (everything else should be).
> 
> 
> -Ilari

Yeah, it uses pretty much the same WNAF algorithm ECCLib uses, but it burns 60 or 70kcy first to decompress the public key.

— Mike