Re: [Cfrg] When's the decision?

David Jacobson <dmjacobson@sbcglobal.net> Tue, 07 October 2014 05:35 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 C58031A9125 for <cfrg@ietfa.amsl.com>; Mon, 6 Oct 2014 22:35:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=ham
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 F0A0izKm-J7m for <cfrg@ietfa.amsl.com>; Mon, 6 Oct 2014 22:35:44 -0700 (PDT)
Received: from nm22-vm1.access.bullet.mail.gq1.yahoo.com (nm22-vm1.access.bullet.mail.gq1.yahoo.com [216.39.63.20]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8A8B71A9123 for <cfrg@irtf.org>; Mon, 6 Oct 2014 22:35:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1412660144; bh=qAO27/aLB+AOZRddGGB23LC0FROziQH9dSlNvAGPYcU=; h=Received:Received:Received:DKIM-Signature:X-Yahoo-Newman-Id:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type:From:Subject; b=zf6+yP6aCZLJk+pAdXuJSCXBMbjqEhGpcAlPVYJzUmxHxZDfefKqEZnKUURJ0d5+S+GZorj0TQZNjKmPHgHwdhhE2l+z6t5Hd1N6CkYjdZfdD66x07V6MER3vBnkVtr8FPzLEEbmWHRY5aK+Vhla5etaveYOUtr/iaY+Z3AvtVI=
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=sbcglobal.net; b=Fw5Zga/ynkk1OLQ1pdvp3A2ltYKaqdRnv+SM1W90nIpIsCqD/+QBUirvS2mJQYI1Nzg+RQ4tCYqS2v0dUThq23y2Z8uGersiY3rtXOvcj2zGiLHSIDg5Hm9TQEzu9hVPPsP2B+ESaOsgT29gI4WzAQcqWpH1j2QvdxsHNqdekrg=;
Received: from [216.39.60.176] by nm22.access.bullet.mail.gq1.yahoo.com with NNFMP; 07 Oct 2014 05:35:44 -0000
Received: from [67.195.22.118] by tm12.access.bullet.mail.gq1.yahoo.com with NNFMP; 07 Oct 2014 05:35:44 -0000
Received: from [127.0.0.1] by smtp113.sbc.mail.gq1.yahoo.com with NNFMP; 07 Oct 2014 05:35:44 -0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1412660144; bh=qAO27/aLB+AOZRddGGB23LC0FROziQH9dSlNvAGPYcU=; h=X-Yahoo-Newman-Id:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:References:In-Reply-To:Content-Type; b=H5IfJP/wu/wlkOr3l+YVnjFm4DBnD8ooXbgnW849GXNOWGWraxmm+yl3vvYxgx1Q31R7NAKyRXlvY4SjK88wNOpWTeTC/Q54NWowd/Ui0SvUgmrq2yWr5yRhT05BA/50vlk4zUIsW/dvEJo6FAEQggGnN/gWBeishBtPtphXqmg=
X-Yahoo-Newman-Id: 263251.6854.bm@smtp113.sbc.mail.gq1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: NzBBycYVM1lwxEKTkvjy.GsHz03QjXEIIaJSLTE15IEhE8M iWMf6ezDIJeYlruK1_M4AcyJuVwVJ05NKvM5esmeFOJF.PBQgrvLBlsrFYKC gs6zQnbMvyCemgmuwglUQaLjEENsHGkaJGj18tX95gPcSF6jXq7NFveUeDKy NGJtDcsWPKglza4jPrXlEB5FuuaxHoHElRlIN19rjyPCvRVc5_dEezRtKBcQ GoMnQKvL_OEIFw5sSBqptMDwveV8VtwDkki6yqCyuPEdK.l8gnxD6rvzKhQi ad3FOzpslzsxT.mEDjFXaTWfaM6tW3TumcD0H5kmJYdoFw2WiGVlsStSMDQY qMfX0k8Aka.tbx0_IX_Oq6oxoJGNOgFYWMZ.IW0jQYTgBWuCHL.25nCR3K0w IxyANHK5MV9doliJl7YhRW_LP105CgXlJqPZc8nOuiU4DA_AgwLmX9jXC7gU Od3VajqM3uDpKDiubgajZj50cLIPzrMa6jBb2ls8j1ucdl8Dpgw93LinjwvO pRseSpJ443nsv.FA9L9D_R1UwMNUr4_.jvo6.dQ9OtShg3Dw8
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
Message-ID: <54337BAF.30104@sbcglobal.net>
Date: Mon, 06 Oct 2014 22:35:43 -0700
From: David Jacobson <dmjacobson@sbcglobal.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Michael Hamburg <mike@shiftleft.org>, Watson Ladd <watsonbladd@gmail.com>
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> <A4BDE147-FC90-4275-81E5-5570FE37F551@shiftleft.org>
In-Reply-To: <A4BDE147-FC90-4275-81E5-5570FE37F551@shiftleft.org>
Content-Type: multipart/alternative; boundary="------------020500000706090104010209"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/VdwGNP7_mMhwyqB5shayams0zic
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:35:47 -0000

On 10/6/14, 10:20 PM, Michael Hamburg wrote:
>
>> On Oct 6, 2014, at 9:56 PM, Watson Ladd <watsonbladd@gmail.com 
>> <mailto: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 
>>> <mailto: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
>
We should probably wait a day or two to see if there are any opposing 
opinions.  But given the response from people who have implemented 
compression, I'd lean towards compressed as the only option.

    --David