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

2 files changed, 7 insertions, 5 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):