Hi,
upfront: sorry for double posting!! Some people told me, that I should send
my findings directly to the list instead of a link. Sorry if I violated the
netiquette on the list!
So, here we go again (text from the forum where I posted it).
regarding the allegations about a backdoor beeing planted into OpenBSD, I
did a code review myself and I believe that I've found two bugs in the PRNG
code. I'm NOT saying that this is the backdoor or even part of the backdoor.
I'm not even saying, that these two bugs create a weakness in the PRNG
itself, however the two bugs just don't look good and possibly need more
investigation!!
Here we go...
OpenBSD uses arc4random() and arc4random_buf() all over the code to generate
random numbers. This code is defined in src/sys/dev/rnd.c.
Within arc4random() and arc4random_buf() the code flow is like this:
arc4random -> arc4maybeinit -> arc4_stir
arc4_stir() will be called at least every 10 minutes, as a timer is set
within arc4maybeinit() that resets the variable 'arc4random_initialized'
(see below).
> static void
> arc4maybeinit(void)
> {
>
> if (!arc4random_initialized) {
> #ifdef DIAGNOSTIC
> if (!rnd_attached)
> panic("arc4maybeinit: premature");
> #endif
> arc4random_initialized++;
> arc4_stir();
> /* 10 minutes, per dm@'s suggestion */
> timeout_add_sec(&arc4_timeout, 10 * 60);
> }
> }
Now, let's have a look at arc4_stir().
> arc4_stir(void)
> {
> u_int8_t buf[256];
> int len;
>
> nanotime((struct timespec *) buf);
> len = sizeof(buf) - sizeof(struct timespec);
> get_random_bytes(buf + sizeof (struct timespec), len);
> len += sizeof(struct timespec);
>
> mtx_enter(&rndlock);
> if (rndstats.arc4_nstirs > 0)
> rc4_crypt(&arc4random_state, buf, buf, sizeof(buf));
>
> rc4_keysetup(&arc4random_state, buf, sizeof(buf));
> arc4random_count = 0;
> rndstats.arc4_stirs += len;
> rndstats.arc4_nstirs++;
>
> /*
> * 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.)
> */
> rc4_skip(&arc4random_state, 256 * 4);
> mtx_leave(&rndlock);
>
> }
This initializes the RC4 context with some random data, gathered by system
enthropy, that is mainly done by get_random_bytes().
==> Bug #1
HOWEVER: Have a look at the buffer that's beeing used as a seed for the RC4
key setup. It's beeing filled with the random data, BUT at the beginning it
will be filled with just the value of nanotime().
> nanotime((struct timespec *) buf);
> len = sizeof(buf) - sizeof(struct timespec);
> get_random_bytes(buf + sizeof (struct timespec), len);
> len += sizeof(struct timespec);
So, there is a lot of effort in get_random_bytes() to get "real random" data
for the buffer and then the value of nanotime() is prepended to the buffer?
That does not look right. Please consider: this buffer will be used as key
for rc4_keysetup() and thus it should contain unrelated and unpredictable
data.
==> Bug #2
The function rc4_crypt() get's called as soon as rndstats.arc4_nstirs > 0.
This will be the case whenever arc4_stir get's called the second time (by
the timer reset - see above).
> if (rndstats.arc4_nstirs > 0)
> rc4_crypt(&arc4random_state, buf, buf, sizeof(buf));
> rc4_keysetup(&arc4random_state, buf, sizeof(buf));
> arc4random_count = 0;
> rndstats.arc4_stirs += len;
> rndstats.arc4_nstirs++;
HOWEVER, right after the call of rc4_crypt(), we call rc4_keysetup() with
the same 'arc4random_state'. This makes the call to rc4_crypt() useless, as
the data structure will be overwritten again with the init data of the RC4
function.
AGAIN: I'm not saying that this is part of the backdoor nor that it weakens
the PRNG. HOWEVER, this does not look right and leaves some bad feeling for
me!
I think we will need some investigation on the effect of PRNG quality caused
by these two bugs.
Regards
Kurt Knochner
http://knochner.com/
