Merge GH #2007 Improve RDRAND reseeding logic

5 files changed, 172 insertions, 145 deletions

diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index d969c7f5b..caa160eb0 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -210,24 +210,6 @@
 #define BOTAN_SYSTEM_RNG_POLL_TIMEOUT_MS 20
 
 /*
-How many times to read from the RDRAND/RDSEED RNGs.
-Each read generates 32 bits of output
-*/
-#define BOTAN_ENTROPY_INTEL_RNG_POLLS 32
-
-/*
-According to Intel, RDRAND is guaranteed to generate a random
-number within 10 retries on a working CPU
-*/
-#define BOTAN_ENTROPY_RDRAND_RETRIES 10
-
-/*
-* RdSeed is not guaranteed to generate a random number within a specific number of retries
-* Define the number of retries here
-*/
-#define BOTAN_ENTROPY_RDSEED_RETRIES 20
-
-/*
 * When a PBKDF is self-tuning parameters, it will attempt to take about this
 * amount of time to self-benchmark.
 */
diff --git a/src/lib/entropy/rdrand/rdrand.cpp b/src/lib/entropy/rdrand/rdrand.cpp
index b8a74ce2f..e22227326 100644
--- a/src/lib/entropy/rdrand/rdrand.cpp
+++ b/src/lib/entropy/rdrand/rdrand.cpp
@@ -1,6 +1,6 @@
 /*
 * Entropy Source Using Intel's rdrand instruction
-* (C) 2012,2015 Jack Lloyd
+* (C) 2012,2015,2019 Jack Lloyd
 * (C) 2015 Daniel Neus
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -13,12 +13,29 @@ namespace Botan {
 
 size_t Intel_Rdrand::poll(RandomNumberGenerator& rng)
    {
-   if(BOTAN_ENTROPY_INTEL_RNG_POLLS > 0 && RDRAND_RNG::available())
+   /*
+   * Intel's documentation for RDRAND at
+   * https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
+   * claims that software can guarantee a reseed event by polling enough data:
+   * "There is an upper bound of 511 samples per seed in the implementation
+   * where samples are 128 bits in size and can provide two 64-bit random
+   * numbers each."
+   *
+   * By requesting 8192 bytes we are asking for 512 samples and thus are assured
+   * that at some point in producing the output, at least one reseed of the
+   * internal state will occur.
+   *
+   * The alternative approach is to "Iteratively execute 32 RDRAND invocations
+   * with a 10 us wait period per iteration." however in practice this proves to
+   * be about 20x slower, despite producing much less seed material.
+   */
+   const size_t RDRAND_POLL_BYTES = 8*1024;
+
+   if(RDRAND_RNG::available())
       {
       RDRAND_RNG rdrand_rng;
-      secure_vector<uint8_t> buf(4 * BOTAN_ENTROPY_INTEL_RNG_POLLS);
-
-      rdrand_rng.randomize(buf.data(), buf.size());
+      secure_vector<uint8_t> buf(RDRAND_POLL_BYTES);
+      rdrand_rng.randomize(&buf[0], buf.size());
       rng.add_entropy(buf.data(), buf.size());
       }
 
diff --git a/src/lib/entropy/rdseed/rdseed.cpp b/src/lib/entropy/rdseed/rdseed.cpp
index fccc53f6a..1830edf9d 100644
--- a/src/lib/entropy/rdseed/rdseed.cpp
+++ b/src/lib/entropy/rdseed/rdseed.cpp
@@ -1,6 +1,7 @@
 /*
 * Entropy Source Using Intel's rdseed instruction
-* (C) 2015 Jack Lloyd, Daniel Neus
+* (C) 2015 Daniel Neus
+* (C) 2015,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -8,41 +9,88 @@
 #include <botan/internal/rdseed.h>
 #include <botan/cpuid.h>
 
-#if !defined(BOTAN_USE_GCC_INLINE_ASM)
-  #include <immintrin.h>
-#endif
+#include <immintrin.h>
 
 namespace Botan {
 
+namespace {
+
 BOTAN_FUNC_ISA("rdseed")
-size_t Intel_Rdseed::poll(RandomNumberGenerator& rng)
+bool read_rdseed(secure_vector<uint32_t>& seed)
    {
-   if(CPUID::has_rdseed())
+   /*
+   * RDSEED is not guaranteed to generate an output within any specific number
+   * of attempts. However in testing on a Skylake system, with all hyperthreads
+   * occupied in tight RDSEED loops, RDSEED will still usually succeed in under
+   * 150 attempts. The maximum ever seen was 230 attempts until success. When
+   * idle, RDSEED usually succeeds in 1 or 2 attempts.
+   *
+   * We set an upper bound of 512 attempts, because it is possible that due
+   * to firmware issue RDSEED is simply broken and never succeeds. We do not
+   * want to loop forever in that case. If we exceed that limit, then we assume
+   * the hardware is actually just broken, and stop the poll.
+   */
+   const size_t RDSEED_RETRIES = 512;
+
+   for(size_t i = 0; i != RDSEED_RETRIES; ++i)
       {
-      for(size_t p = 0; p != BOTAN_ENTROPY_INTEL_RNG_POLLS; ++p)
-         {
-         for(size_t i = 0; i != BOTAN_ENTROPY_RDSEED_RETRIES; ++i)
-            {
-            uint32_t r = 0;
+      uint32_t r = 0;
+      int cf = 0;
 
 #if defined(BOTAN_USE_GCC_INLINE_ASM)
-            int cf = 0;
-
-            // Encoding of rdseed %eax
-            asm(".byte 0x0F, 0xC7, 0xF8; adcl $0,%1" :
-                "=a" (r), "=r" (cf) : "0" (r), "1" (cf) : "cc");
+      asm("rdseed %0; adcl $0,%1" :
+          "=r" (r), "=r" (cf) : "0" (r), "1" (cf) : "cc");
 #else
-            int cf = _rdseed32_step(&r);
+      cf = _rdseed32_step(&r);
 #endif
-            if(1 == cf)
-               {
-               rng.add_entropy_T(r);
-               break;
-               }
-            }
+
+      if(1 == cf)
+         {
+         seed.push_back(r);
+         return true;
+         }
+
+      // Intel suggests pausing if RDSEED fails.
+      _mm_pause();
+      }
+
+   return false; // failed to produce an output after many attempts
+   }
+
+}
+
+size_t Intel_Rdseed::poll(RandomNumberGenerator& rng)
+   {
+   const size_t RDSEED_BYTES = 1024;
+   static_assert(RDSEED_BYTES % 4 == 0, "Bad RDSEED configuration");
+
+   if(CPUID::has_rdseed())
+      {
+      secure_vector<uint32_t> seed;
+      seed.reserve(RDSEED_BYTES / 4);
+
+      for(size_t p = 0; p != RDSEED_BYTES / 4; ++p)
+         {
+         /*
+         If at any point we exceed our retry count, we stop the entire seed
+         gathering process. This situation will only occur in situations of
+         extremely high RDSEED utilization. If RDSEED is currently so highly
+         contended, then the rest of the poll is likely to also face contention and
+         it is better to quit now rather than (presumably) face very high retry
+         times for the rest of the poll.
+         */
+         if(!read_rdseed(seed))
+            break;
+         }
+
+      if(seed.size() > 0)
+         {
+         rng.add_entropy(reinterpret_cast<const uint8_t*>(seed.data()),
+                         seed.size() * sizeof(uint32_t));
          }
       }
 
+   // RDSEED is used but not trusted
    return 0;
    }
 
diff --git a/src/lib/rng/rdrand_rng/rdrand_rng.cpp b/src/lib/rng/rdrand_rng/rdrand_rng.cpp
index 5b4b05ddb..fa612b615 100644
--- a/src/lib/rng/rdrand_rng/rdrand_rng.cpp
+++ b/src/lib/rng/rdrand_rng/rdrand_rng.cpp
@@ -1,6 +1,6 @@
 /*
 * RDRAND RNG
-* (C) 2016 Jack Lloyd
+* (C) 2016,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -15,77 +15,36 @@
 
 namespace Botan {
 
-RDRAND_RNG::RDRAND_RNG()
-   {
-   if(!RDRAND_RNG::available())
-      throw Invalid_State("Current CPU does not support RDRAND instruction");
-   }
-
-//static
-bool RDRAND_RNG::available()
-   {
-   return CPUID::has_rdrand();
-   }
-
-//static
-uint32_t RDRAND_RNG::rdrand()
-   {
-   for(;;)
-      {
-      bool ok = false;
-      uint32_t r = rdrand_status(ok);
-      if(ok)
-         return r;
-      }
-   }
-
-//static
-BOTAN_FUNC_ISA("rdrnd")
-uint32_t RDRAND_RNG::rdrand_status(bool& ok)
-   {
-   ok = false;
-   uint32_t r = 0;
-
-   for(size_t i = 0; i != BOTAN_ENTROPY_RDRAND_RETRIES; ++i)
-      {
-#if defined(BOTAN_USE_GCC_INLINE_ASM)
-      int cf = 0;
+namespace {
 
-      // Encoding of rdrand %eax
-      asm(".byte 0x0F, 0xC7, 0xF0; adcl $0,%1" :
-          "=a" (r), "=r" (cf) : "0" (r), "1" (cf) : "cc");
+#if defined(BOTAN_TARGET_ARCH_IS_X86_64)
+   typedef uint64_t rdrand_output;
 #else
-      int cf = _rdrand32_step(&r);
+   typedef uint32_t rdrand_output;
 #endif
-      if(1 == cf)
-         {
-         ok = true;
-         break;
-         }
-      }
-
-   return r;
-   }
-
-#if defined(BOTAN_TARGET_ARCH_IS_X86_64)
-
-namespace {
 
 BOTAN_FUNC_ISA("rdrnd")
-uint64_t rdrand64()
+rdrand_output read_rdrand()
    {
-   for(;;)
-      {
-      uint64_t r = 0;
+   /*
+   * According to Intel, RDRAND is guaranteed to generate a random
+   * number within 10 retries on a working CPU
+   */
+   const size_t RDRAND_RETRIES = 10;
 
-#if defined(BOTAN_USE_GCC_INLINE_ASM)
+   for(size_t i = 0; i < RDRAND_RETRIES; ++i)
+      {
+      rdrand_output r = 0;
       int cf = 0;
 
-      // Encoding of rdrand %rax
-      asm(".byte 0x48, 0x0F, 0xC7, 0xF0; adcl $0,%1" :
-          "=a" (r), "=r" (cf) : "0" (r), "1" (cf) : "cc");
+#if defined(BOTAN_USE_GCC_INLINE_ASM)
+      // same asm seq works for 32 and 64 bit
+      asm("rdrand %0; adcl $0,%1" :
+          "=r" (r), "=r" (cf) : "0" (r), "1" (cf) : "cc");
+#elif defined(BOTAN_TARGET_ARCH_IS_X86_64)
+      cf = _rdrand64_step(&r);
 #else
-      int cf = _rdrand64_step(&r);
+      cf = _rdrand32_step(&r);
 #endif
       if(1 == cf)
          {
@@ -93,41 +52,62 @@ uint64_t rdrand64()
          }
       }
 
-   return 0;
+   throw PRNG_Unseeded("RDRAND read failed");
    }
 
 }
 
-#endif
-
 void RDRAND_RNG::randomize(uint8_t out[], size_t out_len)
    {
-#if defined(BOTAN_TARGET_ARCH_IS_X86_64)
-   while(out_len >= 8)
+   while(out_len >= sizeof(rdrand_output))
       {
-      const uint64_t r = rdrand64();
-
+      const rdrand_output r = read_rdrand();
       store_le(r, out);
-      out += 8;
-      out_len -= 8;
+      out += sizeof(rdrand_output);
+      out_len -= sizeof(rdrand_output);
       }
-#endif
 
-   while(out_len >= 4)
+   if(out_len > 0) // at most sizeof(rdrand_output)-1
       {
-      const uint32_t r = RDRAND_RNG::rdrand();
-
-      store_le(r, out);
-      out += 4;
-      out_len -= 4;
+      const rdrand_output r = read_rdrand();
+      for(size_t i = 0; i != out_len; ++i)
+         out[i] = get_byte(i, r);
       }
+   }
+
+RDRAND_RNG::RDRAND_RNG()
+   {
+   if(!RDRAND_RNG::available())
+      throw Invalid_State("Current CPU does not support RDRAND instruction");
+   }
 
-   if(out_len) // final trailing bytes, at most 3
+//static
+bool RDRAND_RNG::available()
+   {
+   return CPUID::has_rdrand();
+   }
+
+//static
+uint32_t RDRAND_RNG::rdrand()
+   {
+   return static_cast<uint32_t>(read_rdrand());
+   }
+
+//static
+BOTAN_FUNC_ISA("rdrnd")
+uint32_t RDRAND_RNG::rdrand_status(bool& ok)
+   {
+   ok = false;
+
+   try
       {
-      const uint32_t r = RDRAND_RNG::rdrand();
-      for(size_t i = 0; i != out_len; ++i)
-         out[i] = get_byte(i, r);
+      const uint32_t r = static_cast<uint32_t>(read_rdrand());
+      ok = true;
+      return r;
       }
+   catch(PRNG_Unseeded&) {}
+
+   return 0;
    }
 
 }
diff --git a/src/lib/rng/rdrand_rng/rdrand_rng.h b/src/lib/rng/rdrand_rng/rdrand_rng.h
index 181edcd47..f441731cf 100644
--- a/src/lib/rng/rdrand_rng/rdrand_rng.h
+++ b/src/lib/rng/rdrand_rng/rdrand_rng.h
@@ -1,6 +1,6 @@
 /*
 * RDRAND RNG
-* (C) 2016 Jack Lloyd
+* (C) 2016,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -16,18 +16,9 @@ class BOTAN_PUBLIC_API(2,0) RDRAND_RNG final : public Hardware_RNG
    {
    public:
       /**
-      * On correctly working hardware, RDRAND is always supposed to
-      * succeed within a set number of retries. If after that many
-      * retries RDRAND has still not suceeded, sets ok = false and
-      * returns 0.
-      */
-      static uint32_t rdrand_status(bool& ok);
-
-      /*
-      * Calls RDRAND until it succeeds, this could hypothetically
-      * loop forever on broken hardware.
+      * Constructor will throw if CPU does not have RDRAND bit set
       */
-      static uint32_t rdrand();
+      RDRAND_RNG();
 
       /**
       * Return true if RDRAND is available on the current processor
@@ -37,11 +28,6 @@ class BOTAN_PUBLIC_API(2,0) RDRAND_RNG final : public Hardware_RNG
       bool accepts_input() const override { return false; }
 
       /**
-      * Constructor will throw if CPU does not have RDRAND bit set
-      */
-      RDRAND_RNG();
-
-      /**
       * Uses RDRAND to produce output
       */
       void randomize(uint8_t out[], size_t out_len) override;
@@ -61,6 +47,20 @@ class BOTAN_PUBLIC_API(2,0) RDRAND_RNG final : public Hardware_RNG
       std::string name() const override { return "RDRAND"; }
 
       bool is_seeded() const override { return true; }
+
+      /**
+      * On correctly working hardware, RDRAND is always supposed to
+      * succeed within a set number of retries. If after that many
+      * retries RDRAND has still not suceeded, sets ok = false and
+      * returns 0.
+      */
+      static uint32_t BOTAN_DEPRECATED("Use RDRAND_RNG::randomize") rdrand_status(bool& ok);
+
+      /*
+      * Calls RDRAND until it succeeds, this could hypothetically
+      * loop forever on broken hardware.
+      */
+      static uint32_t BOTAN_DEPRECATED("Use RDRAND_RNG::randomize") rdrand();
    };
 
 }