Branch data Line data Source code
1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : : // Copyright (c) 2009-2022 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 <span.h>
12 : : #include <uint256.h>
13 : :
14 : : #include <cassert>
15 : : #include <chrono>
16 : : #include <cstdint>
17 : : #include <limits>
18 : : #include <vector>
19 : :
20 : : /**
21 : : * Overall design of the RNG and entropy sources.
22 : : *
23 : : * We maintain a single global 256-bit RNG state for all high-quality randomness.
24 : : * The following (classes of) functions interact with that state by mixing in new
25 : : * entropy, and optionally extracting random output from it:
26 : : *
27 : : * - The GetRand*() class of functions, as well as construction of FastRandomContext objects,
28 : : * perform 'fast' seeding, consisting of mixing in:
29 : : * - A stack pointer (indirectly committing to calling thread and call stack)
30 : : * - A high-precision timestamp (rdtsc when available, c++ high_resolution_clock otherwise)
31 : : * - 64 bits from the hardware RNG (rdrand) when available.
32 : : * These entropy sources are very fast, and only designed to protect against situations
33 : : * where a VM state restore/copy results in multiple systems with the same randomness.
34 : : * FastRandomContext on the other hand does not protect against this once created, but
35 : : * is even faster (and acceptable to use inside tight loops).
36 : : *
37 : : * - The GetStrongRand*() class of function perform 'slow' seeding, including everything
38 : : * that fast seeding includes, but additionally:
39 : : * - OS entropy (/dev/urandom, getrandom(), ...). The application will terminate if
40 : : * this entropy source fails.
41 : : * - Another high-precision timestamp (indirectly committing to a benchmark of all the
42 : : * previous sources).
43 : : * These entropy sources are slower, but designed to make sure the RNG state contains
44 : : * fresh data that is unpredictable to attackers.
45 : : *
46 : : * - RandAddPeriodic() seeds everything that fast seeding includes, but additionally:
47 : : * - A high-precision timestamp
48 : : * - Dynamic environment data (performance monitoring, ...)
49 : : * - Strengthen the entropy for 10 ms using repeated SHA512.
50 : : * This is run once every minute.
51 : : *
52 : : * On first use of the RNG (regardless of what function is called first), all entropy
53 : : * sources used in the 'slow' seeder are included, but also:
54 : : * - 256 bits from the hardware RNG (rdseed or rdrand) when available.
55 : : * - Dynamic environment data (performance monitoring, ...)
56 : : * - Static environment data
57 : : * - Strengthen the entropy for 100 ms using repeated SHA512.
58 : : *
59 : : * When mixing in new entropy, H = SHA512(entropy || old_rng_state) is computed, and
60 : : * (up to) the first 32 bytes of H are produced as output, while the last 32 bytes
61 : : * become the new RNG state.
62 : : */
63 : :
64 : : /**
65 : : * Generate random data via the internal PRNG.
66 : : *
67 : : * These functions are designed to be fast (sub microsecond), but do not necessarily
68 : : * meaningfully add entropy to the PRNG state.
69 : : *
70 : : * Thread-safe.
71 : : */
72 : : void GetRandBytes(Span<unsigned char> bytes) noexcept;
73 : : /** Generate a uniform random integer in the range [0..range). Precondition: range > 0 */
74 : : uint64_t GetRandInternal(uint64_t nMax) noexcept;
75 : : /** Generate a uniform random integer of type T in the range [0..nMax)
76 : : * nMax defaults to std::numeric_limits<T>::max()
77 : : * Precondition: nMax > 0, T is an integral type, no larger than uint64_t
78 : : */
79 : : template<typename T>
80 : 0 : T GetRand(T nMax=std::numeric_limits<T>::max()) noexcept {
81 : : static_assert(std::is_integral<T>(), "T must be integral");
82 : : static_assert(std::numeric_limits<T>::max() <= std::numeric_limits<uint64_t>::max(), "GetRand only supports up to uint64_t");
83 : 0 : return T(GetRandInternal(nMax));
84 : : }
85 : : /** Generate a uniform random duration in the range [0..max). Precondition: max.count() > 0 */
86 : : template <typename D>
87 : 0 : D GetRandomDuration(typename std::common_type<D>::type max) noexcept
88 : : // Having the compiler infer the template argument from the function argument
89 : : // is dangerous, because the desired return value generally has a different
90 : : // type than the function argument. So std::common_type is used to force the
91 : : // call site to specify the type of the return value.
92 : : {
93 [ # # ][ # # ]: 0 : assert(max.count() > 0);
94 [ # # ][ # # ]: 0 : return D{GetRand(max.count())};
95 : : };
96 : : constexpr auto GetRandMicros = GetRandomDuration<std::chrono::microseconds>;
97 : : constexpr auto GetRandMillis = GetRandomDuration<std::chrono::milliseconds>;
98 : :
99 : : /**
100 : : * Return a timestamp in the future sampled from an exponential distribution
101 : : * (https://en.wikipedia.org/wiki/Exponential_distribution). This distribution
102 : : * is memoryless and should be used for repeated network events (e.g. sending a
103 : : * certain type of message) to minimize leaking information to observers.
104 : : *
105 : : * The probability of an event occurring before time x is 1 - e^-(x/a) where a
106 : : * is the average interval between events.
107 : : * */
108 : : std::chrono::microseconds GetExponentialRand(std::chrono::microseconds now, std::chrono::seconds average_interval);
109 : :
110 : : uint256 GetRandHash() noexcept;
111 : :
112 : : /**
113 : : * Gather entropy from various sources, feed it into the internal PRNG, and
114 : : * generate random data using it.
115 : : *
116 : : * This function will cause failure whenever the OS RNG fails.
117 : : *
118 : : * Thread-safe.
119 : : */
120 : : void GetStrongRandBytes(Span<unsigned char> bytes) noexcept;
121 : :
122 : : /**
123 : : * Gather entropy from various expensive sources, and feed them to the PRNG state.
124 : : *
125 : : * Thread-safe.
126 : : */
127 : : void RandAddPeriodic() noexcept;
128 : :
129 : : /**
130 : : * Gathers entropy from the low bits of the time at which events occur. Should
131 : : * be called with a uint32_t describing the event at the time an event occurs.
132 : : *
133 : : * Thread-safe.
134 : : */
135 : : void RandAddEvent(const uint32_t event_info) noexcept;
136 : :
137 : : /**
138 : : * Fast randomness source. This is seeded once with secure random data, but
139 : : * is completely deterministic and does not gather more entropy after that.
140 : : *
141 : : * This class is not thread-safe.
142 : : */
143 : 0 : class FastRandomContext
144 : : {
145 : : private:
146 : : bool requires_seed;
147 : : ChaCha20 rng;
148 : :
149 : : uint64_t bitbuf;
150 : : int bitbuf_size;
151 : :
152 : : void RandomSeed();
153 : :
154 : 0 : void FillBitBuffer()
155 : : {
156 : 0 : bitbuf = rand64();
157 : 0 : bitbuf_size = 64;
158 : 0 : }
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 : 0 : uint64_t rand64() noexcept
176 : : {
177 [ # # ][ # # ]: 0 : if (requires_seed) RandomSeed();
178 : : std::array<std::byte, 8> buf;
179 [ # # ]: 0 : rng.Keystream(buf);
180 [ # # ][ # # ]: 0 : return ReadLE64(UCharCast(buf.data()));
181 : : }
182 : :
183 : : /** Generate a random (bits)-bit integer. */
184 : 0 : uint64_t randbits(int bits) noexcept
185 : : {
186 [ # # ]: 0 : if (bits == 0) {
187 : 0 : return 0;
188 [ # # ]: 0 : } else if (bits > 32) {
189 : 0 : return rand64() >> (64 - bits);
190 : : } else {
191 [ # # ][ # # ]: 0 : if (bitbuf_size < bits) FillBitBuffer();
192 : 0 : uint64_t ret = bitbuf & (~uint64_t{0} >> (64 - bits));
193 : 0 : bitbuf >>= bits;
194 : 0 : bitbuf_size -= bits;
195 : 0 : return ret;
196 : : }
197 : 0 : }
198 : :
199 : : /** Generate a random integer in the range [0..range).
200 : : * Precondition: range > 0.
201 : : */
202 : 0 : uint64_t randrange(uint64_t range) noexcept
203 : : {
204 [ # # ]: 0 : assert(range);
205 : 0 : --range;
206 [ # # ]: 0 : int bits = CountBits(range);
207 : 0 : while (true) {
208 : 0 : uint64_t ret = randbits(bits);
209 [ # # ]: 0 : if (ret <= range) return ret;
210 : : }
211 : : }
212 : :
213 : : /** Generate random bytes. */
214 : : template <typename B = unsigned char>
215 : : std::vector<B> randbytes(size_t len);
216 : :
217 : : /** Fill a byte Span with random bytes. */
218 : : void fillrand(Span<std::byte> output);
219 : :
220 : : /** Generate a random 32-bit integer. */
221 : 0 : uint32_t rand32() noexcept { return randbits(32); }
222 : :
223 : : /** generate a random uint256. */
224 : : uint256 rand256() noexcept;
225 : :
226 : : /** Generate a random boolean. */
227 : 0 : bool randbool() noexcept { return randbits(1); }
228 : :
229 : : /** Return the time point advanced by a uniform random duration. */
230 : : template <typename Tp>
231 : 0 : Tp rand_uniform_delay(const Tp& time, typename Tp::duration range)
232 : : {
233 : 0 : return time + rand_uniform_duration<Tp>(range);
234 : : }
235 : :
236 : : /** Generate a uniform random duration in the range from 0 (inclusive) to range (exclusive). */
237 : : template <typename Chrono>
238 : 0 : typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
239 : : {
240 : : using Dur = typename Chrono::duration;
241 [ # # ][ # # ]: 0 : return range.count() > 0 ? /* interval [0..range) */ Dur{randrange(range.count())} :
[ # # ][ # # ]
242 [ # # ][ # # ]: 0 : range.count() < 0 ? /* interval (range..0] */ -Dur{randrange(-range.count())} :
[ # # ][ # # ]
[ # # ][ # # ]
243 [ # # ][ # # ]: 0 : /* interval [0..0] */ Dur{0};
244 : : };
245 : :
246 : : // Compatibility with the UniformRandomBitGenerator concept
247 : : typedef uint64_t result_type;
248 : 0 : static constexpr uint64_t min() { return 0; }
249 : 0 : static constexpr uint64_t max() { return std::numeric_limits<uint64_t>::max(); }
250 : 0 : inline uint64_t operator()() noexcept { return rand64(); }
251 : : };
252 : :
253 : : /** More efficient than using std::shuffle on a FastRandomContext.
254 : : *
255 : : * This is more efficient as std::shuffle will consume entropy in groups of
256 : : * 64 bits at the time and throw away most.
257 : : *
258 : : * This also works around a bug in libstdc++ std::shuffle that may cause
259 : : * type::operator=(type&&) to be invoked on itself, which the library's
260 : : * debug mode detects and panics on. This is a known issue, see
261 : : * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
262 : : */
263 : : template <typename I, typename R>
264 : 0 : void Shuffle(I first, I last, R&& rng)
265 : : {
266 [ # # ][ # # ]: 0 : while (first != last) {
[ # # ][ # # ]
267 : 0 : size_t j = rng.randrange(last - first);
268 [ # # ][ # # ]: 0 : if (j) {
[ # # ][ # # ]
269 : : using std::swap;
270 : 0 : swap(*first, *(first + j));
271 : 0 : }
272 : 0 : ++first;
273 : : }
274 : 0 : }
275 : :
276 : : /* Number of random bytes returned by GetOSRand.
277 : : * When changing this constant make sure to change all call sites, and make
278 : : * sure that the underlying OS APIs for all platforms support the number.
279 : : * (many cap out at 256 bytes).
280 : : */
281 : : static const int NUM_OS_RANDOM_BYTES = 32;
282 : :
283 : : /** Get 32 bytes of system entropy. Do not use this in application code: use
284 : : * GetStrongRandBytes instead.
285 : : */
286 : : void GetOSRand(unsigned char* ent32);
287 : :
288 : : /** Check that OS randomness is available and returning the requested number
289 : : * of bytes.
290 : : */
291 : : bool Random_SanityCheck();
292 : :
293 : : /**
294 : : * Initialize global RNG state and log any CPU features that are used.
295 : : *
296 : : * Calling this function is optional. RNG state will be initialized when first
297 : : * needed if it is not called.
298 : : */
299 : : void RandomInit();
300 : :
301 : : #endif // BITCOIN_RANDOM_H
|
