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

[Andy Lutomirski <[e-mail]>]

On 01/22/2014 05:17 PM, Robert Ransom wrote:
> On 1/22/14, Manuel Pégourié-Gonnard <[e-mail]> wrote:
>> On 22/01/2014 22:16, Robert Ransom wrote:
> 
>>> * The draft should specify that implementations MUST discard (i.e. set
>>> to zero) the most significant bit of a received public key, for two
>>> reasons: (a) Existing Curve25519 scalarmult implementations differ in
>>> their handling of inputs with that bit set, and could be distinguished
>>> by an active attacker using that difference.
>>
>> I wasn't aware that some implementations ignored the most significant bit.
>> Out
>> of curiosity, could you cite examples?
> 
> curve25519-donna and -donna-c64 ignore the MSB.
> 
> Nick Mathewson (Tor lead developer) tested whether Dr. Bernstein's
> floating-point implementation for IA-32 in NaCl ignores the MSB; he
> reported that it does.
> 
> The ‘ref’ implementation in NaCl does not ignore the MSB.
> 
> I have no idea what Dr. Bernstein's original floating-point Curve25519
> implementation for IA-32 does with the MSB, but the web page
> documenting it hints that it treats the MSB as part of the x
> coordinate.
> 
>> One of the "selling points" of Curve25519 is that no public key validation
>> is
>> needed, so I find it quite unfortunate that after all there is something to
>> do
>> when receiving public keys.
> 
> Fingerprinting of implementations wasn't one of the security concerns
> that Dr. Bernstein had in mind at the time, and it still isn't widely
> considered to be a security risk.  It's certainly minor compared to
> the numerous ways that NSA-curve ECDH implementations can leak their
> keys.
> 
> But the bigger reason to mask off the high bit is extensibility.
> 
>>> (b) Future specifications
>>> may wish to include the sign bit of an Edwards-form x coordinate in a
>>> Curve25519 point format for use with other protocols (e.g. Schnorr
>>> signature, Ace) without breaking backwards compatibility with use in
>>> ECDH.
>>>
>> This is a serious concern indeed. By the way, there was another issue under
>> discussion that is related: should the point format be just the 32 bytes, or
>> should we use a leading byte to follow the existing practice from X9.62, as
>> Salz
>> Rich suggested? If we use a leading byte, maybe it's better to have two
>> formats,
>> one for "x coordinate only", one for "y + bit sign of x"?
> 
> * You appear to be confusing Montgomery form with Edwards form.  The
> Curve25519 paper specifies ‘Montgomery-form x coordinate only’; the
> other format you are suggesting seems to be ‘Edwards-form y coordinate
> with sign bit of Edwards-form x coordinate’.  (Remember that the
> Edwards-form y coordinate is analogous to the Montgomery-form x
> coordinate.)
> 
> * There is no reason to ever transmit an Edwards-form y coordinate for
> use in ECDH.  The formats that would be useful here are
> ‘Montgomery-form x coordinate only’ and ‘Montgomery-form x coordinate
> with sign bit of Edwards-form x coordinate’.
> 
> * If you do not add a leading point-format byte, there is no reason to
> specify the meaning of the high bit in this document.  If you do add a
> leading byte, you will have to choose in this document whether the
> sign bit is for the Edwards-form x coordinate or the Montgomery-form y
> coordinate.
> 
> * Some future applications may wish to transmit an uncompressed
> Edwards-form x coordinate or Montgomery-form y coordinate, not just
> the sign bit.  If you add a leading byte, you'll have to choose which
> coordinate to use now.  Alternatively, you could specify that
> implementations of this document accept 64-byte points and ignore the
> second half of the point structure.  (Note that this means
> implementations of this protocol MUST ignore the second half, even if
> they know how to use it in some other protocol, or they will be
> distinguishable from other ECDH implementations.  I don't think that
> restriction will ever be a problem for ECDH implementations.)
> 
> * Some future (non-ECDH) applications may wish to transmit an
> Edwards-form y coordinate instead of a Montgomery-form x coordinate
> (e.g. so that they can distinguish the point of order 2 from the
> identity).  If you do not add a leading point-format byte now, those
> applications will have to use a different NamedCurve in order to
> indicate that they are incompatible with the point formats used for
> ECDH.  (I'm not sure that this is a problem, or that any such
> applications will ever exist.)

Can someone remind me why any of the above is better than using
ECPointFormat to specify the point format?

--Andy