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 */ 184289549Srpaulo bytes = buf; 185252190Srpaulo left = len; 186252190Srpaulo while (left) { 187252190Srpaulo size_t siz, i; 188252190Srpaulo u8 tmp[EXTRACT_LEN]; 189252190Srpaulo if (crypto_get_random(tmp, sizeof(tmp)) < 0) { 190252190Srpaulo wpa_printf(MSG_ERROR, "random: No entropy available " 191252190Srpaulo "for generating strong random bytes"); 192252190Srpaulo return -1; 193252190Srpaulo } 194252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto module", 195252190Srpaulo tmp, sizeof(tmp)); 196252190Srpaulo siz = left > EXTRACT_LEN ? EXTRACT_LEN : left; 197252190Srpaulo for (i = 0; i < siz; i++) 198252190Srpaulo *bytes++ ^= tmp[i]; 199252190Srpaulo left -= siz; 200252190Srpaulo } 201252190Srpaulo#endif /* CONFIG_FIPS */ 202252190Srpaulo 203252190Srpaulo wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len); 204252190Srpaulo 205252190Srpaulo if (entropy < len) 206252190Srpaulo entropy = 0; 207252190Srpaulo else 208252190Srpaulo entropy -= len; 209252190Srpaulo 210252190Srpaulo return ret; 211252190Srpaulo} 212252190Srpaulo 213252190Srpaulo 214252190Srpauloint random_pool_ready(void) 215252190Srpaulo{ 216252190Srpaulo#ifdef __linux__ 217252190Srpaulo int fd; 218252190Srpaulo ssize_t res; 219252190Srpaulo 220252190Srpaulo /* 221252190Srpaulo * Make sure that there is reasonable entropy available before allowing 222252190Srpaulo * some key derivation operations to proceed. 223252190Srpaulo */ 224252190Srpaulo 225252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) 226252190Srpaulo return 1; /* Already initialized - good to continue */ 227252190Srpaulo 228252190Srpaulo /* 229252190Srpaulo * Try to fetch some more data from the kernel high quality 230252190Srpaulo * /dev/random. There may not be enough data available at this point, 231252190Srpaulo * so use non-blocking read to avoid blocking the application 232252190Srpaulo * completely. 233252190Srpaulo */ 234252190Srpaulo fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 235252190Srpaulo if (fd < 0) { 236252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 237281806Srpaulo strerror(errno)); 238252190Srpaulo return -1; 239252190Srpaulo } 240252190Srpaulo 241252190Srpaulo res = read(fd, dummy_key + dummy_key_avail, 242252190Srpaulo sizeof(dummy_key) - dummy_key_avail); 243252190Srpaulo if (res < 0) { 244252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 245252190Srpaulo "%s", strerror(errno)); 246252190Srpaulo res = 0; 247252190Srpaulo } 248252190Srpaulo wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from " 249252190Srpaulo "/dev/random", (unsigned) res, 250252190Srpaulo (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 251252190Srpaulo dummy_key_avail += res; 252252190Srpaulo close(fd); 253252190Srpaulo 254252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) { 255252190Srpaulo if (own_pool_ready < MIN_READY_MARK) 256252190Srpaulo own_pool_ready = MIN_READY_MARK; 257252190Srpaulo random_write_entropy(); 258252190Srpaulo return 1; 259252190Srpaulo } 260252190Srpaulo 261252190Srpaulo wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong " 262252190Srpaulo "random data available from /dev/random", 263252190Srpaulo (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key)); 264252190Srpaulo 265252190Srpaulo if (own_pool_ready >= MIN_READY_MARK || 266252190Srpaulo total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) { 267252190Srpaulo wpa_printf(MSG_INFO, "random: Allow operation to proceed " 268252190Srpaulo "based on internal entropy"); 269252190Srpaulo return 1; 270252190Srpaulo } 271252190Srpaulo 272252190Srpaulo wpa_printf(MSG_INFO, "random: Not enough entropy pool available for " 273252190Srpaulo "secure operations"); 274252190Srpaulo return 0; 275252190Srpaulo#else /* __linux__ */ 276252190Srpaulo /* TODO: could do similar checks on non-Linux platforms */ 277252190Srpaulo return 1; 278252190Srpaulo#endif /* __linux__ */ 279252190Srpaulo} 280252190Srpaulo 281252190Srpaulo 282252190Srpaulovoid random_mark_pool_ready(void) 283252190Srpaulo{ 284252190Srpaulo own_pool_ready++; 285252190Srpaulo wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be " 286252190Srpaulo "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK); 287252190Srpaulo random_write_entropy(); 288252190Srpaulo} 289252190Srpaulo 290252190Srpaulo 291252190Srpaulo#ifdef __linux__ 292252190Srpaulo 293252190Srpaulostatic void random_close_fd(void) 294252190Srpaulo{ 295252190Srpaulo if (random_fd >= 0) { 296252190Srpaulo eloop_unregister_read_sock(random_fd); 297252190Srpaulo close(random_fd); 298252190Srpaulo random_fd = -1; 299252190Srpaulo } 300252190Srpaulo} 301252190Srpaulo 302252190Srpaulo 303252190Srpaulostatic void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx) 304252190Srpaulo{ 305252190Srpaulo ssize_t res; 306252190Srpaulo 307252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) { 308252190Srpaulo random_close_fd(); 309252190Srpaulo return; 310252190Srpaulo } 311252190Srpaulo 312252190Srpaulo res = read(sock, dummy_key + dummy_key_avail, 313252190Srpaulo sizeof(dummy_key) - dummy_key_avail); 314252190Srpaulo if (res < 0) { 315252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 316252190Srpaulo "%s", strerror(errno)); 317252190Srpaulo return; 318252190Srpaulo } 319252190Srpaulo 320252190Srpaulo wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random", 321252190Srpaulo (unsigned) res, 322252190Srpaulo (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 323252190Srpaulo dummy_key_avail += res; 324252190Srpaulo 325252190Srpaulo if (dummy_key_avail == sizeof(dummy_key)) { 326252190Srpaulo random_close_fd(); 327252190Srpaulo if (own_pool_ready < MIN_READY_MARK) 328252190Srpaulo own_pool_ready = MIN_READY_MARK; 329252190Srpaulo random_write_entropy(); 330252190Srpaulo } 331252190Srpaulo} 332252190Srpaulo 333252190Srpaulo#endif /* __linux__ */ 334252190Srpaulo 335252190Srpaulo 336252190Srpaulostatic void random_read_entropy(void) 337252190Srpaulo{ 338252190Srpaulo char *buf; 339252190Srpaulo size_t len; 340252190Srpaulo 341252190Srpaulo if (!random_entropy_file) 342252190Srpaulo return; 343252190Srpaulo 344252190Srpaulo buf = os_readfile(random_entropy_file, &len); 345252190Srpaulo if (buf == NULL) 346252190Srpaulo return; /* entropy file not yet available */ 347252190Srpaulo 348252190Srpaulo if (len != 1 + RANDOM_ENTROPY_SIZE) { 349252190Srpaulo wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s", 350252190Srpaulo random_entropy_file); 351252190Srpaulo os_free(buf); 352252190Srpaulo return; 353252190Srpaulo } 354252190Srpaulo 355252190Srpaulo own_pool_ready = (u8) buf[0]; 356252190Srpaulo random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE); 357252190Srpaulo random_entropy_file_read = 1; 358252190Srpaulo os_free(buf); 359252190Srpaulo wpa_printf(MSG_DEBUG, "random: Added entropy from %s " 360252190Srpaulo "(own_pool_ready=%u)", 361252190Srpaulo random_entropy_file, own_pool_ready); 362252190Srpaulo} 363252190Srpaulo 364252190Srpaulo 365252190Srpaulostatic void random_write_entropy(void) 366252190Srpaulo{ 367252190Srpaulo char buf[RANDOM_ENTROPY_SIZE]; 368252190Srpaulo FILE *f; 369252190Srpaulo u8 opr; 370252190Srpaulo int fail = 0; 371252190Srpaulo 372252190Srpaulo if (!random_entropy_file) 373252190Srpaulo return; 374252190Srpaulo 375252190Srpaulo if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0) 376252190Srpaulo return; 377252190Srpaulo 378252190Srpaulo f = fopen(random_entropy_file, "wb"); 379252190Srpaulo if (f == NULL) { 380252190Srpaulo wpa_printf(MSG_ERROR, "random: Could not open entropy file %s " 381252190Srpaulo "for writing", random_entropy_file); 382252190Srpaulo return; 383252190Srpaulo } 384252190Srpaulo 385252190Srpaulo opr = own_pool_ready > 0xff ? 0xff : own_pool_ready; 386252190Srpaulo if (fwrite(&opr, 1, 1, f) != 1 || 387252190Srpaulo fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1) 388252190Srpaulo fail = 1; 389252190Srpaulo fclose(f); 390252190Srpaulo if (fail) { 391252190Srpaulo wpa_printf(MSG_ERROR, "random: Could not write entropy data " 392252190Srpaulo "to %s", random_entropy_file); 393252190Srpaulo return; 394252190Srpaulo } 395252190Srpaulo 396252190Srpaulo wpa_printf(MSG_DEBUG, "random: Updated entropy file %s " 397252190Srpaulo "(own_pool_ready=%u)", 398252190Srpaulo random_entropy_file, own_pool_ready); 399252190Srpaulo} 400252190Srpaulo 401252190Srpaulo 402252190Srpaulovoid random_init(const char *entropy_file) 403252190Srpaulo{ 404252190Srpaulo os_free(random_entropy_file); 405252190Srpaulo if (entropy_file) 406252190Srpaulo random_entropy_file = os_strdup(entropy_file); 407252190Srpaulo else 408252190Srpaulo random_entropy_file = NULL; 409252190Srpaulo random_read_entropy(); 410252190Srpaulo 411252190Srpaulo#ifdef __linux__ 412252190Srpaulo if (random_fd >= 0) 413252190Srpaulo return; 414252190Srpaulo 415252190Srpaulo random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 416252190Srpaulo if (random_fd < 0) { 417252190Srpaulo wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 418281806Srpaulo strerror(errno)); 419252190Srpaulo return; 420252190Srpaulo } 421252190Srpaulo wpa_printf(MSG_DEBUG, "random: Trying to read entropy from " 422252190Srpaulo "/dev/random"); 423252190Srpaulo 424252190Srpaulo eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL); 425252190Srpaulo#endif /* __linux__ */ 426252190Srpaulo 427252190Srpaulo random_write_entropy(); 428252190Srpaulo} 429252190Srpaulo 430252190Srpaulo 431252190Srpaulovoid random_deinit(void) 432252190Srpaulo{ 433252190Srpaulo#ifdef __linux__ 434252190Srpaulo random_close_fd(); 435252190Srpaulo#endif /* __linux__ */ 436252190Srpaulo random_write_entropy(); 437252190Srpaulo os_free(random_entropy_file); 438252190Srpaulo random_entropy_file = NULL; 439252190Srpaulo} 440