CVE-2018-12435: Exposure of Sensitive Information to an Unauthorized Actor (CWE-200)
value: Botan 2.5.0 through 2.6.0 before 2.7.0 allows a memory-cache side-channel attack on ECDSA signatures, aka the Return Of the Hidden Number Problem or ROHNP, related to dsa/dsa.cpp, ec_group/ec_group.cpp, and ecdsa/ecdsa.cpp. To discover an ECDSA key, the attacker needs access to either the local machine or a different virtual machine on the same physical host.
CWE description: The product exposes sensitive information to an actor that is not explicitly authorized to have access to that information.
CVSS v3 base score: 5.9
Published: 2018-06-15T02:29Z
Repository: https://github.com/randombit/botan
Language: C++
Files changed: doc/security.rst, src/lib/pubkey/dsa/dsa.cpp, src/lib/pubkey/ec_group/ec_group.cpp, src/lib/pubkey/ec_group/ec_group.h, src/lib/pubkey/ecdsa/ecdsa.cpp
Commit date: 2018-06-13 11:01:17 -0400
Commit message: Address DSA/ECDSA side channel

Diff: diff --git a/doc/security.rst b/doc/security.rst
index 8e661c0ad..cd84997cc 100644
--- a/doc/security.rst
+++ b/doc/security.rst
@@ -16,10 +16,18 @@ This key can be found in the file ``doc/pgpkey.txt`` or online at
 https://keybase.io/jacklloyd and on most PGP keyservers.
 
 2018
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
+* 2018-06-13 (CVE-2018-0495): ECDSA side channel
+
+  A side channel in the ECDSA signature operation could allow a local attacker
+  to recover the secret key. Found by Keegan Ryan of NCC Group.
+
+  Fixed in 2.7.0. Due to a slight difference in code structure, versions before
+  2.5.0 are not affected by this issue.
+
 * 2018-04-10 (CVE-2018-9860): Memory overread in TLS CBC decryption
 
   An off by one error in TLS CBC decryption meant that for a particular
   malformed ciphertext, the receiver would miscompute a length field and HMAC
   exactly 64K bytes of data following the record buffer as if it was part of the
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
@@ -72,19 +72,24 @@ namespace {
 * Object that can create a DSA signature
 */
 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()),
          m_mod_q(dsa.group_q())
          {
 #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(); }
 
       secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
@@ -94,34 +99,46 @@ class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
       const BigInt& m_x;
       Modular_Reducer m_mod_q;
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
       std::string m_rfc6979_hash;
 #endif
+
+      BigInt m_b, m_b_inv;
    };
 
 secure_vector<uint8_t>
 DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
                                   RandomNumberGenerator& rng)
    {
    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())
       throw Internal_Error("Computed zero r/s during DSA signature");
 
@@ -138,11 +155,12 @@ class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
                                  const std::string& emsa) :
          PK_Ops::Verification_with_EMSA(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(); }
 
       bool with_recovery() const override { return false; }
 
@@ -191,15 +209,15 @@ DSA_PublicKey::create_verification_op(const std::string& params,
       return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
    throw Provider_Not_Found(algo_name(), provider);
    }
 
 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
@@ -82,15 +82,25 @@ class EC_Group_Data final
       bool a_is_minus_3() const { return m_a_is_minus_3; }
       bool a_is_zero() const { return m_a_is_zero; }
 
       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);
          }
 
@@ -475,15 +485,25 @@ const BigInt& EC_Group::get_cofactor() const
 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
@@ -201,15 +201,25 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final
       /*
       * Return inverse of x modulo the order
       */
       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
       */
       const BigInt& get_cofactor() const;
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
@@ -49,18 +49,22 @@ namespace {
 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())
          {
 #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(); }
 
       secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
@@ -73,10 +77,12 @@ class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
       std::string m_rfc6979_hash;
 #endif
 
       std::vector<BigInt> m_ws;
+
+      BigInt m_b, m_b_inv;
    };
 
 secure_vector<uint8_t>
 ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
                                     RandomNumberGenerator& rng)
@@ -87,16 +93,25 @@ ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    const BigInt k = generate_rfc6979_nonce(m_x, m_group.get_order(), m, m_rfc6979_hash);
 #else
    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())
       throw Internal_Error("During ECDSA signature generated zero r/s");
 
@@ -142,11 +157,11 @@ bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
    if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order())
       return false;
 
    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);
 
    if(R.is_zero())
       return false;
@@ -196,11 +211,11 @@ ECDSA_PublicKey::create_verification_op(const std::string& params,
 
    throw Provider_Not_Found(algo_name(), provider);
    }
 
 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
    {
 #if defined(BOTAN_HAS_BEARSSL)
    if(provider == "bearssl" || provider.empty())
@@ -231,11 +246,11 @@ 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);
    }
 
 }

Vulnerable code:       DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& emsa) :
   BigInt i(msg, msg_len, q.bits());
   while(i >= q)
      i -= q;
   const BigInt k = generate_rfc6979_nonce(m_x, q, i, m_rfc6979_hash);
   BigInt s = inverse_mod(k, q);
   s = m_mod_q.multiply(s, mul_add(m_x, r, i));
         {}
DSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
      return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params));
                                const std::string& emsa) :
   const BigInt k_inv = m_group.inverse_mod_order(k);
   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 u1 = m_group.multiply_mod_order(e, w);
ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
      return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params));
Fixed code: * 2018-06-13 (CVE-2018-0495): ECDSA side channel

  A side channel in the ECDSA signature operation could allow a local attacker
  to recover the secret key. Found by Keegan Ryan of NCC Group.

  Fixed in 2.7.0. Due to a slight difference in code structure, versions before
  2.5.0 are not affected by this issue.

      DSA_Signature_Operation(const DSA_PrivateKey& dsa,
                              const std::string& emsa,
                              RandomNumberGenerator& rng) :

         m_b = BigInt::random_integer(rng, 2, dsa.group_q());
         m_b_inv = inverse_mod(m_b, dsa.group_q());

      BigInt m_b, m_b_inv;
   BigInt m(msg, msg_len, q.bits());
   while(m >= q)
      m -= q;
   const BigInt k = generate_rfc6979_nonce(m_x, q, m, m_rfc6979_hash);
   const BigInt k_inv = inverse_mod(k, q);

   /*
   * 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));
         {
         }
DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
      return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params, rng));
      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 BigInt& z) const
         {
         return m_mod_order.multiply(m_mod_order.multiply(x, y), z);
         }

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 BigInt& z) const
   {
   return data().multiply_mod_order(x, y, z);
   }

      /*
      * Reduce (x*x) modulo the order
      */
      BigInt square_mod_order(const BigInt& x) const;

      /*
      * Reduce (x*y*z) modulo the order
      */
      BigInt multiply_mod_order(const BigInt& x, const BigInt& y, const BigInt& z) const;

                                const std::string& emsa,
                                RandomNumberGenerator& rng) :

         m_b = m_group.random_scalar(rng);
         m_b_inv = m_group.inverse_mod_order(m_b);

      BigInt m_b, m_b_inv;
   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);
   const BigInt u1 = m_group.multiply_mod_order(m_group.mod_order(e), w);
ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
      return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params, rng));