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

[Watson Ladd <[e-mail]>]

On Thu, Jan 8, 2015 at 7:11 PM, Andrey Jivsov <[e-mail]> wrote:
> On 01/08/2015 01:51 PM, Watson Ladd wrote:
>>
>> Three points:
>>
>> 1: There are recurring security issues caused by not sending
>> compressed points, as well as additional complexity
>> 2: We're not talking about signatures in this draft.
>> 3: Options are bad.
>
>
> Regarding options, this draft is a foundational document of a low-level
> crypto primitive. Protocols above can still pick a single wire format.
>
> The spec should allow, for example, S/MIME to select (x) for space saving,
> while TLS to select (x,y) for performance. (I am not making these choices
> here).

The performance gain you've been repeatedly citing is nonexistent for
variable base multiplications, and can be achieved for fixed based
mults anyway. Let's look at Curve25519 in detail:

A Montgomery ladder implementation does 255 rounds of a differential
addition and doubling, each differential addition 8.2 multiplications
(z=1 initially) This is a total cost of 2091 multiplications. At the
end there is an inversion, cost around 400 multiplications, grand
total 2491.

An Edwards-based implementation, using the fastest coordinates (which
are incomplete: I'll neglect this) with a window of width 5 will first
compute 31 multiples of the basepoint, then carry out 51 additions and
254 doublings. Each point addition costs 9.8 muls, each doubling 6.2
muls. The cheapest computation of the table is 15 doublings and 15
additions. At the end there is again an inversion, cost around 400
multiplications. The cost of this computation is 2714 multiplications.

Now, you could object that I've not used a large enough window, but
larger windows slow down side-channel protected lookups. You could
also object to my eschewing wNAF or some other advanced encoding, but
these are harder to protect against side-channels due to an irregular
pattern of additions. You could try to add in additional inversions to
save on multiplications by forcing z=1, but for curves this size the
gains are small. You could object to my inversion numbers: they are
probably too large.

For fixed based multiplications we use combs, so there is a speedup,
but Montgomery wire format doesn't interfere with this operation.

Furthermore, the TLS WG doesn't know nearly as much about cryptography
as we do. Other WGs are likely to know even less.

>
> The entire document is an optional primitive. SuiteB and Brainpool curves
> will be around for awhile.
>
> One might say that the proposed tweak retains a single format, which is
> (x,y), with an available (internal) optimization to use x with a Montgomery
> ladder.
>
>
> Re: security issues, the easiest fix would be to add one paragraph to to
> check that (x,y) is on the curve. The spec already deals with the cofactor>1
> in section 9.1.

An implementer who omits clearing the low bits isn't going to
completely break everything. One who omits this check will. Despite
lots of documents explaining the necessity of validation, plenty of
implementations fail to do it consistently.

Sincerely,
Watson Ladd

>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin