From: NIIBE Yutaka <gniibe@fsij.org>
Date: Fri, 25 Aug 2017 18:13:28 +0900
Subject: ecc: Add input validation for X25519.
Origin: https://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commitdiff;h=da780c8183cccc8f533c8ace8211ac2cb2bdee7b
Bug-Debian-Security: https://security-tracker.debian.org/tracker/CVE-2017-0379
Bug-Debian: https://bugs.debian.org/873383

* cipher/ecc.c (ecc_decrypt_raw): Add input validation.
* mpi/ec.c (ec_p_init): Use scratch buffer for bad points.
(_gcry_mpi_ec_bad_point): New.

--

Following is the paper describing the attack:

    May the Fourth Be With You: A Microarchitectural Side Channel Attack
    on Real-World Applications of Curve25519
    by Daniel Genkin, Luke Valenta, and Yuval Yarom

In the current implementation, we do output checking and it results an
error for those bad points.  However, when attacked, the computation
will done with leak of private key, even it will results errors.  To
mitigate leak, we added input validation.

Note that we only list bad points with MSB=0.  By X25519, MSB is
always cleared.

In future, we should implement constant-time field computation.  Then,
this input validation could be removed, if performance is important
and we are sure for no leak.

CVE-id: CVE-2017-0379
Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
(cherry picked from commit bf76acbf0da6b0f245e491bec12c0f0a1b5be7c9)
---
 cipher/ecc.c | 17 +++++++++++++++--
 mpi/ec.c     | 51 ++++++++++++++++++++++++++++++++++++++++++++++++---
 src/mpi.h    |  1 +
 3 files changed, 64 insertions(+), 5 deletions(-)

diff --git a/cipher/ecc.c b/cipher/ecc.c
index e25bf095..4e3e5b1a 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -1628,9 +1628,22 @@ ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
   if (DBG_CIPHER)
     log_printpnt ("ecc_decrypt    kG", &kG, NULL);
 
-  if (!(flags & PUBKEY_FLAG_DJB_TWEAK)
+  if ((flags & PUBKEY_FLAG_DJB_TWEAK))
+    {
       /* For X25519, by its definition, validation should not be done.  */
-      && !_gcry_mpi_ec_curve_point (&kG, ec))
+      /* (Instead, we do output check.)
+       *
+       * However, to mitigate secret key leak from our implementation,
+       * we also do input validation here.  For constant-time
+       * implementation, we can remove this input validation.
+       */
+      if (_gcry_mpi_ec_bad_point (&kG, ec))
+        {
+          rc = GPG_ERR_INV_DATA;
+          goto leave;
+        }
+    }
+  else if (!_gcry_mpi_ec_curve_point (&kG, ec))
     {
       rc = GPG_ERR_INV_DATA;
       goto leave;
diff --git a/mpi/ec.c b/mpi/ec.c
index 3ac0547f..1469339c 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -382,6 +382,29 @@ ec_get_two_inv_p (mpi_ec_t ec)
 }
 
 
+static const char *curve25519_bad_points[] = {
+  "0x0000000000000000000000000000000000000000000000000000000000000000",
+  "0x0000000000000000000000000000000000000000000000000000000000000001",
+  "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0",
+  "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f",
+  "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec",
+  "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed",
+  "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee",
+  NULL
+};
+
+static gcry_mpi_t
+scanval (const char *string)
+{
+  gpg_err_code_t rc;
+  gcry_mpi_t val;
+
+  rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
+  if (rc)
+    log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
+  return val;
+}
+
 
 /* This function initialized a context for elliptic curve based on the
    field GF(p).  P is the prime specifying this field, A is the first
@@ -420,9 +443,17 @@ ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
 
   _gcry_mpi_ec_get_reset (ctx);
 
-  /* Allocate scratch variables.  */
-  for (i=0; i< DIM(ctx->t.scratch); i++)
-    ctx->t.scratch[i] = mpi_alloc_like (ctx->p);
+  if (model == MPI_EC_MONTGOMERY)
+    {
+      for (i=0; i< DIM(ctx->t.scratch) && curve25519_bad_points[i]; i++)
+        ctx->t.scratch[i] = scanval (curve25519_bad_points[i]);
+    }
+  else
+    {
+      /* Allocate scratch variables.  */
+      for (i=0; i< DIM(ctx->t.scratch); i++)
+        ctx->t.scratch[i] = mpi_alloc_like (ctx->p);
+    }
 
   /* Prepare for fast reduction.  */
   /* FIXME: need a test for NIST values.  However it does not gain us
@@ -1558,3 +1589,17 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
 
   return res;
 }
+
+
+int
+_gcry_mpi_ec_bad_point (gcry_mpi_point_t point, mpi_ec_t ctx)
+{
+  int i;
+  gcry_mpi_t x_bad;
+
+  for (i = 0; (x_bad = ctx->t.scratch[i]); i++)
+    if (!mpi_cmp (point->x, x_bad))
+      return 1;
+
+  return 0;
+}
diff --git a/src/mpi.h b/src/mpi.h
index cd539f5c..ea2a4cbe 100644
--- a/src/mpi.h
+++ b/src/mpi.h
@@ -296,6 +296,7 @@ void _gcry_mpi_ec_mul_point (mpi_point_t result,
                              gcry_mpi_t scalar, mpi_point_t point,
                              mpi_ec_t ctx);
 int  _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx);
+int _gcry_mpi_ec_bad_point (gcry_mpi_point_t point, mpi_ec_t ctx);
 
 gcry_mpi_t _gcry_mpi_ec_ec2os (gcry_mpi_point_t point, mpi_ec_t ectx);
 
-- 
2.14.1