Auto-calibrated ring oscillator TRNG based on jitter accumulation

Depósito de investigación de la Universidad de Sevilla https://idus.us.es/ This is an Accepted Manuscript of an article published by IEEE in IEEE International Symposium on Circuits and Systems on 28 September 2020, available at: https://doi.org/10.1109/ISCAS45731.2020.9180598 “© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other Works” Auto-Calibrated Ring Oscillator TRNG based on Jitter Accumulation Miguel A. Prada-Delgado IBM Research - Zurich IBM Switzerland AG Rüschlikon, Switzerland [email protected]m.com Cristina Martínez-Gómez IMSE-CNM University of Seville, CSIC Seville, Spain [email protected] Iluminada Baturone IMSE-CNM University of Seville, CSIC Seville, Spain [email protected]ic.es Abstract—This paper provides a mathematical model that describes how deterministic and Gaussian jitter of an oscillating signal accumulated during a time interval are related to the bits of the binary-coded count value of the oscillations. The model is employed to propose a robust TRNG that has a simple interface (an initialization signal as input and the random bits as output) and that features auto-calibration to certify high entropy of the raw bits provided as well as to work at the highest throughput allowed by the available local Gaussian noise. The mathematical analysis is confirmed with experimental results of ring oscillator (RO) TRNGs described in VHDL and implemented in the programmable logic of Zynq family Xilinx FPGAs, using either another RO or the clock of the FPGA board to control the time interval of oscillations. Keywords— TRNG, ring oscillator, jitter, calibration I. INTRODUCTION True Random Number Generators (TRNGs) are typical building blocks of cryptographic systems. They harvest entropy from physical noise sources and provide unpredictable seeds. Many digital implementations of TRNGs reported in literature employ metastable circuits and oscillators. Comparatively, the latter provide higher entropy with simpler designs, although at a slower speed. However, such speed can be enough for many applications. Among oscillators, ring oscillators (RO) are widely employed. They are constructed with an odd number of inverters connected in cascade and forming a closed-loop, which makes them oscillate freely when enabled [1]-[2]. The entropy exploited by a TRNG must be certified to fulfill quality criteria. For that purpose, a mathematical model is required to describe how random bits are generated, and the raw bit strings should pass statistical tests performed off-line or on-line [3]-[4]. In addition, the TRNG should be robust against attacks that could modify its performance and the noise source. Hence, the only input of the TRNG should be its initialization signal, and the only output, the random bits. In this sense, it is not secure that the TRNG could be calibrated from outside but it should feature auto-calibration. Most of RO TRNGs use the jitter of the oscillating signal generated as a source of randomness. Some of them sample instantaneous jitter and others, accumulated jitter. The first ones compensate the influence of deterministic variations by more or less complex post-processing stages. However, they are prone to be targeted by attacks, particularly injection attacks at power supply [5]. Hence, this paper focuses on the second ones. Recent proposals that employ accumulated jitter are based on the principle of beat frequency detection (BFD) [6]-[7]. Using a pair of ROs (one slightly faster than the other), BFD-based TRNGs digitize (by using a counter) the quotient between the frequency of the slowest RO and the difference in frequencies of both ROs, and take the least significant bits (LSBs) of the counter as random bits. Calibration techniques are proposed in [6]-[7] to select the pair of ROs adequately. The problem is that those proposals extract entropy from random variations in the manufacturing (or programming) process of the TRNG circuit, which usually dominates over the internal semiconductor noise. That entropy is suitable to generate unique (and true random) circuit identifiers as physical unclonable functions (PUFs) do, but it is not adequate to produce true random sequences whenever they are employed, because they repeat the identifying output sequences. Besides, they use Von Neumann correction to post-process the bits in order to pass statistical tests successfully. Another proposal that employs accumulated jitter is reported in [8]. It uses a pair of ROs whose oscillations are counted simultaneously by two counters, which is the same structure employed in RO PUFs. The ROs are stopped when one of the counters overflows. The LSBs of the counter that does not overflow are used to generate random sequences after being post-processed by Von Neumann or XOR correction. The authors do not propose any calibration technique to select the pair of ROs and the size of the counters. Moreover, they do not explain mathematically how many LSBs are adequate to generate true random sequences. This paper explains with a mathematical model: (a) how the influence of deterministic and Gaussian variations in the accumulated jitter can be measured by counting the oscillations of an RO during a reference time; (b) that the given reference time, which is the unique parameter to select in the design, can be determined by a simple auto-calibration step; and (c) that using a theoretically identical RO to measure the given reference time is better than using other kind of timers, not only to exploit the same structure as RO PUF, as presented in [8], but also to ease auto-calibration. The paper is organized as follows. Section II describes the TRNG and its mathematical model. Section III proposes an auto calibration step based on evaluating the standard deviation of the counter results. In Section IV, experimental results confirm the mathematical and the auto calibration model proposed in the previous sections. Finally, conclusions and future work are exposed in Section V. II. TRNG PROPOSAL A. Description of the TRNG The core of a simple TRNG based on jitter accumulation is made of two oscillators,  and  , and two counters, as shown in Fig. 1. When the core is activated (the signal  is ‘1’), both oscillators oscillate simultaneously and stop when the counter of  reaches a given value . Then, a given number, , of LSBs of the counter of  are taken to generate the random bit sequence. If the oscillation frequency of  is  (  = 1/), the time to generate the  bits is  =  = ∙ (1) The core should be activated  times to generate ∙ bits. The objective of the calibration step is to determine the value of  so as to obtain m=1 random bit every , since that case optimizes the TRNG throughput, as will be seen in the following. Of course, several oscillators  can be employed in parallel to increase the throughput further. B. TRNG Mathematical Model If the oscillation frequency of  is  (=1/), its counter reaches the following value after  = ∙= ∙ ∙ (2) The period of an oscillator can be modelled as [9] = +∆ +∆ +∆ +∆ = +∆ (3) where  is the nominal period due to the oscillator configuration (for example, if it is a RO made of 3 theoretically identical inverters, its nominal period is 6 times the delay of an inverter), ∆is the jitter due to global and deterministic causes such as changes in temperature or global power supply nominal values, ∆is the jitter caused by local and deterministic causes due to the location of the oscillator within the system (for example, the variations in the manufacturing process produce different oscillation frequencies in ROs [10], and the voltage seen by the oscillator is the global supply voltage minus the IR-drop and di/dt-drop, which changes across the chip due to the transition activity of the surrounding circuitry [11]), ∆is the jitter due to global Gaussian variations that come from inside (e.g. from the substrate) or outside the device (e.g. power supply noise or electromagnetic interference signals), and ∆is the jitter due to local Gaussian variations caused by noise generated in semiconductors. Hence, the frequency of an oscillator can be modelled as =  ∆≅ −∆ = ∙󰇡1−∆ 󰇢= ∙(1−) (4) Substituting  by (3) and  by (4) in (2), it follows that =  ∙ ∙(1+∆ )∙∙(1−∆ ) (5) which can be approximated as =  ∙  ∙(1+∆  −∆ )=  ∙  ∙(1+−) (6) If  is a precise clock generator (for example the clock of the system), which features a negligible jitter, so that ∆ ≅0, the value of  is =󰇿  ∙  ∙(1−∆ +∆ +∆ +∆ )󰈀=  ∙  ∙(1−  −  −  − ) (7) Instead, if  is theoretically identical to  (for example they are both ROs, like in a RO PUF), so that  =  and  = , the value of  is =󰇿  ∙(1+∆ ∆ +∆  ∆ +∆ ∆ + ∆  ∆ )󰈀= ∙(1+  +  +  +  ) (8) Three main terms can be seen in the expressions (7) and (8) above: the nominal count value, the count due to deterministic variations, and the count due to Gaussian variations. They are shown in Table I, where the realization in (7) is referred to as CLK for , and the realization in (8), as RO for . III. AUTO-CALIBRATION From all the above commented variations, the global deterministic variations are the most harmful for a TRNG, since they are not random and can be injected from outside the TRNG, perturbing its performance. Local deterministic variations are mainly associated with the PUF nature of the realization. As commented in [6]-[7], they are in the range of 0.2% to 0.5%, depending on the manufacturing process variations. Therefore, their influence appears in count values greater than 10.005 =200 to 10.002 =500 , which means from the 9th or 10th MSB in the count value of the  counter. Once the circuit is manufactured or programmed in the case of FPGAs, these variations do not change over time so that they can be considered as a constant contribution to the count value. The local Gaussian variations are the best as physical source of noise for a TRNG, since they are random and cannot be modified from outside. They depend mainly on the technology. As commented in [8] and [10], these variations are one order of magnitude inferior to local deterministic Fig. 1. Block diagram of the TRNG core. TABLE I. MAIN CONTRIBUTIONS TO COUNT VALUES  Nominal Deterministic Gaussian CLK  = ∙   ∙(  + )  ∙  RO   ∙(  +  )  ∙  ones. For example, it is reported in [2] that Spartan 6 and Cyclone V FPGA families feature variations in the range of 0.05%. Such influence would appear in count values greater than 10.0005 =2000, which means from the 12th MSB in the count value of the  counter. In these cases, the bits in the counter associated with deterministic and random variations are separated. However, it is also reported in [2] that the SmartFusion 2 family features Gaussian variations in the range of 0.2%, which could be in the same range as deterministic variations, masking them. In the realization using the RO as , the Gaussian variations can be twice the variations with the CLK, since the noise of both oscillators are added. The proposed auto calibration step should be carried out in a controlled environment free of global variations, so that the distribution of sequentially measured count values can be modeled by a Gaussian distribution, since the local deterministic variations are practically constant and the variations are caused mainly by the local Gaussian noise. Hence, if   is the average of the count values and    is the relative standard deviations of the count values, and considering that 68.26% of the counted  are between  − and  +, the calibration step is based on measuring  to identify the at least m LSBs responsible of counting till  (>2−1), which are related to noise. With that information, the calibration reduces or increases the value of  accordingly. For example, if a  between 64 and 127 (which can be counted with 7 LSBs) is measured with a selected , the calibration step reduces (and, hence, the time ) by a factor of 2 to obtain 1 instead of 7 LSBs counting variations, thus increasing significantly the TRNG throughput. The calibration procedure to find the adequate  can use a binary search, as employed in [7]. If the calibration is performed in a non-controlled environment, the number of bits estimated from  can be also associated with global variations. In the realization using a RO, since the global deterministic variations are similar in both oscillators, ∆  ≅ ∆, they can be neutralized, making the term   very small. To take into account these small variations, the calibration step can determine  to obtain m>1 changing bits, to ensure that at least one of them measures Gaussian variations, at the cost of reducing the speed of the TRNG. This solution can be acceptable for the RO realization but not for the CLK realization, because in the latter, the global variations can be so much significant that the resulting calibrated TRNG can be very slow. IV. EXPERIMENTAL RESULTS Both realizations of the analyzed TRNG were described in VHDL and implemented in the Zedboard from Xilinx with the SoC XC7Z020-CLG484-1, using Vivado 2015.4. This SoC contains programmable logic where the ROs acting as  and the counters were implemented. In the CLK realization, the clock of the board was employed. In the RO realization, another RO was implemented. No place and route constraints were applied to implement the ROs so that the design is portable. The counters of the ROs were designed carefully so as to be able to count oscillations of ROs with only 1 inverter. The count values N of the TRNG are written in a block RAM. In the current design, those values are read by the ARM Cortex-A9 processor in the SoC to analyze them and to perform the calibration step that determines .Therefore, the calibration step is implemented in software. Of course, a more secure design is to implement the calibration also in programmable logic, thus reducing possible attacks from the processor. Several experiments were done with the board working at ambient temperature and the power supply provided by the regulator MAX15021 in the board, which is considered as a normal controlled environment for the calibration. After checking that the relative standard deviations of the count values N in several realizations were very similar, it was concluded that the local Gaussian noise can be estimated from them, as predicted by the model. The first 4 columns in Table II show the results of CLK realizations with ROs implemented with a different number of inverters. By measuring several ROs placed and routed randomly by Vivado in the FPGA, it was also checked they remained constant independently of local deterministic variations. For example, the 5th and 6th columns show the relative standard deviations measured for the slowest and the fastest ROs with 3 inverters (the result for the 2nd column correspond to another RO of medium speed with 3 inverters). The 8th column in Table II shows that the variations in the RO realization are approximately twice the variations with the CLK, as predicted by the mathematical model. Figure 2 shows how the histograms obtained with both realizations using a RO with 3 inverters follow a Gaussian distribution. Since variations in the power supply voltage value are the global variations that most influence the RO behavior, the Zedboard was altered to inject the voltage value directly to the programmable logic (PL), basically by disconnecting the regulator MAX15021. In this way, the nominal PL supply voltage of 1V was changed between the minimum (0.95V) and maximum (1.05V) values admitted by the SoC. The results shown in columns 7 and 9 in Table II confirm that global variations have smaller influence in the RO than in the CLK realization, as predicted by the model. To cope with the worst Vdd variations, the calibration step of the RO realization can determine that 5 LSBs counting variations should be provided to ensure that at least 1 is measuring true local noise. In the CLK realization, 8 LSBs can be provided to ensure 1, which is much less efficient. Several experiments were done to evaluate the effectiveness of the calibration step in a normal controlled environment. The bits of the count values N provided by both realizations were analyzed statistically with NIST tests. Besides, the minimum entropy of a bit j was measured in n sequences made of q times that bit, as follows , =− ∑   (9) TABLE II. RELATIVE STANDARD DEVIATIONS FOR SEVERAL TRNG CONFIGURATIONS CLK realization RO realization No Vdd variations Vdd variations No Vdd variations Vdd variations Relative standard deviation 1 inv. 3 inv. 7 inv. 15 inv. 3 inv. (slowest) 3 inv. (fastest) 3 inv. 3 inv. 3 inv. 0.03% 0.02% 0.03% 0.02% 0.02% 0.02% 4.89% 0.04% 0.50% where  is the maximum probability of the bit j taking logic value ’0’ or ’1’ in the q times, The results shown in Table III correspond to 103100 15- bit N values from both realizations, using ROs with 3 inverters, organized as 100 sequences of 1031 bit values for each bit of N so as to analyze the randomness of each bit. The calibration step in the CLK realization determined that 2 LSBs in the 15-bit N values were counting random variations, because the measured  was 3.66 (for  =18317). The calibration in the RO realization determined that 3 LSBs were random, because the measured  was 10.44 (for  =29600). The results in Table III confirm that the bits selected by the calibration (non-shadowed) passed the NIST Tests and provided high minimum entropy. The RO realization, calibrated to produce 1 LSB per measurement and using a 3-inverter RO of typical speed, provided a throughput of 200 Kb/s. Hence, a TRNG with 10 ROs oscillating in parallel (and another of reference) reaches a throughput of 2 Mb/s. The TRNG reported in [1] employed 110 ROs for a similar throughput. V. CONCLUSIONS AND FUTURE WORK An auto-calibrated TRNG made of two oscillators and two counters has been analyzed mathematically and verified experimentally in Zynq FPGAs. Using two theoretically identical ROs as oscillators is better for calibration. The calibration realized in a controlled environment with no power supply variations obtains the highest TRNG speed. Once calibrated, the TRNG is robust against attacks since the provided bits go on harvesting local Gaussian noise, which was estimated as 0.04%. The NIST tests were passed by the provided raw bits, without post-processing, and the minimum entropy provided per raw bit was greater than 96.6%. A throughput of 2 Mb/s can be obtained with 10 3- inverter ROs of typical speed oscillating in parallel, and another RO acting as timer. As future work, the calibration step will also be implemented in programmable logic. ACKNOWLEDGMENT This work was supported in part by the Projects TEC2017-83557-R (AEI/FEDER, UE) and RTC-2017-6595- 7 (AEI/FEDER, UE). REFERENCES [1] D. Schellekens, B. Preneel, and I. Verbauwhede, "FPGA vendor agnostic true random number generator," in Proc. FPL 2006, pp. 139- 144, 2006. [2] O. Petura, U. Mureddu, N. Bochard, V. Fischer, L. Bossuet, “A survey of AIS-20/31 compliant TRNG cores suitable for FPGA devices”, in Proc. FPL 2016. [3] A. Rukhin et al., “A statistical test suite for random and pseudorandom number generators for cryptographic applications,” NIST Special Publication 800-22-1a, 2010. [4] E. Barker and J. Kelsey, “Recommendation for the entropy sources used for random bit generation,” NIST Special Publication 800-90A, 2012. [5] P. Bayon, L. Bossuet, A. Aubert, V. Fischer, “Fault model of electromagnetic attacks targeting ring oscillator-based true random number generators”, Journ. Cryptogr. Eng., vol. 6, pp. 61-74, 2016. [6] A. P. Johnson, R. S. Chakraborty, and D. Mukhopadyay, “An improved DCM-based tunable true random number generator for Xilinx FPGA”, IEEE TCAS-II, vol. 64, pp. 452-456, 2017. [7] Q. Tang, B. Kim, Y. Lao, K. K. Parhi, and C. H. Kim, “True random number generator circuits based on single- and multi-phase beat frequency detection,” in Proc. IEEE Custom Integr. Circuits Conf., 2014, pp. 1–4. [8] S. Buchovecka, R. Lorencz, F. Kodytek, J. Bucek, “True random number generator based on ring oscillator PUF circuit”, Microprocessors and Microsystems, 53, pp. 33–41, 2017. [9] B. Valtchanov, A. Aubert, F. Bernard, V. Fischer, “Modeling and observing the jitter in ring oscillators implemented in FPGAs”, in Proc. 2008 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems. [10] A. Maiti, J. Casarona, L. McHale, and P. Schaumont, “A large scale characterization of RO-PUF”, in Proc. IEEE Int. Symp. on Hardware- Oriented Security and Trust (HOST), pp. 94–99, 2010. [11] A. Kumar and M. Anis, “IR-Drop management in FPGAs”, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, pp. 988–993, 2010. (a) (b) Fig. 2. Histograms of the counter values, N, in: (a) the CLK and (b) RO realizations. Rel. Std. Deviations are shown in percentage. TABLE III. NIST TEST RESULTS AND MINIMUM ENTROPY Position (LSB) 1 2 3 4 5 6 P-val/Proportion P-val Prop P-val Prop P-val Prop P-val Prop P-val Prop P-val Prop CLK Frequency 0.85 1.00 0.55 1.00 0.00 0.52 0.00 0.11 0.00 0.10 0.00 0.00 BlockFrequency 0.11 1.00 0.46 0.97 0.00 0.04 0.00 0.00 0.00 0.00 0.00 0.00 Cum. sums (fw) 0.38 1.00 0.44 1.00 0.00 0.42 0.00 0.00 0.00 0.00 0.00 0.00 Cum. sums (bw) 0.33 1.00 0.40 1.00 0.00 0.38 0.00 0.00 0.00 0.00 0.00 0.00 Runs 0.96 0.99 0.66 0.99 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 LongestRun 0.10 0.99 0.44 1.00 0.00 0.23 0.00 0.00 0.00 0.00 0.00 0.00 FFT 0.08 0.99 0.72 1.00 0.05 0.96 0.00 0.34 0.00 0.17 0.00 0.00 Minimum entropy 97.11% 97.22% 90.26% 46.42% 29.63% 0.04% RO Frequency 0.64 0.97 0.47 0.98 0.47 0.98 0.00 0.93 0.00 0.18 0.00 0.04 BlockFrequency 0.90 0.99 0.38 0.97 0.06 1.00 0.00 0.93 0.00 0.00 0.00 0.00 Cum. sums (fw) 0.96 0.97 0.90 0.97 0.42 0.98 0.00 0.93 0.00 0.08 0.00 0.02 Cum. sums (bw) 0.95 0.97 0.20 0.98 0.06 0.97 0.00 0.90 0.00 0.10 0.00 0.01 Runs 0.97 0.99 0.19 1.00 0.12 0.99 0.00 0.84 0.00 0.00 0.00 0.00 LongestRun 0.37 1.00 0.13 0.98 0.20 0.97 0.00 0.93 0.00 0.12 0.00 0.00 FFT 0.17 1.00 0.28 1.00 0.07 0.98 0.10 0.99 0.00 0.96 0.00 0.38 Minimum entropy 96.79% 97.02% 96.64% 95.45% 78.88% 47.04%