A kernel module for randomness generation

This module aims to reimplement the core part of the randomness generation algorithm in the linux kernel source code. It can be served as a basis to generate randomness in different fashions.

In randomized algorithms, one may need fast but statistically reliable randomness while in cryptography one needs secure randomness even if it means to sacrifice efficiency. This code allows to adapt and study randomness generation algorithms under different entropy models. Note that it is not a production-level code.

Structure

• The algorithm collects many TSC (Time Stamp Counter) data upon every IRQ (Interrupt Request) per each CPU core. This data depends on the exact timing of the IRQ and the jitters in the hardware, during each interrupt. Both are unpredictable.
• In each CPU core, the data is then hashed by SipHash and put in a per-CPU struct called fast pool.
• Every min(1024 IRQ, 1 second), the data is pushed into a slow pool shared by all cores where it gets absorbed by the BLAKE2 hash function state.
• Only when BLAKE2 is called 256 times, /dev/myrnd gets unblocked and ready to be used as follows:
  • each reading call to /dev/myrnd extracts a key from the slow pool and use it as the seed in the ChaCha pseudorandom number generator (PRG).

If you need more algorithmic randomness you can reduce the number of rounds or even remove BLAKE2 hashing part. If you are in a very conservative cryptographic setting, you can increase the number of rounds and use better PRGs such as Keccak-based ones.

To run the module

Install essentials and linux kernel headers:

sudo apt install build-essential linux-headers-$(uname -r)

Clone the repo and do the following in the cloned directory:

make
make load OR sudo insmod myrnd.ko

If the secure boot on you machine is on, you need to sign the module with the machine owner key before loading it.

Check if the module is on:

sudo dmesg | tail # expect to see:  "myrnd: collecting"
lsmod | grep myrnd
ls -l /dev/myrnd

You can watch live the number of times BLAKE2 is applied to slow pool:

make watch

You can read /dev/myrnd to extract randomness, for instance:

head -10 /dev/myrnd

NOTE: /dev/myrnd is blocked until at leat 256 BLAKE2 hashes are applied. You can watch it live as explained above.

You can unload the kernel as follows:

make unload OR sudo rmmod myrnd
make clean