Add back in blinding to RSA, RW, ElGamal, and DH.

There are multiple unsatisfactory elements to the current solution,
as compared to how blinding was previously done:

Firstly, blinding is only used in the baseline implementations; the code
using OpenSSL and GMP is not protected by blinding at all.

Secondly, at the point we need to set up blinding, there is no access
to a PRNG. Currently I am going with a quite nasty solution, of using
a private key parameter to seed a simple PRNG constructed as:
  SHA-512(TS1 || private_key_param || public_key_param || TS2)

I really want to fix both of these elements but I'm not sure how to do
so easily.

15 files changed, 175 insertions, 103 deletions

diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index 6412d8a6a..724801040 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -20,7 +20,6 @@
 #define BOTAN_MP_WORD_BITS %{mp_bits}
 #define BOTAN_KARAT_MUL_THRESHOLD 32
 #define BOTAN_KARAT_SQR_THRESHOLD 32
-#define BOTAN_PRIVATE_KEY_OP_BLINDING_BITS 64
 
 /* PK key consistency checking toggles */
 #define BOTAN_PUBLIC_KEY_STRONG_CHECKS_ON_LOAD 1
diff --git a/src/math/numbertheory/blinding.cpp b/src/math/numbertheory/blinding.cpp
deleted file mode 100644
index c6a3fd1bd..000000000
--- a/src/math/numbertheory/blinding.cpp
+++ /dev/null
@@ -1,49 +0,0 @@
-/*
-* Blinder
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/blinding.h>
-#include <botan/numthry.h>
-
-namespace Botan {
-
-/*
-* Blinder Constructor
-*/
-Blinder::Blinder(const BigInt& e, const BigInt& d, const BigInt& n)
-   {
-   if(e < 1 || d < 1 || n < 1)
-      throw Invalid_Argument("Blinder: Arguments too small");
-
-   reducer = Modular_Reducer(n);
-   this->e = e;
-   this->d = d;
-   }
-
-/*
-* Blind a number
-*/
-BigInt Blinder::blind(const BigInt& i) const
-   {
-   if(!reducer.initialized())
-      return i;
-
-   e = reducer.square(e);
-   d = reducer.square(d);
-   return reducer.multiply(i, e);
-   }
-
-/*
-* Unblind a number
-*/
-BigInt Blinder::unblind(const BigInt& i) const
-   {
-   if(!reducer.initialized())
-      return i;
-   return reducer.multiply(i, d);
-   }
-
-}
diff --git a/src/math/numbertheory/blinding.h b/src/math/numbertheory/blinding.h
deleted file mode 100644
index 5f7f9e6b7..000000000
--- a/src/math/numbertheory/blinding.h
+++ /dev/null
@@ -1,34 +0,0 @@
-/*
-* Blinder
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_BLINDER_H__
-#define BOTAN_BLINDER_H__
-
-#include <botan/bigint.h>
-#include <botan/reducer.h>
-
-namespace Botan {
-
-/*
-* Blinding Function Object
-*/
-class BOTAN_DLL Blinder
-   {
-   public:
-      BigInt blind(const BigInt&) const;
-      BigInt unblind(const BigInt&) const;
-
-      Blinder() {}
-      Blinder(const BigInt&, const BigInt&, const BigInt&);
-   private:
-      Modular_Reducer reducer;
-      mutable BigInt e, d;
-   };
-
-}
-
-#endif
diff --git a/src/math/numbertheory/info.txt b/src/math/numbertheory/info.txt
index 58851e055..18349ef78 100644
--- a/src/math/numbertheory/info.txt
+++ b/src/math/numbertheory/info.txt
@@ -3,7 +3,6 @@ load_on auto
 define BIGINT_MATH
 
 <header:public>
-blinding.h
 curve_gfp.h
 numthry.h
 point_gfp.h
@@ -16,7 +15,6 @@ def_powm.h
 </header:internal>
 
 <source>
-blinding.cpp
 dsa_gen.cpp
 jacobi.cpp
 make_prm.cpp
diff --git a/src/pubkey/blinding.cpp b/src/pubkey/blinding.cpp
new file mode 100644
index 000000000..2bb6680d6
--- /dev/null
+++ b/src/pubkey/blinding.cpp
@@ -0,0 +1,76 @@
+/*
+* Blinding for public key operations
+* (C) 1999-2010 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/blinding.h>
+#include <botan/numthry.h>
+#include <botan/libstate.h>
+#include <botan/hash.h>
+#include <botan/time.h>
+#include <botan/loadstor.h>
+#include <memory>
+
+namespace Botan {
+
+/*
+* Blinder Constructor
+*/
+Blinder::Blinder(const BigInt& e, const BigInt& d, const BigInt& n)
+   {
+   if(e < 1 || d < 1 || n < 1)
+      throw Invalid_Argument("Blinder: Arguments too small");
+
+   reducer = Modular_Reducer(n);
+   this->e = e;
+   this->d = d;
+   }
+
+BigInt Blinder::choose_nonce(const BigInt& x, const BigInt& mod)
+   {
+   Algorithm_Factory& af = global_state().algorithm_factory();
+
+   std::auto_ptr<HashFunction> hash(af.make_hash_function("SHA-512"));
+
+   u64bit ns_clock = get_nanoseconds_clock();
+   for(size_t i = 0; i != sizeof(ns_clock); ++i)
+      hash->update(get_byte(0, ns_clock));
+
+   hash->update(BigInt::encode(x));
+   hash->update(BigInt::encode(mod));
+
+   u64bit timestamp = system_time();
+   for(size_t i = 0; i != sizeof(timestamp); ++i)
+      hash->update(get_byte(0, timestamp));
+
+   SecureVector<byte> r = hash->final();
+
+   return BigInt::decode(r) % mod;
+   }
+
+/*
+* Blind a number
+*/
+BigInt Blinder::blind(const BigInt& i) const
+   {
+   if(!reducer.initialized())
+      return i;
+
+   e = reducer.square(e);
+   d = reducer.square(d);
+   return reducer.multiply(i, e);
+   }
+
+/*
+* Unblind a number
+*/
+BigInt Blinder::unblind(const BigInt& i) const
+   {
+   if(!reducer.initialized())
+      return i;
+   return reducer.multiply(i, d);
+   }
+
+}
diff --git a/src/pubkey/blinding.h b/src/pubkey/blinding.h
new file mode 100644
index 000000000..d1d9a8875
--- /dev/null
+++ b/src/pubkey/blinding.h
@@ -0,0 +1,51 @@
+/*
+* Blinding for public key operations
+* (C) 1999-2010 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_BLINDER_H__
+#define BOTAN_BLINDER_H__
+
+#include <botan/bigint.h>
+#include <botan/reducer.h>
+
+namespace Botan {
+
+/*
+* Blinding Function Object
+*/
+class BOTAN_DLL Blinder
+   {
+   public:
+      BigInt blind(const BigInt& x) const;
+      BigInt unblind(const BigInt& x) const;
+
+      /**
+      * Choose a nonce to use for blinding
+      * @param x a secret seed value
+      * @param mod the modulus
+      */
+      static BigInt choose_nonce(const BigInt& x, const BigInt& mod);
+
+      Blinder() {}
+
+      /**
+      * Construct a blinder
+      * @param mask the forward (blinding) mask
+      * @param inverse_mask the inverse of mask (depends on algo)
+      * @param modulus of the group operations are performed in
+      */
+      Blinder(const BigInt& mask,
+              const BigInt& inverse_mask,
+              const BigInt& modulus);
+
+   private:
+      Modular_Reducer reducer;
+      mutable BigInt e, d;
+   };
+
+}
+
+#endif
diff --git a/src/pubkey/dh/dh.cpp b/src/pubkey/dh/dh.cpp
index 70791fee4..b242bf8c0 100644
--- a/src/pubkey/dh/dh.cpp
+++ b/src/pubkey/dh/dh.cpp
@@ -75,4 +75,20 @@ MemoryVector<byte> DH_PrivateKey::public_value() const
    return DH_PublicKey::public_value();
    }
 
+DH_KA_Operation::DH_KA_Operation(const DH_PrivateKey& dh) :
+   p(dh.group_p()), powermod_x_p(dh.get_x(), p)
+   {
+   BigInt k = Blinder::choose_nonce(dh.get_x(), p);
+   blinder = Blinder(k, power_mod(inverse_mod(k, p), dh.get_x(), p), p);
+   }
+
+SecureVector<byte> DH_KA_Operation::agree(const byte w[], u32bit w_len) const
+   {
+   BigInt input = BigInt::decode(w, w_len);
+
+   BigInt r = blinder.unblind(powermod_x_p(blinder.blind(input)));
+
+   return BigInt::encode_1363(r, p.bytes());
+   }
+
 }
diff --git a/src/pubkey/dh/dh.h b/src/pubkey/dh/dh.h
index ed8caf0c1..0cc2aaabc 100644
--- a/src/pubkey/dh/dh.h
+++ b/src/pubkey/dh/dh.h
@@ -10,6 +10,7 @@
 
 #include <botan/dl_algo.h>
 #include <botan/pow_mod.h>
+#include <botan/blinding.h>
 #include <botan/pk_ops.h>
 
 namespace Botan {
@@ -77,22 +78,14 @@ class BOTAN_DLL DH_PrivateKey : public DH_PublicKey,
 class BOTAN_DLL DH_KA_Operation : public PK_Ops::Key_Agreement
    {
    public:
+      DH_KA_Operation(const DH_PrivateKey& key);
 
-      DH_KA_Operation(const DH_PrivateKey& key) :
-         powermod_x_p(key.get_x(), key.get_domain().get_p()),
-         p_bytes(key.get_domain().get_p().bytes())
-         {}
-
-      SecureVector<byte> agree(const byte w[], u32bit w_len) const
-         {
-         return BigInt::encode_1363(
-            powermod_x_p(BigInt::decode(w, w_len)),
-            p_bytes);
-         }
-
+      SecureVector<byte> agree(const byte w[], u32bit w_len) const;
    private:
+      const BigInt& p;
+
       Fixed_Exponent_Power_Mod powermod_x_p;
-      u32bit p_bytes;
+      Blinder blinder;
    };
 
 }
diff --git a/src/pubkey/elgamal/elgamal.cpp b/src/pubkey/elgamal/elgamal.cpp
index fe83b3b2b..b2ffe36f3 100644
--- a/src/pubkey/elgamal/elgamal.cpp
+++ b/src/pubkey/elgamal/elgamal.cpp
@@ -117,6 +117,9 @@ ElGamal_Decryption_Operation::ElGamal_Decryption_Operation(const ElGamal_Private
 
    powermod_x_p = Fixed_Exponent_Power_Mod(key.get_x(), p);
    mod_p = Modular_Reducer(p);
+
+   BigInt k = Blinder::choose_nonce(key.get_x(), p);
+   blinder = Blinder(k, power_mod(k, key.get_x(), p), p);
    }
 
 SecureVector<byte>
@@ -135,7 +138,11 @@ ElGamal_Decryption_Operation::decrypt(const byte msg[], u32bit msg_len) const
    if(a >= p || b >= p)
       throw Invalid_Argument("ElGamal decryption: Invalid message");
 
-   return BigInt::encode(mod_p.multiply(b, inverse_mod(powermod_x_p(a), p)));
+   a = blinder.blind(a);
+
+   BigInt r = mod_p.multiply(b, inverse_mod(powermod_x_p(a), p));
+
+   return BigInt::encode(blinder.unblind(r));
    }
 
 }
diff --git a/src/pubkey/elgamal/elgamal.h b/src/pubkey/elgamal/elgamal.h
index dad9dbc3e..c94779e96 100644
--- a/src/pubkey/elgamal/elgamal.h
+++ b/src/pubkey/elgamal/elgamal.h
@@ -11,6 +11,7 @@
 #include <botan/dl_algo.h>
 #include <botan/numthry.h>
 #include <botan/reducer.h>
+#include <botan/blinding.h>
 #include <botan/pk_ops.h>
 
 namespace Botan {
@@ -80,6 +81,7 @@ class BOTAN_DLL ElGamal_Decryption_Operation : public PK_Ops::Decryption
    private:
       Fixed_Exponent_Power_Mod powermod_x_p;
       Modular_Reducer mod_p;
+      Blinder blinder;
    };
 
 }
diff --git a/src/pubkey/info.txt b/src/pubkey/info.txt
index a4a5bfc71..956a5e369 100644
--- a/src/pubkey/info.txt
+++ b/src/pubkey/info.txt
@@ -1,6 +1,7 @@
 define PUBLIC_KEY_CRYPTO
 
 <source>
+blinding.cpp
 pk_algs.cpp
 pk_keys.cpp
 pkcs8.cpp
@@ -11,6 +12,7 @@ x509_key.cpp
 </source>
 
 <header:public>
+blinding.h
 pk_keys.h
 pk_ops.h
 pkcs8.h
diff --git a/src/pubkey/rsa/rsa.cpp b/src/pubkey/rsa/rsa.cpp
index 984d030ef..2ac001a31 100644
--- a/src/pubkey/rsa/rsa.cpp
+++ b/src/pubkey/rsa/rsa.cpp
@@ -79,6 +79,8 @@ RSA_Private_Operation::RSA_Private_Operation(const RSA_PrivateKey& rsa) :
    powermod_d2_q(rsa.get_d2(), rsa.get_q()),
    mod_p(rsa.get_p())
    {
+   BigInt k = Blinder::choose_nonce(rsa.get_d(), n);
+   blinder = Blinder(power_mod(k, rsa.get_e(), n), inverse_mod(k, n), n);
    }
 
 BigInt RSA_Private_Operation::private_op(const BigInt& m) const
@@ -99,7 +101,7 @@ RSA_Private_Operation::sign(const byte msg[], u32bit msg_len,
                             RandomNumberGenerator&) const
    {
    BigInt m(msg, msg_len);
-   BigInt x = private_op(m);
+   BigInt x = blinder.unblind(private_op(blinder.blind(m)));
    return BigInt::encode_1363(x, n.bytes());
    }
 
@@ -110,7 +112,8 @@ SecureVector<byte>
 RSA_Private_Operation::decrypt(const byte msg[], u32bit msg_len) const
    {
    BigInt m(msg, msg_len);
-   return BigInt::encode(private_op(m));
+   BigInt x = blinder.unblind(private_op(blinder.blind(m)));
+   return BigInt::encode(x);
    }
 
 }
diff --git a/src/pubkey/rsa/rsa.h b/src/pubkey/rsa/rsa.h
index cf81e0f3b..fc84b36df 100644
--- a/src/pubkey/rsa/rsa.h
+++ b/src/pubkey/rsa/rsa.h
@@ -10,6 +10,7 @@
 
 #include <botan/if_algo.h>
 #include <botan/reducer.h>
+#include <botan/blinding.h>
 
 namespace Botan {
 
@@ -110,6 +111,7 @@ class BOTAN_DLL RSA_Private_Operation : public PK_Ops::Signature,
       const BigInt& c;
       Fixed_Exponent_Power_Mod powermod_d1_p, powermod_d2_q;
       Modular_Reducer mod_p;
+      Blinder blinder;
    };
 
 class BOTAN_DLL RSA_Public_Operation : public PK_Ops::Verification,
diff --git a/src/pubkey/rw/rw.cpp b/src/pubkey/rw/rw.cpp
index b2bf2f916..af2b849ff 100644
--- a/src/pubkey/rw/rw.cpp
+++ b/src/pubkey/rw/rw.cpp
@@ -81,6 +81,8 @@ RW_Signature_Operation::RW_Signature_Operation(const RW_PrivateKey& rw) :
    powermod_d2_q(rw.get_d2(), rw.get_q()),
    mod_p(rw.get_p())
    {
+   BigInt k = Blinder::choose_nonce(rw.get_d(), n);
+   blinder = Blinder(power_mod(k, rw.get_e(), n), inverse_mod(k, n), n);
    }
 
 SecureVector<byte>
@@ -95,11 +97,13 @@ RW_Signature_Operation::sign(const byte msg[], u32bit msg_len,
    if(jacobi(i, n) != 1)
       i >>= 1;
 
+   i = blinder.blind(i);
+
    BigInt j1 = powermod_d1_p(i);
    BigInt j2 = powermod_d2_q(i);
    j1 = mod_p.reduce(sub_mul(j1, j2, c));
 
-   BigInt r = mul_add(j1, q, j2);
+   BigInt r = blinder.unblind(mul_add(j1, q, j2));
 
    r = std::min(r, n - r);
 
diff --git a/src/pubkey/rw/rw.h b/src/pubkey/rw/rw.h
index 8ca8d18b0..25e7be634 100644
--- a/src/pubkey/rw/rw.h
+++ b/src/pubkey/rw/rw.h
@@ -10,6 +10,7 @@
 
 #include <botan/if_algo.h>
 #include <botan/reducer.h>
+#include <botan/blinding.h>
 
 namespace Botan {
 
@@ -73,6 +74,7 @@ class BOTAN_DLL RW_Signature_Operation : public PK_Ops::Signature
 
       Fixed_Exponent_Power_Mod powermod_d1_p, powermod_d2_q;
       Modular_Reducer mod_p;
+      Blinder blinder;
    };
 
 class BOTAN_DLL RW_Verification_Operation : public PK_Ops::Verification