SEO

On Wed, Jan 31, 2007 at 10:11:31AM +1100, Damien Miller wrote:
> On Tue, 30 Jan 2007, Henric Jungheim wrote:
>
> > Looking through the sys/dev/rnd.c code, it struck me that
> > two calls to "extract_entropy()" could perhaps get the same
> > data. If an interrupt happens when a "randomread()" just
[...]
>
> Yes, this is possible. This patch may help:
>
[...]
> + /* Modify pool so next hash will produce different results */
> + getnanotime(&ts);
> + add_entropy_words((u_int32_t *)&ts,
> + sizeof(ts) / sizeof(u_int32_t));
[...]

That is better...

>
> Updating the pool through the add_entropy_words() is very fast, so
> this should not be a significant performance hit.
>
> > There are "splhigh()"s to protect the internal arc4 state
> > variables. However, there are some other state variables
> > that are referenced and modified outside this protection
> > (e.g., "arc4random_initialized"). This can lead to races
> > between multiple callers to "arc4maybeinit()". I don't see
> > anything particularly dangerous of the "it might crash the
> > system variety," but it does mean a caller may get bytes
> > from the pre-stirred state or before/during the "Throw away
> > the first N words of output" stuff.
>
> I don't think so: the actual stirring is done at splhigh.

The "throw away" stuff was not at splhigh() nor was the
test. Using the old state a while longer is irrelevant, but
using the new state before doing the throw-away thing seems
more bothersome than holding splhigh() longer (enough to
include the throw-away code).

>
> > The arc4 word size is 8 bits, so the comment about throwing
> > away 256 words is inconsistent with the loop that throws
> > away 1024 input words (256 * 4 != 256). (That's around line
> > 550 or so.)
>
> The comment is wrong. For the normal 8-bit word RC4, Mantin[1]
> recommends dicarding at least 256 output rounds, up to a
> conservative maximum of 1536 (6*256) rounds. The kernel
> implementation is fairly conservative, but the libc one is less
> so - it only discards 256 rounds.
>
> > What is rand_event's "re_state" supposed to be used for? It
> > is assigned, but not referenced.
>
> It is probably redundant.

Getting rid of it entirely made the code grow. I think it's
because the pointer math gets a bit more complicated since
the structure size is no longer a nice, round 16. Speaking
of which, sticking the large buffers at the end of structs
means that generated "ptr+immediate" opcodes for accessing
the other struct members can get simpler (the "immediate" is
smaller, so possibly smaller/faster machine instructions can
be used). The x86 code shrank a bit from re-ordering the
structs.

>
> -d
>
> [1] s 6.3.4, "Analysus of the stream cipher RC4", Itsik Mantin
> http://www.wisdom.weizmann.ac.il/~it...rs/Mantin1.zip


Anyway, I've tinkered a bit more than I'd intended, but the
below is what I've tested. The important change from my
previous diff is to use Damien's timespec to stir the pool
instead of a fixed word. BTW, wouldn't "ts.tv_nanosec" be
sufficient? I don't see the leading "tv_sec" part as adding
anything constructive other than more iterations inside
"add_entropy_words()" (the time is sampled in so many other
place anyway).


Index: rnd.c
================================================== =================
RCS file: /usr/cvs/openbsd/src/sys/dev/rnd.c,v
retrieving revision 1.80
diff -u -r1.80 rnd.c
--- rnd.c 11 Apr 2006 14:31:52 -0000 1.80
+++ rnd.c 31 Jan 2007 11:08:11 -0000
@@ -366,9 +366,9 @@
u_int add_ptr;
u_int entropy_count;
u_char input_rotate;
- u_int32_t pool[POOLWORDS];
u_int asleep;
u_int tmo;
+ u_int32_t pool[POOLWORDS];
};

/* There is one of these per entropy source */
@@ -381,14 +381,14 @@
};

struct arc4_stream {
- u_int8_t s[256];
u_int cnt;
u_int8_t i;
u_int8_t j;
+ u_int8_t s[256];
};

struct rand_event {
- struct timer_rand_state *re_state;
+ u_int re_pad;
u_int re_nbits;
u_int re_time;
u_int re_val;
@@ -472,7 +472,7 @@
void dequeue_randomness(void *);

static void add_entropy_words(const u_int32_t *, u_int n);
-void extract_entropy(register u_int8_t *, int);
+void extract_entropy(u_int8_t *, int);

static u_int8_t arc4_getbyte(void);
void arc4_stir(void);
@@ -500,7 +500,7 @@
static u_int8_t
arc4_getbyte(void)
{
- register u_int8_t si, sj, ret;
+ u_int8_t si, sj, ret;
int s;

s = splhigh();
@@ -521,8 +521,8 @@
arc4_stir(void)
{
u_int8_t buf[256];
- register u_int8_t si;
- register int n, s;
+ u_int8_t si;
+ int n, s;
int len;

nanotime((struct timespec *) buf);
@@ -533,6 +533,13 @@
len += sizeof(struct timeval);

s = splhigh();
+
+ if (arc4random_initialized) {
+ splx(s);
+ return;
+ }
+ arc4random_initialized = 1;
+
arc4random_state.i--;
for (n = 0; n < 256; n++) {
arc4random_state.i++;
@@ -546,15 +553,17 @@
arc4random_state.cnt = 0;
rndstats.arc4_stirs += len;
rndstats.arc4_nstirs++;
- splx(s);

/*
* Throw away the first N words of output, as suggested in the
* paper "Weaknesses in the Key Scheduling Algorithm of RC4"
- * by Fluher, Mantin, and Shamir. (N = 256 in our case.)
+ * by Fluher, Mantin, and Shamir. (N = 256 in our case, but
+ * we throw away N * 4 to be safe.)
*/
for (n = 0; n < 256 * 4; n++)
arc4_getbyte();
+
+ splx(s);
}

void
@@ -567,7 +576,6 @@
if (!rnd_attached)
panic("arc4maybeinit: premature");
#endif
- arc4random_initialized++;
arc4_stir();
/* 10 minutes, per dm@'s suggestion */
timeout_add(&arc4_timeout, 10 * 60 * hz);
@@ -680,8 +688,8 @@
};

for (; n--; buf++) {
- register u_int32_t w = roll(*buf, random_state.input_rotate);
- register u_int i = random_state.add_ptr =
+ u_int32_t w = roll(*buf, random_state.input_rotate);
+ u_int i = random_state.add_ptr =
(random_state.add_ptr - 1) & (POOLWORDS - 1);
/*
* Normally, we add 7 bits of rotation to the pool.
@@ -719,8 +727,8 @@
enqueue_randomness(state, val)
int state, val;
{
- register struct timer_rand_state *p;
- register struct rand_event *rep;
+ struct timer_rand_state *p;
+ struct rand_event *rep;
struct timespec tv;
u_int time, nbits;
int s;
@@ -747,7 +755,7 @@
* deltas in order to make our estimate.
*/
if (!p->dont_count_entropy) {
- register int delta, delta2, delta3;
+ int delta, delta2, delta3;
delta = time - p->last_time;
delta2 = delta - p->last_delta;
delta3 = delta2 - p->last_delta2;
@@ -807,7 +815,6 @@
return;
}

- rep->re_state = p;
rep->re_nbits = nbits;
rep->re_time = tv.tv_nsec ^ (tv.tv_sec << 20);
rep->re_val = val;
@@ -829,7 +836,7 @@
void *v;
{
struct random_bucket *rs = v;
- register struct rand_event *rep;
+ struct rand_event *rep;
u_int32_t buf[2];
u_int nbits;
int s;
@@ -843,7 +850,6 @@
buf[0] = rep->re_time;
buf[1] = rep->re_val;
nbits = rep->re_nbits;
- splx(s);

add_entropy_words(buf, 2);

@@ -852,6 +858,8 @@
if (rs->entropy_count > POOLBITS)
rs->entropy_count = POOLBITS;

+ splx(s);
+
if (rs->asleep && rs->entropy_count > 8) {
#ifdef RNDEBUG
if (rnd_debug & RD_WAIT)
@@ -884,7 +892,7 @@
*/
void
extract_entropy(buf, nbytes)
- register u_int8_t *buf;
+ u_int8_t *buf;
int nbytes;
{
struct random_bucket *rs = &random_state;
@@ -892,6 +900,7 @@
MD5_CTX tmp;
u_int i;
int s;
+ struct timespec ts;

add_timer_randomness(nbytes);

@@ -901,6 +910,9 @@
else
i = sizeof(buffer) / 2;

+ if (rs->entropy_count / 8 < i)
+ dequeue_randomness(&random_state);
+
/* Hash the pool to get the output */
MD5Init(&tmp);
s = splhigh();
@@ -909,6 +921,12 @@
rs->entropy_count -= i * 8;
else
rs->entropy_count = 0;
+
+ /* Modify pool so next hash will produce different results */
+ getnanotime(&ts);
+ add_entropy_words((u_int32_t *)&ts,
+ sizeof (ts) / sizeof(u_int32_t));
+
splx(s);
MD5Final(buffer, &tmp);

@@ -929,15 +947,12 @@
bcopy(buffer, buf, i);
nbytes -= i;
buf += i;
-
- /* Modify pool so next hash will produce different results */
- add_timer_randomness(nbytes);
- dequeue_randomness(&random_state);
}

/* Wipe data from memory */
bzero(&tmp, sizeof(tmp));
bzero(&buffer, sizeof(buffer));
+ bzero(&ts, sizeof(ts));
}

/*
@@ -1126,7 +1141,7 @@
struct uio *uio;
int flags;
{
- int ret = 0;
+ int s, ret = 0;
u_int32_t *buf;

if (minor(dev) == RND_RND || minor(dev) == RND_PRND)
@@ -1144,7 +1159,9 @@
if (!ret) {
while (n % sizeof(u_int32_t))
((u_int8_t *) buf)[n++] = 0;
+ s = splhigh();
add_entropy_words(buf, n / 4);
+ splx(s);
}
}