15
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Thomas Apr 23 '13 at 5:52
  • $\begingroup$ @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? $\endgroup$ – Hal Bal Apr 23 '13 at 6:18
  • $\begingroup$ 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) $\endgroup$ – Thomas Apr 23 '13 at 6:38
  • 5
13
$\begingroup$

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: enter image description here 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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Even with all its flaws, you can still use it safely, e.g. haveged -n 1M -f /dev/urandom, which will mix in 1 MiB of data with the random pool without issuing the ioctls required to artificially boost the entropy estimate. $\endgroup$ – forest Mar 17 '18 at 5:03
-3
$\begingroup$

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/

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hi Quandar and welcome. Please spent as much time possible formatting your answer. It was pretty tricky to format it without all the dots, commas and suchlike at the wrong places. At least capitalize your sentences; you've already shown you understand how to do that. $\endgroup$ – Maarten Bodewes Apr 28 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.