The venerable Linux /dev/random served users of cryptographic mechanisms well for a long time. Its behavior is well understood to deliver entropic data. In the last years, however, the Linux /dev/random showed signs of age where it has challenges to cope with modern computing environments ranging from tiny embedded systems, over new hardware resources such as SSDs, up to massive parallel systems as well as virtualized environments. This paper proposes a new approach to entropy collection in the Linux kernel with the intention of addressing all identified shortcomings of the legacy /dev/random implementation. The new Linux Random Number Generator's design is presented and all its cryptographic aspects are backed with qualitative assessment and complete quantitative testing. The test approaches are explained and the test code is made available to allow researchers to re-perform these tests.
The Linux Random Number Generator is an API and ABI compatible drop-in replacement to the legacy /dev/random implementation in the Linux kernel.
A public git repository is found at smuellerDD/lrng.
A PDF documentation is also available. The pictures and graphs are better to read in the PDF version.
The following source code contains the implementation of the Linux Random Number Generator.
Removal of the Jitter RNG fast noise source as requested by Ted
Addition of processing of add_input_randomness as suggested by Ted
Update documentation and testing to cover the updates
Addition of a SystemTap script to test add_input_randomness
To clarify the question whether sufficient entropy is present during boot I added one more test in 3.3.1 which demonstrates the providing of sufficient entropy during initialization. In the worst case of no fast noise sources, in the worst case of a virtual machine with only very few hardware devices, the testing shows that the secondary DRBG is fully seeded with 256 bits of entropy before user space injects the random data obtained during shutdown of the previous boot (i.e. the requirement phrased by the legacy /dev/random implementation). As the writing of the random data into /dev/random by user space will happen before any cryptographic service is initialized in user space, this test demonstrates that sufficient entropy is already present in the LRNG at the time user space requires it for seeding cryptographic daemons. Note, this test result was obtained for different architectures, such as x86 64 bit, x86 32 bit, ARM 32 bit and MIPS 32 bit.
Convert debug printk to pr_debug as suggested by Joe Perches
Add missing \n as suggested by Joe Perches
Do not mix in struck IRQ measurements as requested by Pavel Machek
Add handling logic for systems without high-res timer as suggested by Pavel Machek -- it uses ideas from the add_interrupt_randomness of the legacy /dev/random implementation
add per NUMA node secondary DRBGs as suggested by Andi Kleen -- the explanation of how the logic works is given in section 2.1.1 of my documentation , especially how the initial seeding is performed.
port to 4.7-rc1
Use classical twisted LFSR approach to collect entropic data as requested by George Spelvin. The LFSR is based on a primitive and irreducible polynomial whose taps are not too close to the location the current byte is mixed in. Primitive polynomials for other entropy pool sizes are offered in the code.
The reading of the entropy pool is performed with a hash. The hash can be specified at compile time. The pre-defined hashes are the same as used for the DRBG type (e.g. a SHA256 Hash DRBG implies the use of SHA-256, an AES256 CTR DRBG implies the use of CMAC-AES).
Addition of the example defines for a CTR DRBG with AES128 which can be enabled during compile time.
Entropy estimate: one bit of entropy per interrupt. In case a system does not have a high-resolution timer, apply 1/10th bit of entropy per interrupt. The interrupt estimates can be changed arbitrarily at compile time.
Use kmalloc_node for the per-NUMA node secondary DRBGs.
Add boot time entropy tests discussed in section 3.4.3 .
Align all buffers that are processed by the kernel crypto API to an 8 byte boundary. This boundary covers all currently existing cipher implementations.
fix treating LRNG_POOL_SIZE_BITS as entropy value in lrng_get_pool
use CTR DRBG with AES256 as default due to its superior speed -- on X86_64 executing within a KVM I get read speeds of up to 850 MB/s now. When using a fake NUMA system with 4 nodes on 4 CPUs, I still get up to 430 MB/s read speed with four parallel reads. Note, this patch applies to the current cryptodev-2.6 tree.
use DRBG security strengths as defined in SP800-57 section 5.6.1
add security strength to /proc/sys/kernel/random/lrng_type
add ChaCha20 DRNG: in case the kernel crypto API is not compiled, the ChaCha20 DRNG with the SHA-1 C implementations are used to drive the cryptographic part of the LRNG.The ChaCha20 RNG is described in . I analyzed it with a user space version of it.
Editorial changes requested by checkpatch.pl
port to 4.8-rc1
add missing memzero_explicit to ChaCha20 DRNG
use kernel-doc documentation style
use of min3 in lrng_get_pool to beautify code
prevent fast noise sources from dominating slow noise sources in case of /dev/random
set read wakeup threshold to 64 bits to comply with legacy /dev/random
simplify the interrupt to entropy amount conversion code
move wakeup call of entropy-providers to a code location where /dev/urandom will benefit from the wake up as well (i.e. when the primary DRBG entropy runs low because of /dev/urandom reseeds, the entropy provider is woken up)
inject current time into primary DRBG at the time of seeding from noise sources (suggested by Sandy Harris)
port to 4.9-rc1
add lrng_drng_generate_helper_full() function for DRNGs to inform them about requests that shall have the capability to transport close to 1 bit of entropy per data bit
streamline code in lrng_pdrbg_seed_internal
test NUMA code on real NUMA system: fixes of NUMA support code to support deactivated NUMA nodes
constify buffers to crypto operations
port to kernel v4.10-rc1works also on the released linux kernel 4.10
fix race condition in add_interrupt_randomness when low res timer is used
re-add Jitter RNG noise source assumed to provide one 16th bit of entropy per data bit (every source of entropy is helpful)
make LFSR invocation much more efficient in hot code paths
increase reseed threshold of secondary DRBG to 2^17 requests (maximum number of bytes to be generated without reseeding attempt: 2^17 requests * 2^12 bytes per requests)
initialize ChaCha20 key space with time stamp and arch_get_random_long
reseed the secondary DRBG always with full entropy equal to its security strength -- further details are given in section 2.6 of the documentation
add FIPS 140-2 continuous self test to ChaCha20 code path
port to kernel v4.11-rc1
fix race condition in initialization code path of secondary DRBGs
SHA-256 based DRBG have a security strength of 256 bits as per SP800-57A table 3
Increase LRNG_MIN_SEED_ENTROPY_BITS to 128 bits based on updates proposed to FIPS 140-2 and BSI's TR02102
when writing/IOCTL to /dev/random or /dev/urandom, the data is only inserted into the primary DRBG, the secondary DRBG(s) will forcefully reseeded when processing next request for the respective secondary DRBG instead of injecting the input data also into the secondary DRBGs
use ERR_PTR for return code of lrng_drng_alloc
port to kernel v4.11
contintionally compile JitterRNG code depending on CONFIG_CRYPTO_JITTERENTROPY
update error code path when lrng_hash_buffer fails to report the successfully read entropy
remove LRNG_DRBG_BLOCKLEN_BYTES in favor of LRNG_DRBG_BLOCKSIZE
add get_random_u64 and get_random_u32 from legacy /dev/random
port to 4.12-rc1
(identical to code 20170502) contintionally compile JitterRNG code depending on CONFIG_CRYPTO_JITTERENTROPY
(identical to code 20170502) update error code path when lrng_hash_buffer fails to report the successfully read entropy
(identical to code 20170502) remove LRNG_DRBG_BLOCKLEN_BYTES in favor of LRNG_DRBG_BLOCKSIZE
(identical to code 20170502) add get_random_u64 and get_random_u32 from legacy /dev/random to prevent any modifications of random.c
move LRNG to drivers/char/
wakeup user space writers only when entropy in pool is low (not when primary DRBG entropy is low)
LFSR alteration to space the processed words 67 words apart to counter polynomial taps that are close together which may be affected by dependencies
Always mix in an interrupt time stamp even when considered stuck, just do not increment number of collected interrupts used to determine the entropy content
port to 4.13-rc1
use PTR_ERR_OR_ZERO as suggested by Julia Lawall
fixed coccocinelle warnings
fixed cppcheck style hints
all DRNG-specific code is re-allocated to the C files specific to the respective DRNG
rename all macros from DRBG -> DRNG
rename all functions from *drbg* -> *drng*
functions grouped into pdrng and sdrng processing for easier reading
Use Jitter RNG to seed even the init RNG for entropy at earliest boot time which implies that the very first random number generated by the LRNG is seeded with the Jitter RNG
incorporate wait_for_random_bytes from Jason A. Donenfeld
incorporate invalidate_batched_entropy from Jason A. Donenfeld
incorporate debug logs for unseeded DRNGs from Jason A. Donenfeld including rate limiting from Ted Ts'o
rename lrng_standalone.c -> lrng_chacha20.c
bug fix edge condition during reseed on NUMA systems
enable stuck test during early boot
When waiting for "good" random numbers, the following concept applies: - kernel space: reaching the minimally seeded level triggers wakeup - user space: reaching the fully seeded level triggers wakeup
Use RDSEED for seeding operations and RDRAND as a fallback as suggested by DJ Johnston (note, the final fallback to use a high-resolution timer is implicitly present by using the time stamp unconditional for each reseed).
conserve entropy in output function of primary DRNG
port to 4.13 and 4.14-rc1works also on the released linux kernel 4.14
Update drivers/char/Makefile as suggested by Arnd Bergmann
Update use of jitterentropy.c as suggested by Arnd Bergmann
Add runtime loading/unloading of DRNG implementations
Use mutex for locking as kernel crypto API may sleep
Add fix to prandom to prevent calling of get_random_bytes from atomic context
DRBG support: allow run-time switching of DRBG type using lrng_drbg_type insmod parameter
port to 4.15
Covered kernel version: 4.15
Add put_cpu_var in the code paths where get_cpu_var is used in patch 1 (reported by Farin Sami)
Covered kernel version: 4.16
Addition of SPOX copyright identifier
Use the updated poll infrastructure
Add the kernel crypto API PRNG support
Covered kernel version: 4.17
Bug fix in add_device_randomness
async allocation of per-NUMA-node DRNG instances in a work queue
add RNDRESEEDCRNG IOCTL
Covered kernel version: 4.18
Provide full support for get_random_bytes in atomic operations (LRNG is now fully complete for all use cases in the kernel)
Increase performance of ChaCha20 DRNG by using unused random numbers during the update operation - the LRNG speed using ChaCha20 is between 20% (smaller block sizes) and 120% (larger block sizes) higher than the legacy implementation.
Drop patch modifying genhd.h
Covered kernel version: 4.20
Port to 4.20
Covered kernel version: 5.0
Port to 5.0
Covered kernel version: 5.1
Port to 5.1
Fix a bug in error handling
Add raw entropy sampling code
Covered kernel version: 5.2
Port to 5.2
Enhance raw entropy sampling code
Add support for CONFIG_RANDOM_TRUST_CPU
Covered kernel version: 5.4-rc6
breakup of the monolithic code base into several logically isolated files and move all files into drivers/char/lrng/ - this also reduces the number of ifdefs in the code significantly as the make system is used to select the enabled code
Add Tested-by and Reviewed-by lines
Significant speedup of code executing in interrupt handler: the LRNG is now almost 50% faster as the existing /dev/random. On one example system, the LRNG interrupt handling code executes within an average of 65 cycles whereas the existing /dev/random on the same device takes about 97 cycles.
prune base LRNG code of any FIPS-related code - all FIPS-related code is in the SP800-90B compliance code that can be deactivated at compile time
testing performed with all tests offered at  including all required SP800-90B tests, as well as KASAN, UBSAN, and lockdep while executing stress tests. Tests were performed on: x86, S390
make DRNG switching support compile-time configurable
selection of entropy pool size is now a configure option
support deactivation of TRNG (i.e. blocking behavior of /dev/random) at compile time. If deactivated, /dev/random behaves like getrandom(2).
conditionally compile NUMA support
eliminate in_atomic() invocation: In-kernel consumers always use the ChaCha20 DRNG unless the new API call get_random_bytes_full is invoked which may sleep but offer access to the full functionality of the LRNG including all types of DRNG.
use debugfs file for obtaining raw entropy test data required to fulfill SP800-90B requirements
fix: ensure that gathering raw entropy does not affect runtime of the kernel
fix: import upstream patch b7d5dc21072cda7124d13eae2aefb7343ef94197
fix: import upstream patch 428826f5358c922dc378830a1717b682c0823160
fix: integrate patch "random: Don't freeze in add_hwgenerator_randomness() if stopping kthread"
documentation enhancement: import upstream patch 92e507d216139b356a375afbda2824e85235e748 into documentation to cover all interfaces of the LRNG
speedup of injection of non-aligned data into entropy pool
Remove of the boiler plate disclaimers as requested by Thomas Gleixner
fix compile issues reported by kbuild: adding missing header files and turn large stack variable into a heap variable with lrng_testing.c
fix patch descriptions as suggested by Florian Weimer and Alexander E. Patrakov
remove stale comment in _lrng_sdrng_seed
ove blocking of /dev/random and getrandom(GRND_RANDOM) until LRNG is seeded to the interface handling code to simplify the code and to ensure the blocking is also enforced if the TRNG is not compiled.
add BROKEN test support for SP800-90B adaptive proportion test and repetitive count test as suggested by Alexander E. Patrakov
Extract the time initalization code into its own function lrng_init_time_source and invoke it with core_initcall as reported by Nicolai Stange
Add linux/errno.h include to lrng.h as suggested by Nicolai Stange
Add linux/slab.h to lrng_chacha20.h
Changed lrng_testing.c reading/writing of ring buffer to use a lock as suggested by Andy Lutomirski
Use "depends on DEBUG_FS" for lrng_testing.c Kconfig entry as suggested by Randy Dunlap
Remove declaration of random_table from lrng_proc.c as suggested by Eric W. Biederman
Move the lrng_type file out of the sysctl table into its own file /proc/lrng_type since its purpose is not to serve as a sysctl as suggested by Eric W. Biederman
Update patch description for /proc patch to refer to sysctls as suggested by Eric W. Biederman
/dev/random and getrandom(GRND_RANDOM) now invokes the secondary DRNG ensuring that the DRNG is fully seeded before requests are served. With this change, /dev/random is no TRNG any more. This change implements the suggestion from Andy Lutomirski and is based on the discussions previously on the LKML and the changes developed by Andy for the existing random.c implementation.
Simplification of the debugfs code in lrng_testing.c as return code checks are not further needed any more as suggested by Nicolai Stange.
Addition of GRND_TRUERANDOM to the getrandom(2) syscall to make the TRNG externally accessible as a TRNG. The change also includes the GRND_INSECURE flag as proposed by Andy Lutomirski. To avoid touching the random.h and potentially clashing with Andy's patch set, I kept the symbol definitions in lrng_interfaces.c noting that they should be moved to random.h. The GRND_TRUERANDOM allows unprivileged user space to access the TRNG as follows: if CAP_SYS_ADMIN calls, the whole entropy available to the LRNG is used. If an unprivileged process invokes GRND_TRUERANDOM, at least 1024 bits of entropy will remain in the pool to serve CAP_SYS_ADMIN and all secondary DRNGs serving /dev/urandom, /dev/random and getrandom(.., 0) with entropy. With that unprivileged processes calling GRND_TRUERANDOM have the lowest priority in getting entropy and must wait accordingly. If the TRNG is not present, GRND_TRUERANDOM returns -EOPNOTSUPP. A new test tool is provided as part of the LRNG test archive found at  allowing to analyze all four types of RNGs accessible via getrandom(2).
Remove duplication of MODULE_LICENSE/AUTHOR/DESCRIPTION from lrng_testing.c