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
51 static u32 pool[POOL_WORDS];
52 static unsigned int input_rotate = 0;
53 static unsigned int pool_pos = 0;
54 static u8 dummy_key[20];
55 #ifdef __linux__
56 static size_t dummy_key_avail = 0;
57 static int random_fd = -1;
58 #endif /* __linux__ */
59 static unsigned int own_pool_ready = 0;
60 #define RANDOM_ENTROPY_SIZE 20
61 static char *random_entropy_file = NULL;
62 static int random_entropy_file_read = 0;
63
64 #define MIN_COLLECT_ENTROPY 1000
65 static unsigned int entropy = 0;
66 static unsigned int total_collected = 0;
67
68
69 static void random_write_entropy(void);
70
71
__ROL32(u32 x,u32 y)72 static u32 __ROL32(u32 x, u32 y)
73 {
74 return (x << (y & 31)) | (x >> (32 - (y & 31)));
75 }
76
77
random_mix_pool(const void * buf,size_t len)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
random_extract(u8 * out)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
random_add_randomness(const void * buf,size_t len)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 wpa_printf(MSG_MSGDUMP, "Add randomness: count=%u entropy=%u",
138 count, entropy);
139 if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
140 /*
141 * No need to add more entropy at this point, so save CPU and
142 * skip the update.
143 */
144 return;
145 }
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
random_get_bytes(void * buf,size_t len)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 wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
187
188 if (entropy < len)
189 entropy = 0;
190 else
191 entropy -= len;
192
193 return ret;
194 }
195
196
random_pool_ready(void)197 int random_pool_ready(void)
198 {
199 #ifdef __linux__
200 int fd;
201 ssize_t res;
202
203 /*
204 * Make sure that there is reasonable entropy available before allowing
205 * some key derivation operations to proceed.
206 */
207
208 if (dummy_key_avail == sizeof(dummy_key))
209 return 1; /* Already initialized - good to continue */
210
211 /*
212 * Try to fetch some more data from the kernel high quality
213 * /dev/random. There may not be enough data available at this point,
214 * so use non-blocking read to avoid blocking the application
215 * completely.
216 */
217 fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
218 if (fd < 0) {
219 #ifndef CONFIG_NO_STDOUT_DEBUG
220 int error = errno;
221 perror("open(/dev/random)");
222 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
223 strerror(error));
224 #endif /* CONFIG_NO_STDOUT_DEBUG */
225 return -1;
226 }
227
228 res = read(fd, dummy_key + dummy_key_avail,
229 sizeof(dummy_key) - dummy_key_avail);
230 if (res < 0) {
231 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
232 "%s", strerror(errno));
233 res = 0;
234 }
235 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from "
236 "/dev/random", (unsigned) res,
237 (unsigned) (sizeof(dummy_key) - dummy_key_avail));
238 dummy_key_avail += res;
239 close(fd);
240
241 if (dummy_key_avail == sizeof(dummy_key)) {
242 if (own_pool_ready < MIN_READY_MARK)
243 own_pool_ready = MIN_READY_MARK;
244 random_write_entropy();
245 return 1;
246 }
247
248 wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
249 "random data available from /dev/random",
250 (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key));
251
252 if (own_pool_ready >= MIN_READY_MARK ||
253 total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) {
254 wpa_printf(MSG_INFO, "random: Allow operation to proceed "
255 "based on internal entropy");
256 return 1;
257 }
258
259 wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
260 "secure operations");
261 return 0;
262 #else /* __linux__ */
263 /* TODO: could do similar checks on non-Linux platforms */
264 return 1;
265 #endif /* __linux__ */
266 }
267
268
random_mark_pool_ready(void)269 void random_mark_pool_ready(void)
270 {
271 own_pool_ready++;
272 wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be "
273 "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK);
274 random_write_entropy();
275 }
276
277
278 #ifdef __linux__
279
random_close_fd(void)280 static void random_close_fd(void)
281 {
282 if (random_fd >= 0) {
283 eloop_unregister_read_sock(random_fd);
284 close(random_fd);
285 random_fd = -1;
286 }
287 }
288
289
random_read_fd(int sock,void * eloop_ctx,void * sock_ctx)290 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
291 {
292 ssize_t res;
293
294 if (dummy_key_avail == sizeof(dummy_key)) {
295 random_close_fd();
296 return;
297 }
298
299 res = read(sock, dummy_key + dummy_key_avail,
300 sizeof(dummy_key) - dummy_key_avail);
301 if (res < 0) {
302 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
303 "%s", strerror(errno));
304 return;
305 }
306
307 wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
308 (unsigned) res,
309 (unsigned) (sizeof(dummy_key) - dummy_key_avail));
310 dummy_key_avail += res;
311
312 if (dummy_key_avail == sizeof(dummy_key)) {
313 random_close_fd();
314 if (own_pool_ready < MIN_READY_MARK)
315 own_pool_ready = MIN_READY_MARK;
316 random_write_entropy();
317 }
318 }
319
320 #endif /* __linux__ */
321
322
random_read_entropy(void)323 static void random_read_entropy(void)
324 {
325 char *buf;
326 size_t len;
327
328 if (!random_entropy_file)
329 return;
330
331 buf = os_readfile(random_entropy_file, &len);
332 if (buf == NULL)
333 return; /* entropy file not yet available */
334
335 if (len != 1 + RANDOM_ENTROPY_SIZE) {
336 wpa_printf(MSG_DEBUG, "random: Invalid entropy file %s",
337 random_entropy_file);
338 os_free(buf);
339 return;
340 }
341
342 own_pool_ready = (u8) buf[0];
343 random_add_randomness(buf + 1, RANDOM_ENTROPY_SIZE);
344 random_entropy_file_read = 1;
345 os_free(buf);
346 wpa_printf(MSG_DEBUG, "random: Added entropy from %s "
347 "(own_pool_ready=%u)",
348 random_entropy_file, own_pool_ready);
349 }
350
351
random_write_entropy(void)352 static void random_write_entropy(void)
353 {
354 char buf[RANDOM_ENTROPY_SIZE];
355 FILE *f;
356 u8 opr;
357
358 if (!random_entropy_file)
359 return;
360
361 random_get_bytes(buf, RANDOM_ENTROPY_SIZE);
362
363 f = fopen(random_entropy_file, "wb");
364 if (f == NULL) {
365 wpa_printf(MSG_ERROR, "random: Could not write %s",
366 random_entropy_file);
367 return;
368 }
369
370 opr = own_pool_ready > 0xff ? 0xff : own_pool_ready;
371 fwrite(&opr, 1, 1, f);
372 fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f);
373 fclose(f);
374
375 wpa_printf(MSG_DEBUG, "random: Updated entropy file %s "
376 "(own_pool_ready=%u)",
377 random_entropy_file, own_pool_ready);
378 }
379
380
random_init(const char * entropy_file)381 void random_init(const char *entropy_file)
382 {
383 os_free(random_entropy_file);
384 if (entropy_file)
385 random_entropy_file = os_strdup(entropy_file);
386 else
387 random_entropy_file = NULL;
388 random_read_entropy();
389
390 #ifdef __linux__
391 if (random_fd >= 0)
392 return;
393
394 random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
395 if (random_fd < 0) {
396 #ifndef CONFIG_NO_STDOUT_DEBUG
397 int error = errno;
398 perror("open(/dev/random)");
399 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
400 strerror(error));
401 #endif /* CONFIG_NO_STDOUT_DEBUG */
402 return;
403 }
404 wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
405 "/dev/random");
406
407 eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
408 #endif /* __linux__ */
409
410 random_write_entropy();
411 }
412
413
random_deinit(void)414 void random_deinit(void)
415 {
416 #ifdef __linux__
417 random_close_fd();
418 #endif /* __linux__ */
419 random_write_entropy();
420 os_free(random_entropy_file);
421 random_entropy_file = NULL;
422 }
423