research-article

Beat Frequency Detector--Based High-Speed True Random Number Generators: Statistical Modeling and Analysis

Authors:

Yingjie Lao,

Qianying Tang,

Chris H. Kim,

Keshab K. ParhiAuthors Info & Claims

ACM Journal on Emerging Technologies in Computing Systems (JETC), Volume 13, Issue 1

Article No.: 9, Pages 1 - 25

https://doi.org/10.1145/2866574

Published: 13 April 2016 Publication History

Get Access

Abstract

True random number generators (TRNGs) are crucial components for the security of cryptographic systems. In contrast to pseudo--random number generators (PRNGs), TRNGs provide higher security by extracting randomness from physical phenomena. To evaluate a TRNG, statistical properties of the circuit model and raw bitstream should be studied. In this article, a model for the beat frequency detector--based high-speed TRNG (BFD-TRNG) is proposed. The parameters of the model are extracted from the experimental data of a test chip. A statistical analysis of the proposed model is carried out to derive mean and variance of the counter values of the TRNG. Our statistical analysis results show that mean of the counter values is inversely proportional to the frequency difference of the two ring oscillators (ROSCs), whereas the dynamic range of the counter values increases linearly with standard deviation of environmental noise and decreases with increase of the frequency difference. Without the measurements from the test data, a model cannot be created; similarly, without a model, performance of a TRNG cannot be predicted. The key contribution of the proposed approach lies in fitting the model to measured data and the ability to use the model to predict performance of BFD-TRNGs that have not been fabricated. Several novel alternate BFD-TRNG architectures are also proposed; these include parallel BFD, cascade BFD, and parallel-cascade BFD. These TRNGs are analyzed using the proposed model, and it is shown that the parallel BFD structure requires less area per bit, whereas the cascade BFD structure has a larger dynamic range while maintaining the same mean of the counter values as the original BFD-TRNG. It is shown that 3.25M and 4M random bits can be obtained per counter value from parallel BFD and parallel-cascade BFD, respectively, where M counter values are computed in parallel. Furthermore, the statistical analysis results illustrate that BFD-TRNGs have better randomness and less cost per bit than other existing ROSC-TRNG designs. For example, it is shown that BFD-TRNGs accumulate 150% more jitter than the original two-oscillator TRNG and that parallel BFD-TRNGs require one-third power and one-half area for same number of random bits for a specified period.

References

[1]

Brian J. Abcunas. 2004. Evaluation of Random Number Generators on FPGAs. Ph.D. Dissertation. Worcester Polytechnic Institute.

Google Scholar

[2]

Asad A. Abidi. 2006. Phase noise and jitter in CMOS ring oscillators. IEEE Journal of Solid-State Circuits 41, 8, 1803--1816.

Crossref

Google Scholar

[3]

Takehiko Amaki, Masanori Hashimoto, and Takao Onoye. 2013. Jitter amplifier for oscillator-based true random number generator. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 96, 3, 684--696.

Crossref

Google Scholar

[4]

Ganesh K. Balachandran and Raymond E. Barnett. 2008. A 440-nA true random number generator for passive RFID tags. IEEE Transactions on Circuits and Systems I: Regular Papers 55, 11, 3723--3732.

Crossref

Google Scholar

[5]

Mathieu Baudet, David Lubicz, Julien Micolod, and André Tassiaux. 2011. On the security of oscillator-based random number generators. Journal of Cryptology 24, 2, 398--425.

Digital Library

Google Scholar

[6]

Nathalie Bochard, Florent Bernard, and Viktor Fischer. 2009. Observing the randomness in RO-based TRNG. In Proceedings of the International Conference on Reconfigurable Computing and FPGAs. 237--242.

Digital Library

Google Scholar

[7]

Holger Bock, Marco Bucci, and Raimondo Luzzi. 2004. An offset-compensated oscillator-based random bit source for security applications. In Proceedings of the Conference on Cryptographic Hardware and Embedded Systems (CHES’04). 268--281.

Crossref

Google Scholar

[8]

Ralf Brederlow, Ramesh Prakash, Christian Paulus, and Roland Thewes. 2006. A low-power true random number generator using random telegraph noise of single oxide-traps. In Proceedings of the IEEE International Solid-State Circuits Conference. 1666--1675.

Crossref

Google Scholar

[9]

Marco Bucci, Lucia Germani, Raimondo Luzzi, Alessandro Trifiletti, and Mario Varanonuovo. 2003. A high-speed oscillator-based truly random number source for cryptographic applications on a smart card IC. IEEE Transactions on Computers 52, 4, 403--409.

Digital Library

Google Scholar

[10]

Marco Bucci and Raimondo Luzzi. 2008. Fully digital random bit generators for cryptographic applications. IEEE Transactions on Circuits and Systems I: Regular Papers 55, 3, 861--875.

Crossref

Google Scholar

[11]

Wayne R. Coppock. 2005. A Mathematical and Physical Analysis of Circuit Jitter with Application to Cryptographic Random Bit Generation. Ph.D. Dissertation. Worcester Polytechnic Institute.

Google Scholar

[12]

Markus Dichtl. 2007. Bad and good ways of post-processing biased physical random numbers. In Proceedings of the Conference on Fast Software Encryption. 137--152.

Digital Library

Google Scholar

[13]

Markus Dichtl and Jovan Dj Golić. 2007. High-Speed True Random Number Generation with Logic Gates Only. Springer.

Google Scholar

[14]

Michael Epstein, Laszlo Hars, Raymond Krasinski, Martin Rosner, and Hao Zheng. 2003. Design and implementation of a true random number generator based on digital circuit artifacts. In Proceedings of the Conference on Cryptographic Hardware and Embedded Systems (CHES’03). 152--165.

Crossref

Google Scholar

[15]

Viktor Fischer, Florent Bernard, Nathalie Bochard, and Michal Varchola. 2008. Enhancing security of ring oscillator-based TRNG implemented in FPGA. In Proceedings of the International Conference on Field Programmable Logic and Applications. 245--250.

Crossref

Google Scholar

[16]

Daniel E. Holcomb, Wayne P. Burleson, and Kevin Fu. 2007. Initial SRAM state as a fingerprint and source of true random numbers for RFID tags. In Proceedings of the Conference on RFID Security, Vol. 7.

Google Scholar

[17]

Wolfgang Killmann and Werner Schindler. 2001. AIS 31: Functionality Classes and Evaluation Methodology for True (Physical) Random Number Generators, Version 3.1. Bundesamt fur Sicherheit in der Informationstechnik (BSI).

Google Scholar

[18]

Tae-Hyoung Kim, Randy Persaud, and Chris H. Kim. 2008. Silicon odometer: An on-chip reliability monitor for measuring frequency degradation of digital circuits. IEEE Journal of Solid-State Circuits 43, 4, 874--880.

Crossref

Google Scholar

[19]

Paul Kohlbrenner and Kris Gaj. 2004. An embedded true random number generator for FPGAs. In Proceedings of the 2004 ACM/SIGDA 12th International Symposium on Field Programmable Gate Arrays. 71--78.

Digital Library

Google Scholar

[20]

Patrick Lacharme. 2008. Post-processing functions for a biased physical random number generator. In Proceedings of the Conference on Fast Software Encryption. 334--342.

Digital Library

Google Scholar

[21]

J. S. Liberty, A Barrera, D. W. Boerstler, T. B. Chadwick, S. R. Cottier, H. P. Hofstee, J. A. Rosser, and M. L. Tsai. 2013. True hardware random number generation implemented in the 32-nm SOI POWER7+ processor. IBM Journal of Research and Development 57, 6, 4:1--4:7.

Digital Library

Google Scholar

[22]

Mehrdad Majzoobi, Farinaz Koushanfar, and Srinivas Devadas. 2011. FPGA-based true random number generation using circuit metastability with adaptive feedback control. In Proceedings of the Conference on Cryptographic Hardware and Embedded Systems (CHES’11). 17--32.

Digital Library

Google Scholar

[23]

George Marsaglia. 1996. DIEHARD: A Battery of Tests of Randomness. Available at http://stat.fsu.edu/pub/diehard/ 1995.

Google Scholar

[24]

Craig S. Petrie and J. Alvin Connelly. 1996. Modeling and simulation of oscillator-based random number generators. In Proceedings of the IEEE International Symposium on Circuits and Systems, Vol. 4. 324--327.

Google Scholar

[25]

Craig S. Petrie and J. Alvin Connelly. 1998. A noise-based random bit generator IC for applications in cryptography. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’98), Vol. 2. 197--200.

Google Scholar

[26]

Craig S. Petrie and J. Alvin Connelly. 2000. A noise-based IC random number generator for applications in cryptography. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 47, 5, 615--621.

Crossref

Google Scholar

[27]

Md. Tauhidur Rahman, Kan Xiao, Domenic Forte, Xuhei Zhang, Jerry Shi, and Mohammad Tehranipoor. 2014. TI-TRNG: Technology independent true random number generator. In Proceedings of the 51st Annual Design Automation Conference (DAC’14). 1--6.

Digital Library

Google Scholar

[28]

Vladimir Rozic and Ingrid Verbauwhede. 2009. Random numbers generation: Investigation of narrowtransitions suppression on FPGA. In Proceedings of the International Conference on Field Programmable Logic and Applications. 699--702.

Crossref

Google Scholar

[29]

Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, and Elaine Barker. 2001. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Technical Report. DTIC Document.

Crossref

Google Scholar

[30]

Werner Schindler. 2003. A stochastical model and its analysis for a physical random number generator presented at CHES 2002. In Cryptography and Coding. Lecture Notes in Computer Science, Vol. 2898. Springer, 276--289.

Crossref

Google Scholar

[31]

Suresh Srinivasan, Sanu Mathew, Rajaraman Ramanarayanan, Farhana Sheikh, Mark Anders, Himanshu Kaul, Vasantha Erraguntla, Ram Krishnamurthy, and Greg Taylor. 2010. 2.4 GHz 7mW all-digital PVT-variation tolerant true random number generator in 45nm CMOS. In Proceedings of the IEEE Symposium on VLSI Circuits (VLSIC’10). 203--204.

Google Scholar

[32]

Alan Stuart and J. Keith Ord. 1994. Kendall’s Advanced Theory of Statistics: Distribution Theory. Vol. I. Arnold, London, England.

Google Scholar

[33]

Berk Sunar, William J. Martin, and Douglas R. Stinson. 2007. A provably secure true random number generator with built-in tolerance to active attacks. IEEE Transactions on Computers 56, 1, 109--119.

Digital Library

Google Scholar

[34]

Qianying Tang, Bongjin Kim, Yingjie Lao, Keshab K. Parhi, and Chris H. Kim. 2014. True random number generator circuits based on single- and multi-phase beat frequency detection. In Proceedings of the IEEE Customs Integrated Circuits Conference. 1--4.

Google Scholar

[35]

Qianying Tang, Xiaofei Wang, John Keane, and Chris H. Kim. 2013. RTN induced frequency shift measurements using a ring oscillator based circuit. In Proceedings of the Symposium on VLSI Technology. T188--T189.

Google Scholar

[36]

Carlos Tokunaga, David Blaauw, and Trevor Mudge. 2008. True random number generator with a metastability-based quality control. IEEE Journal of Solid-State Circuits 43, 1, 78--85.

Crossref

Google Scholar

[37]

Boyan Valtchanov, Viktor Fischer, Alain Aubert, and Florent Bernard. 2009. TRNG based on the coherent sampling. In Proceedings of the 3rd International Conference on Signals, Circuits, and Systems (SCS’09). 1--6.

Google Scholar

[38]

John Von Neumann. 1951. Various techniques used in connection with random digits. Applied Math Series 12, 36-38, 1.

Google Scholar

[39]

Knut Wold. 2011. Security Properties of a Class of True Random Number Generators in Programmable Logic. Ph.D. Dissertation. Gjovik University College.

Google Scholar

[40]

Knut Wold and Chik How Tan. 2009. Analysis and enhancement of random number generator in FPGA based on oscillator rings. International Journal of Reconfigurable Computing 2009, Article No. 4.

Digital Library

Google Scholar

[41]

Kaiyuan Yang, David Fick, Michael B. Henry, Yoonmyung Lee, David Blaauw, and Dennis Sylvester. 2014. A 23Mb/s 23pJ/b fully synthesized true-random-number generator in 28nm and 65nm CMOS. In Proceedings of the IEEE International Solid-State Circuits Conference Digest of Technical Papers. 280--281.

Crossref

Google Scholar

Cited By

View all

Fujieda NTakashima S(2021)An MMCM-based high-speed true random number generator for Xilinx FPGAInternational Journal of Networking and Computing10.15803/ijnc.11.2_15411:2(154-171)Online publication date: 2021
https://doi.org/10.15803/ijnc.11.2_154
Fujieda N(2020)On the Feasibility of TERO-Based True Random Number Generator on Xilinx FPGAs2020 30th International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL50879.2020.00027(103-108)Online publication date: Aug-2020
https://doi.org/10.1109/FPL50879.2020.00027
Fujieda NTakashima S(2020)Enhanced use of mixed-mode clock manager for coherent sampling-based true random number generator2020 Eighth International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW51189.2020.00047(197-203)Online publication date: Nov-2020
https://doi.org/10.1109/CANDARW51189.2020.00047
Show More Cited By

Index Terms

Beat Frequency Detector--Based High-Speed True Random Number Generators: Statistical Modeling and Analysis
1. Hardware
  1. Integrated circuits

Recommendations

Next generation QCA technology based true random number generator for cryptographic applications
Abstract
The penchant for almost all modern-day devices is high data and communication security. To achieve the highest standard of security, hardware-based encryption architectures like true random number generators (TRNG) and physically ...
True Random Number Generator Based on Ring Oscillator PUFs
ICMSSP 2017: Proceedings of the 2017 2nd International Conference on Multimedia Systems and Signal Processing

Random number generator is an important building block for many cryptographic primitives and protocols. Random numbers are used to initialize key bits, nonces and initialization vectors and seed pseudo-random number generators. Physical Unclonable ...
Multi-bit per cycle true random number generator based on XOR-XNOR ring oscillator unit
Abstract
To achieve a fast and resource-efficient entropy source, we present a novel oscillator unit, called XOR-XNOR ring oscillator (XXRO) which consists of an XOR gate and an XNOR gate. The XXRO unit has an internal feedback loop that allows the ...

Reviews

Reviewer: Xinfei Guo

With the increased number of personal electronic devices, the security of these devices and personal information has become a big concern. As effective solutions to securing a system, encryption and the signing of confidential information with digital key streams have been widely used. These digital key streams are usually generated by random number generators (RNGs), which can be classified into true random number generators (TRNGs) and pseudo-random number generators (PRNGs). The difference is that TRNGs derive randomness from analog physical processes, such as thermal noise, voltage noise, and so on; PRNGs derive randomness from computational complexity, which is decided by the seed. This paper focuses on TRNGs, which are usually used in systems requiring a high level of security. The mechanism behind the on-chip TRNGs is that the circuit converts all of the transistor-level randomness (like random telegraph noise, flicker noise, and thermal noise) into voltage or delay signals. A ring oscillator is one of the best-fitting circuits for this purpose; it is simple to build and also easy to control. Most importantly, it can capture noise accurately. Although designing a ring oscillator is easy, the challenge of such a TRNG is how to evaluate it. To make it clearer, since TRNGs deal with randomness, which is really hard to predict and verify, it is very hard to evaluate and test TRNGs. In this paper, Lao et al. provide a comprehensive study of the randomness of different variation sources, and propose a model for beat frequency detector-based high-speed TRNGs (BFD-TRNGs). The model is calibrated against the actual measurement. According to the paper, "the key contribution of the proposed approach lies in fitting the model to measured data and the ability to use the model to predict performance of BFD-TRNGs that have not been fabricated." Based on the proposed model, the authors also present several novel designs of BFD-TRNGs, such as parallel BFD based, cascade BFD based, and a combination of both. The paper compares the pros and cons of each and also validates the model. This paper provides a very useful TRNG model for researchers working in the hardware security area. Also, the comparison study of different TRNGs will guide researchers to pick the right one to satisfy different requirements and metric budgets. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Journal on Emerging Technologies in Computing Systems

ACM Journal on Emerging Technologies in Computing Systems Volume 13, Issue 1

Special Issue on Secure and Trustworthy Computing

January 2017

208 pages

ISSN:1550-4832

EISSN:1550-4840

DOI:10.1145/2917757

Editor:
Yuan Xie
University of California, Santa Barbara, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 13 April 2016

Accepted: 01 December 2015

Revised: 01 October 2015

Received: 01 October 2014

Published in JETC Volume 13, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation
Semiconductor Research Corporation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
353
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fujieda NTakashima S(2021)An MMCM-based high-speed true random number generator for Xilinx FPGAInternational Journal of Networking and Computing10.15803/ijnc.11.2_15411:2(154-171)Online publication date: 2021
https://doi.org/10.15803/ijnc.11.2_154
Fujieda N(2020)On the Feasibility of TERO-Based True Random Number Generator on Xilinx FPGAs2020 30th International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL50879.2020.00027(103-108)Online publication date: Aug-2020
https://doi.org/10.1109/FPL50879.2020.00027
Fujieda NTakashima S(2020)Enhanced use of mixed-mode clock manager for coherent sampling-based true random number generator2020 Eighth International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW51189.2020.00047(197-203)Online publication date: Nov-2020
https://doi.org/10.1109/CANDARW51189.2020.00047
Perach Bkvatinsky s(2019)An Asynchronous and Low-Power True Random Number Generator Using STT-MTJIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2019.292781627:11(2473-2484)Online publication date: Nov-2019
https://doi.org/10.1109/TVLSI.2019.2927816
Koyily AAvvaru SZhou CKim CParhi KShin Y(2018)Effect of aging on linear and nonlinear MUX PUFs by statistical modelingProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201625(76-83)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201625
Govindaraj RGhosh SKatkoori S(2018)CSRO-Based Reconfigurable True Random Number Generator Using RRAMIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2018.282327426:12(2661-2670)Online publication date: Dec-2018
https://doi.org/10.1109/TVLSI.2018.2823274
Koyily AAvvaru SZhou CKim CParhi K(2018)Effect of aging on linear and nonlinear MUX PUFs by statistical modeling2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2018.8297286(76-83)Online publication date: Jan-2018
https://doi.org/10.1109/ASPDAC.2018.8297286
Govindan VChakraborty RSantikellur PChaudhary A(2018)A Hardware Trojan Attack on FPGA-Based Cryptographic Key Generation: Impact and DetectionJournal of Hardware and Systems Security10.1007/s41635-018-0042-52:3(225-239)Online publication date: 20-Jun-2018
https://doi.org/10.1007/s41635-018-0042-5

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Next generation QCA technology based true random number generator for cryptographic applications

True Random Number Generator Based on Ring Oscillator PUFs

Multi-bit per cycle true random number generator based on XOR-XNOR ring oscillator unit

Reviews

Access critical reviews of Computing literature here

Comments

Published In

Publisher

Journal Family

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Next generation QCA technology based true random number generator for cryptographic applications

True Random Number Generator Based on Ring Oscillator PUFs

Multi-bit per cycle true random number generator based on XOR-XNOR ring oscillator unit

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Journal Family

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations