Curve25519 ECDH with ephemeral key input O

NIIBE Yutaka gniibe at fsij.org
Mon Feb 29 05:46:07 CET 2016


Hello,

While Curve25519 computation is defined as "no input validation"
required, I think that it is good for our ECDH implementation to have
input validation against the point O.

Let's consider a scenario with GnuPG.  While current GnuPG has no
possibility creating such a message, (by some other tool) I could
create an encrypted message by Curve25519 ECDH with ephemeral key of
point O.

Suppose the function Curve25519(k, P) is defined as RFC 7748; The bit
of next to msb and least significant bits of k will be tweaked before
the computation of point multiplication.


In the terms of RFC-6637 (page 7), it's like:

         Obtain the authenticated recipient public key R

  where (r, R): private key, public key

         Generate an ephemeral key pair {v, V=vG}

  Here, I chose V=O, although any value of k to Curve25519(k, P)
  cannot produce O if P != O (because of the tweak).

         Compute the shared point S = vR;

  And I proceed ECDH computation as if S = O.

         m = symm_alg_ID || session key || checksum || pkcs5_padding;
         curve_OID_len = (byte)len(curve_OID);
         Param = curve_OID_len || curve_OID || public_key_alg_ID || 03
         || 01 || KDF_hash_ID || KEK_alg_ID for AESKeyWrap || "Anonymous
         Sender    " || recipient_fingerprint;
         Z_len = the key size for the KEK_alg_ID used with AESKeyWrap
         Compute Z = KDF( S, Z_len, Param );
         Compute C = AESKeyWrap( Z, m ) as per [RFC3394]
         VB = convert point V to the octet string
         Output (MPI(VB) || len(C) || C).

  I send the encrypted message to the recipient.

  The recipient gets the shared point by the computation of:

    S = rV = rvG

  With Curve25519 function, it is:

    S = Curve15519(r, V) = Curve15519(r, O) = O

  Then, the ECDH decryption will be done by recipient correctly.


Note that if the ephemeral public key V = O, it can be also decrypted
by anyone, because Curve15519(any-value, O) = O.  The recipient
usually assumes that it is only possible for owner of private key to
decrypt.  This violates this assumption.


Current situation:

GnuPG doesn't produce O as ephemeral public key, since it always sets
second most significant bit and clears three least significant bits
for the scalar v (the tweak).

Current libgcrypt dumps core when it tries to compute S to be O.
(Fatal: ecdh: Failed to get affine coordinates)

So, it's considered safe.


Possible improvement:

Make libgcrypt return GPG_ERR_INV_DATA when input P=O for
ecc_decrypt_raw.  Possibly, also check scalar DATA against bit-tweak
for ecc_encrypt_raw (or do the tweak by ecc_encrypt_raw itself) to
make sure.
-- 



More information about the Gcrypt-devel mailing list