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.

5 files changed, 99 insertions, 73 deletions

diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 7bac56bc7..e6aa4a434 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -31,55 +31,6 @@ using namespace Botan;
 
 namespace {
 
-class Test_State
-   {
-   public:
-      void started(const std::string& /*msg*/) { m_tests_run++; }
-
-      void test_ran(const char* msg);
-
-      void failure(const char* test, const std::string& what_failed)
-         {
-         std::cout << "FAIL " << test << " " << what_failed << "\n";
-         m_tests_failed++;
-         }
-
-      size_t ran() const { return m_tests_run; }
-      size_t failed() const { return m_tests_failed; }
-   private:
-      size_t m_tests_run = 0, m_tests_failed = 0;
-   };
-
-#define BOTAN_CONFIRM_NOTHROW(block) do {                              \
-   try { block }                                                        \
-   catch(std::exception& e) {                                           \
-      _test.failure(BOTAN_CURRENT_FUNCTION, e.what());  \
-   } } while(0)                                                         \
-
-#define BOTAN_TEST(lhs, rhs, msg) do {                                     \
-   _test.started(msg);                                                  \
-   BOTAN_CONFIRM_NOTHROW({                                              \
-      const auto lhs_val = lhs;                                         \
-      const auto rhs_val = rhs;                                         \
-      const bool cmp = lhs_val == rhs_val;                              \
-      if(!cmp)                                                          \
-         {                                                              \
-         std::ostringstream fmt;                                        \
-         fmt << "expr '" << #lhs << " == " << #rhs << "' false, "       \
-             << "actually " << lhs_val << " " << rhs_val                \
-             << " (" << msg << ")";                                     \
-         _test.failure(BOTAN_CURRENT_FUNCTION, fmt.str()); \
-         }                                                              \
-      });                                                               \
-   } while(0)
-
-#define BOTAN_TEST_CASE(name, descr, block) size_t test_ ## name() {     \
-   Test_State _test;                                                    \
-   BOTAN_CONFIRM_NOTHROW(block);                                           \
-   test_report(descr, _test.ran(), _test.failed());                     \
-   return _test.failed();                                   \
-   }
-
 BOTAN_TEST_CASE(bigint_to_u32bit, "BigInt to_u32bit", {
    for(size_t i = 0; i != 32; ++i)
       {
diff --git a/src/tests/test_ecdsa.cpp b/src/tests/test_ecdsa.cpp
index a2ec8d115..8d385b4bf 100644
--- a/src/tests/test_ecdsa.cpp
+++ b/src/tests/test_ecdsa.cpp
@@ -25,7 +25,6 @@ size_t ecdsa_sig_kat(const std::string& group_id,
                      const std::string& x,
                      const std::string& hash,
                      const std::string& msg,
-                     const std::string& nonce,
                      const std::string& signature)
    {
    auto& rng = test_rng();
@@ -39,7 +38,7 @@ size_t ecdsa_sig_kat(const std::string& group_id,
    PK_Signer sign(ecdsa, padding);
 
    return validate_signature(verify, sign, "ECDSA/" + group_id + '/' + hash,
-                             msg, rng, nonce, signature);
+                             msg, rng, signature);
    }
 
 }
@@ -53,7 +52,7 @@ size_t test_ecdsa()
    fails += run_tests_bb(ecdsa_sig, "ECDSA Signature", "Signature", false,
              [](std::map<std::string, std::string> m) -> size_t
              {
-             return ecdsa_sig_kat(m["Group"], m["X"], m["Hash"], m["Msg"], m["Nonce"], m["Signature"]);
+             return ecdsa_sig_kat(m["Group"], m["X"], m["Hash"], m["Msg"], m["Signature"]);
              });
 
    return fails;
diff --git a/src/tests/tests.cpp b/src/tests/tests.cpp
index 63e6761ac..763417209 100644
--- a/src/tests/tests.cpp
+++ b/src/tests/tests.cpp
@@ -304,6 +304,7 @@ int main(int argc, char* argv[])
    DEF_TEST(mceliece);
 
    DEF_TEST(ecc_unit);
+   DEF_TEST(ecc_randomized);
    DEF_TEST(ecdsa_unit);
    DEF_TEST(ecdh_unit);
    DEF_TEST(pk_keygen);
diff --git a/src/tests/tests.h b/src/tests/tests.h
index 88102f289..14ec5a17b 100644
--- a/src/tests/tests.h
+++ b/src/tests/tests.h
@@ -16,6 +16,7 @@
 #include <string>
 #include <vector>
 #include <iostream>
+#include <sstream>
 
 Botan::RandomNumberGenerator& test_rng();
 
@@ -45,7 +46,69 @@ typedef std::function<size_t ()> test_fn;
 size_t run_tests(const std::vector<std::pair<std::string, test_fn>>& tests);
 void test_report(const std::string& name, size_t ran, size_t failed);
 
-#define TEST(expr, msg) do { if(!(expr)) { ++fails; std::cout << msg; } while(0)
+class Test_State
+   {
+   public:
+      void started(const std::string& /*msg*/) { m_tests_run++; }
+
+      void test_ran(const char* msg);
+
+      void failure(const char* test, const std::string& what_failed)
+         {
+         std::cout << "FAIL " << test << " " << what_failed << "\n";
+         m_tests_failed++;
+         }
+
+      size_t ran() const { return m_tests_run; }
+      size_t failed() const { return m_tests_failed; }
+   private:
+      size_t m_tests_run = 0, m_tests_failed = 0;
+   };
+
+#define BOTAN_CONFIRM_NOTHROW(block) do {                              \
+   try { block }                                                        \
+   catch(std::exception& e) {                                           \
+      _test.failure(BOTAN_CURRENT_FUNCTION, e.what());  \
+   } } while(0)                                                         \
+
+#define BOTAN_TEST(lhs, rhs, msg) do {                                     \
+   _test.started(msg);                                                  \
+   BOTAN_CONFIRM_NOTHROW({                                              \
+      const auto lhs_val = lhs;                                         \
+      const auto rhs_val = rhs;                                         \
+      const bool cmp = lhs_val == rhs_val;                              \
+      if(!cmp)                                                          \
+         {                                                              \
+         std::ostringstream fmt;                                        \
+         fmt << "expr '" << #lhs << " == " << #rhs << "' false, "       \
+             << "actually " << lhs_val << " " << rhs_val                \
+             << " (" << msg << ")";                                     \
+         _test.failure(BOTAN_CURRENT_FUNCTION, fmt.str()); \
+         }                                                              \
+      });                                                               \
+   } while(0)
+
+#define BOTAN_CONFIRM(expr, msg) do {                                     \
+   _test.started(msg);                                                  \
+   BOTAN_CONFIRM_NOTHROW({                                              \
+      const bool expr_val = expr;                                         \
+      if(!expr_val)                                                     \
+         {                                                              \
+         std::ostringstream fmt;                                        \
+         fmt << "expr '" << #expr << " false (" << msg << ")";           \
+         _test.failure(BOTAN_CURRENT_FUNCTION, fmt.str());              \
+         }                                                              \
+      });                                                               \
+   } while(0)
+
+#define BOTAN_TEST_CASE(name, descr, block) size_t test_ ## name() {     \
+   Test_State _test;                                                    \
+   BOTAN_CONFIRM_NOTHROW(block);                                           \
+   test_report(descr, _test.ran(), _test.failed());                     \
+   return _test.failed();                                   \
+   }
+
+//#define TEST(expr, msg) do { if(!(expr)) { ++fails; std::cout << msg; } while(0)
 
 #define TEST_DATA_DIR     "src/tests/data"
 #define TEST_DATA_DIR_PK  "src/tests/data/pubkey"
@@ -75,6 +138,7 @@ size_t test_dh();
 size_t test_dlies();
 size_t test_elgamal();
 size_t test_ecc_pointmul();
+size_t test_ecc_random();
 size_t test_ecdsa();
 size_t test_gost_3410();
 size_t test_curve25519();
@@ -94,6 +158,7 @@ size_t test_pk_keygen();
 size_t test_bigint();
 
 size_t test_ecc_unit();
+size_t test_ecc_randomized();
 size_t test_ecdsa_unit();
 size_t test_ecdh_unit();
 
diff --git a/src/tests/unit_ecc.cpp b/src/tests/unit_ecc.cpp
index 8498e3b43..3cb1436d3 100644
--- a/src/tests/unit_ecc.cpp
+++ b/src/tests/unit_ecc.cpp
@@ -816,9 +816,9 @@ size_t test_curve_cp_ctor()
    return 0;
    }
 
-size_t ecc_randomized_test()
-   {
-   const std::vector<std::string> groups = {
+namespace {
+
+const std::vector<std::string> ec_groups = {
       "brainpool160r1",
       "brainpool192r1",
       "brainpool224r1",
@@ -849,11 +849,16 @@ size_t ecc_randomized_test()
       "x962_p239v3"
    };
 
+}
+
+}
+
+BOTAN_TEST_CASE(ecc_randomized, "ECC Randomized", {
    auto& rng = test_rng();
    size_t fails = 0;
    size_t tests = 0;
 
-   for(auto&& group_name : groups)
+   for(auto&& group_name : ec_groups)
       {
       EC_Group group(group_name);
 
@@ -861,8 +866,8 @@ size_t ecc_randomized_test()
       const BigInt& group_order = group.get_order();
 
       const PointGFp inf = base_point * group_order;
-      CHECK(inf.is_zero());
-      CHECK(inf.on_the_curve());
+      BOTAN_CONFIRM(inf.is_zero(), "Group math ok");
+      BOTAN_CONFIRM(inf.on_the_curve(), "Infinity still on the curve");
 
       try
          {
@@ -870,6 +875,9 @@ size_t ecc_randomized_test()
             {
             ++tests;
 
+            const size_t h = 1 + (rng.next_byte() % 8);
+            Blinded_Point_Multiply blind(base_point, group_order, h);
+
             const BigInt a = BigInt::random_integer(rng, 2, group_order);
             const BigInt b = BigInt::random_integer(rng, 2, group_order);
             const BigInt c = a + b;
@@ -878,16 +886,24 @@ size_t ecc_randomized_test()
             const PointGFp Q = base_point * b;
             const PointGFp R = base_point * c;
 
+            const PointGFp P1 = blind.blinded_multiply(a, rng);
+            const PointGFp Q1 = blind.blinded_multiply(b, rng);
+            const PointGFp R1 = blind.blinded_multiply(c, rng);
+
             const PointGFp A1 = P + Q;
             const PointGFp A2 = Q + P;
 
-            CHECK(A1 == R);
-            CHECK(A2 == R);
-            CHECK(P.on_the_curve());
-            CHECK(Q.on_the_curve());
-            CHECK(R.on_the_curve());
-            CHECK(A1.on_the_curve());
-            CHECK(A2.on_the_curve());
+            BOTAN_TEST(A1, R, "Addition");
+            BOTAN_TEST(A2, R, "Addition");
+            BOTAN_CONFIRM(P.on_the_curve(), "On the curve");
+            BOTAN_CONFIRM(Q.on_the_curve(), "On the curve");
+            BOTAN_CONFIRM(R.on_the_curve(), "On the curve");
+            BOTAN_CONFIRM(A1.on_the_curve(), "On the curve");
+            BOTAN_CONFIRM(A2.on_the_curve(), "On the curve");
+
+            BOTAN_TEST(P, P1, "P1");
+            BOTAN_TEST(Q, Q1, "Q1");
+            BOTAN_TEST(R, R1, "R1");
             }
          }
       catch(std::exception& e)
@@ -896,12 +912,8 @@ size_t ecc_randomized_test()
          ++fails;
          }
       }
+   });
 
-   test_report("ECC Randomized", tests, fails);
-   return fails;
-   }
-
-}
 
 size_t test_ecc_unit()
    {
@@ -934,8 +946,6 @@ size_t test_ecc_unit()
 
    test_report("ECC", 0, fails);
 
-   ecc_randomized_test();
-
    return fails;
    }