1 /* 2 * Random number generator 3 * Copyright (c) 2010-2011, Jouni Malinen <j (at) w1.fi> 4 * 5 * This software may be distributed under the terms of the BSD license. 6 * See README for more details. 7 * 8 * This random number generator is used to provide additional entropy to the 9 * one provided by the operating system (os_get_random()) for session key 10 * generation. The os_get_random() output is expected to be secure and the 11 * implementation here is expected to provide only limited protection against 12 * cases where os_get_random() cannot provide strong randomness. This 13 * implementation shall not be assumed to be secure as the sole source of 14 * randomness. The random_get_bytes() function mixes in randomness from 15 * os_get_random() and as such, calls to os_get_random() can be replaced with 16 * calls to random_get_bytes() without reducing security. 17 * 18 * The design here follows partially the design used in the Linux 19 * drivers/char/random.c, but the implementation here is simpler and not as 20 * strong. This is a compromise to reduce duplicated CPU effort and to avoid 21 * extra code/memory size. As pointed out above, os_get_random() needs to be 22 * guaranteed to be secure for any of the security assumptions to hold. 23 */ 24 25 #include "utils/includes.h" 26 #ifdef __linux__ 27 #include <fcntl.h> 28 #ifdef CONFIG_GETRANDOM 29 #include <sys/random.h> 30 #endif /* CONFIG_GETRANDOM */ 31 #endif /* __linux__ */ 32 33 #include "utils/common.h" 34 #include "utils/eloop.h" 35 #include "crypto/crypto.h" 36 #include "sha1.h" 37 #include "random.h" 38 39 #define POOL_WORDS 32 40 #define POOL_WORDS_MASK (POOL_WORDS - 1) 41 #define POOL_TAP1 26 42 #define POOL_TAP2 20 43 #define POOL_TAP3 14 44 #define POOL_TAP4 7 45 #define POOL_TAP5 1 46 #define EXTRACT_LEN 16 47 #define MIN_READY_MARK 2 48 49 static u32 pool[POOL_WORDS]; 50 static unsigned int input_rotate = 0; 51 static unsigned int pool_pos = 0; 52 static u8 dummy_key[20]; 53 #ifdef __linux__ 54 static size_t dummy_key_avail = 0; 55 static int random_fd = -1; 56 #endif /* __linux__ */ 57 static unsigned int own_pool_ready = 0; 58 #define RANDOM_ENTROPY_SIZE 20 59 static char *random_entropy_file = NULL; 60 61 #define MIN_COLLECT_ENTROPY 1000 62 static unsigned int entropy = 0; 63 static unsigned int total_collected = 0; 64 65 66 static void random_write_entropy(void); 67 68 69 static u32 __ROL32(u32 x, u32 y) 70 { 71 if (y == 0) 72 return x; 73 74 return (x << (y & 31)) | (x >> (32 - (y & 31))); 75 } 76 77 78 static void random_mix_pool(const void *buf, size_t len) 79 { 80 static const u32 twist[8] = { 81 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 82 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 83 }; 84 const u8 *pos = buf; 85 u32 w; 86 87 wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len); 88 89 while (len--) { 90 w = __ROL32(*pos++, input_rotate & 31); 91 input_rotate += pool_pos ? 7 : 14; 92 pool_pos = (pool_pos - 1) & POOL_WORDS_MASK; 93 w ^= pool[pool_pos]; 94 w ^= pool[(pool_pos + POOL_TAP1) & POOL_WORDS_MASK]; 95 w ^= pool[(pool_pos + POOL_TAP2) & POOL_WORDS_MASK]; 96 w ^= pool[(pool_pos + POOL_TAP3) & POOL_WORDS_MASK]; 97 w ^= pool[(pool_pos + POOL_TAP4) & POOL_WORDS_MASK]; 98 w ^= pool[(pool_pos + POOL_TAP5) & POOL_WORDS_MASK]; 99 pool[pool_pos] = (w >> 3) ^ twist[w & 7]; 100 } 101 } 102 103 104 static void random_extract(u8 *out) 105 { 106 unsigned int i; 107 u8 hash[SHA1_MAC_LEN]; 108 u32 *hash_ptr; 109 u32 buf[POOL_WORDS / 2]; 110 111 /* First, add hash back to pool to make backtracking more difficult. */ 112 hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) pool, 113 sizeof(pool), hash); 114 random_mix_pool(hash, sizeof(hash)); 115 /* Hash half the pool to extra data */ 116 for (i = 0; i < POOL_WORDS / 2; i++) 117 buf[i] = pool[(pool_pos - i) & POOL_WORDS_MASK]; 118 hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) buf, 119 sizeof(buf), hash); 120 /* 121 * Fold the hash to further reduce any potential output pattern. 122 * Though, compromise this to reduce CPU use for the most common output 123 * length (32) and return 16 bytes from instead of only half. 124 */ 125 hash_ptr = (u32 *) hash; 126 hash_ptr[0] ^= hash_ptr[4]; 127 os_memcpy(out, hash, EXTRACT_LEN); 128 } 129 130 131 void random_add_randomness(const void *buf, size_t len) 132 { 133 struct os_time t; 134 static unsigned int count = 0; 135 136 count++; 137 if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) { 138 /* 139 * No need to add more entropy at this point, so save CPU and 140 * skip the update. 141 */ 142 return; 143 } 144 wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u", 145 count, entropy); 146 147 os_get_time(&t); 148 wpa_hexdump_key(MSG_EXCESSIVE, "random pool", 149 (const u8 *) pool, sizeof(pool)); 150 random_mix_pool(&t, sizeof(t)); 151 random_mix_pool(buf, len); 152 wpa_hexdump_key(MSG_EXCESSIVE, "random pool", 153 (const u8 *) pool, sizeof(pool)); 154 entropy++; 155 total_collected++; 156 } 157 158 159 int random_get_bytes(void *buf, size_t len) 160 { 161 int ret; 162 u8 *bytes = buf; 163 size_t left; 164 165 wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u", 166 (unsigned int) len, entropy); 167 168 #ifdef CONFIG_USE_OPENSSL_RNG 169 /* Start with assumed strong randomness from OpenSSL */ 170 ret = crypto_get_random(buf, len); 171 wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto_get_random", 172 buf, len); 173 #else /* CONFIG_USE_OPENSSL_RNG */ 174 /* Start with assumed strong randomness from OS */ 175 ret = os_get_random(buf, len); 176 wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random", 177 buf, len); 178 #endif /* CONFIG_USE_OPENSSL_RNG */ 179 180 /* Mix in additional entropy extracted from the internal pool */ 181 left = len; 182 while (left) { 183 size_t siz, i; 184 u8 tmp[EXTRACT_LEN]; 185 random_extract(tmp); 186 wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool", 187 tmp, sizeof(tmp)); 188 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left; 189 for (i = 0; i < siz; i++) 190 *bytes++ ^= tmp[i]; 191 left -= siz; 192 } 193 194 #ifdef CONFIG_FIPS 195 /* Mix in additional entropy from the crypto module */ 196 bytes = buf; 197 left = len; 198 while (left) { 199 size_t siz, i; 200 u8 tmp[EXTRACT_LEN]; 201 if (crypto_get_random(tmp, sizeof(tmp)) < 0) { 202 wpa_printf(MSG_ERROR, "random: No entropy available " 203 "for generating strong random bytes"); 204 return -1; 205 } 206 wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto module", 207 tmp, sizeof(tmp)); 208 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left; 209 for (i = 0; i < siz; i++) 210 *bytes++ ^= tmp[i]; 211 left -= siz; 212 } 213 #endif /* CONFIG_FIPS */ 214 215 wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len); 216 217 if (entropy < len) 218 entropy = 0; 219 else 220 entropy -= len; 221 222 return ret; 223 } 224 225 226 int random_pool_ready(void) 227 { 228 #ifdef __linux__ 229 int fd; 230 ssize_t res; 231 232 /* 233 * Make sure that there is reasonable entropy available before allowing 234 * some key derivation operations to proceed. 235 */ 236 237 if (dummy_key_avail == sizeof(dummy_key)) 238 return 1; /* Already initialized - good to continue */ 239 240 /* 241 * Try to fetch some more data from the kernel high quality RNG. 242 * There may not be enough data available at this point, 243 * so use non-blocking read to avoid blocking the application 244 * completely. 245 */ 246 247 #ifdef CONFIG_GETRANDOM 248 res = getrandom(dummy_key + dummy_key_avail, 249 sizeof(dummy_key) - dummy_key_avail, GRND_NONBLOCK); 250 if (res < 0) { 251 if (errno == ENOSYS) { 252 wpa_printf(MSG_DEBUG, 253 "random: getrandom() not supported, falling back to /dev/random"); 254 } else { 255 wpa_printf(MSG_INFO, 256 "random: no data from getrandom(): %s", 257 strerror(errno)); 258 res = 0; 259 } 260 } 261 #else /* CONFIG_GETRANDOM */ 262 res = -1; 263 #endif /* CONFIG_GETRANDOM */ 264 if (res < 0) { 265 fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 266 if (fd < 0) { 267 wpa_printf(MSG_ERROR, 268 "random: Cannot open /dev/random: %s", 269 strerror(errno)); 270 return -1; 271 } 272 273 res = read(fd, dummy_key + dummy_key_avail, 274 sizeof(dummy_key) - dummy_key_avail); 275 if (res < 0) { 276 wpa_printf(MSG_ERROR, 277 "random: Cannot read from /dev/random: %s", 278 strerror(errno)); 279 res = 0; 280 } 281 close(fd); 282 } 283 284 wpa_printf(MSG_DEBUG, "random: Got %u/%u random bytes", (unsigned) res, 285 (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 286 dummy_key_avail += res; 287 288 if (dummy_key_avail == sizeof(dummy_key)) { 289 if (own_pool_ready < MIN_READY_MARK) 290 own_pool_ready = MIN_READY_MARK; 291 random_write_entropy(); 292 return 1; 293 } 294 295 wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong " 296 "random data available", 297 (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key)); 298 299 if (own_pool_ready >= MIN_READY_MARK || 300 total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) { 301 wpa_printf(MSG_INFO, "random: Allow operation to proceed " 302 "based on internal entropy"); 303 return 1; 304 } 305 306 wpa_printf(MSG_INFO, "random: Not enough entropy pool available for " 307 "secure operations"); 308 return 0; 309 #else /* __linux__ */ 310 /* TODO: could do similar checks on non-Linux platforms */ 311 return 1; 312 #endif /* __linux__ */ 313 } 314 315 316 void random_mark_pool_ready(void) 317 { 318 own_pool_ready++; 319 wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be " 320 "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK); 321 random_write_entropy(); 322 } 323 324 325 #ifdef __linux__ 326 327 static void random_close_fd(void) 328 { 329 if (random_fd >= 0) { 330 eloop_unregister_read_sock(random_fd); 331 close(random_fd); 332 random_fd = -1; 333 } 334 } 335 336 337 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx) 338 { 339 ssize_t res; 340 341 if (dummy_key_avail == sizeof(dummy_key)) { 342 random_close_fd(); 343 return; 344 } 345 346 res = read(sock, dummy_key + dummy_key_avail, 347 sizeof(dummy_key) - dummy_key_avail); 348 if (res < 0) { 349 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 350 "%s", strerror(errno)); 351 return; 352 } 353 354 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random", 355 (unsigned) res, 356 (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 357 dummy_key_avail += res; 358 359 if (dummy_key_avail == sizeof(dummy_key)) { 360 random_close_fd(); 361 if (own_pool_ready < MIN_READY_MARK) 362 own_pool_ready = MIN_READY_MARK; 363 random_write_entropy(); 364 } 365 } 366 367 #endif /* __linux__ */ 368 369 370 static void random_read_entropy(void) 371 { 372 char *buf; 373 size_t len; 374 375 if (!random_entropy_file) 376 return; 377 378 buf = os_readfile(random_entropy_file, &len); 379 if (buf == NULL) 380 return; /* entropy file not yet available */ 381 382 if (len != 1 + RANDOM_ENTROPY_SIZE) { 383 wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s", 384 random_entropy_file); 385 os_free(buf); 386 return; 387 } 388 389 own_pool_ready = (u8) buf[0]; 390 random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE); 391 os_free(buf); 392 wpa_printf(MSG_DEBUG, "random: Added entropy from %s " 393 "(own_pool_ready=%u)", 394 random_entropy_file, own_pool_ready); 395 } 396 397 398 static void random_write_entropy(void) 399 { 400 char buf[RANDOM_ENTROPY_SIZE]; 401 FILE *f; 402 u8 opr; 403 int fail = 0; 404 405 if (!random_entropy_file) 406 return; 407 408 if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0) 409 return; 410 411 f = fopen(random_entropy_file, "wb"); 412 if (f == NULL) { 413 wpa_printf(MSG_ERROR, "random: Could not open entropy file %s " 414 "for writing", random_entropy_file); 415 return; 416 } 417 418 opr = own_pool_ready > 0xff ? 0xff : own_pool_ready; 419 if (fwrite(&opr, 1, 1, f) != 1 || 420 fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1) 421 fail = 1; 422 fclose(f); 423 if (fail) { 424 wpa_printf(MSG_ERROR, "random: Could not write entropy data " 425 "to %s", random_entropy_file); 426 return; 427 } 428 429 wpa_printf(MSG_DEBUG, "random: Updated entropy file %s " 430 "(own_pool_ready=%u)", 431 random_entropy_file, own_pool_ready); 432 } 433 434 435 void random_init(const char *entropy_file) 436 { 437 os_free(random_entropy_file); 438 if (entropy_file) 439 random_entropy_file = os_strdup(entropy_file); 440 else 441 random_entropy_file = NULL; 442 random_read_entropy(); 443 444 #ifdef __linux__ 445 if (random_fd >= 0) 446 return; 447 448 #ifdef CONFIG_GETRANDOM 449 { 450 u8 dummy; 451 452 if (getrandom(&dummy, 0, GRND_NONBLOCK) == 0 || 453 errno != ENOSYS) { 454 wpa_printf(MSG_DEBUG, 455 "random: getrandom() support available"); 456 return; 457 } 458 } 459 #endif /* CONFIG_GETRANDOM */ 460 461 random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 462 if (random_fd < 0) { 463 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 464 strerror(errno)); 465 return; 466 } 467 wpa_printf(MSG_DEBUG, "random: Trying to read entropy from " 468 "/dev/random"); 469 470 eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL); 471 #endif /* __linux__ */ 472 473 random_write_entropy(); 474 } 475 476 477 void random_deinit(void) 478 { 479 #ifdef __linux__ 480 random_close_fd(); 481 #endif /* __linux__ */ 482 random_write_entropy(); 483 os_free(random_entropy_file); 484 random_entropy_file = NULL; 485 } 486
