Externalize the state of a RFC 6979 nonce computation.

This lets you amortize quite a few memory allocations (RNG, various
BigInts, etc) over many nonce generations.

Change generate_rfc6979_nonce to just instantiate one of these states,
call the function once, and return. This doesn't have any additional
overhead versus the previous implementation of this function.

Fix HMAC_DRBG to correctly reset its state to its starting position
when you call clear() on it.

6 files changed, 94 insertions, 32 deletions

diff --git a/src/lib/pubkey/rfc6979/rfc6979.cpp b/src/lib/pubkey/rfc6979/rfc6979.cpp
index 3bd723d6d..58cdbaa1b 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.cpp
+++ b/src/lib/pubkey/rfc6979/rfc6979.cpp
@@ -1,6 +1,6 @@
 /*
 * RFC 6979 Deterministic Nonce Generator
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -25,32 +25,43 @@ std::string hash_for_deterministic_signature(const std::string& emsa)
    return "SHA-512"; // safe default if nothing we understand
    }
 
-BigInt generate_rfc6979_nonce(const BigInt& x,
-                              const BigInt& q,
-                              const BigInt& h,
-                              const std::string& hash)
+RFC6979_Nonce_Generator::RFC6979_Nonce_Generator(const std::string& hash,
+                                                 const BigInt& order,
+                                                 const BigInt& x) :
+   m_order(order),
+   m_qlen(m_order.bits()),
+   m_rlen(m_qlen / 8 + (m_qlen % 8 ? 1 : 0)),
+   m_hmac_drbg(new HMAC_DRBG(make_message_auth("HMAC(" + hash + ")").release())),
+   m_rng_in(m_rlen * 2),
+   m_rng_out(m_rlen)
    {
-   HMAC_DRBG rng(make_message_auth("HMAC(" + hash + ")").release(), nullptr);
-
-   const size_t qlen = q.bits();
-   const size_t rlen = qlen / 8 + (qlen % 8 ? 1 : 0);
-
-   secure_vector<byte> input = BigInt::encode_1363(x, rlen);
-
-   input += BigInt::encode_1363(h, rlen);
-
-   rng.add_entropy(&input[0], input.size());
-
-   BigInt k;
+   BigInt::encode_1363(&m_rng_in[0], m_rlen, x);
+   }
 
-   secure_vector<byte> kbits(rlen);
+const BigInt& RFC6979_Nonce_Generator::nonce_for(const BigInt& m)
+   {
+   BigInt::encode_1363(&m_rng_in[m_rlen], m_rlen, m);
+   m_hmac_drbg->clear();
+   m_hmac_drbg->add_entropy(&m_rng_in[0], m_rng_in.size());
 
-   while(k == 0 || k >= q)
+   do
       {
-      rng.randomize(&kbits[0], kbits.size());
-      k = BigInt::decode(kbits) >> (8*rlen - qlen);
+      m_hmac_drbg->randomize(&m_rng_out[0], m_rng_out.size());
+      m_k.binary_decode(&m_rng_out[0], m_rng_out.size());
+      m_k >>= (8*m_rlen - m_qlen);
       }
+   while(m_k == 0 || m_k >= m_order);
 
+   return m_k;
+   }
+
+BigInt generate_rfc6979_nonce(const BigInt& x,
+                              const BigInt& q,
+                              const BigInt& h,
+                              const std::string& hash)
+   {
+   RFC6979_Nonce_Generator gen(hash, q, x);
+   BigInt k = gen.nonce_for(h);
    return k;
    }
 
diff --git a/src/lib/pubkey/rfc6979/rfc6979.h b/src/lib/pubkey/rfc6979/rfc6979.h
index 8e2940578..5b3dee8ef 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.h
+++ b/src/lib/pubkey/rfc6979/rfc6979.h
@@ -1,6 +1,6 @@
 /*
 * RFC 6979 Deterministic Nonce Generator
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -10,9 +10,31 @@
 
 #include <botan/bigint.h>
 #include <string>
+#include <memory>
 
 namespace Botan {
 
+class RandomNumberGenerator;
+
+class BOTAN_DLL RFC6979_Nonce_Generator
+   {
+   public:
+      /**
+      * Note: keeps persistent reference to order
+      */
+      RFC6979_Nonce_Generator(const std::string& hash,
+                              const BigInt& order,
+                              const BigInt& x);
+
+      const BigInt& nonce_for(const BigInt& m);
+   private:
+      const BigInt& m_order;
+      BigInt m_k;
+      size_t m_qlen, m_rlen;
+      std::unique_ptr<RandomNumberGenerator> m_hmac_drbg;
+      secure_vector<byte> m_rng_in, m_rng_out;
+   };
+
 /**
 * @param x the secret (EC)DSA key
 * @param q the group order
diff --git a/src/lib/rng/hmac_drbg/hmac_drbg.cpp b/src/lib/rng/hmac_drbg/hmac_drbg.cpp
index 064088c59..dc0d18afe 100644
--- a/src/lib/rng/hmac_drbg/hmac_drbg.cpp
+++ b/src/lib/rng/hmac_drbg/hmac_drbg.cpp
@@ -1,6 +1,6 @@
 /*
 * HMAC_DRBG
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -17,7 +17,7 @@ HMAC_DRBG::HMAC_DRBG(MessageAuthenticationCode* mac,
    m_V(m_mac->output_length(), 0x01),
    m_reseed_counter(0)
    {
-   m_mac->set_key(secure_vector<byte>(m_mac->output_length(), 0x00));
+   m_mac->set_key(std::vector<byte>(m_mac->output_length(), 0x00));
    }
 
 void HMAC_DRBG::randomize(byte out[], size_t length)
@@ -94,9 +94,11 @@ bool HMAC_DRBG::is_seeded() const
 
 void HMAC_DRBG::clear()
    {
-   zeroise(m_V);
+   m_reseed_counter = 0;
+   for(size_t i = 0; i != m_V.size(); ++i)
+      m_V[i] = 0x01;
 
-   m_mac->clear();
+   m_mac->set_key(std::vector<byte>(m_mac->output_length(), 0x00));
 
    if(m_prng)
       m_prng->clear();
diff --git a/src/lib/rng/hmac_drbg/hmac_drbg.h b/src/lib/rng/hmac_drbg/hmac_drbg.h
index b56e90fc4..979b754b2 100644
--- a/src/lib/rng/hmac_drbg/hmac_drbg.h
+++ b/src/lib/rng/hmac_drbg/hmac_drbg.h
@@ -1,6 +1,6 @@
 /*
 * HMAC_DRBG (SP800-90A)
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -33,7 +33,7 @@ class BOTAN_DLL HMAC_DRBG : public RandomNumberGenerator
       * @param underlying_rng RNG used generating inputs (eg HMAC_RNG)
       */
       HMAC_DRBG(MessageAuthenticationCode* mac,
-                RandomNumberGenerator* underlying_rng);
+                RandomNumberGenerator* underlying_rng = nullptr);
 
    private:
       void update(const byte input[], size_t input_len);
diff --git a/src/tests/test_rfc6979.cpp b/src/tests/test_rfc6979.cpp
index 8ecc04fa3..4f286b96e 100644
--- a/src/tests/test_rfc6979.cpp
+++ b/src/tests/test_rfc6979.cpp
@@ -22,10 +22,12 @@ size_t rfc6979_testcase(const std::string& q_str,
                         const std::string& hash,
                         size_t testcase)
    {
-   using namespace Botan;
+   size_t fails = 0;
 
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
 
+   using namespace Botan;
+
    const BigInt q(q_str);
    const BigInt x(x_str);
    const BigInt h(h_str);
@@ -37,12 +39,38 @@ size_t rfc6979_testcase(const std::string& q_str,
       {
       std::cout << "RFC 6979 test #" << testcase << " failed; generated k="
                 << std::hex << gen_k << "\n";
-      return 1;
+      ++fails;
+      }
+
+   RFC6979_Nonce_Generator gen(hash, q, x);
+
+   const BigInt gen_0 = gen.nonce_for(h);
+   if(gen_0 != exp_k)
+      {
+      std::cout << "RFC 6979 test #" << testcase << " failed; generated k="
+                << std::hex << gen_k << " (gen_0)\n";
+      ++fails;
+      }
+
+   const BigInt gen_1 = gen.nonce_for(h+1);
+   if(gen_1 == exp_k)
+      {
+      std::cout << "RFC 6979 test #" << testcase << " failed; generated k="
+                << std::hex << gen_1 << " (gen_1)\n";
+      ++fails;
+      }
+
+   const BigInt gen_2 = gen.nonce_for(h);
+   if(gen_2 != exp_k)
+      {
+      std::cout << "RFC 6979 test #" << testcase << " failed; generated k="
+                << std::hex << gen_2 << " (gen_2)\n";
+      ++fails;
       }
 
 #endif
 
-   return 0;
+   return fails;
    }
 
 }
diff --git a/src/tests/tests.h b/src/tests/tests.h
index 43ed1dbd5..a51f6742f 100644
--- a/src/tests/tests.h
+++ b/src/tests/tests.h
@@ -34,7 +34,6 @@ size_t run_tests(const std::string& filename,
                  bool clear_between_cb,
                  std::function<std::string (std::map<std::string, std::string>)> cb);
 
-std::vector<std::string> list_dir(const std::string& dir_path);
 size_t run_tests_in_dir(const std::string& dir, std::function<size_t (const std::string&)> fn);
 
 // Run a list of tests