multiple timing side channels

[NIIBE Yutaka]

On 11/08/2015 07:08 AM, Taylor R Campbell wrote:
> This morning I had occasion to glance at the libgcrypt source code,
> and to my unpleasant surprise I found a collection of independent,
> obvious timing side channels in the code:

Thank you for your review and suggestions.  While I share your view,
it's not that easy to fix all at once.  I'd like to fix one by one,
with my capability.  I understand your suggestions, but it is not
clear for me how to achieve that.  When I implement Curve25519, I did
my best on top of existing code.

Let me fix where I can.


> - In twisted Edwards scalar multiplication, _gcry_mpi_ec_mul_point
> branches depending on whether a bit in a secret scalar is set:
> 
> (mpi/ec.c, _gcry_mpi_ec_mul_point)
>   1232                _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
>   1233                if (mpi_test_bit (scalar, j))
>   1234                  point_set (result, &tmppnt);
> 
> Presumably this is intended to run in constant time, because the
> scalar is a secret -- there's even a comment above saying `we use
> constant time operation' in that case.  But secret-dependent branches
> are not that.  (Easy fix: add point_swap_cond like point_set, using
> mpi_cond_swap, and use it here.)

Yes.  I'll fix that.

> - In conditional mpi swapping, _gcry_mpi_cond_swap branches depending
> on the swap condition:
> 
> (mpi/mpiutil.c, _gcry_mpi_cond_swap)
>    576    mpi_limb_t mask = ((mpi_limb_t)0) - !!swap;
> 
> Some compilers may not turn this into a branch -- but some do.
> Presumably this is intended to run in constant time because it is used
> in code that operates on secrets, so I suggest it be documented as
> such.  (Easy fix: saturate instead of !!, e.g. iterate swap |= (swap
> << (1<<i)) | (swap >> (1<<i)) for i in 0..6.)

I understand your point.  It is possible for compilers to turn this
into a branch, that's true, but I haven't had any experience for
existing compilers for libgcrypt (for supported architectures), so
far.  Let me consider.  It would be also good considering its API
itself.

> - In mpi bit testing, _gcry_mpi_test_bit branches depending on the
> value of the limb:
> 
> (mpi/mpi-bit.c, _gcry_mpi_test_bit)
>    109      return (limb & (A_LIMB_1 << bitno))? 1: 0;
> 
> Again, some compilers may use a constant-time conditional move here --
> but some will use a branch.  (Easy fix: return 1 & (limb >> bitno).)

I understand your point.  While good compilers turns the expression to
the one you suggest, I'm afraid it could not be constant time on some
architecture which doesn't have barrel shifter in lower level.  Let me
consider.

> - ~All general-purpose modular reduction involves numerator- and
> denominator-dependent branches, e.g.:
> 
> (mpi/mpih-div.c, _gcry_mpih_divrem)
>    319              if( n0 >= dX ) {
> 
> Here n0 and dX are limbs of the numerator and the denominator.  This
> includes modular reduction for elliptic curve arithmetic, in which the
> numerator is secret; and modular reduction for RSA, in which the
> numerator (plaintext message) or denominator (p, q) can be secret.
> 
> - Many arithmetic routines normalize their inputs and outputs, so that
> secrets flow into nlimbs and thence into loop counts and memory
> reference patterns.

Yes.  I understand.


For now, here is a patch to address the first issue.  Built and
tested.

diff --git a/mpi/ec.c b/mpi/ec.c
index 7266f2a..671cf78 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -138,6 +138,22 @@ point_set (mpi_point_t d, mpi_point_t s)
   mpi_set (d->z, s->z);
 }

+static void
+point_resize (mpi_point_t p, size_t nlimbs)
+{
+  mpi_resize (p->x, nlimbs);
+  mpi_resize (p->y, nlimbs);
+  mpi_resize (p->z, nlimbs);
+}
+
+static void
+point_swap_cond (mpi_point_t d, mpi_point_t s, unsigned long swap)
+{
+  mpi_swap_cond (d->x, s->x, swap);
+  mpi_swap_cond (d->y, s->y, swap);
+  mpi_swap_cond (d->z, s->z, swap);
+}
+

 /* Set the projective coordinates from POINT into X, Y, and Z.  If a
    coordinate is not required, X, Y, or Z may be passed as NULL.  */
@@ -1224,14 +1240,16 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
           /* If SCALAR is in secure memory we assume that it is the
              secret key we use constant time operation.  */
           mpi_point_struct tmppnt;
+          size_t nlimbs = 2*(nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB+1;

           point_init (&tmppnt);
+          point_resize (result, nlimbs);
+          point_resize (&tmppnt, nlimbs);
           for (j=nbits-1; j >= 0; j--)
             {
               _gcry_mpi_ec_dup_point (result, result, ctx);
               _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
-              if (mpi_test_bit (scalar, j))
-                point_set (result, &tmppnt);
+              point_swap_cond (result, &tmppnt, mpi_test_bit (scalar, j));
             }
           point_free (&tmppnt);
         }
--