Module Name: src
Committed By: tls
Date: Mon Apr 7 02:00:00 UTC 2014
Modified Files:
src/sys/kern [tls-earlyentropy]: kern_rndpool.c kern_rndq.c
src/sys/sys [tls-earlyentropy]: rnd.h
Log Message:
Entropy estimation changes:
1) Avoid wraparound problems with delta estimator by making estimation
framework 64-bit.
2) Adjust rnd_counter to always return a 64-bit value, accordingly.
3) Make delta estimator generic and create two instances: delta-time and
delta-value.
4) Add LZF estimator -- used mostly to protect us against injection of
bulk data we think is random but is really constant.
5) Allow value and time estimation/collection to be controlled separately.
6) Expose estimator performance to userspace.
To generate a diff of this commit:
cvs rdiff -u -r1.5 -r1.5.2.1 src/sys/kern/kern_rndpool.c
cvs rdiff -u -r1.23 -r1.23.2.1 src/sys/kern/kern_rndq.c
cvs rdiff -u -r1.40 -r1.40.2.1 src/sys/sys/rnd.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/kern/kern_rndpool.c
diff -u src/sys/kern/kern_rndpool.c:1.5 src/sys/kern/kern_rndpool.c:1.5.2.1
--- src/sys/kern/kern_rndpool.c:1.5 Thu Aug 29 01:04:49 2013
+++ src/sys/kern/kern_rndpool.c Mon Apr 7 02:00:00 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_rndpool.c,v 1.5 2013/08/29 01:04:49 tls Exp $ */
+/* $NetBSD: kern_rndpool.c,v 1.5.2.1 2014/04/07 02:00:00 tls Exp $ */
/*-
* Copyright (c) 1997 The NetBSD Foundation, Inc.
@@ -31,7 +31,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_rndpool.c,v 1.5 2013/08/29 01:04:49 tls Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_rndpool.c,v 1.5.2.1 2014/04/07 02:00:00 tls Exp $");
#include <sys/param.h>
#include <sys/systm.h>
@@ -85,6 +85,12 @@ rndpool_get_entropy_count(rndpool_t *rp)
return (rp->stats.curentropy);
}
+void
+rndpool_set_entropy_count(rndpool_t *rp, u_int32_t count)
+{
+ rp->stats.curentropy = count;
+}
+
void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
{
Index: src/sys/kern/kern_rndq.c
diff -u src/sys/kern/kern_rndq.c:1.23 src/sys/kern/kern_rndq.c:1.23.2.1
--- src/sys/kern/kern_rndq.c:1.23 Tue Mar 11 20:26:08 2014
+++ src/sys/kern/kern_rndq.c Mon Apr 7 02:00:00 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_rndq.c,v 1.23 2014/03/11 20:26:08 pooka Exp $ */
+/* $NetBSD: kern_rndq.c,v 1.23.2.1 2014/04/07 02:00:00 tls Exp $ */
/*-
* Copyright (c) 1997-2013 The NetBSD Foundation, Inc.
@@ -32,7 +32,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,v 1.23 2014/03/11 20:26:08 pooka Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,v 1.23.2.1 2014/04/07 02:00:00 tls Exp $");
#include <sys/param.h>
#include <sys/ioctl.h>
@@ -63,7 +63,7 @@ __KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,
#endif
#ifdef RND_DEBUG
-#define DPRINTF(l,x) if (rnd_debug & (l)) printf x
+#define DPRINTF(l,x) if (rnd_debug & (l)) rnd_printf x
int rnd_debug = 0;
#else
#define DPRINTF(l,x)
@@ -81,6 +81,10 @@ int rnd_debug = 0;
#define RND_VERBOSE
#endif
+#ifdef RND_VERBOSE
+static unsigned int deltacnt;
+#endif
+
/*
* This is a little bit of state information attached to each device that we
* collect entropy from. This is simply a collection buffer, and when it
@@ -93,7 +97,7 @@ typedef struct _rnd_sample_t {
krndsource_t *source;
int cursor;
int entropy;
- u_int32_t ts[RND_SAMPLE_COUNT];
+ uint64_t ts[RND_SAMPLE_COUNT];
u_int32_t values[RND_SAMPLE_COUNT];
} rnd_sample_t;
@@ -129,31 +133,45 @@ static krndsource_t rnd_source_no_collec
/* LIST_ENTRY list */
.name = { 'N', 'o', 'C', 'o', 'l', 'l', 'e', 'c', 't',
0, 0, 0, 0, 0, 0, 0 },
- .last_time = 0, .last_delta = 0, .last_delta2 = 0, .total = 0,
+ .total = 0,
.type = RND_TYPE_UNKNOWN,
.flags = (RND_FLAG_NO_COLLECT |
- RND_FLAG_NO_ESTIMATE |
- RND_TYPE_UNKNOWN),
+ RND_FLAG_NO_ESTIMATE),
+ .state = NULL,
+ .test_cnt = 0,
+ .test = NULL
+};
+
+static krndsource_t rnd_source_anonymous = {
+ /* LIST_ENTRY list */
+ .name = { 'A', 'n', 'o', 'n', 'y', 'm', 'o', 'u', 's',
+ 0, 0, 0, 0, 0, 0, 0 },
+ .total = 0,
+ .type = RND_TYPE_UNKNOWN,
+ .flags = (RND_FLAG_COLLECT_TIME|
+ RND_FLAG_COLLECT_VALUE|
+ RND_FLAG_ESTIMATE_TIME),
.state = NULL,
.test_cnt = 0,
.test = NULL
};
+
void *rnd_process, *rnd_wakeup;
struct callout skew_callout;
-void rnd_wakeup_readers(void);
-static inline u_int32_t rnd_estimate_entropy(krndsource_t *, u_int32_t);
-static inline u_int32_t rnd_counter(void);
+void rnd_wakeup_readers(void);
+static inline uint64_t rnd_counter(void);
static void rnd_intr(void *);
static void rnd_wake(void *);
static void rnd_process_events(void);
u_int32_t rnd_extract_data_locked(void *, u_int32_t, u_int32_t); /* XXX */
static void rnd_add_data_ts(krndsource_t *, const void *const,
- uint32_t, uint32_t, uint32_t);
+ uint32_t, uint32_t, uint64_t);
static inline void rnd_schedule_process(void);
int rnd_ready = 0;
int rnd_initial_entropy = 0;
+int rnd_printing = 0;
#ifdef DIAGNOSTIC
static int rnd_tested = 0;
@@ -165,6 +183,23 @@ LIST_HEAD(, krndsource) rnd_sources;
rndsave_t *boot_rsp;
+static inline void
+rnd_printf(const char *fmt, ...)
+{
+ va_list ap;
+
+ membar_consumer();
+ if (rnd_printing) {
+ return;
+ }
+ rnd_printing = 1;
+ membar_producer();
+ va_start(ap, fmt);
+ vprintf(fmt, ap);
+ va_end(ap);
+ rnd_printing = 0;
+}
+
void
rnd_init_softint(void) {
rnd_process = softint_establish(SOFTINT_SERIAL|SOFTINT_MPSAFE,
@@ -175,21 +210,25 @@ rnd_init_softint(void) {
}
/*
- * Generate a 32-bit counter. This should be more machine dependent,
- * using cycle counters and the like when possible.
+ * Generate a 64-bit counter.
*/
-static inline u_int32_t
+static inline uint64_t
rnd_counter(void)
{
- struct timeval tv;
+ struct timespec ts;
+ uint64_t ret;
#if defined(__HAVE_CPU_COUNTER)
- if (cpu_hascounter())
- return (cpu_counter32());
+ if (cpu_hascounter() && sizeof(cpu_counter() == sizeof(uint64_t))) {
+ return (cpu_counter());
+ }
#endif
if (rnd_ready) {
- microtime(&tv);
- return (tv.tv_sec * 1000000 + tv.tv_usec);
+ nanouptime(&ts);
+ ret = ts.tv_sec;
+ ret *= (uint64_t)1000000000;
+ ret += ts.tv_nsec;
+ return ret;
}
/* when called from rnd_init, its too early to call microtime safely */
return (0);
@@ -243,7 +282,7 @@ rnd_getmore(size_t byteswanted)
KASSERT(rs->getarg != NULL);
rs->get(byteswanted, rs->getarg);
#ifdef RND_VERBOSE
- printf("rnd: asking source %s for %zu bytes\n",
+ rnd_printf("rnd: asking source %s for %zu bytes\n",
rs->name, byteswanted);
#endif
}
@@ -271,7 +310,7 @@ rnd_wakeup_readers(void)
} else {
#ifdef RND_VERBOSE
if (__predict_false(!rnd_initial_entropy))
- printf("rnd: have initial entropy (%zu)\n",
+ rnd_printf("rnd: have initial entropy (%zu)\n",
entropy_count);
#endif
rnd_empty = 0;
@@ -282,42 +321,85 @@ rnd_wakeup_readers(void)
rndsinks_distribute();
}
+static uint32_t
+rnd_lz_estimate(krndsource_t *rs, rnd_lz_t *const est,
+ const void *const data, uint32_t len)
+{
+ const uint8_t *const cdata = data;
+ size_t c = 0, wherein = 0, cursor = est->cursor;
+ size_t isz = sizeof(est->in), osz = sizeof(est->out);
+ LZF_STATE *state = &est->state;
+ uint8_t *in = est->in, *out = est->out;
+ uint32_t total = 0;
+
+ KASSERT(rs != NULL);
+ KASSERT(cursor < isz);
+ KASSERT(cursor < osz);
+
+ /* We don't loop, so the maximum estimate we will
+ ever return is one internal-buffer-size worth of bits. */
+
+ if (cursor + len - wherein >= isz) {
+ c = lzf_compress_r(in, cursor, out,
+ cursor, *state);
+ memset(out, 0, osz);
+ memset(in, 0, isz);
+ if (c == 0) {
+ c = cursor;
+ }
+ total += c;
+ wherein += cursor;
+ cursor = 0;
+ } else {
+ memcpy(in + cursor, cdata + wherein, len - wherein);
+ cursor += len - wherein;
+ wherein += len - wherein;
+ }
+
+ total *= NBBY;
+
+ /*
+ * Compressing a stream of zeroes gives us 144 output
+ * bits per input kilobyte -- pure overhead, not entropy.
+ */
+ total = total > 144 ? total - 144 : 0;
+
+ /* LZF is not a very good LZ compressor! */
+ total /= 2;
+
+ est->cursor = cursor;
+ est->inbytes += len;
+ est->outbits += total;
+
+ return est->outbits > rs->total ? est->outbits - rs->total : 0;
+}
+
/*
- * Use the timing of the event to estimate the entropy gathered.
+ * Use the timing/value of the event to estimate the entropy gathered.
* If all the differentials (first, second, and third) are non-zero, return
* non-zero. If any of these are zero, return zero.
*/
-static inline u_int32_t
-rnd_estimate_entropy(krndsource_t *rs, u_int32_t t)
+static inline uint32_t
+rnd_delta_estimate(rnd_delta_t *d, uint64_t v, int64_t delta)
{
- int32_t delta, delta2, delta3;
+ int64_t delta2, delta3;
- /*
- * If the time counter has overflowed, calculate the real difference.
- * If it has not, it is simplier.
- */
- if (t < rs->last_time)
- delta = UINT_MAX - rs->last_time + t;
- else
- delta = rs->last_time - t;
-
- if (delta < 0)
- delta = -delta;
+ d->insamples++;
/*
* Calculate the second and third order differentials
*/
- delta2 = rs->last_delta - delta;
+ delta2 = d->dx - delta;
if (delta2 < 0)
delta2 = -delta2;
- delta3 = rs->last_delta2 - delta2;
+ delta3 = d->d2x - delta2;
if (delta3 < 0)
delta3 = -delta3;
- rs->last_time = t;
- rs->last_delta = delta;
- rs->last_delta2 = delta2;
+ d->x = v;
+ d->dx = delta;
+ d->d2x = delta2;
/*
* If any delta is 0, we got no entropy. If all are non-zero, we
@@ -326,10 +408,77 @@ rnd_estimate_entropy(krndsource_t *rs, u
if (delta == 0 || delta2 == 0 || delta3 == 0)
return (0);
+ d->outbits++;
return (1);
}
-#if defined(__HAVE_CPU_COUNTER)
+/*
+ * Delta estimator for 64-bit timeestamps. Must handle wrap.
+ */
+static inline uint32_t
+rnd_dt_estimate(krndsource_t *rs, uint32_t t)
+{
+ int64_t delta;
+ uint64_t ret;
+ rnd_delta_t *d = &rs->time_delta;
+
+ if (t < d->x) {
+ delta = UINT64_MAX - d->x + t;
+ } else {
+ delta = d->x - t;
+ }
+
+ if (delta < 0) {
+ delta = -delta;
+ }
+
+ ret = rnd_delta_estimate(d, t, delta);
+
+ KASSERT(d->x == t);
+ KASSERT(d->dx == delta);
+#ifdef RND_VERBOSE
+ if (deltacnt++ % 1151 == 0) {
+ rnd_printf("rnd_dt_estimate: %s x = %lld, dx = %lld, "
+ "d2x = %lld\n", rs->name,
+ (long long int)d->x,
+ (long long int)d->dx,
+ (long long int)d->d2x);
+ }
+#endif
+ return ret;
+}
+
+/*
+ * Delta estimator for 32 or 64 bit values. "Wrap" isn't.
+ */
+static inline uint32_t
+rnd_dv_estimate(krndsource_t *rs, uint64_t v)
+{
+ int64_t delta;
+ uint32_t ret;
+ rnd_delta_t *d = &rs->value_delta;
+
+ delta = d->x - v;
+
+ if (delta < 0) {
+ delta = -delta;
+ }
+ ret = rnd_delta_estimate(d, v, (uint64_t)delta);
+
+ KASSERT(d->x == v);
+ KASSERT(d->dx == delta);
+#ifdef RND_VERBOSE
+ if (deltacnt++ % 1151 == 0) {
+ rnd_printf("rnd_dv_estimate: %s x = %lld, dx = %lld, "
+ " d2x = %lld\n", rs->name,
+ (long long int)d->x,
+ (long long int)d->dx,
+ (long long int)d->d2x);
+ }
+#endif
+ return ret;
+}
+
static void
rnd_skew(void *arg)
{
@@ -344,27 +493,28 @@ rnd_skew(void *arg)
/*
* Even on systems with seemingly stable clocks, the
- * entropy estimator seems to think we get 1 bit here
- * about every 2 calls. That seems like too much. Set
- * NO_ESTIMATE on this source until we can better analyze
- * the entropy of its output.
+ * delta-time entropy estimator seems to think we get 1 bit here
+ * about every 2 calls. That seems like too much. Instead,
+ * we feed the rnd_counter() value to the value estimator as well,
+ * to take advantage of the additional LZ test on estimated values.
+ *
*/
if (__predict_false(!live)) {
rnd_attach_source(&skewsrc, "callout", RND_TYPE_SKEW,
- RND_FLAG_NO_ESTIMATE);
+ RND_FLAG_COLLECT_VALUE|
+ RND_FLAG_ESTIMATE_VALUE);
live = 1;
}
flipflop = !flipflop;
if (flipflop) {
- rnd_add_uint32(&skewsrc, rnd_counter());
- callout_schedule(&skew_callout, hz);
+ rnd_add_uint64(&skewsrc, rnd_counter());
+ callout_schedule(&skew_callout, hz / 10);
} else {
callout_schedule(&skew_callout, 1);
}
}
-#endif
/*
* initialize the global random pool for our use.
@@ -374,7 +524,7 @@ rnd_skew(void *arg)
void
rnd_init(void)
{
- u_int32_t c;
+ uint64_t c;
if (rnd_ready)
return;
@@ -421,16 +571,11 @@ rnd_init(void)
mutex_spin_exit(&rndpool_mtx);
}
- rnd_ready = 1;
-
/*
* If we have a cycle counter, take its error with respect
* to the callout mechanism as a source of entropy, ala
* TrueRand.
*
- * XXX This will do little when the cycle counter *is* what's
- * XXX clocking the callout mechanism. How to get this right
- * XXX without unsightly spelunking in the timecounter code?
*/
#if defined(__HAVE_CPU_COUNTER)
callout_init(&skew_callout, CALLOUT_MPSAFE);
@@ -439,7 +584,7 @@ rnd_init(void)
#endif
#ifdef RND_VERBOSE
- printf("rnd: initialised (%u)%s", RND_POOLBITS,
+ rnd_printf("rnd: initialised (%u)%s", RND_POOLBITS,
c ? " with counter\n" : "\n");
#endif
if (boot_rsp != NULL) {
@@ -454,11 +599,16 @@ rnd_init(void)
}
mutex_spin_exit(&rndpool_mtx);
#ifdef RND_VERBOSE
- printf("rnd: seeded with %d bits\n",
+ rnd_printf("rnd: seeded with %d bits\n",
MIN(boot_rsp->entropy, RND_POOLBITS / 2));
#endif
memset(boot_rsp, 0, sizeof(*boot_rsp));
}
+ rnd_attach_source(&rnd_source_anonymous, "Anonymous",
+ RND_TYPE_UNKNOWN,
+ RND_FLAG_COLLECT_TIME|RND_FLAG_COLLECT_VALUE|
+ RND_FLAG_ESTIMATE_TIME);
+ rnd_ready = 1;
}
static rnd_sample_t *
@@ -507,17 +657,18 @@ rnd_sample_free(rnd_sample_t *c)
* Add a source to our list of sources.
*/
void
-rnd_attach_source(krndsource_t *rs, const char *name, u_int32_t type,
- u_int32_t flags)
+rnd_attach_source(krndsource_t *rs, const char *name, uint32_t type,
+ uint32_t flags)
{
- u_int32_t ts;
+ uint64_t ts;
ts = rnd_counter();
strlcpy(rs->name, name, sizeof(rs->name));
- rs->last_time = ts;
- rs->last_delta = 0;
- rs->last_delta2 = 0;
+ memset(&rs->time_delta, 0, sizeof(rs->time_delta));
+ rs->time_delta.x = ts;
+ memset(&rs->value_delta, 0, sizeof(rs->value_delta));
+ memset(&rs->lz_v, 0, sizeof(rs->lz_v));
rs->total = 0;
/*
@@ -526,6 +677,10 @@ rnd_attach_source(krndsource_t *rs, cons
rs->test = NULL;
rs->test_cnt = -1;
+ if (flags == 0) {
+ flags = RND_FLAG_DEFAULT;
+ }
+
switch (type) {
case RND_TYPE_NET: /* Don't collect by default */
flags |= (RND_FLAG_NO_COLLECT | RND_FLAG_NO_ESTIMATE);
@@ -550,22 +705,24 @@ rnd_attach_source(krndsource_t *rs, cons
LIST_INSERT_HEAD(&rnd_sources, rs, list);
#ifdef RND_VERBOSE
- printf("rnd: %s attached as an entropy source (", rs->name);
+ rnd_printf("rnd: %s attached as an entropy source (", rs->name);
if (!(flags & RND_FLAG_NO_COLLECT)) {
- printf("collecting");
+ rnd_printf("collecting");
if (flags & RND_FLAG_NO_ESTIMATE)
- printf(" without estimation");
+ rnd_printf(" without estimation");
}
else
- printf("off");
- printf(")\n");
+ rnd_printf("off");
+ rnd_printf(")\n");
#endif
/*
* Again, put some more initial junk in the pool.
- * XXX Bogus, but harder to guess than zeros.
+ * FreeBSD claim to have an analysis that show 4 bits of
+ * entropy per source-attach timestamp. I am skeptical,
+ * but we count 1 bit per source here.
*/
- rndpool_add_data(&rnd_pool, &ts, sizeof(u_int32_t), 1);
+ rndpool_add_data(&rnd_pool, &ts, sizeof(ts), 1);
mutex_spin_exit(&rndpool_mtx);
}
@@ -607,19 +764,41 @@ rnd_detach_source(krndsource_t *source)
}
#ifdef RND_VERBOSE
- printf("rnd: %s detached as an entropy source\n", source->name);
+ rnd_printf("rnd: %s detached as an entropy source\n", source->name);
#endif
}
+static inline uint32_t
+rnd_estimate(krndsource_t *rs, uint64_t ts, uint64_t val)
+{
+ uint32_t entropy = 0, dt_est, dv_est, lz_est;
+
+ dt_est = rnd_dt_estimate(rs, ts);
+ dv_est = rnd_dv_estimate(rs, val);
+ lz_est = rnd_lz_estimate(rs, &rs->lz_v, &val, sizeof(val));
+
+ if (!(rs->flags & RND_FLAG_NO_ESTIMATE)) {
+ if (rs->flags & RND_FLAG_ESTIMATE_TIME) {
+ entropy += dt_est;
+ }
+
+ if (rs->flags & RND_FLAG_ESTIMATE_VALUE) {
+ entropy += MIN(lz_est, dv_est);
+ }
+
+ }
+ return entropy;
+}
+
/*
* Add a 32-bit value to the entropy pool. The rs parameter should point to
* the source-specific source structure.
*/
void
-_rnd_add_uint32(krndsource_t *rs, u_int32_t val)
+_rnd_add_uint32(krndsource_t *rs, uint32_t val)
{
- u_int32_t ts;
- u_int32_t entropy = 0;
+ uint64_t ts;
+ uint32_t entropy = 0;
if (rs->flags & RND_FLAG_NO_COLLECT)
return;
@@ -631,13 +810,34 @@ _rnd_add_uint32(krndsource_t *rs, u_int3
ts = rnd_counter();
/*
- * If we are estimating entropy on this source,
- * calculate differentials.
+ * Calculate estimates - we may not use them, but if we do
+ * not calculate them, the estimators' history becomes invalid.
*/
+ entropy = rnd_estimate(rs, ts, (uint64_t)val);
- if ((rs->flags & RND_FLAG_NO_ESTIMATE) == 0) {
- entropy = rnd_estimate_entropy(rs, ts);
- }
+ rnd_add_data_ts(rs, &val, sizeof(val), entropy, ts);
+}
+
+void
+_rnd_add_uint64(krndsource_t *rs, uint64_t val)
+{
+ uint64_t ts;
+ uint32_t entropy = 0;
+
+ if (rs->flags & RND_FLAG_NO_COLLECT)
+ return;
+
+ /*
+ * Sample the counter as soon as possible to avoid
+ * entropy overestimation.
+ */
+ ts = rnd_counter();
+
+ /*
+ * Calculate estimates - we may not use them, but if we do
+ * not calculate them, the estimators' history becomes invalid.
+ */
+ entropy = rnd_estimate(rs, ts, val);
rnd_add_data_ts(rs, &val, sizeof(val), entropy, ts);
}
@@ -651,18 +851,18 @@ rnd_add_data(krndsource_t *rs, const voi
* itself, random. Don't estimate entropy based on
* timestamp, just directly add the data.
*/
+ mutex_spin_enter(&rndpool_mtx);
if (__predict_false(rs == NULL)) {
- mutex_spin_enter(&rndpool_mtx);
- rndpool_add_data(&rnd_pool, data, len, entropy);
- mutex_spin_exit(&rndpool_mtx);
- } else {
- rnd_add_data_ts(rs, data, len, entropy, rnd_counter());
+ rs = &rnd_source_anonymous;
}
+ entropy = MIN(entropy, rnd_lz_estimate(rs, &rs->lz_v, data, len));
+ rndpool_add_data(&rnd_pool, data, len, entropy);
+ mutex_spin_exit(&rndpool_mtx);
}
static void
rnd_add_data_ts(krndsource_t *rs, const void *const data, u_int32_t len,
- u_int32_t entropy, uint32_t ts)
+ u_int32_t entropy, uint64_t ts)
{
rnd_sample_t *state = NULL;
const uint32_t *dint = data;
@@ -671,10 +871,12 @@ rnd_add_data_ts(krndsource_t *rs, const
SIMPLEQ_HEAD(, _rnd_sample_t) tmp_samples =
SIMPLEQ_HEAD_INITIALIZER(tmp_samples);
- if (rs->flags & RND_FLAG_NO_COLLECT) {
+ if (rs && (rs->flags & RND_FLAG_NO_COLLECT ||
+ __predict_false(!(rs->flags &
+ (RND_FLAG_COLLECT_TIME|
+ RND_FLAG_COLLECT_VALUE))))) {
return;
}
-
todo = len / sizeof(*dint);
/*
* Let's try to be efficient: if we are warm, and a source
@@ -689,12 +891,12 @@ rnd_add_data_ts(krndsource_t *rs, const
getmicrouptime(&upt);
if ((todo >= RND_SAMPLE_COUNT) ||
- (rs->total > upt.tv_sec * 10) ||
+ (upt.tv_sec > 0 && rs->total > upt.tv_sec * 10) ||
(upt.tv_sec > 10 && rs->total > upt.tv_sec) ||
(upt.tv_sec > 100 &&
rs->total > upt.tv_sec / 10)) {
#ifdef RND_VERBOSE
- printf("rnd: source %s is fast (%d samples "
+ rnd_printf("rnd: source %s is fast (%d samples "
"at once, %d bits in %lld seconds), "
"processing samples in bulk.\n",
rs->name, todo, rs->total,
@@ -790,7 +992,7 @@ rnd_hwrng_test(rnd_sample_t *sample)
v2 = (uint8_t *)sample->values + cmplen;
if (__predict_false(!memcmp(v1, v2, cmplen))) {
- printf("rnd: source \"%s\" failed continuous-output test.\n",
+ rnd_printf("rnd: source \"%s\" failed continuous-output test.\n",
source->name);
return 1;
}
@@ -811,7 +1013,7 @@ rnd_hwrng_test(rnd_sample_t *sample)
strlcpy(source->test->rt_name, source->name,
sizeof(source->test->rt_name));
if (rngtest(source->test)) {
- printf("rnd: source \"%s\" failed statistical test.",
+ rnd_printf("rnd: source \"%s\" failed statistical test.",
source->name);
return 1;
}
@@ -855,8 +1057,9 @@ rnd_process_events(void)
* the source was disabled before we were called, but
* after the entry was queued.
*/
- if (__predict_false(sample->source->flags
- & RND_FLAG_NO_COLLECT)) {
+ if (__predict_false(!(sample->source->flags &
+ (RND_FLAG_COLLECT_TIME|
+ RND_FLAG_COLLECT_VALUE)))) {
SIMPLEQ_INSERT_TAIL(&df_samples, sample, next);
} else {
SIMPLEQ_INSERT_TAIL(&dq_samples, sample, next);
@@ -868,21 +1071,14 @@ rnd_process_events(void)
mutex_spin_enter(&rndpool_mtx);
pool_entropy = rndpool_get_entropy_count(&rnd_pool);
- if (pool_entropy > RND_ENTROPY_THRESHOLD * NBBY) {
- wake++;
- } else {
- rnd_empty = 1;
- rnd_getmore(howmany((RND_POOLBITS - pool_entropy), NBBY));
-#ifdef RND_VERBOSE
- printf("rnd: empty, asking for %zu bytes\n",
- howmany((RND_POOLBITS - pool_entropy), NBBY));
-#endif
- }
while ((sample = SIMPLEQ_FIRST(&dq_samples))) {
+ int sample_count;
+
SIMPLEQ_REMOVE_HEAD(&dq_samples, next);
source = sample->source;
entropy = sample->entropy;
+ sample_count = sample->cursor + 1;
/*
* Don't provide a side channel for timing attacks on
@@ -906,20 +1102,40 @@ rnd_process_events(void)
* Detach the bad source. See below.
*/
badsource = source;
- printf("rnd: detaching source \"%s\".",
+ rnd_printf("rnd: detaching source \"%s\".",
badsource->name);
break;
}
}
- rndpool_add_data(&rnd_pool, sample->values,
- RND_SAMPLE_COUNT * 4, 0);
- rndpool_add_data(&rnd_pool, sample->ts,
- RND_SAMPLE_COUNT * 4, entropy);
+ if (source->flags & RND_FLAG_COLLECT_VALUE) {
+ rndpool_add_data(&rnd_pool, sample->values,
+ sample_count *
+ sizeof(sample->values[1]),
+ 0);
+ }
+ if (source->flags & RND_FLAG_COLLECT_TIME) {
+ rndpool_add_data(&rnd_pool, sample->ts,
+ sample_count *
+ sizeof(sample->ts[1]),
+ 0);
+ }
+ pool_entropy += entropy;
source->total += sample->entropy;
SIMPLEQ_INSERT_TAIL(&df_samples, sample, next);
}
+ rndpool_set_entropy_count(&rnd_pool, pool_entropy);
+ if (pool_entropy > RND_ENTROPY_THRESHOLD * 8) {
+ wake++;
+ } else {
+ rnd_empty = 1;
+ rnd_getmore((RND_POOLBITS - pool_entropy) / 8);
+#ifdef RND_VERBOSE
+ rnd_printf("rnd: empty, asking for %d bits\n",
+ (int)((RND_POOLBITS - pool_entropy) / 8));
+#endif
+ }
mutex_spin_exit(&rndpool_mtx);
/* Now we hold no locks: clean up. */
@@ -941,7 +1157,6 @@ rnd_process_events(void)
rnd_sample_free(sample);
}
-
/*
* Wake up any potential readers waiting.
*/
@@ -977,22 +1192,22 @@ rnd_extract_data_locked(void *p, u_int32
timed_in++;
}
if (__predict_false(!rnd_initial_entropy)) {
- u_int32_t c;
+ uint64_t c;
#ifdef RND_VERBOSE
- printf("rnd: WARNING! initial entropy low (%u).\n",
+ rnd_printf("rnd: WARNING! initial entropy low (%u).\n",
rndpool_get_entropy_count(&rnd_pool));
#endif
/* Try once again to put something in the pool */
c = rnd_counter();
- rndpool_add_data(&rnd_pool, &c, sizeof(u_int32_t), 1);
+ rndpool_add_data(&rnd_pool, &c, sizeof(c), 1);
}
#ifdef DIAGNOSTIC
while (!rnd_tested) {
entropy_count = rndpool_get_entropy_count(&rnd_pool);
#ifdef RND_VERBOSE
- printf("rnd: starting statistical RNG test, entropy = %d.\n",
+ rnd_printf("rnd: starting statistical RNG test, entropy = %d.\n",
entropy_count);
#endif
if (rndpool_extract_data(&rnd_pool, rnd_rt.rt_b,
@@ -1016,7 +1231,7 @@ rnd_extract_data_locked(void *p, u_int32
* The relevant standard says to reset the module,
* but developers objected...
*/
- printf("rnd: WARNING, ENTROPY POOL FAILED "
+ rnd_printf("rnd: WARNING, ENTROPY POOL FAILED "
"STATISTICAL TEST!\n");
continue;
}
@@ -1025,7 +1240,7 @@ rnd_extract_data_locked(void *p, u_int32
entropy_count);
memset(rnd_testbits, 0, sizeof(rnd_testbits));
#ifdef RND_VERBOSE
- printf("rnd: statistical RNG test done, entropy = %d.\n",
+ rnd_printf("rnd: statistical RNG test done, entropy = %d.\n",
rndpool_get_entropy_count(&rnd_pool));
#endif
rnd_tested++;
@@ -1056,7 +1271,7 @@ rnd_seed(void *base, size_t len)
uint8_t digest[SHA1_DIGEST_LENGTH];
if (len != sizeof(*boot_rsp)) {
- aprint_error("rnd: bad seed length %d\n", (int)len);
+ rnd_printf("rnd: bad seed length %d\n", (int)len);
return;
}
@@ -1068,7 +1283,7 @@ rnd_seed(void *base, size_t len)
SHA1Final(digest, &s);
if (memcmp(digest, boot_rsp->digest, sizeof(digest))) {
- aprint_error("rnd: bad seed checksum\n");
+ rnd_printf("rnd: bad seed checksum\n");
return;
}
@@ -1078,7 +1293,7 @@ rnd_seed(void *base, size_t len)
*/
if (rnd_ready) {
#ifdef RND_VERBOSE
- printf("rnd: ready, feeding in seed data directly.\n");
+ rnd_printf("rnd: ready, feeding in seed data directly.\n");
#endif
mutex_spin_enter(&rndpool_mtx);
rndpool_add_data(&rnd_pool, boot_rsp->data,
@@ -1088,7 +1303,7 @@ rnd_seed(void *base, size_t len)
mutex_spin_exit(&rndpool_mtx);
} else {
#ifdef RND_VERBOSE
- printf("rnd: not ready, deferring seed feed.\n");
+ rnd_printf("rnd: not ready, deferring seed feed.\n");
#endif
}
}
Index: src/sys/sys/rnd.h
diff -u src/sys/sys/rnd.h:1.40 src/sys/sys/rnd.h:1.40.2.1
--- src/sys/sys/rnd.h:1.40 Thu Aug 29 01:04:49 2013
+++ src/sys/sys/rnd.h Mon Apr 7 02:00:00 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: rnd.h,v 1.40 2013/08/29 01:04:49 tls Exp $ */
+/* $NetBSD: rnd.h,v 1.40.2.1 2014/04/07 02:00:00 tls Exp $ */
/*-
* Copyright (c) 1997 The NetBSD Foundation, Inc.
@@ -42,6 +42,7 @@
#ifdef _KERNEL
#include <sys/queue.h>
+#include <sys/systm.h>
#endif
#ifdef _KERNEL
@@ -85,13 +86,29 @@ typedef struct {
uint32_t flags; /* flags */
} rndsource_t;
+typedef struct {
+ rndsource_t rt;
+ uint32_t dt_samples; /* time-delta samples input */
+ uint32_t dt_total; /* time-delta entropy estimate */
+ uint32_t dv_samples; /* value-delta samples input */
+ uint32_t dv_total; /* value-delta entropy estimate */
+ uint32_t lzv_bytes; /* LZF bytes in */
+ uint32_t lzv_total; /* LZF entropy estimate (bits) */
+} rndsource_est_t;
+
/*
* Flags to control the source. Low byte is type, upper bits are flags.
*/
-#define RND_FLAG_NO_ESTIMATE 0x00000100 /* don't estimate entropy */
-#define RND_FLAG_NO_COLLECT 0x00000200 /* don't collect entropy */
+#define RND_FLAG_NO_ESTIMATE 0x00000100
+#define RND_FLAG_NO_COLLECT 0x00000200
#define RND_FLAG_FAST 0x00000400 /* process samples in bulk */
#define RND_FLAG_HASCB 0x00000800 /* has get callback */
+#define RND_FLAG_COLLECT_TIME 0x00001000 /* use timestamp as input */
+#define RND_FLAG_COLLECT_VALUE 0x00002000 /* use value as input */
+#define RND_FLAG_ESTIMATE_TIME 0x00004000 /* estimate entropy on time */
+#define RND_FLAG_ESTIMATE_VALUE 0x00008000 /* estimate entropy on value */
+#define RND_FLAG_DEFAULT (RND_FLAG_COLLECT_VALUE|RND_FLAG_COLLECT_TIME|\
+ RND_FLAG_ESTIMATE_TIME)
#define RND_TYPE_UNKNOWN 0 /* unknown source */
#define RND_TYPE_DISK 1 /* source is physical disk */
@@ -115,20 +132,37 @@ typedef struct {
#endif
#define RND_POOLBITS (RND_POOLWORDS * 32)
+typedef struct rnd_lz_estimator {
+ LZF_STATE state;
+ size_t cursor;
+ uint8_t in[1024];
+ uint8_t out[1024];
+ uint64_t inbytes;
+ uint64_t outbits;
+} rnd_lz_t;
+
+typedef struct rnd_delta_estimator {
+ uint64_t x;
+ uint64_t dx;
+ uint64_t d2x;
+ uint64_t insamples;
+ uint64_t outbits;
+} rnd_delta_t;
+
typedef struct krndsource {
LIST_ENTRY(krndsource) list; /* the linked list */
char name[16]; /* device name */
- uint32_t last_time; /* last time recorded */
- uint32_t last_delta; /* last delta value */
- uint32_t last_delta2; /* last delta2 value */
+ rnd_delta_t time_delta; /* time delta estimator */
+ rnd_delta_t value_delta; /* value delta estimator */
uint32_t total; /* entropy from this source */
uint32_t type; /* type */
uint32_t flags; /* flags */
void *state; /* state information */
size_t test_cnt; /* how much test data accumulated? */
- rngtest_t *test; /* test data for RNG type sources */
void (*get)(size_t, void *); /* pool wants N bytes (badly) */
void *getarg; /* argument to get-function */
+ rnd_lz_t lz_v; /* LZF context as entropy estimator */
+ rngtest_t *test; /* test data for RNG type sources */
} krndsource_t;
static inline void
@@ -151,6 +185,7 @@ typedef struct {
void rndpool_init(rndpool_t *);
void rndpool_init_global(void);
uint32_t rndpool_get_entropy_count(rndpool_t *);
+void rndpool_set_entropy_count(rndpool_t *, uint32_t);
void rndpool_get_stats(rndpool_t *, void *, int);
void rndpool_increment_entropy_count(rndpool_t *, uint32_t);
uint32_t *rndpool_get_pool(rndpool_t *);
@@ -161,6 +196,7 @@ uint32_t rndpool_extract_data(rndpool_t
void rnd_init(void);
void rnd_init_softint(void);
void _rnd_add_uint32(krndsource_t *, uint32_t);
+void _rnd_add_uint64(krndsource_t *, uint64_t);
void rnd_add_data(krndsource_t *, const void *const, uint32_t,
uint32_t);
void rnd_attach_source(krndsource_t *, const char *,
@@ -174,8 +210,22 @@ void rnd_seed(void *, size_t);
static inline void
rnd_add_uint32(krndsource_t *kr, uint32_t val)
{
- if (__predict_true(kr) && RND_ENABLED(kr)) {
- _rnd_add_uint32(kr, val);
+ if (__predict_true(kr)) {
+ if (RND_ENABLED(kr)) {
+ _rnd_add_uint32(kr, val);
+ }
+ } else {
+ rnd_add_data(NULL, &val, sizeof(val), 0);
+ }
+}
+
+static inline void
+rnd_add_uint64(krndsource_t *kr, uint64_t val)
+{
+ if (__predict_true(kr)) {
+ if (RND_ENABLED(kr)) {
+ _rnd_add_uint64(kr, val);
+ }
} else {
rnd_add_data(NULL, &val, sizeof(val), 0);
}
@@ -186,6 +236,9 @@ extern int rnd_full;
extern int rnd_filled;
extern int rnd_initial_entropy;
+extern int rnd_ready;
+extern int rnd_printing; /* XXX recursion through printf */
+
#endif /* _KERNEL */
#define RND_MAXSTATCOUNT 10 /* 10 sources at once max */
@@ -200,6 +253,16 @@ typedef struct {
} rndstat_t;
/*
+ * return "count" random entries with estimates, starting at "start"
+ */
+typedef struct {
+ uint32_t start;
+ uint32_t count;
+ rndsource_est_t source[RND_MAXSTATCOUNT];
+} rndstat_est_t;
+
+
+/*
* return information on a specific source by name
*/
typedef struct {
@@ -207,6 +270,12 @@ typedef struct {
rndsource_t source;
} rndstat_name_t;
+typedef struct {
+ char name[16];
+ rndsource_est_t source;
+} rndstat_est_name_t;
+
+
/*
* set/clear device flags. If type is set to 0xff, the name is used
* instead. Otherwise, the flags set/cleared apply to all devices of
@@ -235,5 +304,7 @@ typedef struct {
#define RNDCTL _IOW('R', 104, rndctl_t) /* set/clear source flags */
#define RNDADDDATA _IOW('R', 105, rnddata_t) /* add data to the pool */
#define RNDGETPOOLSTAT _IOR('R', 106, rndpoolstat_t) /* get statistics */
+#define RNDGETESTNUM _IOWR('R', 107, rndstat_est_t) /* get srcest */
+#define RNDGETESTNAME _IOWR('R', 108, rndstat_est_name_t) /* " by name */
#endif /* !_SYS_RND_H_ */
