Re: [Cfrg] On the use of Montgomery form curves for key agreement

Andrey Jivsov <crypto@brainhub.org> Tue, 02 September 2014 21:37 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 8B7501A071F for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 14:37:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] 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 hrNvV0RAOFvW for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 14:37:03 -0700 (PDT)
Received: from qmta07.emeryville.ca.mail.comcast.net (qmta07.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:64]) by ietfa.amsl.com (Postfix) with ESMTP id E56EF1A0707 for <cfrg@irtf.org>; Tue, 2 Sep 2014 14:37:03 -0700 (PDT)
Received: from omta20.emeryville.ca.mail.comcast.net ([76.96.30.87]) by qmta07.emeryville.ca.mail.comcast.net with comcast id mMcz1o0061smiN4A7Md3uu; Tue, 02 Sep 2014 21:37:03 +0000
Received: from [IPv6:::1] ([71.202.164.227]) by omta20.emeryville.ca.mail.comcast.net with comcast id mMd21o00Q4uhcbK8gMd2Ja; Tue, 02 Sep 2014 21:37:03 +0000
Message-ID: <5406387E.4060507@brainhub.org>
Date: Tue, 02 Sep 2014 14:37:02 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com> <CACsn0cktxTyPpeaqKU-oL+DiP4Fu0risHB1Wx8-by+94s30h=g@mail.gmail.com> <CA+Vbu7yMvyPzRAGrtVH38mzaYy3XQ1wswEUQisqbwpT10JfQVg@mail.gmail.com> <54058021.9040801@cs.tcd.ie> <CACsn0c=XV4bQSa7Oh3=s+JvFpJdT3Lm16wQHRG2ACEjxuU-dvg@mail.gmail.com> <5405E343.7010302@cs.tcd.ie>
In-Reply-To: <5405E343.7010302@cs.tcd.ie>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1409693823; bh=9L9a6cdH736WWVNYXiWrEohq2NGJibYcwKHZrgltugQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=k7p9fKfuzWOhn2mxsuvrkinXUcRBZhDY1gH9AB3cqmW+U4rWidY8Nkuq2vCKvPPex 4TbP1IEecVNkMeC5kjeBEVU0rgbRJEk1WyWNm9T3/E/6g5tKhvA2xxQTJuymyhjb0C EFHi4vSwRtMjb7d6YjFS5A9Izx6rtVbVtAMqRZ2DtHaOLE8d+zVamLx8hLuxkr5VGg +CyYff5JarSNcYf43QGKZ6/eTaWSL2LOD4X/eTLKNZWirkvH4NO/BZ2/TubH/U9x11 S4d9RRNqmuJegoO1oiNaBCqdbmY9Tlyza9T13ljSvwCONusIqVYS1iyfpGplds4GFN 9sIY77aFVR1NA==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/sUfHxgbQRDDryO2JUOXlxORiatQ
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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, 02 Sep 2014 21:37:05 -0000

On 09/02/2014 08:33 AM, Stephen Farrell wrote:
> Main point is: I don't believe wire-format issues make any
> difference when picking new curves.

If this refers to which tag to use (i.e. 02, 03, 04 in SEC1), no tag at 
all, endianess, or even point compression, then I can see this.

However, the actual bytes representing a point imply a 10% penalty in 
dual-key uses for "another use" due to the inversion in F(p) (and 
possibly double inversion).

If the format is selected to favour variable base ECDH (Montgomery X), 
there is a 10% penalty to perform digital signature with this key or 
some server-side optimization that depend on the ability to add two points.

The reverse of this is true if the coordinates are on the Edwards curves.

At least this is what follows from 
http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html, 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05035.html, if the 
types of the curves under consideration are Montgomery and -1 twisted 
Edwards.

If it's possible to reduce this penalty for some curves and encodings, 
performance and security being equal, this is a plus for these curves 
(even though the encoding issue will formally be decided later).