An embedded true random number generator for FPGAs

ABSTRACT

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 we extend a technique that uses on-chip jitter and PLLs to a much larger class of FPGAs that do not contain PLLs. Our design uses only the Configurable Logic Blocks (CLBs) common to all FPGAs, and has a self-testing capability. Using the intrinsic jitter contained in digital circuits, we produce random bits at speeds of up to 0.5 Mbits/second with good statistical characteristics. We discuss the engineering challenges of extracting random bits from digital circuits, and we report the results of running standard statistical tests (NIST) on the output generated by our system.

REFERENCES

• 1: Chu, P., P., Jones, R., E., Design Techniques of FPGA Based Random Number Generator, Military and Aerospace Applications of Programmable Devices and Technologies Conference, The Johns Hopkins University- Applied Physics Laboratory, September 1999.
• 2: Cryptography Research Inc., Evaluation of VIA C3 Nehemiah Random Number Generator. Technical Report, Revision Dated: February 27,2003, Available at: http://www.cryptography.com/resources/whitepapers/index.html
• 3: Davies, R., Exclusive Or (XOR) and Hardware Random Number Generators. Feb 28, 2002, Available at: http://www.robertnz.net.
• 4: Eastlake, D., Crocker, S., Schiller, J., 1994. Randomness Recommendations for Security - RFC 1750, Available at: http://www.faqs.org.
• 5: Epstein, M., Hars, L., Krasinski, R., Rosner, M., Zheng, H., Design and Implementation of a True Random Number Generator Based on Digital Circuit Artifacts, Proceedings of the 5th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2003), Springer-Verlag, LNCS 2779 (2003).
• 6: R C Fairfield , R L Mortenson , K B Coulthart, An LSI random number generator (RNG), Proceedings of CRYPTO 84 on Advances in cryptology, p.203-230, August 1985, Santa Barbara, California, United States
• 7: Viktor Fischer , Milos Drutarovský, True Random Number Generator Embedded in Reconfigurable Hardware, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.415-430, August 13-15, 2002
• 8: Goldberg, I., Wagner, D., Randomness And the Netscape Browser, Dr. Dobb's Journal, January 1996.
• 9: International Telecommunication Union. Series G: Transmission Systems and Media: Definitions and terminology for synchronization networks - ITU-T Recommendation G.810, (08/96).
• 10: Jun, B., Kocher, P., The Intel Random Number Generator, White Paper Prepared For Intel Corporation. by Cryptography Research Inc. Available at: http://www.cryptography.com/resources/whitepapers/index.html
• 11: John Kelsey , Bruce Schneier , Niels Ferguson, Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator, Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, p.13-33, August 09-10, 1999
• 12: Kohlbrenner, P., The Design and Analyses of a True Random Number Generator in a Field Programmable Gate Array, MS Thesis, ECE Department, George Mason University, Dec 2003, available from the author at [e-mail].
• 13: Sergio López-Buedo , Paula Riviere , Pablo Pernas , Eduardo I. Boemo, Run-Time Reconfiguration to Check Temperature in Custom Computers: An Application of JBits Technology, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.162-170, September 02-04, 2002
• 14: Marsaglia, G., Diehard: A battery of tests for random number generators, 1985, http://stat.fsu.edu/~geo/diehard.html.
• 15: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 16: Petrie, C., S., Connelly, J., A., Modeling and simulation of oscillator-based random number generators, IEEE International Symposium on Circuits and Systems, 1996. ISCAS '96 'Connecting the World', Volume: 4, May 1996 Pages: 324--327 vol.4.
• 17: RAND Corporation, A Million Random Digits with 100,000 Normal Deviates., 1956, The Free Press.
• 18: Rukhin et al., A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST Special Publication 800-22 (revised May 15 2002).
• 19: Werner Schindler , Wolfgang Killmann, Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.431-449, August 13-15, 2002
• 20: K. H. Tsoi , K. H. Leung , P. H. W. Leong, Compact FPGA-based True and Pseudo Random Number Generators, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.51, April 09-11, 2003
• 21: Xilinx, 2002, Superior Jitter Management With DLLs. Virtex Tech Topic, VTT013(v1.2).
• 22: Xilinx, 2002, Annual Report and Form 10-k. http://media.corporateir.net/media.les/NSD/XLNX/annual2002/ar02/letter%.htm.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Design, Experimentation, Security

Keywords:
FPGA, RNG, TRNG, cryptographic, random numbers