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