Using mpz_powm_sec

Niels Möller nisse at
Mon Jun 20 07:30:47 CEST 2016

I'm considering the below patch, making use of the side-channel silent
mpz_powm_sec function. The idea is to make the RSA and DSA code less
vulnerable to side-channel attacks.

Exponentiation routines typically build a small table of powers at run
time, and then look up exponent bits in the table, a few bits at the
time. This table lookup may leak information about the exponent bits
(which in the case of RSA and DSA are secret) to an attacker running
other processes on the same physical machine.

mpz_powm_sec uses a slower table-lookup function, which for each lookup
does a sequential read of the entire table. Some caveats:

* The CRT code used for RSA signing uses other functions which may leak,
  in particular division functions with branches depending on secret

* Since we still use the mpz interface rather than the mpn interface in
  gmp, the exponents use a normalized size field (so top limb is
  non-zero). This might still leak information about the top exponent

* The patch drops support for GMP versions older than GMP-5.0, relased
  in 2010. 

* Mini-gmp builds don't try to be side-channel silent, they will use
  a #define mpz_powm_sec mpz_powm.

* I haven't yet had time to do proper benchmarks. Signing should get a
  bit slower, but I don't know how much.

Despite not plugging *all* potential leaks in the RSA code, I think the
simple change to use use mpz_powm_sec should make attacks using the
cache side-channel considerably more difficult.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: powm_sec.patch
Type: text/x-diff
Size: 2835 bytes
Desc: not available
URL: <>
-------------- next part --------------

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

More information about the nettle-bugs mailing list