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