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 #ifdef CONFIG_GETRANDOM
  29 #include <sys/random.h>
  30 #endif /* CONFIG_GETRANDOM */
  31 #endif /* __linux__ */
  32
  33 #include "utils/common.h"
  34 #include "utils/eloop.h"
  35 #include "crypto/crypto.h"
  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
  47 #define MIN_READY_MARK 2
  48
  49 static u32 pool[POOL_WORDS];
  50 static unsigned int input_rotate = 0;
  51 static unsigned int pool_pos = 0;
  52 static u8 dummy_key[20];
  53 #ifdef __linux__
  54 static size_t dummy_key_avail = 0;
  55 static int random_fd = -1;
  56 #endif /* __linux__ */
  57 static unsigned int own_pool_ready = 0;
  58 #define RANDOM_ENTROPY_SIZE 20
  59 static char *random_entropy_file = NULL;
  60
  61 #define MIN_COLLECT_ENTROPY 1000
  62 static unsigned int entropy = 0;
  63 static unsigned int total_collected = 0;
  64
  65
  66 static void random_write_entropy(void);
  67
  68
  69 static u32 __ROL32(u32 x, u32 y)
  70 {
  71         if (y == 0)
  72                 return x;
  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         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         }
 144         wpa_printf(MSG_EXCESSIVE, "Add randomness: count=%u entropy=%u",
 145                    count, entropy);
 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++;
 155         total_collected++;
 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
 187 #ifdef CONFIG_FIPS
 188         /* Mix in additional entropy from the crypto module */
 189         bytes = buf;
 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
 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 }
 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         /*
 234          * Try to fetch some more data from the kernel high quality RNG.
 235          * There may not be enough data available at this point,
 236          * so use non-blocking read to avoid blocking the application
 237          * completely.
 238          */
 239
 240 #ifdef CONFIG_GETRANDOM
 241         res = getrandom(dummy_key + dummy_key_avail,
 242                         sizeof(dummy_key) - dummy_key_avail, GRND_NONBLOCK);
 243         if (res < 0) {
 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);
 275         }
 276
 277         wpa_printf(MSG_DEBUG, "random: Got %u/%u random bytes", (unsigned) res,
 278                    (unsigned) (sizeof(dummy_key) - dummy_key_avail));
 279         dummy_key_avail += res;
 280
 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();
 285                 return 1;
 286         }
 287
 288         wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
 289                    "random data available",
 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);
 314         random_write_entropy();
 315 }
 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
 352         if (dummy_key_avail == sizeof(dummy_key)) {
 353                 random_close_fd();
 354                 if (own_pool_ready < MIN_READY_MARK)
 355                         own_pool_ready = MIN_READY_MARK;
 356                 random_write_entropy();
 357         }
 358 }
 359
 360 #endif /* __linux__ */
 361
 362
 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);
 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)
 392 {
 393         char buf[RANDOM_ENTROPY_SIZE];
 394         FILE *f;
 395         u8 opr;
 396         int fail = 0;
 397
 398         if (!random_entropy_file)
 399                 return;
 400
 401         if (random_get_bytes(buf, RANDOM_ENTROPY_SIZE) < 0)
 402                 return;
 403
 404         f = fopen(random_entropy_file, "wb");
 405         if (f == NULL) {
 406                 wpa_printf(MSG_ERROR, "random: Could not open entropy file %s "
 407                            "for writing", random_entropy_file);
 408                 return;
 409         }
 410
 411         opr = own_pool_ready > 0xff ? 0xff : own_pool_ready;
 412         if (fwrite(&opr, 1, 1, f) != 1 ||
 413             fwrite(buf, RANDOM_ENTROPY_SIZE, 1, f) != 1)
 414                 fail = 1;
 415         fclose(f);
 416         if (fail) {
 417                 wpa_printf(MSG_ERROR, "random: Could not write entropy data "
 418                            "to %s", random_entropy_file);
 419                 return;
 420         }
 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
 437 #ifdef __linux__
 438         if (random_fd >= 0)
 439                 return;
 440
 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
 454         random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
 455         if (random_fd < 0) {
 456                 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
 457                            strerror(errno));
 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__ */
 465
 466         random_write_entropy();
 467 }
 468
 469
 470 void random_deinit(void)
 471 {
 472 #ifdef __linux__
 473         random_close_fd();
 474 #endif /* __linux__ */
 475         random_write_entropy();
 476         os_free(random_entropy_file);
 477         random_entropy_file = NULL;
 478 }