multiple timing side channels

[Taylor R Campbell]

   Date: Tue, 10 Nov 2015 17:00:37 +0900
   From: NIIBE Yutaka <gniibe at fsij.org>

   On 11/08/2015 07:08 AM, Taylor R Campbell wrote:
   > - 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.

It's certainly worth naming, with cheaper CPU-specific versions.  The
last time I ran into this, I wrote down that `it's not hard to find
CPU/compiler combinations with branches for ``!res'' ' -- but I
foolishly neglected to write down which combinations.

Another possibly cheaper generic option, with fewer shifts, is:

for (i = 1; i < CHAR_BIT*sizeof(swap); i <<= 1)
        swap |= swap >> i;
swap = ~((swap & 1) - 1);

(It is, of course, theoretically possible for a compiler would
translate even this into a conditional branch -- but I've never heard
of a compiler doing that, and that would be rather surprising to many
people.)

   > - 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.

In this case, bitno is not (or should not be) secret, so it's OK for
the time of the shift to vary depending on bitno.  What's not OK is
when the time of an operation varies depending on the value of limb --
that's secret.  The problem here is not the shift, but using the
secret (limb) in the condition part of a ?: expression.

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

Great, thanks!  That looks better.

Some other parts of _gcry_mpi_ec_mul_point look likely to be
problematic:

- `if (p1.z->nlimbs == 0) ...'  I don't see how this could be true --
  but if it can be, that's probably secret-dependent and thus leads to
  a timing leak.
- `if ( mpi_has_sign (k) )'  Even allowing for negative scalars seems
  to me likely to be a mistake.
- The rest of the routine, after branches for the twisted Edwards and
  Montgomery cases, I assume handles Weierstrass coordinates, for
  which timing side channels are not surprising -- but I started to
  list them before I realized it was for Weierstrass coordinates,
  since nothing in the routine says so.