twuewand - a truerand algorithm for generating entropy - Whonix integration

Development
,
1

was mentioned in Linux Random Number Generation (RNG) Innerworkings and Early Boot Seeding by HulaHoop

https://www.finnie.org/software/twuewand/

twuewand - a truerand algorithm for generating entropy

Looking into it.

  • Has signed git commits.
  • python2 but maybe could be ported to python3.
  • Debian packaging looks very doable.
  • Causes ~15% CPU on my system. Therefore probably no good idea to run it permanently. But there might be no need for that.
  • stdout contains progress info. Could be discarded to /dev/null.
  • stderr contains entropy. Could be redirected to /dev/random.

time twuewand --bytes 100 takes ~ 6 seconds.

I could write a wrapper. Read XX random amount of bytes. Redirect that entropy to /dev/random. Run that at early boot.

How many random bytes would be worth reading? It should be based on some number considered useful for the kernel. Too many would needlessly slow down the boot.

Size of /var/lib/systemd/random-seed is 512 bytes.

twuewand --bytes 512 1>/dev/random 2>/dev/null

Takes ~ 25 seconds. Quite a long time during boot.

twuewand could alternatively/either/or be used to re-seed. CPU could be limited using cpulimit or so. Reseeding is much less critical, kinda optional and can be slow so this doesn’t stress the CPU.

1 Like
2

See if 256 is a reasonable time? 128 is the minimum needed.

Linux ECC DRNG needs 128 bits to seed and the entropy pool apparently. in newest Linux designs. See this report by Stephan Muller (jitterentropy fame):

I’m hearing reports of python 2 deprecation underway by stable next. Hopefully this can be worked out before then.

No need. Just for initial seeding would do.

1 Like
3

Debian packaging files but outdated since it’s for old perl version not for python version:
https://github.com/finnix/twuewand-pkg-debian

It is part of

DistroWatch.com: Finnix lists it as “Status: Dormant (defined)”.

Quote Bug #1090513 “Background twuewand generation, increase default t...” : Bugs : Finnix

With enhanced debiasing, twuewand now takes a noticeable amount of time to generate 8 bytes (over 1 second, compared with 0.125 seconds before). This process can be backgrounded, and as long as it’s being backgrounded, we can increase the amount of entropy generated to a better number. 128 bytes would be a good compromise of CPU work and total time (about 15 seconds in the background).

  • 128 bits would be fast but is just 16 bytes.
  • 1024 bits are 128 bytes.

128 bytes are 1024 bits.

And also just “a good compromise”. Not maximum security.

Sized between 1024 bytes and 4096 bytes are being discussed.

1 Like
4

Unfortunately this is a very CPU intensive process.

These settings were tested with entropy re-seeding in mind during a long running system.

twuewand --bytes 128

  • 1.5 minutes at 50% CPU
  • 32 minutes 1% CPU

twuewand --bytes 64

  • 17.5 minutes at 1% CPU

In theory entropy collection would be improved and therefore (without further action required) reflected in systemd’s usual /var/lib/systemd/random-seed systemd-random-seed.service mechanisms.

I think capping it at 1% CPU makes sense to avoid running CPU at maximum (fan turns on, producing heat, noise) (and perhaps CPU or other hardware longevity?). This is to avoid wasting too much CPU resources for such a background process. When running multiple VMs, this might add up.

These settings were tested with blocking at boot until entropy is gathered in mind.

twuewand --bytes 4096

  • 3 minutes 8 seconds at maximum CPU

twuewand --bytes 1024

  • 50 seconds at maximum CPU

System boot time might increase up to ~ 50 seconds. Maybe a little less due to systemd parallelization but not much (this has to happen before sysinit.target) and maybe a bit faster/slower depending on CPU speed and system load.

Can write entropy directly to /dev/random? I.e.

twuewand --quiet --bytes 1
twuewand --quiet --bytes 1 >/dev/random

Or convert to hex first? I.e.

twuewand --quiet --bytes 1 | xxd -pu
twuewand --quiet --bytes 1 | xxd -pu >/dev/random

Or convert to bas64 first? I.e.

twuewand --quiet --bytes 1 | base64
twuewand --quiet --bytes 1 | base64 >/dev/random

Or can we stretch its output using sha512sums or something?

twuewand --quiet --bytes 1 | sha512sum

7d5467b2a25a07300b523705b6c26c13c4869ebdbe1c1ee038a6501211d8666bea7e238cf8afa5b73532bbd426291159b588b380c09fcb89a5824acb2fe0b385 -

The latter might be useless at best.

1 Like
5

The slow part is caused by debiasing which is absolutely necessary. Let’s see which one is the fastest and stick to that. Some techniques may need pycrypto.

The most comprehensive method will be chosen, depending on what Python modules are available. They include:

Von Neumann simple debiasing.
Output hashing with SHA256.
Kaminsky debiasing, an extension of Von Neumann. This requires pycrypto.

Important note:

You may also send twuewand output to /dev/random or /dev/urandom, but this merely “stirs the pot”, and does not directly add entropy to the pool.

Seeding the entropy pool != sending bits to /dev/random. The former is done with rndaddentropy:

twuewand $(($(cat /proc/sys/kernel/random/poolsize)/8)) | sudo rndaddentropy

On Linux systems, a small C program is also available called rndaddentropy. This is a wrapper for the RNDADDENTROPY ioctl, and is used for directly adding entropy to the Linux primary pool. Please see its manpage for more details.

1 Like
6

Interesting info:

Finnie refers to Dan’s project which originally inspired him. Dan cites Finnie and van Heusden’s timer_entropyd as similar projects in this space.

I would therefore ask van Heusden if his program deals with seed entropy and if it’s output is ok without debiasing if it doesn’t have any. It seems more performant 500bits/s

1 Like
7

I am not sure. Does the kernel do its own debiasing? This is a critical question.

time twuewand --quiet --bytes 1024 --no-debias requires just 11 seconds. That would make it fit (or more likely fit) for doing this by default during boot.

[1] Also writing to /dev/random should never make it less secure. This is a kernel feature.

Unless perhaps if a less secure source of entropy “gets credited”. (see below)

I am also not sure about that.

refers to this as “credit the entropy” vs “not credit the entropy”.

Quote random(4) - Linux manual page

RNDADDENTROPY

Add some additional entropy to the input pool, incrementing
the entropy count. This differs from writing to /dev/random
or /dev/urandom, which only adds some data but does not incre‐
ment the entropy count. The following structure is used:

struct rand_pool_info {
   int    entropy_count;
   int    buf_size;
   __u32  buf[0];
};

Here entropy_count is the value added to (or subtracted from)
the entropy count, and buf is the buffer of size buf_size
which gets added to the entropy pool.

I think it is safer to improve the actual entropy but not credit it. The rationale here is if whatever is being developed here won’t ever worsen entropy. The only requisite for that is that assumption [1] is actually true. If entropy was credited and the added entropy was flawed, the security could be actually worsened. Therefore I am following the same strategy that systemd is implementing - adding entropy but not crediting it - just to stay safe. Better for entropy but no gain in performance. [2]

[2] No faster boot times and no better defense against entropy depletion. While the latter is probably rather theoretic nowadays with jitterentropy_rng and haveged already installed by default.

1 Like
8

Not for third party sources which is why twuewand/dakarand goes thru so much trouble implementing it.

True but we are looking for pool seeding exclusively with twuewand because of how fragile this time window is

1 Like
9

Well if we’re not crediting then the main usecase is gone. Let’s stick with better performing alternatives?

1 Like
10

I don’t think there’s a fragile time window. We’re distrusting RDRAND already. Kernel will block /dev/random until ready and of sufficient quality. Any new entropy gathering daemons could block booting until systemd sysinit.target or something even earlier is done.

If we added extra entropy and credited it, the process will be faster but less secure. I don’t think we should make the process faster at the expense for higher risks. That would be possible but would require this solution to generate traction and peer review.

If we added extra entropy and credited it,

  • in best case: entropy quality increases
  • in worst case: we waste CPU cycles, increase lines of Whonix source code, waste time and accomplish no entropy quality increase but also no entropy quality degradation.
  • Main goal: improve entropy quality
  • Improving boot time (credit entropy): non-goal
  • Not worsening boot time so that nobody wants to use Whonix anymore: goal
  • Price to pay: slightly increased boot time / system load

Yes, additionally but not as a replacement. If I remember right, somewhere you wrote “our best bet is to make use of as many entropy sources as we can”? I very much agree with that still.

twuewand is truerand based. twuewand could be replaced with a different implementation based on truerand but better performance.

timer_entropyd by Van Heusden though is not truerand based. At least I cannot find any reference trivially to that in the source code.

clrngd fork is by Van Heusden is truerand based.

In conclusion: 1 implementation based on truerand and other entropy sources based on other devices (preferably) or other algorithms.

1 Like
11

I see. I asked the questions before you posted though:

sounds awfully similar to timer jitter concept?

Clock randomness gathering daemon
The Clock randomness gathering daemon gathers system randomness from fluctuations between different physical high-frequency clocks in a system. The randomness is tested with FIPS, and if this is successful, fed into the system entropy pool. It is especially useful for systems without real hardware random number generators.

1 Like
12

I am not sure twuewand and timer_entropyd are jitter based. “Something with timers” but still need to learn more.

I don’t understand the differences yet. Which ones are different, how, worth combining, which aren’t.

We are considering twuewand to combat the problem of distros enabling trust of hw cpu rngs which in some cases are broken and output repeating numbers, if malicious outright.

distrusting RDRAND should completely mitigate that.

1 Like
13

currently looking in to porting “twuewand” to python3 per @Patrick 's request, hung up out how to run the tests currently

This line was removed from the worker file
Programming Language :: Python :: 2 :: Only

and replaced with
Programming Language :: Python

Also there was already a python 2 method removed as well in the truerand.py

relevant commit Support Python 2 / 3 ¡ rfinnie/twuewand@3631539 ¡ GitHub

Edit by Patrick:
fix link

2 Likes
14

Maybe it already has (partial) python3 support? Maybe just shebang changes?

15

Since this is a TRNG as opposed to a PRNG, could twuewand be used in place of systems that use rdrand? Could a CPU be instructed to not only distrust rdrand, which we do already, but also use twuewand in its place for all applications that need it? For example, take a openvpn server that needs good quality random numbers.

16

rdrand is unrelated. distrusting RDRAND is a separate.

There is probably no need to configure per application. The Linux kernel provides APIs, entropy pools. You could learn more about that here: good read on the linux security wrt to entropy / randomness

By installing and configuring twuewand, the entropy quality might get better. All applications would benefit from that without further action required.

1 Like
17

You think I should add python3 to the top of just the twuewand files? The setup does not like it when I try to build with python3 because of dependencies issues.

Thanks for your patience, as this is new territory :slight_smile:

2 Likes
18

Probably yes. I don’t think there is any reason to keep python2 compatibility. Can by python3 only.

No worries at all. Appreciate your work! :slight_smile:

1 Like
19

We better don’t use debiasing as per Questions on seeeding, value of similar utilities · Issue #16 · smuellerDD/jitterentropy-library · GitHub.

(Read de bias. Not Debian. Easily misread and almost wrote Debian myself instead of debias.)

Before I knew that, started creating of two files, each 1 MB big in size, containing entropy created by twuewand without debias. Just sharing for the fun of it since I already produced the results.

twuewand --no-debias --bytes 1000000

Generated 1000000.0 bytes, output 1000000

real 234m
user 1853m
sys 0m34s

And with twuewand with debias.

twuewand --bytes 1000000

Generated 1000000.1 bytes, output 1000000

real 1158m
user 9136m
sys 2m

Debias takes around 5 times longer. And also takes a very long time to create 1 MB of random data using twuewand anyhow.

1 Like
20

Stephan’s is a general statement not really applying to twuerand per se:

A Von-Neumann unbiaser is good IFF we have stochastically independent values.
Otherwise, a Von-Neumann unbiaser can be a disaster. Such independence,
however, is commonly not given.

Therefore we can’t conclude de-biasing is useless in that case.

1 Like