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
diff --git a/bignum.h b/bignum.h
index 24158e0..64ed278 100644
--- a/bignum.h
+++ b/bignum.h
@@ -53,6 +53,8 @@
# define mpz_combit mpz_combit
# define mpz_import mpz_import
# define mpz_export mpz_export
+/* Side-channel silent powm not available in mini-gmp. */
+# define mpz_powm_sec mpz_pwm
#else
# include <gmp.h>
#endif
diff --git a/configure.ac b/configure.ac
index e1ee64c..92a3605 100644
--- a/configure.ac
+++ b/configure.ac
@@ -236,9 +236,9 @@ fi
# Checks for libraries
if test "x$enable_public_key" = "xyes" ; then
if test "x$enable_mini_gmp" = "xno" ; then
- AC_CHECK_LIB(gmp, __gmpz_getlimbn,,
+ AC_CHECK_LIB(gmp, __gmpz_mpz_powm,,
[AC_MSG_WARN(
- [GNU MP not found, or not 3.1 or up, see http://gmplib.org/.
+ [GNU MP not found, or too old. GMP-5.0 or later is needed, see http://gmplib.org/.
Support for public key algorithms will be unavailable.])]
enable_public_key=no)
diff --git a/dsa-sign.c b/dsa-sign.c
index 62c7d4a..9d6bb18 100644
--- a/dsa-sign.c
+++ b/dsa-sign.c
@@ -65,7 +65,7 @@ dsa_sign(const struct dsa_params *params,
mpz_add_ui(k, k, 1);
/* Compute r = (g^k (mod p)) (mod q) */
- mpz_powm(tmp, params->g, k, params->p);
+ mpz_powm_sec(tmp, params->g, k, params->p);
mpz_fdiv_r(signature->r, tmp, params->q);
/* Compute hash */
diff --git a/rsa-blind.c b/rsa-blind.c
index 7662f50..16b03d7 100644
--- a/rsa-blind.c
+++ b/rsa-blind.c
@@ -61,7 +61,7 @@ _rsa_blind (const struct rsa_public_key *pub,
while (!mpz_invert (ri, r, pub->n));
/* c = c*(r^e) mod n */
- mpz_powm(r, r, pub->e, pub->n);
+ mpz_powm_sec(r, r, pub->e, pub->n);
mpz_mul(c, c, r);
mpz_fdiv_r(c, c, pub->n);
diff --git a/rsa-sign-tr.c b/rsa-sign-tr.c
index 3d80ed4..68233a3 100644
--- a/rsa-sign-tr.c
+++ b/rsa-sign-tr.c
@@ -60,7 +60,7 @@ rsa_blind (const struct rsa_public_key *pub,
while (!mpz_invert (ri, r, pub->n));
/* c = c*(r^e) mod n */
- mpz_powm(r, r, pub->e, pub->n);
+ mpz_powm_sec(r, r, pub->e, pub->n);
mpz_mul(c, m, r);
mpz_fdiv_r(c, c, pub->n);
@@ -97,7 +97,7 @@ rsa_compute_root_tr(const struct rsa_public_key *pub,
rsa_compute_root (key, xb, mb);
- mpz_powm(t, xb, pub->e, pub->n);
+ mpz_powm_sec(t, xb, pub->e, pub->n);
res = (mpz_cmp(mb, t) == 0);
if (res)
diff --git a/rsa-sign.c b/rsa-sign.c
index eba7388..4832352 100644
--- a/rsa-sign.c
+++ b/rsa-sign.c
@@ -96,11 +96,11 @@ rsa_compute_root(const struct rsa_private_key *key,
/* Compute xq = m^d % q = (m%q)^b % q */
mpz_fdiv_r(xq, m, key->q);
- mpz_powm(xq, xq, key->b, key->q);
+ mpz_powm_sec(xq, xq, key->b, key->q);
/* Compute xp = m^d % p = (m%p)^a % p */
mpz_fdiv_r(xp, m, key->p);
- mpz_powm(xp, xp, key->a, key->p);
+ mpz_powm_sec(xp, xp, key->a, key->p);
/* Set xp' = (xp - xq) c % p. */
mpz_sub(xp, xp, xq);
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
