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

[Robert Ransom <[e-mail]>]

This is relevant to CFRG discussions as well, and I don't know whether
everyone on the CFRG list is also subscribed to the TLS list.

---------- Forwarded message ----------
From: Robert Ransom <[e-mail]>
Date: Thu, 23 Jan 2014 13:37:18 -0800
Subject: Re: [TLS] Curve25519 in TLS and Additional Curves in TLS
To: Manuel Pégourié-Gonnard <[e-mail]>
Cc: [e-mail]

On 1/23/14, Robert Ransom <[e-mail]> wrote:
> On 1/23/14, Manuel Pégourié-Gonnard <[e-mail]> wrote:
>> On 23/01/2014 02:17, Robert Ransom wrote:

>>> * 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.
>
> I think that's easiest (provided that current implementations also
> accept 64-byte points and discard the second half; see below).

On further thought, there is a major technical benefit to sending
(either all of or a sign bit for) the Edwards-form x coordinate rather
than the Montgomery-form y coordinate.  Denoting the Montgomery-form
point as (u, v) and the Edwards-form point as (x, y), the isomorphism
from Montgomery form to Edwards form computes x = 2 u/v, which is
undefined for the point of order 2 (Montgomery (0, 0)).

I think that issue, combined with the fact that implementations which
use the sign bit will almost certainly use Edwards form internally,
should rule out any use of a Montgomery-form y coordinate in any
current or future protocol.

Since Curve25519's coordinate field order is congruent to 5 mod 8,
there is no notion of ‘principal square root’, and thus no plausible
alternative to using the least significant bit of a coordinate as its
sign bit.  So there is only one likely choice of sign bit for
Curve25519 group elements, and that is the LSB of the Edwards-form x
coordinate.

Now that I'm not worried about what will eventually be chosen as the
sign bit, the only reason I can see to use a leading magic byte in the
point format is to distinguish ‘the sender did not compute the sign
bit of this point’ from ‘the sender computed the sign bit of this
point, and it is 0’.  I have previously suggested that distinguishing
those cases could be useful, but now I think mitigation of
implementation fingerprinting is more important -- I see no reason to
advertise whether an implementation computes the sign bit of its group
elements or not, even if an attacker could infer that piece of
information after a series of connections.


Robert Ransom