Title Page
Wayne Coppock
Colin Philbrook
Abstract
In this paper analysis of jitter is conducted to determine its suitability for use as an entropy source for a true random number generator. To achieve this, efforts are taken to isolate and quantify jitter in ring oscillator circuits and to understand its relationship to design specifications. The accumulation of jitter via various methods is also investigated to determine whether there is an optimal accumulation technique for sampling the uncertainty of jitter events. Mathematical techniques are used to analyze the accumulation process and an attempt at modeling a signal with jitter is made. The physical properties responsible for the noise that causes jitter are also briefly investigated.
Acknowledgements
Table of Contents
Title Page 1
Abstract 2
Acknowledgements 3
Table of Figures 5
Table of Tables 5
1 Background 6
1.1 Cryptography 6
1.2 Random Number Generators 7
1.3 Jitter 9
2 Methodology 10
2.1 Development Environment 10
2.1.1 Hardware 10
2.1.2 Software Design Flow 10
2.2 Testing Environment and Procedures 11
2.2.1 Jitter Measurement 11
2.2.2 Oscilloscope 14
3 Results and Analysis 15
3.1 Ring Oscillator 15
3.2 Theoretical Analysis 18
3.2.1 Central Limit Theorem 18
3.2.2 Correlated Noise Sources 19
3.3 Experimental Analysis 20
3.3.1 Basic Jitter Statistics 20
3.3.2 N-Cycle Accumulation 21
3.3.3 Jitter Density 26
3.3.4 Periodic Noise and Filtering 28
3.4 Modeling 31
4 Future Work 33
5 Conclusion 34
References 35
Table of Figures
Figure 1: Basic Jitter Diagram 9
Figure 2: Design Flow 11
Figure 3: Jitter Measurement Techniques [3] 12
Figure 4: Simple 3-Inverter Ring 15
Figure 5: Timing Diagram 16
Figure 6: Comparison of 57 and 151 Inverter Waveforms 17
Figure 7: Log-Log Plot of Standard Deviation vs. Measurement Period [6] 20
Figure 8: Standard Deviation vs. Number of Inverters 21
Figure 9: N-Cycle Accumulations 22
Figure 10: First Fifty Cycles 23
Figure 11: Log-Log plot of N-Cycle Data 23
Figure 12: Period Measurements for 67 Inverter Ring 24
Figure 13: Period Measurements for 101 Inverter Ring 24
Figure 14: N-Cycle Histogram Comparison for 67 Inverter Ring 25
Figure 15: TIE Time Trend 28
Figure 16: TIE Spectrogram 29
Figure 17: Filtered TIE Time Trend 30
Figure 18: TIE Histogram Improvement 30
Figure 19: Signal / Model Comparison 32
Table of Tables
Table 1: Jitter Density Results 27
1 Background
1.1 Cryptography
Cryptography is a pervasive element in modern life, the importance of which can hardly be overstated. It is nothing less than the modern application of technology (though its origins date back to the beginnings of civilization) to the problem of keeping secrets secret. In a modern sense, cryptography mostly involves the use of algorithms to keep electronic data secure. In a broader context, there are various ways which cryptography can keep data secure. It can keep data secure from someone for whom it was not intended, it can confirm that data not become corrupted or altered in transit, and it can ensure that the data comes from a trustworthy source. These are called confidentiality, data integrity, and authentication respectively. Although they differ in their application of it, all use the basic cryptographic system of encryption and decryption.
No matter how secure from attacks the algorithm used for the encryption process is, this system is only as strong as the key used to encode the information. In many modern systems the assumption is made that the key is unknown and unable to be guessed. This assumption has lead to the widespread use of random (mostly pseudorandom) numbers as keys, meaning that a system is now only as secure as the random number generator used to produce the key. A weak random number generator whose output can be easily guessed provides no security for the data being encrypted. In cryptographic applications, random numbers must be completely unpredictable to any form of attack, including an attacker who has great computing power and a large sample of random numbers from the source being used.
1.2 Random Number Generators
A “random number generator” (RNG) is a device or system which produces an unpredictable sequence of numbers or bits that cannot be reproduced. RNGs are widely used today in a variety of applications including simulation, modeling, computer games, and cryptographic systems. For many of these applications a pseudorandom number generator (PRNG) is sufficient to meet the demands, however for cryptographic applications a very strong random number generator is needed. In order to ensure a completely reliable source of random numbers, true (physical) random number generators (TRNGs) should be used.
For less demanding applications, a set of algorithms (PRNGs) are typically used that, when seeded with random input from some entropy source, can generate a sequence which may be computationally infeasible to distinguish from the output of a TRNG [2]. Since PRNG algorithms are deterministic, the entropy of the output will be at most that of the seed input. This makes them typically inadequate for use in secure communications, especially in the face of ever-increasing computing power, which may make currently infeasible calculations quite easy in the near future. In cryptographic applications the concept of an ‘attacker’ is often used to discern weaknesses in the unpredictability of random number generators. With PRNGs an attacker need only to discover the seed and algorithm to generate the exact same sequence of ‘random’ numbers, thus compromising the security of the system. Additionally since PRNGs use deterministic algorithms, the sequence of numbers generated will eventually repeat, so an attacker with a large amount of computing power could check every possible output that the algorithm can generate, again compromising the system.
With TRNGs an internal physical source of entropy is identified and used to generate random numbers, usually involving a conversion of analogue noise of some kind to a digital signal [1]. In a well-designed TRNG this source of entropy is sampled to obtain a sequence of statistically independent bits which may undergo post-processing and result in a string of truly random bits. TRNGs are completely reliant on their source of entropy being truly random, and any amount of deterministic input that may influence the output puts the system at risk of attack. However it is difficult to exclude all deterministic input from systems whose entropy is easily isolated, and so a robust design should take deterministic elements in this source into account.
Several sources of entropy are available, however many are plagued with problems of practical implementation and strength against attack. Proposed sources such as the interval between user keystrokes or device interrupts, network traffic, least significant bits of analog input, and atmospheric radio noise are all vulnerable to either being biased from an outside attack or by an attacker’s ability to measure the same events. A few sources not vulnerable to these attacks such as radioactive decay and the photoelectric effect are difficult and costly to implement, especially for use in a portable environment. Currently the most promising source of entropy seems to be noise in electronic components. This noise has a basis in quantum effects yet is easily implemented with existing semiconductor technology.
1.3 Jitter
Physical limitations in the implementation of circuit designs often give rise to unexpected problems, such as a timing problem known as “jitter.” Jitter is a phenomenon which arises in oscillators and thereby any circuit with a timing clock. In an ideal oscillator the time between state transitions is constant; however in real application this time is always variable. A rather concise, albeit useful, definition of jitter is “the short-term variations of a digital signal’s significant instants from their ideal positions in time,” [5] where the “significant instants” are the state transitions. Since every state transition has some uncertainty in its timing and the uncertainty from each transition affects later transitions, these small amounts of uncertainty accumulate as the observed timeframe grows larger.
Figure 1: Basic Jitter Diagram
In many cases the term “jitter” is used to refer to all phase noise within a signal. In this framework jitter is broken up into two varieties: random and deterministic. Random jitter is considered to be unbounded, while deterministic jitter is considered to be bounded [3]. Furthermore, deterministic jitter is broken down into various varieties of deterministic noise which may affect signal timing. For the purposes of this paper only “random jitter” will be referred to as jitter and all varieties of “deterministic jitter” will be referred to as deterministic noise. Although as a random noise source it may have any probability distribution, jitter is generally assumed to have a Gaussian (normal) distribution.
2 Methodology
2.1 Development Environment
2.1.1 Hardware
The hardware used for our designs is a Nallatech Ballyneuy 2 Virtex PCI card. It houses the Virtex XCV800 Field Programmable Gate Array (FPGA), which was used to run our oscillator ring designs. The FPGA uses look up tables (LUTs) to simulate function generators. These LUTs require current and voltage to function. Floorplanning was used to minimize any electric field effects by placing high frequency components as far apart as possible on the board.
2.1.2 Software Design Flow
The Exceed program was used to access the following tools used: Modelsim, Synopsys FPGA Compiler II, Xilinx Floorplanner, and Xilinx Design Manager. The design flow used is shown in Figure 2. The VHDL design is first loaded into the FPGA compiler. The FPGA compiler creates a design hierarchy for the Virtex FPGA. The Pin Constraints is the ucf file used for pin to signal assignments. The floorplanner is run to create a layout for where the components are to be placed physically on the Virtex chip. This design is then loaded into the Xilinx Design Manager, where by translating the design constraints, a bit file is produced. A C program is then used to upload the bit file to the FPGA to the PCI board.
Figure 2: Design Flow
2.2 Testing Environment and Procedures
2.2.1 Jitter Measurement
In order to gain a better understanding of jitter, it is important to first quantify it. Although jitter has seen a fair share of attention in recent times as it has become increasingly problematic for high-speed communications design, much of the investigation conducted upon it has sought to minimize its impact on circuit designs. Many of the tools and methods for measuring jitter and its effects reflect this and are more concerned with its effects than its underlying causes. For this reason, only a few techniques are of interest to the topic being investigated in this paper.
Figure 3: Jitter Measurement Techniques [3]
Period
Because jitter events are directly manifested as changes in a signal’s period, measuring these variations in the period is a good way to gauge the effects of these events. Period jitter measurements consist simply of taking repeated measurements of the signal’s period (either from one rising edge to the next or one falling edge to the next, but rising is generally preferred) and compiling the data to obtain statistical results. Although the standard deviation is typically the most interesting numerical result, the mean of the period can also be useful for determining an idealized waveform. The distribution of these results is typically assumed to be normal and a histogram can confirm this visually.
Cycle-Cycle
Cycle to cycle (or cycle-cycle) jitter is another measurement built upon the basic period measurement. Through the application of a first-order difference equation on the period measurements the differences between adjacent cycles can be calculated. These differences can show the actual amount of phase-shift caused by jitter events on a per-cycle basis. Since this is a difference function applied to what should be a normally distributed dataset, its mean should be zero, or very close thereto. Its standard deviation is generally the only result of interest, although plotting cycle-cycle jitter versus time (typically done on a per-cycle scale) can yield interesting results about the period growing consistently longer or shorter for spans of time.
Time Interval Error (TIE)
While not able to be directly observed, time interval error provides some useful information about the results of jitter events on a signal. The measurement technique requires an idealized clock signal for comparison against the measured signal, making it impossible to directly observe due to the lack of physical jitter-less clock circuits. However, it is possible to compute the TIE via post-processing by subtracting the ideal clock period (determined through measurement) from each period measurement and then integrating the differences [3]. Although it does require post-processing, several jitter-related applications for commercial oscilloscopes are able to compute the TIE from data as it is collected. The TIE can be used to observe the cumulative effects of jitter over time, and when plotted versus time it can show deterministic modulation on the signal’s phase. Because it is based upon differences from the ideal, the TIE should have a mean of zero, or something close thereto. Additionally, the histogram of TIE data can show the distribution of deviations from the idealized signal to help identify whether the measured signal is biased towards being slow or fast.
N-Cycle
In order to investigate the accumulated effects of jitter events it is necessary to utilize a so-called ‘N-cycle’ jitter measurement technique. This technique again relies upon a form of idealized clock period, however instead of calculating for every period like the TIE, it waits for N-cycles of the signal and measures the difference between the expected Nth-cycle rising edge and the actual rising edge. As with TIE measurement, commercial jitter-measurement applications are able to calculate N-cycle measurements on data as it is collected. The standard deviation of these results is useful to examine the effects of this accumulation, as well as viewing the histogram to investigate the distribution it generates. As with the TIE, N-cycle jitter distributions should be centered about a mean at or near zero.
Data Captures and Post-Processing
Although much of the data relevant to measuring jitter can be collected directly through oscilloscopes and jitter measurement software packages for them, for the purposes of this paper it was desirable to investigate other aspects of jitter not typically measured in industrial design. It was necessary to use an oscilloscope to save waveform capture data that could be appropriately post-processed to analyze these aspects.
2.2.2 Oscilloscope
The oscilloscope used was a Tektronix 5104B. The sampling rate is 5 Gigasamples per second. Most of the measurements taken used the TDSJITv3 software. The period and standard deviation of the period measurements were taken by acquiring data from one million waveform captures. The scope measures the period between rising edges of the waveform. The ideal period for the TIE measurements was synthesized by the software through clock recovery. Clock recovery is performed by averaging the period for the waveform and then using the mean of the period to fit the clock to the measured data. Another source of data extracted from the TIE measurement is the random and deterministic jitter (Rj/Dj) analysis performed by the software. The TDSJIT3 software decomposes the total jitter into deterministic and random components. It does this analysis by using an industry-standard technique involving deconvolving the distribution for the total jitter. This is done by assuming the random jitter uses a Gaussian distribution [7]. The software was also used to calculate the N-cycle jitter. The software first calculates the ideal N-cycle period and compares it to the time between the first measured clock edge and the Nth clock edge. The difference is the result of the N-cycle measurement.