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 : 2954040 : 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 : 2954040 : uint64_t r1 = 0, r2 = 0;
76 : 5908080 : __asm__ volatile ("rdtsc" : "=a"(r1), "=d"(r2)); // Constrain r1 to rax and r2 to rdx.
77 : 2954040 : 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 : 1237 : void InitHardwareRand()
97 : : {
98 : 1237 : uint32_t eax, ebx, ecx, edx;
99 : 1237 : GetCPUID(1, 0, eax, ebx, ecx, edx);
100 [ + - ]: 1237 : if (ecx & CPUID_F1_ECX_RDRAND) {
101 : 1237 : g_rdrand_supported = true;
102 : : }
103 : 1237 : GetCPUID(7, 0, eax, ebx, ecx, edx);
104 [ + - ]: 1237 : if (ebx & CPUID_F7_EBX_RDSEED) {
105 : 1237 : g_rdseed_supported = true;
106 : : }
107 : 1237 : }
108 : :
109 : 1182 : 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 [ + - ]: 1182 : if (g_rdseed_supported) {
114 : 1182 : LogPrintf("Using RdSeed as an additional entropy source\n");
115 : : }
116 [ + - ]: 1182 : if (g_rdrand_supported) {
117 : 1182 : LogPrintf("Using RdRand as an additional entropy source\n");
118 : : }
119 : 1182 : }
120 : :
121 : : /** Read 64 bits of entropy using rdrand.
122 : : *
123 : : * Must only be called when RdRand is supported.
124 : : */
125 : 2665335 : 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 = 0;
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 : 2665335 : uint8_t ok = 0;
145 : 2665335 : uint64_t r1 = 0; // See above why we initialize to 0.
146 [ + - ]: 2665335 : for (int i = 0; i < 10; ++i) {
147 : 2665335 : __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf0; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdrand %rax
148 [ - + ]: 2665335 : if (ok) break;
149 : : }
150 : 2665335 : 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 : 4948 : 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 = 0;
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 : 4948 : uint8_t ok;
180 : 4948 : uint64_t r1;
181 : 4948 : do {
182 : 4948 : __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf8; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdseed %rax
183 [ - + ]: 4948 : if (ok) break;
184 : 0 : __asm__ volatile ("pause");
185 : : } while(true);
186 : 4948 : 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 : : bool g_rndrrs_supported = false;
196 : :
197 : : void InitHardwareRand()
198 : : {
199 : : if (getauxval(AT_HWCAP2) & HWCAP2_RNG) {
200 : : g_rndr_supported = true;
201 : : g_rndrrs_supported = VerifyRNDRRS();
202 : : }
203 : : }
204 : :
205 : : void ReportHardwareRand()
206 : : {
207 : : // This must be done in a separate function, as InitHardwareRand() may be indirectly called
208 : : // from global constructors, before logging is initialized.
209 : : if (g_rndr_supported && g_rndrrs_supported) {
210 : : LogPrintf("Using RNDR and RNDRRS as additional entropy sources\n");
211 : : } else if (g_rndr_supported) {
212 : : LogPrintf("Using RNDR as an additional entropy source\n");
213 : : }
214 : : }
215 : :
216 : : /** Read 64 bits of entropy using rndr.
217 : : *
218 : : * Must only be called when RNDR is supported.
219 : : */
220 : : uint64_t GetRNDR() noexcept
221 : : {
222 : : uint8_t ok = 0;
223 : : uint64_t r1;
224 : : do {
225 : : // https://developer.arm.com/documentation/ddi0601/2022-12/AArch64-Registers/RNDR--Random-Number
226 : : __asm__ volatile("mrs %0, s3_3_c2_c4_0; cset %w1, ne;"
227 : : : "=r"(r1), "=r"(ok)::"cc");
228 : : if (ok) break;
229 : : __asm__ volatile("yield");
230 : : } while (true);
231 : : return r1;
232 : : }
233 : :
234 : : // Helper function to retrieve random value using RNDRRS
235 : : bool GetRNDRRSInternal(uint64_t &r1) noexcept
236 : : {
237 : : uint8_t ok = 0;
238 : : __asm__ volatile("mrs %0, s3_3_c2_c4_1; cset %w1, ne;"
239 : : : "=r"(r1), "=r"(ok)::"cc");
240 : : return ok != 0;
241 : : }
242 : :
243 : :
244 : : /** Read 64 bits of entropy using RNDRRS.
245 : : * Must only be called when RNDRRS is supported.
246 : : */
247 : : uint64_t GetRNDRRS() noexcept
248 : : {
249 : : uint64_t r1;
250 : : while (!GetRNDRRSInternal(r1)) {
251 : : __asm__ volatile("yield");
252 : : }
253 : : return r1;
254 : : }
255 : :
256 : : /** Verify if RNDRRS is supported and functional.
257 : : * Return true if it works within the retry limit.
258 : : */
259 : : bool VerifyRNDRRS() noexcept
260 : : {
261 : : uint64_t test;
262 : : for (int retry = 0; retry < 10; ++retry) {
263 : : if (GetRNDRRSInternal(test)) {
264 : : return true;
265 : : }
266 : : __asm__ volatile("yield");
267 : : }
268 : : return false;
269 : : }
270 : :
271 : : #else
272 : : /* Access to other hardware random number generators could be added here later,
273 : : * assuming it is sufficiently fast (in the order of a few hundred CPU cycles).
274 : : * Slower sources should probably be invoked separately, and/or only from
275 : : * RandAddPeriodic (which is called once a minute).
276 : : */
277 : : void InitHardwareRand() {}
278 : : void ReportHardwareRand() {}
279 : : #endif
280 : :
281 : : /** Add 64 bits of entropy gathered from hardware to hasher. Do nothing if not supported. */
282 : 2665335 : void SeedHardwareFast(CSHA512& hasher) noexcept {
283 : : #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
284 [ + - ]: 2665335 : if (g_rdrand_supported) {
285 : 2665335 : uint64_t out = GetRdRand();
286 : 2665335 : hasher.Write((const unsigned char*)&out, sizeof(out));
287 : 2665335 : return;
288 : : }
289 : : #elif defined(__aarch64__) && defined(HWCAP2_RNG)
290 : : if (g_rndr_supported) {
291 : : uint64_t out = GetRNDR();
292 : : hasher.Write((const unsigned char*)&out, sizeof(out));
293 : : return;
294 : : }
295 : : #endif
296 : : }
297 : :
298 : : /** Add 256 bits of entropy gathered from hardware to hasher. Do nothing if not supported. */
299 : 1237 : void SeedHardwareSlow(CSHA512& hasher) noexcept {
300 : : #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
301 : : // When we want 256 bits of entropy, prefer RdSeed over RdRand, as it's
302 : : // guaranteed to produce independent randomness on every call.
303 [ + - ]: 1237 : if (g_rdseed_supported) {
304 [ + + ]: 6185 : for (int i = 0; i < 4; ++i) {
305 : 4948 : uint64_t out = GetRdSeed();
306 : 4948 : hasher.Write((const unsigned char*)&out, sizeof(out));
307 : : }
308 : : return;
309 : : }
310 : : // When falling back to RdRand, XOR the result of 1024 results.
311 : : // This guarantees a reseeding occurs between each.
312 [ # # ]: 0 : if (g_rdrand_supported) {
313 [ # # ]: 0 : for (int i = 0; i < 4; ++i) {
314 : 0 : uint64_t out = 0;
315 [ # # ]: 0 : for (int j = 0; j < 1024; ++j) out ^= GetRdRand();
316 : 0 : hasher.Write((const unsigned char*)&out, sizeof(out));
317 : : }
318 : : return;
319 : : }
320 : : #elif defined(__aarch64__) && defined(HWCAP2_RNG)
321 : : if (g_rndrrs_supported) {
322 : : for (int i = 0; i < 4; ++i) {
323 : : uint64_t out = GetRNDRRS();
324 : : hasher.Write((const unsigned char*)&out, sizeof(out));
325 : : }
326 : : return;
327 : : }
328 : : #endif
329 : : }
330 : :
331 : : /** Use repeated SHA512 to strengthen the randomness in seed32, and feed into hasher. */
332 : 1413 : void Strengthen(const unsigned char (&seed)[32], SteadyClock::duration dur, CSHA512& hasher) noexcept
333 : : {
334 : 1413 : CSHA512 inner_hasher;
335 : 1413 : inner_hasher.Write(seed, sizeof(seed));
336 : :
337 : : // Hash loop
338 : 1413 : unsigned char buffer[64];
339 : 1413 : const auto stop{SteadyClock::now() + dur};
340 : 67997 : do {
341 [ + + ]: 68064997 : for (int i = 0; i < 1000; ++i) {
342 : 67997000 : inner_hasher.Finalize(buffer);
343 : 67997000 : inner_hasher.Reset();
344 : 67997000 : inner_hasher.Write(buffer, sizeof(buffer));
345 : : }
346 : : // Benchmark operation and feed it into outer hasher.
347 : 67997 : int64_t perf = GetPerformanceCounter();
348 : 67997 : hasher.Write((const unsigned char*)&perf, sizeof(perf));
349 [ + + ]: 67997 : } while (SteadyClock::now() < stop);
350 : :
351 : : // Produce output from inner state and feed it to outer hasher.
352 : 1413 : inner_hasher.Finalize(buffer);
353 : 1413 : hasher.Write(buffer, sizeof(buffer));
354 : : // Try to clean up.
355 : 1413 : inner_hasher.Reset();
356 : 1413 : memory_cleanse(buffer, sizeof(buffer));
357 : 1413 : }
358 : :
359 : : #ifndef WIN32
360 : : /** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
361 : : * compatible way to get cryptographic randomness on UNIX-ish platforms.
362 : : */
363 : : [[maybe_unused]] void GetDevURandom(unsigned char *ent32)
364 : : {
365 : : int f = open("/dev/urandom", O_RDONLY);
366 : : if (f == -1) {
367 : : RandFailure();
368 : : }
369 : : int have = 0;
370 : : do {
371 : : ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
372 : : if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
373 : : close(f);
374 : : RandFailure();
375 : : }
376 : : have += n;
377 : : } while (have < NUM_OS_RANDOM_BYTES);
378 : : close(f);
379 : : }
380 : : #endif
381 : :
382 : : /** Get 32 bytes of system entropy. */
383 : 4240 : void GetOSRand(unsigned char *ent32)
384 : : {
385 : : #if defined(WIN32)
386 : : HCRYPTPROV hProvider;
387 : : int ret = CryptAcquireContextW(&hProvider, nullptr, nullptr, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
388 : : if (!ret) {
389 : : RandFailure();
390 : : }
391 : : ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
392 : : if (!ret) {
393 : : RandFailure();
394 : : }
395 : : CryptReleaseContext(hProvider, 0);
396 : : #elif defined(HAVE_GETRANDOM)
397 : : /* Linux. From the getrandom(2) man page:
398 : : * "If the urandom source has been initialized, reads of up to 256 bytes
399 : : * will always return as many bytes as requested and will not be
400 : : * interrupted by signals."
401 : : */
402 [ - + ]: 4240 : if (getrandom(ent32, NUM_OS_RANDOM_BYTES, 0) != NUM_OS_RANDOM_BYTES) {
403 : 0 : RandFailure();
404 : : }
405 : : #elif defined(__OpenBSD__)
406 : : /* OpenBSD. From the arc4random(3) man page:
407 : : "Use of these functions is encouraged for almost all random number
408 : : consumption because the other interfaces are deficient in either
409 : : quality, portability, standardization, or availability."
410 : : The function call is always successful.
411 : : */
412 : : arc4random_buf(ent32, NUM_OS_RANDOM_BYTES);
413 : : #elif defined(HAVE_GETENTROPY_RAND) && defined(__APPLE__)
414 : : if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
415 : : RandFailure();
416 : : }
417 : : #elif defined(HAVE_SYSCTL_ARND)
418 : : /* FreeBSD, NetBSD and similar. It is possible for the call to return less
419 : : * bytes than requested, so need to read in a loop.
420 : : */
421 : : static int name[2] = {CTL_KERN, KERN_ARND};
422 : : int have = 0;
423 : : do {
424 : : size_t len = NUM_OS_RANDOM_BYTES - have;
425 : : if (sysctl(name, std::size(name), ent32 + have, &len, nullptr, 0) != 0) {
426 : : RandFailure();
427 : : }
428 : : have += len;
429 : : } while (have < NUM_OS_RANDOM_BYTES);
430 : : #else
431 : : /* Fall back to /dev/urandom if there is no specific method implemented to
432 : : * get system entropy for this OS.
433 : : */
434 : : GetDevURandom(ent32);
435 : : #endif
436 : 4240 : }
437 : :
438 : : class RNGState {
439 : : Mutex m_mutex;
440 : : /* The RNG state consists of 256 bits of entropy, taken from the output of
441 : : * one operation's SHA512 output, and fed as input to the next one.
442 : : * Carrying 256 bits of entropy should be sufficient to guarantee
443 : : * unpredictability as long as any entropy source was ever unpredictable
444 : : * to an attacker. To protect against situations where an attacker might
445 : : * observe the RNG's state, fresh entropy is always mixed when
446 : : * GetStrongRandBytes is called.
447 : : */
448 : : unsigned char m_state[32] GUARDED_BY(m_mutex) = {0};
449 : : uint64_t m_counter GUARDED_BY(m_mutex) = 0;
450 : : bool m_strongly_seeded GUARDED_BY(m_mutex) = false;
451 : :
452 : : /** If not nullopt, the output of this RNGState is redirected and drawn from here
453 : : * (unless always_use_real_rng is passed to MixExtract). */
454 : : std::optional<ChaCha20> m_deterministic_prng GUARDED_BY(m_mutex);
455 : :
456 : : Mutex m_events_mutex;
457 : : CSHA256 m_events_hasher GUARDED_BY(m_events_mutex);
458 : :
459 : : public:
460 : 1237 : RNGState() noexcept
461 : 1237 : {
462 : 1237 : InitHardwareRand();
463 : 1237 : }
464 : :
465 : 1237 : ~RNGState() = default;
466 : :
467 : 215382 : void AddEvent(uint32_t event_info) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_events_mutex)
468 : : {
469 : 215382 : LOCK(m_events_mutex);
470 : :
471 : 215382 : m_events_hasher.Write((const unsigned char *)&event_info, sizeof(event_info));
472 : : // Get the low four bytes of the performance counter. This translates to roughly the
473 : : // subsecond part.
474 : 215382 : uint32_t perfcounter = (GetPerformanceCounter() & 0xffffffff);
475 [ + - ]: 215382 : m_events_hasher.Write((const unsigned char*)&perfcounter, sizeof(perfcounter));
476 : 215382 : }
477 : :
478 : : /**
479 : : * Feed (the hash of) all events added through AddEvent() to hasher.
480 : : */
481 : 3242 : void SeedEvents(CSHA512& hasher) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_events_mutex)
482 : : {
483 : : // We use only SHA256 for the events hashing to get the ASM speedups we have for SHA256,
484 : : // since we want it to be fast as network peers may be able to trigger it repeatedly.
485 : 3242 : LOCK(m_events_mutex);
486 : :
487 : 3242 : unsigned char events_hash[32];
488 : 3242 : m_events_hasher.Finalize(events_hash);
489 : 3242 : hasher.Write(events_hash, 32);
490 : :
491 : : // Re-initialize the hasher with the finalized state to use later.
492 : 3242 : m_events_hasher.Reset();
493 [ + - ]: 3242 : m_events_hasher.Write(events_hash, 32);
494 : 3242 : }
495 : :
496 : : /** Make the output of MixExtract (unless always_use_real_rng) deterministic, with specified seed. */
497 : 628 : void MakeDeterministic(const uint256& seed) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
498 : : {
499 : 628 : LOCK(m_mutex);
500 [ + - ]: 628 : m_deterministic_prng.emplace(MakeByteSpan(seed));
501 : 628 : }
502 : :
503 : : /** Extract up to 32 bytes of entropy from the RNG state, mixing in new entropy from hasher.
504 : : *
505 : : * If this function has never been called with strong_seed = true, false is returned.
506 : : *
507 : : * If always_use_real_rng is false, and MakeDeterministic has been called before, output
508 : : * from the deterministic PRNG instead.
509 : : */
510 : 2667790 : bool MixExtract(unsigned char* out, size_t num, CSHA512&& hasher, bool strong_seed, bool always_use_real_rng) noexcept EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
511 : : {
512 [ - + ]: 2667790 : assert(num <= 32);
513 : 2667790 : unsigned char buf[64];
514 : 2667790 : static_assert(sizeof(buf) == CSHA512::OUTPUT_SIZE, "Buffer needs to have hasher's output size");
515 : 2667790 : bool ret;
516 : 2667790 : {
517 : 2667790 : LOCK(m_mutex);
518 : 2667790 : ret = (m_strongly_seeded |= strong_seed);
519 : : // Write the current state of the RNG into the hasher
520 : 2667790 : hasher.Write(m_state, 32);
521 : : // Write a new counter number into the state
522 : 2667790 : hasher.Write((const unsigned char*)&m_counter, sizeof(m_counter));
523 : 2667790 : ++m_counter;
524 : : // Finalize the hasher
525 : 2667790 : hasher.Finalize(buf);
526 : : // Store the last 32 bytes of the hash output as new RNG state.
527 [ + + ]: 2667790 : memcpy(m_state, buf + 32, 32);
528 : : // Handle requests for deterministic randomness.
529 [ + + + + ]: 2667790 : if (!always_use_real_rng && m_deterministic_prng.has_value()) [[unlikely]] {
530 : : // Overwrite the beginning of buf, which will be used for output.
531 : 498738 : m_deterministic_prng->Keystream(AsWritableBytes(Span{buf, num}));
532 : : // Do not require strong seeding for deterministic output.
533 : 498738 : ret = true;
534 : : }
535 : 2667790 : }
536 : : // If desired, copy (up to) the first 32 bytes of the hash output as output.
537 [ + + ]: 2667790 : if (num) {
538 [ - + ]: 2664314 : assert(out != nullptr);
539 : 2664314 : memcpy(out, buf, num);
540 : : }
541 : : // Best effort cleanup of internal state
542 : 2667790 : hasher.Reset();
543 : 2667790 : memory_cleanse(buf, 64);
544 : 2667790 : return ret;
545 : : }
546 : : };
547 : :
548 : 2881150 : RNGState& GetRNGState() noexcept
549 : : {
550 : : // This idiom relies on the guarantee that static variable are initialized
551 : : // on first call, even when multiple parallel calls are permitted.
552 [ + + + - ]: 2881150 : static std::vector<RNGState, secure_allocator<RNGState>> g_rng(1);
553 : 2881150 : return g_rng[0];
554 : : }
555 : :
556 : : /* A note on the use of noexcept in the seeding functions below:
557 : : *
558 : : * None of the RNG code should ever throw any exception.
559 : : */
560 : :
561 : 2668577 : void SeedTimestamp(CSHA512& hasher) noexcept
562 : : {
563 : 2668577 : int64_t perfcounter = GetPerformanceCounter();
564 : 2668577 : hasher.Write((const unsigned char*)&perfcounter, sizeof(perfcounter));
565 : 2668577 : }
566 : :
567 : 2665335 : void SeedFast(CSHA512& hasher) noexcept
568 : : {
569 : 2665335 : unsigned char buffer[32];
570 : :
571 : : // Stack pointer to indirectly commit to thread/callstack
572 : 2665335 : const unsigned char* ptr = buffer;
573 : 2665335 : hasher.Write((const unsigned char*)&ptr, sizeof(ptr));
574 : :
575 : : // Hardware randomness is very fast when available; use it always.
576 : 2665335 : SeedHardwareFast(hasher);
577 : :
578 : : // High-precision timestamp
579 : 2665335 : SeedTimestamp(hasher);
580 : 2665335 : }
581 : :
582 : 3066 : void SeedSlow(CSHA512& hasher, RNGState& rng) noexcept
583 : : {
584 : 3066 : unsigned char buffer[32];
585 : :
586 : : // Everything that the 'fast' seeder includes
587 : 3066 : SeedFast(hasher);
588 : :
589 : : // OS randomness
590 : 3066 : GetOSRand(buffer);
591 : 3066 : hasher.Write(buffer, sizeof(buffer));
592 : :
593 : : // Add the events hasher into the mix
594 : 3066 : rng.SeedEvents(hasher);
595 : :
596 : : // High-precision timestamp.
597 : : //
598 : : // Note that we also commit to a timestamp in the Fast seeder, so we indirectly commit to a
599 : : // benchmark of all the entropy gathering sources in this function).
600 : 3066 : SeedTimestamp(hasher);
601 : 3066 : }
602 : :
603 : : /** Extract entropy from rng, strengthen it, and feed it into hasher. */
604 : 1413 : void SeedStrengthen(CSHA512& hasher, RNGState& rng, SteadyClock::duration dur) noexcept
605 : : {
606 : : // Generate 32 bytes of entropy from the RNG, and a copy of the entropy already in hasher.
607 : : // Never use the deterministic PRNG for this, as the result is only used internally.
608 : 1413 : unsigned char strengthen_seed[32];
609 : 1413 : rng.MixExtract(strengthen_seed, sizeof(strengthen_seed), CSHA512(hasher), false, /*always_use_real_rng=*/true);
610 : : // Strengthen the seed, and feed it into hasher.
611 : 1413 : Strengthen(strengthen_seed, dur, hasher);
612 : 1413 : }
613 : :
614 : 176 : void SeedPeriodic(CSHA512& hasher, RNGState& rng) noexcept
615 : : {
616 : : // Everything that the 'fast' seeder includes
617 : 176 : SeedFast(hasher);
618 : :
619 : : // High-precision timestamp
620 : 176 : SeedTimestamp(hasher);
621 : :
622 : : // Add the events hasher into the mix
623 : 176 : rng.SeedEvents(hasher);
624 : :
625 : : // Dynamic environment data (clocks, resource usage, ...)
626 : 176 : auto old_size = hasher.Size();
627 : 176 : RandAddDynamicEnv(hasher);
628 [ - + ]: 176 : LogDebug(BCLog::RAND, "Feeding %i bytes of dynamic environment data into RNG\n", hasher.Size() - old_size);
629 : :
630 : : // Strengthen for 10 ms
631 : 176 : SeedStrengthen(hasher, rng, 10ms);
632 : 176 : }
633 : :
634 : 1237 : void SeedStartup(CSHA512& hasher, RNGState& rng) noexcept
635 : : {
636 : : // Gather 256 bits of hardware randomness, if available
637 : 1237 : SeedHardwareSlow(hasher);
638 : :
639 : : // Everything that the 'slow' seeder includes.
640 : 1237 : SeedSlow(hasher, rng);
641 : :
642 : : // Dynamic environment data (clocks, resource usage, ...)
643 : 1237 : auto old_size = hasher.Size();
644 : 1237 : RandAddDynamicEnv(hasher);
645 : :
646 : : // Static environment data
647 : 1237 : RandAddStaticEnv(hasher);
648 [ - + ]: 1237 : LogDebug(BCLog::RAND, "Feeding %i bytes of environment data into RNG\n", hasher.Size() - old_size);
649 : :
650 : : // Strengthen for 100 ms
651 : 1237 : SeedStrengthen(hasher, rng, 100ms);
652 : 1237 : }
653 : :
654 : : enum class RNGLevel {
655 : : FAST, //!< Automatically called by GetRandBytes
656 : : SLOW, //!< Automatically called by GetStrongRandBytes
657 : : PERIODIC, //!< Called by RandAddPeriodic()
658 : : };
659 : :
660 : 2664098 : void ProcRand(unsigned char* out, int num, RNGLevel level, bool always_use_real_rng) noexcept
661 : : {
662 : : // Make sure the RNG is initialized first (as all Seed* function possibly need hwrand to be available).
663 : 2664098 : RNGState& rng = GetRNGState();
664 : :
665 [ - + ]: 2664098 : assert(num <= 32);
666 : :
667 : 2664098 : CSHA512 hasher;
668 [ + + + - ]: 2664098 : switch (level) {
669 : 2662093 : case RNGLevel::FAST:
670 : 2662093 : SeedFast(hasher);
671 : 2662093 : break;
672 : 1829 : case RNGLevel::SLOW:
673 : 1829 : SeedSlow(hasher, rng);
674 : 1829 : break;
675 : 176 : case RNGLevel::PERIODIC:
676 : 176 : SeedPeriodic(hasher, rng);
677 : 176 : break;
678 : : }
679 : :
680 : : // Combine with and update state
681 [ + + ]: 2664098 : if (!rng.MixExtract(out, num, std::move(hasher), false, always_use_real_rng)) {
682 : : // On the first invocation, also seed with SeedStartup().
683 : 1237 : CSHA512 startup_hasher;
684 : 1237 : SeedStartup(startup_hasher, rng);
685 : 1237 : rng.MixExtract(out, num, std::move(startup_hasher), true, always_use_real_rng);
686 : : }
687 : 2664098 : }
688 : :
689 : : } // namespace
690 : :
691 : :
692 : : /** Internal function to set g_determinstic_rng. Only accessed from tests. */
693 : 628 : void MakeRandDeterministicDANGEROUS(const uint256& seed) noexcept
694 : : {
695 : 628 : GetRNGState().MakeDeterministic(seed);
696 : 628 : }
697 : : std::atomic<bool> g_used_g_prng{false}; // Only accessed from tests
698 : :
699 : 2660911 : void GetRandBytes(Span<unsigned char> bytes) noexcept
700 : : {
701 : 2660911 : g_used_g_prng = true;
702 : 2660911 : ProcRand(bytes.data(), bytes.size(), RNGLevel::FAST, /*always_use_real_rng=*/false);
703 : 2660911 : }
704 : :
705 : 1829 : void GetStrongRandBytes(Span<unsigned char> bytes) noexcept
706 : : {
707 : 1829 : ProcRand(bytes.data(), bytes.size(), RNGLevel::SLOW, /*always_use_real_rng=*/true);
708 : 1829 : }
709 : :
710 : 176 : void RandAddPeriodic() noexcept
711 : : {
712 : 176 : ProcRand(nullptr, 0, RNGLevel::PERIODIC, /*always_use_real_rng=*/false);
713 : 176 : }
714 : :
715 : 215382 : void RandAddEvent(const uint32_t event_info) noexcept { GetRNGState().AddEvent(event_info); }
716 : :
717 : 2644554 : void FastRandomContext::RandomSeed() noexcept
718 : : {
719 : 2644554 : uint256 seed = GetRandHash();
720 : 2644554 : rng.SetKey(MakeByteSpan(seed));
721 : 2644554 : requires_seed = false;
722 : 2644554 : }
723 : :
724 : 1146354 : void FastRandomContext::fillrand(Span<std::byte> output) noexcept
725 : : {
726 [ + + ]: 1146354 : if (requires_seed) RandomSeed();
727 : 1146354 : rng.Keystream(output);
728 : 1146354 : }
729 : :
730 : 5 : FastRandomContext::FastRandomContext(const uint256& seed) noexcept : requires_seed(false), rng(MakeByteSpan(seed)) {}
731 : :
732 : 693 : void FastRandomContext::Reseed(const uint256& seed) noexcept
733 : : {
734 : 693 : FlushCache();
735 : 693 : requires_seed = false;
736 : 693 : rng = {MakeByteSpan(seed)};
737 : 693 : }
738 : :
739 : 1042 : bool Random_SanityCheck()
740 : : {
741 : 1042 : uint64_t start = GetPerformanceCounter();
742 : :
743 : : /* This does not measure the quality of randomness, but it does test that
744 : : * GetOSRand() overwrites all 32 bytes of the output given a maximum
745 : : * number of tries.
746 : : */
747 : 1042 : static constexpr int MAX_TRIES{1024};
748 : 1042 : uint8_t data[NUM_OS_RANDOM_BYTES];
749 : 1042 : bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
750 : 1042 : int num_overwritten;
751 : 1042 : int tries = 0;
752 : : /* Loop until all bytes have been overwritten at least once, or max number tries reached */
753 : 1174 : do {
754 : 1174 : memset(data, 0, NUM_OS_RANDOM_BYTES);
755 : 1174 : GetOSRand(data);
756 [ + + ]: 38742 : for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
757 : 37568 : overwritten[x] |= (data[x] != 0);
758 : : }
759 : :
760 : : num_overwritten = 0;
761 [ + + ]: 38742 : for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
762 [ + + ]: 37568 : if (overwritten[x]) {
763 : 37430 : num_overwritten += 1;
764 : : }
765 : : }
766 : :
767 : 1174 : tries += 1;
768 [ + + ]: 1174 : } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
769 [ + - ]: 1042 : if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
770 : :
771 : : // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
772 : 1042 : std::this_thread::sleep_for(std::chrono::milliseconds(1));
773 : 1042 : uint64_t stop = GetPerformanceCounter();
774 [ + - ]: 1042 : if (stop == start) return false;
775 : :
776 : : // We called GetPerformanceCounter. Use it as entropy.
777 : 1042 : CSHA512 to_add;
778 : 1042 : to_add.Write((const unsigned char*)&start, sizeof(start));
779 : 1042 : to_add.Write((const unsigned char*)&stop, sizeof(stop));
780 : 1042 : GetRNGState().MixExtract(nullptr, 0, std::move(to_add), false, /*always_use_real_rng=*/true);
781 : :
782 : 1042 : return true;
783 : : }
784 : :
785 : : static constexpr std::array<std::byte, ChaCha20::KEYLEN> ZERO_KEY{};
786 : :
787 : 3355757 : FastRandomContext::FastRandomContext(bool fDeterministic) noexcept : requires_seed(!fDeterministic), rng(ZERO_KEY)
788 : : {
789 : : // Note that despite always initializing with ZERO_KEY, requires_seed is set to true if not
790 : : // fDeterministic. That means the rng will be reinitialized with a secure random key upon first
791 : : // use.
792 : 3355757 : }
793 : :
794 : 1182 : void RandomInit()
795 : : {
796 : : // Invoke RNG code to trigger initialization (if not already performed)
797 : 1182 : ProcRand(nullptr, 0, RNGLevel::FAST, /*always_use_real_rng=*/true);
798 : :
799 : 1182 : ReportHardwareRand();
800 : 1182 : }
801 : :
802 : 13712 : double MakeExponentiallyDistributed(uint64_t uniform) noexcept
803 : : {
804 : : // To convert uniform into an exponentially-distributed double, we use two steps:
805 : : // - Convert uniform into a uniformly-distributed double in range [0, 1), use the expression
806 : : // ((uniform >> 11) * 0x1.0p-53), as described in https://prng.di.unimi.it/ under
807 : : // "Generating uniform doubles in the unit interval". Call this value x.
808 : : // - Given an x in uniformly distributed in [0, 1), we find an exponentially distributed value
809 : : // by applying the quantile function to it. For the exponential distribution with mean 1 this
810 : : // is F(x) = -log(1 - x).
811 : : //
812 : : // Combining the two, and using log1p(x) = log(1 + x), we obtain the following:
813 : 13712 : return -std::log1p((uniform >> 11) * -0x1.0p-53);
814 : : }
|
