I previously blogged about the HAVEGE algorithm that is billed as extracting randomness from microarchitectural variations in modern processors. Since it was supposed to rely on hardware timing variations, I wondered what would happen if I ran it on Simics that does not model the processor pipeline, caches, and branch predictor. Wouldn’t that make the randomness of HAVEGE go away?
I got HAVEGE up on a Simics x86 target model with Linux pretty quickly, and ran the two provided tests. Ent, which is a quick entropy test, and nist which supposedly much more thorough.
To my surprise, they both said the randomness we got was totally acceptable. This would seem to invalidate the fundamental assumption of HAVEGE – that it needs to collect randomness from hardware in order to produce good-quality randomness. To try to understand a bit more of what was going on, I took at look at the execution using Simics Analyzer (the dredd.motherboard.processor lines are the processors, and the orange part is the HAVEGE program, yellow is the kernel):
Zooming in a bit:
We can see that the program is regularly interrupted by the OS, which could be a reason for random timing variations. The instructions run by the OS should vary in count, which would disturb the time stamp counter values read by the HAVEGE program. That could be sufficient to cause random variations, essentially showing that HAVEGE really works well just from OS noise – even in an otherwise idle machine.
However, at this point I started to have my doubts. Something did not feel right.
So I tried to remove all variations from the HAVEGE program. I replaced the “HARDTICKS” macro in HAVEGE with the constant 0 (zero) rather than reading the time stamp counter of the processor. This immediately failed the randomness test.
However, when I used the constant 1 (one) instead, the ent test passed. And even nist almost passed with only a single missed test out of the 426 tests executed.
Thus, the conclusion is that we do not know how well HAVEGE ‘s collection of hardware randomness works, since the evaluation software is too weak. In essence, we do not know if the collection of hardware randomness matters or not, as the proposed measurement hides the randomness behind a pretty good PRNG algorithm.
Ideally, we would need a measurement that would evaluate the predictability of the randomness generated. Or at least one that can correctly estimate the impact of the variation of low-level hardware timing on the quality of the final random numbers. Unfortunately, that is not the case here, throwing the entire idea into doubt.
Hi,
I was pointed out your blog.
As the author of HAVEGE, I respectfully try to point out that you are making a confusion between “does a sequence of bits appears to a uniformly randomly distributed sequence” (uniform distribution) that the Nist and the ent test are intended to test and “does a sequence of bits is unpredictable random” (unpredictable randomness).
In the absence of external events injection (I presume that when running SIMICS you do not get external events injections and that the modeling of the hardware clock counter on SIMICS is quite primitive,) HAVEGE is just a good pseudo-random number generator (that is a deterministic algorithm) on any machine: if the initial microarchitectural states of the processors,e.g. branch predictor contents, cache contents, pipeline states .. (the seed of the generator) are fixed at beginning of the execution and if there is no external state injection then the result will be the same (and pass the uniformity test such as NIST and ent).
What makes HAVEGE an unpredictable random number generator (when run on a real machine) is that:
1) the initial hardware state of the machine can not be monitored and reproduced
(except freezing the clock and dumping all the hardware states of the processors)
2) external events (interruptions, OS handlers, etc) are constantly modifying the microarchitectural states of the processor during the random number generation.
(We deliberately ensure that there will be several OS interruptions during a random number generation).
Isn’t there an Ankos theorem that states that NOT getting an RNG from observing the behaviour of a computer is a very difficut task? 😉
Totally agree. The problem is that those tests are used in the HAVEGE papers to show that using hardware randomness is good. I do want a test that can actually measure the hardware randomness, anything to offer on that would be great!
When running Simics, you do get external events like timer interrupts, console I/O, etc. There is no model of pipelines, caches, branch predictors, but there is a full OS running with its noise. I was really curious to see the impact of OS noise isolated from low-level factors in the target machine.
Obviously, Simics is designed to be repeatable and deterministic, so each run on Simics from the same initial state with the same scripted input sequence will yield the exact same random sequence.
Yes. But it would be nice to be able to quantify the effect of this microarchitectural noise.