multiple timing side channels

[Jussi Kivilinna]

On 10.11.2015 19:49, Taylor R Campbell wrote:
>    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.)
> 

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

 xor    %r10d,%r10d
 test   %rdx,%rdx
 setne  %r10b
 neg    %r10

-Jussi