Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

Watson Ladd <watsonbladd@gmail.com> Thu, 08 January 2015 21:51 UTC

Return-Path: <watsonbladd@gmail.com>
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 5D12F1A005D for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 13:51:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.878
X-Spam-Level:
X-Spam-Status: No, score=-0.878 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001, URI_HEX=1.122] 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 ZSLj3R3Yhsxn for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 13:51:20 -0800 (PST)
Received: from mail-yh0-x22f.google.com (mail-yh0-x22f.google.com [IPv6:2607:f8b0:4002:c01::22f]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F09D51A0AFE for <cfrg@irtf.org>; Thu, 8 Jan 2015 13:51:19 -0800 (PST)
Received: by mail-yh0-f47.google.com with SMTP id f73so2501947yha.6 for <cfrg@irtf.org>; Thu, 08 Jan 2015 13:51:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=PJfLCLQRsYFy5W9VGTe2AqIo0VLPx8FfgxIfnW0BXKQ=; b=O700XtpLKtV+2Kyv1t7aC7Z7XDMra0RRHwmY34HmjUya2/ThBvwoWthSzE1WOmmvSO sMprm3EvtyTAsx/yRkCgj8FZihIrJORcJLGz9B3ICLcDJ9aUUiLZfVMQRAMZZea5/xPg FAC6smOfDwjBaVggZfvZEPdNmjZ9kkEzXHtChoTETENjUPr0P8IBhKCMGBSCuugrTXpA 3y4UlH7/yrQOpzWx6A/LTFdiJVjsqZadvueCJS9gAXR1a9dkUnpbnqa25prhRcZDcCKX zcsr58LR1yppV1pGREEG79TMdXiEJWpsB3yBQ4BEe+vMp1in7xxBtiEUGqWReCNrcchL 8t6w==
MIME-Version: 1.0
X-Received: by 10.170.89.130 with SMTP id g124mr9927079yka.24.1420753878975; Thu, 08 Jan 2015 13:51:18 -0800 (PST)
Received: by 10.170.207.6 with HTTP; Thu, 8 Jan 2015 13:51:18 -0800 (PST)
In-Reply-To: <54AEF855.4090100@brainhub.org>
References: <54AAE2CA.1080701@isode.com> <54AEF855.4090100@brainhub.org>
Date: Thu, 8 Jan 2015 16:51:18 -0500
Message-ID: <CACsn0cm01o4vhwwzs_WNpLq6vnA_cBchvLNS+Eyg5YZH_hQyMg@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/Mus7Lzp4fJONulWwnw_oGPe3XIE>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
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, 08 Jan 2015 21:51:22 -0000

On Thu, Jan 8, 2015 at 4:36 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> On 01/05/2015 11:15 AM, Alexey Melnikov wrote:
>>
>> This message starts 2 weeks adoption call (ending on January 19th 2015)
>> on:
>>
>> https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml
>>
>> as the starting point for the CFRG document which describes an algorithm
>> for safe curve parameter generation for a particular security level and
>> also recommends a specific curve (2^255-19) for the 128-bit security
>> level.
>>
>> Please reply to this message or directly to CFRG chairs, stating whether
>> you support (or not) adoption of this document. If you do not support
>> adoption of this document, please state whether you support adoption of
>> any alternative document or whether you want a particular change be made
>> to the document before adoption.
>
>
>
> For http://tools.ietf.org/html/draft-agl-cfrgcurve-00:
>>
>>
>> 9. Elliptic Curve Diffie-Hellman
>>
>>
> ...
>>
>>        z_2 = E * (AA + a24 * E)
>>        // Conditional swap; see text below.
>>        (x_2, x_3) = cswap (s_t, x_2, x_3)
>>        (z_2, z_3) = cswap (s_t, z_2, z_3)
>>    Return x_2 * (z_2^(p - 1))
>
>
> should be
>
>      Return x_2 * (z_2^(p - 2))
>
>> 8. Wire-format of field elements
>
>
>>    When transmitting field elements in the Diffie-Hellman protocol
>>    below, they MUST be encoded as an array of bytes, x,
>
>
> I would like to see an uncompressed format allowed as (x,y) as an optional
> format. This avoids ~10% performance penalty for some applications, v.s. the
> case when only (x) is sent.
>
> the y above can be calculated for "free" at the end of Montgomery ladder
> calculation due to the above z_2^-1 inverse calculation, using a method
> described in section 5 (p.13-14) in
> http://ed25519.cr.yp.to/ed25519-20110705.pdf. The code would be needed
> anyway for decompression with signatures that use compressed point.

Three points:

1: There are recurring security issues caused by not sending
compressed points, as well as additional complexity
2: We're not talking about signatures in this draft.
3: Options are bad.

>
> Likewise, receiving (x,y) allows a conversion to a projective form of
> twisted Edwards coordinates for "free" for a peer. At the same time a peer
> is free to ignore y and proceed with the Montgomery ladder multiplication
> exactly as described in sec 9.
>
> Therefore, (x,y) on the wire allows the most suitable choice of
> implementation for ECDH, whereas (x) limits it to Montgomery ladder given
> that one needs to overcome the 10% penalty of recovering y with a square
> root.
>
> Many applications and protocols will require generation of a new ECDH key
> pair (i.e. they cannot reuse it). For these applications fixed-base scalar
> multiplication on Edwards curve is much faster. These applications may
> prefer to use the same code for variable-base scalar multiplication as well.
> Likewise, the code reuse argument applies to applications that support
> signatures on Curve25519.

4: Fixed based scalar optimizations already require different code
from variable base for maximal speed: combs vs. radix. The Montgomery
ladder is so small that using it for variable base multiplication
isn't a major complexity increase.

>
> I support the draft with the above tweak.
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin