Quality of randomness on a Linux system with haveged

Question

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?

Answer 1

TL;DR: do not use HAVEGE, it was flawed. It's evolution HAVEGED (notice the additional D) has improvements, but this answer is about HAVEGE, because the original question was.

---

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.

---

The above is advice about HAVEGE, as in 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.

Answer 2

The haveged program provides a viable additional source of entropy, preferably not as the only source. However, haveged is a product that produces results we surely need in computers starved of random bits including mobile markets.

The CPU/GPU configured so can obviously create logical and not so perfectly entropic results. We have to ask ourselves: do we need random filled with a viable source available to all? The answer is obvious yes.

Haveged produces a data far superior to just the user input. Furthermore the tasks running on the computer and or within the system improve the output.

As the necessity to use haveged increases, then most likely the user will be running more tasks that need to use it and hence there will be better results and more of them.

A true TRNG is a state of peace in the true security advocates heart but there is always room for an improved haveged; both on Windows, on Mac and other operating systems.

http://esa-space.blogspot.com/2017/04/rng-and-random-web.html

http://esa-space.blogspot.com/