Re: [Cfrg] When's the decision?

Michael Hamburg <mike@shiftleft.org> Tue, 07 October 2014 05:20 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 4F50F1A9126 for <cfrg@ietfa.amsl.com>; Mon, 6 Oct 2014 22:20:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 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, HTML_MESSAGE=0.001, 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 lwqIbJigmUEf for <cfrg@ietfa.amsl.com>; Mon, 6 Oct 2014 22:20:56 -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 D849D1A9123 for <cfrg@irtf.org>; Mon, 6 Oct 2014 22:20:55 -0700 (PDT)
Received: from [192.168.1.129] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 5573A3AA49; Mon, 6 Oct 2014 22:19:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1412659175; bh=S4b+T8NJ5u3RgIrojn7tos1eqqqnrTZSPDF6V6L1gJE=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=Gfut0anar2jOXP8GCq/yZy4gZAtGGVCScruqr3hPlH90QS1bRzHpLeinRTMA0o4pS mr8+uSG81IZ9gc8r07IMYd/7Z/hQXKpyNTgrMWNpiTRDeDQ5OPppYEYFRpOty5nDUo TzO0OvMRtWN308jfuyZH63/pfmPVkhuXTaGWEkxA=
Content-Type: multipart/alternative; boundary="Apple-Mail=_22A1AD4A-8FF9-4E4E-B7A8-5D160CCA4A01"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1988\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CACsn0cm8-V6D0E_B_x8c91nQeKkdnrzGO3Azkm+Y02zFJ8AWWw@mail.gmail.com>
Date: Mon, 6 Oct 2014 22:20:53 -0700
Message-Id: <A4BDE147-FC90-4275-81E5-5570FE37F551@shiftleft.org>
References: <CACsn0cnHDc6_jWf1mXc5kQgj5XEc6dBBZa7K8D2=4uLti5e3aA@mail.gmail.com> <3EE5AEA5-3ADE-4D67-AC51-478074349D1B@gmail.com> <5432BBF1.5060003@cs.tcd.ie> <CACsn0cmwJh295=R8Ns3Y01UTLBwoQAg5g_PB=yN6nJUCYxgqnw@mail.gmail.com> <5433671E.9080308@sbcglobal.net> <CACsn0cm8-V6D0E_B_x8c91nQeKkdnrzGO3Azkm+Y02zFJ8AWWw@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
X-Mailer: Apple Mail (2.1988)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/7boI3PqOs411pyG-b88VT2xlg3Q
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] When's the decision?
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, 07 Oct 2014 05:20:58 -0000

> On Oct 6, 2014, at 9:56 PM, Watson Ladd <watsonbladd@gmail.com> wrote:
> 
> On Mon, Oct 6, 2014 at 9:07 PM, David Jacobson <dmjacobson@sbcglobal.net <mailto:dmjacobson@sbcglobal.net>> wrote:
>> On 10/6/14, 4:28 PM, Watson Ladd wrote:
>> 
>> 
>> On Oct 6, 2014 8:57 AM, "Stephen Farrell" <stephen.farrell@cs.tcd.ie> wrote:
>>> 
>>> 
>>> Hiya,
>>> 
>>> On 06/10/14 16:53, Yoav Nir wrote:
>>>> They’re all good enough
>>> 
>>> Tend to agree. But CFRG, pretty-please don't pick them all!
>> 
>> This ignores the significance of choices such as which coordinates to use on
>> the wire, whether to use compression, and which signature scheme to use.
>> 
>> These are not make or break items, and any curve could be used several ways,
>> but these issues do not go away with the choice of curve.
>>> 
>>> If you do we'll just have to pick elsewhere (e.g. saag or
>>> specific IETF wgs) with less clue immediately involved.
>> 
>> Agreed: the buck stops here.
>>> 
>>> S.
>>> 
>> 
>> 
>> I've implemented elliptic curve systems quite a few times.  But never with
>> compression.  (The patent just expired.)  Could someone with experience
>> implementing compression and with the short list of candidates, comment, for
>> each curve, on how much of a hassle compression is to write, how much it
>> expands the code, and how much it slows down the computation?
> 
> Huh? The choice of formula doesn't have much of an impact. For any
> prime not 1 mod 8, a single square root is pretty quick: equivalent to
> a single modular exponentiation. Compression doesn't add much time.

In particular, compression adds almost no time vs sending the point in affine, because you’re mostly just throwing away information.  Decompression costs about 10% of a variable-base scalarmul.  This doesn’t really depend on which curve is chosen.

Edwards point compression has a trick required to implement it efficiently, as described in the EdDSA paper.  But it isn’t terribly complicated.

> Montgomery form never needs compression: the question is whether
> Edwards points should be compressed. This reduces the size of
> signatures, but isn't as critical for security as
> compression/validation of points for use in ECDH.

Depends on the form of your signature, of course.  Traditional Schnorr sigs don’t send the point anyway, and neither does ECDSA, but DJB’s "EdDSA" Schnorr variant does.

> The code bloat is another addition chain, but you can probably take
> advantage of the relation between (p+1)/4 and p-1 when code size is a
> concern.

Yeah, it’s easiest to just base everything on a 1/sqrt(x) subroutine, or if 4th roots are needed for something in the same library, an x^(-3/4) subroutine.  That way the addition chain won’t add bloat.

For compression code bloat, I have some data.  The Ed448-Goldilocks reference code uses an unusually complicated compression mode for kicks: it’s compatible with the Montgomery ladder, conveys sign without a sign bit, and reduces the cofactor by encoding only even points.  According to nm, the code uses 528 bytes for compression and 592 for decompression on Mac clang -O3 with field additions inlined, but not multiplications.  The size doesn’t include the exception handling tables, which probably get stripped anyway because this is C and there are no exceptions.  This is comparable to 560 bytes for a point addition on the same settings.

A more traditional compression method would be somewhat smaller than this.

> Sincerely,
> Watson Ladd
> 
>> 
>> If the hassle, code bloat, and slowdown are minor, I suggest we just do
>> compressed.  (Rationale:  Compression is always a win so do compressed.
>> Keep it simple---no options)

I concur.  I think the code bloat and slowdown will only be a problem for embedded machines, and those are the ones which will feel the size advantage most.  The only exception is that some protocols may have required point formats, but that will be annoying anyway.

Cheers,
— Mike

>> If the hassle, code bloat, or slowdown are considerable, I suggest we
>> require uncompressed and make compressed optional.  (Rationale:  Compression
>> is sometimes a win, e.g. for applications were bits on the wire are
>> precious, and sometimes a lose.  For guaranteed interoperability there
>> should be one variant that is always there, and that one should be the
>> simpler, smaller.)
>> 
>> This probably interacts with the on-the-wire representation.  That will make
>> the deciding a bit harder, but such is life.
>> 
>>   --David Jacobson
>> 
> 
> 
> 
> -- 
> "Those who would give up Essential Liberty to purchase a little
> Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>