Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto 2 : // Copyright (c) 2009-2018 The Bitcoin developers 3 : // Copyright (c) 2019-2021 The PIVX Core developers 4 : // Distributed under the MIT/X11 software license, see the accompanying 5 : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 6 : 7 : #ifndef PIVX_RANDOM_H 8 : #define PIVX_RANDOM_H 9 : 10 : #include "crypto/chacha20.h" 11 : #include "crypto/common.h" 12 : #include "uint256.h" 13 : 14 : #include <stdint.h> 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 : uint64_t GetRand(uint64_t nMax) noexcept; 71 : int GetRandInt(int nMax) noexcept; 72 : uint256 GetRandHash() noexcept; 73 : 74 : bool GetRandBool(double rate) noexcept; 75 : 76 : /** 77 : * Gather entropy from various sources, feed it into the internal PRNG, and 78 : * generate random data using it. 79 : * 80 : * This function will cause failure whenever the OS RNG fails. 81 : * 82 : * Thread-safe. 83 : */ 84 : void GetStrongRandBytes(unsigned char* buf, int num) noexcept; 85 : 86 : /** 87 : * Gather entropy from various expensive sources, and feed them to the PRNG state. 88 : * 89 : * Thread-safe. 90 : */ 91 : void RandAddPeriodic() noexcept; 92 : 93 : /** 94 : * Gathers entropy from the low bits of the time at which events occur. Should 95 : * be called with a uint32_t describing the event at the time an event occurs. 96 : * 97 : * Thread-safe. 98 : */ 99 : void RandAddEvent(const uint32_t event_info) noexcept; 100 : 101 : /** 102 : * Fast randomness source. This is seeded once with secure random data, but 103 : * is completely deterministic and does not gather more entropy after that. 104 : * 105 : * This class is not thread-safe. 106 : */ 107 : class FastRandomContext { 108 : private: 109 : bool requires_seed{false}; 110 : ChaCha20 rng; 111 : 112 : unsigned char bytebuf[64]; 113 : int bytebuf_size{0}; 114 : 115 : uint64_t bitbuf{0}; 116 : int bitbuf_size{0}; 117 : 118 : void RandomSeed(); 119 : 120 14835931 : void FillByteBuffer() 121 : { 122 14835931 : if (requires_seed) { 123 2566073 : RandomSeed(); 124 : } 125 14835931 : rng.Keystream(bytebuf, sizeof(bytebuf)); 126 14835931 : bytebuf_size = sizeof(bytebuf); 127 14835931 : } 128 : 129 96493048 : void FillBitBuffer() 130 : { 131 192986516 : bitbuf = rand64(); 132 96493048 : bitbuf_size = 64; 133 96493048 : } 134 : 135 : public: 136 : explicit FastRandomContext(bool fDeterministic = false) noexcept; 137 : 138 : /** Initialize with explicit seed (only for testing) */ 139 : explicit FastRandomContext(const uint256& seed) noexcept; 140 : 141 : // Do not permit copying a FastRandomContext (move it, or create a new one to get reseeded). 142 : FastRandomContext(const FastRandomContext&) = delete; 143 : FastRandomContext(FastRandomContext&&) = delete; 144 : FastRandomContext& operator=(const FastRandomContext&) = delete; 145 : 146 : /** Move a FastRandomContext. If the original one is used again, it will be reseeded. */ 147 : FastRandomContext& operator=(FastRandomContext&& from) noexcept; 148 : 149 : /** Generate a random 64-bit integer. */ 150 99083130 : uint64_t rand64() noexcept 151 : { 152 98991508 : if (bytebuf_size < 8) FillByteBuffer(); 153 2590069 : uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size); 154 99083130 : bytebuf_size -= 8; 155 98984846 : return ret; 156 : } 157 : 158 : /** Generate a random (bits)-bit integer. */ 159 1023910481 : uint64_t randbits(int bits) noexcept { 160 1023910481 : if (bits == 0) { 161 : return 0; 162 1023839608 : } else if (bits > 32) { 163 5087808 : return rand64() >> (64 - bits); 164 : } else { 165 1021250165 : if (bitbuf_size < bits) FillBitBuffer(); 166 1021250165 : uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits)); 167 1021250165 : bitbuf >>= bits; 168 1021250165 : bitbuf_size -= bits; 169 1021250165 : return ret; 170 : } 171 : } 172 : 173 : /** Generate a random integer in the range [0..range). */ 174 4644056 : uint64_t randrange(uint64_t range) noexcept 175 : { 176 7774986 : --range; 177 7524588 : int bits = CountBits(range); 178 8634507 : while (true) { 179 8634507 : uint64_t ret = randbits(bits); 180 8634507 : if (ret <= range) return ret; 181 : } 182 : } 183 : 184 : /** Generate random bytes. */ 185 : std::vector<unsigned char> randbytes(size_t len); 186 : 187 : /** Generate a random 16-bit integer. */ 188 2 : uint16_t rand16() { return randbits(16); } 189 : 190 : /** Generate a random 32-bit integer. */ 191 16890456 : uint32_t rand32() noexcept { return randbits(32); } 192 : 193 : /** generate a random uint256. */ 194 : uint256 rand256() noexcept; 195 : 196 : /** Generate a random boolean. */ 197 343722702 : bool randbool() noexcept { return randbits(1); } 198 : 199 : // Compatibility with the C++11 UniformRandomBitGenerator concept 200 : typedef uint64_t result_type; 201 : static constexpr uint64_t min() { return 0; } 202 : static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); } 203 674 : inline uint64_t operator()() noexcept { return rand64(); } 204 : }; 205 : 206 : /** More efficient than using std::shuffle on a FastRandomContext. 207 : * 208 : * This is more efficient as std::shuffle will consume entropy in groups of 209 : * 64 bits at the time and throw away most. 210 : * 211 : * This also works around a bug in libstdc++ std::shuffle that may cause 212 : * type::operator=(type&&) to be invoked on itself, which the library's 213 : * debug mode detects and panics on. This is a known issue, see 214 : * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle 215 : */ 216 : template<typename I, typename R> 217 46299 : void Shuffle(I first, I last, R&& rng) 218 : { 219 1058151 : while (first != last) { 220 1011852 : size_t j = rng.randrange(last - first); 221 1011852 : if (j) { 222 : using std::swap; 223 905930 : swap(*first, *(first + j)); 224 : } 225 1046151 : ++first; 226 : } 227 46299 : } 228 : 229 : /* Number of random bytes returned by GetOSRand. 230 : * When changing this constant make sure to change all call sites, and make 231 : * sure that the underlying OS APIs for all platforms support the number. 232 : * (many cap out at 256 bytes). 233 : */ 234 : static const ssize_t NUM_OS_RANDOM_BYTES = 32; 235 : 236 : /** Get 32 bytes of system entropy. Do not use this in application code: use 237 : * GetStrongRandBytes instead. 238 : */ 239 : void GetOSRand(unsigned char *ent32); 240 : 241 : /** Check that OS randomness is available and returning the requested number 242 : * of bytes. 243 : */ 244 : bool Random_SanityCheck(); 245 : 246 : /** 247 : * Initialize global RNG state and log any CPU features that are used. 248 : * 249 : * Calling this function is optional. RNG state will be initialized when first 250 : * needed if it is not called. 251 : */ 252 : void RandomInit(); 253 : 254 : #endif // PIVX_RANDOM_H