Curve25519 ECDH with ephemeral key input O

[Ian Goldberg]

On Tue, Mar 01, 2016 at 09:06:41AM +0900, NIIBE Yutaka wrote:
> On 02/29/2016 10:17 PM, Ian Goldberg wrote:
> > On Mon, Feb 29, 2016 at 01:46:07PM +0900, NIIBE Yutaka wrote:
> >>   although any value of k to Curve25519(k, P) cannot produce O if P !=
> >>   O (because of the tweak).
> > 
> > This line does not sound true to me.  If k is the order of the point P
> > (or 0, for that matter?), why would Curve25519(k, P) not output O (or
> > more correctly, the all-0 string)?
> 
> Sorry, I should have clarified the context.  I am talking about
> Curve25519 specified in RFC 7748.  It's not only a point
> multiplication of [k]P.  Because of the function decodeScalar25519(k)
> which changes the bits (to be multiple of cofactor), the scalar can't
> be the order of the point P.

Sure it can.  (Well, it can be 8 times the order, but that amounts to
the same thing.)  What happens if you feed in k = 8 * (2^252 +
27742317777372353535851937790883648493)?

> 
> More simply, my question is:
> 
>     When an implementation (GnuPG in our case) is offered the input of
>     all-0 string as ephemeral key for Curve25519 ECDH, what should it
>     do?
> 
>     The situation:
> 
>     * It can be decrypted by the recipient.
>     * But it can be also decrypted by anyone.
>     * It is not generated by the correct procedure.
> 
> My opinion is that GnuPG should results an error as invalid input data,
> although the computation of Curve25519 itself is defined with such a
> data.

It's not just the all-0 string that is problematic in this way.  From
https://cr.yp.to/ecdh.html :

    There are some unusual non-Diffie-Hellman elliptic-curve protocols
    that need to ensure ``contributory'' behavior. In those protocols,
    you should reject the 32-byte strings that, in little-endian form,
    represent 0, 1,
    325606250916557431795983626356110631294008115727848805560023387167927233504
    (which has order 8),
    39382357235489614581723060781553021112529911719440698176882885853963445705823
    (which also has order 8), 2^255 - 19 - 1, 2^255 - 19, 2^255 - 19 +
    1, 2^255 - 19 +
    325606250916557431795983626356110631294008115727848805560023387167927233504,
    2^255 - 19 +
    39382357235489614581723060781553021112529911719440698176882885853963445705823,
    2(2^255 - 19) - 1, 2(2^255 - 19), and 2(2^255 - 19) + 1. But these
    exclusions are unnecessary for Diffie-Hellman.

If you're worried about contributory behaviour (if your side is behaving
properly, then the session key is random, even if the other side is
faulty), then you should worry about the above values as well.  I don't
think it's a big deal to worry about it with DH, but did I see you say
that currently libgcrypt crashes on the all-0 input?  That would be bad.

   - Ian