You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

random.cpp 14KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467
  1. // Copyright (c) 2009-2010 Satoshi Nakamoto
  2. // Copyright (c) 2009-2016 The Starwels developers
  3. // Distributed under the MIT software license, see the accompanying
  4. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5. #include "random.h"
  6. #include "crypto/sha512.h"
  7. #include "support/cleanse.h"
  8. #ifdef WIN32
  9. #include "compat.h" // for Windows API
  10. #include <wincrypt.h>
  11. #endif
  12. #include "util.h" // for LogPrint()
  13. #include "utilstrencodings.h" // for GetTime()
  14. #include <stdlib.h>
  15. #include <limits>
  16. #include <chrono>
  17. #include <thread>
  18. #ifndef WIN32
  19. #include <sys/time.h>
  20. #endif
  21. #ifdef HAVE_SYS_GETRANDOM
  22. #include <sys/syscall.h>
  23. #include <linux/random.h>
  24. #endif
  25. #if defined(HAVE_GETENTROPY) || (defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX))
  26. #include <unistd.h>
  27. #endif
  28. #if defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX)
  29. #include <sys/random.h>
  30. #endif
  31. #ifdef HAVE_SYSCTL_ARND
  32. #include <sys/sysctl.h>
  33. #endif
  34. #include <mutex>
  35. #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
  36. #include <cpuid.h>
  37. #endif
  38. #include <openssl/err.h>
  39. #include <openssl/rand.h>
  40. static void RandFailure()
  41. {
  42. LogPrintf("Failed to read randomness, aborting\n");
  43. abort();
  44. }
  45. static inline int64_t GetPerformanceCounter()
  46. {
  47. // Read the hardware time stamp counter when available.
  48. // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information.
  49. #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64))
  50. return __rdtsc();
  51. #elif !defined(_MSC_VER) && defined(__i386__)
  52. uint64_t r = 0;
  53. __asm__ volatile ("rdtsc" : "=A"(r)); // Constrain the r variable to the eax:edx pair.
  54. return r;
  55. #elif !defined(_MSC_VER) && (defined(__x86_64__) || defined(__amd64__))
  56. uint64_t r1 = 0, r2 = 0;
  57. __asm__ volatile ("rdtsc" : "=a"(r1), "=d"(r2)); // Constrain r1 to rax and r2 to rdx.
  58. return (r2 << 32) | r1;
  59. #else
  60. // Fall back to using C++11 clock (usually microsecond or nanosecond precision)
  61. return std::chrono::high_resolution_clock::now().time_since_epoch().count();
  62. #endif
  63. }
  64. #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
  65. static std::atomic<bool> hwrand_initialized{false};
  66. static bool rdrand_supported = false;
  67. static constexpr uint32_t CPUID_F1_ECX_RDRAND = 0x40000000;
  68. static void RDRandInit()
  69. {
  70. uint32_t eax, ebx, ecx, edx;
  71. if (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx & CPUID_F1_ECX_RDRAND)) {
  72. LogPrintf("Using RdRand as an additional entropy source\n");
  73. rdrand_supported = true;
  74. }
  75. hwrand_initialized.store(true);
  76. }
  77. #else
  78. static void RDRandInit() {}
  79. #endif
  80. static bool GetHWRand(unsigned char* ent32) {
  81. #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__)
  82. assert(hwrand_initialized.load(std::memory_order_relaxed));
  83. if (rdrand_supported) {
  84. uint8_t ok;
  85. // Not all assemblers support the rdrand instruction, write it in hex.
  86. #ifdef __i386__
  87. for (int iter = 0; iter < 4; ++iter) {
  88. uint32_t r1, r2;
  89. __asm__ volatile (".byte 0x0f, 0xc7, 0xf0;" // rdrand %eax
  90. ".byte 0x0f, 0xc7, 0xf2;" // rdrand %edx
  91. "setc %2" :
  92. "=a"(r1), "=d"(r2), "=q"(ok) :: "cc");
  93. if (!ok) return false;
  94. WriteLE32(ent32 + 8 * iter, r1);
  95. WriteLE32(ent32 + 8 * iter + 4, r2);
  96. }
  97. #else
  98. uint64_t r1, r2, r3, r4;
  99. __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf0, " // rdrand %rax
  100. "0x48, 0x0f, 0xc7, 0xf3, " // rdrand %rbx
  101. "0x48, 0x0f, 0xc7, 0xf1, " // rdrand %rcx
  102. "0x48, 0x0f, 0xc7, 0xf2; " // rdrand %rdx
  103. "setc %4" :
  104. "=a"(r1), "=b"(r2), "=c"(r3), "=d"(r4), "=q"(ok) :: "cc");
  105. if (!ok) return false;
  106. WriteLE64(ent32, r1);
  107. WriteLE64(ent32 + 8, r2);
  108. WriteLE64(ent32 + 16, r3);
  109. WriteLE64(ent32 + 24, r4);
  110. #endif
  111. return true;
  112. }
  113. #endif
  114. return false;
  115. }
  116. void RandAddSeed()
  117. {
  118. // Seed with CPU performance counter
  119. int64_t nCounter = GetPerformanceCounter();
  120. RAND_add(&nCounter, sizeof(nCounter), 1.5);
  121. memory_cleanse((void*)&nCounter, sizeof(nCounter));
  122. }
  123. static void RandAddSeedPerfmon()
  124. {
  125. RandAddSeed();
  126. #ifdef WIN32
  127. // Don't need this on Linux, OpenSSL automatically uses /dev/urandom
  128. // Seed with the entire set of perfmon data
  129. // This can take up to 2 seconds, so only do it every 10 minutes
  130. static int64_t nLastPerfmon;
  131. if (GetTime() < nLastPerfmon + 10 * 60)
  132. return;
  133. nLastPerfmon = GetTime();
  134. std::vector<unsigned char> vData(250000, 0);
  135. long ret = 0;
  136. unsigned long nSize = 0;
  137. const size_t nMaxSize = 10000000; // Bail out at more than 10MB of performance data
  138. while (true) {
  139. nSize = vData.size();
  140. ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", nullptr, nullptr, vData.data(), &nSize);
  141. if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize)
  142. break;
  143. vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); // Grow size of buffer exponentially
  144. }
  145. RegCloseKey(HKEY_PERFORMANCE_DATA);
  146. if (ret == ERROR_SUCCESS) {
  147. RAND_add(vData.data(), nSize, nSize / 100.0);
  148. memory_cleanse(vData.data(), nSize);
  149. LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize);
  150. } else {
  151. static bool warned = false; // Warn only once
  152. if (!warned) {
  153. LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) failed with code %i\n", __func__, ret);
  154. warned = true;
  155. }
  156. }
  157. #endif
  158. }
  159. #ifndef WIN32
  160. /** Fallback: get 32 bytes of system entropy from /dev/urandom. The most
  161. * compatible way to get cryptographic randomness on UNIX-ish platforms.
  162. */
  163. void GetDevURandom(unsigned char *ent32)
  164. {
  165. int f = open("/dev/urandom", O_RDONLY);
  166. if (f == -1) {
  167. RandFailure();
  168. }
  169. int have = 0;
  170. do {
  171. ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have);
  172. if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) {
  173. close(f);
  174. RandFailure();
  175. }
  176. have += n;
  177. } while (have < NUM_OS_RANDOM_BYTES);
  178. close(f);
  179. }
  180. #endif
  181. /** Get 32 bytes of system entropy. */
  182. void GetOSRand(unsigned char *ent32)
  183. {
  184. #if defined(WIN32)
  185. HCRYPTPROV hProvider;
  186. int ret = CryptAcquireContextW(&hProvider, nullptr, nullptr, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
  187. if (!ret) {
  188. RandFailure();
  189. }
  190. ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32);
  191. if (!ret) {
  192. RandFailure();
  193. }
  194. CryptReleaseContext(hProvider, 0);
  195. #elif defined(HAVE_SYS_GETRANDOM)
  196. /* Linux. From the getrandom(2) man page:
  197. * "If the urandom source has been initialized, reads of up to 256 bytes
  198. * will always return as many bytes as requested and will not be
  199. * interrupted by signals."
  200. */
  201. int rv = syscall(SYS_getrandom, ent32, NUM_OS_RANDOM_BYTES, 0);
  202. if (rv != NUM_OS_RANDOM_BYTES) {
  203. if (rv < 0 && errno == ENOSYS) {
  204. /* Fallback for kernel <3.17: the return value will be -1 and errno
  205. * ENOSYS if the syscall is not available, in that case fall back
  206. * to /dev/urandom.
  207. */
  208. GetDevURandom(ent32);
  209. } else {
  210. RandFailure();
  211. }
  212. }
  213. #elif defined(HAVE_GETENTROPY) && defined(__OpenBSD__)
  214. /* On OpenBSD this can return up to 256 bytes of entropy, will return an
  215. * error if more are requested.
  216. * The call cannot return less than the requested number of bytes.
  217. getentropy is explicitly limited to openbsd here, as a similar (but not
  218. the same) function may exist on other platforms via glibc.
  219. */
  220. if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
  221. RandFailure();
  222. }
  223. #elif defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX)
  224. // We need a fallback for OSX < 10.12
  225. if (&getentropy != NULL) {
  226. if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) {
  227. RandFailure();
  228. }
  229. } else {
  230. GetDevURandom(ent32);
  231. }
  232. #elif defined(HAVE_SYSCTL_ARND)
  233. /* FreeBSD and similar. It is possible for the call to return less
  234. * bytes than requested, so need to read in a loop.
  235. */
  236. static const int name[2] = {CTL_KERN, KERN_ARND};
  237. int have = 0;
  238. do {
  239. size_t len = NUM_OS_RANDOM_BYTES - have;
  240. if (sysctl(name, ARRAYLEN(name), ent32 + have, &len, nullptr, 0) != 0) {
  241. RandFailure();
  242. }
  243. have += len;
  244. } while (have < NUM_OS_RANDOM_BYTES);
  245. #else
  246. /* Fall back to /dev/urandom if there is no specific method implemented to
  247. * get system entropy for this OS.
  248. */
  249. GetDevURandom(ent32);
  250. #endif
  251. }
  252. void GetRandBytes(unsigned char* buf, int num)
  253. {
  254. if (RAND_bytes(buf, num) != 1) {
  255. RandFailure();
  256. }
  257. }
  258. static void AddDataToRng(void* data, size_t len);
  259. void RandAddSeedSleep()
  260. {
  261. int64_t nPerfCounter1 = GetPerformanceCounter();
  262. std::this_thread::sleep_for(std::chrono::milliseconds(1));
  263. int64_t nPerfCounter2 = GetPerformanceCounter();
  264. // Combine with and update state
  265. AddDataToRng(&nPerfCounter1, sizeof(nPerfCounter1));
  266. AddDataToRng(&nPerfCounter2, sizeof(nPerfCounter2));
  267. memory_cleanse(&nPerfCounter1, sizeof(nPerfCounter1));
  268. memory_cleanse(&nPerfCounter2, sizeof(nPerfCounter2));
  269. }
  270. static std::mutex cs_rng_state;
  271. static unsigned char rng_state[32] = {0};
  272. static uint64_t rng_counter = 0;
  273. static void AddDataToRng(void* data, size_t len) {
  274. CSHA512 hasher;
  275. hasher.Write((const unsigned char*)&len, sizeof(len));
  276. hasher.Write((const unsigned char*)data, len);
  277. unsigned char buf[64];
  278. {
  279. std::unique_lock<std::mutex> lock(cs_rng_state);
  280. hasher.Write(rng_state, sizeof(rng_state));
  281. hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
  282. ++rng_counter;
  283. hasher.Finalize(buf);
  284. memcpy(rng_state, buf + 32, 32);
  285. }
  286. memory_cleanse(buf, 64);
  287. }
  288. void GetStrongRandBytes(unsigned char* out, int num)
  289. {
  290. assert(num <= 32);
  291. CSHA512 hasher;
  292. unsigned char buf[64];
  293. // First source: OpenSSL's RNG
  294. RandAddSeedPerfmon();
  295. GetRandBytes(buf, 32);
  296. hasher.Write(buf, 32);
  297. // Second source: OS RNG
  298. GetOSRand(buf);
  299. hasher.Write(buf, 32);
  300. // Third source: HW RNG, if available.
  301. if (GetHWRand(buf)) {
  302. hasher.Write(buf, 32);
  303. }
  304. // Combine with and update state
  305. {
  306. std::unique_lock<std::mutex> lock(cs_rng_state);
  307. hasher.Write(rng_state, sizeof(rng_state));
  308. hasher.Write((const unsigned char*)&rng_counter, sizeof(rng_counter));
  309. ++rng_counter;
  310. hasher.Finalize(buf);
  311. memcpy(rng_state, buf + 32, 32);
  312. }
  313. // Produce output
  314. memcpy(out, buf, num);
  315. memory_cleanse(buf, 64);
  316. }
  317. uint64_t GetRand(uint64_t nMax)
  318. {
  319. if (nMax == 0)
  320. return 0;
  321. // The range of the random source must be a multiple of the modulus
  322. // to give every possible output value an equal possibility
  323. uint64_t nRange = (std::numeric_limits<uint64_t>::max() / nMax) * nMax;
  324. uint64_t nRand = 0;
  325. do {
  326. GetRandBytes((unsigned char*)&nRand, sizeof(nRand));
  327. } while (nRand >= nRange);
  328. return (nRand % nMax);
  329. }
  330. int GetRandInt(int nMax)
  331. {
  332. return GetRand(nMax);
  333. }
  334. uint256 GetRandHash()
  335. {
  336. uint256 hash;
  337. GetRandBytes((unsigned char*)&hash, sizeof(hash));
  338. return hash;
  339. }
  340. void FastRandomContext::RandomSeed()
  341. {
  342. uint256 seed = GetRandHash();
  343. rng.SetKey(seed.begin(), 32);
  344. requires_seed = false;
  345. }
  346. uint256 FastRandomContext::rand256()
  347. {
  348. if (bytebuf_size < 32) {
  349. FillByteBuffer();
  350. }
  351. uint256 ret;
  352. memcpy(ret.begin(), bytebuf + 64 - bytebuf_size, 32);
  353. bytebuf_size -= 32;
  354. return ret;
  355. }
  356. std::vector<unsigned char> FastRandomContext::randbytes(size_t len)
  357. {
  358. std::vector<unsigned char> ret(len);
  359. if (len > 0) {
  360. rng.Output(&ret[0], len);
  361. }
  362. return ret;
  363. }
  364. FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
  365. {
  366. rng.SetKey(seed.begin(), 32);
  367. }
  368. bool Random_SanityCheck()
  369. {
  370. uint64_t start = GetPerformanceCounter();
  371. /* This does not measure the quality of randomness, but it does test that
  372. * OSRandom() overwrites all 32 bytes of the output given a maximum
  373. * number of tries.
  374. */
  375. static const ssize_t MAX_TRIES = 1024;
  376. uint8_t data[NUM_OS_RANDOM_BYTES];
  377. bool overwritten[NUM_OS_RANDOM_BYTES] = {}; /* Tracks which bytes have been overwritten at least once */
  378. int num_overwritten;
  379. int tries = 0;
  380. /* Loop until all bytes have been overwritten at least once, or max number tries reached */
  381. do {
  382. memset(data, 0, NUM_OS_RANDOM_BYTES);
  383. GetOSRand(data);
  384. for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
  385. overwritten[x] |= (data[x] != 0);
  386. }
  387. num_overwritten = 0;
  388. for (int x=0; x < NUM_OS_RANDOM_BYTES; ++x) {
  389. if (overwritten[x]) {
  390. num_overwritten += 1;
  391. }
  392. }
  393. tries += 1;
  394. } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
  395. if (num_overwritten != NUM_OS_RANDOM_BYTES) return false; /* If this failed, bailed out after too many tries */
  396. // Check that GetPerformanceCounter increases at least during a GetOSRand() call + 1ms sleep.
  397. std::this_thread::sleep_for(std::chrono::milliseconds(1));
  398. uint64_t stop = GetPerformanceCounter();
  399. if (stop == start) return false;
  400. // We called GetPerformanceCounter. Use it as entropy.
  401. RAND_add((const unsigned char*)&start, sizeof(start), 1);
  402. RAND_add((const unsigned char*)&stop, sizeof(stop), 1);
  403. return true;
  404. }
  405. FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
  406. {
  407. if (!fDeterministic) {
  408. return;
  409. }
  410. uint256 seed;
  411. rng.SetKey(seed.begin(), 32);
  412. }
  413. void RandomInit()
  414. {
  415. RDRandInit();
  416. }