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 data.
* 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 bits.
* 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.
Regards, /Niels