The Basics of PRNGs

Abstract

Most modern encryption and authentication methods rely on generating random numbers for key generation, initial vectors, or nonces. A Random Number Generator is cryptographically secure if the sequences of numbers that it generates are unpredictable. They are typically grouped into two categories: Pseudo-Random Number Generators and True Random Number Generators. Small-size, low-cost true Random Number Generators have already been integrated into off-the-shelf devices such as smartphones, computers, and hardware security modules. In addition, applications involving particularly sensitive data can combine the output from two or more independent sources of randomness for improved security.

Introduction

Most modern encryption and authentication methods rely on the generation of random numbers, such as for key generation, initial vectors, or nonces. Therefore, a reliable source of entropy is fundamental in making encryption and authentication methods secure - weak sources of randomness can compromise otherwise secure encryption and authentication schemes.

Analysis

Definition

A Random Number Generator (RNG) is cryptographically secure if the sequences of numbers that it generates are unpredictable. RNGs are typically grouped in two categories: Pseudo-Random Number Generators (PRNG) and True Random Number Generators (TRNG).

PRNGs depend on a seed value, from which a seemingly erratic albeit deterministic sequence is produced; it is a quick and debug-friendly version of RNGs often used in statistical applications. They are not suitable for cryptographic applications in isolation. However, they may be used when correctly combined (seeded) with a reliable entropy source.

TRNGs rely on physical phenomena, e.g., radioactive decay, thermal noise, small-scale hardware activity, or particular hardware based on quantum physics (abbreviated QRNG). As it is hard to balance physical processes such that the probability of 0's and 1's is exactly ½, the output of TRNGs must be adequately post-processed. Secure mixing functions such as hash functions or symmetric encryption schemes may produce unbiased output. These mixing functions also remove serial dependence between bits. An excellent example of such an implementation is the Linux kernel RNG /dev/urandom.

Quantum RNGs are often presented as the only means to protect infrastructure against future powerful quantum computers. However, this is misleading, as any reliable source of randomness remains unpredictable against any adversary with arbitrary computing power.

Trends

Small-size, low-cost QRNGs have already been integrated into off-the-shelf devices such as smartphones, computers, and hardware security modules.

Consequences for Switzerland

People, businesses, and authorities in Switzerland should continue using and promoting research on secure random hardware number generators. This will ensure that they can benefit from the newest technological advances when they become available.

Implementation Possibilities: Make or Buy

Using secure RNGs that cannot be manipulated or tampered with and whose output is not predictable is fundamental as a basis for encryption methods. Applications involving particularly sensitive data can combine the output from two or more independent sources of randomness for improved security. PRNGs, which produce deterministic outcomes, must not be used in cryptography in isolation and must at least blend in TRNG's randomness.

Open-source solutions such as the Linux kernel RNG /dev/urandom are considered reliable. Hardware products dedicated to producing randomness from reliable and reputable producers can be used as a complement after appropriate verification and approval.

Several companies are operating in the TRNG market, e.g., developing QRNG chips that can be integrated into hardware. A few companies selling QRNG chips or systems are listed in Table 7.1. These QRNG chips do not offer stronger guarantees than other TRNGs; they are just another means of potentially generating cryptographically secure randomness.

Table 7.1 Different companies active in the QRNG field

Company	Description	Technology	Country
ID Quantique	Technology pioneers, well established, integrated into a chip, promote cost-effectiveness.	Photonic (Optical)	Switzerland (Linked to South Korea through SK Telecom)
Quintessence Labs	Well established, fastest generators, not chip integrated	Barrier Tunneling	Australia
RandomPower	Newcomers, growing, qualification and MVP in place, offers new technology. RUAG Switzerland ran tests on their products.	In-silico	Italy

Variation and Recommendation

RNGs should be appropriately isolated and integrity protected to prevent tampering or access to internal states that could leak information about the random sequence. Combining the output of several RNGs (e.g., using XOR) can mitigate the potential weaknesses of individual RNGs.
The US National Institute of Standards and Technology (NIST) published a range of hypothesis tests that can provide evidence of potentially complex dependence patterns. Its German equivalent (Bundesamt für Sicherheit in der Informationstechnik, BSI) also suggests a suite of tests. These tests do not provide proof of randomness; they can, at best, reject the null hypothesis that a specific dependence pattern occurs in a sequence at a given confidence level. The longer the test sequence, the more confidence can be placed in the test results. A good understanding of the inner workings of a TRNG is key to assuring the unpredictability of its output.

Conclusion

A reliable source of randomness is critical to ensuring the security of most modern encryption and authentication systems. Unfortunately, pseudo-random number generators are not suited in such a context, except if suitably combined with a reliable entropy source.

Proving that a source of bits is truly random is impossible on finite sequences, but statistical test suites exist that provide evidence against non-randomness. Good physical sources of entropy must be chained with robust post-processing techniques to remove biases and serial dependencies.

Standard tools like /dev/urandom on Linux systems provide a good source of random numbers based on multiple hardware-based entropy sources. Additional security can be achieved by combining independent RNGs, typically based on physical processes of different types, e.g., quantum physics.

---

Source: Thomas Lugrin, https://link.springer.com/chapter/10.1007/978-3-031-33386-6_7#:~:text=Most%20modern%20encryption%20and%20authentication,that%20it%20generates%20are%20unpredictable.
This work is licensed under a Creative Commons Attribution 4.0 License.