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

[Robert Ransom <[e-mail]>]

On 1/23/14, Manuel Pégourié-Gonnard <[e-mail]> wrote:
> 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.

Samuel Neves reports that Dr. Bernstein's original Curve25519
implementation for IA-32 does ignore the high bit.

So, the only implementation I know of that does not ignore the MSB is
a horribly slow one that should never be used in production -- I would
not be surprised if it's slower than a typical implementation of the
BND curves.

>> 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?

I still think that avoiding implementation fingerprinting would
justify “implementations SHOULD mask off the high bit”.

Remember that what Dr. Bernstein refers to as ‘public key validation’
in the Curve25519 paper is considerably more expensive than one
bitwise AND:

* With typical (non-twist-secure) curves in x-coordinate-only form,
the recipient must compute the Legendre/Jacobi symbol of x^3 + c*x^2 +
a*x + b in order to avoid operating on the twist.  With Curve25519,
the twist is as secure as the curve which contains the basepoint, so
operating on the twist does not expose the secret key to any useful
attacks.

* The standard advice for handling curves with cofactor >1 is to check
that it is a member of the prime-order subgroup before using it; this
effectively performs the scalar multiplication operation twice.
Curve25519 avoids this by (a) masking secret keys to be divisible by
the cofactor, so the output will be in a subgroup of large-prime order
regardless of the input; and (b) ignoring the widespread
recommendation to reject ECDH keys which have small order.


>> * 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).

>> * 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.

If a future protocol wants to be compatible with implementations of
this protocol, this protocol must specify some form of extension hook.

If you choose a leading byte as the only extension hook, you must
reserve a few alternate leading bytes now, along with enough
information about the formats they will eventually describe that
current implementations will be able to dig a Montgomery-form x
coordinate out of the ECPoint blob.

If you add a leading byte as an extension hook *and* specify an
ECPointFormat value for the current ‘Montgomery-form x’ point format,
current implementations can refuse to receive point formats which they
won't understand.  (This has the slight theoretical disadvantage that
if a future protocol specifies time-based authentication of servers'
ECDH public keys (to avoid the overhead of one signing for each client
connection), implementations of that future protocol may have to sign
more than one type of Curve25519 key per time period.  I don't think
this will be a real problem.)

If you don't add a leading byte, I think the ECPoint length byte can
still be used as an adequate extension mechanism for future non-ECDH
protocols.


>> * 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.

OK.  (Like I said, I'm not sure that anyone will ever want to do that.)


>> 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.

I agree, but future implementations should be allowed to send an
uncompressed second coordinate without breaking compatibility with
implementations of this protocol.  What I'm suggesting is that (a)
current implementations send 32-byte points; (b) current
implementations accept both 32-byte and 64-byte point objects, and
ignore the second half of a 64-byte point.


Robert Ransom