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

[Mike Hamburg <[e-mail]>]

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