1252190Srpaulo/* 2252190Srpaulo * Random number generator 3252190Srpaulo * Copyright (c) 2010-2011, Jouni Malinen <j@w1.fi> 4252190Srpaulo * 5252190Srpaulo * This software may be distributed under the terms of the BSD license. 6252190Srpaulo * See README for more details. 7252190Srpaulo * 8252190Srpaulo * This random number generator is used to provide additional entropy to the 9252190Srpaulo * one provided by the operating system (os_get_random()) for session key 10252190Srpaulo * generation. The os_get_random() output is expected to be secure and the 11252190Srpaulo * implementation here is expected to provide only limited protection against 12252190Srpaulo * cases where os_get_random() cannot provide strong randomness. This 13252190Srpaulo * implementation shall not be assumed to be secure as the sole source of 14252190Srpaulo * randomness. The random_get_bytes() function mixes in randomness from 15252190Srpaulo * os_get_random() and as such, calls to os_get_random() can be replaced with 16252190Srpaulo * calls to random_get_bytes() without reducing security. 17252190Srpaulo * 18252190Srpaulo * The design here follows partially the design used in the Linux 19252190Srpaulo * drivers/char/random.c, but the implementation here is simpler and not as 20252190Srpaulo * strong. This is a compromise to reduce duplicated CPU effort and to avoid 21252190Srpaulo * extra code/memory size. As pointed out above, os_get_random() needs to be 22252190Srpaulo * guaranteed to be secure for any of the security assumptions to hold. 23252190Srpaulo */ 24252190Srpaulo 25252190Srpaulo#include "utils/includes.h" 26252190Srpaulo#ifdef __linux__ 27252190Srpaulo#include <fcntl.h> 28252190Srpaulo#endif /* __linux__ */ 29252190Srpaulo 30252190Srpaulo#include "utils/common.h" 31252190Srpaulo#include "utils/eloop.h" 32252190Srpaulo#include "crypto/crypto.h" 33252190Srpaulo#include "sha1.h" 34252190Srpaulo#include "random.h" 35252190Srpaulo 36252190Srpaulo#define POOL_WORDS 32 37252190Srpaulo#define POOL_WORDS_MASK (POOL_WORDS - 1) 38252190Srpaulo#define POOL_TAP1 26 39252190Srpaulo#define POOL_TAP2 20 40252190Srpaulo#define POOL_TAP3 14 41252190Srpaulo#define POOL_TAP4 7 42252190Srpaulo#define POOL_TAP5 1 43252190Srpaulo#define EXTRACT_LEN 16 44252190Srpaulo#define MIN_READY_MARK 2 45252190Srpaulo 46252190Srpaulostatic u32 pool[POOL_WORDS]; 47252190Srpaulostatic unsigned int input_rotate = 0; 48252190Srpaulostatic unsigned int pool_pos = 0; 49252190Srpaulostatic u8 dummy_key[20]; 50252190Srpaulo#ifdef __linux__ 51252190Srpaulostatic size_t dummy_key_avail = 0; 52252190Srpaulostatic int random_fd = -1; 53252190Srpaulo#endif /* __linux__ */ 54252190Srpaulostatic unsigned int own_pool_ready = 0; 55252190Srpaulo#define RANDOM_ENTROPY_SIZE 20 56252190Srpaulostatic char *random_entropy_file = NULL; 57252190Srpaulostatic int random_entropy_file_read = 0; 58252190Srpaulo 59252190Srpaulo#define MIN_COLLECT_ENTROPY 1000 60252190Srpaulostatic unsigned int entropy = 0; 61252190Srpaulostatic unsigned int total_collected = 0; 62252190Srpaulo 63252190Srpaulo 64252190Srpaulostatic void random_write_entropy(void); 65252190Srpaulo 66252190Srpaulo 67252190Srpaulostatic u32 __ROL32(u32 x, u32 y) 68252190Srpaulo{ 69252190Srpaulo return (x << (y & 31)) | (x >> (32 - (y & 31))); 70252190Srpaulo} 71252190Srpaulo 72252190Srpaulo 73252190Srpaulostatic void random_mix_pool(const void *buf, size_t len) 74252190Srpaulo{ 75252190Srpaulo static const u32 twist[8] = { 76252190Srpaulo 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 77252190Srpaulo 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 78252190Srpaulo }; 79252190Srpaulo const u8 *pos = buf; 80252190Srpaulo u32 w; 81252190Srpaulo 82252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len); 83252190Srpaulo 84252190Srpaulo while (len--) { 85252190Srpaulo w = __ROL32(*pos++, input_rotate & 31); 86252190Srpaulo input_rotate += pool_pos ? 7 : 14; 87252190Srpaulo pool_pos = (pool_pos - 1) & POOL_WORDS_MASK; 88252190Srpaulo w ^= pool[pool_pos]; 89252190Srpaulo w ^= pool[(pool_pos + POOL_TAP1) & POOL_WORDS_MASK]; 90252190Srpaulo w ^= pool[(pool_pos + POOL_TAP2) & POOL_WORDS_MASK]; 91252190Srpaulo w ^= pool[(pool_pos + POOL_TAP3) & POOL_WORDS_MASK]; 92252190Srpaulo w ^= pool[(pool_pos + POOL_TAP4) & POOL_WORDS_MASK]; 93252190Srpaulo w ^= pool[(pool_pos + POOL_TAP5) & POOL_WORDS_MASK]; 94252190Srpaulo pool[pool_pos] = (w >> 3) ^ twist[w & 7]; 95252190Srpaulo } 96252190Srpaulo} 97252190Srpaulo 98252190Srpaulo 99252190Srpaulostatic void random_extract(u8 *out) 100252190Srpaulo{ 101252190Srpaulo unsigned int i; 102252190Srpaulo u8 hash[SHA1_MAC_LEN]; 103252190Srpaulo u32 *hash_ptr; 104252190Srpaulo u32 buf[POOL_WORDS / 2]; 105252190Srpaulo 106252190Srpaulo /* First, add hash back to pool to make backtracking more difficult. */ 107252190Srpaulo hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) pool, 108252190Srpaulo sizeof(pool), hash); 109252190Srpaulo random_mix_pool(hash, sizeof(hash)); 110252190Srpaulo /* Hash half the pool to extra data */ 111252190Srpaulo for (i = 0; i < POOL_WORDS / 2; i++) 112252190Srpaulo buf[i] = pool[(pool_pos - i) & POOL_WORDS_MASK]; 113252190Srpaulo hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) buf, 114252190Srpaulo sizeof(buf), hash); 115252190Srpaulo /* 116252190Srpaulo * Fold the hash to further reduce any potential output pattern. 117252190Srpaulo * Though, compromise this to reduce CPU use for the most common output 118252190Srpaulo * length (32) and return 16 bytes from instead of only half. 119252190Srpaulo */ 120252190Srpaulo hash_ptr = (u32 *) hash; 121252190Srpaulo hash_ptr[0] ^= hash_ptr[4]; 122252190Srpaulo os_memcpy(out, hash, EXTRACT_LEN); 123252190Srpaulo} 124252190Srpaulo 125252190Srpaulo 126252190Srpaulovoid random_add_randomness(const void *buf, size_t len) 127252190Srpaulo{ 128252190Srpaulo struct os_time t; 129252190Srpaulo static unsigned int count = 0; 130252190Srpaulo 131252190Srpaulo count++; 132252190Srpaulo if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) { 133252190Srpaulo /* 134252190Srpaulo * No need to add more entropy at this point, so save CPU and 135252190Srpaulo * skip the update. 136252190Srpaulo */ 137252190Srpaulo return; 138252190Srpaulo } 139252190Srpaulo wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u", 140252190Srpaulo count, entropy); 141252190Srpaulo 142252190Srpaulo os_get_time(&t); 143252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random pool", 144252190Srpaulo (const u8 *) pool, sizeof(pool)); 145252190Srpaulo random_mix_pool(&t, sizeof(t)); 146252190Srpaulo random_mix_pool(buf, len); 147252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random pool", 148252190Srpaulo (const u8 *) pool, sizeof(pool)); 149252190Srpaulo entropy++; 150252190Srpaulo total_collected++; 151252190Srpaulo} 152252190Srpaulo 153252190Srpaulo 154252190Srpauloint random_get_bytes(void *buf, size_t len) 155252190Srpaulo{ 156252190Srpaulo int ret; 157252190Srpaulo u8 *bytes = buf; 158252190Srpaulo size_t left; 159252190Srpaulo 160252190Srpaulo wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u", 161252190Srpaulo (unsigned int) len, entropy); 162252190Srpaulo 163252190Srpaulo /* Start with assumed strong randomness from OS */ 164252190Srpaulo ret = os_get_random(buf, len); 165252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random", 166252190Srpaulo buf, len); 167252190Srpaulo 168252190Srpaulo /* Mix in additional entropy extracted from the internal pool */ 169252190Srpaulo left = len; 170252190Srpaulo while (left) { 171252190Srpaulo size_t siz, i; 172252190Srpaulo u8 tmp[EXTRACT_LEN]; 173252190Srpaulo random_extract(tmp); 174252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool", 175252190Srpaulo tmp, sizeof(tmp)); 176252190Srpaulo siz = left > EXTRACT_LEN ? EXTRACT_LEN : left; 177252190Srpaulo for (i = 0; i < siz; i++) 178252190Srpaulo *bytes++ ^= tmp[i]; 179252190Srpaulo left -= siz; 180252190Srpaulo } 181252190Srpaulo 182252190Srpaulo#ifdef CONFIG_FIPS 183252190Srpaulo /* Mix in additional entropy from the crypto module */ 184252190Srpaulo left = len; 185252190Srpaulo while (left) { 186252190Srpaulo size_t siz, i; 187252190Srpaulo u8 tmp[EXTRACT_LEN]; 188252190Srpaulo if (crypto_get_random(tmp, sizeof(tmp)) < 0) { 189252190Srpaulo wpa_printf(MSG_ERROR, "random: No entropy available " 190252190Srpaulo "for generating strong random bytes"); 191252190Srpaulo return -1; 192252190Srpaulo } 193252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto module", 194252190Srpaulo tmp, sizeof(tmp)); 195252190Srpaulo siz = left > EXTRACT_LEN ? EXTRACT_LEN : left; 196252190Srpaulo for (i = 0; i < siz; i++) 197252190Srpaulo *bytes++ ^= tmp[i]; 198252190Srpaulo left -= siz; 199252190Srpaulo } 200252190Srpaulo#endif /* CONFIG_FIPS */ 201252190Srpaulo 202252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len); 203252190Srpaulo 204252190Srpaulo if (entropy < len) 205252190Srpaulo entropy = 0; 206252190Srpaulo else 207252190Srpaulo entropy -= len; 208252190Srpaulo 209252190Srpaulo return ret; 210252190Srpaulo} 211252190Srpaulo 212252190Srpaulo 213252190Srpauloint random_pool_ready(void) 214252190Srpaulo{ 215252190Srpaulo#ifdef __linux__ 216252190Srpaulo int fd; 217252190Srpaulo ssize_t res; 218252190Srpaulo 219252190Srpaulo /* 220252190Srpaulo * Make sure that there is reasonable entropy available before allowing 221252190Srpaulo * some key derivation operations to proceed. 222252190Srpaulo */ 223252190Srpaulo 224252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) 225252190Srpaulo return 1; /* Already initialized - good to continue */ 226252190Srpaulo 227252190Srpaulo /* 228252190Srpaulo * Try to fetch some more data from the kernel high quality 229252190Srpaulo * /dev/random. There may not be enough data available at this point, 230252190Srpaulo * so use non-blocking read to avoid blocking the application 231252190Srpaulo * completely. 232252190Srpaulo */ 233252190Srpaulo fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 234252190Srpaulo if (fd < 0) { 235252190Srpaulo#ifndef CONFIG_NO_STDOUT_DEBUG 236252190Srpaulo int error = errno; 237252190Srpaulo perror("open(/dev/random)"); 238252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 239252190Srpaulo strerror(error)); 240252190Srpaulo#endif /* CONFIG_NO_STDOUT_DEBUG */ 241252190Srpaulo return -1; 242252190Srpaulo } 243252190Srpaulo 244252190Srpaulo res = read(fd, dummy_key + dummy_key_avail, 245252190Srpaulo sizeof(dummy_key) - dummy_key_avail); 246252190Srpaulo if (res < 0) { 247252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 248252190Srpaulo "%s", strerror(errno)); 249252190Srpaulo res = 0; 250252190Srpaulo } 251252190Srpaulo wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from " 252252190Srpaulo "/dev/random", (unsigned) res, 253252190Srpaulo (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 254252190Srpaulo dummy_key_avail += res; 255252190Srpaulo close(fd); 256252190Srpaulo 257252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) { 258252190Srpaulo if (own_pool_ready < MIN_READY_MARK) 259252190Srpaulo own_pool_ready = MIN_READY_MARK; 260252190Srpaulo random_write_entropy(); 261252190Srpaulo return 1; 262252190Srpaulo } 263252190Srpaulo 264252190Srpaulo wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong " 265252190Srpaulo "random data available from /dev/random", 266252190Srpaulo (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key)); 267252190Srpaulo 268252190Srpaulo if (own_pool_ready >= MIN_READY_MARK || 269252190Srpaulo total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) { 270252190Srpaulo wpa_printf(MSG_INFO, "random: Allow operation to proceed " 271252190Srpaulo "based on internal entropy"); 272252190Srpaulo return 1; 273252190Srpaulo } 274252190Srpaulo 275252190Srpaulo wpa_printf(MSG_INFO, "random: Not enough entropy pool available for " 276252190Srpaulo "secure operations"); 277252190Srpaulo return 0; 278252190Srpaulo#else /* __linux__ */ 279252190Srpaulo /* TODO: could do similar checks on non-Linux platforms */ 280252190Srpaulo return 1; 281252190Srpaulo#endif /* __linux__ */ 282252190Srpaulo} 283252190Srpaulo 284252190Srpaulo 285252190Srpaulovoid random_mark_pool_ready(void) 286252190Srpaulo{ 287252190Srpaulo own_pool_ready++; 288252190Srpaulo wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be " 289252190Srpaulo "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK); 290252190Srpaulo random_write_entropy(); 291252190Srpaulo} 292252190Srpaulo 293252190Srpaulo 294252190Srpaulo#ifdef __linux__ 295252190Srpaulo 296252190Srpaulostatic void random_close_fd(void) 297252190Srpaulo{ 298252190Srpaulo if (random_fd >= 0) { 299252190Srpaulo eloop_unregister_read_sock(random_fd); 300252190Srpaulo close(random_fd); 301252190Srpaulo random_fd = -1; 302252190Srpaulo } 303252190Srpaulo} 304252190Srpaulo 305252190Srpaulo 306252190Srpaulostatic void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx) 307252190Srpaulo{ 308252190Srpaulo ssize_t res; 309252190Srpaulo 310252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) { 311252190Srpaulo random_close_fd(); 312252190Srpaulo return; 313252190Srpaulo } 314252190Srpaulo 315252190Srpaulo res = read(sock, dummy_key + dummy_key_avail, 316252190Srpaulo sizeof(dummy_key) - dummy_key_avail); 317252190Srpaulo if (res < 0) { 318252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 319252190Srpaulo "%s", strerror(errno)); 320252190Srpaulo return; 321252190Srpaulo } 322252190Srpaulo 323252190Srpaulo wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random", 324252190Srpaulo (unsigned) res, 325252190Srpaulo (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 326252190Srpaulo dummy_key_avail += res; 327252190Srpaulo 328252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) { 329252190Srpaulo random_close_fd(); 330252190Srpaulo if (own_pool_ready < MIN_READY_MARK) 331252190Srpaulo own_pool_ready = MIN_READY_MARK; 332252190Srpaulo random_write_entropy(); 333252190Srpaulo } 334252190Srpaulo} 335252190Srpaulo 336252190Srpaulo#endif /* __linux__ */ 337252190Srpaulo 338252190Srpaulo 339252190Srpaulostatic void random_read_entropy(void) 340252190Srpaulo{ 341252190Srpaulo char *buf; 342252190Srpaulo size_t len; 343252190Srpaulo 344252190Srpaulo if (!random_entropy_file) 345252190Srpaulo return; 346252190Srpaulo 347252190Srpaulo buf = os_readfile(random_entropy_file, &len); 348252190Srpaulo if (buf == NULL) 349252190Srpaulo return; /* entropy file not yet available */ 350252190Srpaulo 351252190Srpaulo if (len != 1 + RANDOM_ENTROPY_SIZE) { 352252190Srpaulo wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s", 353252190Srpaulo random_entropy_file); 354252190Srpaulo os_free(buf); 355252190Srpaulo return; 356252190Srpaulo } 357252190Srpaulo 358252190Srpaulo own_pool_ready = (u8) buf[0]; 359252190Srpaulo random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE); 360252190Srpaulo random_entropy_file_read = 1; 361252190Srpaulo os_free(buf); 362252190Srpaulo wpa_printf(MSG_DEBUG, "random: Added entropy from %s " 363252190Srpaulo "(own_pool_ready=%u)", 364252190Srpaulo random_entropy_file, own_pool_ready); 365252190Srpaulo} 366252190Srpaulo 367252190Srpaulo 368252190Srpaulostatic void random_write_entropy(void) 369252190Srpaulo{ 370252190Srpaulo char buf[RANDOM_ENTROPY_SIZE]; 371252190Srpaulo FILE *f; 372252190Srpaulo u8 opr; 373252190Srpaulo int fail = 0; 374252190Srpaulo 375252190Srpaulo if (!random_entropy_file) 376252190Srpaulo return; 377252190Srpaulo 378252190Srpaulo if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0) 379252190Srpaulo return; 380252190Srpaulo 381252190Srpaulo f = fopen(random_entropy_file, "wb"); 382252190Srpaulo if (f == NULL) { 383252190Srpaulo wpa_printf(MSG_ERROR, "random: Could not open entropy file %s " 384252190Srpaulo "for writing", random_entropy_file); 385252190Srpaulo return; 386252190Srpaulo } 387252190Srpaulo 388252190Srpaulo opr = own_pool_ready > 0xff ? 0xff : own_pool_ready; 389252190Srpaulo if (fwrite(&opr, 1, 1, f) != 1 || 390252190Srpaulo fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1) 391252190Srpaulo fail = 1; 392252190Srpaulo fclose(f); 393252190Srpaulo if (fail) { 394252190Srpaulo wpa_printf(MSG_ERROR, "random: Could not write entropy data " 395252190Srpaulo "to %s", random_entropy_file); 396252190Srpaulo return; 397252190Srpaulo } 398252190Srpaulo 399252190Srpaulo wpa_printf(MSG_DEBUG, "random: Updated entropy file %s " 400252190Srpaulo "(own_pool_ready=%u)", 401252190Srpaulo random_entropy_file, own_pool_ready); 402252190Srpaulo} 403252190Srpaulo 404252190Srpaulo 405252190Srpaulovoid random_init(const char *entropy_file) 406252190Srpaulo{ 407252190Srpaulo os_free(random_entropy_file); 408252190Srpaulo if (entropy_file) 409252190Srpaulo random_entropy_file = os_strdup(entropy_file); 410252190Srpaulo else 411252190Srpaulo random_entropy_file = NULL; 412252190Srpaulo random_read_entropy(); 413252190Srpaulo 414252190Srpaulo#ifdef __linux__ 415252190Srpaulo if (random_fd >= 0) 416252190Srpaulo return; 417252190Srpaulo 418252190Srpaulo random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 419252190Srpaulo if (random_fd < 0) { 420252190Srpaulo#ifndef CONFIG_NO_STDOUT_DEBUG 421252190Srpaulo int error = errno; 422252190Srpaulo perror("open(/dev/random)"); 423252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 424252190Srpaulo strerror(error)); 425252190Srpaulo#endif /* CONFIG_NO_STDOUT_DEBUG */ 426252190Srpaulo return; 427252190Srpaulo } 428252190Srpaulo wpa_printf(MSG_DEBUG, "random: Trying to read entropy from " 429252190Srpaulo "/dev/random"); 430252190Srpaulo 431252190Srpaulo eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL); 432252190Srpaulo#endif /* __linux__ */ 433252190Srpaulo 434252190Srpaulo random_write_entropy(); 435252190Srpaulo} 436252190Srpaulo 437252190Srpaulo 438252190Srpaulovoid random_deinit(void) 439252190Srpaulo{ 440252190Srpaulo#ifdef __linux__ 441252190Srpaulo random_close_fd(); 442252190Srpaulo#endif /* __linux__ */ 443252190Srpaulo random_write_entropy(); 444252190Srpaulo os_free(random_entropy_file); 445252190Srpaulo random_entropy_file = NULL; 446252190Srpaulo} 447