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 #ifdef CONFIG_GETRANDOM
29 #include <sys/random.h>
30 #endif /* CONFIG_GETRANDOM */
31 #endif /* __linux__ */
32
33 #include "utils/common.h"
34 #include "utils/eloop.h"
35 #include "crypto/crypto.h"
36 #include "sha1.h"
37 #include "random.h"
38
39 #define POOL_WORDS 32
40 #define POOL_WORDS_MASK (POOL_WORDS - 1)
41 #define POOL_TAP1 26
42 #define POOL_TAP2 20
43 #define POOL_TAP3 14
44 #define POOL_TAP4 7
45 #define POOL_TAP5 1
46 #define EXTRACT_LEN 16
47 #define MIN_READY_MARK 2
48
49 static u32 pool[POOL_WORDS];
50 static unsigned int input_rotate = 0;
51 static unsigned int pool_pos = 0;
52 static u8 dummy_key[20];
53 #ifdef __linux__
54 static size_t dummy_key_avail = 0;
55 static int random_fd = -1;
56 #endif /* __linux__ */
57 static unsigned int own_pool_ready = 0;
58 #define RANDOM_ENTROPY_SIZE 20
59 static char *random_entropy_file = NULL;
60
61 #define MIN_COLLECT_ENTROPY 1000
62 static unsigned int entropy = 0;
63 static unsigned int total_collected = 0;
64
65
66 static void random_write_entropy(void);
67
68
__ROL32(u32 x,u32 y)69 static u32 __ROL32(u32 x, u32 y)
70 {
71 if (y == 0)
72 return x;
73
74 return (x << (y & 31)) | (x >> (32 - (y & 31)));
75 }
76
77
random_mix_pool(const void * buf,size_t len)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
random_extract(u8 * out)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
random_add_randomness(const void * buf,size_t len)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 if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
138 /*
139 * No need to add more entropy at this point, so save CPU and
140 * skip the update.
141 */
142 return;
143 }
144 wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u",
145 count, entropy);
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
random_get_bytes(void * buf,size_t len)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 #ifdef CONFIG_USE_OPENSSL_RNG
169 /* Start with assumed strong randomness from OpenSSL */
170 ret = crypto_get_random(buf, len);
171 wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto_get_random",
172 buf, len);
173 #else /* CONFIG_USE_OPENSSL_RNG */
174 /* Start with assumed strong randomness from OS */
175 ret = os_get_random(buf, len);
176 wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random",
177 buf, len);
178 #endif /* CONFIG_USE_OPENSSL_RNG */
179
180 /* Mix in additional entropy extracted from the internal pool */
181 left = len;
182 while (left) {
183 size_t siz, i;
184 u8 tmp[EXTRACT_LEN];
185 random_extract(tmp);
186 wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool",
187 tmp, sizeof(tmp));
188 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
189 for (i = 0; i < siz; i++)
190 *bytes++ ^= tmp[i];
191 left -= siz;
192 }
193
194 #ifdef CONFIG_FIPS
195 /* Mix in additional entropy from the crypto module */
196 bytes = buf;
197 left = len;
198 while (left) {
199 size_t siz, i;
200 u8 tmp[EXTRACT_LEN];
201 if (crypto_get_random(tmp, sizeof(tmp)) < 0) {
202 wpa_printf(MSG_ERROR, "random: No entropy available "
203 "for generating strong random bytes");
204 return -1;
205 }
206 wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto module",
207 tmp, sizeof(tmp));
208 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
209 for (i = 0; i < siz; i++)
210 *bytes++ ^= tmp[i];
211 left -= siz;
212 }
213 #endif /* CONFIG_FIPS */
214
215 wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
216
217 if (entropy < len)
218 entropy = 0;
219 else
220 entropy -= len;
221
222 return ret;
223 }
224
225
random_pool_ready(void)226 int random_pool_ready(void)
227 {
228 #ifdef __linux__
229 int fd;
230 ssize_t res;
231
232 /*
233 * Make sure that there is reasonable entropy available before allowing
234 * some key derivation operations to proceed.
235 */
236
237 if (dummy_key_avail == sizeof(dummy_key))
238 return 1; /* Already initialized - good to continue */
239
240 /*
241 * Try to fetch some more data from the kernel high quality RNG.
242 * There may not be enough data available at this point,
243 * so use non-blocking read to avoid blocking the application
244 * completely.
245 */
246
247 #ifdef CONFIG_GETRANDOM
248 res = getrandom(dummy_key + dummy_key_avail,
249 sizeof(dummy_key) - dummy_key_avail, GRND_NONBLOCK);
250 if (res < 0) {
251 if (errno == ENOSYS) {
252 wpa_printf(MSG_DEBUG,
253 "random: getrandom() not supported, falling back to /dev/random");
254 } else {
255 wpa_printf(MSG_INFO,
256 "random: no data from getrandom(): %s",
257 strerror(errno));
258 res = 0;
259 }
260 }
261 #else /* CONFIG_GETRANDOM */
262 res = -1;
263 #endif /* CONFIG_GETRANDOM */
264 if (res < 0) {
265 fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
266 if (fd < 0) {
267 wpa_printf(MSG_ERROR,
268 "random: Cannot open /dev/random: %s",
269 strerror(errno));
270 return -1;
271 }
272
273 res = read(fd, dummy_key + dummy_key_avail,
274 sizeof(dummy_key) - dummy_key_avail);
275 if (res < 0) {
276 wpa_printf(MSG_ERROR,
277 "random: Cannot read from /dev/random: %s",
278 strerror(errno));
279 res = 0;
280 }
281 close(fd);
282 }
283
284 wpa_printf(MSG_DEBUG, "random: Got %u/%u random bytes", (unsigned) res,
285 (unsigned) (sizeof(dummy_key) - dummy_key_avail));
286 dummy_key_avail += res;
287
288 if (dummy_key_avail == sizeof(dummy_key)) {
289 if (own_pool_ready < MIN_READY_MARK)
290 own_pool_ready = MIN_READY_MARK;
291 random_write_entropy();
292 return 1;
293 }
294
295 wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
296 "random data available",
297 (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key));
298
299 if (own_pool_ready >= MIN_READY_MARK ||
300 total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) {
301 wpa_printf(MSG_INFO, "random: Allow operation to proceed "
302 "based on internal entropy");
303 return 1;
304 }
305
306 wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
307 "secure operations");
308 return 0;
309 #else /* __linux__ */
310 /* TODO: could do similar checks on non-Linux platforms */
311 return 1;
312 #endif /* __linux__ */
313 }
314
315
random_mark_pool_ready(void)316 void random_mark_pool_ready(void)
317 {
318 own_pool_ready++;
319 wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be "
320 "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK);
321 random_write_entropy();
322 }
323
324
325 #ifdef __linux__
326
random_close_fd(void)327 static void random_close_fd(void)
328 {
329 if (random_fd >= 0) {
330 eloop_unregister_read_sock(random_fd);
331 close(random_fd);
332 random_fd = -1;
333 }
334 }
335
336
random_read_fd(int sock,void * eloop_ctx,void * sock_ctx)337 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
338 {
339 ssize_t res;
340
341 if (dummy_key_avail == sizeof(dummy_key)) {
342 random_close_fd();
343 return;
344 }
345
346 res = read(sock, dummy_key + dummy_key_avail,
347 sizeof(dummy_key) - dummy_key_avail);
348 if (res < 0) {
349 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
350 "%s", strerror(errno));
351 return;
352 }
353
354 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
355 (unsigned) res,
356 (unsigned) (sizeof(dummy_key) - dummy_key_avail));
357 dummy_key_avail += res;
358
359 if (dummy_key_avail == sizeof(dummy_key)) {
360 random_close_fd();
361 if (own_pool_ready < MIN_READY_MARK)
362 own_pool_ready = MIN_READY_MARK;
363 random_write_entropy();
364 }
365 }
366
367 #endif /* __linux__ */
368
369
random_read_entropy(void)370 static void random_read_entropy(void)
371 {
372 char *buf;
373 size_t len;
374
375 if (!random_entropy_file)
376 return;
377
378 buf = os_readfile(random_entropy_file, &len);
379 if (buf == NULL)
380 return; /* entropy file not yet available */
381
382 if (len != 1 + RANDOM_ENTROPY_SIZE) {
383 wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s",
384 random_entropy_file);
385 os_free(buf);
386 return;
387 }
388
389 own_pool_ready = (u8) buf[0];
390 random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE);
391 os_free(buf);
392 wpa_printf(MSG_DEBUG, "random: Added entropy from %s "
393 "(own_pool_ready=%u)",
394 random_entropy_file, own_pool_ready);
395 }
396
397
random_write_entropy(void)398 static void random_write_entropy(void)
399 {
400 char buf[RANDOM_ENTROPY_SIZE];
401 FILE *f;
402 u8 opr;
403 int fail = 0;
404
405 if (!random_entropy_file)
406 return;
407
408 if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0)
409 return;
410
411 f = fopen(random_entropy_file, "wb");
412 if (f == NULL) {
413 wpa_printf(MSG_ERROR, "random: Could not open entropy file %s "
414 "for writing", random_entropy_file);
415 return;
416 }
417
418 opr = own_pool_ready > 0xff ? 0xff : own_pool_ready;
419 if (fwrite(&opr, 1, 1, f) != 1 ||
420 fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1)
421 fail = 1;
422 fclose(f);
423 if (fail) {
424 wpa_printf(MSG_ERROR, "random: Could not write entropy data "
425 "to %s", random_entropy_file);
426 return;
427 }
428
429 wpa_printf(MSG_DEBUG, "random: Updated entropy file %s "
430 "(own_pool_ready=%u)",
431 random_entropy_file, own_pool_ready);
432 }
433
434
random_init(const char * entropy_file)435 void random_init(const char *entropy_file)
436 {
437 os_free(random_entropy_file);
438 if (entropy_file)
439 random_entropy_file = os_strdup(entropy_file);
440 else
441 random_entropy_file = NULL;
442 random_read_entropy();
443
444 #ifdef __linux__
445 if (random_fd >= 0)
446 return;
447
448 #ifdef CONFIG_GETRANDOM
449 {
450 u8 dummy;
451
452 if (getrandom(&dummy, 0, GRND_NONBLOCK) == 0 ||
453 errno != ENOSYS) {
454 wpa_printf(MSG_DEBUG,
455 "random: getrandom() support available");
456 return;
457 }
458 }
459 #endif /* CONFIG_GETRANDOM */
460
461 random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
462 if (random_fd < 0) {
463 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
464 strerror(errno));
465 return;
466 }
467 wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
468 "/dev/random");
469
470 eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
471 #endif /* __linux__ */
472
473 random_write_entropy();
474 }
475
476
random_deinit(void)477 void random_deinit(void)
478 {
479 #ifdef __linux__
480 random_close_fd();
481 #endif /* __linux__ */
482 random_write_entropy();
483 os_free(random_entropy_file);
484 random_entropy_file = NULL;
485 }
486