Re: [Cfrg] [TLS] Curve25519 in TLS and Additional Curves in TLS

[Michael Hamburg <[e-mail]>]

On Jan 23, 2014, at 10:31 PM, Andrey Jivsov <[e-mail]> wrote:

> On 01/23/2014 06:08 PM, Michael Hamburg wrote:
>> On Jan 23, 2014, at 4:59 PM, Andrey Jivsov <[e-mail]> wrote:
>>> 
>>> Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact be another method?
>>> 
>>> Traditionally the problem was solved by carrying 1 bit and then finding a place to fit it in and defining what it means, etc. There is another way. One can adjust the private key to make the coordinate that we drop, x in this case, be the smallest of the two possibilities.
>>> 
>>> The nice feature of my proposal is that you can still also encode the bit if you wish so, as you proposed.
>> 
>> This is interesting, but I think it works better with the Edwards x-coordinate instead of the Montgomery y-coordinate.  That is, it applies well to Watson’s (Montgomery x, Edwards x) representation.  This is because not every point you might want to transmit is a public key; it might be the product of something which does not support an easy negation, such as PAKE.  In this case, with your proposal, implementers have to send the sign bit, and we have two wire formats again.  But if the Edwards x-coordinate is used, you can also fast-adjust by adding the point of order 2, which maps EdX to -EdX.  (It maps EdY to -EdY and MontX to 1/MontX.)  If the protocol wipes out the cofactor (almost every protocol does for security reasons), then this is more likely to be acceptable than negating the point.
>> 
>> Then again, any discussion like this is fraught with issues about alternative encodings for non-wire formats, implementation compatibility, uniqueness, covert channels, etc.  Might take some hashing out.
>> 
>> Cheers,
>> — Mike
>> 
> 
> It seems to me that it will be possible to find an option to tweak the private scalar in more complex protocols, while making this an internal adjustment.
> 
> For example, in
> http://tools.ietf.org/search/draft-irtf-cfrg-dragonfly-02#page-10
> 
> the PE is never sent out, so its generation doesn't change.
> 
> The Element is a point, which is very similar to a public key for our purpose. The Element is sent to the other peer and it needs to be "compliant". The element is generated from a random mask and PE; thus the mask can be adjusted appropriately so that the Element is "compliant" (then the 'scalar' is calculated with the appropriately adjusted mask).


Dragonfly, SPEKE and ECDH don’t use addition, and don’t need y-coordinates at all.  They could use a Montgomery ladder and never compute or transmit those coordinates.

Some systems, such as signatures, use addition but don’t send the results out on the wire.  Your technique works well for those.  You still need a point encoding before hashing, but compression has no value there anyway.

But I can’t think of an obvious way to extend your approach to a protocol like SPAKE2 which requires sending a point out after addition.

— Mike