# Quality of randomness on a Linux system with haveged

Has anyone checked if using haveged, a Linux daemon which uses the HAVEGE algorithm, changes the non-deterministic properties of the random data from /dev/random in any negative ways?

-
A real-time HRNG requiring no additional hardware suitable for both cryptography and Monte-Carlo simulations sounds a bit too good to be true, to be fair. And there are almost no reviews on it, which makes me feel uneasy about using it. That said, unless the algorithm is phenomenally bad, it is quite hard to defeat a good entropy collector even when feeding huge amounts of garbage in it, so I would guess the bias would be academical. Good question though! –  Thomas Apr 23 '13 at 5:52
@Thomas :Thanks! I believe the Tails OS ships with it by default, but I don't know if there are any cryptographers on their programming team. If we assumed that the majority of the data fed by the daemon was garbage, would the driver responsible for /dev/random weed out the bad from the good? –  Hal Bal Apr 23 '13 at 6:18
When I meant garbage I meant stuff like an infinite string of zeros, e.g. zero-entropy stuff intended to corrupt the entropy pool, because the entropy pool hopefully reinitializes every few milliseconds and does not rely on one unique source of entropy, it's supposed to be resistant to this kind of poisoning by design, so, yes, I would expect the driver to implement correct accumulation algorithms, since it's what it's supposed to do :p (though it is much more complex than that) –  Thomas Apr 23 '13 at 6:38
–  Gilles Apr 29 '13 at 12:45

I do not buy some of HAVEGE, specifically the claim made here "tens of thousands of unpredictable bits can be gathered per operating system call in average", and the methodology used to support that claim, as found here.

Entropy gathering is described by this pseudocode: where HARDTICK() is a function that reads a hardware clock counter. An experimental evaluation of the entropy gathered was made as follows:

We determined the threshold for NMININT above which the content of Entrop array can be CONSISTENTLY considered as random, i.e. it cannot be distinguished by our battery of tests from truly random numbers (i.e DieHard + ent + FIPS 140 +NIST suite).

(Emphasis using bold is mine)

The data gathered in Entrop is built using a Pseudo-Random Number Generator, complete with repeated rotation by 5 bit of each 32-bit word of Entrop, combination by XOR with one bit of the least recently modified word of Entrop, and combination by XOR with the actual source of entropy, HARDTICK() (or rather, the delta between successive HARDTICK() which is to closest to the actual source of entropy). See HAVEGE's paper for more details.

The entropy at the output of that PRNG has been evaluated using an experimental test (not designed specifically against this PRNG). That's a cardinal mistake: any half-decent PRNG will pass this test, even if fed very little actual entropy in its input, which makes its output highly predictable.

While this does not constitute a practical break of HAVEGE, it shows that the justification of its entropy-gathering part is flawed. My recommendation is thus not to use HAVEGE.

Update: the above is advice about HAVEGE, as in the original title and some of the text of the original question, based on references from 2003. In it's successor HAVEGED (notice the additional D) of the 201x, there was some effort made towards a sound methodology, in particular checking the entropy at input of the PRNG, leading to the conclusion: "Most samples failed all tests!". It is acknowledged that theoretical analysis of the source of entropy to build a model suitable to support a demonstration of security "were not sufficient to constitute such a model". This at least is quite believable.

-