From b6aae8b2364f24edc13c6cdf774bb8c8d282e02f Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 28 Sep 2016 12:01:26 +0100 Subject: [PATCH] dh.c, rsa.c: use `mpz_powm_sec' for modexps. This makes an effort to run in constant time. It's not perfect, but it's a lot better than nothing. * It uses fixed windows from the exponent rather than the traditional sliding windows used by `mpz_powm'. Sliding windows are more efficient on low Hamming-weight exponents, which is obviously bad if you were hoping for constant-time behaviour. * It uses a cache-oblivious algorithm to pick values out of its table of small multiples -- i.e., it scans the entire table and plucks out the entry it's looking for using bitmasking. (This is tweakable with a macro `WANT_CACHE_SECURITY', but that's hardwired on.) * It uses a constant-time conditional subtract to finish up after a Montgomery reduction. On the other hand there are some rough edges. * The initial reduction of the exponentiand is done with a non- constant-time algorithm. It /could/ be done a fancy way, using Montgomery reduction, but they've not done this yet. * I've not looked at the Secnet code to see whether there are other timing leaks. The call in `rsa_sig_check' is safe to leave as the faster `mpz_powm', since it's verifying a signature which could, in principle, be done by anyone using only public information. Signed-off-by: Mark Wooding --- dh.c | 4 ++-- rsa.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/dh.c b/dh.c index 4300a91..0616a43 100644 --- a/dh.c +++ b/dh.c @@ -52,7 +52,7 @@ static string_t dh_makepublic(void *sst, uint8_t *secret, int32_t secretlen) read_mpbin(&a, secret, secretlen); - mpz_powm(&b, &st->g, &a, &st->p); + mpz_powm_sec(&b, &st->g, &a, &st->p); r=write_mpstring(&b); @@ -76,7 +76,7 @@ static void dh_makeshared(void *sst, uint8_t *secret, int32_t secretlen, read_mpbin(&a, secret, secretlen); mpz_set_str(&b, rempublic, 16); - mpz_powm(&c, &b, &a, &st->p); + mpz_powm_sec(&c, &b, &a, &st->p); write_mpbin(&c,sharedsecret,buflen); diff --git a/rsa.c b/rsa.c index 51a382e..068cf41 100644 --- a/rsa.c +++ b/rsa.c @@ -148,8 +148,8 @@ static string_t rsa_sign(void *sst, uint8_t *data, int32_t datalen) mpz_init(&u); mpz_init(&v); - mpz_powm(&u, &a, &st->dp, &st->p); - mpz_powm(&v, &a, &st->dq, &st->q); + mpz_powm_sec(&u, &a, &st->dp, &st->p); + mpz_powm_sec(&v, &a, &st->dq, &st->q); mpz_sub(&tmp, &u, &v); mpz_mul(&tmp2, &tmp, &st->w); mpz_add(&tmp, &tmp2, &v); -- 2.11.0