HArdware Volatile Entropy Gathering and Expansion
Authors: André Seznec, Nicolas Sendrier
New version HAVEGE2.0 (August 2002)
- HAVEGE1.0 is still available from here
- HAVEGE motivations and principles
- Currently supported architectures and operating systems
- Using HAVEGE
- Testing unpredictability
- Download sources and executable
- What is new in HAVEGE2.0?
- New License (09/25/2003)
- A lot of interesting pointers to web sites on random numbers can be found here
An unpredictable random number generator is a practical approximation of a truly random number generator.
Most previous software algorithms for generating unpredictable random number sequences rely on entropy gathering from measuring unpredictable external events. The throughput of these generators are in the range of 10-100 bits per second. This limits them to being used as seeds for pseudo-random generators. Such unpredictable random number generators are needed for cryptography.
Modern superscalar processors feature a large number of hardware mechanisms which aim at improving performance: caches, branch predictors, TLBs, long pipelines, instruction level parallelism… 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 invocation of the operating system modifies thousands of these binary volatile states .
HAVEGE (HArdware Volatile Entropy Gathering and Expansion) is a user-level software unpredictable random number generator for general-purpose computers that exploits these modifications of the internal volatile hardware states as a source of uncertainty.
During an initialization phase, the hardware clock cycle counter of the processor is used to gather part of this entropy: tens of thousands of unpredictable bits can be gathered per operating system call in average.
HAVEGE combines on-the-fly hardware volatile entropy gathering with pseudo-random number generation.
The internal state of HAVEGE includes thousands of internal volatile hardware states and is merely unmonitorable. Therefore HAVEGE features a very high security level. HAVEGE can reach an unprecedented throughput for a software unpredictable random number generator: several hundreds of megabits per second on current workstations and PCs.
The throughput of HAVEGE favorably competes with usual pseudo-random number generators such as rand() or random(). While HAVEGE was initially designed for cryptology-like application, this high throughput makes HAVEGE usable for all application domains demanding for high performance and high quality random number generators, e.g. Monte Carlo simulations.
Last, but not least, more and more modern appliances such as PDAs, cell phones, etc are built around low-power superscalar processors (e.g. StrongARM, Intel Xscale) and features complex operating systems. HAVEGE can also be implemented on these platforms. A demonstrator of HAVEGE for such a PDA featuring PocketPC2002 and a Xscale processor is available.
More on the HAVEGE approach :
- A. Seznec, N. Sendrier, “HArdware Volatile Entropy Gathering and Expansion: generating unpredictable random numbers at user level”, initial research report, 2002, postscript (302 Kb), pdf (316 Kb)
- A. Seznec, N. Sendrier, “HAVEGE: a user-level software heuristic for generating empirically strong random numbers”, 2003, to appear in the special issue on “Random number generation and highly uniform point sets” of ACM Transaction on Modeling and Computer Simulations, October 2003, postscript (209 Kb), pdf (278 Kb)