Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

[Michael Hamburg <[e-mail]>]

> On Mar 16, 2015, at 1:04 AM, Andrey Jivsov <[e-mail]> wrote:
> 
> On 03/15/2015 11:50 PM, Michael Hamburg wrote:
>>> On Mar 15, 2015, at 10:26 PM, Andrey Jivsov <[e-mail]> wrote:
>>> 
>>> In my proposal the v, the second coordinate, is only sent in the first flight (or a part of the public key in general). That's where we can expect that the Montgomery ladder will be less common. The second flight, the shared secret calculation, doesn't use v and thus there is no change to the Montgomery ladder.
>>> Each 32 bytes arrive every 1/((200*10^6/8)/32) = 0.00000128 seconds (every 1.2 microsec on 200 Mbps). While we seem OK with the *whole* quad-code CPU, the CPU is a precious resource on a busy server (so in reality we are not OK in this scenario). Why pay 10% penalty?
>>> 
>>> If we look at https://tools.ietf.org/html/rfc5246#section-6.2.1, the World is wasting 2 bytes per each
>>> 2^14 bytes of traffic in the best case scenario. There is also some waste in 4K handshake and block cipher padding that could be eliminated.
>> I understand that there are implementations out there other than the Montgomery ladder, and they
>> require more compute time if you don’t send a v coordinate.  It may be worth discussing further
>> whether the communication cost to send v is more or less than the cost for the recipient to compute
>> it, though I still expect that in most cases it is cheaper to recompute v.
>> 
>> But this just doesn’t make sense for ECDH.  You want to force *every* implementation, of
>> which the considerable majority will probably be the Montgomery ladder, to send and receive an
>> 32 extra bytes.  You want to add non-negligible extra complexity to the simplest implementations
>> (IOT) to make this happen.  You want this so that a small (and so far hypothetical) minority of
>> implementations can make a tradeoff of compute time vs communication that *still* might be
>> unfavorable.  I just don’t see how this adds up.
> 
> The protocols that cannot afford a few additional lines of code like in the diff https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4 might standardize on u only ( as I wrote in http://www.ietf.org/mail-archive/web/cfrg/current/msg06480.html ). I would like to hear more about these protocols, though.

Maybe this doesn’t exist in the use cases of TLS, even though IoT devices can be pretty limited.

I work in the deeply embedded space, where every byte of code or data costs something.  At some point I wrote NIST p256 math and point add, double, and isqrt in 600 bytes of code.  We ended up not needing it for that project but we are likely to need something similar for the next one.  It was isqrt instead of inverse so that we could decompress points, because even with code limitations we couldn’t afford to store public keys uncompressed in NVM.  The bandwidth wasn’t a problem in that project, though.

> On the Internet in general (YouTube, Netflix streaming) and TLS in particular, it's hard to see that ~32 bytes per (not reused) handshake matter. This part of the Internet is currently using uncompressed points and RSA.

I agree that we’re arguing over minutiae, but I’m not satisfied with “wasting 32 bytes for no clear purpose is a good idea because other people waste bytes too”.

— Mike