Maintain internal entropy pool for augmenting random number generation

By default, make hostapd and wpa_supplicant maintain an internal
entropy pool that is fed with following information:

hostapd:
- Probe Request frames (timing, RSSI)
- Association events (timing)
- SNonce from Supplicants

wpa_supplicant:
- Scan results (timing, signal/noise)
- Association events (timing)

The internal pool is used to augment the random numbers generated
with the OS mechanism (os_get_random()). While the internal
implementation is not expected to be very strong due to limited
amount of generic (non-platform specific) information to feed the
pool, this may strengthen key derivation on some devices that are
not configured to provide strong random numbers through
os_get_random() (e.g., /dev/urandom on Linux/BSD).

This new mechanism is not supposed to replace proper OS provided
random number generation mechanism. The OS mechanism needs to be
initialized properly (e.g., hw random number generator,
maintaining entropy pool over reboots, etc.) for any of the
security assumptions to hold.

If the os_get_random() is known to provide strong ramdom data (e.g., on
Linux/BSD, the board in question is known to have reliable source of
random data from /dev/urandom), the internal hostapd random pool can be
disabled. This will save some in binary size and CPU use. However, this
should only be considered for builds that are known to be used on
devices that meet the requirements described above. The internal pool
is disabled by adding CONFIG_NO_RANDOM_POOL=y to the .config file.

diff --git a/hostapd/Makefile b/hostapd/Makefile
index bb5e387c6f0a67e5fa6147045e286bb7db7d6ed2..a99ebc0f514f4bff7bad6a617a62b1cf6200cf0c 100644 (file)
--- a/hostapd/Makefile
+++ b/hostapd/Makefile
@@ -646,6 +646,7 @@ endif
 ifdef NEED_MD5
 ifdef CONFIG_INTERNAL_MD5
 OBJS += ../src/crypto/md5-internal.o
+HOBJS += ../src/crypto/md5-internal.o
 endif
 endif
 
@@ -686,6 +687,15 @@ OBJS += ../src/crypto/dh_group5.o
 endif
 endif
 
+ifdef CONFIG_NO_RANDOM_POOL
+CFLAGS += -DCONFIG_NO_RANDOM_POOL
+else
+OBJS += ../src/crypto/random.o
+HOBJS += ../src/crypto/random.o
+HOBJS += $(SHA1OBJS)
+HOBJS += ../src/crypto/md5.o
+endif
+
 ifdef CONFIG_RADIUS_SERVER
 CFLAGS += -DRADIUS_SERVER
 OBJS += ../src/radius/radius_server.o

diff --git a/hostapd/defconfig b/hostapd/defconfig
index 61793c47921cc863b41e62590b007490c9c35ca4..8a87646b2e124a70dfa47a5fbf929be8d7e5538a 100644 (file)
--- a/hostapd/defconfig
+++ b/hostapd/defconfig
@@ -179,3 +179,28 @@ CONFIG_IPV6=y
 #LIBS += -lbfd -liberty -lz
 #LIBS_p += -lbfd -liberty -lz
 #LIBS_c += -lbfd -liberty -lz
+
+# hostapd depends on strong random number generation being available from the
+# operating system. os_get_random() function is used to fetch random data when
+# needed, e.g., for key generation. On Linux and BSD systems, this works by
+# reading /dev/urandom. It should be noted that the OS entropy pool needs to be
+# properly initialized before hostapd is started. This is important especially
+# on embedded devices that do not have a hardware random number generator and
+# may by default start up with minimal entropy available for random number
+# generation.
+#
+# As a safety net, hostapd is by default trying to internally collect
+# additional entropy for generating random data to mix in with the data
+# fetched from the OS. This by itself is not considered to be very strong, but
+# it may help in cases where the system pool is not initialized properly.
+# However, it is very strongly recommended that the system pool is initialized
+# with enough entropy either by using hardware assisted random number
+# generatior or by storing state over device reboots.
+#
+# If the os_get_random() is known to provide strong ramdom data (e.g., on
+# Linux/BSD, the board in question is known to have reliable source of random
+# data from /dev/urandom), the internal hostapd random pool can be disabled.
+# This will save some in binary size and CPU use. However, this should only be
+# considered for builds that are known to be used on devices that meet the
+# requirements described above.
+#CONFIG_NO_RANDOM_POOL=y

diff --git a/src/ap/drv_callbacks.c b/src/ap/drv_callbacks.c
index 7c5b79418cc1cc06b7145ebd2d4f44b187b9a7a7..04ff6a155cae508b18f2be0e2f9584363f6e954a 100644 (file)
--- a/src/ap/drv_callbacks.c
+++ b/src/ap/drv_callbacks.c
@@ -20,6 +20,7 @@
 #include "common/ieee802_11_defs.h"
 #include "common/ieee802_11_common.h"
 #include "common/wpa_ctrl.h"
+#include "crypto/random.h"
 #include "p2p/p2p.h"
 #include "wps/wps.h"
 #include "hostapd.h"
@@ -58,6 +59,7 @@ int hostapd_notif_assoc(struct hostapd_data *hapd, const u8 *addr,
                           "no address");
                return -1;
        }
+       random_add_randomness(addr, ETH_ALEN);
 
        hostapd_logger(hapd, addr, HOSTAPD_MODULE_IEEE80211,
                       HOSTAPD_LEVEL_INFO, "associated");
@@ -348,6 +350,8 @@ static void hostapd_mgmt_rx(struct hostapd_data *hapd, struct rx_mgmt *rx_mgmt)
                                        rx_mgmt->frame_len, &fi);
        } else
                ieee802_11_mgmt(hapd, rx_mgmt->frame, rx_mgmt->frame_len, &fi);
+
+       random_add_randomness(&fi, sizeof(fi));
 }
 
 
@@ -371,6 +375,8 @@ static int hostapd_probe_req_rx(struct hostapd_data *hapd, const u8 *sa,
        size_t i;
        int ret = 0;
 
+       if (sa)
+               random_add_randomness(sa, ETH_ALEN);
        for (i = 0; hapd->probereq_cb && i < hapd->num_probereq_cb; i++) {
                if (hapd->probereq_cb[i].cb(hapd->probereq_cb[i].ctx,
                                            sa, ie, ie_len) > 0) {

diff --git a/src/ap/wpa_auth.c b/src/ap/wpa_auth.c
index 7d66aff3fadbfa747f0fe2ba24aad4fff05842a9..851612ef8084ef82391be670d5b6cba2e4248af2 100644 (file)
--- a/src/ap/wpa_auth.c
+++ b/src/ap/wpa_auth.c
@@ -824,6 +824,7 @@ void wpa_receive(struct wpa_authenticator *wpa_auth,
                                         sm->wpa_ptk_state);
                        return;
                }
+               random_add_randomness(key->key_nonce, WPA_NONCE_LEN);
                if (wpa_parse_kde_ies((u8 *) (key + 1), key_data_length,
                                      &kde) < 0) {
                        wpa_auth_vlogger(wpa_auth, sm->addr, LOGGER_INFO,

diff --git a/src/crypto/random.c b/src/crypto/random.c
new file mode 100644 (file)
index 0000000..33eae4d
--- /dev/null
+++ b/src/crypto/random.c
@@ -0,0 +1,176 @@
+/*
+ * Random number generator
+ * Copyright (c) 2010, Jouni Malinen <j@w1.fi>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * Alternatively, this software may be distributed under the terms of BSD
+ * license.
+ *
+ * See README and COPYING for more details.
+ *
+ * This random number generator is used to provide additional entropy to the
+ * one provided by the operating system (os_get_random()) for session key
+ * generation. The os_get_random() output is expected to be secure and the
+ * implementation here is expected to provide only limited protection against
+ * cases where os_get_random() cannot provide strong randomness. This
+ * implementation shall not be assumed to be secure as the sole source of
+ * randomness. The random_get_bytes() function mixes in randomness from
+ * os_get_random() and as such, calls to os_get_random() can be replaced with
+ * calls to random_get_bytes() without reducing security.
+ *
+ * The design here follows partially the design used in the Linux
+ * drivers/char/random.c, but the implementation here is simpler and not as
+ * strong. This is a compromise to reduce duplicated CPU effort and to avoid
+ * extra code/memory size. As pointed out above, os_get_random() needs to be
+ * guaranteed to be secure for any of the security assumptions to hold.
+ */
+
+#include "utils/includes.h"
+
+#include "utils/common.h"
+#include "sha1.h"
+#include "random.h"
+
+#define POOL_WORDS 32
+#define POOL_WORDS_MASK (POOL_WORDS - 1)
+#define POOL_TAP1 26
+#define POOL_TAP2 20
+#define POOL_TAP3 14
+#define POOL_TAP4 7
+#define POOL_TAP5 1
+#define EXTRACT_LEN 16
+
+static u32 pool[POOL_WORDS];
+static unsigned int input_rotate = 0;
+static unsigned int pool_pos = 0;
+static const u8 dummy_key[20];
+
+#define MIN_COLLECT_ENTROPY 1000
+static unsigned int entropy = 0;
+
+
+static u32 __ROL32(u32 x, u32 y)
+{
+       return (x << (y & 31)) | (x >> (32 - (y & 31)));
+}
+
+
+static void random_mix_pool(const void *buf, size_t len)
+{
+       static const u32 twist[8] = {
+               0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
+               0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
+       };
+       const u8 *pos = buf;
+       u32 w;
+
+       wpa_hexdump_key(MSG_EXCESSIVE, "random_mix_pool", buf, len);
+
+       while (len--) {
+               w = __ROL32(*pos++, input_rotate & 31);
+               input_rotate += pool_pos ? 7 : 14;
+               pool_pos = (pool_pos - 1) & POOL_WORDS_MASK;
+               w ^= pool[pool_pos];
+               w ^= pool[(pool_pos + POOL_TAP1) & POOL_WORDS_MASK];
+               w ^= pool[(pool_pos + POOL_TAP2) & POOL_WORDS_MASK];
+               w ^= pool[(pool_pos + POOL_TAP3) & POOL_WORDS_MASK];
+               w ^= pool[(pool_pos + POOL_TAP4) & POOL_WORDS_MASK];
+               w ^= pool[(pool_pos + POOL_TAP5) & POOL_WORDS_MASK];
+               pool[pool_pos] = (w >> 3) ^ twist[w & 7];
+       }
+}
+
+
+static void random_extract(u8 *out)
+{
+       unsigned int i;
+       u8 hash[SHA1_MAC_LEN];
+       u32 *hash_ptr;
+       u32 buf[POOL_WORDS / 2];
+
+       /* First, add hash back to pool to make backtracking more difficult. */
+       hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) pool,
+                 sizeof(pool), hash);
+       random_mix_pool(hash, sizeof(hash));
+       /* Hash half the pool to extra data */
+       for (i = 0; i < POOL_WORDS / 2; i++)
+               buf[i] = pool[(pool_pos - i) & POOL_WORDS_MASK];
+       hmac_sha1(dummy_key, sizeof(dummy_key), (const u8 *) buf,
+                 sizeof(buf), hash);
+       /*
+        * Fold the hash to further reduce any potential output pattern.
+        * Though, compromise this to reduce CPU use for the most common output
+        * length (32) and return 16 bytes from instead of only half.
+        */
+       hash_ptr = (u32 *) hash;
+       hash_ptr[0] ^= hash_ptr[4];
+       os_memcpy(out, hash, EXTRACT_LEN);
+}
+
+
+void random_add_randomness(const void *buf, size_t len)
+{
+       struct os_time t;
+       static unsigned int count = 0;
+
+       count++;
+       wpa_printf(MSG_MSGDUMP, "Add randomness: count=%u entropy=%u",
+                  count, entropy);
+       if (entropy > MIN_COLLECT_ENTROPY && (count & 0x3ff) != 0) {
+               /*
+                * No need to add more entropy at this point, so save CPU and
+                * skip the update.
+                */
+               return;
+       }
+
+       os_get_time(&t);
+       wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
+                       (const u8 *) pool, sizeof(pool));
+       random_mix_pool(&t, sizeof(t));
+       random_mix_pool(buf, len);
+       wpa_hexdump_key(MSG_EXCESSIVE, "random pool",
+                       (const u8 *) pool, sizeof(pool));
+       entropy++;
+}
+
+
+int random_get_bytes(void *buf, size_t len)
+{
+       int ret;
+       u8 *bytes = buf;
+       size_t left;
+
+       wpa_printf(MSG_MSGDUMP, "Get randomness: len=%u entropy=%u",
+                  (unsigned int) len, entropy);
+
+       /* Start with assumed strong randomness from OS */
+       ret = os_get_random(buf, len);
+       wpa_hexdump_key(MSG_EXCESSIVE, "random from os_get_random",
+                       buf, len);
+
+       /* Mix in additional entropy extracted from the internal pool */
+       left = len;
+       while (left) {
+               size_t siz, i;
+               u8 tmp[EXTRACT_LEN];
+               random_extract(tmp);
+               wpa_hexdump_key(MSG_EXCESSIVE, "random from internal pool",
+                               tmp, sizeof(tmp));
+               siz = left > EXTRACT_LEN ? EXTRACT_LEN : left;
+               for (i = 0; i < siz; i++)
+                       *bytes++ ^= tmp[i];
+               left -= siz;
+       }
+       wpa_hexdump_key(MSG_EXCESSIVE, "mixed random", buf, len);
+
+       if (entropy < len)
+               entropy = 0;
+       else
+               entropy -= len;
+
+       return ret;
+}

diff --git a/src/crypto/random.h b/src/crypto/random.h
index 749840069ad2f59ae1a1ae841d32682115ddbfa9..65a19003b334d1e730aca2a64c7eac854a9479c2 100644 (file)
--- a/src/crypto/random.h
+++ b/src/crypto/random.h
@@ -15,6 +15,12 @@
 #ifndef RANDOM_H
 #define RANDOM_H
 
+#ifdef CONFIG_NO_RANDOM_POOL
+#define random_add_randomness(b, l) do { } while (0)
 #define random_get_bytes(b, l) os_get_random((b), (l))
+#else /* CONFIG_NO_RANDOM_POOL */
+void random_add_randomness(const void *buf, size_t len);
+int random_get_bytes(void *buf, size_t len);
+#endif /* CONFIG_NO_RANDOM_POOL */
 
 #endif /* RANDOM_H */

diff --git a/wpa_supplicant/Makefile b/wpa_supplicant/Makefile
index ee086e31f4d65df1032855434c0acb93e500f242..f9fe57c8c5ad4bb89d2e781668695a2499820da5 100644 (file)
--- a/wpa_supplicant/Makefile
+++ b/wpa_supplicant/Makefile
@@ -1065,6 +1065,12 @@ OBJS += ../src/crypto/dh_group5.o
 endif
 endif
 
+ifdef CONFIG_NO_RANDOM_POOL
+CFLAGS += -DCONFIG_NO_RANDOM_POOL
+else
+OBJS += ../src/crypto/random.o
+endif
+
 ifdef CONFIG_CTRL_IFACE
 ifeq ($(CONFIG_CTRL_IFACE), y)
 ifdef CONFIG_NATIVE_WINDOWS

diff --git a/wpa_supplicant/defconfig b/wpa_supplicant/defconfig
index 50569e4918979a0b8771bf1531f40bc6dd66208a..c3b230238dc5ea549349a2003732364bcff68c69 100644 (file)
--- a/wpa_supplicant/defconfig
+++ b/wpa_supplicant/defconfig
@@ -412,3 +412,28 @@ CONFIG_PEERKEY=y
 #LIBS += -lbfd -liberty -lz
 #LIBS_p += -lbfd -liberty -lz
 #LIBS_c += -lbfd -liberty -lz
+
+# wpa_supplicant depends on strong random number generation being available
+# from the operating system. os_get_random() function is used to fetch random
+# data when needed, e.g., for key generation. On Linux and BSD systems, this
+# works by reading /dev/urandom. It should be noted that the OS entropy pool
+# needs to be properly initialized before wpa_supplicant is started. This is
+# important especially on embedded devices that do not have a hardware random
+# number generator and may by default start up with minimal entropy available
+# for random number generation.
+#
+# As a safety net, wpa_supplicant is by default trying to internally collect
+# additional entropy for generating random data to mix in with the data fetched
+# from the OS. This by itself is not considered to be very strong, but it may
+# help in cases where the system pool is not initialized properly. However, it
+# is very strongly recommended that the system pool is initialized with enough
+# entropy either by using hardware assisted random number generatior or by
+# storing state over device reboots.
+#
+# If the os_get_random() is known to provide strong ramdom data (e.g., on
+# Linux/BSD, the board in question is known to have reliable source of random
+# data from /dev/urandom), the internal wpa_supplicant random pool can be
+# disabled. This will save some in binary size and CPU use. However, this
+# should only be considered for builds that are known to be used on devices
+# that meet the requirements described above.
+#CONFIG_NO_RANDOM_POOL=y

diff --git a/wpa_supplicant/events.c b/wpa_supplicant/events.c
index 39ac33b0295b810b494a028844adb3f24e44981b..8498cbab8d498e50a293e4b7e516ace8e9b85a38 100644 (file)
--- a/wpa_supplicant/events.c
+++ b/wpa_supplicant/events.c
@@ -32,6 +32,7 @@
 #include "notify.h"
 #include "common/ieee802_11_defs.h"
 #include "common/ieee802_11_common.h"
+#include "crypto/random.h"
 #include "blacklist.h"
 #include "wpas_glue.h"
 #include "wps_supplicant.h"
@@ -838,6 +839,23 @@ static void wpa_supplicant_event_scan_results(struct wpa_supplicant *wpa_s,
                return;
        }
 
+#ifndef CONFIG_NO_RANDOM_POOL
+       size_t i, num;
+       num = scan_res->num;
+       if (num > 10)
+               num = 10;
+       for (i = 0; i < num; i++) {
+               u8 buf[5];
+               struct wpa_scan_res *res = scan_res->res[i];
+               buf[0] = res->bssid[5];
+               buf[1] = res->qual & 0xff;
+               buf[2] = res->noise & 0xff;
+               buf[3] = res->level & 0xff;
+               buf[4] = res->tsf & 0xff;
+               random_add_randomness(buf, sizeof(buf));
+       }
+#endif /* CONFIG_NO_RANDOM_POOL */
+
        if (wpa_s->scan_res_handler) {
                wpa_s->scan_res_handler(wpa_s, scan_res);
                wpa_s->scan_res_handler = NULL;
@@ -1098,6 +1116,7 @@ static void wpa_supplicant_event_assoc(struct wpa_supplicant *wpa_s,
             os_memcmp(bssid, wpa_s->bssid, ETH_ALEN) != 0)) {
                wpa_msg(wpa_s, MSG_DEBUG, "Associated to a new BSS: BSSID="
                        MACSTR, MAC2STR(bssid));
+               random_add_randomness(bssid, ETH_ALEN);
                bssid_changed = os_memcmp(wpa_s->bssid, bssid, ETH_ALEN);
                os_memcpy(wpa_s->bssid, bssid, ETH_ALEN);
                os_memset(wpa_s->pending_bssid, 0, ETH_ALEN);