[PATCH] mpi_swap_conditional

[NIIBE Yutaka]

On 2014-06-19 at 14:08 -0400, Ian Goldberg wrote:
> So the values of a and b are public, but only the value of SW is
> private?  Isn't that a pretty unusual case?  The timing of the code
> below definitely depends on the values (in particular the relative
> sizes) of a and b, so if a and b are non-public, this is not a
> constant-time routine, right?

I'm sorry that my code was too bad and caused confusion.  Here is
today's version.

==============================================
void
_gcry_mpi_swap_conditional (gcry_mpi_t a, gcry_mpi_t b, unsigned long swap)
{
  size_t i;
  size_t nlimbs = a->alloced;
  unsigned long mask = 0UL - !!swap;
  unsigned long x;

  if (a->alloced != b->alloced)
    log_bug ("mpi_swap_conditional: different sizes\n");

  for (i = 0; i < nlimbs; i++)
    {
      x = mask & (a->d[i] ^ b->d[i]);
      a->d[i] = a->d[i] ^ x;
      b->d[i] = b->d[i] ^ x;
    }

  x = mask & (a->nlimbs ^ b->nlimbs);
  a->nlimbs = a->nlimbs ^ x;
  b->nlimbs = b->nlimbs ^ x;

  x = mask & (a->sign ^ b->sign);
  a->sign = a->sign ^ x;
  b->sign = b->sign ^ x;
}
==============================================

Now, it is caller's responsibility to keep same sizes of A and B.

The calculation is as same as:

  if (swap)
    _gcry_mpi_swap (a, b);

But _gcry_mpi_swap_conditional does swapping at lower level, to enable
same cache usage pattern of caller and the intention of the
implementation is constant-time (not to depend SWAP).

The intended usage is allocating MPI at the beginning, and use
mpi_swap_conditional in the loop of crypto computation, where SWAP
is private.

Since I think that there is no guarantee that we can keep using same
place of MPI memory, it would be possible log_bug will be called,
I'm afraid.

Please see my next post for actual usage.
--