[PATCH 2/2] dh.c, rsa.c: use `mpz_powm_sec' for modexps.

Mark Wooding mdw at distorted.org.uk
Thu Sep 29 00:42:29 BST 2016

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.
 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);
@@ -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);
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_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);

More information about the sgo-software-discuss mailing list