On Tue, Dec 21, 2010 at 05:59:33PM +0100, Kurt Knochner wrote:
> 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.
I don't know the answer to this question, but my guess is that the
buffer is filled by nanotime() to cover the case that
get_random_bytes() does not have enough entropy available, so at least
some non-constant data is used.
>
> ==> 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.
rc4_crypt() changes both the state and the contents of buf, since buf is
used both as source and destination. That buf is used by rc4_keysetup()
to create a new state. So indeed the state is overwritten, but the
contents of buf produced by rc4_crypt() is used to do that. So both
calls serve their purpose.
-Otto
>
> 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/
