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