A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks
|
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.
[1] 109 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.
[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.
[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.
[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, http://stat.fsu.edu~geo, 1996.
[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 ,” http://www.win.tue.nl/~aebvoorlincod.html .
[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.
[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.
[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.
[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.
Index Terms:
True (and pseudo) random number generators, resilient functions, cryptography.
Citation:
Berk Sunar, William J. Martin, Douglas R. Stinson, "A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks," IEEE Transactions on Computers, vol. 56, no. 1, pp. 109-119, Jan. 2007, doi:10.1109/TC.2007.4
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb