From fcbb9fcc2e6983ea61bf565b6ee2e29816b8cd57 Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gniibe@fsij.org>
Date: Wed, 10 Feb 2016 17:43:03 +0900
Subject: [PATCH] ecc: Fix for chosen cipher text attacks.

* src/mpi.h (_gcry_mpi_ec_curve_point): New internal function.
* cipher/ecc.c (ecc_decrypt_raw): Validate input.  Remove duplicated
point_free.
* mpi/ec.c (_gcry_mpi_ec_mul_point):Use simple left-to-right binary
method for when SCALAR is secure.
(_gcry_mpi_ec_curve_point): New.

--

CVE-id: CVE-2015-7511

Thanks to Daniel Genkin, Lev Pachmanov, Itamar Pipman, and Eran
Tromer.   http://www.cs.tau.ac.IL/~tromer/ecdh/

This could be an effective contermeasure to some chosen cipher text
attacks.

(backport from master
 commit 88e1358962e902ff1cbec8d53ba3eee46407851a)
(backport from LIBGCRYPT-1-6-BRANCH
 commit 28eb424e4427b320ec1c9c4ce56af25d495230bd)

Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
---
 cipher/ecc.c |  11 ++-
 mpi/ec.c     | 226 +++++++++++++++++++++++++++++++++++------------------------
 src/mpi.h    |   2 +-
 3 files changed, 145 insertions(+), 94 deletions(-)

diff --git a/cipher/ecc.c b/cipher/ecc.c
index b8487dc..80b67ae 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -1535,12 +1535,19 @@ ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
 
   ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a);
 
+  if (!_gcry_mpi_ec_curve_point (&kG, sk.E.b, ctx))
+    {
+      point_free (&kG);
+      point_free (&sk.E.G);
+      point_free (&sk.Q);
+      _gcry_mpi_ec_free (ctx);
+      return GPG_ERR_INV_DATA;
+    }
+
   /* R = dkG */
   point_init (&R);
   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
 
-  point_free (&kG);
-
   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
   {
     gcry_mpi_t x, y;
diff --git a/mpi/ec.c b/mpi/ec.c
index fa00818..bdb155a 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -612,110 +612,154 @@ _gcry_mpi_ec_mul_point (mpi_point_t *result,
                         gcry_mpi_t scalar, mpi_point_t *point,
                         mpi_ec_t ctx)
 {
-#if 0
-  /* Simple left to right binary method.  GECC Algorithm 3.27 */
-  unsigned int nbits;
-  int i;
-
-  nbits = mpi_get_nbits (scalar);
-  mpi_set_ui (result->x, 1);
-  mpi_set_ui (result->y, 1);
-  mpi_set_ui (result->z, 0);
-
-  for (i=nbits-1; i >= 0; i--)
+  if (mpi_is_secure(scalar))
     {
-      _gcry_mpi_ec_dup_point (result, result, ctx);
-      if (mpi_test_bit (scalar, i) == 1)
-        _gcry_mpi_ec_add_points (result, result, point, ctx);
-    }
-
-#else
-  gcry_mpi_t x1, y1, z1, k, h, yy;
-  unsigned int i, loops;
-  mpi_point_t p1, p2, p1inv;
-
-  x1 = mpi_alloc_like (ctx->p);
-  y1 = mpi_alloc_like (ctx->p);
-  h  = mpi_alloc_like (ctx->p);
-  k  = mpi_copy (scalar);
-  yy = mpi_copy (point->y);
+      /* Simple left to right binary method.  GECC Algorithm 3.27 */
+      unsigned int nbits;
+      int i;
+      mpi_point_t tmppnt;
 
-  if ( mpi_is_neg (k) )
-    {
-      k->sign = 0;
-      ec_invm (yy, yy, ctx);
-    }
+      nbits = mpi_get_nbits (scalar);
+      mpi_set_ui (result->x, 1);
+      mpi_set_ui (result->y, 1);
+      mpi_set_ui (result->z, 0);
 
-  if (!mpi_cmp_ui (point->z, 1))
-    {
-      mpi_set (x1, point->x);
-      mpi_set (y1, yy);
+      point_init (&tmppnt);
+      for (i=nbits-1; i >= 0; i--)
+        {
+          _gcry_mpi_ec_dup_point (result, result, ctx);
+          _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
+          if (mpi_test_bit (scalar, i) == 1)
+            point_set (result, &tmppnt);
+        }
+      point_free (&tmppnt);
     }
   else
     {
-      gcry_mpi_t z2, z3;
-
-      z2 = mpi_alloc_like (ctx->p);
-      z3 = mpi_alloc_like (ctx->p);
-      ec_mulm (z2, point->z, point->z, ctx);
-      ec_mulm (z3, point->z, z2, ctx);
-      ec_invm (z2, z2, ctx);
-      ec_mulm (x1, point->x, z2, ctx);
-      ec_invm (z3, z3, ctx);
-      ec_mulm (y1, yy, z3, ctx);
-      mpi_free (z2);
-      mpi_free (z3);
-    }
-  z1 = mpi_copy (ctx->one);
+      gcry_mpi_t x1, y1, z1, k, h, yy;
+      unsigned int i, loops;
+      mpi_point_t p1, p2, p1inv;
 
-  mpi_mul (h, k, ctx->three); /* h = 3k */
-  loops = mpi_get_nbits (h);
-  if (loops < 2)
-    {
-      /* If SCALAR is zero, the above mpi_mul sets H to zero and thus
-         LOOPs will be zero.  To avoid an underflow of I in the main
-         loop we set LOOP to 2 and the result to (0,0,0).  */
-      loops = 2;
-      mpi_clear (result->x);
-      mpi_clear (result->y);
-      mpi_clear (result->z);
-    }
-  else
-    {
-      mpi_set (result->x, point->x);
-      mpi_set (result->y, yy);
-      mpi_set (result->z, point->z);
-    }
-  mpi_free (yy); yy = NULL;
+      x1 = mpi_alloc_like (ctx->p);
+      y1 = mpi_alloc_like (ctx->p);
+      h  = mpi_alloc_like (ctx->p);
+      k  = mpi_copy (scalar);
+      yy = mpi_copy (point->y);
 
-  p1.x = x1; x1 = NULL;
-  p1.y = y1; y1 = NULL;
-  p1.z = z1; z1 = NULL;
-  point_init (&p2);
-  point_init (&p1inv);
+      if ( mpi_is_neg (k) )
+        {
+          k->sign = 0;
+          ec_invm (yy, yy, ctx);
+        }
 
-  for (i=loops-2; i > 0; i--)
-    {
-      _gcry_mpi_ec_dup_point (result, result, ctx);
-      if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
+      if (!mpi_cmp_ui (point->z, 1))
+        {
+          mpi_set (x1, point->x);
+          mpi_set (y1, yy);
+        }
+      else
         {
-          point_set (&p2, result);
-          _gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
+          gcry_mpi_t z2, z3;
+
+          z2 = mpi_alloc_like (ctx->p);
+          z3 = mpi_alloc_like (ctx->p);
+          ec_mulm (z2, point->z, point->z, ctx);
+          ec_mulm (z3, point->z, z2, ctx);
+          ec_invm (z2, z2, ctx);
+          ec_mulm (x1, point->x, z2, ctx);
+          ec_invm (z3, z3, ctx);
+          ec_mulm (y1, yy, z3, ctx);
+          mpi_free (z2);
+          mpi_free (z3);
         }
-      if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
+      z1 = mpi_copy (ctx->one);
+
+      mpi_mul (h, k, ctx->three); /* h = 3k */
+      loops = mpi_get_nbits (h);
+      if (loops < 2)
         {
-          point_set (&p2, result);
-          /* Invert point: y = p - y mod p  */
-          point_set (&p1inv, &p1);
-          ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
-          _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
+          /* If SCALAR is zero, the above mpi_mul sets H to zero and thus
+             LOOPs will be zero.  To avoid an underflow of I in the main
+             loop we set LOOP to 2 and the result to (0,0,0).  */
+          loops = 2;
+          mpi_clear (result->x);
+          mpi_clear (result->y);
+          mpi_clear (result->z);
+        }
+      else
+        {
+          mpi_set (result->x, point->x);
+          mpi_set (result->y, yy);
+          mpi_set (result->z, point->z);
+        }
+      mpi_free (yy); yy = NULL;
+
+      p1.x = x1; x1 = NULL;
+      p1.y = y1; y1 = NULL;
+      p1.z = z1; z1 = NULL;
+      point_init (&p2);
+      point_init (&p1inv);
+
+      for (i=loops-2; i > 0; i--)
+        {
+          _gcry_mpi_ec_dup_point (result, result, ctx);
+          if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
+            {
+              point_set (&p2, result);
+              _gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
+            }
+          if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
+            {
+              point_set (&p2, result);
+              /* Invert point: y = p - y mod p  */
+              point_set (&p1inv, &p1);
+              ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
+              _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
+            }
         }
+
+      point_free (&p1);
+      point_free (&p2);
+      point_free (&p1inv);
+      mpi_free (h);
+      mpi_free (k);
     }
+}
+
+
+/* Return true if POINT is on the curve described by CTX.  */
+int
+_gcry_mpi_ec_curve_point (mpi_point_t *point, gcry_mpi_t b, mpi_ec_t ctx)
+{
+  int res = 0;
+  gcry_mpi_t x, y, w;
+  gcry_mpi_t xxx;
+
+  x = mpi_new (0);
+  y = mpi_new (0);
+  w = mpi_new (0);
+  xxx = mpi_new (0);
+
+  if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
+    goto leave;
+
+  /* y^2 == x^3 + a·x + b */
+  ec_mulm (y, y, y, ctx);
+
+  ec_mulm (xxx, x, x, ctx);
+  ec_mulm (xxx, xxx, x, ctx);
+  ec_mulm (w, ctx->a, x, ctx);
+  ec_addm (w, w, b, ctx);
+  ec_addm (w, w, xxx, ctx);
+
+  if (!mpi_cmp (y, w))
+    res = 1;
+
+ leave:
+  _gcry_mpi_release (xxx);
+  _gcry_mpi_release (w);
+  _gcry_mpi_release (x);
+  _gcry_mpi_release (y);
 
-  point_free (&p1);
-  point_free (&p2);
-  point_free (&p1inv);
-  mpi_free (h);
-  mpi_free (k);
-#endif
+  return res;
 }
diff --git a/src/mpi.h b/src/mpi.h
index 65a4f97..adc65e2 100644
--- a/src/mpi.h
+++ b/src/mpi.h
@@ -257,7 +257,7 @@ void _gcry_mpi_ec_add_points (mpi_point_t *result,
 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 (mpi_point_t *point, gcry_mpi_t b, mpi_ec_t ctx);
 
 
 #endif /*G10_MPI_H*/
-- 
2.1.4