From ff26efb1c4b8530024dc9b42d75e39536ece6e11 Mon Sep 17 00:00:00 2001 From: lloyd Date: Thu, 12 Mar 2015 11:48:27 +0000 Subject: 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. --- src/lib/pubkey/rfc6979/rfc6979.cpp | 53 ++++++++++++++++++++++--------------- src/lib/pubkey/rfc6979/rfc6979.h | 24 ++++++++++++++++- src/lib/rng/hmac_drbg/hmac_drbg.cpp | 10 ++++--- src/lib/rng/hmac_drbg/hmac_drbg.h | 4 +-- 4 files changed, 63 insertions(+), 28 deletions(-) (limited to 'src/lib') 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 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 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 #include +#include 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 m_hmac_drbg; + secure_vector 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(m_mac->output_length(), 0x00)); + m_mac->set_key(std::vector(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(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); -- cgit v1.2.3