research-article

A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks

Authors:

William J. Martin,

Douglas R. StinsonAuthors Info & Claims

IEEE Transactions on Computers, Volume 56, Issue 1

Pages 109 - 119

Published: 01 January 2007 Publication History

Abstract

This paper is a contribution to the theory of true random number generators based on sampling phase jitter in oscillator rings. After discussing several misconceptions and apparently insurmountable obstacles, we propose a general model which, under mild assumptions, will generate provably random bits with some tolerance to adversarial manipulation and running in the megabit-per-second range. A key idea throughout the paper is the fill rate, which measures the fraction of the time domain in which the analog output signal is arguably random. Our study shows that an exponential increase in the number of oscillators is required to obtain a constant factor improvement in the fill rate. Yet, we overcome this problem by introducing a postprocessing step which consists of an application of an appropriate resilient function. These allow the designer to extract random samples only from a signal with only moderate fill rate and, therefore, many fewer oscillators than in other designs. Last, we develop fault-attack models and we employ the properties of resilient functions to withstand such attacks. All of our analysis is based on rigorous methods, enabling us to develop a framework in which we accurately quantify the performance and the degree of resilience of the design.

References

[1]

B. Barak, R. Shaltiel, and E. Tomer, “True Random Number Generators Secure in a Changing Environment,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '03), Ç.K. Koç and C.Paar, eds., pp. 166-180, 2003.

[2]

B. Abcunas, S.P. Coughlin, G. Pedro, and D.C. Reisberg, “Evaluation of RNGs Using FPGAs,” Worcester Polytechnic Inst., Major Qualifying Project Report, May 2004.

[3]

W.R. Coppock and C.R. Philbrook, “A Mathematical and Physical Analysis of Circuit Jitter with Application to Cryptographic Random Bit Generation,” Worcester Polytechnic Inst., Major Qualifying Project Report, Apr. 2005.

[4]

B. Jun and P. Kocher, “The Intel Random Number Generator,” white paper prepared for Intel Corp., Apr. 1999

[5]

R.A. Schulz, “Random Number Generator Circuit,” US Patent Number 4905176, Feb. 1990.

[6]

V. Bagini and M. Bucci, “A Design of Reliable True Random Number Generator for Cryptographic Applications,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '99), Ç.K.Koç and C. Paar, eds., pp. 204-218, 1999.

Digital Library

[7]

V. Fischer and M. Drutarovský, “True Random Number Generator Embedded in Reconfigurable Hardware,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '02), B.S.KaliskiJr., Ç.K. Koç, and C. Paar, eds., pp. 415-430, 2002.

Digital Library

[8]

T.E. Tkacik, “A Hardware Random Number Generator,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '02), B.S. Kaliski Jr., Ç.K. Koç, and C. Paar, eds., pp. 450-453, 2002.

Digital Library

[9]

C.J. Colbourn, J.H. Dinitz, and D.R. Stinson, “Applications of Combinatorial Designs to Communications, Cryptography and Networking,” Surveys in Combinatorics (Proc. 1999 British Combinatorial Conf.), pp. 37-100, 1999.

[10]

D.R. Stinson and K. Gopalakrishnan, “Applications of Designs to Cryptography,” CRC Handbook of Combinatorial Designs, C.D.Colbourn, and J.H. Dinitz, eds., CRC Press, 1996.

[11]

M. Epstein, L. Hars, R. Krasinski, M. Rosner, and H. Zheng, “Design and Implementation of a True Random Number Generator Based on Digital Circuit Artifacts,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '03), C.D.Walter, Ç.K. Koç, and C. Paar, eds., pp. 152-165, 2003.

[12]

G. Marsaglia, DIEHARD: A Battery of Tests of Randomness,

[13]

NIST Special Publication 800-22, “A Statistical Test Suite for Random and Pseudorandom Numbers,” Dec. 2000.

[14]

A.E. Brouwer, “Server for Bounds on the Minimum Distance of $q{\hbox{-}}\rm ary$ Linear Codes, q = 2,3,4,5,7,8,9,”

[15]

B. Chor, O. Goldreich, J. Håstad, J. Friedman, S. Rudich, and R. Smolensky, “The Bit Extraction Problem or $t{\hbox{-}}\rm Resilient$ Functions,” Proc. 26th IEEE Symp. Foundations of Computer Science, pp. 396-407, 1985.

Digital Library

[16]

M. Dichtl, “How to Predict the Output of a Hardware Random Number Generator,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '03), C.D. Walter, Ç.K. Koç, and C. Paar, eds., pp. 181-188, 2003.

[17]

W. Schindler, “A Stochastical Model and Its Analysis for a Physical Random Number Generator,” Proc. Cryptography and Coding '03, K.G. Paterson, ed., pp. 276-289, 2003.

[18]

W. Schindler and W. Killmann, “Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '02), B.S. Kaliski Jr., Ç.K. Koç, and C. Paar, eds., pp. 431-449, Aug. 2002.

Digital Library

[19]

M. Bucci and R. Luzzi, “Design of Testable Random Bit Generators,” Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES '05), J.R. Rao and B. Sunar, eds., pp. 131-146, Aug. 2005.

Digital Library

[20]

Anwendungshinweise und Interpretationen zum Schema (AIS), AIS 32, Version 1, Bundesamt fr Sicherheit in der Informationstechnik, 2001.

[21]

D. Schellekens, B. Preneel, and I. Verbauwhede, “FPGA Vendor Agnostic True Random Number Generator,” Proc. 16th Int'l Conf. Field Programmable Logic and Applications, to appear.

Cited By

Amirany AJafari KMoaiyeri M(2020)True Random Number Generator for Reliable Hardware Security Modules Based on a Neuromorphic Variation-Tolerant Spintronic StructureIEEE Transactions on Nanotechnology10.1109/TNANO.2020.303481819(784-791)Online publication date: 23-Nov-2020
https://dl.acm.org/doi/10.1109/TNANO.2020.3034818
Aldaghri NMahdavifar H(2020)Physical Layer Secret Key Generation in Static EnvironmentsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2020.297462115(2692-2705)Online publication date: 10-Mar-2020
https://dl.acm.org/doi/10.1109/TIFS.2020.2974621
Giechaskiel IRasmussen K(2020)Taxonomy and Challenges of Out-of-Band Signal Injection Attacks and DefensesIEEE Communications Surveys & Tutorials10.1109/COMST.2019.295285822:1(645-670)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1109/COMST.2019.2952858
Show More Cited By

Index Terms

A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks

Recommendations

An embedded true random number generator for FPGAs
FPGA '04: Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays

Field Programmable Gate Arrays (FPGAs) are an increasingly popular choice of platform for the implementation of cryptographic systems. Until recently, designers using FPGAs had less than optimal choices for a source of truly random bits. In this paper ...
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 ...
Secure true random number generator in WLAN/LAN
SIN '13: Proceedings of the 6th International Conference on Security of Information and Networks

Wireless networks need more security in comparison to the other networks due to their intrinsic vulnerabilities to possible attacks. It is expected that by using a distributed method for true random number generators (TRNG) in wireless sensor networks (...

Comments

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 56, Issue 1

January 2007

143 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amirany AJafari KMoaiyeri M(2020)True Random Number Generator for Reliable Hardware Security Modules Based on a Neuromorphic Variation-Tolerant Spintronic StructureIEEE Transactions on Nanotechnology10.1109/TNANO.2020.303481819(784-791)Online publication date: 23-Nov-2020
https://dl.acm.org/doi/10.1109/TNANO.2020.3034818
Aldaghri NMahdavifar H(2020)Physical Layer Secret Key Generation in Static EnvironmentsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2020.297462115(2692-2705)Online publication date: 10-Mar-2020
https://dl.acm.org/doi/10.1109/TIFS.2020.2974621
Giechaskiel IRasmussen K(2020)Taxonomy and Challenges of Out-of-Band Signal Injection Attacks and DefensesIEEE Communications Surveys & Tutorials10.1109/COMST.2019.295285822:1(645-670)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1109/COMST.2019.2952858
Sadhu ADas KDe DKanjilal M(2020)SSTRNG: self starved feedback SRAM based true random number generator using quantum cellular automataMicrosystem Technologies10.1007/s00542-019-04525-w26:7(2203-2215)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s00542-019-04525-w
Jin Cvan Dijk M(2019)Secure and Efficient Initialization and Authentication Protocols for SHIELDIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.264795016:1(156-173)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TDSC.2017.2647950
Bernard FHaddad PFischer VNicolai J(2019)From Physical to Stochastic Modeling of a TERO-Based TRNGJournal of Cryptology10.1007/s00145-018-9291-232:2(435-458)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00145-018-9291-2
Yang KForte DTehranipoor M(2018)ReSCACM Transactions on Design Automation of Electronic Systems10.1145/317485023:3(1-27)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1145/3174850
Rajagopalan SRethinam SArumugham SUpadhyay HRayappan JAmirtharajan R(2018)Networked hardware assisted key image and chaotic attractors for secure RGB image communicationMultimedia Tools and Applications10.1007/s11042-017-5566-077:18(23449-23482)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11042-017-5566-0
Wang FXi WHan JZhao KGao Y(2017)Security in Uplink MU-MIMO NetworksProceedings of the Second International Conference on Internet-of-Things Design and Implementation10.1145/3054977.3057325(351-352)Online publication date: 18-Apr-2017
https://dl.acm.org/doi/10.1145/3054977.3057325
Johnson APatranabis SChakraborty RMukhopadhyay D(2017)Remote dynamic partial reconfigurationMicroprocessors & Microsystems10.1016/j.micpro.2017.06.00552:C(131-144)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.micpro.2017.06.005
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents