Merge #14955: Switch all RNG code to the built-in PRNG

223de8d94d6522f795ec3c2e7db27469f24aa68c Document RNG design in random.h (Pieter Wuille)
f2e60ca98530e0a865ff6c6fd3c5633aec11a515 Use secure allocator for RNG state (Pieter Wuille)
cddb31bb0a132afa50b5350196cf26f0064fe3e2 Encapsulate RNGState better (Pieter Wuille)
152146e782d401aa1ce7d989d62306aabc85f22e DRY: Implement GetRand using FastRandomContext::randrange (Pieter Wuille)
a1f252eda87356fa329c838a7bf569808489648f Sprinkle some sweet noexcepts over the RNG code (Pieter Wuille)
4ea8e50837a0932b31a241988fd68d6730a2048a Remove hwrand_initialized. (Pieter Wuille)
9d7032e4f066777c97c58b1394884716e213790a Switch all RNG code to the built-in PRNG. (Pieter Wuille)
16e40a8b562ad849a5f5e8b21ceb375e46038243 Integrate util/system's CInit into RNGState (Pieter Wuille)
2ccc3d3aa346e96206281a391bc29874cf5ee7f4 Abstract out seeding/extracting entropy into RNGState::MixExtract (Pieter Wuille)
aae8b9bf0f4fd2b801ee72cf191588c8b3a67c3c Add thread safety annotations to RNG state (Pieter Wuille)
d3f54d1c82b131d817b20cd9daa75f9d3c9475e1 Rename some hardware RNG related functions (Pieter Wuille)
05fde14e3afe6f7156ebb6df6cd0e3ae12635b89 Automatically initialize RNG on first use. (Pieter Wuille)
2d1cc5093949f8ea9487a68724162c8b39035ad8 Don't log RandAddSeedPerfmon details (Pieter Wuille)
6a57ca91da23c6a5d91399ffc7fc09a99b6d4c76 Use FRC::randbytes instead of reading >32 bytes from RNG (Pieter Wuille)

Pull request description:

  This does not remove OpenSSL, but makes our own PRNG the 'main' one; for GetStrongRandBytes, the OpenSSL RNG is still used (indirectly, by feeding its output into our PRNG state).

  It includes a few policy changes (regarding what entropy is seeded when).

  Before this PR:
  * GetRand*:
    * OpenSSL
  * GetStrongRand*:
    * CPU cycle counter
    * Perfmon data (on Windows, once 10 min)
    * /dev/urandom (or equivalent)
    * rdrand (if available)
  * From scheduler when idle:
    * CPU cycle counter before and after 1ms sleep
  * At startup:
    * CPU cycle counter before and after 1ms sleep

  After this PR:
  * GetRand*:
    * Stack pointer (which indirectly identifies thread and some call stack information)
    * rdrand (if available)
    * CPU cycle counter
  * GetStrongRand*:
    * Stack pointer (which indirectly identifies thread and some call stack information)
    * rdrand (if available)
    * CPU cycle counter
    * /dev/urandom (or equivalent)
    * OpenSSL
    * CPU cycle counter again
  * From scheduler when idle:
    * Stack pointer (which indirectly identifies thread and some call stack information)
    * rdrand (if available)
    * CPU cycle counter before and after 1ms sleep
    * Perfmon data (on Windows, once every 10 min)
  * At startup:
    * Stack pointer (which indirectly identifies thread and some call stack information)
    * rdrand (if available)
    * CPU cycle counter
    * /dev/urandom (or equivalent)
    * OpenSSL
    * CPU cycle counter again
    * Perfmon data (on Windows, once every 10 min)

  The interface of random.h is also simplified, and documentation is added.

  This implements most of #14623.

Tree-SHA512: 0120e19bd4ce80a509b5c180a4f29497d299ce8242e25755880851344b825bc2d64a222bc245e659562fb5463fb7c70fbfcf003616be4dc59d0ed6534f93dd20

1 files changed, 259 insertions, 101 deletions

diff --git a/src/random.cpp b/src/random.cpp
index f8ffda136d..3b7f7910b0 100644
--- a/src/random.cpp
+++ b/src/random.cpp
@@ -19,6 +19,8 @@
 #include <chrono>
 #include <thread>
 
+#include <support/allocators/secure.h>
+
 #ifndef WIN32
 #include <fcntl.h>
 #include <sys/time.h>
@@ -47,6 +49,7 @@
 
 #include <openssl/err.h>
 #include <openssl/rand.h>
+#include <openssl/conf.h>
 
 [[noreturn]] static void RandFailure()
 {
@@ -54,7 +57,7 @@
     std::abort();
 }
 
-static inline int64_t GetPerformanceCounter()
+static inline int64_t GetPerformanceCounter() noexcept
 {
     // Read the hardware time stamp counter when available.
     // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information.
@@ -74,27 +77,38 @@ static inline int64_t GetPerformanceCounter()
 #endif
 }
 
-
 #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
-static std::atomic<bool> hwrand_initialized{false};
 static bool rdrand_supported = false;
 static constexpr uint32_t CPUID_F1_ECX_RDRAND = 0x40000000;
-static void RDRandInit()
+static void InitHardwareRand()
 {
     uint32_t eax, ebx, ecx, edx;
     if (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx & CPUID_F1_ECX_RDRAND)) {
-        LogPrintf("Using RdRand as an additional entropy source\n");
         rdrand_supported = true;
     }
-    hwrand_initialized.store(true);
 }
+
+static void ReportHardwareRand()
+{
+    if (rdrand_supported) {
+        // This must be done in a separate function, as HWRandInit() may be indirectly called
+        // from global constructors, before logging is initialized.
+        LogPrintf("Using RdRand as an additional entropy source\n");
+    }
+}
+
 #else
-static void RDRandInit() {}
+/* Access to other hardware random number generators could be added here later,
+ * assuming it is sufficiently fast (in the order of a few hundred CPU cycles).
+ * Slower sources should probably be invoked separately, and/or only from
+ * RandAddSeedSleep (which is called during idle background operation).
+ */
+static void InitHardwareRand() {}
+static void ReportHardwareRand() {}
 #endif
 
-static bool GetHWRand(unsigned char* ent32) {
+static bool GetHardwareRand(unsigned char* ent32) noexcept {
 #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
-    assert(hwrand_initialized.load(std::memory_order_relaxed));
     if (rdrand_supported) {
         uint8_t ok;
         // Not all assemblers support the rdrand instruction, write it in hex.
@@ -129,18 +143,8 @@ static bool GetHWRand(unsigned char* ent32) {
     return false;
 }
 
-void RandAddSeed()
+static void RandAddSeedPerfmon(CSHA512& hasher)
 {
-    // Seed with CPU performance counter
-    int64_t nCounter = GetPerformanceCounter();
-    RAND_add(&nCounter, sizeof(nCounter), 1.5);
-    memory_cleanse((void*)&nCounter, sizeof(nCounter));
-}
-
-static void RandAddSeedPerfmon()
-{
-    RandAddSeed();
-
 #ifdef WIN32
     // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
     // Seed with the entire set of perfmon data
@@ -164,15 +168,15 @@ static void RandAddSeedPerfmon()
     }
     RegCloseKey(HKEY_PERFORMANCE_DATA);
     if (ret == ERROR_SUCCESS) {
-        RAND_add(vData.data(), nSize, nSize / 100.0);
+        hasher.Write(vData.data(), nSize);
         memory_cleanse(vData.data(), nSize);
-        LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize);
     } else {
-        static bool warned = false; // Warn only once
-        if (!warned) {
-            LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) failed with code %i\n", __func__, ret);
-            warned = true;
-        }
+        // Performance data is only a best-effort attempt at improving the
+        // situation when the OS randomness (and other sources) aren't
+        // adequate. As a result, failure to read it is isn't considered critical,
+        // so we don't call RandFailure().
+        // TODO: Add logging when the logger is made functional before global
+        // constructors have been invoked.
     }
 #endif
 }
@@ -272,106 +276,255 @@ void GetOSRand(unsigned char *ent32)
 #endif
 }
 
-void GetRandBytes(unsigned char* buf, int num)
+void LockingCallbackOpenSSL(int mode, int i, const char* file, int line);
+
+namespace {
+
+class RNGState {
+    Mutex m_mutex;
+    /* The RNG state consists of 256 bits of entropy, taken from the output of
+     * one operation's SHA512 output, and fed as input to the next one.
+     * Carrying 256 bits of entropy should be sufficient to guarantee
+     * unpredictability as long as any entropy source was ever unpredictable
+     * to an attacker. To protect against situations where an attacker might
+     * observe the RNG's state, fresh entropy is always mixed when
+     * GetStrongRandBytes is called.
+     */
+    unsigned char m_state[32] GUARDED_BY(m_mutex) = {0};
+    uint64_t m_counter GUARDED_BY(m_mutex) = 0;
+    bool m_strongly_seeded GUARDED_BY(m_mutex) = false;
+    std::unique_ptr<Mutex[]> m_mutex_openssl;
+
+public:
+    RNGState() noexcept
+    {
+        InitHardwareRand();
+
+        // Init OpenSSL library multithreading support
+        m_mutex_openssl.reset(new Mutex[CRYPTO_num_locks()]);
+        CRYPTO_set_locking_callback(LockingCallbackOpenSSL);
+
+        // OpenSSL can optionally load a config file which lists optional loadable modules and engines.
+        // We don't use them so we don't require the config. However some of our libs may call functions
+        // which attempt to load the config file, possibly resulting in an exit() or crash if it is missing
+        // or corrupt. Explicitly tell OpenSSL not to try to load the file. The result for our libs will be
+        // that the config appears to have been loaded and there are no modules/engines available.
+        OPENSSL_no_config();
+    }
+
+    ~RNGState()
+    {
+        // Securely erase the memory used by the OpenSSL PRNG
+        RAND_cleanup();
+        // Shutdown OpenSSL library multithreading support
+        CRYPTO_set_locking_callback(nullptr);
+    }
+
+    /** Extract up to 32 bytes of entropy from the RNG state, mixing in new entropy from hasher.
+     *
+     * If this function has never been called with strong_seed = true, false is returned.
+     */
+    bool MixExtract(unsigned char* out, size_t num, CSHA512&& hasher, bool strong_seed) noexcept
+    {
+        assert(num <= 32);
+        unsigned char buf[64];
+        static_assert(sizeof(buf) == CSHA512::OUTPUT_SIZE, "Buffer needs to have hasher's output size");
+        bool ret;
+        {
+            LOCK(m_mutex);
+            ret = (m_strongly_seeded |= strong_seed);
+            // Write the current state of the RNG into the hasher
+            hasher.Write(m_state, 32);
+            // Write a new counter number into the state
+            hasher.Write((const unsigned char*)&m_counter, sizeof(m_counter));
+            ++m_counter;
+            // Finalize the hasher
+            hasher.Finalize(buf);
+            // Store the last 32 bytes of the hash output as new RNG state.
+            memcpy(m_state, buf + 32, 32);
+        }
+        // If desired, copy (up to) the first 32 bytes of the hash output as output.
+        if (num) {
+            assert(out != nullptr);
+            memcpy(out, buf, num);
+        }
+        // Best effort cleanup of internal state
+        hasher.Reset();
+        memory_cleanse(buf, 64);
+        return ret;
+    }
+
+    Mutex& GetOpenSSLMutex(int i) { return m_mutex_openssl[i]; }
+};
+
+RNGState& GetRNGState() noexcept
 {
-    if (RAND_bytes(buf, num) != 1) {
-        RandFailure();
+    // This C++11 idiom relies on the guarantee that static variable are initialized
+    // on first call, even when multiple parallel calls are permitted.
+    static std::vector<RNGState, secure_allocator<RNGState>> g_rng(1);
+    return g_rng[0];
+}
+}
+
+void LockingCallbackOpenSSL(int mode, int i, const char* file, int line) NO_THREAD_SAFETY_ANALYSIS
+{
+    RNGState& rng = GetRNGState();
+
+    if (mode & CRYPTO_LOCK) {
+        rng.GetOpenSSLMutex(i).lock();
+    } else {
+        rng.GetOpenSSLMutex(i).unlock();
     }
 }
 
-static void AddDataToRng(void* data, size_t len);
+/* A note on the use of noexcept in the seeding functions below:
+ *
+ * None of the RNG code should ever throw any exception, with the sole exception
+ * of MilliSleep in SeedSleep, which can (and does) support interruptions which
+ * cause a boost::thread_interrupted to be thrown.
+ *
+ * This means that SeedSleep, and all functions that invoke it are throwing.
+ * However, we know that GetRandBytes() and GetStrongRandBytes() never trigger
+ * this sleeping logic, so they are noexcept. The same is true for all the
+ * GetRand*() functions that use GetRandBytes() indirectly.
+ *
+ * TODO: After moving away from interruptible boost-based thread management,
+ * everything can become noexcept here.
+ */
 
-void RandAddSeedSleep()
+static void SeedTimestamp(CSHA512& hasher) noexcept
 {
-    int64_t nPerfCounter1 = GetPerformanceCounter();
-    std::this_thread::sleep_for(std::chrono::milliseconds(1));
-    int64_t nPerfCounter2 = GetPerformanceCounter();
+    int64_t perfcounter = GetPerformanceCounter();
+    hasher.Write((const unsigned char*)&perfcounter, sizeof(perfcounter));
+}
 
-    // Combine with and update state
-    AddDataToRng(&nPerfCounter1, sizeof(nPerfCounter1));
-    AddDataToRng(&nPerfCounter2, sizeof(nPerfCounter2));
+static void SeedFast(CSHA512& hasher) noexcept
+{
+    unsigned char buffer[32];
+
+    // Stack pointer to indirectly commit to thread/callstack
+    const unsigned char* ptr = buffer;
+    hasher.Write((const unsigned char*)&ptr, sizeof(ptr));
+
+    // Hardware randomness is very fast when available; use it always.
+    bool have_hw_rand = GetHardwareRand(buffer);
+    if (have_hw_rand) hasher.Write(buffer, sizeof(buffer));
 
-    memory_cleanse(&nPerfCounter1, sizeof(nPerfCounter1));
-    memory_cleanse(&nPerfCounter2, sizeof(nPerfCounter2));
+    // High-precision timestamp
+    SeedTimestamp(hasher);
 }
 
+static void SeedSlow(CSHA512& hasher) noexcept
+{
+    unsigned char buffer[32];
 
-static Mutex cs_rng_state;
-static unsigned char rng_state[32] = {0};
-static uint64_t rng_counter = 0;
+    // Everything that the 'fast' seeder includes
+    SeedFast(hasher);
 
-static void AddDataToRng(void* data, size_t len) {
-    CSHA512 hasher;
-    hasher.Write((const unsigned char*)&len, sizeof(len));
-    hasher.Write((const unsigned char*)data, len);
-    unsigned char buf[64];
-    {
-        WAIT_LOCK(cs_rng_state, lock);
-        hasher.Write(rng_state, sizeof(rng_state));
-        hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
-        ++rng_counter;
-        hasher.Finalize(buf);
-        memcpy(rng_state, buf + 32, 32);
-    }
-    memory_cleanse(buf, 64);
+    // OS randomness
+    GetOSRand(buffer);
+    hasher.Write(buffer, sizeof(buffer));
+
+    // OpenSSL RNG (for now)
+    RAND_bytes(buffer, sizeof(buffer));
+    hasher.Write(buffer, sizeof(buffer));
+
+    // High-precision timestamp.
+    //
+    // Note that we also commit to a timestamp in the Fast seeder, so we indirectly commit to a
+    // benchmark of all the entropy gathering sources in this function).
+    SeedTimestamp(hasher);
 }
 
-void GetStrongRandBytes(unsigned char* out, int num)
+static void SeedSleep(CSHA512& hasher)
 {
-    assert(num <= 32);
-    CSHA512 hasher;
-    unsigned char buf[64];
+    // Everything that the 'fast' seeder includes
+    SeedFast(hasher);
+
+    // High-precision timestamp
+    SeedTimestamp(hasher);
+
+    // Sleep for 1ms
+    MilliSleep(1);
+
+    // High-precision timestamp after sleeping (as we commit to both the time before and after, this measures the delay)
+    SeedTimestamp(hasher);
 
-    // First source: OpenSSL's RNG
-    RandAddSeedPerfmon();
-    GetRandBytes(buf, 32);
-    hasher.Write(buf, 32);
+    // Windows performance monitor data (once every 10 minutes)
+    RandAddSeedPerfmon(hasher);
+}
+
+static void SeedStartup(CSHA512& hasher) noexcept
+{
+#ifdef WIN32
+    RAND_screen();
+#endif
 
-    // Second source: OS RNG
-    GetOSRand(buf);
-    hasher.Write(buf, 32);
+    // Everything that the 'slow' seeder includes.
+    SeedSlow(hasher);
+
+    // Windows performance monitor data.
+    RandAddSeedPerfmon(hasher);
+}
+
+enum class RNGLevel {
+    FAST, //!< Automatically called by GetRandBytes
+    SLOW, //!< Automatically called by GetStrongRandBytes
+    SLEEP, //!< Called by RandAddSeedSleep()
+};
+
+static void ProcRand(unsigned char* out, int num, RNGLevel level)
+{
+    // Make sure the RNG is initialized first (as all Seed* function possibly need hwrand to be available).
+    RNGState& rng = GetRNGState();
 
-    // Third source: HW RNG, if available.
-    if (GetHWRand(buf)) {
-        hasher.Write(buf, 32);
+    assert(num <= 32);
+
+    CSHA512 hasher;
+    switch (level) {
+    case RNGLevel::FAST:
+        SeedFast(hasher);
+        break;
+    case RNGLevel::SLOW:
+        SeedSlow(hasher);
+        break;
+    case RNGLevel::SLEEP:
+        SeedSleep(hasher);
+        break;
     }
 
     // Combine with and update state
-    {
-        WAIT_LOCK(cs_rng_state, lock);
-        hasher.Write(rng_state, sizeof(rng_state));
-        hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
-        ++rng_counter;
-        hasher.Finalize(buf);
-        memcpy(rng_state, buf + 32, 32);
+    if (!rng.MixExtract(out, num, std::move(hasher), false)) {
+        // On the first invocation, also seed with SeedStartup().
+        CSHA512 startup_hasher;
+        SeedStartup(startup_hasher);
+        rng.MixExtract(out, num, std::move(startup_hasher), true);
     }
 
-    // Produce output
-    memcpy(out, buf, num);
-    memory_cleanse(buf, 64);
+    // For anything but the 'fast' level, feed the resulting RNG output (after an additional hashing step) back into OpenSSL.
+    if (level != RNGLevel::FAST) {
+        unsigned char buf[64];
+        CSHA512().Write(out, num).Finalize(buf);
+        RAND_add(buf, sizeof(buf), num);
+        memory_cleanse(buf, 64);
+    }
 }
 
-uint64_t GetRand(uint64_t nMax)
-{
-    if (nMax == 0)
-        return 0;
+void GetRandBytes(unsigned char* buf, int num) noexcept { ProcRand(buf, num, RNGLevel::FAST); }
+void GetStrongRandBytes(unsigned char* buf, int num) noexcept { ProcRand(buf, num, RNGLevel::SLOW); }
+void RandAddSeedSleep() { ProcRand(nullptr, 0, RNGLevel::SLEEP); }
 
-    // The range of the random source must be a multiple of the modulus
-    // to give every possible output value an equal possibility
-    uint64_t nRange = (std::numeric_limits<uint64_t>::max() / nMax) * nMax;
-    uint64_t nRand = 0;
-    do {
-        GetRandBytes((unsigned char*)&nRand, sizeof(nRand));
-    } while (nRand >= nRange);
-    return (nRand % nMax);
+uint64_t GetRand(uint64_t nMax) noexcept
+{
+    return FastRandomContext().randrange(nMax);
 }
 
-int GetRandInt(int nMax)
+int GetRandInt(int nMax) noexcept
 {
     return GetRand(nMax);
 }
 
-uint256 GetRandHash()
+uint256 GetRandHash() noexcept
 {
     uint256 hash;
     GetRandBytes((unsigned char*)&hash, sizeof(hash));
@@ -385,7 +538,7 @@ void FastRandomContext::RandomSeed()
     requires_seed = false;
 }
 
-uint256 FastRandomContext::rand256()
+uint256 FastRandomContext::rand256() noexcept
 {
     if (bytebuf_size < 32) {
         FillByteBuffer();
@@ -406,7 +559,7 @@ std::vector<unsigned char> FastRandomContext::randbytes(size_t len)
     return ret;
 }
 
-FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
+FastRandomContext::FastRandomContext(const uint256& seed) noexcept : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
 {
     rng.SetKey(seed.begin(), 32);
 }
@@ -449,13 +602,15 @@ bool Random_SanityCheck()
     if (stop == start) return false;
 
     // We called GetPerformanceCounter. Use it as entropy.
-    RAND_add((const unsigned char*)&start, sizeof(start), 1);
-    RAND_add((const unsigned char*)&stop, sizeof(stop), 1);
+    CSHA512 to_add;
+    to_add.Write((const unsigned char*)&start, sizeof(start));
+    to_add.Write((const unsigned char*)&stop, sizeof(stop));
+    GetRNGState().MixExtract(nullptr, 0, std::move(to_add), false);
 
     return true;
 }
 
-FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
+FastRandomContext::FastRandomContext(bool fDeterministic) noexcept : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
 {
     if (!fDeterministic) {
         return;
@@ -480,5 +635,8 @@ FastRandomContext& FastRandomContext::operator=(FastRandomContext&& from) noexce
 
 void RandomInit()
 {
-    RDRandInit();
+    // Invoke RNG code to trigger initialization (if not already performed)
+    ProcRand(nullptr, 0, RNGLevel::FAST);
+
+    ReportHardwareRand();
 }