Security Properties of a Class of True Random Number Generators in Programmable Logic

Nowadays, digital equipment such as computers with Internet and cellular phones arecommonly used for communication. The users want secure communications, meaning thatconfidentiality, integrity and authenticity are maintained throughout the session. Confidentialitymeans that only the intended recipient has access to the transmitted information,integrity ensures that the information is protected against modifications, and finally, authenticityguarantees the identities of the communicating parties. All these security aspectscan be achieved using cryptographic techniques and protocols. In a cryptographic systemwhere the algorithm is public, the entire security depends on the used cryptographic key.These keys are generated by using pseudo random number generators (PRNGs) using analgorithm combined with a seed or true random number generators (TRNGs) based on aphysical property generating random noise. A TRNG is preferred if the cryptographic systemrequires a high level of security. Traditionally, a cryptographic system is implementedin an application specific integrated circuit (ASIC), but during the recent years a field programmablegate array (FPGA) has become an attractive alternative. The advantages ofusing an FPGA compared to an ASIC are the flexibility regarding update of the configurationfor correcting errors or adding new functionality, an easier and faster developmentprocess and availability of FPGA devices on short notice from the vendors. On the otherhand, the flexibility of an FPGA with the possibility of changing the configuration makes itmore vulnerable against attacks. The challenge is to design a TRNG in an FPGA with goodstatistical properties, a reasonable high bit rate and robustness against attacks. In this thesis, a practical and functional enhancement of a class of TRNGs based on severalequal length oscillator rings is proposed. The generation of true randomness is basedon the uncertainty of where in time a transition, i.e. a change from logical zero to logicalone or vice versa, of the oscillator ring outputs occur due to the presence of jitter. The enhancedTRNG was implemented in several FPGA families and the security properties wereexamined. The statistical properties were investigated by running the statistical test suitesNIST SP 800-22 and DIEHARD, and the test results showed that this TRNG passes thesetests. Due to the proposed enhancement the number of oscillator rings could be reducedand a post-processor was not needed in order to pass the statistical tests. Restart experimentsfrom an identical reset state showed that this TRNG generates true randomnessand not only pseudo randomness. A detailed spectral analysis was performed on each ofthe building blocks of this TRNG by investigating the frequency spectrum both in theoryand by simulations showing that it approaches the frequency spectrum of an ideal randomnumber generator. The purpose was also to optimize the design parameters in orderto achieve a high bit rate. Experiments were performed and a bit rate of 300Mbit/s wasachieved while generating random bits with good statistical properties. Even though thestatistical properties were found to be good, understanding the noise source and quantifyingthe amount of entropy are important in the evaluation of an TRNG. A model basedon the accumulation of jitter was proposed and simulations were carried out showing theinfluence of the different design parameters and technology properties on the number ofhits close to a transition region defined by the standard deviation of the accumulated jitter.The simulations show that the proposed TRNG with high probability generates bits withhigh entropy at every sampling point. An investigation of the properties of oscillator ringsimplemented in three different FPGAs was performed in order to examine the interactionibetween rings located close to each other, the correlation and dependency between therings and also the dispersion of the oscillator ring frequencies. The investigation revealedthat there is interaction between some of the rings and a few of them could be regardedas correlated due to almost identical ring frequencies. The experiments showed that thereare differences between the examined SRAM based FPGAs compared to a flash FPGA regardingthe dispersion of the ring frequencies. The robustness of the TRNG was examinedby employing an attack by superimposing a noise signal onto the power supply voltage tothe FPGA. Four different TRNG designs were investigated and the two designs based onseveral oscillator rings were not influenced by this attack while two other reference TRNGdesigns were. Simulations were performed in order to explain the observed behavior onthe TRNGs consisting of oscillator rings. A more exact power model of a microcontrollerbus based on the influence of crosstalk due to capacitive couplings between the bus lineswas proposed in order to more precisely determine the energy consumption. This modelcould for instance be used in a side-channel attack determining the encryption key withreduced computational effort. A TRNG based on the proposed design was implemented in a real life cryptographicsystem with good results showing that this TRNG is both practical and secure. In addition,this TRNG design is easy to implement in programmable logic, the placement of theinverters inside the FPGA is not critical, it is robust against temperature and power supplyvariations and not influenced by effects related to aging. All this makes a TRNG based onXOR of several sampled oscillator rings a suitable component in a cryptographic system