Description: fix sidechannel attack via timing variations in mpi_powm Origin: backport, http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commit;h=deb6f231ba85f65283c9e1deb3e2dea3b6ca46dc Origin: backport, http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commit;h=d9f002899d26dc64f1502ae5050632340a4780fe Origin: backport, http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commit;h=5e72b6c76ebee720f69b8a5c212f52d38eb50287 Index: libgcrypt11-1.5.4/mpi/mpi-pow.c =================================================================== --- libgcrypt11-1.5.4.orig/mpi/mpi-pow.c 2015-03-26 08:14:32.728379999 -0400 +++ libgcrypt11-1.5.4/mpi/mpi-pow.c 2015-03-26 08:14:32.720379940 -0400 @@ -381,7 +381,7 @@ *xsize_p = rsize + ssize; } -#define SIZE_B_2I3 ((1 << (5 - 1)) - 1) +#define SIZE_PRECOMP ((1 << (5 - 1))) /**************** * RES = BASE ^ EXPO mod MOD @@ -417,11 +417,12 @@ unsigned int bp_nlimbs = 0; unsigned int ep_nlimbs = 0; unsigned int xp_nlimbs = 0; - mpi_ptr_t b_2i3[SIZE_B_2I3]; /* Pre-computed array: BASE^3, ^5, ^7, ... */ - mpi_size_t b_2i3size[SIZE_B_2I3]; + mpi_ptr_t precomp[SIZE_PRECOMP]; /* Pre-computed array: BASE^1, ^3, ^5, ... */ + mpi_size_t precomp_size[SIZE_PRECOMP]; mpi_size_t W; mpi_ptr_t base_u; mpi_size_t base_u_size; + mpi_size_t max_u_size; esize = expo->nlimbs; msize = mod->nlimbs; @@ -540,7 +541,7 @@ /* Main processing. */ { - mpi_size_t i, j; + mpi_size_t i, j, k; mpi_ptr_t xp; mpi_size_t xsize; int c; @@ -555,33 +556,30 @@ memset( &karactx, 0, sizeof karactx ); negative_result = (ep[0] & 1) && bsign; - /* Precompute B_2I3[], BASE^(2 * i + 3), BASE^3, ^5, ^7, ... */ + /* Precompute PRECOMP[], BASE^(2 * i + 1), BASE^1, ^3, ^5, ... */ if (W > 1) /* X := BASE^2 */ mul_mod (xp, &xsize, bp, bsize, bp, bsize, mp, msize, &karactx); - for (i = 0; i < (1 << (W - 1)) - 1; i++) - { /* B_2I3[i] = BASE^(2 * i + 3) */ - if (i == 0) - { - base_u = bp; - base_u_size = bsize; - } - else - { - base_u = b_2i3[i-1]; - base_u_size = b_2i3size[i-1]; - } - + base_u = precomp[0] = mpi_alloc_limb_space (bsize, esec); + base_u_size = max_u_size = precomp_size[0] = bsize; + MPN_COPY (precomp[0], bp, bsize); + for (i = 1; i < (1 << (W - 1)); i++) + { /* PRECOMP[i] = BASE^(2 * i + 1) */ if (xsize >= base_u_size) mul_mod (rp, &rsize, xp, xsize, base_u, base_u_size, mp, msize, &karactx); else mul_mod (rp, &rsize, base_u, base_u_size, xp, xsize, mp, msize, &karactx); - b_2i3[i] = mpi_alloc_limb_space (rsize, esec); - b_2i3size[i] = rsize; - MPN_COPY (b_2i3[i], rp, rsize); + base_u = precomp[i] = mpi_alloc_limb_space (rsize, esec); + base_u_size = precomp_size[i] = rsize; + if (max_u_size < base_u_size) + max_u_size = base_u_size; + MPN_COPY (precomp[i], rp, rsize); } + base_u = mpi_alloc_limb_space (max_u_size, esec); + MPN_ZERO (base_u, max_u_size); + i = esize - 1; /* Main loop. @@ -667,15 +665,23 @@ rsize = xsize; } - if (e0 == 0) + /* + * base_u <= precomp[e0] + * base_u_size <= precomp_size[e0] + */ + base_u_size = 0; + for (k = 0; k < (1<< (W - 1)); k++) { - base_u = bp; - base_u_size = bsize; - } - else - { - base_u = b_2i3[e0 - 1]; - base_u_size = b_2i3size[e0 -1]; + struct gcry_mpi w, u; + w.alloced = w.nlimbs = precomp_size[k]; + u.alloced = u.nlimbs = precomp_size[k]; + w.sign = u.sign = 0; + w.flags = u.flags = 0; + w.d = base_u; + u.d = precomp[k]; + + mpi_set_cond (&w, &u, k == e0); + base_u_size |= (precomp_size[k] & ((mpi_size_t)0 - (k == e0)) ); } mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size, @@ -703,15 +709,23 @@ if (e != 0) { - if ((e>>1) == 0) + /* + * base_u <= precomp[(e>>1)] + * base_u_size <= precomp_size[(e>>1)] + */ + base_u_size = 0; + for (k = 0; k < (1<< (W - 1)); k++) { - base_u = bp; - base_u_size = bsize; - } - else - { - base_u = b_2i3[(e>>1) - 1]; - base_u_size = b_2i3size[(e>>1) -1]; + struct gcry_mpi w, u; + w.alloced = w.nlimbs = precomp_size[k]; + u.alloced = u.nlimbs = precomp_size[k]; + w.sign = u.sign = 0; + w.flags = u.flags = 0; + w.d = base_u; + u.d = precomp[k]; + + mpi_set_cond (&w, &u, k == (e>>1)); + base_u_size |= (precomp_size[k] & ((mpi_size_t)0 - (k == (e>>1))) ); } mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size, @@ -761,8 +775,9 @@ MPN_NORMALIZE (rp, rsize); _gcry_mpih_release_karatsuba_ctx (&karactx ); - for (i = 0; i < (1 << (W - 1)) - 1; i++) - _gcry_mpi_free_limb_space( b_2i3[i], esec ? b_2i3size[i] : 0 ); + for (i = 0; i < (1 << (W - 1)); i++) + _gcry_mpi_free_limb_space( precomp[i], esec ? precomp_size[i] : 0 ); + _gcry_mpi_free_limb_space (base_u, esec ? max_u_size : 0); } /* Fixup for negative results. */ Index: libgcrypt11-1.5.4/mpi/mpiutil.c =================================================================== --- libgcrypt11-1.5.4.orig/mpi/mpiutil.c 2015-03-26 08:14:32.728379999 -0400 +++ libgcrypt11-1.5.4/mpi/mpiutil.c 2015-03-26 08:14:32.720379940 -0400 @@ -386,6 +386,31 @@ / BITS_PER_MPI_LIMB ); } +gcry_mpi_t +_gcry_mpi_set_cond (gcry_mpi_t w, const gcry_mpi_t u, unsigned long set) +{ + mpi_size_t i; + mpi_size_t nlimbs = u->alloced; + mpi_limb_t mask = ((mpi_limb_t)0) - !!set; + mpi_limb_t x; + + if (w->alloced != u->alloced) + log_bug ("mpi_set_cond: different sizes\n"); + + for (i = 0; i < nlimbs; i++) + { + x = mask & (w->d[i] ^ u->d[i]); + w->d[i] = w->d[i] ^ x; + } + + x = mask & (w->nlimbs ^ u->nlimbs); + w->nlimbs = w->nlimbs ^ x; + + x = mask & (w->sign ^ u->sign); + w->sign = w->sign ^ x; + return w; +} + gcry_mpi_t gcry_mpi_snew( unsigned int nbits ) Index: libgcrypt11-1.5.4/src/mpi.h =================================================================== --- libgcrypt11-1.5.4.orig/src/mpi.h 2015-03-26 08:14:32.728379999 -0400 +++ libgcrypt11-1.5.4/src/mpi.h 2015-03-26 08:15:07.112640773 -0400 @@ -116,8 +116,11 @@ #define mpi_swap(a,b) _gcry_mpi_swap ((a),(b)) #define mpi_new(n) _gcry_mpi_new ((n)) #define mpi_snew(n) _gcry_mpi_snew ((n)) +#define mpi_set_cond(w,u,set) _gcry_mpi_set_cond ((w),(u),(set)) void _gcry_mpi_clear( gcry_mpi_t a ); +gcry_mpi_t _gcry_mpi_set_cond (gcry_mpi_t w, const gcry_mpi_t u, + unsigned long swap); gcry_mpi_t _gcry_mpi_alloc_like( gcry_mpi_t a ); gcry_mpi_t _gcry_mpi_alloc_set_ui( unsigned long u); gcry_err_code_t _gcry_mpi_get_ui (gcry_mpi_t w, ulong *u);