Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Andrey Jivsov <crypto@brainhub.org> Sun, 25 January 2015 21:35 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 094BC1A86EF for <cfrg@ietfa.amsl.com>; Sun, 25 Jan 2015 13:35:16 -0800 (PST)
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 tf65wS3nOzGi for <cfrg@ietfa.amsl.com>; Sun, 25 Jan 2015 13:35:13 -0800 (PST)
Received: from resqmta-po-12v.sys.comcast.net (resqmta-po-12v.sys.comcast.net [IPv6:2001:558:fe16:19:96:114:154:171]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 971D01A000C for <cfrg@irtf.org>; Sun, 25 Jan 2015 13:35:13 -0800 (PST)
Received: from resomta-po-20v.sys.comcast.net ([96.114.154.244]) by resqmta-po-12v.sys.comcast.net with comcast id kMaV1p0045Geu2801MbDHg; Sun, 25 Jan 2015 21:35:13 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by resomta-po-20v.sys.comcast.net with comcast id kMbC1p0064uhcbK01MbCVp; Sun, 25 Jan 2015 21:35:12 +0000
Message-ID: <54C56190.2060407@brainhub.org>
Date: Sun, 25 Jan 2015 13:35:12 -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: Watson Ladd <watsonbladd@gmail.com>, Andrey Jivsov <crypto@brainhub.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com> <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org> <CACsn0ck6q9nxioS7q66MkB6M+YmaGj=Nmqop1LQ-DuG0q78GaQ@mail.gmail.com> <54BCAE24.6020408@brainhub.org> <CACsn0ckb6t_bsAocYnBhiqRkaJ3HExF4QNDf83riQqc=uHdQ0A@mail.gmail.com> <54BF6B8C.2020707@brainhub.org> <CACsn0cn9vT8QnaKhZx5LQ1FSjRyagOzHDnW9Ub=xvV93E4EBJw@mail.gmail.com>
In-Reply-To: <CACsn0cn9vT8QnaKhZx5LQ1FSjRyagOzHDnW9Ub=xvV93E4EBJw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1422221713; bh=2MPOgHvNQ4N8yNBYURwvDnMTkePI/hwXnbR6aIZsbOQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=qf0vJT1/osFx+NRARPoYgKQsDkdS0/jMNSFUciyHsobjIzKhnj19ocm+lRkksSIJV otxWXMzfGKvgpGcVt9p93nyEOYBGhOYCQ5Jwie0DsVkPxSHu2pcHgBXJcuiSnO+4b3 FBXxM/r+324x05lAwQJtkKkFx9Pxn73myB7jRByCV6mrVHJoMrAoKD3ocfB5V/GAb3 k8Y3s+Dyb9mstjKB0Ug+Mz4OdXYXG91VaqsgkL2wMumy32piJ7vQ1kPs+4SvZohvpp QtKd8IVwe/xhyBzeMRebyySILG9gJx2c4ilnXe2E2thXtp0BSFqw2pkB/s0vvw9QO6 bKwD7vnZEIOEw==
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/eoEAsUl2lGVZzZ1NubHal6gJorg>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
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: Sun, 25 Jan 2015 21:35:16 -0000

On 01/21/2015 05:39 PM, Watson Ladd wrote:
> On Wed, Jan 21, 2015 at 1:04 AM, Andrey Jivsov <crypto@brainhub.org>; wrote:
>> On 01/19/2015 04:20 PM, Watson Ladd wrote:
>>> And once again, the Montgomery ladder is extremely small in codesize,
>>> one the field operations are implemented. Or is there some other
>>> benefit I don't understand you are thinking of?
>>
>> The benefits of using extended twisted Edwards coordinates would be:
>>
>> * An order of magnitude faster key generation (this is a part of signature
>> generation or ECDH ephemeral key generation)
>> * Ability to add points (needed for signatures and many other protocols)
>> * The same code can do what Montgomery ladder does (variable case
>> scalarmult) at the same speed.
>>
>> It plausible that a library that needs more then ECDH variable base
>> scalarmult would implement the above operations without the Montgomery
>> ladder.
>>
>> However, if there there is a penalty to recover 'y', that unified
>> implementation is less likely to happen.
> And the cost here is what? Note that your first bullet point is false:
> the comb method on twisted Edwards can deliver a point on a Montgomery
> curve, with minimal change in performance. I agree we would be using
> twisted Edwards for signatures and protocols that require addition
> (although Mike Hamburg has some ideas on safer point formats, based on
> Jacobi quartics). But that doesn't mean we should use the same method
> for ECDH: there are security advantages which your proposal doesn't
> have.
>
> Once again this got discussed extensively over the summer.

You are proposing to use a Montgomery ladder for second flight of ECDH 
(variable base). There is a benefit of simplicity of code here and 
protection against timing attacks for free, but not much of performance. 
This makes sense.

The first flight of ECDH (fixed-base) is too slow with same 
implementation used for variable base (or any key generation), and so 
you propose to use a discussed over the summer idea to have another type 
of Montgomery ladder (which I couldn't locate). It won't be as simple as 
the first Montgomery ladder and it will probably be more complex as a 
simple ~20 additions of points from a pre-computed read-only table.

This, however, still doesn't solve the problem of digital signatures and 
SPAKE, which need to add points.

For example, in https://tools.ietf.org/html/draft-ladd-spake2-01 each 
peer does 1 fixed-base, 2 variable-base, 2 addition. I would do this 
with a single implementation of a curve formula (e.g. using extended 
twisted Edward).

IMO a library like OpenSSL that anticipates to implement most of these 
algorithms *may* consider a single implementation that can add points 
with no performance loss.