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/