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);