1 /* 2 * Random number generator 3 * Copyright (c) 2010-2011, Jouni Malinen <j (at) w1.fi> 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License version 2 as 7 * published by the Free Software Foundation. 8 * 9 * Alternatively, this software may be distributed under the terms of BSD 10 * license. 11 * 12 * See README and COPYING for more details. 13 * 14 * This random number generator is used to provide additional entropy to the 15 * one provided by the operating system (os_get_random()) for session key 16 * generation. The os_get_random() output is expected to be secure and the 17 * implementation here is expected to provide only limited protection against 18 * cases where os_get_random() cannot provide strong randomness. This 19 * implementation shall not be assumed to be secure as the sole source of 20 * randomness. The random_get_bytes() function mixes in randomness from 21 * os_get_random() and as such, calls to os_get_random() can be replaced with 22 * calls to random_get_bytes() without reducing security. 23 * 24 * The design here follows partially the design used in the Linux 25 * drivers/char/random.c, but the implementation here is simpler and not as 26 * strong. This is a compromise to reduce duplicated CPU effort and to avoid 27 * extra code/memory size. As pointed out above, os_get_random() needs to be 28 * guaranteed to be secure for any of the security assumptions to hold. 29 */ 30 31 #include "utils/includes.h" 32 #ifdef __linux__ 33 #include <fcntl.h> 34 #endif /* __linux__ */ 35 36 #include "utils/common.h" 37 #include "utils/eloop.h" 38 #include "sha1.h" 39 #include "random.h" 40 41 #define POOL_WORDS 32 42 #define POOL_WORDS_MASK (POOL_WORDS - 1) 43 #define POOL_TAP1 26 44 #define POOL_TAP2 20 45 #define POOL_TAP3 14 46 #define POOL_TAP4 7 47 #define POOL_TAP5 1 48 #define EXTRACT_LEN 16 49 #define MIN_READY_MARK 2 50 51 static u32 pool[POOL_WORDS]; 52 static unsigned int input_rotate = 0; 53 static unsigned int pool_pos = 0; 54 static u8 dummy_key[20]; 55 #ifdef __linux__ 56 static size_t dummy_key_avail = 0; 57 static int random_fd = -1; 58 #endif /* __linux__ */ 59 static unsigned int own_pool_ready = 0; 60 #define RANDOM_ENTROPY_SIZE 20 61 static char *random_entropy_file = NULL; 62 static int random_entropy_file_read = 0; 63 64 #define MIN_COLLECT_ENTROPY 1000 65 static unsigned int entropy = 0; 66 static unsigned int total_collected = 0; 67 68 69 static void random_write_entropy(void); 70 71 72 static u32 __ROL32(u32 x, u32 y) 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 wpa_printf(MSG_MSGDUMP, "Add randomness: count=%u entropy=%u", 138 count, entropy); 139 if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) { 140 /* 141 * No need to add more entropy at this point, so save CPU and 142 * skip the update. 143 */ 144 return; 145 } 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 /* Start with assumed strong randomness from OS */ 169 ret = os_get_random(buf, len); 170 wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random", 171 buf, len); 172 173 /* Mix in additional entropy extracted from the internal pool */ 174 left = len; 175 while (left) { 176 size_t siz, i; 177 u8 tmp[EXTRACT_LEN]; 178 random_extract(tmp); 179 wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool", 180 tmp, sizeof(tmp)); 181 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left; 182 for (i = 0; i < siz; i++) 183 *bytes++ ^= tmp[i]; 184 left -= siz; 185 } 186 wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len); 187 188 if (entropy < len) 189 entropy = 0; 190 else 191 entropy -= len; 192 193 return ret; 194 } 195 196 197 int random_pool_ready(void) 198 { 199 #ifdef __linux__ 200 int fd; 201 ssize_t res; 202 203 /* 204 * Make sure that there is reasonable entropy available before allowing 205 * some key derivation operations to proceed. 206 */ 207 208 if (dummy_key_avail == sizeof(dummy_key)) 209 return 1; /* Already initialized - good to continue */ 210 211 /* 212 * Try to fetch some more data from the kernel high quality 213 * /dev/random. There may not be enough data available at this point, 214 * so use non-blocking read to avoid blocking the application 215 * completely. 216 */ 217 fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 218 if (fd < 0) { 219 #ifndef CONFIG_NO_STDOUT_DEBUG 220 int error = errno; 221 perror("open(/dev/random)"); 222 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 223 strerror(error)); 224 #endif /* CONFIG_NO_STDOUT_DEBUG */ 225 return -1; 226 } 227 228 res = read(fd, dummy_key + dummy_key_avail, 229 sizeof(dummy_key) - dummy_key_avail); 230 if (res < 0) { 231 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 232 "%s", strerror(errno)); 233 res = 0; 234 } 235 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from " 236 "/dev/random", (unsigned) res, 237 (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 238 dummy_key_avail += res; 239 close(fd); 240 241 if (dummy_key_avail == sizeof(dummy_key)) { 242 if (own_pool_ready < MIN_READY_MARK) 243 own_pool_ready = MIN_READY_MARK; 244 random_write_entropy(); 245 return 1; 246 } 247 248 wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong " 249 "random data available from /dev/random", 250 (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key)); 251 252 if (own_pool_ready >= MIN_READY_MARK || 253 total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) { 254 wpa_printf(MSG_INFO, "random: Allow operation to proceed " 255 "based on internal entropy"); 256 return 1; 257 } 258 259 wpa_printf(MSG_INFO, "random: Not enough entropy pool available for " 260 "secure operations"); 261 return 0; 262 #else /* __linux__ */ 263 /* TODO: could do similar checks on non-Linux platforms */ 264 return 1; 265 #endif /* __linux__ */ 266 } 267 268 269 void random_mark_pool_ready(void) 270 { 271 own_pool_ready++; 272 wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be " 273 "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK); 274 random_write_entropy(); 275 } 276 277 278 #ifdef __linux__ 279 280 static void random_close_fd(void) 281 { 282 if (random_fd >= 0) { 283 eloop_unregister_read_sock(random_fd); 284 close(random_fd); 285 random_fd = -1; 286 } 287 } 288 289 290 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx) 291 { 292 ssize_t res; 293 294 if (dummy_key_avail == sizeof(dummy_key)) { 295 random_close_fd(); 296 return; 297 } 298 299 res = read(sock, dummy_key + dummy_key_avail, 300 sizeof(dummy_key) - dummy_key_avail); 301 if (res < 0) { 302 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: " 303 "%s", strerror(errno)); 304 return; 305 } 306 307 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random", 308 (unsigned) res, 309 (unsigned) (sizeof(dummy_key) - dummy_key_avail)); 310 dummy_key_avail += res; 311 312 if (dummy_key_avail == sizeof(dummy_key)) { 313 random_close_fd(); 314 if (own_pool_ready < MIN_READY_MARK) 315 own_pool_ready = MIN_READY_MARK; 316 random_write_entropy(); 317 } 318 } 319 320 #endif /* __linux__ */ 321 322 323 static void random_read_entropy(void) 324 { 325 char *buf; 326 size_t len; 327 328 if (!random_entropy_file) 329 return; 330 331 buf = os_readfile(random_entropy_file, &len); 332 if (buf == NULL) 333 return; /* entropy file not yet available */ 334 335 if (len != 1 + RANDOM_ENTROPY_SIZE) { 336 wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s", 337 random_entropy_file); 338 os_free(buf); 339 return; 340 } 341 342 own_pool_ready = (u8) buf[0]; 343 random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE); 344 random_entropy_file_read = 1; 345 os_free(buf); 346 wpa_printf(MSG_DEBUG, "random: Added entropy from %s " 347 "(own_pool_ready=%u)", 348 random_entropy_file, own_pool_ready); 349 } 350 351 352 static void random_write_entropy(void) 353 { 354 char buf[RANDOM_ENTROPY_SIZE]; 355 FILE *f; 356 u8 opr; 357 358 if (!random_entropy_file) 359 return; 360 361 random_get_bytes(buf, RANDOM_ENTROPY_SIZE); 362 363 f = fopen(random_entropy_file, "wb"); 364 if (f == NULL) { 365 wpa_printf(MSG_ERROR, "random: Could not write %s", 366 random_entropy_file); 367 return; 368 } 369 370 opr = own_pool_ready > 0xff ? 0xff : own_pool_ready; 371 fwrite(&opr, 1, 1, f); 372 fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f); 373 fclose(f); 374 375 wpa_printf(MSG_DEBUG, "random: Updated entropy file %s " 376 "(own_pool_ready=%u)", 377 random_entropy_file, own_pool_ready); 378 } 379 380 381 void random_init(const char *entropy_file) 382 { 383 os_free(random_entropy_file); 384 if (entropy_file) 385 random_entropy_file = os_strdup(entropy_file); 386 else 387 random_entropy_file = NULL; 388 random_read_entropy(); 389 390 #ifdef __linux__ 391 if (random_fd >= 0) 392 return; 393 394 random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK); 395 if (random_fd < 0) { 396 #ifndef CONFIG_NO_STDOUT_DEBUG 397 int error = errno; 398 perror("open(/dev/random)"); 399 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", 400 strerror(error)); 401 #endif /* CONFIG_NO_STDOUT_DEBUG */ 402 return; 403 } 404 wpa_printf(MSG_DEBUG, "random: Trying to read entropy from " 405 "/dev/random"); 406 407 eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL); 408 #endif /* __linux__ */ 409 410 random_write_entropy(); 411 } 412 413 414 void random_deinit(void) 415 { 416 #ifdef __linux__ 417 random_close_fd(); 418 #endif /* __linux__ */ 419 random_write_entropy(); 420 os_free(random_entropy_file); 421 random_entropy_file = NULL; 422 } 423
