src/crypto/random.c

   1 /*
   2  * Random number generator
   3  * Copyright (c) 2010-2011, Jouni Malinen <j@w1.fi>
   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"
  32 #ifdef __linux__
  33 #include <fcntl.h>
  34 #endif /* __linux__ */
  35
  36 #include "utils/common.h"
  37 #include "utils/eloop.h"
  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
  49 #define MIN_READY_MARK 2
  50
  51 static u32 pool[POOL_WORDS];
  52 static unsigned int input_rotate = 0;
  53 static unsigned int pool_pos = 0;
  54 static u8 dummy_key[20];
  55 #ifdef __linux__
  56 static size_t dummy_key_avail = 0;
  57 static int random_fd = -1;
  58 #endif /* __linux__ */
  59 static unsigned int own_pool_ready = 0;
  60
  61 #define MIN_COLLECT_ENTROPY 1000
  62 static unsigned int entropy = 0;
  63 static unsigned int total_collected = 0;
  64
  65
  66 static u32 __ROL32(u32 x, u32 y)
  67 {
  68         return (x << (y & 31)) | (x >> (32 - (y & 31)));
  69 }
  70
  71
  72 static void random_mix_pool(const void *buf, size_t len)
  73 {
  74         static const u32 twist[8] = {
  75                 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
  76                 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
  77         };
  78         const u8 *pos = buf;
  79         u32 w;
  80
  81         wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len);
  82
  83         while (len--) {
  84                 w = __ROL32(*pos++, input_rotate & 31);
  85                 input_rotate += pool_pos ? 7 : 14;
  86                 pool_pos = (pool_pos - 1) & POOL_WORDS_MASK;
  87                 w ^= pool[pool_pos];
  88                 w ^= pool[(pool_pos + POOL_TAP1) & POOL_WORDS_MASK];
  89                 w ^= pool[(pool_pos + POOL_TAP2) & POOL_WORDS_MASK];
  90                 w ^= pool[(pool_pos + POOL_TAP3) & POOL_WORDS_MASK];
  91                 w ^= pool[(pool_pos + POOL_TAP4) & POOL_WORDS_MASK];
  92                 w ^= pool[(pool_pos + POOL_TAP5) & POOL_WORDS_MASK];
  93                 pool[pool_pos] = (w >> 3) ^ twist[w & 7];
  94         }
  95 }
  96
  97
  98 static void random_extract(u8 *out)
  99 {
 100         unsigned int i;
 101         u8 hash[SHA1_MAC_LEN];
 102         u32 *hash_ptr;
 103         u32 buf[POOL_WORDS / 2];
 104
 105         /* First, add hash back to pool to make backtracking more difficult. */
 106         hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) pool,
 107                   sizeof(pool), hash);
 108         random_mix_pool(hash, sizeof(hash));
 109         /* Hash half the pool to extra data */
 110         for (i = 0; i < POOL_WORDS / 2; i++)
 111                 buf[i] = pool[(pool_pos - i) & POOL_WORDS_MASK];
 112         hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) buf,
 113                   sizeof(buf), hash);
 114         /*
 115          * Fold the hash to further reduce any potential output pattern.
 116          * Though, compromise this to reduce CPU use for the most common output
 117          * length (32) and return 16 bytes from instead of only half.
 118          */
 119         hash_ptr = (u32 *) hash;
 120         hash_ptr[0] ^= hash_ptr[4];
 121         os_memcpy(out, hash, EXTRACT_LEN);
 122 }
 123
 124
 125 void random_add_randomness(const void *buf, size_t len)
 126 {
 127         struct os_time t;
 128         static unsigned int count = 0;
 129
 130         count++;
 131         wpa_printf(MSG_MSGDUMP, "Add randomness: count=%u entropy=%u",
 132                    count, entropy);
 133         if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
 134                 /*
 135                  * No need to add more entropy at this point, so save CPU and
 136                  * skip the update.
 137                  */
 138                 return;
 139         }
 140
 141         os_get_time(&t);
 142         wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
 143                         (const u8 *) pool, sizeof(pool));
 144         random_mix_pool(&t, sizeof(t));
 145         random_mix_pool(buf, len);
 146         wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
 147                         (const u8 *) pool, sizeof(pool));
 148         entropy++;
 149         total_collected++;
 150 }
 151
 152
 153 int random_get_bytes(void *buf, size_t len)
 154 {
 155         int ret;
 156         u8 *bytes = buf;
 157         size_t left;
 158
 159         wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u",
 160                    (unsigned int) len, entropy);
 161
 162         /* Start with assumed strong randomness from OS */
 163         ret = os_get_random(buf, len);
 164         wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random",
 165                         buf, len);
 166
 167         /* Mix in additional entropy extracted from the internal pool */
 168         left = len;
 169         while (left) {
 170                 size_t siz, i;
 171                 u8 tmp[EXTRACT_LEN];
 172                 random_extract(tmp);
 173                 wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool",
 174                                 tmp, sizeof(tmp));
 175                 siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
 176                 for (i = 0; i < siz; i++)
 177                         *bytes++ ^= tmp[i];
 178                 left -= siz;
 179         }
 180         wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
 181
 182         if (entropy < len)
 183                 entropy = 0;
 184         else
 185                 entropy -= len;
 186
 187         return ret;
 188 }
 189
 190
 191 int random_pool_ready(void)
 192 {
 193 #ifdef __linux__
 194         int fd;
 195         ssize_t res;
 196
 197         /*
 198          * Make sure that there is reasonable entropy available before allowing
 199          * some key derivation operations to proceed.
 200          */
 201
 202         if (dummy_key_avail == sizeof(dummy_key))
 203                 return 1; /* Already initialized - good to continue */
 204
 205         /*
 206          * Try to fetch some more data from the kernel high quality
 207          * /dev/random. There may not be enough data available at this point,
 208          * so use non-blocking read to avoid blocking the application
 209          * completely.
 210          */
 211         fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
 212         if (fd < 0) {
 213 #ifndef CONFIG_NO_STDOUT_DEBUG
 214                 int error = errno;
 215                 perror("open(/dev/random)");
 216                 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
 217                            strerror(error));
 218 #endif /* CONFIG_NO_STDOUT_DEBUG */
 219                 return -1;
 220         }
 221
 222         res = read(fd, dummy_key + dummy_key_avail,
 223                    sizeof(dummy_key) - dummy_key_avail);
 224         if (res < 0) {
 225                 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
 226                            "%s", strerror(errno));
 227                 res = 0;
 228         }
 229         wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from "
 230                    "/dev/random", (unsigned) res,
 231                    (unsigned) (sizeof(dummy_key) - dummy_key_avail));
 232         dummy_key_avail += res;
 233         close(fd);
 234
 235         if (dummy_key_avail == sizeof(dummy_key))
 236                 return 1;
 237
 238         wpa_printf(MSG_INFO, "random: Only %u/%u bytes of strong "
 239                    "random data available from /dev/random",
 240                    (unsigned) dummy_key_avail, (unsigned) sizeof(dummy_key));
 241
 242         if (own_pool_ready >= MIN_READY_MARK ||
 243             total_collected + 10 * own_pool_ready > MIN_COLLECT_ENTROPY) {
 244                 wpa_printf(MSG_INFO, "random: Allow operation to proceed "
 245                            "based on internal entropy");
 246                 return 1;
 247         }
 248
 249         wpa_printf(MSG_INFO, "random: Not enough entropy pool available for "
 250                    "secure operations");
 251         return 0;
 252 #else /* __linux__ */
 253         /* TODO: could do similar checks on non-Linux platforms */
 254         return 1;
 255 #endif /* __linux__ */
 256 }
 257
 258
 259 void random_mark_pool_ready(void)
 260 {
 261         own_pool_ready++;
 262         wpa_printf(MSG_DEBUG, "random: Mark internal entropy pool to be "
 263                    "ready (count=%u/%u)", own_pool_ready, MIN_READY_MARK);
 264 }
 265
 266
 267 #ifdef __linux__
 268
 269 static void random_close_fd(void)
 270 {
 271         if (random_fd >= 0) {
 272                 eloop_unregister_read_sock(random_fd);
 273                 close(random_fd);
 274                 random_fd = -1;
 275         }
 276 }
 277
 278
 279 static void random_read_fd(int sock, void *eloop_ctx, void *sock_ctx)
 280 {
 281         ssize_t res;
 282
 283         if (dummy_key_avail == sizeof(dummy_key)) {
 284                 random_close_fd();
 285                 return;
 286         }
 287
 288         res = read(sock, dummy_key + dummy_key_avail,
 289                    sizeof(dummy_key) - dummy_key_avail);
 290         if (res < 0) {
 291                 wpa_printf(MSG_ERROR, "random: Cannot read from /dev/random: "
 292                            "%s", strerror(errno));
 293                 return;
 294         }
 295
 296         wpa_printf(MSG_DEBUG, "random: Got %u/%u bytes from /dev/random",
 297                    (unsigned) res,
 298                    (unsigned) (sizeof(dummy_key) - dummy_key_avail));
 299         dummy_key_avail += res;
 300
 301         if (dummy_key_avail == sizeof(dummy_key))
 302                 random_close_fd();
 303 }
 304
 305 #endif /* __linux__ */
 306
 307
 308 void random_init(void)
 309 {
 310 #ifdef __linux__
 311         if (random_fd >= 0)
 312                 return;
 313
 314         random_fd = open("/dev/random", O_RDONLY | O_NONBLOCK);
 315         if (random_fd < 0) {
 316 #ifndef CONFIG_NO_STDOUT_DEBUG
 317                 int error = errno;
 318                 perror("open(/dev/random)");
 319                 wpa_printf(MSG_ERROR, "random: Cannot open /dev/random: %s",
 320                            strerror(error));
 321 #endif /* CONFIG_NO_STDOUT_DEBUG */
 322                 return;
 323         }
 324         wpa_printf(MSG_DEBUG, "random: Trying to read entropy from "
 325                    "/dev/random");
 326
 327         eloop_register_read_sock(random_fd, random_read_fd, NULL, NULL);
 328 #endif /* __linux__ */
 329 }
 330
 331
 332 void random_deinit(void)
 333 {
 334 #ifdef __linux__
 335         random_close_fd();
 336 #endif /* __linux__ */
 337 }