Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2020 The Bitcoin Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #ifndef BITCOIN_RANDOM_H
       7             : #define BITCOIN_RANDOM_H
       8             : 
       9             : #include <crypto/chacha20.h>
      10             : #include <crypto/common.h>
      11             : #include <uint256.h>
      12             : 
      13             : #include <chrono> // For std::chrono::microseconds
      14             : #include <cstdint>
      15             : #include <limits>
      16             : 
      17             : /**
      18             :  * Overall design of the RNG and entropy sources.
      19             :  *
      20             :  * We maintain a single global 256-bit RNG state for all high-quality randomness.
      21             :  * The following (classes of) functions interact with that state by mixing in new
      22             :  * entropy, and optionally extracting random output from it:
      23             :  *
      24             :  * - The GetRand*() class of functions, as well as construction of FastRandomContext objects,
      25             :  *   perform 'fast' seeding, consisting of mixing in:
      26             :  *   - A stack pointer (indirectly committing to calling thread and call stack)
      27             :  *   - A high-precision timestamp (rdtsc when available, c++ high_resolution_clock otherwise)
      28             :  *   - 64 bits from the hardware RNG (rdrand) when available.
      29             :  *   These entropy sources are very fast, and only designed to protect against situations
      30             :  *   where a VM state restore/copy results in multiple systems with the same randomness.
      31             :  *   FastRandomContext on the other hand does not protect against this once created, but
      32             :  *   is even faster (and acceptable to use inside tight loops).
      33             :  *
      34             :  * - The GetStrongRand*() class of function perform 'slow' seeding, including everything
      35             :  *   that fast seeding includes, but additionally:
      36             :  *   - OS entropy (/dev/urandom, getrandom(), ...). The application will terminate if
      37             :  *     this entropy source fails.
      38             :  *   - Another high-precision timestamp (indirectly committing to a benchmark of all the
      39             :  *     previous sources).
      40             :  *   These entropy sources are slower, but designed to make sure the RNG state contains
      41             :  *   fresh data that is unpredictable to attackers.
      42             :  *
      43             :  * - RandAddPeriodic() seeds everything that fast seeding includes, but additionally:
      44             :  *   - A high-precision timestamp
      45             :  *   - Dynamic environment data (performance monitoring, ...)
      46             :  *   - Strengthen the entropy for 10 ms using repeated SHA512.
      47             :  *   This is run once every minute.
      48             :  *
      49             :  * On first use of the RNG (regardless of what function is called first), all entropy
      50             :  * sources used in the 'slow' seeder are included, but also:
      51             :  * - 256 bits from the hardware RNG (rdseed or rdrand) when available.
      52             :  * - Dynamic environment data (performance monitoring, ...)
      53             :  * - Static environment data
      54             :  * - Strengthen the entropy for 100 ms using repeated SHA512.
      55             :  *
      56             :  * When mixing in new entropy, H = SHA512(entropy || old_rng_state) is computed, and
      57             :  * (up to) the first 32 bytes of H are produced as output, while the last 32 bytes
      58             :  * become the new RNG state.
      59             : */
      60             : 
      61             : /**
      62             :  * Generate random data via the internal PRNG.
      63             :  *
      64             :  * These functions are designed to be fast (sub microsecond), but do not necessarily
      65             :  * meaningfully add entropy to the PRNG state.
      66             :  *
      67             :  * Thread-safe.
      68             :  */
      69             : void GetRandBytes(unsigned char* buf, int num) noexcept;
      70             : /** Generate a uniform random integer in the range [0..range). Precondition: range > 0 */
      71             : uint64_t GetRand(uint64_t nMax) noexcept;
      72             : /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */
      73             : template <typename D>
      74        2769 : D GetRandomDuration(typename std::common_type<D>::type max) noexcept
      75             : // Having the compiler infer the template argument from the function argument
      76             : // is dangerous, because the desired return value generally has a different
      77             : // type than the function argument. So std::common_type is used to force the
      78             : // call site to specify the type of the return value.
      79             : {
      80        2769 :     assert(max.count() > 0);
      81        2769 :     return D{GetRand(max.count())};
      82           0 : };
      83             : constexpr auto GetRandMicros = GetRandomDuration<std::chrono::microseconds>;
      84             : constexpr auto GetRandMillis = GetRandomDuration<std::chrono::milliseconds>;
      85             : int GetRandInt(int nMax) noexcept;
      86             : uint256 GetRandHash() noexcept;
      87             : 
      88             : /**
      89             :  * Gather entropy from various sources, feed it into the internal PRNG, and
      90             :  * generate random data using it.
      91             :  *
      92             :  * This function will cause failure whenever the OS RNG fails.
      93             :  *
      94             :  * Thread-safe.
      95             :  */
      96             : void GetStrongRandBytes(unsigned char* buf, int num) noexcept;
      97             : 
      98             : /**
      99             :  * Gather entropy from various expensive sources, and feed them to the PRNG state.
     100             :  *
     101             :  * Thread-safe.
     102             :  */
     103             : void RandAddPeriodic() noexcept;
     104             : 
     105             : /**
     106             :  * Gathers entropy from the low bits of the time at which events occur. Should
     107             :  * be called with a uint32_t describing the event at the time an event occurs.
     108             :  *
     109             :  * Thread-safe.
     110             :  */
     111             : void RandAddEvent(const uint32_t event_info) noexcept;
     112             : 
     113             : /**
     114             :  * Fast randomness source. This is seeded once with secure random data, but
     115             :  * is completely deterministic and does not gather more entropy after that.
     116             :  *
     117             :  * This class is not thread-safe.
     118             :  */
     119             : class FastRandomContext
     120             : {
     121             : private:
     122             :     bool requires_seed;
     123             :     ChaCha20 rng;
     124             : 
     125             :     unsigned char bytebuf[64];
     126             :     int bytebuf_size;
     127             : 
     128             :     uint64_t bitbuf;
     129             :     int bitbuf_size;
     130             : 
     131             :     void RandomSeed();
     132             : 
     133     3327326 :     void FillByteBuffer()
     134             :     {
     135     3327326 :         if (requires_seed) {
     136     1048556 :             RandomSeed();
     137     1048556 :         }
     138     3327326 :         rng.Keystream(bytebuf, sizeof(bytebuf));
     139     3327326 :         bytebuf_size = sizeof(bytebuf);
     140     3327326 :     }
     141             : 
     142    15589183 :     void FillBitBuffer()
     143             :     {
     144    15589183 :         bitbuf = rand64();
     145    15589183 :         bitbuf_size = 64;
     146    15589183 :     }
     147             : 
     148             : public:
     149             :     explicit FastRandomContext(bool fDeterministic = false) noexcept;
     150             : 
     151             :     /** Initialize with explicit seed (only for testing) */
     152             :     explicit FastRandomContext(const uint256& seed) noexcept;
     153             : 
     154             :     // Do not permit copying a FastRandomContext (move it, or create a new one to get reseeded).
     155             :     FastRandomContext(const FastRandomContext&) = delete;
     156             :     FastRandomContext(FastRandomContext&&) = delete;
     157             :     FastRandomContext& operator=(const FastRandomContext&) = delete;
     158             : 
     159             :     /** Move a FastRandomContext. If the original one is used again, it will be reseeded. */
     160             :     FastRandomContext& operator=(FastRandomContext&& from) noexcept;
     161             : 
     162             :     /** Generate a random 64-bit integer. */
     163    16661931 :     uint64_t rand64() noexcept
     164             :     {
     165    16661931 :         if (bytebuf_size < 8) FillByteBuffer();
     166    16661931 :         uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
     167    16661931 :         bytebuf_size -= 8;
     168    16661931 :         return ret;
     169           0 :     }
     170             : 
     171             :     /** Generate a random (bits)-bit integer. */
     172   395402588 :     uint64_t randbits(int bits) noexcept
     173             :     {
     174   395402588 :         if (bits == 0) {
     175       85544 :             return 0;
     176   395317044 :         } else if (bits > 32) {
     177     1067099 :             return rand64() >> (64 - bits);
     178             :         } else {
     179   394249945 :             if (bitbuf_size < bits) FillBitBuffer();
     180   394249945 :             uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
     181   394249945 :             bitbuf >>= bits;
     182   394249945 :             bitbuf_size -= bits;
     183             :             return ret;
     184             :         }
     185   395402587 :     }
     186             : 
     187             :     /** Generate a random integer in the range [0..range).
     188             :      * Precondition: range > 0.
     189             :      */
     190     7913505 :     uint64_t randrange(uint64_t range) noexcept
     191             :     {
     192     7913505 :         assert(range);
     193     7913505 :         --range;
     194     7913505 :         int bits = CountBits(range);
     195     7913505 :         while (true) {
     196    11619076 :             uint64_t ret = randbits(bits);
     197    11619076 :             if (ret <= range) return ret;
     198     3705571 :         }
     199     7913504 :     }
     200             : 
     201             :     /** Generate random bytes. */
     202             :     std::vector<unsigned char> randbytes(size_t len);
     203             : 
     204             :     /** Generate a random 32-bit integer. */
     205    16663243 :     uint32_t rand32() noexcept { return randbits(32); }
     206             : 
     207             :     /** generate a random uint256. */
     208             :     uint256 rand256() noexcept;
     209             : 
     210             :     /** Generate a random boolean. */
     211   361612304 :     bool randbool() noexcept { return randbits(1); }
     212             : 
     213             :     // Compatibility with the C++11 UniformRandomBitGenerator concept
     214             :     typedef uint64_t result_type;
     215             :     static constexpr uint64_t min() { return 0; }
     216             :     static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
     217        5613 :     inline uint64_t operator()() noexcept { return rand64(); }
     218             : };
     219             : 
     220             : /** More efficient than using std::shuffle on a FastRandomContext.
     221             :  *
     222             :  * This is more efficient as std::shuffle will consume entropy in groups of
     223             :  * 64 bits at the time and throw away most.
     224             :  *
     225             :  * This also works around a bug in libstdc++ std::shuffle that may cause
     226             :  * type::operator=(type&&) to be invoked on itself, which the library's
     227             :  * debug mode detects and panics on. This is a known issue, see
     228             :  * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
     229             :  */
     230             : template <typename I, typename R>
     231       25663 : void Shuffle(I first, I last, R&& rng)
     232             : {
     233     1011018 :     while (first != last) {
     234      985355 :         size_t j = rng.randrange(last - first);
     235      985355 :         if (j) {
     236             :             using std::swap;
     237      914571 :             swap(*first, *(first + j));
     238      914571 :         }
     239      985355 :         ++first;
     240             :     }
     241       25663 : }
     242             : 
     243             : /* Number of random bytes returned by GetOSRand.
     244             :  * When changing this constant make sure to change all call sites, and make
     245             :  * sure that the underlying OS APIs for all platforms support the number.
     246             :  * (many cap out at 256 bytes).
     247             :  */
     248             : static const int NUM_OS_RANDOM_BYTES = 32;
     249             : 
     250             : /** Get 32 bytes of system entropy. Do not use this in application code: use
     251             :  * GetStrongRandBytes instead.
     252             :  */
     253             : void GetOSRand(unsigned char* ent32);
     254             : 
     255             : /** Check that OS randomness is available and returning the requested number
     256             :  * of bytes.
     257             :  */
     258             : bool Random_SanityCheck();
     259             : 
     260             : /**
     261             :  * Initialize global RNG state and log any CPU features that are used.
     262             :  *
     263             :  * Calling this function is optional. RNG state will be initialized when first
     264             :  * needed if it is not called.
     265             :  */
     266             : void RandomInit();
     267             : 
     268             : #endif // BITCOIN_RANDOM_H