]>
Commit | Line | Data |
---|---|---|
bbb921da JM |
1 | /* |
2 | * Random number generator | |
d47fa330 | 3 | * Copyright (c) 2010-2011, Jouni Malinen <j@w1.fi> |
bbb921da | 4 | * |
0f3d578e JM |
5 | * This software may be distributed under the terms of the BSD license. |
6 | * See README for more details. | |
bbb921da JM |
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" | |
08704cd8 JM |
26 | #ifdef __linux__ |
27 | #include <fcntl.h> | |
89a7cdd6 LR |
28 | #ifdef CONFIG_GETRANDOM |
29 | #include <sys/random.h> | |
30 | #endif /* CONFIG_GETRANDOM */ | |
08704cd8 | 31 | #endif /* __linux__ */ |
bbb921da JM |
32 | |
33 | #include "utils/common.h" | |
d47fa330 | 34 | #include "utils/eloop.h" |
982bafed | 35 | #include "crypto/crypto.h" |
bbb921da JM |
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 | |
08704cd8 | 47 | #define MIN_READY_MARK 2 |
bbb921da JM |
48 | |
49 | static u32 pool[POOL_WORDS]; | |
50 | static unsigned int input_rotate = 0; | |
51 | static unsigned int pool_pos = 0; | |
08704cd8 | 52 | static u8 dummy_key[20]; |
b993e77b | 53 | #ifdef __linux__ |
08704cd8 | 54 | static size_t dummy_key_avail = 0; |
d47fa330 | 55 | static int random_fd = -1; |
b993e77b | 56 | #endif /* __linux__ */ |
08704cd8 | 57 | static unsigned int own_pool_ready = 0; |
38e24575 JM |
58 | #define RANDOM_ENTROPY_SIZE 20 |
59 | static char *random_entropy_file = NULL; | |
bbb921da JM |
60 | |
61 | #define MIN_COLLECT_ENTROPY 1000 | |
62 | static unsigned int entropy = 0; | |
08704cd8 | 63 | static unsigned int total_collected = 0; |
bbb921da JM |
64 | |
65 | ||
38e24575 JM |
66 | static void random_write_entropy(void); |
67 | ||
68 | ||
bbb921da JM |
69 | static u32 __ROL32(u32 x, u32 y) |
70 | { | |
333517ac MB |
71 | if (y == 0) |
72 | return x; | |
73 | ||
bbb921da JM |
74 | return (x << (y & 31)) | (x >> (32 - (y & 31))); |
75 | } | |
76 | ||
77 | ||
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 | ||
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 | ||
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++; | |
bbb921da JM |
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 | } | |
3208b5a0 JM |
144 | wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u", |
145 | count, entropy); | |
bbb921da JM |
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++; | |
08704cd8 | 155 | total_collected++; |
bbb921da JM |
156 | } |
157 | ||
158 | ||
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 | } | |
982bafed JM |
186 | |
187 | #ifdef CONFIG_FIPS | |
188 | /* Mix in additional entropy from the crypto module */ | |
f413eb03 | 189 | bytes = buf; |
982bafed JM |
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 | ||
bbb921da JM |
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 | } | |
08704cd8 JM |
217 | |
218 | ||
219 | int 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 | /* | |
89a7cdd6 LR |
234 | * Try to fetch some more data from the kernel high quality RNG. |
235 | * There may not be enough data available at this point, | |
08704cd8 JM |
236 | * so use non-blocking read to avoid blocking the application |
237 | * completely. | |
238 | */ | |
08704cd8 | 239 | |
89a7cdd6 LR |
240 | #ifdef CONFIG_GETRANDOM |
241 | res = getrandom(dummy_key + dummy_key_avail, | |
242 | sizeof(dummy_key) - dummy_key_avail, GRND_NONBLOCK); | |
08704cd8 | 243 | if (res < 0) { |
89a7cdd6 LR |
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); | |
08704cd8 | 275 | } |
89a7cdd6 LR |
276 | |
277 | wpa_printf(MSG_DEBUG, "random: Got %u/%u random bytes", (unsigned) res, | |
08704cd8 JM |
278 | (unsigned) (sizeof(dummy_key) - dummy_key_avail)); |
279 | dummy_key_avail += res; | |
08704cd8 | 280 | |
38e24575 JM |
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(); | |
08704cd8 | 285 | return 1; |
38e24575 | 286 | } |
08704cd8 JM |
287 | |
288 | wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong " | |
89a7cdd6 | 289 | "random data available", |
08704cd8 JM |
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 | ||
309 | void 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); | |
38e24575 | 314 | random_write_entropy(); |
08704cd8 | 315 | } |
d47fa330 JM |
316 | |
317 | ||
318 | #ifdef __linux__ | |
319 | ||
320 | static 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 | ||
330 | static 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 | ||
38e24575 | 352 | if (dummy_key_avail == sizeof(dummy_key)) { |
d47fa330 | 353 | random_close_fd(); |
38e24575 JM |
354 | if (own_pool_ready < MIN_READY_MARK) |
355 | own_pool_ready = MIN_READY_MARK; | |
356 | random_write_entropy(); | |
357 | } | |
d47fa330 JM |
358 | } |
359 | ||
360 | #endif /* __linux__ */ | |
361 | ||
362 | ||
38e24575 JM |
363 | static 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); | |
38e24575 JM |
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 | ||
391 | static void random_write_entropy(void) | |
d47fa330 | 392 | { |
38e24575 JM |
393 | char buf[RANDOM_ENTROPY_SIZE]; |
394 | FILE *f; | |
395 | u8 opr; | |
2e923102 | 396 | int fail = 0; |
38e24575 JM |
397 | |
398 | if (!random_entropy_file) | |
399 | return; | |
400 | ||
15f09614 JM |
401 | if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0) |
402 | return; | |
38e24575 JM |
403 | |
404 | f = fopen(random_entropy_file, "wb"); | |
405 | if (f == NULL) { | |
9339bd5c PR |
406 | wpa_printf(MSG_ERROR, "random: Could not open entropy file %s " |
407 | "for writing", random_entropy_file); | |
38e24575 JM |
408 | return; |
409 | } | |
410 | ||
411 | opr = own_pool_ready > 0xff ? 0xff : own_pool_ready; | |
2e923102 JM |
412 | if (fwrite(&opr, 1, 1, f) != 1 || |
413 | fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1) | |
414 | fail = 1; | |
38e24575 | 415 | fclose(f); |
2e923102 | 416 | if (fail) { |
9339bd5c PR |
417 | wpa_printf(MSG_ERROR, "random: Could not write entropy data " |
418 | "to %s", random_entropy_file); | |
2e923102 JM |
419 | return; |
420 | } | |
38e24575 JM |
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 | ||
428 | void 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 | ||
d47fa330 JM |
437 | #ifdef __linux__ |
438 | if (random_fd >= 0) | |
439 | return; | |
440 | ||
89a7cdd6 LR |
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 | ||
d47fa330 JM |
454 | random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK); |
455 | if (random_fd < 0) { | |
d47fa330 | 456 | wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", |
a193231d | 457 | strerror(errno)); |
d47fa330 JM |
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__ */ | |
38e24575 JM |
465 | |
466 | random_write_entropy(); | |
d47fa330 JM |
467 | } |
468 | ||
469 | ||
470 | void random_deinit(void) | |
471 | { | |
472 | #ifdef __linux__ | |
473 | random_close_fd(); | |
474 | #endif /* __linux__ */ | |
38e24575 JM |
475 | random_write_entropy(); |
476 | os_free(random_entropy_file); | |
477 | random_entropy_file = NULL; | |
d47fa330 | 478 | } |