Implement RFC 6979 determinstic signatures for DSA and ECDSA.

Drop the GNU MP engine. Its implementations were potentially faster in
some scenarios but not well protected against side channels.

9 files changed, 63 insertions, 43 deletions

diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index c66db52f6..1dc2173da 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -1,6 +1,6 @@
 /*
 * DSA
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2014 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -8,7 +8,9 @@
 #include <botan/dsa.h>
 #include <botan/numthry.h>
 #include <botan/keypair.h>
+#include <botan/rfc6979.h>
 #include <future>
+
 namespace Botan {
 
 /*
@@ -65,11 +67,13 @@ bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)");
    }
 
-DSA_Signature_Operation::DSA_Signature_Operation(const DSA_PrivateKey& dsa) :
+DSA_Signature_Operation::DSA_Signature_Operation(const DSA_PrivateKey& dsa,
+                                                 const std::string& emsa) :
    q(dsa.group_q()),
    x(dsa.get_x()),
    powermod_g_p(dsa.group_g(), dsa.group_p()),
-   mod_q(dsa.group_q())
+   mod_q(dsa.group_q()),
+   m_hash(hash_for_deterministic_signature(emsa))
    {
    }
 
@@ -80,22 +84,22 @@ DSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
    rng.add_entropy(msg, msg_len);
 
    BigInt i(msg, msg_len);
-   BigInt r = 0, s = 0;
-
-   while(r == 0 || s == 0)
-      {
-      BigInt k;
-      do
-         k.randomize(rng, q.bits());
-      while(k >= q);
-
-      auto future_r = std::async(std::launch::async,
-                            [&]() { return mod_q.reduce(powermod_g_p(k)); });
-
-      s = inverse_mod(k, q);
-      r = future_r.get();
-      s = mod_q.multiply(s, mul_add(x, r, i));
-      }
+
+   if(i >= q)
+      i -= q;
+
+   const BigInt k = generate_rfc6979_nonce(x, q, i, m_hash);
+
+   auto future_r = std::async(std::launch::async,
+                              [&]() { return mod_q.reduce(powermod_g_p(k)); });
+
+   BigInt s = inverse_mod(k, q);
+   const BigInt r = future_r.get();
+   s = mod_q.multiply(s, mul_add(x, r, i));
+
+   // With overwhelming probability, a bug rather than actual zero r/s
+   BOTAN_ASSERT(s != 0, "invalid s");
+   BOTAN_ASSERT(r != 0, "invalid r");
 
    secure_vector<byte> output(2*q.bytes());
    r.binary_encode(&output[output.size() / 2 - r.bytes()]);
diff --git a/src/lib/pubkey/dsa/dsa.h b/src/lib/pubkey/dsa/dsa.h
index 7d51cfdd0..19c6c22d6 100644
--- a/src/lib/pubkey/dsa/dsa.h
+++ b/src/lib/pubkey/dsa/dsa.h
@@ -63,7 +63,7 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
 class BOTAN_DLL DSA_Signature_Operation : public PK_Ops::Signature
    {
    public:
-      DSA_Signature_Operation(const DSA_PrivateKey& dsa);
+      DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& hash);
 
       size_t message_parts() const { return 2; }
       size_t message_part_size() const { return q.bytes(); }
@@ -76,6 +76,7 @@ class BOTAN_DLL DSA_Signature_Operation : public PK_Ops::Signature
       const BigInt& x;
       Fixed_Base_Power_Mod powermod_g_p;
       Modular_Reducer mod_q;
+      std::string m_hash;
    };
 
 /**
diff --git a/src/lib/pubkey/dsa/info.txt b/src/lib/pubkey/dsa/info.txt
index a3f2a1ee4..ad14494a2 100644
--- a/src/lib/pubkey/dsa/info.txt
+++ b/src/lib/pubkey/dsa/info.txt
@@ -6,4 +6,5 @@ dl_group
 keypair
 libstate
 numbertheory
+rfc6979
 </requires>
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 6ff082649..b83a41e68 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -9,6 +9,7 @@
 
 #include <botan/ecdsa.h>
 #include <botan/keypair.h>
+#include <botan/rfc6979.h>
 
 namespace Botan {
 
@@ -24,37 +25,30 @@ bool ECDSA_PrivateKey::check_key(RandomNumberGenerator& rng,
    return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)");
    }
 
-ECDSA_Signature_Operation::ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa) :
+ECDSA_Signature_Operation::ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa, const std::string& emsa) :
    base_point(ecdsa.domain().get_base_point()),
    order(ecdsa.domain().get_order()),
    x(ecdsa.private_value()),
-   mod_order(order)
+   mod_order(order),
+   m_hash(hash_for_deterministic_signature(emsa))
    {
    }
 
 secure_vector<byte>
 ECDSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                                RandomNumberGenerator& rng)
+                                RandomNumberGenerator&)
    {
-   rng.add_entropy(msg, msg_len);
+   const BigInt m(msg, msg_len);
 
-   BigInt m(msg, msg_len);
+   const BigInt k = generate_rfc6979_nonce(x, order, m, m_hash);
 
-   BigInt r = 0, s = 0;
+   const PointGFp k_times_P = base_point * k;
+   const BigInt r = mod_order.reduce(k_times_P.get_affine_x());
+   const BigInt s = mod_order.multiply(inverse_mod(k, order), mul_add(x, r, m));
 
-   while(r == 0 || s == 0)
-      {
-      // This contortion is necessary for the tests
-      BigInt k;
-      k.randomize(rng, order.bits());
-
-      while(k >= order)
-         k.randomize(rng, order.bits() - 1);
-
-      PointGFp k_times_P = base_point * k;
-      r = mod_order.reduce(k_times_P.get_affine_x());
-      s = mod_order.multiply(inverse_mod(k, order), mul_add(x, r, m));
-      }
+   // With overwhelming probability, a bug rather than actual zero r/s
+   BOTAN_ASSERT(s != 0, "invalid s");
+   BOTAN_ASSERT(r != 0, "invalid r");
 
    secure_vector<byte> output(2*order.bytes());
    r.binary_encode(&output[output.size() / 2 - r.bytes()]);
diff --git a/src/lib/pubkey/ecdsa/ecdsa.h b/src/lib/pubkey/ecdsa/ecdsa.h
index e37fa1562..40eb9c7a7 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -95,7 +95,8 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
 class BOTAN_DLL ECDSA_Signature_Operation : public PK_Ops::Signature
    {
    public:
-      ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa);
+      ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
+                                const std::string& hash);
 
       secure_vector<byte> sign(const byte msg[], size_t msg_len,
                               RandomNumberGenerator& rng);
@@ -109,6 +110,7 @@ class BOTAN_DLL ECDSA_Signature_Operation : public PK_Ops::Signature
       const BigInt& order;
       const BigInt& x;
       Modular_Reducer mod_order;
+      std::string m_hash;
    };
 
 /**
diff --git a/src/lib/pubkey/ecdsa/info.txt b/src/lib/pubkey/ecdsa/info.txt
index fcf688402..26640328f 100644
--- a/src/lib/pubkey/ecdsa/info.txt
+++ b/src/lib/pubkey/ecdsa/info.txt
@@ -6,4 +6,5 @@ ec_group
 ecc_key
 numbertheory
 rng
+rfc6979
 </requires>
diff --git a/src/lib/pubkey/pubkey.cpp b/src/lib/pubkey/pubkey.cpp
index a2c5cb745..a6fc7b2c9 100644
--- a/src/lib/pubkey/pubkey.cpp
+++ b/src/lib/pubkey/pubkey.cpp
@@ -134,10 +134,10 @@ PK_Signer::PK_Signer(const Private_Key& key,
    while(const Engine* engine = i.next())
       {
       if(!m_op)
-         m_op.reset(engine->get_signature_op(key, rng));
+         m_op.reset(engine->get_signature_op(key, emsa_name, rng));
 
       if(!m_verify_op && prot == ENABLE_FAULT_PROTECTION)
-         m_verify_op.reset(engine->get_verify_op(key, rng));
+         m_verify_op.reset(engine->get_verify_op(key, emsa_name, rng));
 
       if(m_op && (m_verify_op || prot == DISABLE_FAULT_PROTECTION))
          break;
@@ -249,7 +249,7 @@ PK_Verifier::PK_Verifier(const Public_Key& key,
 
    while(const Engine* engine = i.next())
       {
-      m_op.reset(engine->get_verify_op(key, rng));
+      m_op.reset(engine->get_verify_op(key, emsa_name, rng));
       if(m_op)
          break;
       }
diff --git a/src/lib/pubkey/rfc6979/rfc6979.cpp b/src/lib/pubkey/rfc6979/rfc6979.cpp
index 0bad4ecbf..21d6c356a 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.cpp
+++ b/src/lib/pubkey/rfc6979/rfc6979.cpp
@@ -8,9 +8,24 @@
 #include <botan/rfc6979.h>
 #include <botan/hmac_drbg.h>
 #include <botan/libstate.h>
+#include <botan/scan_name.h>
 
 namespace Botan {
 
+std::string hash_for_deterministic_signature(const std::string& emsa)
+   {
+   SCAN_Name emsa_name(emsa);
+
+   if(emsa_name.arg_count() > 0)
+      {
+      const std::string pos_hash = emsa_name.arg(0);
+      if(global_state().algorithm_factory().prototype_hash_function(pos_hash))
+         return pos_hash;
+      }
+
+   return "SHA-512"; // safe default if nothing we understand
+   }
+
 BigInt generate_rfc6979_nonce(const BigInt& x,
                               const BigInt& q,
                               const BigInt& h,
diff --git a/src/lib/pubkey/rfc6979/rfc6979.h b/src/lib/pubkey/rfc6979/rfc6979.h
index 6184d0dbb..6e6073154 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.h
+++ b/src/lib/pubkey/rfc6979/rfc6979.h
@@ -24,6 +24,8 @@ BigInt BOTAN_DLL generate_rfc6979_nonce(const BigInt& x,
                                         const BigInt& h,
                                         const std::string& hash);
 
+std::string hash_for_deterministic_signature(const std::string& emsa);
+
 }
 
 #endif