On 1/22/14, Manuel Pégourié-Gonnard <mpg@polarssl.org> 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.)

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.


>> * The draft does not specify the curve equation of Curve25519 or the
>> basepoint for use in ECDH.
>>
> Of course it's no problem to add it. Do you think we should explain the
> arithmetic too (Montgomery ladder + differential addition formulas)?

Only if you will do it well.


>> * The ‘Security Considerations’ section suggests that Curve25519 can
>> be implemented securely using bignum libraries which leak information
>> about the numbers they operate on to a side-channel attacker, as long
>> as the internal projective representation of each point is randomized.
>>  Has this proposed side-channel countermeasure been evaluated?  If so,
>> which types of information leakage does the countermeasure render
>> harmless?
>>
> I'm not aware of any specific analysis of this countermeasure for this type
> of
> curves.

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.


Robert Ransom