RNG Attacks: How Random Are Your Numbers?

TL;DR

Random number generators (RNGs) aren’t truly random. They’re algorithms, and if an attacker understands the algorithm or has access to its internal state, they can predict future numbers. This guide covers common attacks and how to protect against them.

Understanding the Problem

Computers need randomness for things like security keys, simulations, and games. True randomness is hard to get, so we use Pseudo-Random Number Generators (PRNGs). These are algorithms that *look* random but are actually deterministic – given the same starting point (‘seed’), they’ll always produce the same sequence of numbers.

Attacks on Random Number Generators

1. Seed Prediction: If an attacker can guess or discover the seed value used to initialise the PRNG, they can recreate the entire number stream.
2. State Recovery: Some RNGs have relatively small internal states. An attacker who can observe enough output from the generator might be able to reconstruct that state and predict future values.
3. Bias Detection: Even if an attacker can’t fully predict numbers, they might detect statistical biases in the output (e.g., certain numbers appearing more often than expected). This weakens security.
4. Side-Channel Attacks: These attacks don’t target the algorithm directly but exploit information leaked during its execution – like timing variations or power consumption.

Practical Attack Examples

1. Linear Congruential Generator (LCG) Weakness: LCGs are simple and fast, but easily predictable if you know a few consecutive outputs.

   # Example in Python - very insecure! 
   seed = 12345
   a = 1664525
   c = 1013904223
   m = 2**32
   def lcg(x):
     return (a * x + c) % m
   
   for i in range(10):
     seed = lcg(seed)
     print(seed)

2. /dev/random vs. /dev/urandom on Linux: /dev/random blocks if not enough entropy is available, making it more secure but slower. /dev/urandom doesn’t block and uses a PRNG seeded from system noise. If the system lacks sufficient initial entropy, /dev/urandom can become predictable.

   cat /dev/random  # Blocks until enough entropy
   cat /dev/urandom # Non-blocking, may be less secure initially

3. Predictable Seeds in Web Applications: If a web application uses the current timestamp as a seed without sufficient mixing (e.g., adding other random data), an attacker could predict numbers if they know when the server generated them.

How to Protect Against RNG Attacks

1. Use Cryptographically Secure PRNGs (CSPRNGs): These are designed specifically for security and resist many attacks. Examples include:
   • Fortuna: A robust CSPRNG algorithm.
   • ChaCha20/XORoshiro128+: Modern, fast CSPRNGs.
   • System Libraries: Use the built-in CSPRNG functions provided by your operating system or programming language (e.g., openssl rand in OpenSSL, secrets module in Python).
2. Proper Seeding:
   • Gather Sufficient Entropy: Collect enough random data from reliable sources (hardware RNGs, system noise, etc.).
   • Mix the Seed Well: Combine multiple entropy sources using strong cryptographic hash functions.
   • Re-seed Regularly: Periodically update the seed with fresh entropy.
3. Avoid Weak Algorithms: Don’t use simple RNGs like LCGs for security-critical applications.
4. Protect Internal State: Ensure that the internal state of the PRNG is kept secret and protected from tampering.
5. Regular Audits & Testing: Periodically review your RNG implementation and test its randomness properties using statistical tests (e.g., NIST Statistical Test Suite).

Resources

• Random.org – True random number generator.
• CSPRNG Wikipedia Page