From 44a287747f8594c0ab517526190c7d8af6f8572b Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Thu, 26 May 2005 04:40:42 +0000 Subject: [PATCH] make sure DSA signing exponentiations really are constant-time --- CHANGES | 7 +++++++ crypto/dsa/dsa_ossl.c | 30 +++++++++++++++++++++++++++--- 2 files changed, 34 insertions(+), 3 deletions(-) diff --git a/CHANGES b/CHANGES index 83ffbba552..33f1067330 100644 --- a/CHANGES +++ b/CHANGES @@ -4,6 +4,13 @@ Changes between 0.9.7g and 0.9.7h [XX xxx XXXX] + *) For DSA signing, unless DSA_FLAG_NO_EXP_CONSTTIME is set, perform + the exponentiation using a fixed-length exponent. (Otherwise, + the information leaked through timing could expose the secret key + after many signatures; cf. Bleichenbacher's attack on DSA with + biased k.) + [Bodo Moeller] + *) Make a new fixed-window mod_exp implementation the default for RSA, DSA, and DH private-key operations so that the sequence of squares and multiplies and the memory access pattern are diff --git a/crypto/dsa/dsa_ossl.c b/crypto/dsa/dsa_ossl.c index e668b079e3..12509a7083 100644 --- a/crypto/dsa/dsa_ossl.c +++ b/crypto/dsa/dsa_ossl.c @@ -172,7 +172,7 @@ err: static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) { BN_CTX *ctx; - BIGNUM k,*kinv=NULL,*r=NULL; + BIGNUM k,kq,*K,*kinv=NULL,*r=NULL; int ret=0; if (!dsa->p || !dsa->q || !dsa->g) @@ -182,6 +182,7 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) } BN_init(&k); + BN_init(&kq); if (ctx_in == NULL) { @@ -191,7 +192,6 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) ctx=ctx_in; if ((r=BN_new()) == NULL) goto err; - kinv=NULL; /* Get random k */ do @@ -211,7 +211,30 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) } /* Compute r = (g^k mod p) mod q */ - if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx, + + if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) + { + if (!BN_copy(&kq, &k)) goto err; + + /* We do not want timing information to leak the length of k, + * so we compute g^k using an equivalent exponent of fixed length. + * + * (This is a kludge that we need because the BN_mod_exp_mont() + * does not let us specify the desired timing behaviour.) */ + + if (!BN_add(&kq, &kq, dsa->q)) goto err; + if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) + { + if (!BN_add(&kq, &kq, dsa->q)) goto err; + } + + K = &kq; + } + else + { + K = &k; + } + if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,K,dsa->p,ctx, (BN_MONT_CTX *)dsa->method_mont_p)) goto err; if (!BN_mod(r,r,dsa->q,ctx)) goto err; @@ -234,6 +257,7 @@ err: if (ctx_in == NULL) BN_CTX_free(ctx); if (kinv != NULL) BN_clear_free(kinv); BN_clear_free(&k); + BN_clear_free(&kq); return(ret); } -- 2.25.1