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