HAVEGE: A user-level software heuristic for generating empirically strong random numbers

ABSTRACT

Random numbers with high cryptographic quality are needed to enhance the security of cryptography applications. Software heuristics for generating empirically strong random number sequences rely on entropy gathering by measuring unpredictable external events. These generators only deliver a few bits per event. This limits them to being used as seeds for pseudorandom generators.General-purpose processors feature a large number of hardware mechanisms that aim to improve performance: caches, branch predictors, …. The state of these components is not architectural (i.e., the result of an ordinary application does not depend on it). It is also volatile and cannot be directly monitored by the user. On the other hand, every operating system interrupt modifies thousands of these binary volatile states.In this article, we present and analyze HAVEGE (HArdware Volatile Entropy Gathering and Expansion), a new user-level software heuristic to generate practically strong random numbers on general-purpose computers. The hardware clock cycle counter of the processor can be used to gather part of the entropy/uncertainty introduced by operating system interrupts in the internal states of the processor. Then, we show how this entropy gathering technique can be combined with pseudorandom number generation in HAVEGE. Since the internal state of HAVEGE includes thousands of internal volatile hardware states, it seems impossible even for the user itself to reproduce the generated sequences.

REFERENCES

• 1: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 2: Don Davis , Ross Ihaka , Philip Fenstermacher, Cryptographic Randomness from Air Turbulence in Disk Drives, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.114-120, August 21-25, 1994
• 3: Diefendhorff, K. 1999a. Compaq chooses SMT for Alpha. Microproc. Rep. 13, 13, 3--8.
• 4: Diefendhorff, K. 1999b. Power4 focuses on memory bandwidth. Microproc. Rep. 13, 16, 1--6.
• 5: FIPS-140-2. 2001. Security requirements for cryptographic modules. Federal Information Processing Standard publication 140-2.
• 6: Markus Jakobsson , Elizabeth Shriver , Bruce K. Hillyer , Ari Juels, A practical secure physical random bit generator, Proceedings of the 5th ACM conference on Computer and communications security, p.103-111, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288114]
• 7: Jun, B. and Kocher, P. 1999. The Intel random number generator. Cryptography Research, Inc., White Paper prepared for Intel Corporation.
• 8: 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
• 9: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 10: P. L'Ecuyer , R. Proulx, About polynomial-time “unpredictable” generators, Proceedings of the 21st conference on Winter simulation, p.467-476, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76799]
• 11: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 12: Andreas Moshovos , Gurindar S. Sohi, Streamlining inter-operation memory communication via data dependence prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.235-245, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 13: Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., and Vo, S. 2001. A statistical test suite for random and pseudorandom number generators for cryptographic applications. National Institute of Standards and Technology publication 800-22.
• 14: Seznec, A. and Sendrier, N. 2002. Hardware volatile entropy gathering and expansion: generating unpredictable random number at user level. Tech. Rep. 4592, INRIA.
• 15: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Security

Keywords:
Cryptography, hardware clock counters, random number generation, superscalar processor