Re: [Cfrg] Outline -> was Re: normative references

Michael Hamburg <mike@shiftleft.org> Thu, 16 January 2014 20:44 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 9BE6B1ACCEF for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 12:44:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.156
X-Spam-Level: **
X-Spam-Status: No, score=2.156 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, J_CHICKENPOX_12=0.6, RDNS_DYNAMIC=0.982, 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 dUwkKSVNDuZn for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 12:44:22 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id 80CBD1ABBB1 for <cfrg@irtf.org>; Thu, 16 Jan 2014 12:44:22 -0800 (PST)
Received: from [10.184.148.249] (w035.z205158021.lax-ca.dsl.cnc.net [205.158.21.35]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id CC8BF3AA07; Thu, 16 Jan 2014 12:42:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1389904941; bh=4RPwJtWzdC3sgD3bCc7t8COm8Hp9oCHDHEVO9SrMMi0=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=OPLMbOeFb0/FOjHxXtyAFuC0g7EdAgzs0J7BTR+tXSIZBBhJ5QcintF9EOOlSvShP M+IY+t0kC56ac9cCY8T5RioQPOcKkQwZknR8/+UHJMKdm/5gLlnLO65NPOb1pXFEn2 FIh8Lris8yLmVHKTNxIEwAzLQ2bMH5XkMcF/mTtA=
Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <52D8417B.9030908@cisco.com>
Date: Thu, 16 Jan 2014 12:44:08 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <DE877BC0-E5DA-406B-8CE6-0C3175912E62@shiftleft.org>
References: <CEFC6B5C.2C6E8%paul@marvell.com> <CACsn0ckSMUbEJ4F3bQ5KVMbhdPQw1MTMCce6B8uhMfA_V0Nupw@mail.gmail.com> <CEFCBB2E.2C792%paul@marvell.com> <3C4AAD4B5304AB44A6BA85173B4675CABA9A493F@MSMR-GH1-UEA03.corp.nsa.gov> <52D8417B.9030908@cisco.com>
To: David McGrew <mcgrew@cisco.com>
X-Mailer: Apple Mail (2.1827)
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Yaron Sheffer <yaronf.ietf@gmail.com>
Subject: Re: [Cfrg] Outline -> was Re: normative references
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, 16 Jan 2014 20:44:23 -0000

On Jan 16, 2014, at 12:30 PM, David McGrew <mcgrew@cisco.com> wrote:

> Hi Kevin, Paul, and Watson,
> 
> Watson said in a previous email:
> >
> > Montgomery curves are here for their blazing speed in ECDH without large tables.
> > Edwards curves are here for their blazing speed in signatures where we can't toss out
> > one coordinate. I'ld much rather use Montgomery for ECDH and Edwards
> > for signatures than Edwards for everything.
> 
> So, what would this mean for an implementation that uses both ECDH and an EC signature?   That the math routines for both Edwards and Montgomery need to be included?    Or is translation between the formats very efficient?  If a single curve type and a single set of math/algorithms could be used for both, then an implementation could be simpler and more compact, and could perform better in software.

It is preferable to include both formats.  It is possible to use Edwards for ECDH or Montgomery for signatures, but it is not ideal speedwise.  Anyway, whereas Montgomery implementations can be extremely simple, Edwards implementations are usually significantly more complex (because they need complexity to extract maximum performance, unlike the Montgomery ladder).  For curves larger than 256 bits, authors probably won’t inline their multiplication formulas into their laddering, so I don’t think the extra formulas will hurt much.

Conversion hurts Montgomery curves more than it hurts Edwards curves, so it might make sense to use only Montgomery form for the wire format.  The conversion adds non-negligible complexity, though, especially because fast conversion routines may vary between curves.

On the other hand, if the wire format is Montgomery, then a *really* space-constrained device could use Montgomery for signatures as well as ECDH without too much pain.

> David

Cheers,
— Mike