Branch data 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>
# 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 : : 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 : 2110 : {
# 80 : 2110 : assert(max.count() > 0);
# 81 : 0 : return D{GetRand(max.count())};
# 82 : 2110 : };
# 83 : : constexpr auto GetRandMicros = GetRandomDuration<std::chrono::microseconds>;
# 84 : : constexpr auto GetRandMillis = GetRandomDuration<std::chrono::milliseconds>;
# 85 : :
# 86 : : /**
# 87 : : * Return a timestamp in the future sampled from an exponential distribution
# 88 : : * (https://en.wikipedia.org/wiki/Exponential_distribution). This distribution
# 89 : : * is memoryless and should be used for repeated network events (e.g. sending a
# 90 : : * certain type of message) to minimize leaking information to observers.
# 91 : : *
# 92 : : * The probability of an event occurring before time x is 1 - e^-(x/a) where a
# 93 : : * is the average interval between events.
# 94 : : * */
# 95 : : std::chrono::microseconds GetExponentialRand(std::chrono::microseconds now, std::chrono::seconds average_interval);
# 96 : :
# 97 : : int GetRandInt(int nMax) noexcept;
# 98 : : uint256 GetRandHash() noexcept;
# 99 : :
# 100 : : /**
# 101 : : * Gather entropy from various sources, feed it into the internal PRNG, and
# 102 : : * generate random data using it.
# 103 : : *
# 104 : : * This function will cause failure whenever the OS RNG fails.
# 105 : : *
# 106 : : * Thread-safe.
# 107 : : */
# 108 : : void GetStrongRandBytes(unsigned char* buf, int num) noexcept;
# 109 : :
# 110 : : /**
# 111 : : * Gather entropy from various expensive sources, and feed them to the PRNG state.
# 112 : : *
# 113 : : * Thread-safe.
# 114 : : */
# 115 : : void RandAddPeriodic() noexcept;
# 116 : :
# 117 : : /**
# 118 : : * Gathers entropy from the low bits of the time at which events occur. Should
# 119 : : * be called with a uint32_t describing the event at the time an event occurs.
# 120 : : *
# 121 : : * Thread-safe.
# 122 : : */
# 123 : : void RandAddEvent(const uint32_t event_info) noexcept;
# 124 : :
# 125 : : /**
# 126 : : * Fast randomness source. This is seeded once with secure random data, but
# 127 : : * is completely deterministic and does not gather more entropy after that.
# 128 : : *
# 129 : : * This class is not thread-safe.
# 130 : : */
# 131 : : class FastRandomContext
# 132 : : {
# 133 : : private:
# 134 : : bool requires_seed;
# 135 : : ChaCha20 rng;
# 136 : :
# 137 : : unsigned char bytebuf[64];
# 138 : : int bytebuf_size;
# 139 : :
# 140 : : uint64_t bitbuf;
# 141 : : int bitbuf_size;
# 142 : :
# 143 : : void RandomSeed();
# 144 : :
# 145 : : void FillByteBuffer()
# 146 : 5593697 : {
# 147 [ + + ]: 5593697 : if (requires_seed) {
# 148 : 1454465 : RandomSeed();
# 149 : 1454465 : }
# 150 : 5593697 : rng.Keystream(bytebuf, sizeof(bytebuf));
# 151 : 5593697 : bytebuf_size = sizeof(bytebuf);
# 152 : 5593697 : }
# 153 : :
# 154 : : void FillBitBuffer()
# 155 : 25254324 : {
# 156 : 25254324 : bitbuf = rand64();
# 157 : 25254324 : bitbuf_size = 64;
# 158 : 25254324 : }
# 159 : :
# 160 : : public:
# 161 : : explicit FastRandomContext(bool fDeterministic = false) noexcept;
# 162 : :
# 163 : : /** Initialize with explicit seed (only for testing) */
# 164 : : explicit FastRandomContext(const uint256& seed) noexcept;
# 165 : :
# 166 : : // Do not permit copying a FastRandomContext (move it, or create a new one to get reseeded).
# 167 : : FastRandomContext(const FastRandomContext&) = delete;
# 168 : : FastRandomContext(FastRandomContext&&) = delete;
# 169 : : FastRandomContext& operator=(const FastRandomContext&) = delete;
# 170 : :
# 171 : : /** Move a FastRandomContext. If the original one is used again, it will be reseeded. */
# 172 : : FastRandomContext& operator=(FastRandomContext&& from) noexcept;
# 173 : :
# 174 : : /** Generate a random 64-bit integer. */
# 175 : : uint64_t rand64() noexcept
# 176 : 27858369 : {
# 177 [ + + ]: 27858369 : if (bytebuf_size < 8) FillByteBuffer();
# 178 : 27858369 : uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
# 179 : 27858369 : bytebuf_size -= 8;
# 180 : 27858369 : return ret;
# 181 : 27858369 : }
# 182 : :
# 183 : : /** Generate a random (bits)-bit integer. */
# 184 : : uint64_t randbits(int bits) noexcept
# 185 : 445537442 : {
# 186 [ + + ]: 445537442 : if (bits == 0) {
# 187 : 450160 : return 0;
# 188 [ + + ]: 445087282 : } else if (bits > 32) {
# 189 : 2592060 : return rand64() >> (64 - bits);
# 190 : 442495222 : } else {
# 191 [ + + ]: 442495222 : if (bitbuf_size < bits) FillBitBuffer();
# 192 : 442495222 : uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
# 193 : 442495222 : bitbuf >>= bits;
# 194 : 442495222 : bitbuf_size -= bits;
# 195 : 442495222 : return ret;
# 196 : 442495222 : }
# 197 : 445537442 : }
# 198 : :
# 199 : : /** Generate a random integer in the range [0..range).
# 200 : : * Precondition: range > 0.
# 201 : : */
# 202 : : uint64_t randrange(uint64_t range) noexcept
# 203 : 17067258 : {
# 204 : 17067258 : assert(range);
# 205 : 0 : --range;
# 206 : 17067258 : int bits = CountBits(range);
# 207 : 24682942 : while (true) {
# 208 : 24682942 : uint64_t ret = randbits(bits);
# 209 [ + + ]: 24682942 : if (ret <= range) return ret;
# 210 : 24682942 : }
# 211 : 17067258 : }
# 212 : :
# 213 : : /** Generate random bytes. */
# 214 : : std::vector<unsigned char> randbytes(size_t len);
# 215 : :
# 216 : : /** Generate a random 32-bit integer. */
# 217 : 33068920 : uint32_t rand32() noexcept { return randbits(32); }
# 218 : :
# 219 : : /** generate a random uint256. */
# 220 : : uint256 rand256() noexcept;
# 221 : :
# 222 : : /** Generate a random boolean. */
# 223 : 380877835 : bool randbool() noexcept { return randbits(1); }
# 224 : :
# 225 : : // Compatibility with the C++11 UniformRandomBitGenerator concept
# 226 : : typedef uint64_t result_type;
# 227 : 0 : static constexpr uint64_t min() { return 0; }
# 228 : 0 : static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
# 229 : 11913 : inline uint64_t operator()() noexcept { return rand64(); }
# 230 : : };
# 231 : :
# 232 : : /** More efficient than using std::shuffle on a FastRandomContext.
# 233 : : *
# 234 : : * This is more efficient as std::shuffle will consume entropy in groups of
# 235 : : * 64 bits at the time and throw away most.
# 236 : : *
# 237 : : * This also works around a bug in libstdc++ std::shuffle that may cause
# 238 : : * type::operator=(type&&) to be invoked on itself, which the library's
# 239 : : * debug mode detects and panics on. This is a known issue, see
# 240 : : * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
# 241 : : */
# 242 : : template <typename I, typename R>
# 243 : : void Shuffle(I first, I last, R&& rng)
# 244 : 264240 : {
# 245 [ + + ][ + + ]: 2176411 : while (first != last) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 246 : 1912171 : size_t j = rng.randrange(last - first);
# 247 [ + + ][ + + ]: 1912171 : if (j) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ - + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 248 : 1534253 : using std::swap;
# 249 : 1534253 : swap(*first, *(first + j));
# 250 : 1534253 : }
# 251 : 1912171 : ++first;
# 252 : 1912171 : }
# 253 : 264240 : }
# 254 : :
# 255 : : /* Number of random bytes returned by GetOSRand.
# 256 : : * When changing this constant make sure to change all call sites, and make
# 257 : : * sure that the underlying OS APIs for all platforms support the number.
# 258 : : * (many cap out at 256 bytes).
# 259 : : */
# 260 : : static const int NUM_OS_RANDOM_BYTES = 32;
# 261 : :
# 262 : : /** Get 32 bytes of system entropy. Do not use this in application code: use
# 263 : : * GetStrongRandBytes instead.
# 264 : : */
# 265 : : void GetOSRand(unsigned char* ent32);
# 266 : :
# 267 : : /** Check that OS randomness is available and returning the requested number
# 268 : : * of bytes.
# 269 : : */
# 270 : : bool Random_SanityCheck();
# 271 : :
# 272 : : /**
# 273 : : * Initialize global RNG state and log any CPU features that are used.
# 274 : : *
# 275 : : * Calling this function is optional. RNG state will be initialized when first
# 276 : : * needed if it is not called.
# 277 : : */
# 278 : : void RandomInit();
# 279 : :
# 280 : : #endif // BITCOIN_RANDOM_H
|
