multiple timing side channels

[NIIBE Yutaka]

On 11/11/2015 05:09 AM, Jussi Kivilinna wrote:
> Another is to do '!!' by bit-wise ORing number and its negative and
> extracting sign-bit, which will be set only if number was non-zero:
> 
>  /* Convert non-zero values to '1' and zero to '0'. */
> 
>  static inline int is_not_zero(unsigned long val)
>  {
>    val |= -val; /* sign-bit will be set if 'val != 0' */
>    return (val >> (CHAR_BIT * sizeof(val) - 1)) & 1;
>  }
> 
>  ...
> 
>  mpi_limb_t mask = ((mpi_limb_t)0) - is_not_zero(swap);
> 
> With above GCC/x86-64 generates four instructions (in: swap = rdx,
> out: mask = rdx):
> 
>  mov    %rdx,%rax
>  neg    %rax
>  or     %rax,%rdx
>  sar    $0x3f,%rdx
> 
> Which is same amount as with original '!!swap' (in: swap = rdx,
> out: mask = r10):

Thank you for discussions.  I'll be back to this issue.

Before this fine-grained timing issue, I have to handle following, as
we have attacks now (as you had already imagined).  Please don't get
me wrong when you see another fixes before this paticular fix.  I
never ignore your point.

Well, I am considering how to fix libgcrypt ECC to be constant-time.

> 2. Eliminate mpi normalization.  Most k-bit multiprecision integers
> that libgcrypt handles are uniformly distributed in [0, 2^k), or at
> least in [0, p) where 2^(k - 1) <= p <= 2^k.  It's hard to imagine
> that there's much value in saving a handful of integer operations on
> the last limb once in every ~2^32 cases for an mpi operation -- but
> this frequency is high enough that it's not hard to imagine devising a
> timing attack where you learn something after a billion messages.

Yes.  When I did the implementation for Montgomery curve computation,
I also think that MPI normalization should be done at highest layer
only, and we should avoid the normalization in the middle of
computation.  Chosen cipher text attack would be surly possible.

I'm going to fix functions in mpi/ec.c (ec_mod, ec_addm, ec_subm,
ec_mulm, ec_mul2, and possibly ec_powm), so that those will use fixed
number of limbs.  Perhaps, we need another implementation of mpi_invm
which is constant-time.

> 3. Eliminate mpi altogether for arithmetic in fixed finite fields,
> such as GF(2^255 - 19) as used in Curve25519.  There's plenty of
> easy-to-use, high-quality, high-performance, constant-time code to
> compute it -- faster and more safely than the generic mpi code.

I basically agree this view, and I do something like this for my own
project (Gnuk).

For the maintenance and development of libgcrypt itself, it's not that
easy though, since we need to maintain API for existing applications.

> 4. Eliminate the generic elliptic-curve abstraction, especially for
> new curves.  For modern curve design, it offers no benefits over
> curve-specific code, and makes variable-time code much more tempting.
> Applications don't care that there are elliptic curves or points on
> them involved -- applications deal in opaque octet strings.

While I agree, this would require major API changes, I'm afraid of.

I'm going to fix major timing difference of ec_* functions, small
timing difference issues like point_set_cond, and micro timing
difference issues like use of !!.
--