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
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
