Non-physical true random number generator

From HandWiki
Short description: Type of random number generator

A non-physical true random number generator (NPTRNG),[1] also known as a non-physical nondeterministic random bit generator, is a generator of unpredictable random numbers without the use of a dedicated hardware entropy source.[2] An NPTRNG uses a non-physical noise source that obtains entropy from system data, such as outputs of application programming interface functions, residual information in random access memory, system time, or human input (e.g., mouse movements and keystrokes),[3][1] in the expectation that that data may contain elements that are truly random or at least not known to or controllable by an adversary. A typical NPTRNG is implemented as software running on a general-purpose computer.[1] NPTRNGs are found in the kernels of popular operating systems[4] that are expected to run on any generic CPU without requiring specialised hardware.

Classification

Within the taxonomy established by NIST Special Publication 800-90B,[3] random number generation components are classified as either entropy sources or deterministic random bit generators (DRBGs). An NPTRNG functions primarily as an entropy source: it accumulates unpredictable data from the environment, conditions it to produce uniform bits, and optionally seeds a DRBG (such as CTR DRBG, Hash_DRBG or HMAC_DRBG) to produce an essentially unlimited output stream.

The German Bundesamt für Sicherheit in der Informationstechnik (BSI) classification in AIS 31 distinguishes between PTG.1 (physical true RNG with online test), PTG.2 (physical true RNG with online and offline test), and NTG.1 (non-physical true RNG), where an NTG.1 generator must pass defined statistical tests and demonstrate that each output block contributes at least one bit of entropy to the internal state.[5]

In practice, operating-system random number subsystems are hybrid: a true-entropy accumulator (the NPTRNG component) seeds an internal DRBG that handles the bulk of output generation. This design separates the entropy-gathering problem from the output-generation problem, and means that the DRBG's output rate is not limited by the rate at which environmental entropy can be collected.

Reliability

An NPTRNG is inherently less trustworthy than its physical random number generator counterpart, because the non-physical noise sources depend on specific conditions to function, and entropy estimates require significant assumptions about the external environment and the capabilities of an attacker.[5] Typical attacks include:[6]

  • vulnerability to an adversary with system access (just like any software-based TRNG);
  • an attacker supplying a predictable source of events (for example, a mouse simulator);
  • operating in an environment where the assumptions about system behaviour no longer hold (for example, inside a virtual machine).

A more sophisticated attack in 2007 breached the forward secrecy of the NPTRNG in Windows 2000 by exploiting implementation flaws.[7]

Reset and cloning vulnerabilities in virtualised environments

Virtualisation introduces a class of problems specific to NPTRNGs. When a virtual machine is cloned or restored from a snapshot, its internal state — including the PRNG seed and entropy pool — is reset to a prior value. Any two cloned instances will then produce identical random output until they have gathered sufficient fresh environmental entropy, a condition known as the reset vulnerability or "entropy hole".[8] Early-boot randomness in virtualised environments is particularly affected because the pool is nearly empty and the sources of entropy (disk I/O, interrupts) are more deterministic than on bare metal. Mitigations include persisting a seed file across reboots, using RDRAND / RDSEED instructions where available, and querying a virtual hardware RNG (e.g., VirtIO RNG or VMware's virtual RNG device).

Implementations

The design of an NPTRNG follows the general TRNG pattern: a noise source is followed by a conditioning randomness extractor and, optionally, a pseudorandom number generator (PRNG) seeded by the true-random bits.

Linux

In Linux, the /dev/random character device requires a true-random seed and can block when the kernel needs to collect more entropy (particularly at boot time), while /dev/urandom is always non-blocking.[9][10] As of 2025, the Linux NPTRNG implementation extracts entropy from:[11][12]

  • interrupts, mixing CPU cycle counter, kernel timer value, IRQ number and instruction pointer of the interrupted instruction into a "fast pool";
  • random-time I/O (events from keyboard, mouse and disk), mixing kernel timer value, cycle counter and device-specific information into the "input pool".

Hardware performance counters have been proposed as an additional entropy source, as they reflect micro-architectural non-determinism that is difficult for an attacker to observe or control.[13][14]

Since Linux 5.17, /dev/random and /dev/urandom have used identical output from the same ChaCha20-based CRNG, with blocking only at very early boot until the pool has been seeded with sufficient entropy; the historical distinction between them for post-boot use was removed.

Windows

The Windows operating system exposes its NPTRNG through the CNG function BCryptGenRandom (and its predecessor CryptGenRandom). The Windows entropy accumulator collects from sources including system interrupt timing, process and thread identifiers, memory allocation addresses, network packet timing and user-interface event timing. On processors supporting RDRAND, Windows uses the instruction to supplement the software entropy pool. The Data Protection API and TLS stack both draw from the same underlying CRNG.

OpenBSD

OpenBSD's arc4random is the user-space and kernel interface to its random number subsystem. The kernel entropy pool is seeded from interrupt jitter, hardware RNG instructions (RDRAND/RDSEED on x86, equivalent instructions on ARM), and a seed stored across reboots. The pool feeds a ChaCha20 stream cipher, and address-space layout randomisation (ASLR) is applied to all processes at fork time, providing per-process key separation.

Entropy estimation

A central challenge in NPTRNG design is entropy estimation: quantifying how much unpredictability each source actually contributes, independently of what an attacker might know. NIST SP 800-90B defines a suite of entropy estimators that treat the source as a black box and bound its min-entropy (the negative log of the probability of the most likely output), rather than Shannon entropy, because min-entropy is the operationally correct measure for security.[2] Sources are tested with estimators including the most-common-value estimate, the collision estimate, the Markov estimate and a compression estimate; the minimum across all estimators is taken as the conservative bound.

Underestimating entropy leads to a system that generates insufficient randomness; overestimating allows an attacker to predict outputs. The difficulty is that the quantity of entropy in, for example, an interrupt timing measurement depends on the specific hardware and workload, and cannot be determined analytically.

See also

References

  1. ↑ 1.0 1.1 1.2 Schindler 2008, p. 18.
  2. ↑ 2.0 2.1 Turan et al. 2018, p. 64.
  3. ↑ 3.0 3.1 Turan et al. 2018, p. 5.
  4. ↑ Hall 2021.
  5. ↑ 5.0 5.1 Peter & Schindler 2022, p. 61.
  6. ↑ Peter & Schindler 2022, p. 62.
  7. ↑ Schindler 2008, p. 20.
  8. ↑ Everspaugh et al. 2014, p. 573.
  9. ↑ Schindler 2008, pp. 18–19.
  10. ↑ Everspaugh et al. 2014, p. 560.
  11. ↑ Everspaugh et al. 2014, p. 561.
  12. ↑ Bouez, Daemen & Mennink 2025, p. 600.
  13. ↑ Bouez, Daemen & Mennink 2025, p. 601.
  14. ↑ Alam et al. 2020, pp. 3–19.

Sources



Retrieved from "https://handwiki.org/wiki/index.php?title=Non-physical_true_random_number_generator&oldid=4416726"