Side-channel leakage in the mpz_powm_sec interface

[Torbjörn Granlund]

marco.bodrato at tutanota.com writes:

  This sounds not too complex to do. Even if, as usual, C code is prone to compiler optimizations...
  I think this is a good idea.

The concern for compilers messing up secure code is very valid.  An
example is that clang makes our mpn_sec_tabselect useless by inserting a
conditional branch instead of our mask; the generated code actually
adheres to the volatile declaration, but is utterly useless for its
intended purpose.

It is a pity that we cannot write certain sensitive code in C.  A C
language extension would be welcome, perhaps some kind of "strict
volatile", or an annotated conditional requiring that no branch or other
conditional execution is generated as a result of it.

A side note: CPU conditional move and conditional select instructions
are usually poorly defined.  Is there a true dependency on all inputs,
or only on the actually chosen input?  I've used my contacts at CPU
manufacturers to address this concern, but never seen any real interest.

Back to the main subject:

We should probably exclude certain sec_ functions when not all sensitive
functions are provided in asm, and thereby as a result of
--disable-assembly?  We should in essence not provide C versions of
e.g., mpn_sec_tabselect.

And we should perhaps provide a normalisation asm function for what
Niels proposes here?

I think we should document mpz_powm_sec as somewhat problematic, but
also fix it along the lines of Niels' proposal.  The right GMP level for
side-channel sensitive application is clearly mpn; we should say that.

We might want to be more cautions about what we promise also for mpn.
It is not necessarily sufficient to do what we do here, i.e. perform the
exact same instruction sequence an data reference sequence for any two
n-bit operand sets.  Careful power measurements typically can
fingerprint either or both operands of a bignum multiply.  Therefore,
additional layers of side-channel obfuscation is needed, like standard
RSA message blinding, mod argument blinding, exponent blinding.

-- 
Torbjörn
Please encrypt, key id 0xC8601622