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