Avoid using unblinded Montgomery ladder during ECC key generation

As doing so means that information about the high bits of the scalar can leak
via timing since the loop bound depends on the length of the scalar. An attacker
who has such information can perform a more efficient brute force attack (using
Pollard's rho) than would be possible otherwise.

Found by Ján Jančár (@J08nY) using ECTester (https://github.com/crocs-muni/ECTester)

CVE-2018-20187

3 files changed, 41 insertions, 11 deletions

diff --git a/doc/security.rst b/doc/security.rst
index 07292132a..174732c4e 100644
--- a/doc/security.rst
+++ b/doc/security.rst
@@ -18,6 +18,15 @@ https://keybase.io/jacklloyd and on most PGP keyservers.
 2018
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
+* 2018-12-17 (CVE-2018-20187): Side channel during ECC key generation
+
+  A timing side channel during ECC key generation could leak information about
+  the high bits of the secret scalar. Such information allows an attacker to
+  perform a brute force attack on the key somewhat more efficiently than they
+  would otherwise. Found by Ján Jančár using ECTester.
+
+  Fixed in 2.8.0, all previous versions affected.
+
 * 2018-06-13 (CVE-2018-12435): ECDSA side channel
 
   A side channel in the ECDSA signature operation could allow a local attacker
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index f5b621dda..c7d8bc7ae 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -62,12 +62,14 @@ PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& b
    std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
 
    PointGFp g = base;
-   PointGFp g4;
+   PointGFp g2, g4;
 
    for(size_t i = 0; i != T_bits; i++)
       {
-      PointGFp g2 = g.double_of(ws);
-      g4 = g2.double_of(ws);
+      g2 = g;
+      g2.mult2(ws);
+      g4 = g2;
+      g4.mult2(ws);
 
       T[7*i+0] = g;
       T[7*i+1] = std::move(g2);
@@ -103,11 +105,28 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
    if(k.is_negative())
       throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
 
-   // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
-   const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS);
-
    // Instead of reducing k mod group order should we alter the mask size??
-   const BigInt scalar = m_mod_order.reduce(k) + group_order * mask;
+   BigInt scalar = m_mod_order.reduce(k);
+
+   if(rng.is_seeded())
+      {
+      // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
+      const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS);
+      scalar += group_order * mask;
+      }
+   else
+      {
+      /*
+      When we don't have an RNG we cannot do scalar blinding. Instead use the
+      same trick as OpenSSL and add one or two copies of the order to normalize
+      the length of the scalar at order.bits()+1. This at least ensures the loop
+      bound does not leak information about the high bits of the scalar.
+      */
+      scalar += group_order;
+      if(scalar.bits() == group_order.bits())
+         scalar += group_order;
+      BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
+      }
 
    const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
 
@@ -154,7 +173,7 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
 
       R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
 
-      if(i == 0)
+      if(i == 0 && rng.is_seeded())
          {
          /*
          * Since we start with the top bit of the exponent we know the
diff --git a/src/lib/pubkey/ecc_key/ecc_key.cpp b/src/lib/pubkey/ecc_key/ecc_key.cpp
index 767a799bf..5a97e7a50 100644
--- a/src/lib/pubkey/ecc_key/ecc_key.cpp
+++ b/src/lib/pubkey/ecc_key/ecc_key.cpp
@@ -127,15 +127,17 @@ EC_PrivateKey::EC_PrivateKey(RandomNumberGenerator& rng,
       m_private_key = x;
       }
 
-   // Can't use rng here because ffi load functions use Null_RNG
+   std::vector<BigInt> ws;
+
    if(with_modular_inverse)
       {
       // ECKCDSA
-      m_public_key = domain().get_base_point() * m_domain_params.inverse_mod_order(m_private_key);
+      m_public_key = domain().blinded_base_point_multiply(
+         m_domain_params.inverse_mod_order(m_private_key), rng, ws);
       }
    else
       {
-      m_public_key = domain().get_base_point() * m_private_key;
+      m_public_key = domain().blinded_base_point_multiply(m_private_key, rng, ws);
       }
 
    BOTAN_ASSERT(m_public_key.on_the_curve(),