Add side-channel countermeasures to DSA.

This patch strenghten the DSA signing code against
side-channel attacks.

The DSA signing formulae:

r = (g^{k} mod p) mod q
s = k^{-1} * (H(m) + r*x) mod q

becomes:

b = random in [1..q)
r = (g^{k} mod p) mod q
s = (b * k)^{-1} * (b*H(m) + r*(b*x)) mod q

In this way we avoid that the secret (x) gets multiplied
by a random factor (r) which is immediately disclosed
to an attacker (which we assume can both collect (r) and
also monitor the side-channel produced by the multiplication).

See also attack DSA_2 in:

"Minimum Requirements for Evaluating Side-Channel Attack Resistance
of RSA, DSA and Diffie-Hellman Key Exchange Implementations", BSI

1 files changed, 19 insertions, 9 deletions

diff --git a/src/_fastmath.c b/src/_fastmath.c
index 7d486c2..c331557 100644
--- a/src/_fastmath.c
+++ b/src/_fastmath.c
@@ -156,22 +156,28 @@ static PyObject *rsaKey_size (rsaKey *, PyObject *);
 static PyObject *rsaKey_has_private (rsaKey *, PyObject *);
 
 static int
-dsaSign (dsaKey * key, mpz_t m, mpz_t k, mpz_t r, mpz_t s)
+dsaSign (dsaKey * key, mpz_t m, mpz_t k, mpz_t blind, mpz_t r, mpz_t s)
 {
 	mpz_t temp;
+	mpz_t temp2;
 	if (mpz_cmp_ui (k, 2) < 0 || mpz_cmp (k, key->q) >= 0)
 	{
 		return 1;
 	}
 	mpz_init (temp);
+	mpz_init (temp2);
 	MPZ_POWM (r, key->g, k, key->p);
 	mpz_mod (r, r, key->q);
-	mpz_invert (s, k, key->q);
-	mpz_mul (temp, key->x, r);
-	mpz_add (temp, m, temp);
+	mpz_mul (temp, blind, key->x);
+	mpz_mul (temp, temp, r);
+	mpz_mul (temp2, m, blind);
+	mpz_add (temp, temp2, temp);
+	mpz_mul (s, k, blind);
+	mpz_invert (s, s, key->q);
 	mpz_mul (s, s, temp);
 	mpz_mod (s, s, key->q);
 	mpz_clear (temp);
+	mpz_clear (temp2);
 	return 0;
 }
 
@@ -490,21 +496,24 @@ dsaKey_getattro (dsaKey * key, PyObject *attr)
 static PyObject *
 dsaKey__sign (dsaKey * key, PyObject * args)
 {
-	PyObject *lm, *lk, *lr, *ls, *retval;
-	mpz_t m, k, r, s;
+	PyObject *lm, *lk, *lblind, *lr, *ls, *retval;
+	mpz_t m, k, blind, r, s;
 	int result;
-	if (!PyArg_ParseTuple (args, "O!O!", &PyLong_Type, &lm,
-			       &PyLong_Type, &lk))
+	if (!PyArg_ParseTuple (args, "O!O!O!", &PyLong_Type, &lm,
+			       &PyLong_Type, &lk,
+			       &PyLong_Type, &lblind))
 	{
 		return NULL;
 	}
 	mpz_init (m);
 	mpz_init (k);
+	mpz_init (blind);
 	mpz_init (r);
 	mpz_init (s);
 	longObjToMPZ (m, (PyLongObject *) lm);
 	longObjToMPZ (k, (PyLongObject *) lk);
-	result = dsaSign (key, m, k, r, s);
+	longObjToMPZ (blind, (PyLongObject *) lblind);
+	result = dsaSign (key, m, k, blind, r, s);
 	if (result == 1)
 	{
 		PyErr_SetString (PyExc_ValueError, "K not between 2 and q");
@@ -515,6 +524,7 @@ dsaKey__sign (dsaKey * key, PyObject * args)
 	if (lr == NULL || ls == NULL) goto errout;
 	mpz_clear (m);
 	mpz_clear (k);
+	mpz_clear (blind);
 	mpz_clear (r);
 	mpz_clear (s);
 	retval = Py_BuildValue ("(NN)", lr, ls);