On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote:
> > > What I meant with that point is that the user may get, say an extra few
> > > hundred bits out of it with no new entropy before the scheduled reseed
> > > task kicks in.
> >
> > How does he know which bits are which? His analysis task just got a whole
> > lot more difficult.
>
> Again, not entirely correct but not relevant either...
>
> Kris is simply right in that the /dev/random semantics change
> and that more bits can be output by Yarrow than there is entropy
> gathered. *In theory* the complexity of an attack on our Yarrow
> has an upper bound of 2^256 and *in theory* this is less than
> the complexity of an attack on our current /dev/random. This is
> a hard fact, no way around that.
Even if the attack on a single non-blocking read from Yarrow is only
of 2^256 complexity, it is designed to be much more expensive than
just cracking a single block cipher. Blowfish has a very large keying
step, and Yarrow is designed to exploit having large keying steps and
then adding more complexity in its setup in addition. This makes it
infeasible to mount attacks on Yarrow, and the security is really not
as weak as just cracking 20-round Blowfish-256.
However, none of this makes Yarrow useless for getting many bits of
high-quality random data for, e.g., generation of an RSA key.
> However, the big question here is not about theory but about
> *practicality*. Is Yarrow less secure than /dev/random in
> practice? How does our /dev/random hold up under attack? How
> does Yarrow compare? I think we need to evaluate these practical
> questions instead of deep theoretical issues as Yarrow is all
> about practicality.
>
> At a more fundamental level we will need to answer the question:
> "Do we need to preserve the current /dev/random semantics or
> can we decide to change 'em? [1]". And how will this affect our
> applications *in practice*.
Mark already stated that in *practicality*, Yarrow-BF-cbc-256 1.0
(I guess that's the proper name for this :-) is complex enough and
generates good enough ouput. If you /really/ want to make the attack
on it much harder, how about this: if you're going to read 1024 bits
of entropy from Yarrow on /dev/random, you will request it all at once
and block just as the old random(4) used to block; the blocking can
occur at 256 bit intervals and sleep until there is a reseed. Waiting
to reseed for each read will ensure a much larger amount of "real"
entropy than it "maybe" happening at random times.
Can you really find anything wrong with doing what I propose *in
practice*? I'm certain that it would make it about as hard to
brute-force the key while knowing certain parameters of its generation
as it would be to just factor the damned 1024-bit number. I've
already implemented this as well as some other bugfixes, so see the
attached diff.
> So let's concentrate this discussion on the practical issues
> and explain why you think backing /dev/random with Yarrow and
> changing the semantics is justifyable or even a good thing.
>
> Cheers,
> Jeroen
>
> [1] And, should we decide not to change /dev/random semantics,
> can we still back /dev/random with a modified Yarrow?
I think it makes sense :)
> --
> Jeroen C. van Gelderen o _ _ _
> [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_)
> _< \_ _>(_) (_)/<_ \_| \ _|/' \/
> (_)>(_) (_) (_) (_) (_)' _\o_
--
Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! /
[EMAIL PROTECTED] `------------------------------'
Index: sys/sys/random.h
===================================================================
RCS file: /usr2/ncvs/src/sys/sys/random.h,v
retrieving revision 1.25
diff -u -r1.25 random.h
--- sys/sys/random.h 2000/07/25 21:18:45 1.25
+++ sys/sys/random.h 2000/07/29 23:19:20
@@ -36,6 +36,8 @@
enum esource { RANDOM_WRITE, RANDOM_KEYBOARD, RANDOM_MOUSE, RANDOM_NET, \
ENTROPYSOURCE };
void random_harvest(void *, u_int, u_int, u_int, enum esource);
+void set_wakeup(int *, int);
+void set_wakeup_exit(int *, int, int);
#endif
Index: sys/dev/randomdev/harvest.c
===================================================================
RCS file: /usr2/ncvs/src/sys/dev/randomdev/harvest.c,v
retrieving revision 1.4
diff -u -r1.4 harvest.c
--- sys/dev/randomdev/harvest.c 2000/07/25 21:18:46 1.4
+++ sys/dev/randomdev/harvest.c 2000/07/29 23:18:50
@@ -30,6 +30,7 @@
#include <sys/systm.h>
#include <sys/types.h>
#include <sys/queue.h>
+#include <sys/kthread.h>
#include <sys/linker.h>
#include <sys/libkern.h>
#include <sys/mbuf.h>
@@ -72,4 +73,23 @@
nanotime(&timebuf);
(*reap)(&timebuf, entropy, count, bits, frac, origin);
}
+}
+
+/*
+ * Helper routines to let kthread_exit() do its stuff properly (i.e. no crash).
+ */
+void
+set_wakeup(int *var, int value)
+{
+
+ *var = value;
+ wakeup(var);
+}
+
+void
+set_wakeup_exit(int *var, int value, int exitval)
+{
+
+ set_wakeup(var, value);
+ kthread_exit(exitval);
}
Index: sys/dev/randomdev/randomdev.c
===================================================================
RCS file: /usr2/ncvs/src/sys/dev/randomdev/randomdev.c,v
retrieving revision 1.10
diff -u -r1.10 randomdev.c
--- sys/dev/randomdev/randomdev.c 2000/07/25 21:22:17 1.10
+++ sys/dev/randomdev/randomdev.c 2000/07/30 03:00:01
@@ -31,6 +31,7 @@
#include <sys/systm.h>
#include <sys/conf.h>
#include <sys/fcntl.h>
+#include <sys/filio.h>
#include <sys/uio.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
@@ -42,6 +43,7 @@
#include <sys/rman.h>
#include <sys/signalvar.h>
#include <sys/sysctl.h>
+#include <sys/vnode.h>
#include <crypto/blowfish/blowfish.h>
#include <dev/randomdev/yarrow.h>
@@ -49,6 +51,7 @@
static d_open_t random_open;
static d_read_t random_read;
static d_write_t random_write;
+static d_ioctl_t random_ioctl;
#define CDEV_MAJOR 2
#define RANDOM_MINOR 3
@@ -59,7 +62,7 @@
/* close */ (d_close_t *)nullop,
/* read */ random_read,
/* write */ random_write,
- /* ioctl */ noioctl,
+ /* ioctl */ random_ioctl,
/* poll */ nopoll,
/* mmap */ nommap,
/* strategy */ nostrategy,
@@ -101,14 +104,30 @@
random_read(dev_t dev, struct uio *uio, int flag)
{
u_int c, ret;
- int error = 0;
+ int error = 0, left;
void *random_buf;
c = min(uio->uio_resid, PAGE_SIZE);
random_buf = (void *)malloc(c, M_TEMP, M_WAITOK);
- while (uio->uio_resid > 0 && error == 0) {
- ret = read_random(random_buf, c);
- error = uiomove(random_buf, ret, uio);
+ if (minor(dev) == URANDOM_MINOR) {
+ while (uio->uio_resid > 0 && error == 0) {
+ ret = read_random(random_buf, min(c, uio->uio_resid));
+ error = uiomove(random_buf, ret, uio);
+ }
+ } else {
+ if (flag & IO_NDELAY || c <= KEYSIZE) {
+ ret = read_random(random_buf, c);
+ error = uiomove(random_buf, ret, uio);
+ } else {
+ while (uio->uio_resid > 0 && error == 0) {
+ left = min(KEYSIZE, uio->uio_resid);
+ ret = read_random(random_buf, left);
+ error = uiomove(random_buf, left, uio);
+ if (error == 0)
+ error = tsleep(read_random,
+ PPAUSE | PCATCH, "yarrow", 0);
+ }
+ }
}
free(random_buf, M_TEMP);
return error;
@@ -134,6 +153,18 @@
}
static int
+random_ioctl(dev_t dev, u_long cmd, caddr_t addr, int flags, struct proc *p)
+{
+
+ switch (cmd) {
+ case FIONBIO:
+ return (0);
+ default:
+ return (ENOTTY);
+ }
+}
+
+static int
random_modevent(module_t mod, int type, void *data)
{
switch(type) {
@@ -148,9 +179,11 @@
return 0;
case MOD_UNLOAD:
- random_deinit();
+ if (count_dev(random_dev) != 0 || count_dev(urandom_dev) != 0)
+ return EBUSY;
destroy_dev(random_dev);
destroy_dev(urandom_dev);
+ random_deinit();
return 0;
case MOD_SHUTDOWN:
Index: sys/dev/randomdev/yarrow.c
===================================================================
RCS file: /usr2/ncvs/src/sys/dev/randomdev/yarrow.c,v
retrieving revision 1.14
diff -u -r1.14 yarrow.c
--- sys/dev/randomdev/yarrow.c 2000/07/25 21:22:17 1.14
+++ sys/dev/randomdev/yarrow.c 2000/07/29 23:14:42
@@ -213,6 +213,9 @@
/* 7. Dump to seed file (done by external process) */
+ /* Wake up anyone waiting for a reseed. */
+
+ wakeup(read_random);
}
u_int
@@ -221,7 +224,7 @@
static u_int64_t genval;
static int cur = 0;
static int gate = 1;
- u_int i;
+ u_int i, left;
u_int retval;
intrmask_t mask;
@@ -241,13 +244,13 @@
(unsigned char *)&genval,
sizeof(random_state.counter),
&random_state.key, random_state.ivec, BF_ENCRYPT);
- memcpy((char *)buf + i, &genval,
- sizeof(random_state.counter));
+ left = min(count - i, sizeof(random_state.counter));
+ memcpy((char *)buf + i, &genval, left);
if (++random_state.outputblocks >=
random_state.gengateinterval) {
generator_gate();
random_state.outputblocks = 0;
}
- retval += sizeof(random_state.counter);
+ retval += left;
}
}
else {
