Address DSA/ECDSA side channel

4 files changed, 80 insertions, 17 deletions

diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index 172804972..7142e4788 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -74,7 +74,9 @@ namespace {
 class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
    {
    public:
-      DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& emsa) :
+      DSA_Signature_Operation(const DSA_PrivateKey& dsa,
+                              const std::string& emsa,
+                              RandomNumberGenerator& rng) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(dsa.get_group()),
          m_x(dsa.get_x()),
@@ -83,6 +85,9 @@ class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
          m_rfc6979_hash = hash_for_emsa(emsa);
 #endif
+
+         m_b = BigInt::random_integer(rng, 2, dsa.group_q());
+         m_b_inv = inverse_mod(m_b, dsa.group_q());
          }
 
       size_t max_input_bits() const override { return m_group.get_q().bits(); }
@@ -96,6 +101,8 @@ class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
       std::string m_rfc6979_hash;
 #endif
+
+      BigInt m_b, m_b_inv;
    };
 
 secure_vector<uint8_t>
@@ -104,22 +111,32 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    {
    const BigInt& q = m_group.get_q();
 
-   BigInt i(msg, msg_len, q.bits());
+   BigInt m(msg, msg_len, q.bits());
 
-   while(i >= q)
-      i -= q;
+   while(m >= q)
+      m -= q;
 
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
    BOTAN_UNUSED(rng);
-   const BigInt k = generate_rfc6979_nonce(m_x, q, i, m_rfc6979_hash);
+   const BigInt k = generate_rfc6979_nonce(m_x, q, m, m_rfc6979_hash);
 #else
    const BigInt k = BigInt::random_integer(rng, 1, q);
 #endif
 
-   BigInt s = inverse_mod(k, q);
+   const BigInt k_inv = inverse_mod(k, q);
+
    const BigInt r = m_mod_q.reduce(m_group.power_g_p(k));
 
-   s = m_mod_q.multiply(s, mul_add(m_x, r, i));
+   /*
+   * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
+   */
+   m_b = m_mod_q.square(m_b);
+   m_b_inv = m_mod_q.square(m_b_inv);
+
+   m = m_mod_q.multiply(m_b, m);
+   const BigInt xr = m_mod_q.multiply(m_mod_q.multiply(m_x, m_b), r);
+
+   const BigInt s = m_mod_q.multiply(m_b_inv, m_mod_q.multiply(k_inv, xr + m));
 
    // With overwhelming probability, a bug rather than actual zero r/s
    if(r.is_zero() || s.is_zero())
@@ -140,7 +157,8 @@ class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
          m_group(dsa.get_group()),
          m_y(dsa.get_y()),
          m_mod_q(dsa.group_q())
-         {}
+         {
+         }
 
       size_t max_input_bits() const override { return m_group.get_q().bits(); }
 
@@ -193,12 +211,12 @@ DSA_PublicKey::create_verification_op(const std::string& params,
    }
 
 std::unique_ptr<PK_Ops::Signature>
-DSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
+DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
                                     const std::string& params,
                                     const std::string& provider) const
    {
    if(provider == "base" || provider.empty())
-      return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params));
+      return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params, rng));
    throw Provider_Not_Found(algo_name(), provider);
    }
 
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 004708c7c..2dfcdc0d9 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -84,11 +84,21 @@ class EC_Group_Data final
 
       BigInt mod_order(const BigInt& x) const { return m_mod_order.reduce(x); }
 
+      BigInt square_mod_order(const BigInt& x) const
+         {
+         return m_mod_order.square(x);
+         }
+
       BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const
          {
          return m_mod_order.multiply(x, y);
          }
 
+      BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const
+         {
+         return m_mod_order.multiply(m_mod_order.multiply(x, y), z);
+         }
+
       BigInt inverse_mod_order(const BigInt& x) const
          {
          return inverse_mod(x, m_order);
@@ -477,11 +487,21 @@ BigInt EC_Group::mod_order(const BigInt& k) const
    return data().mod_order(k);
    }
 
+BigInt EC_Group::square_mod_order(const BigInt& x) const
+   {
+   return data().square_mod_order(x);
+   }
+
 BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y) const
    {
    return data().multiply_mod_order(x, y);
    }
 
+BigInt EC_Group::multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const
+   {
+   return data().multiply_mod_order(x, y, z);
+   }
+
 BigInt EC_Group::inverse_mod_order(const BigInt& x) const
    {
    return data().inverse_mod_order(x);
diff --git a/src/lib/pubkey/ec_group/ec_group.h b/src/lib/pubkey/ec_group/ec_group.h
index f273108d2..f8c1c1a12 100644
--- a/src/lib/pubkey/ec_group/ec_group.h
+++ b/src/lib/pubkey/ec_group/ec_group.h
@@ -204,10 +204,20 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final
       BigInt inverse_mod_order(const BigInt& x) const;
 
       /*
+      * Reduce (x*x) modulo the order
+      */
+      BigInt square_mod_order(const BigInt& x) const;
+
+      /*
       * Reduce (x*y) modulo the order
       */
       BigInt multiply_mod_order(const BigInt& x, const BigInt& y) const;
 
+      /*
+      * Reduce (x*y*z) modulo the order
+      */
+      BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const;
+
       /**
       * Return the cofactor
       * @result the cofactor
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 6e104f164..2409d8f0d 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -51,7 +51,8 @@ class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
    public:
 
       ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
-                                const std::string& emsa) :
+                                const std::string& emsa,
+                                RandomNumberGenerator& rng) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(ecdsa.domain()),
          m_x(ecdsa.private_value())
@@ -59,6 +60,9 @@ class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
          m_rfc6979_hash = hash_for_emsa(emsa);
 #endif
+
+         m_b = m_group.random_scalar(rng);
+         m_b_inv = m_group.inverse_mod_order(m_b);
          }
 
       size_t max_input_bits() const override { return m_group.get_order_bits(); }
@@ -75,6 +79,8 @@ class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 #endif
 
       std::vector<BigInt> m_ws;
+
+      BigInt m_b, m_b_inv;
    };
 
 secure_vector<uint8_t>
@@ -89,12 +95,21 @@ ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    const BigInt k = m_group.random_scalar(rng);
 #endif
 
-   const BigInt k_inv = m_group.inverse_mod_order(k);
    const BigInt r = m_group.mod_order(
       m_group.blinded_base_point_multiply_x(k, rng, m_ws));
 
-   const BigInt xrm = m_group.mod_order(m_group.multiply_mod_order(m_x, r) + m);
-   const BigInt s = m_group.multiply_mod_order(k_inv, xrm);
+   const BigInt k_inv = m_group.inverse_mod_order(k);
+
+   /*
+   * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
+   */
+   m_b = m_group.square_mod_order(m_b);
+   m_b_inv = m_group.square_mod_order(m_b_inv);
+
+   m = m_group.multiply_mod_order(m_b, m);
+   const BigInt xr = m_group.multiply_mod_order(m_x, m_b, r);
+
+   const BigInt s = m_group.multiply_mod_order(k_inv, xr + m, m_b_inv);
 
    // With overwhelming probability, a bug rather than actual zero r/s
    if(r.is_zero() || s.is_zero())
@@ -144,7 +159,7 @@ bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
 
    const BigInt w = m_group.inverse_mod_order(s);
 
-   const BigInt u1 = m_group.multiply_mod_order(e, w);
+   const BigInt u1 = m_group.multiply_mod_order(m_group.mod_order(e), w);
    const BigInt u2 = m_group.multiply_mod_order(r, w);
    const PointGFp R = m_gy_mul.multi_exp(u1, u2);
 
@@ -198,7 +213,7 @@ ECDSA_PublicKey::create_verification_op(const std::string& params,
    }
 
 std::unique_ptr<PK_Ops::Signature>
-ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
+ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
                                       const std::string& params,
                                       const std::string& provider) const
    {
@@ -233,7 +248,7 @@ ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
 #endif
 
    if(provider == "base" || provider.empty())
-      return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params));
+      return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params, rng));
 
    throw Provider_Not_Found(algo_name(), provider);
    }