Add power analysis countermeasures for ECC point multiplications.

The plain PointGFp operator* now uses Montgomery ladder exclusively.

Adds a blinded point multiply algorithm which uses exponent and point
randomization, as well as a Montgomery ladder technique that takes a
random walk of the possible addition chains for k.

2 files changed, 37 insertions, 35 deletions

diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 2518a14fe..c327a37c3 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -2,14 +2,13 @@
 * ECDSA implemenation
 * (C) 2007 Manuel Hartl, FlexSecure GmbH
 *     2007 Falko Strenzke, FlexSecure GmbH
-*     2008-2010 Jack Lloyd
+*     2008-2010,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/internal/pk_utils.h>
 #include <botan/ecdsa.h>
-#include <botan/reducer.h>
 #include <botan/keypair.h>
 #include <botan/rfc6979.h>
 
@@ -41,9 +40,10 @@ class ECDSA_Signature_Operation : public PK_Ops::Signature_with_EMSA
                                 const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          base_point(ecdsa.domain().get_base_point()),
-         order(ecdsa.domain().get_order()),
-         x(ecdsa.private_value()),
-         mod_order(order),
+         m_order(ecdsa.domain().get_order()),
+         m_base_point(ecdsa.domain().get_base_point(), m_order),
+         m_x(ecdsa.private_value()),
+         m_mod_order(m_order),
          m_hash(hash_for_deterministic_signature(emsa))
          {
          }
@@ -52,34 +52,36 @@ class ECDSA_Signature_Operation : public PK_Ops::Signature_with_EMSA
                                    RandomNumberGenerator& rng) override;
 
       size_t message_parts() const override { return 2; }
-      size_t message_part_size() const override { return order.bytes(); }
-      size_t max_input_bits() const override { return order.bits(); }
+      size_t message_part_size() const override { return m_order.bytes(); }
+      size_t max_input_bits() const override { return m_order.bits(); }
 
    private:
       const PointGFp& base_point;
-      const BigInt& order;
-      const BigInt& x;
-      Modular_Reducer mod_order;
+      const BigInt& m_order;
+      Blinded_Point_Multiply m_base_point;
+      const BigInt& m_x;
+      Modular_Reducer m_mod_order;
       std::string m_hash;
    };
 
 secure_vector<byte>
 ECDSA_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
-                                    RandomNumberGenerator&)
+                                    RandomNumberGenerator& rng)
    {
    const BigInt m(msg, msg_len);
 
-   const BigInt k = generate_rfc6979_nonce(x, order, m, m_hash);
+   const BigInt k = generate_rfc6979_nonce(m_x, m_order, m, m_hash);
 
-   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));
+   //const PointGFp k_times_P = base_point * k;
+   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const BigInt r = m_mod_order.reduce(k_times_P.get_affine_x());
+   const BigInt s = m_mod_order.multiply(inverse_mod(k, m_order), mul_add(m_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());
+   secure_vector<byte> output(2*m_order.bytes());
    r.binary_encode(&output[output.size() / 2 - r.bytes()]);
    s.binary_encode(&output[output.size() - s.bytes()]);
    return output;
diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp
index 9c3a0ef3c..f04692d12 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.cpp
+++ b/src/lib/pubkey/gost_3410/gost_3410.cpp
@@ -2,7 +2,7 @@
 * GOST 34.10-2001 implemenation
 * (C) 2007 Falko Strenzke, FlexSecure GmbH
 *          Manuel Hartl, FlexSecure GmbH
-* (C) 2008-2010 Jack Lloyd
+* (C) 2008-2010,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -16,7 +16,6 @@ namespace Botan {
 
 std::vector<byte> GOST_3410_PublicKey::x509_subject_public_key() const
    {
-   // Trust CryptoPro to come up with something obnoxious
    const BigInt x = public_point().get_affine_x();
    const BigInt y = public_point().get_affine_y();
 
@@ -53,7 +52,7 @@ GOST_3410_PublicKey::GOST_3410_PublicKey(const AlgorithmIdentifier& alg_id,
    {
    OID ecc_param_id;
 
-   // Also includes hash and cipher OIDs... brilliant design guys
+   // The parameters also includes hash and cipher OIDs
    BER_Decoder(alg_id.parameters).start_cons(SEQUENCE).decode(ecc_param_id);
 
    domain_params = EC_Group(ecc_param_id);
@@ -101,21 +100,23 @@ class GOST_3410_Signature_Operation : public PK_Ops::Signature_with_EMSA
       GOST_3410_Signature_Operation(const GOST_3410_PrivateKey& gost_3410,
                                     const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
-         base_point(gost_3410.domain().get_base_point()),
-         order(gost_3410.domain().get_order()),
-         x(gost_3410.private_value()) {}
+         m_order(gost_3410.domain().get_order()),
+         m_mod_order(m_order),
+         m_base_point(gost_3410.domain().get_base_point(), m_order),
+         m_x(gost_3410.private_value()) {}
 
       size_t message_parts() const override { return 2; }
-      size_t message_part_size() const override { return order.bytes(); }
-      size_t max_input_bits() const override { return order.bits(); }
+      size_t message_part_size() const override { return m_order.bytes(); }
+      size_t max_input_bits() const override { return m_order.bits(); }
 
       secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
                                    RandomNumberGenerator& rng) override;
 
    private:
-      const PointGFp& base_point;
-      const BigInt& order;
-      const BigInt& x;
+      const BigInt& m_order;
+      Modular_Reducer m_mod_order;
+      Blinded_Point_Multiply m_base_point;
+      const BigInt& m_x;
    };
 
 secure_vector<byte>
@@ -124,26 +125,25 @@ GOST_3410_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
    {
    BigInt k;
    do
-      k.randomize(rng, order.bits()-1);
-   while(k >= order);
+      k.randomize(rng, m_order.bits()-1);
+   while(k >= m_order);
 
    BigInt e = decode_le(msg, msg_len);
 
-   e %= order;
+   e = m_mod_order.reduce(e);
    if(e == 0)
       e = 1;
 
-   PointGFp k_times_P = base_point * k;
+   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
    BOTAN_ASSERT(k_times_P.on_the_curve(), "GOST 34.10 k*g is on the curve");
 
-   BigInt r = k_times_P.get_affine_x() % order;
-
-   BigInt s = (r*x + k*e) % order;
+   const BigInt r = m_mod_order.reduce(k_times_P.get_affine_x());
+   const BigInt s = m_mod_order.reduce(r*m_x + k*e);
 
    if(r == 0 || s == 0)
       throw Invalid_State("GOST 34.10: r == 0 || s == 0");
 
-   secure_vector<byte> output(2*order.bytes());
+   secure_vector<byte> output(2*m_order.bytes());
    s.binary_encode(&output[output.size() / 2 - s.bytes()]);
    r.binary_encode(&output[output.size() - r.bytes()]);
    return output;