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 #include <stdlib.h>
33
34 #include "utils/common.h"
35 #include "utils/eloop.h"
36 #include "crypto/crypto.h"
37 #include "sha1.h"
38 #include "random.h"
39
40 #define POOL_WORDS 32
41 #define POOL_WORDS_MASK (POOL_WORDS - 1)
42 #define POOL_TAP1 26
43 #define POOL_TAP2 20
44 #define POOL_TAP3 14
45 #define POOL_TAP4 7
46 #define POOL_TAP5 1
47 #define EXTRACT_LEN 16
48 #define MIN_READY_MARK 2
49
50 static u32 pool[POOL_WORDS];
51 static unsigned int input_rotate = 0;
52 static unsigned int pool_pos = 0;
53 static u8 stub_key[20];
54 #ifdef __linux__
55 static size_t stub_key_avail = 0;
56 static int random_fd = -1;
57 #endif /* __linux__ */
58 static unsigned int own_pool_ready = 0;
59 #define RANDOM_ENTROPY_SIZE 20
60 static char *random_entropy_file = NULL;
61
62 #define MIN_COLLECT_ENTROPY 1000
63 static unsigned int entropy = 0;
64 static unsigned int total_collected = 0;
65
66
67 static void random_write_entropy(void);
68
69
__ROL32(u32 x,u32 y)70 static u32 __ROL32(u32 x, u32 y)
71 {
72 if (y == 0)
73 return x;
74
75 return (x << (y & 31)) | (x >> (32 - (y & 31)));
76 }
77
78
random_mix_pool(const void * buf,size_t len)79 static void random_mix_pool(const void *buf, size_t len)
80 {
81 static const u32 twist[8] = {
82 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
83 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
84 };
85 const u8 *pos = buf;
86 u32 w;
87
88 wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len);
89
90 while (len--) {
91 w = __ROL32(*pos++, input_rotate & 31);
92 input_rotate += pool_pos ? 7 : 14;
93 pool_pos = (pool_pos - 1) & POOL_WORDS_MASK;
94 w ^= pool[pool_pos];
95 w ^= pool[(pool_pos + POOL_TAP1) & POOL_WORDS_MASK];
96 w ^= pool[(pool_pos + POOL_TAP2) & POOL_WORDS_MASK];
97 w ^= pool[(pool_pos + POOL_TAP3) & POOL_WORDS_MASK];
98 w ^= pool[(pool_pos + POOL_TAP4) & POOL_WORDS_MASK];
99 w ^= pool[(pool_pos + POOL_TAP5) & POOL_WORDS_MASK];
100 pool[pool_pos] = (w >> 3) ^ twist[w & 7];
101 }
102 }
103
104
random_extract(u8 * out)105 static void random_extract(u8 *out)
106 {
107 unsigned int i;
108 u8 hash[SHA1_MAC_LEN];
109 u32 *hash_ptr;
110 u32 buf[POOL_WORDS / 2];
111
112 /* First, add hash back to pool to make backtracking more difficult. */
113 hmac_sha1(stub_key, sizeof(stub_key), (const u8 *) pool,
114 sizeof(pool), hash);
115 random_mix_pool(hash, sizeof(hash));
116 /* Hash half the pool to extra data */
117 for (i = 0; i < POOL_WORDS / 2; i++)
118 buf[i] = pool[(pool_pos - i) & POOL_WORDS_MASK];
119 hmac_sha1(stub_key, sizeof(stub_key), (const u8 *) buf,
120 sizeof(buf), hash);
121 /*
122 * Fold the hash to further reduce any potential output pattern.
123 * Though, compromise this to reduce CPU use for the most common output
124 * length (32) and return 16 bytes from instead of only half.
125 */
126 hash_ptr = (u32 *) hash;
127 hash_ptr[0] ^= hash_ptr[4];
128 os_memcpy(out, hash, EXTRACT_LEN);
129 }
130
131
random_add_randomness(const void * buf,size_t len)132 void random_add_randomness(const void *buf, size_t len)
133 {
134 struct os_time t;
135 static unsigned int count = 0;
136
137 count++;
138 if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
139 /*
140 * No need to add more entropy at this point, so save CPU and
141 * skip the update.
142 */
143 return;
144 }
145 wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u",
146 count, entropy);
147
148 os_get_time(&t);
149 wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
150 (const u8 *) pool, sizeof(pool));
151 random_mix_pool(&t, sizeof(t));
152 random_mix_pool(buf, len);
153 wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
154 (const u8 *) pool, sizeof(pool));
155 entropy++;
156 total_collected++;
157 }
158
159
random_get_bytes(void * buf,size_t len)160 int random_get_bytes(void *buf, size_t len)
161 {
162 #ifdef CONFIG_TEST_RANDOM
163 /* Only for test */
164 for (size_t i = 0; i < len; i++) {
165 buf[i] = random();
166 }
167 #else /* CONFIG_TEST_RANDOM */
168 int ret;
169 u8 *bytes = buf;
170 size_t left;
171
172 wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u",
173 (unsigned int) len, entropy);
174
175 /* Start with assumed strong randomness from OS */
176 ret = os_get_random(buf, len);
177 wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random",
178 buf, len);
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 #endif /* CONFIG_TEST_RANDOM */
224 }
225
226
random_pool_ready(void)227 int random_pool_ready(void)
228 {
229 #ifdef CONFIG_TEST_RANDOM
230 return 1;
231 #else /* CONFIG_TEST_RANDOM */
232 #ifdef __linux__
233 int fd;
234 ssize_t res;
235
236 /*
237 * Make sure that there is reasonable entropy available before allowing
238 * some key derivation operations to proceed.
239 */
240
241 if (stub_key_avail == sizeof(stub_key))
242 return 1; /* Already initialized - good to continue */
243
244 /*
245 * Try to fetch some more data from the kernel high quality RNG.
246 * There may not be enough data available at this point,
247 * so use non-blocking read to avoid blocking the application
248 * completely.
249 */
250
251 #ifdef CONFIG_GETRANDOM
252 res = getrandom(stub_key + stub_key_avail,
253 sizeof(stub_key) - stub_key_avail, GRND_NONBLOCK);
254 if (res < 0) {
255 if (errno == ENOSYS) {
256 wpa_printf(MSG_DEBUG,
257 "random: getrandom() not supported, falling back to /dev/random");
258 } else {
259 wpa_printf(MSG_INFO,
260 "random: no data from getrandom(): %s",
261 strerror(errno));
262 res = 0;
263 }
264 }
265 #else /* CONFIG_GETRANDOM */
266 res = -1;
267 #endif /* CONFIG_GETRANDOM */
268 if (res < 0) {
269 fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
270 if (fd < 0) {
271 wpa_printf(MSG_ERROR,
272 "random: Cannot open /dev/random: %s",
273 strerror(errno));
274 return -1;
275 }
276
277 res = read(fd, stub_key + stub_key_avail,
278 sizeof(stub_key) - stub_key_avail);
279 if (res < 0) {
280 wpa_printf(MSG_ERROR,
281 "random: Cannot read from /dev/random: %s",
282 strerror(errno));
283 res = 0;
284 }
285 close(fd);
286 }
287
288 wpa_printf(MSG_DEBUG, "random: Got %u/%u random bytes", (unsigned) res,
289 (unsigned) (sizeof(stub_key) - stub_key_avail));
290 stub_key_avail += res;
291
292 if (stub_key_avail == sizeof(stub_key)) {
293 if (own_pool_ready < MIN_READY_MARK)
294 own_pool_ready = MIN_READY_MARK;
295 random_write_entropy();
296 return 1;
297 }
298
299 wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
300 "random data available",
301 (unsigned) stub_key_avail, (unsigned) sizeof(stub_key));
302
303 if (own_pool_ready >= MIN_READY_MARK ||
304 total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) {
305 wpa_printf(MSG_INFO, "random: Allow operation to proceed "
306 "based on internal entropy");
307 return 1;
308 }
309
310 wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
311 "secure operations");
312 return 0;
313 #else /* __linux__ */
314 /* TODO: could do similar checks on non-Linux platforms */
315 return 1;
316 #endif /* __linux__ */
317 #endif /* CONFIG_TEST_RANDOM */
318 }
319
320
random_mark_pool_ready(void)321 void random_mark_pool_ready(void)
322 {
323 own_pool_ready++;
324 wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be "
325 "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK);
326 random_write_entropy();
327 }
328
329
330 #ifdef __linux__
331
random_close_fd(void)332 static void random_close_fd(void)
333 {
334 if (random_fd >= 0) {
335 eloop_unregister_read_sock(random_fd);
336 close(random_fd);
337 random_fd = -1;
338 }
339 }
340
341
random_read_fd(int sock,void * eloop_ctx,void * sock_ctx)342 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
343 {
344 ssize_t res;
345
346 if (stub_key_avail == sizeof(stub_key)) {
347 random_close_fd();
348 return;
349 }
350
351 res = read(sock, stub_key + stub_key_avail,
352 sizeof(stub_key) - stub_key_avail);
353 if (res < 0) {
354 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
355 "%s", strerror(errno));
356 return;
357 }
358
359 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
360 (unsigned) res,
361 (unsigned) (sizeof(stub_key) - stub_key_avail));
362 stub_key_avail += res;
363
364 if (stub_key_avail == sizeof(stub_key)) {
365 random_close_fd();
366 if (own_pool_ready < MIN_READY_MARK)
367 own_pool_ready = MIN_READY_MARK;
368 random_write_entropy();
369 }
370 }
371
372 #endif /* __linux__ */
373
374
random_read_entropy(void)375 static void random_read_entropy(void)
376 {
377 char *buf;
378 size_t len;
379
380 if (!random_entropy_file)
381 return;
382
383 buf = os_readfile(random_entropy_file, &len);
384 if (buf == NULL)
385 return; /* entropy file not yet available */
386
387 if (len != 1 + RANDOM_ENTROPY_SIZE) {
388 wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s",
389 random_entropy_file);
390 os_free(buf);
391 return;
392 }
393
394 own_pool_ready = (u8) buf[0];
395 random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE);
396 os_free(buf);
397 wpa_printf(MSG_DEBUG, "random: Added entropy from %s "
398 "(own_pool_ready=%u)",
399 random_entropy_file, own_pool_ready);
400 }
401
402
random_write_entropy(void)403 static void random_write_entropy(void)
404 {
405 char buf[RANDOM_ENTROPY_SIZE];
406 FILE *f;
407 u8 opr;
408 int fail = 0;
409
410 if (!random_entropy_file)
411 return;
412
413 if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0)
414 return;
415
416 f = fopen(random_entropy_file, "wb");
417 if (f == NULL) {
418 wpa_printf(MSG_ERROR, "random: Could not open entropy file %s "
419 "for writing", random_entropy_file);
420 return;
421 }
422
423 opr = own_pool_ready > 0xff ? 0xff : own_pool_ready;
424 if (fwrite(&opr, 1, 1, f) != 1 ||
425 fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1)
426 fail = 1;
427 fclose(f);
428 if (fail) {
429 wpa_printf(MSG_ERROR, "random: Could not write entropy data "
430 "to %s", random_entropy_file);
431 return;
432 }
433
434 wpa_printf(MSG_DEBUG, "random: Updated entropy file %s "
435 "(own_pool_ready=%u)",
436 random_entropy_file, own_pool_ready);
437 }
438
439
random_init(const char * entropy_file)440 void random_init(const char *entropy_file)
441 {
442 os_free(random_entropy_file);
443 if (entropy_file)
444 random_entropy_file = os_strdup(entropy_file);
445 else
446 random_entropy_file = NULL;
447 random_read_entropy();
448
449 #ifdef __linux__
450 if (random_fd >= 0)
451 return;
452
453 #ifdef CONFIG_GETRANDOM
454 {
455 u8 stub;
456
457 if (getrandom(&stub, 0, GRND_NONBLOCK) == 0 ||
458 errno != ENOSYS) {
459 wpa_printf(MSG_DEBUG,
460 "random: getrandom() support available");
461 return;
462 }
463 }
464 #endif /* CONFIG_GETRANDOM */
465
466 random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
467 if (random_fd < 0) {
468 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
469 strerror(errno));
470 return;
471 }
472 wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
473 "/dev/random");
474
475 eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
476 #endif /* __linux__ */
477
478 random_write_entropy();
479 }
480
481
random_deinit(void)482 void random_deinit(void)
483 {
484 #ifdef __linux__
485 random_close_fd();
486 #endif /* __linux__ */
487 random_write_entropy();
488 os_free(random_entropy_file);
489 random_entropy_file = NULL;
490 }
491