mpn_sec_div_r

[Niels Möller]

Hi,

I'm trying to use mpn_sec_div_r. To verify the code indeed is
sidechannel silent, I have tests wrapping calls with 

#define MARK_MPZ_LIMBS_UNDEFINED(parm) \
  VALGRIND_MAKE_MEM_UNDEFINED (mpz_limbs_read (parm), \
                               mpz_size (parm) * sizeof (mp_limb_t))

on the sensitive inputs, and run it under valgrind. (Which is a useful
trick because the operations valgrind dislikes on uninitialized data are
the same operation that could leak information via cache and timing). It
fails like this:

==28982== Conditional jump or move depends on uninitialised value(s)
==28982==    at 0x493A982: __gmpn_sec_div_r (in /usr/lib/x86_64-linux-gnu/libgmp.so.10.3.2)

==28982== Use of uninitialised value of size 8
==28982==    at 0x493C07E: __gmpn_invert_limb (in /usr/lib/x86_64-linux-gnu/libgmp.so.10.3.2)
==28982==    by 0x493AA20: __gmpn_sec_div_r (in /usr/lib/x86_64-linux-gnu/libgmp.so.10.3.2)

I think it's all about the high end of the divisor. In
mpn/generic/sec_div.c, we have

  d1 = dp[dn - 1];
  count_leading_zeros (cnt, d1);

  if (cnt != 0)

which is a branch depending of the most significant bit of d.

And we also call invert_limb, where implementations typically start with
a table lookup on the most significant bits, e.g, x86_64/invert_limb.asm

	mov	%rdi, %rax
	shr	$55, %rax
ifdef(`PIC',`
ifdef(`DARWIN',`
	mov	mpn_invert_limb_table at GOTPCREL(%rip), %r8
	add	$-512, %r8
',`
	lea	-512+mpn_invert_limb_table(%rip), %r8
')',`
	movabs	$-512+mpn_invert_limb_table, %r8
')
	movzwl	(%r8,%rax,2), R32(%rcx)	C	%rcx = v0

Not sure what to do about it, but it would be desirable if mpn_sec_div*
functions couldn't leak any of the input bits.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.