Entropy and randomness: Difference between revisions

From Alpine Linux
m (Added suggestion to test entropy across large amounts of data in "Testing entropy with ENT" section)
(update link)
 
(14 intermediate revisions by 3 users not shown)
Line 7: Line 7:
* Generation of cryptographic keys
* Generation of cryptographic keys


* Address Space Layout Randomisation ([http://en.wikipedia.org/wiki/PaX#Address_space_layout_randomization ASLR]) - used by default in Alpine of course ;)
* Address Space Layout Randomisation ([https://en.wikipedia.org/wiki/Executable-space_protection#Address_space_layout_randomization ASLR]) - used by default in Alpine of course ;)


* TCP port randomisation ([https://en.wikipedia.org/wiki/Network_address_translation NAT], outbound connection)
* TCP port randomisation ([https://en.wikipedia.org/wiki/Network_address_translation NAT], outbound connection)


* [https://en.wikipedia.org/wiki/Transmission_Control_Protocol#Reliable_transmission TCP sequence number] selection (see [https://en.wikipedia.org/wiki/TCP_sequence_prediction_attack this too]
* [https://en.wikipedia.org/wiki/Transmission_Control_Protocol#Reliable_transmission TCP sequence number] selection (see [https://en.wikipedia.org/wiki/TCP_sequence_prediction_attack this too)]


* Writing random files for testing network functionality and throughput
* Writing random files for testing network functionality and throughput
Line 26: Line 26:


On a standard system the limit is 4096 bits (512 bytes).  The [https://grsecurity.net/ gr-sec] patch used on Alpine increases this limit to 16384 bits (2048 bytes).
On a standard system the limit is 4096 bits (512 bytes).  The [https://grsecurity.net/ gr-sec] patch used on Alpine increases this limit to 16384 bits (2048 bytes).
Entropy is added to the pool in bits from various sources, "the relative number of unknown bits per event is roughly 8/keyboard, 12/mouse, 3/disk, 4/interrupt" [http://www.issihosts.com/haveged/history.html#intro source] meaning that on a headless server (without mouse and keyboard attached), which ironically is often a system requiring the most entropy, entropy generation is somewhat limited.
Entropy is added to the pool in bits from various sources, "the relative number of unknown bits per event is roughly 8/keyboard, 12/mouse, 3/disk, 4/interrupt" [https://www.issihosts.com/haveged/history.html#intro source] meaning that on a headless server (without mouse and keyboard attached), which ironically is often a system requiring the most entropy, entropy generation is somewhat limited.


The entropy from the pool can be accessed in two ways by default:
The entropy from the pool can be accessed in two ways by default:


'''/dev/random''' - This is a [https://en.wikipedia.org/wiki/Blocking_%28computing%29 blocking] resource, so it will use available entropy from the pool.  If more entropy is required than is available, the process will wait until more entropy is available in the pool.  Due to this behaviour, /dev/random is best used where small amounts of high quality randomness are required, such as for cryptographic keys.
'''/dev/random''' - On Kernels older than 5.6, this is a [https://en.wikipedia.org/wiki/Blocking_%28computing%29 blocking] resource, so it will use available entropy from the pool.  If more entropy is required than is available, the process will wait until more entropy is available in the pool.  Due to this behaviour, /dev/random is best used where small amounts of high quality randomness are required, such as for cryptographic keys.


'''/dev/urandom''' - Is a non-blocking resource. It uses a seed value from the same entropy pool as /dev/random and therefore, if little entropy is available in the pool, it is recommended not to use /dev/urandom until more entropy is made available in the pool.  It runs the seed value through an algorithm and so is a [http://en.wikipedia.org/wiki/Pseudo-random_number_generator pseudo-random number generator], operating much faster than /dev/random.  /dev/urandom is best used for non-cryptographic purposes such as overwriting disks.
'''/dev/urandom''' - Is a non-blocking resource on all Kernel versions. It uses a seed value from the same entropy pool as /dev/random and therefore, if little entropy is available in the pool, it is recommended not to use /dev/urandom until more entropy is made available in the pool.  It runs the seed value through an algorithm and so is a [https://en.wikipedia.org/wiki/Pseudo-random_number_generator pseudo-random number generator], operating much faster than /dev/random.  /dev/urandom is best used for non-cryptographic purposes such as overwriting disks.


Writing to /dev/random or /dev/urandom will update the entropy pool with the data written, but this will not result in a higher entropy count.  This means that it will impact the contents read from both files, but it will not make reads from /dev/random faster.
Writing to /dev/random or /dev/urandom will update the entropy pool with the data written, but this will not result in a higher entropy count.  This means that it will impact the contents read from both files, but it will not make reads from /dev/random faster.
For more information see the [http://www.manpagez.com/man/4/random/ random manpage]
For more information see the [https://linux.die.net/man/4/random random manpage]


It is generally recommended wherever entropy is used heavily to supply additional entropy sources; some possibilities are below.  Adding more sources of entropy to feed into the pool is a good idea.  It makes an attackers job more difficult, because there will be more sources they have to gain control over (or at the very least observe at source), and adding more sources of entropy, even weak ones, can only result in higher entropy.
It is generally recommended wherever entropy is used heavily to supply additional entropy sources; some possibilities are below.  Adding more sources of entropy to feed into the pool is a good idea.  It makes an attackers job more difficult, because there will be more sources they have to gain control over (or at the very least observe at source), and adding more sources of entropy, even weak ones, can only result in higher entropy.


If you are desperate for more entropy and are working on a headless server with no internet connection, you could try generating some via disk activity.  Just don't expect any miracles!  I'm sure someone can come up with something better than my example below:
If you are desperate for more entropy and are working on a headless server with no internet connection, you could try generating some via disk activity.  Just don't expect any miracles!  Here's an example:


<pre>time dd if=/dev/zero of=/var/tmp/tempfile bs=1M count=200 && find / -size +1k && rm /var/tmp/tempfile && sync</pre>
<pre>dd if=/dev/zero of=/var/tmp/tempfile bs=1M count=200 && find / -size +1k && ls -R / && rm /var/tmp/tempfile && sync</pre>


(If you have {{Pkg|wipe}} installed, use this instead of 'rm').  If your server is a 'run-from-ram' setup and so you have no disks to create churn but require more entropy, it is strongly recommended to add alternative entropy sources as discussed below.
If your server is a 'run-from-ram' setup and so you have no disks to create churn but require more entropy, it is strongly recommended to add alternative entropy sources as discussed below.


== Alternative/Additional entropy sources ==
== Alternative/Additional entropy sources ==
{{Obsolete|Much of the content in this section is obsolete [https://github.com/jirka-h/haveged/commit/297bdf1fc52fc6f59d0495f911d4e594b4d29190 since Kernel 5.6], or roughly Alpine Linux version 3.13.0}}


=== Haveged ===
=== Haveged ===


[http://www.issihosts.com/haveged/ Haveged] generates entropy based on [http://www.issihosts.com/haveged/flutter.html CPU flutter].  The entropy is buffered and fed into the entropy pool when write_wakeup_threshold is reached.  Write a value (the number of bits) to it if you wish to change it:  
[https://www.issihosts.com/haveged/ Haveged] generates entropy based on [https://www.issihosts.com/haveged/flutter.html CPU flutter].  The entropy is buffered and fed into the entropy pool when write_wakeup_threshold is reached.  Write a value (the number of bits) to it if you wish to change it:  


{{Cmd|echo "1024" > /proc/sys/kernel/random/write_wakeup_threshold}}
{{Cmd|echo "1024" > /proc/sys/kernel/random/write_wakeup_threshold}}
Line 57: Line 59:
{{Cmd|haveged -w 1024}}
{{Cmd|haveged -w 1024}}


Install [http://alpinelinux.org/apk/main/x86_64/haveged haveged], then start and set to autostart at boot:
Install {{pkg|haveged}}, then start and set to autostart at boot:


{{Cmd|apk -U add haveged && rc-service haveged start && rc-update add haveged}}
{{Cmd|apk -U add haveged && rc-service haveged start && rc-update add haveged}}


[http://linux.die.net/man/8/haveged Further configuration] is possible however the defaults should work fine out of the box.  
[https://linux.die.net/man/8/haveged Further configuration] is possible however the defaults should work fine out of the box.


=== Other possibilities ===
=== Other possibilities ===


Some other possibilites for entropy generation are:
It is also possible to replace /dev/random with [https://egd.sourceforge.net/ EGD, the Entropy Gathering Daemon], or to use this on systems that are not able to support /dev/random.  However, this is not required (or recommended) under normal circumstances.
 
*[http://www.vanheusden.com/te/ timer entropy daemon] -  should provide on-demand entropy based on variances in timings of sleep command.
 
*[http://www.vanheusden.com/ved/ video entropy daemon] - requires a video4linux-device, gathers entropy by taking a couple of images and calculating the differences and then the entropy of that.  Can be run on demand or as a cron job.
 
*[http://www.vanheusden.com/aed/ audio entropy daemon] - requires alsa development libraries and an audio device.  Generates entropy by reading from audio device and de-baising data.
 
*[http://vladz.devzero.fr/guchaos.php GUChaos] - "Give Us Chaos" provides on-demand entropy, by retrieving random blocks of bytes from the [http://www.random.org/ Random.org] website, and transforms them with a [http://en.wikipedia.org/wiki/Substitution_cipher polynumeric substitution cipher] before adding them to /dev/random until the entropy pool is filled.
 
and hardware entropy generators such as:
 
*[http://www.entropykey.co.uk/ Entropy Key] - USB hardware entropy generator
 
It is also possible to replace /dev/random with [http://egd.sourceforge.net/ EGD, the Entropy Gathering Daemon], or to use this on systems that are not able to support /dev/random.  However, this is not required (or recommended) under normal circumstances.


== Testing entropy with ENT ==
== Testing entropy with ENT ==


It is possible to [http://en.wikipedia.org/wiki/Randomness_test test] entropy to see how statistically random it is.  Generally, such tests only reveal part of the picture, since some numbers can pass statistical entropy tests whilst they are not actually random.  Failing a statistical randomness test is not a good indicator of course!
It is possible to [https://en.wikipedia.org/wiki/Randomness_test test] entropy to see how statistically random it is.  Generally, such tests only reveal part of the picture, since some numbers can pass statistical entropy tests whilst they are not actually random.  Failing a statistical randomness test is not a good indicator of course!


Make a folder for testing, and get hold of [http://www.fourmilab.ch/random/ ENT]:
Make a folder for testing, and get hold of [https://www.fourmilab.ch/random/ ENT]:


<pre>
<pre>
mkdir /tmp/test/make
mkdir /tmp/test/make
cd /tmp/test/make
cd /tmp/test/make
wget http://www.fourmilab.ch/random/random.zip
wget https://www.fourmilab.ch/random/random.zip
unzip random.zip
unzip random.zip
make
make
Line 122: Line 110:
=== Other tests ===
=== Other tests ===


Other tests include [http://www.stat.fsu.edu/pub/diehard/ diehard] and [http://www.phy.duke.edu/~rgb/General/dieharder.php dieharder]
Other tests include [https://ani.stat.fsu.edu/diehard/ diehard] and [https://webhome.phy.duke.edu/~rgb/General/dieharder.php dieharder]


== Further reading ==
== Further reading ==


[http://rsmith.home.xs4all.nl/howto/fun-with-encryption-and-randomness.html visualising randomness]
[https://rsmith.home.xs4all.nl/howto/fun-with-encryption-and-randomness.html visualising randomness]


[http://www.linuxfromscratch.org/hints/downloads/files/entropy.txt linux from scratch]
[https://www.linuxfromscratch.org/hints/downloads/files/entropy.txt linux from scratch]


[http://blog.cloudflare.com/ensuring-randomness-with-linuxs-random-number-generator Cloudflare]
[https://blog.cloudflare.com/ensuring-randomness-with-linuxs-random-number-generator Cloudflare]


[https://tools.ietf.org/html/rfc4086 RFC 4086 - Randomness Requirements for Security]
[https://datatracker.ietf.org/doc/html/rfc4086 RFC 4086 - Randomness Requirements for Security]


[https://calomel.org/entropy_random_number_generators.html calomel.org]
[https://calomel.org/entropy_random_number_generators.html calomel.org]


[http://www.av8n.com/turbid/paper/turbid.htm Turbid]
[https://www.av8n.com/turbid/paper/turbid.htm Turbid]


[http://blog.cryptographyengineering.com/2012/02/random-number-generation-illustrated.html Random number generation: An illustrated primer]
[https://blog.cryptographyengineering.com/2012/02/21/random-number-generation-illustrated/ Random number generation: An illustrated primer]


[https://factorable.net/weakkeys12.extended.pdf Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, PDF]
[https://factorable.net/weakkeys12.extended.pdf Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, PDF]


[http://www.pinkas.net/PAPERS/gpr06.pdf  Analysis of the Linux Random Number Generator, PDF]
[http://www.pinkas.net/PAPERS/gpr06.pdf  Analysis of the Linux Random Number Generator, PDF]{{insecure url|Connection refused on HTTPS}}


[http://cryptome.org/2014/03/eat-entropy-have-it.pdf How to Eat Your Entropy and Have it Too — Optimal Recovery Strategies for Compromised RNGs, PDF]
[https://cryptome.org/2014/03/eat-entropy-have-it.pdf How to Eat Your Entropy and Have it Too — Optimal Recovery Strategies for Compromised RNGs, PDF]


[http://eprint.iacr.org/2013/338.pdf Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust, PDF]
[https://eprint.iacr.org/2013/338.pdf Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust, PDF]


[[Category:Server]]
[[Category:Server]]
[[Category:Security]]

Latest revision as of 11:44, 25 August 2023

Introduction

Entropy is described as 'a numerical measure of the uncertainty of an outcome' and is often associated with chaos or disorder however is often more simply called randomness.

It is important for a secure operating system to have sufficient quantities of entropy available for various crypotographic and non-cryptographic purposes, such as:

  • Generation of cryptographic keys
  • Address Space Layout Randomisation (ASLR) - used by default in Alpine of course ;)
  • TCP port randomisation (NAT, outbound connection)
  • Writing random files for testing network functionality and throughput
  • Overwriting hard disks prior to reuse or resale or encryption

Entropy is contained within a pool, which draws its entropy from various sources. To view the current amount of entropy in the pool:

more /proc/sys/kernel/random/entropy_avail

To view the maximum limit of entropy that the pool can hold:

more /proc/sys/kernel/random/poolsize

On a standard system the limit is 4096 bits (512 bytes). The gr-sec patch used on Alpine increases this limit to 16384 bits (2048 bytes). Entropy is added to the pool in bits from various sources, "the relative number of unknown bits per event is roughly 8/keyboard, 12/mouse, 3/disk, 4/interrupt" source meaning that on a headless server (without mouse and keyboard attached), which ironically is often a system requiring the most entropy, entropy generation is somewhat limited.

The entropy from the pool can be accessed in two ways by default:

/dev/random - On Kernels older than 5.6, this is a blocking resource, so it will use available entropy from the pool. If more entropy is required than is available, the process will wait until more entropy is available in the pool. Due to this behaviour, /dev/random is best used where small amounts of high quality randomness are required, such as for cryptographic keys.

/dev/urandom - Is a non-blocking resource on all Kernel versions. It uses a seed value from the same entropy pool as /dev/random and therefore, if little entropy is available in the pool, it is recommended not to use /dev/urandom until more entropy is made available in the pool. It runs the seed value through an algorithm and so is a pseudo-random number generator, operating much faster than /dev/random. /dev/urandom is best used for non-cryptographic purposes such as overwriting disks.

Writing to /dev/random or /dev/urandom will update the entropy pool with the data written, but this will not result in a higher entropy count. This means that it will impact the contents read from both files, but it will not make reads from /dev/random faster. For more information see the random manpage

It is generally recommended wherever entropy is used heavily to supply additional entropy sources; some possibilities are below. Adding more sources of entropy to feed into the pool is a good idea. It makes an attackers job more difficult, because there will be more sources they have to gain control over (or at the very least observe at source), and adding more sources of entropy, even weak ones, can only result in higher entropy.

If you are desperate for more entropy and are working on a headless server with no internet connection, you could try generating some via disk activity. Just don't expect any miracles! Here's an example:

dd if=/dev/zero of=/var/tmp/tempfile bs=1M count=200 && find / -size +1k && ls -R / && rm /var/tmp/tempfile && sync

If your server is a 'run-from-ram' setup and so you have no disks to create churn but require more entropy, it is strongly recommended to add alternative entropy sources as discussed below.

Alternative/Additional entropy sources

This material is obsolete ...

Much of the content in this section is obsolete since Kernel 5.6, or roughly Alpine Linux version 3.13.0 (Discuss)

Haveged

Haveged generates entropy based on CPU flutter. The entropy is buffered and fed into the entropy pool when write_wakeup_threshold is reached. Write a value (the number of bits) to it if you wish to change it:

echo "1024" > /proc/sys/kernel/random/write_wakeup_threshold

Or change it via haveged:

haveged -w 1024

Install haveged, then start and set to autostart at boot:

apk -U add haveged && rc-service haveged start && rc-update add haveged

Further configuration is possible however the defaults should work fine out of the box.

Other possibilities

It is also possible to replace /dev/random with EGD, the Entropy Gathering Daemon, or to use this on systems that are not able to support /dev/random. However, this is not required (or recommended) under normal circumstances.

Testing entropy with ENT

It is possible to test entropy to see how statistically random it is. Generally, such tests only reveal part of the picture, since some numbers can pass statistical entropy tests whilst they are not actually random. Failing a statistical randomness test is not a good indicator of course!

Make a folder for testing, and get hold of ENT:

mkdir /tmp/test/make
cd /tmp/test/make
wget https://www.fourmilab.ch/random/random.zip
unzip random.zip
make
mv ./ent /tmp/test/
cd /tmp/test

Create some random data. In this example we read from /dev/urandom:

dd if=/dev/urandom of=/tmp/test/urandomfile bs=1 count=16384

Run the ENT test against it:

./ent /tmp/test/urandomfile

Try the same test whilst treating the data as a stream of bits and printing an account of character occurrences:

./ent -b -c /tmp/test/urandomfile

Note any differences against the previous test.

I propose also generating larger streams of data (10's or 100's of MB) and testing against this too. Any repeating data or patterns (caused by a small/poor seed value for instance) will make spotting any weaknesses and a lack of randomness much easier across large amounts of data than across small amounts.

I also suggest running the test against known non-random files, so you may see that some tests show that such a file can have some characteristics of a random file, whilst completely failing other randomness tests.

Finally, once you are done testing with ENT, it's good practice to delete the working folder:

rm -r /tmp/test/


Other tests

Other tests include diehard and dieharder

Further reading

visualising randomness

linux from scratch

Cloudflare

RFC 4086 - Randomness Requirements for Security

calomel.org

Turbid

Random number generation: An illustrated primer

Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, PDF

Analysis of the Linux Random Number Generator, PDF 🔓

How to Eat Your Entropy and Have it Too — Optimal Recovery Strategies for Compromised RNGs, PDF

Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust, PDF