Non-physical true random number generator

Non-physical true random number generator (NPTRNG), also known as non-physical nondeterministic random bit generator is a true random number generator that does not have access to dedicated hardware entropy source. NPTRNG uses a non-physical noise source that obtains entropy from system data, like outputs of application programming interface functions, residual information in the random access memory, system time or human input (e.g., mouse movements and keystrokes). A typical NPTRNG is implemented as software running on a computer. The NPTRNGs are frequently found in the kernels of the popular operating systems that are expected to run on any generic CPU (for example /dev/random in Linux).

Reliability

An NPTRNG is inherently less trustworthy that its physical random number generator counterpart, as the non-physical noise sources require specific conditions to work, thus the entropy estimates require major assumptions about the external environment and skills of an attacker.

Typical attacks include:

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

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

Implementations

The design of an NPTRNG is traditional for TRNGs: a noise source is followed by a postprocessing randomness extractor and, optionally, with a pseudorandom number generator (PRNG) seeded by the true random bits. For example, in Linux, the /dev/random does not use the PRNG (and thus can block when it needs to collect more entropy), while /dev/urandom includes one (and therefore can always provide more bits and is non-blocking).

As of 2014, the Linux NPTRNG implementation extracted the entropy from:

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

At the time, testing in virtualized environments had shown that there existed a boot-time "entropy hole" (reset vulnerability) when the early (u)random outputs were catastrophically non-random, but in general the system provided enough uncertainty to thwart an attacker.

Sources

• Turan, Meltem Sönmez; Barker, Elaine; Kelsey, John; McKay, Kerry A; Baish, Mary L; Boyle, Mike (2018). NIST SP800-90B: Recommendation for the entropy sources used for random bit generation (Report). Gaithersburg, MD: National Institute of Standards and Technology. doi:10.6028/nist.sp.800-90b.
• Schindler, Werner (2008). "Random Number Generators for Cryptographic Applications". In Koc, C.K. (ed.). Cryptographic Engineering. Boston, MA: Springer US. pp. 5–23. doi:10.1007/978-0-387-71817-0_2. ISBN 978-0-387-71817-0. Retrieved 2024-08-24.
• Peter, Matthias; Schindler, Werner (September 2, 2022). A Proposal for Functionality Classes for Random Number Generators (2.35 DRAFT ed.). Bundesamt für Sicherheit in der Informationstechnik.
• Hall, Tim (29 April 2021). "Non-physical entropy sources" (PDF). NIST.
• Everspaugh, Adam; Zhai, Yan; Jellinek, Robert; Ristenpart, Thomas; Swift, Michael (2014). Not-So-Random Numbers in Virtualized Linux and the Whirlwind RNG (PDF). 2014 IEEE Symposium on Security and Privacy. IEEE. pp. 559–574. doi:10.1109/SP.2014.42. ISBN 978-1-4799-4686-0.