2 * Random number generator
3 * Copyright (c) 2010-2011, Jouni Malinen <j@w1.fi>
5 * This software may be distributed under the terms of the BSD license.
6 * See README for more details.
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.
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.
25 #include "utils/includes.h"
28 #endif /* __linux__ */
30 #include "utils/common.h"
31 #include "utils/eloop.h"
32 #include "crypto/crypto.h"
37 #define POOL_WORDS_MASK (POOL_WORDS - 1)
43 #define EXTRACT_LEN 16
44 #define MIN_READY_MARK 2
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];
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;
58 #define MIN_COLLECT_ENTROPY 1000
59 static unsigned int entropy = 0;
60 static unsigned int total_collected = 0;
63 static void random_write_entropy(void);
66 static u32 __ROL32(u32 x, u32 y)
71 return (x << (y & 31)) | (x >> (32 - (y & 31)));
75 static void random_mix_pool(const void *buf, size_t len)
77 static const u32 twist[8] = {
78 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
79 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
84 wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len);
87 w = __ROL32(*pos++, input_rotate & 31);
88 input_rotate += pool_pos ? 7 : 14;
89 pool_pos = (pool_pos - 1) & POOL_WORDS_MASK;
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];
101 static void random_extract(u8 *out)
104 u8 hash[SHA1_MAC_LEN];
106 u32 buf[POOL_WORDS / 2];
108 /* First, add hash back to pool to make backtracking more difficult. */
109 hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) pool,
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,
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.
122 hash_ptr = (u32 *) hash;
123 hash_ptr[0] ^= hash_ptr[4];
124 os_memcpy(out, hash, EXTRACT_LEN);
128 void random_add_randomness(const void *buf, size_t len)
131 static unsigned int count = 0;
134 if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
136 * No need to add more entropy at this point, so save CPU and
141 wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u",
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));
156 int random_get_bytes(void *buf, size_t len)
162 wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u",
163 (unsigned int) len, entropy);
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",
170 /* Mix in additional entropy extracted from the internal pool */
176 wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool",
178 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
179 for (i = 0; i < siz; i++)
185 /* Mix in additional entropy from the crypto module */
191 if (crypto_get_random(tmp, sizeof(tmp)) < 0) {
192 wpa_printf(MSG_ERROR, "random: No entropy available "
193 "for generating strong random bytes");
196 wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto module",
198 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
199 for (i = 0; i < siz; i++)
203 #endif /* CONFIG_FIPS */
205 wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
216 int random_pool_ready(void)
223 * Make sure that there is reasonable entropy available before allowing
224 * some key derivation operations to proceed.
227 if (dummy_key_avail == sizeof(dummy_key))
228 return 1; /* Already initialized - good to continue */
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
236 fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
238 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
243 res = read(fd, dummy_key + dummy_key_avail,
244 sizeof(dummy_key) - dummy_key_avail);
246 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
247 "%s", strerror(errno));
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;
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();
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));
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");
274 wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
275 "secure operations");
277 #else /* __linux__ */
278 /* TODO: could do similar checks on non-Linux platforms */
280 #endif /* __linux__ */
284 void random_mark_pool_ready(void)
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();
295 static void random_close_fd(void)
297 if (random_fd >= 0) {
298 eloop_unregister_read_sock(random_fd);
305 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
309 if (dummy_key_avail == sizeof(dummy_key)) {
314 res = read(sock, dummy_key + dummy_key_avail,
315 sizeof(dummy_key) - dummy_key_avail);
317 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
318 "%s", strerror(errno));
322 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
324 (unsigned) (sizeof(dummy_key) - dummy_key_avail));
325 dummy_key_avail += res;
327 if (dummy_key_avail == sizeof(dummy_key)) {
329 if (own_pool_ready < MIN_READY_MARK)
330 own_pool_ready = MIN_READY_MARK;
331 random_write_entropy();
335 #endif /* __linux__ */
338 static void random_read_entropy(void)
343 if (!random_entropy_file)
346 buf = os_readfile(random_entropy_file, &len);
348 return; /* entropy file not yet available */
350 if (len != 1 + RANDOM_ENTROPY_SIZE) {
351 wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s",
352 random_entropy_file);
357 own_pool_ready = (u8) buf[0];
358 random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE);
360 wpa_printf(MSG_DEBUG, "random: Added entropy from %s "
361 "(own_pool_ready=%u)",
362 random_entropy_file, own_pool_ready);
366 static void random_write_entropy(void)
368 char buf[RANDOM_ENTROPY_SIZE];
373 if (!random_entropy_file)
376 if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0)
379 f = fopen(random_entropy_file, "wb");
381 wpa_printf(MSG_ERROR, "random: Could not open entropy file %s "
382 "for writing", random_entropy_file);
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)
392 wpa_printf(MSG_ERROR, "random: Could not write entropy data "
393 "to %s", random_entropy_file);
397 wpa_printf(MSG_DEBUG, "random: Updated entropy file %s "
398 "(own_pool_ready=%u)",
399 random_entropy_file, own_pool_ready);
403 void random_init(const char *entropy_file)
405 os_free(random_entropy_file);
407 random_entropy_file = os_strdup(entropy_file);
409 random_entropy_file = NULL;
410 random_read_entropy();
416 random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
418 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
422 wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
425 eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
426 #endif /* __linux__ */
428 random_write_entropy();
432 void random_deinit(void)
436 #endif /* __linux__ */
437 random_write_entropy();
438 os_free(random_entropy_file);
439 random_entropy_file = NULL;