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/

Reply via email to