]>
Commit | Line | Data |
---|---|---|
bbb921da JM |
1 | /* |
2 | * Random number generator | |
d47fa330 | 3 | * Copyright (c) 2010-2011, Jouni Malinen <j@w1.fi> |
bbb921da JM |
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" | |
08704cd8 JM |
32 | #ifdef __linux__ |
33 | #include <fcntl.h> | |
34 | #endif /* __linux__ */ | |
bbb921da JM |
35 | |
36 | #include "utils/common.h" | |
d47fa330 | 37 | #include "utils/eloop.h" |
bbb921da JM |
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 | |
08704cd8 | 49 | #define MIN_READY_MARK 2 |
bbb921da JM |
50 | |
51 | static u32 pool[POOL_WORDS]; | |
52 | static unsigned int input_rotate = 0; | |
53 | static unsigned int pool_pos = 0; | |
08704cd8 | 54 | static u8 dummy_key[20]; |
b993e77b | 55 | #ifdef __linux__ |
08704cd8 | 56 | static size_t dummy_key_avail = 0; |
d47fa330 | 57 | static int random_fd = -1; |
b993e77b | 58 | #endif /* __linux__ */ |
08704cd8 | 59 | static unsigned int own_pool_ready = 0; |
38e24575 JM |
60 | #define RANDOM_ENTROPY_SIZE 20 |
61 | static char *random_entropy_file = NULL; | |
62 | static int random_entropy_file_read = 0; | |
bbb921da JM |
63 | |
64 | #define MIN_COLLECT_ENTROPY 1000 | |
65 | static unsigned int entropy = 0; | |
08704cd8 | 66 | static unsigned int total_collected = 0; |
bbb921da JM |
67 | |
68 | ||
38e24575 JM |
69 | static void random_write_entropy(void); |
70 | ||
71 | ||
bbb921da JM |
72 | static u32 __ROL32(u32 x, u32 y) |
73 | { | |
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++; | |
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++; | |
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 | } | |
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 | } | |
08704cd8 JM |
195 | |
196 | ||
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) { | |
805253d8 | 219 | #ifndef CONFIG_NO_STDOUT_DEBUG |
08704cd8 JM |
220 | int error = errno; |
221 | perror("open(/dev/random)"); | |
222 | wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s", | |
223 | strerror(error)); | |
805253d8 | 224 | #endif /* CONFIG_NO_STDOUT_DEBUG */ |
08704cd8 JM |
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 | ||
38e24575 JM |
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(); | |
08704cd8 | 245 | return 1; |
38e24575 | 246 | } |
08704cd8 JM |
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 | ||
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); | |
38e24575 | 274 | random_write_entropy(); |
08704cd8 | 275 | } |
d47fa330 JM |
276 | |
277 | ||
278 | #ifdef __linux__ | |
279 | ||
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 | ||
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 | ||
38e24575 | 312 | if (dummy_key_avail == sizeof(dummy_key)) { |
d47fa330 | 313 | random_close_fd(); |
38e24575 JM |
314 | if (own_pool_ready < MIN_READY_MARK) |
315 | own_pool_ready = MIN_READY_MARK; | |
316 | random_write_entropy(); | |
317 | } | |
d47fa330 JM |
318 | } |
319 | ||
320 | #endif /* __linux__ */ | |
321 | ||
322 | ||
38e24575 JM |
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 | ||
352 | static void random_write_entropy(void) | |
d47fa330 | 353 | { |
38e24575 JM |
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 | ||
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 | ||
d47fa330 JM |
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__ */ | |
38e24575 JM |
409 | |
410 | random_write_entropy(); | |
d47fa330 JM |
411 | } |
412 | ||
413 | ||
414 | void random_deinit(void) | |
415 | { | |
416 | #ifdef __linux__ | |
417 | random_close_fd(); | |
418 | #endif /* __linux__ */ | |
38e24575 JM |
419 | random_write_entropy(); |
420 | os_free(random_entropy_file); | |
421 | random_entropy_file = NULL; | |
d47fa330 | 422 | } |