The HAVEGE unpredictable random number generator

HArdware Volatile Entropy Gathering and Expansion

Authors: André Seznec, Nicolas Sendrier


Last Modification: September 25, 2003

HAVEGE is now released under the LGPL terms and conditions, January, 2006.

New license, September 25, 2003

HAVEGE2.0 on PocketPC2002, January 24, 2003

New version HAVEGE2.0 (August 2002)

HAVEGE motivations and principles

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)

A Powerpoint (134 Kb)  (or pdf (83 Kb) ) presentation is also available.