From 0782d68840d0ebf850516e606e398b8a5396eb64 Mon Sep 17 00:00:00 2001 From: Legrandin Date: Fri, 27 Dec 2013 23:44:38 +0100 Subject: 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 --- lib/Crypto/PublicKey/DSA.py | 5 +++-- lib/Crypto/PublicKey/_slowmath.py | 7 ++++--- src/_fastmath.c | 28 +++++++++++++++++++--------- 3 files changed, 26 insertions(+), 14 deletions(-) diff --git a/lib/Crypto/PublicKey/DSA.py b/lib/Crypto/PublicKey/DSA.py index 69f7f04..a5d6f11 100644 --- a/lib/Crypto/PublicKey/DSA.py +++ b/lib/Crypto/PublicKey/DSA.py @@ -98,7 +98,7 @@ from Crypto.Util.py3compat import * from Crypto import Random from Crypto.IO import PKCS8, PEM -from Crypto.Util.number import bytes_to_long, long_to_bytes +from Crypto.Util.number import bytes_to_long, long_to_bytes, getRandomRange from Crypto.PublicKey import _DSA, _slowmath, pubkey from Crypto.Util.asn1 import DerObject, DerSequence,\ DerInteger, DerObjectId, DerBitString, newDerSequence, newDerBitString @@ -234,7 +234,8 @@ class _DSAobj(pubkey.pubkey): raise TypeError("DSA cannot unblind") def _sign(self, m, k): - return self.key._sign(m, k) + blind_factor = getRandomRange(1, self.key.q, self._randfunc) + return self.key._sign(m, k, blind_factor) def _verify(self, m, sig): (r, s) = sig diff --git a/lib/Crypto/PublicKey/_slowmath.py b/lib/Crypto/PublicKey/_slowmath.py index f28ea4c..e9f48f9 100644 --- a/lib/Crypto/PublicKey/_slowmath.py +++ b/lib/Crypto/PublicKey/_slowmath.py @@ -147,15 +147,16 @@ class _DSAKey(object): def has_private(self): return hasattr(self, 'x') - def _sign(self, m, k): # alias for _decrypt + def _sign(self, m, k, blind): # alias for _decrypt # SECURITY TODO - We _should_ be computing SHA1(m), but we don't because that's the API. if not self.has_private(): raise TypeError("No private key") if not (1L < k < self.q): raise ValueError("k is not between 2 and q-1") - inv_k = inverse(k, self.q) # Compute k**-1 mod q + inv_blind_k = inverse(blind * k, self.q) # Compute (blind * k)**-1 mod q + blind_x = self.x * blind r = pow(self.g, k, self.p) % self.q # r = (g**k mod p) mod q - s = (inv_k * (m + self.x * r)) % self.q + s = (inv_blind_k * (m * blind + blind_x * r)) % self.q return (r, s) def _verify(self, m, r, s): 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); -- cgit v1.2.1