As may be obvious to some by now my original proof-of-concept patch was
not exactly complete or even near correct.
This is the actual patch I've been testing (though it's collected from
places in a cvs-examine emacs buffer so may be incomplete).
I've restored some of the code that does actual entropy estimation using
the value and time deltas as before -- I think I've got it correct and
it seems to work as before.
This patch is designed to restore the admin's the ability to choose
non-hardware-RNGs as sources of entropy bits.
After all, this is a "unix" system, and, to quote Eric Allman, "Unix
gives you just enough rope to hang yourself -- and then a couple of more
feet, just to be sure."
The intent of course is also to mostly leave all this rope coiled neatly
in the corner and not to change the default behaviour of the system. I
don't quite do that yet though -- I do leave RND_TYPE_{ENV,POWER,SKEW}
devices without NO_ESTIMATE by default. This is probably still a point
of contention, but I'll propose it as a requirement for older hardware.
Perhaps this choice could be an options(4) option and port maintainers
could choose to enable it in their GENERIC, etc. kernels or not. In the
end though lots of old hardware won't have environmental sensors or any
power events to use, and I'm not sure clock skew is actually a viable
source.
I've tested it on real hardware and with Xen dom0 and domU kernels.
I successfully use the following for Xen domUs that boot and run from
read-only ISOs:
rndctl=YES rndctl_flags="-t disk; -t vm"
I think in the case where your local network is not easily accessed by
adversaries you can also safely add "; -t net" to the above, assuming
your network interface driver has calls to rnd_attach_source() and
rnd_add_uint32().
This patch is against 2021-03-10 sources.
Index: kern/kern_clock.c
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/kern/kern_clock.c,v
retrieving revision 1.144
diff -u -r1.144 kern_clock.c
--- kern/kern_clock.c 16 Jan 2021 02:20:00 -0000 1.144
+++ kern/kern_clock.c 9 Apr 2021 18:16:52 -0000
@@ -173,7 +173,7 @@
if (ci != ci->ci_package1st)
return;
- /* Take a sample and enter it into the pool. */
+ /* Take a sample (timestamp only) and enter it into the pool. */
rnd_add_uint32(&C->source, 0);
/*
@@ -283,12 +283,12 @@
rndsource_setcb(&hardclockrnd.source, clockrnd_get, &hardclockrnd);
rnd_attach_source(&hardclockrnd.source, "hardclock", RND_TYPE_SKEW,
- RND_FLAG_COLLECT_TIME|RND_FLAG_HASCB);
+ RND_FLAG_COLLECT_TIME|RND_FLAG_ESTIMATE_TIME|RND_FLAG_HASCB);
if (stathz) {
rndsource_setcb(&statclockrnd.source, clockrnd_get,
&statclockrnd);
rnd_attach_source(&statclockrnd.source, "statclock",
- RND_TYPE_SKEW, RND_FLAG_COLLECT_TIME|RND_FLAG_HASCB);
+ RND_TYPE_SKEW, RND_FLAG_COLLECT_TIME|RND_FLAG_ESTIMATE_TIME|RND_FLAG_HASCB);
}
}
Index: kern/kern_entropy.c
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/kern/kern_entropy.c,v
retrieving revision 1.30
diff -u -r1.30 kern_entropy.c
--- kern/kern_entropy.c 12 Feb 2021 19:48:26 -0000 1.30
+++ kern/kern_entropy.c 9 Apr 2021 18:08:30 -0000
@@ -1308,6 +1308,8 @@
KASSERT(E->stage >= ENTROPY_WARM);
printf("entropy: pid %d (%s) blocking due to lack of entropy\n",
curproc->p_pid, curproc->p_comm);
+ uprintf("entropy: pid %d (%s) blocking due to lack of entropy\n",
+ curproc->p_pid, curproc->p_comm);
if (ISSET(flags, ENTROPY_SIG)) {
error = cv_wait_sig(&E->cv, &E->lock);
@@ -1512,6 +1514,7 @@
void *getarg)
{
+ /* XXX why the heck doesn't this set RND_FLAG_HACB itself???? */
rs->get = get;
rs->getarg = getarg;
}
@@ -1535,13 +1538,38 @@
/*
* Apply some standard flags:
*
- * - We do not bother with network devices by default, for
- * hysterical raisins (perhaps: because it is often the case
- * that an adversary can influence network packet timings).
+ * - We do not bother at all with network devices and VM events by
+ * default, for hysterical raisins (perhaps: because it is often the
+ * case that an adversary can influence or observe network packet
+ * timings or paging activity and thus possibly infer what entropy
+ * bits have been collected from these devices).
+ *
+ * - We also do not trust anything but environmental sensors, power
+ * events, clock skews, and of course hardware RNG devices for
+ * counting or supplying entropy bits by default, though they are
+ * allowed to contribute to the runtime entropy pool. We could
+ * probably trust tape, disk, and tty devices, but there is some
+ * controversy about these, perhaps because an adversary may also be
+ * able to observe, or perhaps even influence, their activity well
+ * enough to predict their entropy bits. (All told though the more
+ * devices, and device types, the less predictable the whole system's
+ * entropy pool will be as it gets more difficult to simultaneously
+ * influence and/or observe the whole collection of sources.)
*/
switch (type) {
+ case RND_TYPE_SKEW:
+ case RND_TYPE_ENV:
+ case RND_TYPE_POWER:
+ case RND_TYPE_RNG:
+ /* these devices are trusted to both collect and
+ * "estimate"(count) entropy by default */
+ break;
case RND_TYPE_NET:
+ case RND_TYPE_VM:
flags |= RND_FLAG_NO_COLLECT;
+ /* FALLTHRU */
+ default:
+ flags |= RND_FLAG_NO_ESTIMATE;
break;
}
@@ -1577,6 +1605,16 @@
KASSERT(i == __arraycount(extra));
entropy_enter(extra, sizeof extra, 0);
explicit_memset(extra, 0, sizeof extra);
+
+ aprint_verbose("entropy: %s attached as an entropy source (", rs->name);
+ if (!(flags & RND_FLAG_NO_COLLECT)) {
+ printf("collecting");
+ if (flags & RND_FLAG_NO_ESTIMATE)
+ printf(" without estimation");
+ } else {
+ printf("off");
+ }
+ printf(")\n");
}
/*
@@ -1610,6 +1648,8 @@
/* Free the per-CPU data. */
percpu_free(rs->state, sizeof(struct rndsource_cpu));
+
+ aprint_verbose("entropy: %s detached as an entropy source\n", rs->name);
}
/*
@@ -1741,35 +1781,176 @@
}
/*
+ * 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 uint32_t
+rnd_delta_estimate(rnd_delta_t *d, uint32_t v, uint32_t delta)
+{
+ uint32_t delta2, delta3;
+
+ d->insamples++;
+
+ /*
+ * Calculate the second and third order differentials
+ */
+ if (delta > (uint32_t)d->dx)
+ delta2 = delta - (uint32_t)d->dx;
+ else
+ delta2 = (uint32_t)d->dx - delta;
+
+ if (delta2 > (uint32_t)d->d2x)
+ delta3 = delta2 - (uint32_t)d->d2x;
+ else
+ delta3 = (uint32_t)d->d2x - 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
+ * might have something.
+ */
+ if (delta == 0 || delta2 == 0 || delta3 == 0)
+ return 0;
+
+ d->outbits++;
+
+ return 1;
+}
+
+/*
+ * Delta estimator for 32-bit timestamps.
+ * Timestaps generally increase, but may wrap around to 0.
+ * If t decreases, it is assumed that wrap-around occurred (once).
+ */
+static inline uint32_t
+rnd_dt_estimate(krndsource_t *rs, uint32_t t)
+{
+ uint32_t delta;
+ uint32_t ret;
+ rnd_delta_t *d = &rs->time_delta;
+
+ if (t < (uint32_t)d->x) {
+ delta = UINT32_MAX - (uint32_t)d->x + t;
+ } else {
+ delta = t - (uint32_t)d->x;
+ }
+
+ ret = rnd_delta_estimate(d, t, delta);
+
+ KASSERT(d->x == t);
+ KASSERT(d->dx == delta);
+
+ return ret;
+}
+
+/*
+ * Delta estimator for arbitrary unsigned 32 bit values.
+ */
+static inline uint32_t
+rnd_dv_estimate(krndsource_t *rs, uint32_t v)
+{
+ uint32_t delta;
+ uint32_t ret;
+ rnd_delta_t *d = &rs->value_delta;
+
+ if (v >= (uint32_t)d->x) {
+ delta = v - (uint32_t)d->x;
+ } else {
+ delta = (uint32_t)d->x - v;
+ }
+
+ ret = rnd_delta_estimate(d, v, delta);
+
+ KASSERT(d->x == v);
+ KASSERT(d->dx == delta);
+
+ return ret;
+}
+
+static inline uint32_t
+rnd_estimate_entropy(krndsource_t *rs, uint32_t ts, uint32_t val)
+{
+ uint32_t entropy = 0, dt_est, dv_est;
+
+ dt_est = rnd_dt_estimate(rs, ts);
+ dv_est = rnd_dv_estimate(rs, 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 += dv_est;
+ }
+ }
+
+ return entropy;
+}
+
+/*
* rnd_add_uint32(rs, value)
*
- * Enter 32 bits of data from an entropy source into the pool.
+ * Enter a 32 bits of data from an entropy source into the pool.
*
- * If rs is NULL, may not be called from interrupt context.
+ * The number of entropy bits for the value is determined by
+ * rnd_estimate_entropy() based on either the time delta and/or the value's
+ * delta from the last time or value data was added from the same source.
*
- * If rs is non-NULL, may be called from any context. May drop
- * data if called from interrupt context.
+ * If rs is NULL, this may not be called from an interrupt context.
+ *
+ * If rs is non-NULL, this may be called from any context. It may ignore
+ * the data if called from interrupt context.
*/
void
rnd_add_uint32(struct krndsource *rs, uint32_t value)
{
+ u_int32_t ts;
+ u_int32_t entropy = 0;
+
+ if (rs->flags & RND_FLAG_NO_COLLECT)
+ return;
- rnd_add_data(rs, &value, sizeof value, 0);
+ /*
+ * Sample the counter as soon as possible to avoid
+ * entropy overestimation.
+ */
+ ts = entropy_timer();
+
+ /*
+ * If we are estimating entropy on this source,
+ * calculate the possible bits of entropy.
+ */
+
+ if ((rs->flags & RND_FLAG_NO_ESTIMATE) == 0) {
+ entropy = rnd_estimate_entropy(rs, ts, value);
+ }
+
+ rnd_add_data(rs, &value, sizeof value, entropy);
}
+#if 0
+/* xxx Unused */
void
_rnd_add_uint32(struct krndsource *rs, uint32_t value)
{
- rnd_add_data(rs, &value, sizeof value, 0);
+ rnd_add_data(rs, &value, sizeof value, 1);
}
+/* xxx Unused */
void
_rnd_add_uint64(struct krndsource *rs, uint64_t value)
{
- rnd_add_data(rs, &value, sizeof value, 0);
+ rnd_add_data(rs, &value, sizeof value, 1);
}
+#endif
/*
* rnd_add_data(rs, buf, len, entropybits)
Index: kern/subr_autoconf.c
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/kern/subr_autoconf.c,v
retrieving revision 1.277
diff -u -r1.277 subr_autoconf.c
--- kern/subr_autoconf.c 27 Jan 2021 04:54:08 -0000 1.277
+++ kern/subr_autoconf.c 8 Apr 2021 21:38:59 -0000
@@ -358,7 +358,7 @@
TAILQ_INSERT_TAIL(&allcftables, &initcftable, ct_list);
rnd_attach_source(&rnd_autoconf_source, "autoconf", RND_TYPE_UNKNOWN,
- RND_FLAG_COLLECT_TIME);
+ RND_FLAG_COLLECT_TIME|RND_FLAG_ESTIMATE_TIME|RND_FLAG_NO_ESTIMATE);
config_initialized = true;
}
@@ -1429,7 +1429,8 @@
xunit = number(&num[sizeof(num)], myunit);
lunit = &num[sizeof(num)] - xunit;
if (lname + lunit > sizeof(dev->dv_xname))
- panic("config_devalloc: device name too long");
+ panic("config_devalloc: device name too long for %s",
+ cf->cf_atname);
dvl = device_getlock(dev);
@@ -1467,6 +1468,14 @@
if (dev->dv_cfdriver->cd_attrs != NULL)
config_add_attrib_dict(dev);
+#if 0
+ aprint_debug_dev(dev, "config_devalloc: setup completed for %s unit %d as %s (dev = %p)\n",
+ dev->dv_cfdriver->cd_name,
+ dev->dv_unit,
+ dev->dv_xname,
+ dev);
+#endif
+
return dev;
}
Index: kern/subr_prf.c
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/kern/subr_prf.c,v
retrieving revision 1.186
diff -u -r1.186 subr_prf.c
--- kern/subr_prf.c 10 Mar 2021 13:27:51 -0000 1.186
+++ kern/subr_prf.c 8 Apr 2021 21:39:41 -0000
@@ -151,7 +151,7 @@
mutex_init(&kprintf_mtx, MUTEX_DEFAULT, IPL_HIGH);
#ifdef RND_PRINTF
rnd_attach_source(&rnd_printf_source, "printf", RND_TYPE_UNKNOWN,
- RND_FLAG_COLLECT_TIME|RND_FLAG_COLLECT_VALUE);
+ RND_FLAG_DEFAULT);
#endif
kprintf_inited = true;
}
Index: rump/librump/rumpkern/hyperentropy.c
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/rump/librump/rumpkern/hyperentropy.c,v
retrieving revision 1.17
diff -u -r1.17 hyperentropy.c
--- rump/librump/rumpkern/hyperentropy.c 30 Apr 2020 03:41:20 -0000 1.17
+++ rump/librump/rumpkern/hyperentropy.c 8 Apr 2021 22:16:39 -0000
@@ -64,6 +64,6 @@
{
rndsource_setcb(&rndsrc, &feedrandom, NULL);
- rnd_attach_source(&rndsrc, "rump_hyperent", RND_TYPE_VM,
+ rnd_attach_source(&rndsrc, "rump_hyperent", RND_TYPE_VM, /* XXX this seems like a re-use of a type! */
RND_FLAG_COLLECT_VALUE|RND_FLAG_HASCB);
}
Index: sys/rndio.h
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/sys/rndio.h,v
retrieving revision 1.2
diff -u -r1.2 rndio.h
--- sys/rndio.h 6 Sep 2015 06:01:02 -0000 1.2
+++ sys/rndio.h 9 Apr 2021 18:01:03 -0000
@@ -91,8 +91,29 @@
#define RND_FLAG_ESTIMATE_TIME 0x00004000 /* estimate entropy on time */
#define RND_FLAG_ESTIMATE_VALUE 0x00008000 /* estimate entropy on value */
#define RND_FLAG_HASENABLE 0x00010000 /* has enable/disable fns */
-#define RND_FLAG_DEFAULT (RND_FLAG_COLLECT_VALUE|RND_FLAG_COLLECT_TIME|\
- RND_FLAG_ESTIMATE_TIME)
+#define RND_FLAG_DEFAULT (RND_FLAG_COLLECT_VALUE|RND_FLAG_ESTIMATE_VALUE| \
+ RND_FLAG_COLLECT_TIME|RND_FLAG_ESTIMATE_TIME)
+/*
+ * N.B.: It would appear from the above value that by default all devices using
+ * RND_FLAG_DEFAULT will be enabled directly to collect _and_ estimate(count)
+ * entropy based on both deltas in values they submit, and the time delta
+ * between submissions. HOWEVER this is moderated by a switch in
+ * kern_entropy.c:rnd_attach_source() which will add either the NO_COLLECT
+ * and/or the NO_ESTIMATE flag depending on what type the device is.
+ *
+ * By default only RND_TYPE_SKEW, RND_TYPE_ENV, RND_TYPE_POWER, and RND_TYPE_RNG
+ * will avoid both of these flags being set.
+ *
+ * Network devices will be entirely disabled (from both colleciton and
+ * estimating) as they can possibly be easily influenced externally.
+ *
+ * All other devices will be given the NO_ESTIMATE flag such that they are not
+ * used to estimate(count) entropy by default.
+ *
+ * In any case either or both of the RND_FLAG_NO_* flags can be turned off at
+ * runtime by the RNDCTL ioctl on rnd(4), i.e. by rndctl(8) such that entropy
+ * collection and estimation can be enabled on a per-device or per-type basis.
+ */
#define RND_TYPE_UNKNOWN 0 /* unknown source */
#define RND_TYPE_DISK 1 /* source is physical disk */
Index: sys/rndsource.h
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/sys/rndsource.h,v
retrieving revision 1.7
diff -u -r1.7 rndsource.h
--- sys/rndsource.h 30 Apr 2020 03:28:19 -0000 1.7
+++ sys/rndsource.h 8 Apr 2021 18:15:01 -0000
@@ -45,8 +45,6 @@
/*
* struct rnd_delta_estimator
- *
- * Unused. Preserved for ABI compatibility.
*/
typedef struct rnd_delta_estimator {
uint64_t x;
@@ -68,8 +66,8 @@
struct krndsource {
LIST_ENTRY(krndsource) list; /* the linked list */
char name[16]; /* device name */
- rnd_delta_t time_delta; /* unused */
- rnd_delta_t value_delta; /* unused */
+ rnd_delta_t time_delta; /* */
+ rnd_delta_t value_delta; /* */
uint32_t total; /* number of bits added while cold */
uint32_t type; /* type, RND_TYPE_* */
uint32_t flags; /* flags, RND_FLAG_* */
@@ -89,8 +87,10 @@
uint32_t);
void rnd_detach_source(struct krndsource *);
+#if 0
void _rnd_add_uint32(struct krndsource *, uint32_t); /* legacy */
void _rnd_add_uint64(struct krndsource *, uint64_t); /* legacy */
+#endif
void rnd_add_uint32(struct krndsource *, uint32_t);
void rnd_add_data(struct krndsource *, const void *, uint32_t, uint32_t);
Index: uvm/uvm_page.c
===================================================================
RCS file: /cvs/master/m-NetBSD/main/src/sys/uvm/uvm_page.c,v
retrieving revision 1.250
diff -u -r1.250 uvm_page.c
--- uvm/uvm_page.c 20 Dec 2020 11:11:34 -0000 1.250
+++ uvm/uvm_page.c 8 Apr 2021 21:41:20 -0000
@@ -983,8 +983,7 @@
* Attach RNG source for this CPU's VM events
*/
rnd_attach_source(&ucpu->rs, ci->ci_data.cpu_name, RND_TYPE_VM,
- RND_FLAG_COLLECT_TIME|RND_FLAG_COLLECT_VALUE|
- RND_FLAG_ESTIMATE_VALUE);
+ RND_FLAG_DEFAULT);
}
/*
--
Greg A. Woods <gwoods%acm.org@localhost>
Kelowna, BC +1 250 762-7675 RoboHack <woods%robohack.ca@localhost>
Planix, Inc. <woods%planix.com@localhost> Avoncote Farms <woods%avoncote.ca@localhost>
Attachment:
pgpdRLQHnu8h9.pgp
Description: OpenPGP Digital Signature