Side-channel leakage in the mpz_powm_sec interface

[Niels Möller]

Torbjörn Granlund <tg at gmplib.org> writes:

> 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.

I would suggest testing of side channel silence. That's reasonably easy
to do on platforms supported by valgrind. We probably don't want to make
valgrind a hard requirement for make check, but we could recommend it.

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

It's not quite clear to me how that is useful. It could make
mpz_powm_sec silent with respect to leading zero bits in the output, but
as soon as anything uses the resulting size field for accessing the
limbs, we'll leak the resulting size anyway.

> 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.

Agreed.

> 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.

If docs don't already say explicitly what kind of side channels we try
to silence, that should be made more clear. My understanding is that by
ensuring that same instruction sequence and same memory accesses, we
should silence leaks via timing and cache, but not leaks via any other
kind of data dependency in the hardware.

> 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.

I know you've done more work on that recently, while I have no idea how
"mod argument blinding" works... To me physical side channels, like
consumed power in a circuit, seem too dependent both on hardware details
and on the kind of access the attacker can gain to the system. And
rather difficult to devise general and portable countermeasures. That
said, if GMP can provide advice and/or tools to do it, that's nice of
course.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.