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

[Manuel Pégourié-Gonnard <[e-mail]>]

On 23/01/2014 02:17, 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.
> [...] 
> The ‘ref’ implementation in NaCl does not ignore the MSB.
> [...]

Ok, thanks for the information.

> 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.
> 
I fully agree it's the bigger reason. As discussed below, there is probably some
other ways to achieve extensibility, so if extensibility wasn't a concern, would
you think that avoiding implementation fingerprinting is more valuable than
being able to accept any string as a public key without no validation or masking?

>>> (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.)
> 
I misinterpreted your suggestion indeed. I read "Edwards" and immediately
thought that you were talking everything in Edwards form (hence the y
coordinate), which would have made little sense in this context.

> * 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.
> 
Or we could add a leading byte now and say that the meaning of the msb is not
defined yet an reserved for future use (which is what you suggest anyway, IIUC).
Then a future document could update the meaning of this leading byte.

> * 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.)
> 
I'm afraid I didn't get your point. Why would we have to choose which coordinate
to use now? If we add a leading byte meaning "the 32 bytes of the x coordinate
(Montgomery form) follow"[1], and if people later want to be able to transmit
two full coordinates, then they will pick a new leading byte and they will have
to choose which coordinates to use with it, not us.

[1] With some clarification about the msb as discussed above.

> * 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.)
> 
My humble opinion is that those applications should use a different NamedCurve
indeed.

> I'm currently leaning towards ‘just reserve the high bit and tell
> implementations to accept and ignore the second half of a 64-byte
> point structure’, but there may be good enough arguments for using a
> magic byte to justify the minor downsides.
> 
Transmitting 64 bytes when 33 (32 + leading byte allowing future extensions) are
enough will probably be seen as a waste by many people.

> Then either (a) don't recommend that countermeasure as an alternative
> to using constant-time field operations, or (b) explicitly warn that
> there is no evidence that that countermeasure will be sufficient to
> protect against side-channel attacks.
> 
Right.

Manuel.