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>
GetRandomDuration(typename std::common_type<D>::type max)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 {
80 assert(max.count() > 0);
81 return D{GetRand(max.count())};
82 };
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
FillByteBuffer()133 void FillByteBuffer()
134 {
135 if (requires_seed) {
136 RandomSeed();
137 }
138 rng.Keystream(bytebuf, sizeof(bytebuf));
139 bytebuf_size = sizeof(bytebuf);
140 }
141
FillBitBuffer()142 void FillBitBuffer()
143 {
144 bitbuf = rand64();
145 bitbuf_size = 64;
146 }
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. */
rand64()163 uint64_t rand64() noexcept
164 {
165 if (bytebuf_size < 8) FillByteBuffer();
166 uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
167 bytebuf_size -= 8;
168 return ret;
169 }
170
171 /** Generate a random (bits)-bit integer. */
randbits(int bits)172 uint64_t randbits(int bits) noexcept
173 {
174 if (bits == 0) {
175 return 0;
176 } else if (bits > 32) {
177 return rand64() >> (64 - bits);
178 } else {
179 if (bitbuf_size < bits) FillBitBuffer();
180 uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
181 bitbuf >>= bits;
182 bitbuf_size -= bits;
183 return ret;
184 }
185 }
186
187 /** Generate a random integer in the range [0..range).
188 * Precondition: range > 0.
189 */
randrange(uint64_t range)190 uint64_t randrange(uint64_t range) noexcept
191 {
192 assert(range);
193 --range;
194 int bits = CountBits(range);
195 while (true) {
196 uint64_t ret = randbits(bits);
197 if (ret <= range) return ret;
198 }
199 }
200
201 /** Generate random bytes. */
202 std::vector<unsigned char> randbytes(size_t len);
203
204 /** Generate a random 32-bit integer. */
rand32()205 uint32_t rand32() noexcept { return randbits(32); }
206
207 /** generate a random uint256. */
208 uint256 rand256() noexcept;
209
210 /** Generate a random boolean. */
randbool()211 bool randbool() noexcept { return randbits(1); }
212
213 // Compatibility with the C++11 UniformRandomBitGenerator concept
214 typedef uint64_t result_type;
min()215 static constexpr uint64_t min() { return 0; }
max()216 static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
operator()217 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>
Shuffle(I first,I last,R && rng)231 void Shuffle(I first, I last, R&& rng)
232 {
233 while (first != last) {
234 size_t j = rng.randrange(last - first);
235 if (j) {
236 using std::swap;
237 swap(*first, *(first + j));
238 }
239 ++first;
240 }
241 }
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
269