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

Mike Hamburg <mike@shiftleft.org> Tue, 06 January 2015 08:11 UTC

Return-Path: <mike@shiftleft.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 3B6D31A9122 for <cfrg@ietfa.amsl.com>; Tue, 6 Jan 2015 00:11:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 oN21ht9S-e58 for <cfrg@ietfa.amsl.com>; Tue, 6 Jan 2015 00:11:26 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B755C1A911D for <cfrg@irtf.org>; Tue, 6 Jan 2015 00:09:49 -0800 (PST)
Received: from [192.168.1.102] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 221503AA43; Tue, 6 Jan 2015 00:07:16 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1420531636; bh=OlBg3XUdn+9VEmXevXxmauXVK9OJrIlRi0Jq833NRuE=; h=Date:From:To:CC:Subject:References:In-Reply-To:From; b=UZ3WwZNszodA31xdGnz8HbiHl5RbnIB8G9eGclzMt+8u+jrR9NM8OmAKpdJYa7L1y NJQPzI2wSHUnGbeY4EI1uQ1ALwWI+eUWCo+GjbnfrseqOqUp/lZj6eCmF0xJjGFc81 JhdTvELE4ISGbGbnxeCcLlGAkyXqpWw6NnpN8Ync=
Message-ID: <54AB984B.90009@shiftleft.org>
Date: Tue, 06 Jan 2015 00:09:47 -0800
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: Andrey Jivsov <crypto@brainhub.org>
References: <54AA4AB9.70505@brainhub.org> <54AA5AD3.9020009@shiftleft.org> <54AAEEFC.9060309@brainhub.org> <EBF3EC55-3057-496A-8BAE-7EAD405518A7@shiftleft.org> <54AB194A.6020104@brainhub.org> <322BA3AD-7F5F-4A77-ADBA-7E5260DC690A@shiftleft.org> <54AB7AB9.10604@brainhub.org>
In-Reply-To: <54AB7AB9.10604@brainhub.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/AiVrqyRKE87qEzyZXNJ1onA-FTQ
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: Tue, 06 Jan 2015 08:11:28 -0000

On 1/5/2015 10:03 PM, Andrey Jivsov wrote:
> On 01/05/2015 04:04 PM, Michael Hamburg wrote:
>> 2^13 >> 2^7.
>
> Understood, but diverse implementations would be free to choose any 
> the most suitable value of w for the same format on the wire.
>
> Contrast this with Montgomery coordinate on the wire, which can be 
> viewed as an implementation with fixed w=1 (but fewer F(p) per w).
You can use an Edwards fixed-window method to generate ephemerals in 
Montgomery-x wire format.  Ed25519-donna already does this.

> As a side note, I think that only 2^w / (256/w) need be protected. 
> W.g. for w=13 there are 20 sub-tables Ti, where Ti is always accesses 
> in step i=[0,19]. The access within each Ti may need side channel 
> protection, if this fits a threat model. These Tis are public, 
> read-only tables that can be shared between processes and can reside 
> in ROM.
Sure, but protecting 2^13 (or 2^12) points per comb is not going to come 
cheap.  In my measurements the highest speed was about w=5 or 6.

As a side note of my own, all the cool kids are using combs for 
fixed-point scalarmuls these days.  They provide a better tradeoff of 
performance to table size.  The only issue is that one '907 patent, 
which I'm pretty sure doesn't apply to my combs... but MS hasn't gotten 
back to the list on that yet.
>>
>> The same fixed-base code is likely to be used for both ECDH ephemeral
>> keygen, and for signing.  This sort of leak in signing code could be
>> disastrous.
>
> Shouldn't it be possible to get a value T[i] from a public table T 
> with a private i in a secure fashion?
>
> In the worst case an implementation can use Montgomery ladder 
> internally if this is the most suitable option.
Yeah, vs timing attacks you can use vectorized AND/OR/mux/whatever to do 
it.  Vs power attacks you might just have to go back to direct RAM 
access, blind a lot and hope it's enough.

>> Also, converting to an isogenous curve will be done in projective form
>> in practice, so it’s “free”.
>
> Thinking more about it, here is an interesting observation (probably 
> that's what you meant).
>
> Let's say that the wire coordinates are twisted Edwards (x,y).
>
> The implementation that wants to use the t.Edwards curve will use 
> (x,y) directly, validating the point as needed first.
>
> An implementation that wants to use Montgomery ladder will do
>
>   X = -(y+1)
>   Z =   y-1
>
> and proceed with the currently written X25519 code, other than it will 
> use initial Z=y-1 v.s. Z=1. An interesting fact is that the (x,y) can 
> be compressed as (y) and this will work without decompression penalty 
> with a Montgomery ladder.
It's cheaper to divide by Z up front (+~256S) than to multiply by both Z 
and X at each step (+~256M).  There is also an Edwards curve y-only 
ladder but it's significantly more of a pain than the ladder on 
Montgomery curves.
> This is significant because doing it as in Adam's draft doesn't seem 
> to avoid 10% penalty in some cases, specifically, if an implementation 
> uses Edwards formula I think one needs to obtain Y for Montgomery X 
> first, which involves a square root. This makes sense because Edwards 
> calculation needs both (x,y), while Montgomery formula -- only X (and, 
> even better, X happen to depend only on y).
>
> This is largely from 
> http://www.ietf.org/mail-archive/web/cfrg/current/msg05113.html, which 
> relies on http://eprint.iacr.org/2008/013.pdf .
>
> This means that the format on the wire is
>
>   compressed:   t.Edwards (y)
>   uncompressed: t.Edwards (x,y)
>
> and the conversion to Montgomery is indeed free.
I actually meant the opposite.  Sending Montgomery (x,y) or similar is 
easier because the Edwards math won't be hurt as much by a projective 
input point -- it's like 1-2% instead of 10%.  Though that does mean you 
can't encode the identity anymore.

Cheers,
-- Mike