Weeks 3/4

The next goal for our project is to gather a stream of random bits generated from the Linux kernel. As described in the paper “Analysis of the Linux Random Number Generator” by Gutterman & Pinkas, the Linux Random Number Generator (LRNG) gathers random bits from the following sources:

* Keybord

* Mouse

* Hard Drive

* Interrupts

We wish to gather a sampling of these random bits in order to test their statistical properties.

I downloaded the latest Linux source (version 3.9.3) and began looking through the RNG. The majority of relevant code can be found in the file random.c. As documented in this file, and as described in the paper by Gutterman & Pinkas, the LRNG functions as a Twisted Generalized Feedback Shift Register. The functionality is is a pseudo-random number generator that is continuously reseeded as new random events occur.

Each random event produces two random words. One is based on the timing, and the other is based on the type of event. The LRNG runs an algorithm to determine the number of bits that were actually random in those words, and increments the current entropy estimate accordingly. When a random byte is requested from the pool, the output is hashed using the SHA-1 algorithm. It seems that the code is somewhat dependent on the randomness of SHA-1 in that if some part of the input is random, then it will hash to an unpredictable output. The difficulty for us will be determining which of the pre-hash bits are actually random according to the LRNG's estimate, since these are the ones we want to analyze.

I have located each function that adds entropy to the pool for each type of random event. So once I determine how to extract which bits we are interested in, I should be able to output those bits to a file.

I have installed a Linux virtual machine on a Mac laptop through virtual box and plan to make changes to the kernel source in order to write the random bits from each source to a separate file.

I have read parts of Robert Love's book “Linux Kernel Development”. The book is based of the Linux kernel version 2.6.10, but still seems to be a good reference for the kernel's functionality.

I have also been reading up on the functionality of the Twisted Generalized Feedback Shift Register PRNG. It involves quite a bit of complex abstract algebra, but I think I have a decent grasp of its basic functionality. This knowledge is extremely important since the entire LRNG code in random.c is based on it.

I am continuing to examine the kernel code, and am continuing to understand more of it. In the next week, I will continue this process with the goal of extracting the random bits as they are mixed into the entropy pool.