Week 5

The code for the Linux Random Number Generator a continuously reseeded Twisted Generalized Feedback Shift Register. Last week, I found the places in the code where entropy is added and the PRNG is reseeded as well as the places where the entropy estimation is calculated. However, since the entropy estimation is solely based on the length of time between events, I could see no correlation between the entropy estimation and which input bits were considered random. Therefore, I decided to look deeper into the TGFSR to understand how it works and to verify what I found before. After reading several papers, I discovered that the TGFSR works by using a primitive polynomial as a cyclic generator for a finite field. It generates all the powers of x mod the primitive polynomial and evaluates them at x=1. This produces a Tausworthe sequence of statistically random bits. Using a delay factor, this sequence is transformed into a linearly independent matrix that forms the initial seed for the generator. When a random number is requested, the rows of the matrix corresponding to the powers of the primitive polynomial (called the taps) are xored together and hashed via SHA-1. The pre-hash value is then put back into the matrix and the taps are all moved up by one. The LRNG adds randomness by doing the same procedure as described above, except that the value to be put back into the matrix is first xored with the bits produced by the random event.

This functionality seems to support the observation that there is no correlation between the entropy estimate and which bits are random. As long as some of the bits produced by the random event are indeed random, the mixing procedure in conjunction with the SHA-1 hash will ensure an unpredictable output.

In light of this, we decided to proceed by writing all of the random bits from each event to separate files so that we could still do some analysis. I began working on this by trying to modify the Linux kernel in a very small way and then to recompile and reinstall. I am attempting this on a Ubuntu Virtual Machine on a Mac laptop through Virtual Box. I am able to modify and recompile the source code, but I am having difficulty installing the kernel with my changes. The instructions from the book Linux Kernel Development are for using the original Grub boot loader. However, Virtual Box seems to be using Grub2. I have found some forum posts on-line, but am now getting a file system error when I try to boot the new version. I will continue this work in the coming week.