random.c revision 8d520ff1dc2da35cdca849e982051b86468016d8 
1/*
2 * Random number generator
3 * Copyright (c) 2010-2011, Jouni Malinen <j@w1.fi>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation.
8 *
9 * Alternatively, this software may be distributed under the terms of BSD
10 * license.
11 *
12 * See README and COPYING for more details.
13 *
14 * This random number generator is used to provide additional entropy to the
15 * one provided by the operating system (os_get_random()) for session key
16 * generation. The os_get_random() output is expected to be secure and the
17 * implementation here is expected to provide only limited protection against
18 * cases where os_get_random() cannot provide strong randomness. This
19 * implementation shall not be assumed to be secure as the sole source of
20 * randomness. The random_get_bytes() function mixes in randomness from
21 * os_get_random() and as such, calls to os_get_random() can be replaced with
22 * calls to random_get_bytes() without reducing security.
23 *
24 * The design here follows partially the design used in the Linux
25 * drivers/char/random.c, but the implementation here is simpler and not as
26 * strong. This is a compromise to reduce duplicated CPU effort and to avoid
27 * extra code/memory size. As pointed out above, os_get_random() needs to be
28 * guaranteed to be secure for any of the security assumptions to hold.
29 */
30
31#include "utils/includes.h"
32#ifdef __linux__
33#include <fcntl.h>
34#endif /* __linux__ */
35
36#include "utils/common.h"
37#include "utils/eloop.h"
38#include "sha1.h"
39#include "random.h"
40
41#define POOL_WORDS 32
42#define POOL_WORDS_MASK (POOL_WORDS - 1)
43#define POOL_TAP1 26
44#define POOL_TAP2 20
45#define POOL_TAP3 14
46#define POOL_TAP4 7
47#define POOL_TAP5 1
48#define EXTRACT_LEN 16
49#define MIN_READY_MARK 2
50
51static u32 pool[POOL_WORDS];
52static unsigned int input_rotate = 0;
53static unsigned int pool_pos = 0;
54static u8 dummy_key[20];
55#ifdef __linux__
56static size_t dummy_key_avail = 0;
57static int random_fd = -1;
58#endif /* __linux__ */
59static unsigned int own_pool_ready = 0;
60
61#define MIN_COLLECT_ENTROPY 1000
62static unsigned int entropy = 0;
63static unsigned int total_collected = 0;
64
65
66static u32 __ROL32(u32 x, u32 y)
67{
68	return (x << (y & 31)) | (x >> (32 - (y & 31)));
69}
70
71
72static void random_mix_pool(const void *buf, size_t len)
73{
74	static const u32 twist[8] = {
75		0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
76		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
77	};
78	const u8 *pos = buf;
79	u32 w;
80
81	wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len);
82
83	while (len--) {
84		w = __ROL32(*pos++, input_rotate & 31);
85		input_rotate += pool_pos ? 7 : 14;
86		pool_pos = (pool_pos - 1) & POOL_WORDS_MASK;
87		w ^= pool[pool_pos];
88		w ^= pool[(pool_pos + POOL_TAP1) & POOL_WORDS_MASK];
89		w ^= pool[(pool_pos + POOL_TAP2) & POOL_WORDS_MASK];
90		w ^= pool[(pool_pos + POOL_TAP3) & POOL_WORDS_MASK];
91		w ^= pool[(pool_pos + POOL_TAP4) & POOL_WORDS_MASK];
92		w ^= pool[(pool_pos + POOL_TAP5) & POOL_WORDS_MASK];
93		pool[pool_pos] = (w >> 3) ^ twist[w & 7];
94	}
95}
96
97
98static void random_extract(u8 *out)
99{
100	unsigned int i;
101	u8 hash[SHA1_MAC_LEN];
102	u32 *hash_ptr;
103	u32 buf[POOL_WORDS / 2];
104
105	/* First, add hash back to pool to make backtracking more difficult. */
106	hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) pool,
107		  sizeof(pool), hash);
108	random_mix_pool(hash, sizeof(hash));
109	/* Hash half the pool to extra data */
110	for (i = 0; i < POOL_WORDS / 2; i++)
111		buf[i] = pool[(pool_pos - i) & POOL_WORDS_MASK];
112	hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) buf,
113		  sizeof(buf), hash);
114	/*
115	 * Fold the hash to further reduce any potential output pattern.
116	 * Though, compromise this to reduce CPU use for the most common output
117	 * length (32) and return 16 bytes from instead of only half.
118	 */
119	hash_ptr = (u32 *) hash;
120	hash_ptr[0] ^= hash_ptr[4];
121	os_memcpy(out, hash, EXTRACT_LEN);
122}
123
124
125void random_add_randomness(const void *buf, size_t len)
126{
127	struct os_time t;
128	static unsigned int count = 0;
129
130	count++;
131	wpa_printf(MSG_MSGDUMP, "Add randomness: count=%u entropy=%u",
132		   count, entropy);
133	if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
134		/*
135		 * No need to add more entropy at this point, so save CPU and
136		 * skip the update.
137		 */
138		return;
139	}
140
141	os_get_time(&t);
142	wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
143			(const u8 *) pool, sizeof(pool));
144	random_mix_pool(&t, sizeof(t));
145	random_mix_pool(buf, len);
146	wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
147			(const u8 *) pool, sizeof(pool));
148	entropy++;
149	total_collected++;
150}
151
152
153int random_get_bytes(void *buf, size_t len)
154{
155	int ret;
156	u8 *bytes = buf;
157	size_t left;
158
159	wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u",
160		   (unsigned int) len, entropy);
161
162	/* Start with assumed strong randomness from OS */
163	ret = os_get_random(buf, len);
164	wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random",
165			buf, len);
166
167	/* Mix in additional entropy extracted from the internal pool */
168	left = len;
169	while (left) {
170		size_t siz, i;
171		u8 tmp[EXTRACT_LEN];
172		random_extract(tmp);
173		wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool",
174				tmp, sizeof(tmp));
175		siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
176		for (i = 0; i < siz; i++)
177			*bytes++ ^= tmp[i];
178		left -= siz;
179	}
180	wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
181
182	if (entropy < len)
183		entropy = 0;
184	else
185		entropy -= len;
186
187	return ret;
188}
189
190
191int random_pool_ready(void)
192{
193#ifdef __linux__
194	int fd;
195	ssize_t res;
196
197	/*
198	 * Make sure that there is reasonable entropy available before allowing
199	 * some key derivation operations to proceed.
200	 */
201
202	if (dummy_key_avail == sizeof(dummy_key))
203		return 1; /* Already initialized - good to continue */
204
205	/*
206	 * Try to fetch some more data from the kernel high quality
207	 * /dev/random. There may not be enough data available at this point,
208	 * so use non-blocking read to avoid blocking the application
209	 * completely.
210	 */
211	fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
212	if (fd < 0) {
213#ifndef CONFIG_NO_STDOUT_DEBUG
214		int error = errno;
215		perror("open(/dev/random)");
216		wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
217			   strerror(error));
218#endif /* CONFIG_NO_STDOUT_DEBUG */
219		return -1;
220	}
221
222	res = read(fd, dummy_key + dummy_key_avail,
223		   sizeof(dummy_key) - dummy_key_avail);
224	if (res < 0) {
225		wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
226			   "%s", strerror(errno));
227		res = 0;
228	}
229	wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from "
230		   "/dev/random", (unsigned) res,
231		   (unsigned) (sizeof(dummy_key) - dummy_key_avail));
232	dummy_key_avail += res;
233	close(fd);
234
235	if (dummy_key_avail == sizeof(dummy_key))
236		return 1;
237
238	wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
239		   "random data available from /dev/random",
240		   (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key));
241
242	if (own_pool_ready >= MIN_READY_MARK ||
243	    total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) {
244		wpa_printf(MSG_INFO, "random: Allow operation to proceed "
245			   "based on internal entropy");
246		return 1;
247	}
248
249	wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
250		   "secure operations");
251	return 0;
252#else /* __linux__ */
253	/* TODO: could do similar checks on non-Linux platforms */
254	return 1;
255#endif /* __linux__ */
256}
257
258
259void random_mark_pool_ready(void)
260{
261	own_pool_ready++;
262	wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be "
263		   "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK);
264}
265
266
267#ifdef __linux__
268
269static void random_close_fd(void)
270{
271	if (random_fd >= 0) {
272		eloop_unregister_read_sock(random_fd);
273		close(random_fd);
274		random_fd = -1;
275	}
276}
277
278
279static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
280{
281	ssize_t res;
282
283	if (dummy_key_avail == sizeof(dummy_key)) {
284		random_close_fd();
285		return;
286	}
287
288	res = read(sock, dummy_key + dummy_key_avail,
289		   sizeof(dummy_key) - dummy_key_avail);
290	if (res < 0) {
291		wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
292			   "%s", strerror(errno));
293		return;
294	}
295
296	wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
297		   (unsigned) res,
298		   (unsigned) (sizeof(dummy_key) - dummy_key_avail));
299	dummy_key_avail += res;
300
301	if (dummy_key_avail == sizeof(dummy_key))
302		random_close_fd();
303}
304
305#endif /* __linux__ */
306
307
308void random_init(void)
309{
310#ifdef __linux__
311	if (random_fd >= 0)
312		return;
313
314	random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
315	if (random_fd < 0) {
316#ifndef CONFIG_NO_STDOUT_DEBUG
317		int error = errno;
318		perror("open(/dev/random)");
319		wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
320			   strerror(error));
321#endif /* CONFIG_NO_STDOUT_DEBUG */
322		return;
323	}
324	wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
325		   "/dev/random");
326
327	eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
328#endif /* __linux__ */
329}
330
331
332void random_deinit(void)
333{
334#ifdef __linux__
335	random_close_fd();
336#endif /* __linux__ */
337}
338