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

Andrey Jivsov <crypto@brainhub.org> Thu, 08 January 2015 21:36 UTC

Return-Path: <crypto@brainhub.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 CE06C1A01A9 for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 13:36:26 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.779
X-Spam-Level:
X-Spam-Status: No, score=-0.779 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 5wkqfhpZTfkH for <cfrg@ietfa.amsl.com>; Thu, 8 Jan 2015 13:36:24 -0800 (PST)
Received: from resqmta-po-11v.sys.comcast.net (resqmta-po-11v.sys.comcast.net [IPv6:2001:558:fe16:19:96:114:154:170]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 69C361A1A0B for <cfrg@irtf.org>; Thu, 8 Jan 2015 13:36:23 -0800 (PST)
Received: from resomta-po-16v.sys.comcast.net ([96.114.154.240]) by resqmta-po-11v.sys.comcast.net with comcast id dZbm1p0025BUCh401ZcNkK; Thu, 08 Jan 2015 21:36:22 +0000
Received: from [IPv6:::1] ([71.202.164.227]) by resomta-po-16v.sys.comcast.net with comcast id dZcM1p00k4uhcbK01ZcNj1; Thu, 08 Jan 2015 21:36:22 +0000
Message-ID: <54AEF855.4090100@brainhub.org>
Date: Thu, 08 Jan 2015 13:36:21 -0800
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <54AAE2CA.1080701@isode.com>
In-Reply-To: <54AAE2CA.1080701@isode.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1420752982; bh=1xSMNwpbJpvKCryyHEjCiW/+eoCQxViVf+PbD6VdY8Y=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=YUi4nWEkNHYlSPe3xY79ka7mkk/dw+RIPrvhRFIPkmbTi98cdSsM97x1p/ZbhTUaK MgFPIXxYLYa04rO88osKsqzYZ/fboyGMeECB8Vsb0r4wm6xBjzmqgkTcI52fhJ/Sui HQ22cu7uYpL3l2w8kM67iio1J3xXB0pwPbcmLoKJHS4rkSIYdK/ii3dFD2QjVvTIVy XCoLObYmy6d54DOlPkCf/mGdJP25wsBuxZIsKuHAw3+gNnmSB60KXE8zHxuErwsAwP NjqXarJEaf27yKmIaAFNJylFONzGRp2xhcmRcQFXxaQQTyc+tA+VdxYTo2iHwCTl/7 agwuY8633JYQQ==
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/sp25tJrMkD848hDjRQVDJ1nC19k>
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:36:28 -0000

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.

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.

I support the draft with the above tweak.