Generating Pseudorandom Numbers and Sequences for Cryptography

Every time you log into your bank account, send a WhatsApp message, or make an online payment, cryptography protects your information. But there’s a hidden challenge at the heart of cryptographic security: generating numbers that are truly unpredictable. This is where pseudorandom number generators come in, serving as the foundation for encryption keys, digital signatures, and secure communications.

Why randomness matters in cryptography 🔗

Cryptographic systems depend on unpredictability. When you generate an encryption key, it needs to be random enough that attackers cannot guess it. True randomness usually requires sampling data from unpredictable physical processes, such as circuit noise on a CPU, random signal variations, or the precise microsecond when a user presses a key. However, generating truly random numbers this way is computationally expensive and slow.

The solution is to use pseudorandom numbers. These are numbers generated by algorithms that appear random but are actually produced through deterministic processes. The key requirement is that the generated sequences must be computationally indistinguishable from truly random numbers to anyone who doesn’t know the initial starting point.

Understanding pseudorandom number generators 🔗

A Pseudorandom Number Generator (PRNG) is a deterministic algorithm that takes a small amount of truly random bits (called a seed) and produces a much longer sequence of numbers that appear random. The generator is deterministic, meaning that anyone using the same seed will get the same sequence of numbers. However, without knowing the seed, an attacker cannot predict the output.

How PRNGs work 🔗

PRNGs maintain an internal state that gets updated each time new numbers are generated. A typical PRNG has three core functions: Seed (to initialize the generator), Reseed (to add fresh entropy), and Generate (to produce pseudorandom bits). This design allows the generator to produce as many random numbers as needed from a single initial seed.

For example, imagine you need to generate 1000 encryption keys. Instead of collecting 1000 separate truly random values, you can use one truly random seed to initialize a PRNG, which then efficiently generates all 1000 keys.

Cryptographically secure pseudorandom number generators 🔗

Not all PRNGs are suitable for cryptography. A Cryptographically Secure Pseudorandom Number Generator (CSPRNG) must meet stricter requirements than standard PRNGs used in simulations or games. Every CSPRNG must satisfy the next-bit test, meaning that given any sequence of bits, no efficient algorithm can predict the next bit with significantly better than 50% probability.

Key requirements for CSPRNGs 🔗

Unpredictability: The security of cryptographic systems depends heavily on the properties of CSPRNGs. If attackers can predict even part of the sequence, they might be able to break the encryption.

Rollback resistance: If an attacker somehow learns the internal state of a CSPRNG at one point in time, they should not be able to determine any previously-generated numbers. This property prevents attackers from recovering past encryption keys even if they compromise the system later.

Entropy stretching: CSPRNGs can stretch limited available entropy over more bits, making them practical for systems where gathering fresh entropy is slow.

Common CSPRNG algorithms 🔗

Several standardized CSPRNG algorithms are widely used in practice. The NIST SP 800-90A standard specifies three approved mechanisms: Hash_DRBG (based on cryptographic hash functions), HMAC_DRBG (based on HMAC), and CTR_DRBG (based on block ciphers in counter mode).

HMAC-DRBG 🔗

HMAC-DRBG is one of the most commonly-used CSPRNGs, which uses the security properties of HMAC to build a secure generator. It maintains two internal values: a key K and a value V. To generate pseudorandom output, it repeatedly computes HMAC using the previous output as input. Since HMAC output appears random to anyone who doesn’t know the key, the generated sequence is cryptographically secure.

HMAC-DRBG has several advantages. It can accept arbitrarily long seeds, provides rollback resistance, and adding extra data (even data with no entropy) doesn’t weaken the generator’s security.

Hash_DRBG and CTR_DRBG 🔗

Hash_DRBG uses cryptographic hash functions like SHA-256 to generate pseudorandom bits, while CTR_DRBG uses block cipher algorithms like AES in counter mode. These algorithms have been in use for over a decade and are required for all key generation in systems requiring FIPS 140 validation.

Challenges in random number generation 🔗

Designing and implementing secure random number generators is extremely difficult. Several challenges arise in practice:

Seed quality: The entropy used for seeding must be truly unpredictable, as any predictability in the seed compromises the entire system. Operating systems typically gather entropy from hardware events, timing variations, and environmental noise.

Entropy availability: Systems sometimes need random numbers faster than they can gather fresh entropy. CSPRNGs address this by stretching available entropy, but if the initial entropy pool is insufficient, the generated numbers may be predictable.

Implementation vulnerabilities: Even well-designed algorithms can be compromised by implementation flaws. For instance, the Dual_EC_DRBG algorithm included in an earlier NIST standard was later shown to contain a backdoor, leading to its removal from the standard in 2015.

Practical implications for developers 🔗

When developing cryptographic applications, always use your platform’s recommended CSPRNG. In Windows, use BCryptGenRandom; in Python, use os.urandom() or the secrets library; in Java, use java.security.SecureRandom. Never use standard random number functions like C’s rand() or JavaScript’s Math.random() for cryptographic purposes, as these lack the necessary security properties.

Understanding the difference between standard PRNGs and CSPRNGs is crucial. Standard PRNGs may be sufficient for simulations or games, but only CSPRNGs provide the unpredictability needed for encryption keys, authentication tokens, and other security-critical values.

The role of true random number generators 🔗

While CSPRNGs are essential for most cryptographic applications, some high-security systems also use True Random Number Generators (TRNGs). TRNGs capture physical processes like thermal noise or quantum phenomena, and modern CPUs provide built-in hardware random generators accessible through special instructions.

Many robust cryptographic systems combine both approaches: using a TRNG to periodically reseed a CSPRNG. This provides the unpredictability of true randomness with the efficiency of pseudorandom generation.

What do you think? How confident are you in the random number generators used by the applications you rely on daily? What additional security measures might help protect cryptographic systems if a random number generator is compromised?

References

1. https://textbook.cs161.org/crypto/prng.html
2. https://en.wikipedia.org/wiki/Pseudorandom_number_generator
3. https://csrc.nist.gov/glossary/term/pseudorandom_number_generator
4. https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
5. https://www.veracode.com/blog/research/cryptographically-secure-pseudo-random-number-generator-csprng
6. https://en.wikibooks.org/wiki/Cryptography/Random_number_generation
7. https://nvlpubs.nist.gov/nistpubs/specialpublications/nist.sp.800-90ar1.pdf
8. https://www.safelogic.com/blog/introduction-to-the-sp-800-90-series-requirements-on-random-number-generation
9. https://www.cryptomathic.com/blog/the-role-of-random-number-generators-in-cryptography
10. https://en.wikipedia.org/wiki/NIST_SP_800-90A
11. https://cryptobook.nakov.com/secure-random-generators/secure-random-generators-csprng