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
49static u32 pool[POOL_WORDS];
50static unsigned int input_rotate = 0;
51static unsigned int pool_pos = 0;
52static u8 dummy_key[20];
53#ifdef __linux__
54static size_t dummy_key_avail = 0;
55static int random_fd = -1;
56#endif /* __linux__ */
57static unsigned int own_pool_ready = 0;
58#define RANDOM_ENTROPY_SIZE 20
59static char *random_entropy_file = NULL;
60
61#define MIN_COLLECT_ENTROPY 1000
62static unsigned int entropy = 0;
63static unsigned int total_collected = 0;
64
65
66static void random_write_entropy(void);
67
68
69static 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
78static 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
104static 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
131void 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
159int 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
219int 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
309void 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
320static 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
330static 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
363static 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
391static 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
428void 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
470void 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