Implementing and Testing Self-Timed Rings on a FPGA as Entropy Sources

Sammanfattning: Random number generators are basic building blocks of modern cryptographic systems. Usually pseudo random number generators, carefully constructed deter- ministic algorithms that generate seemingly random numbers, are used. These are built upon foundations of thorough mathematical analysis and have been subjected to stringent testing to make sure that they can produce pseudo random sequences at a high bit-rate with good statistical properties. A pseudo random number generator must be initiated with a starting value. Since they are deterministic, the same starting value used twice on the same pseudo random number generator will produce the same seemingly random sequence. Therefore it is of utmost importance that the starting value contains enough en- tropy so that the output cannot be predicted or reproduced in an attack. To gen- erate a high entropy starting value, a true random number generator that uses sampling of some physical non-deterministic phenomenon to generate entropy, can be used. These are generally slower than their pseudo random counterparts but in turn need not generate the same amount of random values. In field programmable gate arrays (FPGA), generating random numbers is not trivial since they are built upon digital logic. A popular technique to generate entropy within a FPGA is to sample jittery clock signals. A quite recent technique proposed to create a robust clock signals, that contains such jitter, is to use self- timed ring oscillators. These are structures in which several events can propagate freely at an evenly spaced phase distribution. In this thesis self-timed rings of six different lengths is implemented on a spe- cific FPGA hardware. The different implementations are tested with the TestU01 test suite. The results show that two of the implementations have a good oscilla- tory behaviour that is well suited for use as random number generators. Others exhibit unexpected behaviours that are not suited to be used in a random num- ber generator. Two of the implemented random generators passed all tests in the TestU01 batteries Alphabit and BlockAlphabit. One of the generators was deemed not fit for use in a random number generator after failing all of the tests. The last three were not subjected to any tests since they did not behave as ex- pected.