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