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 : : #include <bitcoin-build-config.h> // IWYU pragma: keep
7 : :
8 : : #include <random.h>
9 : :
10 : : #include <compat/compat.h>
11 : : #include <compat/cpuid.h>
12 : : #include <crypto/chacha20.h>
13 : : #include <crypto/sha256.h>
14 : : #include <crypto/sha512.h>
15 : : #include <logging.h>
16 : : #include <randomenv.h>
17 : : #include <span.h>
18 : : #include <support/allocators/secure.h>
19 : : #include <support/cleanse.h>
20 : : #include <sync.h>
21 : : #include <util/time.h>
22 : :
23 : : #include <array>
24 : : #include <cmath>
25 : : #include <cstdlib>
26 : : #include <optional>
27 : : #include <thread>
28 : :
29 : : #ifdef WIN32
30 : : #include <windows.h>
31 : : #include <wincrypt.h>
32 : : #else
33 : : #include <fcntl.h>
34 : : #include <sys/time.h>
35 : : #endif
36 : :
37 : : #if defined(HAVE_GETRANDOM) || (defined(HAVE_GETENTROPY_RAND) && defined(__APPLE__))
38 : : #include <sys/random.h>
39 : : #endif
40 : :
41 : : #ifdef HAVE_SYSCTL_ARND
42 : : #include <sys/sysctl.h>
43 : : #endif
44 : : #if defined(HAVE_STRONG_GETAUXVAL) && defined(__aarch64__)
45 : : #include <sys/auxv.h>
46 : : #endif
47 : :
48 : : namespace {
49 : :
50 : : /* Number of random bytes returned by GetOSRand.
51 : : * When changing this constant make sure to change all call sites, and make
52 : : * sure that the underlying OS APIs for all platforms support the number.
53 : : * (many cap out at 256 bytes).
54 : : */
55 : : static const int NUM_OS_RANDOM_BYTES = 32;
56 : :
57 : :
58 : 0 : [[noreturn]] void RandFailure()
59 : : {
60 : 0 : LogError("Failed to read randomness, aborting\n");
61 : 0 : std::abort();
62 : : }
63 : :
64 : 2594621 : inline int64_t GetPerformanceCounter() noexcept
65 : : {
66 : : // Read the hardware time stamp counter when available.
67 : : // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information.
68 : : #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64))
69 : : return __rdtsc();
70 : : #elif !defined(_MSC_VER) && defined(__i386__)
71 : : uint64_t r = 0;
72 : : __asm__ volatile ("rdtsc" : "=A"(r)); // Constrain the r variable to the eax:edx pair.
73 : : return r;
74 : : #elif !defined(_MSC_VER) && (defined(__x86_64__) || defined(__amd64__))
75 : 2594621 : uint64_t r1 = 0, r2 = 0;
76 : 5189242 : __asm__ volatile ("rdtsc" : "=a"(r1), "=d"(r2)); // Constrain r1 to rax and r2 to rdx.
77 : 2594621 : return (r2 << 32) | r1;
78 : : #else
79 : : // Fall back to using standard library clock (usually microsecond or nanosecond precision)
80 : : return std::chrono::high_resolution_clock::now().time_since_epoch().count();
81 : : #endif
82 : : }
83 : :
84 : : #ifdef HAVE_GETCPUID
85 : : bool g_rdrand_supported = false;
86 : : bool g_rdseed_supported = false;
87 : : constexpr uint32_t CPUID_F1_ECX_RDRAND = 0x40000000;
88 : : constexpr uint32_t CPUID_F7_EBX_RDSEED = 0x00040000;
89 : : #ifdef bit_RDRND
90 : : static_assert(CPUID_F1_ECX_RDRAND == bit_RDRND, "Unexpected value for bit_RDRND");
91 : : #endif
92 : : #ifdef bit_RDSEED
93 : : static_assert(CPUID_F7_EBX_RDSEED == bit_RDSEED, "Unexpected value for bit_RDSEED");
94 : : #endif
95 : :
96 : 1156 : void InitHardwareRand()
97 : : {
98 : 1156 : uint32_t eax, ebx, ecx, edx;
99 : 1156 : GetCPUID(1, 0, eax, ebx, ecx, edx);
100 [ + - ]: 1156 : if (ecx & CPUID_F1_ECX_RDRAND) {
101 : 1156 : g_rdrand_supported = true;
102 : : }
103 : 1156 : GetCPUID(7, 0, eax, ebx, ecx, edx);
104 [ + - ]: 1156 : if (ebx & CPUID_F7_EBX_RDSEED) {
105 : 1156 : g_rdseed_supported = true;
106 : : }
107 : 1156 : }
108 : :
109 : 1125 : void ReportHardwareRand()
110 : : {
111 : : // This must be done in a separate function, as InitHardwareRand() may be indirectly called
112 : : // from global constructors, before logging is initialized.
113 [ + - ]: 1125 : if (g_rdseed_supported) {
114 : 1125 : LogPrintf("Using RdSeed as an additional entropy source\n");
115 : : }
116 [ + - ]: 1125 : if (g_rdrand_supported) {
117 : 1125 : LogPrintf("Using RdRand as an additional entropy source\n");
118 : : }
119 : 1125 : }
120 : :
121 : : /** Read 64 bits of entropy using rdrand.
122 : : *
123 : : * Must only be called when RdRand is supported.
124 : : */
125 : 2280674 : uint64_t GetRdRand() noexcept
126 : : {
127 : : // RdRand may very rarely fail. Invoke it up to 10 times in a loop to reduce this risk.
128 : : #ifdef __i386__
129 : : uint8_t ok;
130 : : // Initialize to 0 to silence a compiler warning that r1 or r2 may be used
131 : : // uninitialized. Even if rdrand fails (!ok) it will set the output to 0,
132 : : // but there is no way that the compiler could know that.
133 : : uint32_t r1 = 0, r2 = 0;
134 : : for (int i = 0; i < 10; ++i) {
135 : : __asm__ volatile (".byte 0x0f, 0xc7, 0xf0; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdrand %eax
136 : : if (ok) break;
137 : : }
138 : : for (int i = 0; i < 10; ++i) {
139 : : __asm__ volatile (".byte 0x0f, 0xc7, 0xf0; setc %1" : "=a"(r2), "=q"(ok) :: "cc"); // rdrand %eax
140 : : if (ok) break;
141 : : }
142 : : return (((uint64_t)r2) << 32) | r1;
143 : : #elif defined(__x86_64__) || defined(__amd64__)
144 : 2280674 : uint8_t ok;
145 : 2280674 : uint64_t r1 = 0; // See above why we initialize to 0.
146 [ + - ]: 2280674 : for (int i = 0; i < 10; ++i) {
147 : 2280674 : __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf0; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdrand %rax
148 [ - + ]: 2280674 : if (ok) break;
149 : : }
150 : 2280674 : return r1;
151 : : #else
152 : : #error "RdRand is only supported on x86 and x86_64"
153 : : #endif
154 : : }
155 : :
156 : : /** Read 64 bits of entropy using rdseed.
157 : : *
158 : : * Must only be called when RdSeed is supported.
159 : : */
160 : 4624 : uint64_t GetRdSeed() noexcept
161 : : {
162 : : // RdSeed may fail when the HW RNG is overloaded. Loop indefinitely until enough entropy is gathered,
163 : : // but pause after every failure.
164 : : #ifdef __i386__
165 : : uint8_t ok;
166 : : uint32_t r1, r2;
167 : : do {
168 : : __asm__ volatile (".byte 0x0f, 0xc7, 0xf8; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdseed %eax
169 : : if (ok) break;
170 : : __asm__ volatile ("pause");
171 : : } while(true);
172 : : do {
173 : : __asm__ volatile (".byte 0x0f, 0xc7, 0xf8; setc %1" : "=a"(r2), "=q"(ok) :: "cc"); // rdseed %eax
174 : : if (ok) break;
175 : : __asm__ volatile ("pause");
176 : : } while(true);
177 : : return (((uint64_t)r2) << 32) | r1;
178 : : #elif defined(__x86_64__) || defined(__amd64__)
179 : 4624 : uint8_t ok;
180 : 4624 : uint64_t r1;
181 : 4624 : do {
182 : 4624 : __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf8; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdseed %rax
183 [ - + ]: 4624 : if (ok) break;
184 : 0 : __asm__ volatile ("pause");
185 : : } while(true);
186 : 4624 : return r1;
187 : : #else
188 : : #error "RdSeed is only supported on x86 and x86_64"
189 : : #endif
190 : : }
191 : :
192 : : #elif defined(__aarch64__) && defined(HWCAP2_RNG)
193 : :
194 : : bool g_rndr_supported = false;
195 : :
196 : : void InitHardwareRand()
197 : : {
198 : : if (getauxval(AT_HWCAP2) & HWCAP2_RNG) {
199 : : g_rndr_supported = true;
200 : : }
201 : : }
202 : :
203 : : void ReportHardwareRand()
204 : : {
205 : : // This must be done in a separate function, as InitHardwareRand() may be indirectly called
206 : : // from global constructors, before logging is initialized.
207 : : if (g_rndr_supported) {
208 : : LogPrintf("Using RNDR and RNDRRS as additional entropy sources\n");
209 : : }
210 : : }
211 : :
212 : : /** Read 64 bits of entropy using rndr.
213 : : *
214 : : * Must only be called when RNDR is supported.
215 : : */
216 : : uint64_t GetRNDR() noexcept
217 : : {
218 : : uint8_t ok;
219 : : uint64_t r1;
220 : : do {
221 : : // https://developer.arm.com/documentation/ddi0601/2022-12/AArch64-Registers/RNDR--Random-Number
222 : : __asm__ volatile("mrs %0, s3_3_c2_c4_0; cset %w1, ne;"
223 : : : "=r"(r1), "=r"(ok)::"cc");
224 : : if (ok) break;
225 : : __asm__ volatile("yield");
226 : : } while (true);
227 : : return r1;
228 : : }
229 : :
230 : : /** Read 64 bits of entropy using rndrrs.
231 : : *
232 : : * Must only be called when RNDRRS is supported.
233 : : */
234 : : uint64_t GetRNDRRS() noexcept
235 : : {
236 : : uint8_t ok;
237 : : uint64_t r1;
238 : : do {
239 : : // https://developer.arm.com/documentation/ddi0601/2022-12/AArch64-Registers/RNDRRS--Reseeded-Random-Number
240 : : __asm__ volatile("mrs %0, s3_3_c2_c4_1; cset %w1, ne;"
241 : : : "=r"(r1), "=r"(ok)::"cc");
242 : : if (ok) break;
243 : : __asm__ volatile("yield");
244 : : } while (true);
245 : : return r1;
246 : : }
247 : :
248 : : #else
249 : : /* Access to other hardware random number generators could be added here later,
250 : : * assuming it is sufficiently fast (in the order of a few hundred CPU cycles).
251 : : * Slower sources should probably be invoked separately, and/or only from
252 : : * RandAddPeriodic (which is called once a minute).
253 : : */
254 : : void InitHardwareRand() {}
255 : : void ReportHardwareRand() {}
256 : : #endif
257 : :
258 : : /** Add 64 bits of entropy gathered from hardware to hasher. Do nothing if not supported. */
259 : 2280674 : void SeedHardwareFast(CSHA512& hasher) noexcept {
260 : : #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
261 [ + - ]: 2280674 : if (g_rdrand_supported) {
262 : 2280674 : uint64_t out = GetRdRand();
263 : 2280674 : hasher.Write((const unsigned char*)&out, sizeof(out));
264 : 2280674 : return;
265 : : }
266 : : #elif defined(__aarch64__) && defined(HWCAP2_RNG)
267 : : if (g_rndr_supported) {
268 : : uint64_t out = GetRNDR();
269 : : hasher.Write((const unsigned char*)&out, sizeof(out));
270 : : return;
271 : : }
272 : : #endif
273 : : }
274 : :
275 : : /** Add 256 bits of entropy gathered from hardware to hasher. Do nothing if not supported. */
276 : 1156 : void SeedHardwareSlow(CSHA512& hasher) noexcept {
277 : : #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
278 : : // When we want 256 bits of entropy, prefer RdSeed over RdRand, as it's
279 : : // guaranteed to produce independent randomness on every call.
280 [ + - ]: 1156 : if (g_rdseed_supported) {
281 [ + + ]: 5780 : for (int i = 0; i < 4; ++i) {
282 : 4624 : uint64_t out = GetRdSeed();
283 : 4624 : hasher.Write((const unsigned char*)&out, sizeof(out));
284 : : }
285 : : return;
286 : : }
287 : : // When falling back to RdRand, XOR the result of 1024 results.
288 : : // This guarantees a reseeding occurs between each.
289 [ # # ]: 0 : if (g_rdrand_supported) {
290 [ # # ]: 0 : for (int i = 0; i < 4; ++i) {
291 : 0 : uint64_t out = 0;
292 [ # # ]: 0 : for (int j = 0; j < 1024; ++j) out ^= GetRdRand();
293 : 0 : hasher.Write((const unsigned char*)&out, sizeof(out));
294 : : }
295 : : return;
296 : : }
297 : : #elif defined(__aarch64__) && defined(HWCAP2_RNG)
298 : : if (g_rndr_supported) {
299 : : for (int i = 0; i < 4; ++i) {
300 : : uint64_t out = GetRNDRRS();
301 : : hasher.Write((const unsigned char*)&out, sizeof(out));
302 : : }
303 : : return;
304 : : }
305 : : #endif
306 : : }
307 : :
308 : : /** Use repeated SHA512 to strengthen the randomness in seed32, and feed into hasher. */
309 : 1327 : void Strengthen(const unsigned char (&seed)[32], SteadyClock::duration dur, CSHA512& hasher) noexcept
310 : : {
311 : 1327 : CSHA512 inner_hasher;
312 : 1327 : inner_hasher.Write(seed, sizeof(seed));
313 : :
314 : : // Hash loop
315 : 1327 : unsigned char buffer[64];
316 : 1327 : const auto stop{SteadyClock::now() + dur};
317 : 73850 : do {
318 [ + + ]: 73923850 : for (int i = 0; i < 1000; ++i) {
319 : 73850000 : inner_hasher.Finalize(buffer);
320 : 73850000 : inner_hasher.Reset();
321 : 73850000 : inner_hasher.Write(buffer, sizeof(buffer));
322 : : }
323 : : // Benchmark operation and feed it into outer hasher.
324 : 73850 : int64_t perf = GetPerformanceCounter();
325 : 73850 : hasher.Write((const unsigned char*)&perf, sizeof(perf));
326 [ + + ]: 73850 : } while (SteadyClock::now() < stop);
327 : :
328 : : // Produce output from inner state and feed it to outer hasher.
329 : 1327 : inner_hasher.Finalize(buffer);
330 : 1327 : hasher.Write(buffer, sizeof(buffer));
331 : : // Try to clean up.
332 : 1327 : inner_hasher.Reset();
333 : 1327 : memory_cleanse(buffer, sizeof(buffer));
334 : 1327 : }
335 : :
336 : : #ifndef WIN32
337 : : /** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
338 : : * compatible way to get cryptographic randomness on UNIX-ish platforms.
339 : : */
340 : : [[maybe_unused]] void GetDevURandom(unsigned char *ent32)
341 : : {
342 : : int f = open("/dev/urandom", O_RDONLY);
343 : : if (f == -1) {
344 : : RandFailure();
345 : : }
346 : : int have = 0;
347 : : do {
348 : : ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
349 : : if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
350 : : close(f);
351 : : RandFailure();
352 : : }
353 : : have += n;
354 : : } while (have < NUM_OS_RANDOM_BYTES);
355 : : close(f);
356 : : }
357 : : #endif
358 : :
359 : : /** Get 32 bytes of system entropy. */
360 : 4010 : void GetOSRand(unsigned char *ent32)
361 : : {
362 : : #if defined(WIN32)
363 : : HCRYPTPROV hProvider;
364 : : int ret = CryptAcquireContextW(&hProvider, nullptr, nullptr, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
365 : : if (!ret) {
366 : : RandFailure();
367 : : }
368 : : ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
369 : : if (!ret) {
370 : : RandFailure();
371 : : }
372 : : CryptReleaseContext(hProvider, 0);
373 : : #elif defined(HAVE_GETRANDOM)
374 : : /* Linux. From the getrandom(2) man page:
375 : : * "If the urandom source has been initialized, reads of up to 256 bytes
376 : : * will always return as many bytes as requested and will not be
377 : : * interrupted by signals."
378 : : */
379 [ - + ]: 4010 : if (getrandom(ent32, NUM_OS_RANDOM_BYTES, 0) != NUM_OS_RANDOM_BYTES) {
380 : 0 : RandFailure();
381 : : }
382 : : #elif defined(__OpenBSD__)
383 : : /* OpenBSD. From the arc4random(3) man page:
384 : : "Use of these functions is encouraged for almost all random number
385 : : consumption because the other interfaces are deficient in either
386 : : quality, portability, standardization, or availability."
387 : : The function call is always successful.
388 : : */
389 : : arc4random_buf(ent32, NUM_OS_RANDOM_BYTES);
390 : : #elif defined(HAVE_GETENTROPY_RAND) && defined(__APPLE__)
391 : : if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
392 : : RandFailure();
393 : : }
394 : : #elif defined(HAVE_SYSCTL_ARND)
395 : : /* FreeBSD, NetBSD and similar. It is possible for the call to return less
396 : : * bytes than requested, so need to read in a loop.
397 : : */
398 : : static int name[2] = {CTL_KERN, KERN_ARND};
399 : : int have = 0;
400 : : do {
401 : : size_t len = NUM_OS_RANDOM_BYTES - have;
402 : : if (sysctl(name, std::size(name), ent32 + have, &len, nullptr, 0) != 0) {
403 : : RandFailure();
404 : : }
405 : : have += len;
406 : : } while (have < NUM_OS_RANDOM_BYTES);
407 : : #else
408 : : /* Fall back to /dev/urandom if there is no specific method implemented to
409 : : * get system entropy for this OS.
410 : : */
411 : : GetDevURandom(ent32);
412 : : #endif
413 : 4010 : }
414 : :
415 : : class RNGState {
416 : : Mutex m_mutex;
417 : : /* The RNG state consists of 256 bits of entropy, taken from the output of
418 : : * one operation's SHA512 output, and fed as input to the next one.
419 : : * Carrying 256 bits of entropy should be sufficient to guarantee
420 : : * unpredictability as long as any entropy source was ever unpredictable
421 : : * to an attacker. To protect against situations where an attacker might
422 : : * observe the RNG's state, fresh entropy is always mixed when
423 : : * GetStrongRandBytes is called.
424 : : */
425 : : unsigned char m_state[32] GUARDED_BY(m_mutex) = {0};
426 : : uint64_t m_counter GUARDED_BY(m_mutex) = 0;
427 : : bool m_strongly_seeded GUARDED_BY(m_mutex) = false;
428 : :
429 : : /** If not nullopt, the output of this RNGState is redirected and drawn from here
430 : : * (unless always_use_real_rng is passed to MixExtract). */
431 : : std::optional<ChaCha20> m_deterministic_prng GUARDED_BY(m_mutex);
432 : :
433 : : Mutex m_events_mutex;
434 : : CSHA256 m_events_hasher GUARDED_BY(m_events_mutex);
435 : :
436 : : public:
437 : 1156 : RNGState() noexcept
438 : 1156 : {
439 : 1156 : InitHardwareRand();
440 : 1156 : }
441 : :
442 : 1156 : ~RNGState() = default;
443 : :
444 : 235026 : void AddEvent(uint32_t event_info) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_events_mutex)
445 : : {
446 : 235026 : LOCK(m_events_mutex);
447 : :
448 : 235026 : m_events_hasher.Write((const unsigned char *)&event_info, sizeof(event_info));
449 : : // Get the low four bytes of the performance counter. This translates to roughly the
450 : : // subsecond part.
451 : 235026 : uint32_t perfcounter = (GetPerformanceCounter() & 0xffffffff);
452 [ + - ]: 235026 : m_events_hasher.Write((const unsigned char*)&perfcounter, sizeof(perfcounter));
453 : 235026 : }
454 : :
455 : : /**
456 : : * Feed (the hash of) all events added through AddEvent() to hasher.
457 : : */
458 : 3089 : void SeedEvents(CSHA512& hasher) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_events_mutex)
459 : : {
460 : : // We use only SHA256 for the events hashing to get the ASM speedups we have for SHA256,
461 : : // since we want it to be fast as network peers may be able to trigger it repeatedly.
462 : 3089 : LOCK(m_events_mutex);
463 : :
464 : 3089 : unsigned char events_hash[32];
465 : 3089 : m_events_hasher.Finalize(events_hash);
466 : 3089 : hasher.Write(events_hash, 32);
467 : :
468 : : // Re-initialize the hasher with the finalized state to use later.
469 : 3089 : m_events_hasher.Reset();
470 [ + - ]: 3089 : m_events_hasher.Write(events_hash, 32);
471 : 3089 : }
472 : :
473 : : /** Make the output of MixExtract (unless always_use_real_rng) deterministic, with specified seed. */
474 : 601 : void MakeDeterministic(const uint256& seed) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
475 : : {
476 : 601 : LOCK(m_mutex);
477 [ + - ]: 601 : m_deterministic_prng.emplace(MakeByteSpan(seed));
478 : 601 : }
479 : :
480 : : /** Extract up to 32 bytes of entropy from the RNG state, mixing in new entropy from hasher.
481 : : *
482 : : * If this function has never been called with strong_seed = true, false is returned.
483 : : *
484 : : * If always_use_real_rng is false, and MakeDeterministic has been called before, output
485 : : * from the deterministic PRNG instead.
486 : : */
487 : 2282992 : bool MixExtract(unsigned char* out, size_t num, CSHA512&& hasher, bool strong_seed, bool always_use_real_rng) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
488 : : {
489 [ - + ]: 2282992 : assert(num <= 32);
490 : 2282992 : unsigned char buf[64];
491 : 2282992 : static_assert(sizeof(buf) == CSHA512::OUTPUT_SIZE, "Buffer needs to have hasher's output size");
492 : 2282992 : bool ret;
493 : 2282992 : {
494 : 2282992 : LOCK(m_mutex);
495 : 2282992 : ret = (m_strongly_seeded |= strong_seed);
496 : : // Write the current state of the RNG into the hasher
497 : 2282992 : hasher.Write(m_state, 32);
498 : : // Write a new counter number into the state
499 : 2282992 : hasher.Write((const unsigned char*)&m_counter, sizeof(m_counter));
500 : 2282992 : ++m_counter;
501 : : // Finalize the hasher
502 : 2282992 : hasher.Finalize(buf);
503 : : // Store the last 32 bytes of the hash output as new RNG state.
504 [ + + ]: 2282992 : memcpy(m_state, buf + 32, 32);
505 : : // Handle requests for deterministic randomness.
506 [ + + + + ]: 2282992 : if (!always_use_real_rng && m_deterministic_prng.has_value()) [[unlikely]] {
507 : : // Overwrite the beginning of buf, which will be used for output.
508 : 385734 : m_deterministic_prng->Keystream(AsWritableBytes(Span{buf, num}));
509 : : // Do not require strong seeding for deterministic output.
510 : 385734 : ret = true;
511 : : }
512 : 2282992 : }
513 : : // If desired, copy (up to) the first 32 bytes of the hash output as output.
514 [ + + ]: 2282992 : if (num) {
515 [ - + ]: 2279683 : assert(out != nullptr);
516 : 2279683 : memcpy(out, buf, num);
517 : : }
518 : : // Best effort cleanup of internal state
519 : 2282992 : hasher.Reset();
520 : 2282992 : memory_cleanse(buf, 64);
521 : 2282992 : return ret;
522 : : }
523 : : };
524 : :
525 : 2516136 : RNGState& GetRNGState() noexcept
526 : : {
527 : : // This idiom relies on the guarantee that static variable are initialized
528 : : // on first call, even when multiple parallel calls are permitted.
529 [ + + + - ]: 2516136 : static std::vector<RNGState, secure_allocator<RNGState>> g_rng(1);
530 : 2516136 : return g_rng[0];
531 : : }
532 : :
533 : : /* A note on the use of noexcept in the seeding functions below:
534 : : *
535 : : * None of the RNG code should ever throw any exception.
536 : : */
537 : :
538 : 2283763 : void SeedTimestamp(CSHA512& hasher) noexcept
539 : : {
540 : 2283763 : int64_t perfcounter = GetPerformanceCounter();
541 : 2283763 : hasher.Write((const unsigned char*)&perfcounter, sizeof(perfcounter));
542 : 2283763 : }
543 : :
544 : 2280674 : void SeedFast(CSHA512& hasher) noexcept
545 : : {
546 : 2280674 : unsigned char buffer[32];
547 : :
548 : : // Stack pointer to indirectly commit to thread/callstack
549 : 2280674 : const unsigned char* ptr = buffer;
550 : 2280674 : hasher.Write((const unsigned char*)&ptr, sizeof(ptr));
551 : :
552 : : // Hardware randomness is very fast when available; use it always.
553 : 2280674 : SeedHardwareFast(hasher);
554 : :
555 : : // High-precision timestamp
556 : 2280674 : SeedTimestamp(hasher);
557 : 2280674 : }
558 : :
559 : 2918 : void SeedSlow(CSHA512& hasher, RNGState& rng) noexcept
560 : : {
561 : 2918 : unsigned char buffer[32];
562 : :
563 : : // Everything that the 'fast' seeder includes
564 : 2918 : SeedFast(hasher);
565 : :
566 : : // OS randomness
567 : 2918 : GetOSRand(buffer);
568 : 2918 : hasher.Write(buffer, sizeof(buffer));
569 : :
570 : : // Add the events hasher into the mix
571 : 2918 : rng.SeedEvents(hasher);
572 : :
573 : : // High-precision timestamp.
574 : : //
575 : : // Note that we also commit to a timestamp in the Fast seeder, so we indirectly commit to a
576 : : // benchmark of all the entropy gathering sources in this function).
577 : 2918 : SeedTimestamp(hasher);
578 : 2918 : }
579 : :
580 : : /** Extract entropy from rng, strengthen it, and feed it into hasher. */
581 : 1327 : void SeedStrengthen(CSHA512& hasher, RNGState& rng, SteadyClock::duration dur) noexcept
582 : : {
583 : : // Generate 32 bytes of entropy from the RNG, and a copy of the entropy already in hasher.
584 : : // Never use the deterministic PRNG for this, as the result is only used internally.
585 : 1327 : unsigned char strengthen_seed[32];
586 : 1327 : rng.MixExtract(strengthen_seed, sizeof(strengthen_seed), CSHA512(hasher), false, /*always_use_real_rng=*/true);
587 : : // Strengthen the seed, and feed it into hasher.
588 : 1327 : Strengthen(strengthen_seed, dur, hasher);
589 : 1327 : }
590 : :
591 : 171 : void SeedPeriodic(CSHA512& hasher, RNGState& rng) noexcept
592 : : {
593 : : // Everything that the 'fast' seeder includes
594 : 171 : SeedFast(hasher);
595 : :
596 : : // High-precision timestamp
597 : 171 : SeedTimestamp(hasher);
598 : :
599 : : // Add the events hasher into the mix
600 : 171 : rng.SeedEvents(hasher);
601 : :
602 : : // Dynamic environment data (clocks, resource usage, ...)
603 : 171 : auto old_size = hasher.Size();
604 : 171 : RandAddDynamicEnv(hasher);
605 [ - + ]: 171 : LogDebug(BCLog::RAND, "Feeding %i bytes of dynamic environment data into RNG\n", hasher.Size() - old_size);
606 : :
607 : : // Strengthen for 10 ms
608 : 171 : SeedStrengthen(hasher, rng, 10ms);
609 : 171 : }
610 : :
611 : 1156 : void SeedStartup(CSHA512& hasher, RNGState& rng) noexcept
612 : : {
613 : : // Gather 256 bits of hardware randomness, if available
614 : 1156 : SeedHardwareSlow(hasher);
615 : :
616 : : // Everything that the 'slow' seeder includes.
617 : 1156 : SeedSlow(hasher, rng);
618 : :
619 : : // Dynamic environment data (clocks, resource usage, ...)
620 : 1156 : auto old_size = hasher.Size();
621 : 1156 : RandAddDynamicEnv(hasher);
622 : :
623 : : // Static environment data
624 : 1156 : RandAddStaticEnv(hasher);
625 [ - + ]: 1156 : LogDebug(BCLog::RAND, "Feeding %i bytes of environment data into RNG\n", hasher.Size() - old_size);
626 : :
627 : : // Strengthen for 100 ms
628 : 1156 : SeedStrengthen(hasher, rng, 100ms);
629 : 1156 : }
630 : :
631 : : enum class RNGLevel {
632 : : FAST, //!< Automatically called by GetRandBytes
633 : : SLOW, //!< Automatically called by GetStrongRandBytes
634 : : PERIODIC, //!< Called by RandAddPeriodic()
635 : : };
636 : :
637 : 2279518 : void ProcRand(unsigned char* out, int num, RNGLevel level, bool always_use_real_rng) noexcept
638 : : {
639 : : // Make sure the RNG is initialized first (as all Seed* function possibly need hwrand to be available).
640 : 2279518 : RNGState& rng = GetRNGState();
641 : :
642 [ - + ]: 2279518 : assert(num <= 32);
643 : :
644 : 2279518 : CSHA512 hasher;
645 [ + + + - ]: 2279518 : switch (level) {
646 : 2277585 : case RNGLevel::FAST:
647 : 2277585 : SeedFast(hasher);
648 : 2277585 : break;
649 : 1762 : case RNGLevel::SLOW:
650 : 1762 : SeedSlow(hasher, rng);
651 : 1762 : break;
652 : 171 : case RNGLevel::PERIODIC:
653 : 171 : SeedPeriodic(hasher, rng);
654 : 171 : break;
655 : : }
656 : :
657 : : // Combine with and update state
658 [ + + ]: 2279518 : if (!rng.MixExtract(out, num, std::move(hasher), false, always_use_real_rng)) {
659 : : // On the first invocation, also seed with SeedStartup().
660 : 1156 : CSHA512 startup_hasher;
661 : 1156 : SeedStartup(startup_hasher, rng);
662 : 1156 : rng.MixExtract(out, num, std::move(startup_hasher), true, always_use_real_rng);
663 : : }
664 : 2279518 : }
665 : :
666 : : } // namespace
667 : :
668 : :
669 : : /** Internal function to set g_determinstic_rng. Only accessed from tests. */
670 : 601 : void MakeRandDeterministicDANGEROUS(const uint256& seed) noexcept
671 : : {
672 : 601 : GetRNGState().MakeDeterministic(seed);
673 : 601 : }
674 : :
675 : 2276460 : void GetRandBytes(Span<unsigned char> bytes) noexcept
676 : : {
677 : 2276460 : ProcRand(bytes.data(), bytes.size(), RNGLevel::FAST, /*always_use_real_rng=*/false);
678 : 2276460 : }
679 : :
680 : 1762 : void GetStrongRandBytes(Span<unsigned char> bytes) noexcept
681 : : {
682 : 1762 : ProcRand(bytes.data(), bytes.size(), RNGLevel::SLOW, /*always_use_real_rng=*/true);
683 : 1762 : }
684 : :
685 : 171 : void RandAddPeriodic() noexcept
686 : : {
687 : 171 : ProcRand(nullptr, 0, RNGLevel::PERIODIC, /*always_use_real_rng=*/false);
688 : 171 : }
689 : :
690 : 235026 : void RandAddEvent(const uint32_t event_info) noexcept { GetRNGState().AddEvent(event_info); }
691 : :
692 : 2260467 : void FastRandomContext::RandomSeed() noexcept
693 : : {
694 : 2260467 : uint256 seed = GetRandHash();
695 : 2260467 : rng.SetKey(MakeByteSpan(seed));
696 : 2260467 : requires_seed = false;
697 : 2260467 : }
698 : :
699 : 1077771 : void FastRandomContext::fillrand(Span<std::byte> output) noexcept
700 : : {
701 [ + + ]: 1077771 : if (requires_seed) RandomSeed();
702 : 1077771 : rng.Keystream(output);
703 : 1077771 : }
704 : :
705 : 5 : FastRandomContext::FastRandomContext(const uint256& seed) noexcept : requires_seed(false), rng(MakeByteSpan(seed)) {}
706 : :
707 : 666 : void FastRandomContext::Reseed(const uint256& seed) noexcept
708 : : {
709 : 666 : FlushCache();
710 : 666 : requires_seed = false;
711 : 666 : rng = {MakeByteSpan(seed)};
712 : 666 : }
713 : :
714 : 991 : bool Random_SanityCheck()
715 : : {
716 : 991 : uint64_t start = GetPerformanceCounter();
717 : :
718 : : /* This does not measure the quality of randomness, but it does test that
719 : : * GetOSRand() overwrites all 32 bytes of the output given a maximum
720 : : * number of tries.
721 : : */
722 : 991 : static constexpr int MAX_TRIES{1024};
723 : 991 : uint8_t data[NUM_OS_RANDOM_BYTES];
724 : 991 : bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
725 : 991 : int num_overwritten;
726 : 991 : int tries = 0;
727 : : /* Loop until all bytes have been overwritten at least once, or max number tries reached */
728 : 1092 : do {
729 : 1092 : memset(data, 0, NUM_OS_RANDOM_BYTES);
730 : 1092 : GetOSRand(data);
731 [ + + ]: 36036 : for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
732 : 34944 : overwritten[x] |= (data[x] != 0);
733 : : }
734 : :
735 : : num_overwritten = 0;
736 [ + + ]: 36036 : for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
737 [ + + ]: 34944 : if (overwritten[x]) {
738 : 34833 : num_overwritten += 1;
739 : : }
740 : : }
741 : :
742 : 1092 : tries += 1;
743 [ + + ]: 1092 : } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
744 [ + - ]: 991 : if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
745 : :
746 : : // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
747 : 991 : std::this_thread::sleep_for(std::chrono::milliseconds(1));
748 : 991 : uint64_t stop = GetPerformanceCounter();
749 [ + - ]: 991 : if (stop == start) return false;
750 : :
751 : : // We called GetPerformanceCounter. Use it as entropy.
752 : 991 : CSHA512 to_add;
753 : 991 : to_add.Write((const unsigned char*)&start, sizeof(start));
754 : 991 : to_add.Write((const unsigned char*)&stop, sizeof(stop));
755 : 991 : GetRNGState().MixExtract(nullptr, 0, std::move(to_add), false, /*always_use_real_rng=*/true);
756 : :
757 : 991 : return true;
758 : : }
759 : :
760 : : static constexpr std::array<std::byte, ChaCha20::KEYLEN> ZERO_KEY{};
761 : :
762 : 2963729 : FastRandomContext::FastRandomContext(bool fDeterministic) noexcept : requires_seed(!fDeterministic), rng(ZERO_KEY)
763 : : {
764 : : // Note that despite always initializing with ZERO_KEY, requires_seed is set to true if not
765 : : // fDeterministic. That means the rng will be reinitialized with a secure random key upon first
766 : : // use.
767 : 2963729 : }
768 : :
769 : 1125 : void RandomInit()
770 : : {
771 : : // Invoke RNG code to trigger initialization (if not already performed)
772 : 1125 : ProcRand(nullptr, 0, RNGLevel::FAST, /*always_use_real_rng=*/true);
773 : :
774 : 1125 : ReportHardwareRand();
775 : 1125 : }
776 : :
777 : 13074 : double MakeExponentiallyDistributed(uint64_t uniform) noexcept
778 : : {
779 : : // To convert uniform into an exponentially-distributed double, we use two steps:
780 : : // - Convert uniform into a uniformly-distributed double in range [0, 1), use the expression
781 : : // ((uniform >> 11) * 0x1.0p-53), as described in https://prng.di.unimi.it/ under
782 : : // "Generating uniform doubles in the unit interval". Call this value x.
783 : : // - Given an x in uniformly distributed in [0, 1), we find an exponentially distributed value
784 : : // by applying the quantile function to it. For the exponential distribution with mean 1 this
785 : : // is F(x) = -log(1 - x).
786 : : //
787 : : // Combining the two, and using log1p(x) = log(1 + x), we obtain the following:
788 : 13074 : return -std::log1p((uniform >> 11) * -0x1.0p-53);
789 : : }
|
