diff options
author | NIIBE Yutaka <gniibe@fsij.org> | 2016-02-10 17:43:03 +0900 |
---|---|---|
committer | NIIBE Yutaka <gniibe@fsij.org> | 2016-02-10 17:43:03 +0900 |
commit | fcbb9fcc2e6983ea61bf565b6ee2e29816b8cd57 (patch) | |
tree | 10b0fef6a834996a53f12b7084a620ecb6bbc6a7 | |
parent | 35cd81f134c0da4e7e6fcfe40d270ee1251f52c2 (diff) | |
download | libgcrypt-fcbb9fcc2e6983ea61bf565b6ee2e29816b8cd57.tar.gz |
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>
-rw-r--r-- | cipher/ecc.c | 11 | ||||
-rw-r--r-- | mpi/ec.c | 226 | ||||
-rw-r--r-- | src/mpi.h | 2 |
3 files changed, 145 insertions, 94 deletions
diff --git a/cipher/ecc.c b/cipher/ecc.c index b8487dc1..80b67ae3 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; @@ -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; } @@ -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*/ |