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 
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 
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 	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 
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 
187 #ifdef CONFIG_FIPS
188 	/* Mix in additional entropy from the crypto module */
189 	bytes = buf;
190 	left = len;
191 	while (left) {
192 		size_t siz, i;
193 		u8 tmp[EXTRACT_LEN];
194 		if (crypto_get_random(tmp, sizeof(tmp)) < 0) {
195 			wpa_printf(MSG_ERROR, "random: No entropy available "
196 				   "for generating strong random bytes");
197 			return -1;
198 		}
199 		wpa_hexdump_key(MSG_EXCESSIVE, "random from crypto module",
200 				tmp, sizeof(tmp));
201 		siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
202 		for (i = 0; i < siz; i++)
203 			*bytes++ ^= tmp[i];
204 		left -= siz;
205 	}
206 #endif /* CONFIG_FIPS */
207 
208 	wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
209 
210 	if (entropy < len)
211 		entropy = 0;
212 	else
213 		entropy -= len;
214 
215 	return ret;
216 }
217 
218 
219 int random_pool_ready(void)
220 {
221 #ifdef __linux__
222 	int fd;
223 	ssize_t res;
224 
225 	/*
226 	 * Make sure that there is reasonable entropy available before allowing
227 	 * some key derivation operations to proceed.
228 	 */
229 
230 	if (dummy_key_avail == sizeof(dummy_key))
231 		return 1; /* Already initialized - good to continue */
232 
233 	/*
234 	 * Try to fetch some more data from the kernel high quality RNG.
235 	 * There may not be enough data available at this point,
236 	 * so use non-blocking read to avoid blocking the application
237 	 * completely.
238 	 */
239 
240 #ifdef CONFIG_GETRANDOM
241 	res = getrandom(dummy_key + dummy_key_avail,
242 			sizeof(dummy_key) - dummy_key_avail, GRND_NONBLOCK);
243 	if (res < 0) {
244 		if (errno == ENOSYS) {
245 			wpa_printf(MSG_DEBUG,
246 				   "random: getrandom() not supported, falling back to /dev/random");
247 		} else {
248 			wpa_printf(MSG_INFO,
249 				   "random: no data from getrandom(): %s",
250 				   strerror(errno));
251 			res = 0;
252 		}
253 	}
254 #else /* CONFIG_GETRANDOM */
255 	res = -1;
256 #endif /* CONFIG_GETRANDOM */
257 	if (res < 0) {
258 		fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
259 		if (fd < 0) {
260 			wpa_printf(MSG_ERROR,
261 				   "random: Cannot open /dev/random: %s",
262 				   strerror(errno));
263 			return -1;
264 		}
265 
266 		res = read(fd, dummy_key + dummy_key_avail,
267 			   sizeof(dummy_key) - dummy_key_avail);
268 		if (res < 0) {
269 			wpa_printf(MSG_ERROR,
270 				   "random: Cannot read from /dev/random: %s",
271 				   strerror(errno));
272 			res = 0;
273 		}
274 		close(fd);
275 	}
276 
277 	wpa_printf(MSG_DEBUG, "random: Got %u/%u random bytes", (unsigned) res,
278 		   (unsigned) (sizeof(dummy_key) - dummy_key_avail));
279 	dummy_key_avail += res;
280 
281 	if (dummy_key_avail == sizeof(dummy_key)) {
282 		if (own_pool_ready < MIN_READY_MARK)
283 			own_pool_ready = MIN_READY_MARK;
284 		random_write_entropy();
285 		return 1;
286 	}
287 
288 	wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
289 		   "random data available",
290 		   (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key));
291 
292 	if (own_pool_ready >= MIN_READY_MARK ||
293 	    total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) {
294 		wpa_printf(MSG_INFO, "random: Allow operation to proceed "
295 			   "based on internal entropy");
296 		return 1;
297 	}
298 
299 	wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
300 		   "secure operations");
301 	return 0;
302 #else /* __linux__ */
303 	/* TODO: could do similar checks on non-Linux platforms */
304 	return 1;
305 #endif /* __linux__ */
306 }
307 
308 
309 void random_mark_pool_ready(void)
310 {
311 	own_pool_ready++;
312 	wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be "
313 		   "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK);
314 	random_write_entropy();
315 }
316 
317 
318 #ifdef __linux__
319 
320 static void random_close_fd(void)
321 {
322 	if (random_fd >= 0) {
323 		eloop_unregister_read_sock(random_fd);
324 		close(random_fd);
325 		random_fd = -1;
326 	}
327 }
328 
329 
330 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
331 {
332 	ssize_t res;
333 
334 	if (dummy_key_avail == sizeof(dummy_key)) {
335 		random_close_fd();
336 		return;
337 	}
338 
339 	res = read(sock, dummy_key + dummy_key_avail,
340 		   sizeof(dummy_key) - dummy_key_avail);
341 	if (res < 0) {
342 		wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
343 			   "%s", strerror(errno));
344 		return;
345 	}
346 
347 	wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
348 		   (unsigned) res,
349 		   (unsigned) (sizeof(dummy_key) - dummy_key_avail));
350 	dummy_key_avail += res;
351 
352 	if (dummy_key_avail == sizeof(dummy_key)) {
353 		random_close_fd();
354 		if (own_pool_ready < MIN_READY_MARK)
355 			own_pool_ready = MIN_READY_MARK;
356 		random_write_entropy();
357 	}
358 }
359 
360 #endif /* __linux__ */
361 
362 
363 static void random_read_entropy(void)
364 {
365 	char *buf;
366 	size_t len;
367 
368 	if (!random_entropy_file)
369 		return;
370 
371 	buf = os_readfile(random_entropy_file, &len);
372 	if (buf == NULL)
373 		return; /* entropy file not yet available */
374 
375 	if (len != 1 + RANDOM_ENTROPY_SIZE) {
376 		wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s",
377 			   random_entropy_file);
378 		os_free(buf);
379 		return;
380 	}
381 
382 	own_pool_ready = (u8) buf[0];
383 	random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE);
384 	os_free(buf);
385 	wpa_printf(MSG_DEBUG, "random: Added entropy from %s "
386 		   "(own_pool_ready=%u)",
387 		   random_entropy_file, own_pool_ready);
388 }
389 
390 
391 static void random_write_entropy(void)
392 {
393 	char buf[RANDOM_ENTROPY_SIZE];
394 	FILE *f;
395 	u8 opr;
396 	int fail = 0;
397 
398 	if (!random_entropy_file)
399 		return;
400 
401 	if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0)
402 		return;
403 
404 	f = fopen(random_entropy_file, "wb");
405 	if (f == NULL) {
406 		wpa_printf(MSG_ERROR, "random: Could not open entropy file %s "
407 			   "for writing", random_entropy_file);
408 		return;
409 	}
410 
411 	opr = own_pool_ready > 0xff ? 0xff : own_pool_ready;
412 	if (fwrite(&opr, 1, 1, f) != 1 ||
413 	    fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1)
414 		fail = 1;
415 	fclose(f);
416 	if (fail) {
417 		wpa_printf(MSG_ERROR, "random: Could not write entropy data "
418 			   "to %s", random_entropy_file);
419 		return;
420 	}
421 
422 	wpa_printf(MSG_DEBUG, "random: Updated entropy file %s "
423 		   "(own_pool_ready=%u)",
424 		   random_entropy_file, own_pool_ready);
425 }
426 
427 
428 void random_init(const char *entropy_file)
429 {
430 	os_free(random_entropy_file);
431 	if (entropy_file)
432 		random_entropy_file = os_strdup(entropy_file);
433 	else
434 		random_entropy_file = NULL;
435 	random_read_entropy();
436 
437 #ifdef __linux__
438 	if (random_fd >= 0)
439 		return;
440 
441 #ifdef CONFIG_GETRANDOM
442 	{
443 		u8 dummy;
444 
445 		if (getrandom(&dummy, 0, GRND_NONBLOCK) == 0 ||
446 		    errno != ENOSYS) {
447 			wpa_printf(MSG_DEBUG,
448 				   "random: getrandom() support available");
449 			return;
450 		}
451 	}
452 #endif /* CONFIG_GETRANDOM */
453 
454 	random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
455 	if (random_fd < 0) {
456 		wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
457 			   strerror(errno));
458 		return;
459 	}
460 	wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
461 		   "/dev/random");
462 
463 	eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
464 #endif /* __linux__ */
465 
466 	random_write_entropy();
467 }
468 
469 
470 void random_deinit(void)
471 {
472 #ifdef __linux__
473 	random_close_fd();
474 #endif /* __linux__ */
475 	random_write_entropy();
476 	os_free(random_entropy_file);
477 	random_entropy_file = NULL;
478 }
479