contrib/hostapd/src/crypto/random.c

   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
  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 }