After completing this tutorial, you should be able to:
Random numbers are the invisible foundation of modern cryptography. Every cryptographic operation relies on randomness: encryption keys, nonces, initialization vectors, salts, and padding values all require random numbers. If an adversary can predict or influence the randomness used in a cryptographic system, the system's security can be completely compromised.
In this tutorial, we explore the generation of random numbers for cryptographic use. We begin by defining entropy and randomness, distinguishing between true random (physical) sources and pseudorandom (algorithmic) generation. We examine the properties of cryptographically secure pseudorandom number generators (CSPRNGs) and the standards that govern them (e.g., NIST SP 800-90A/B/C, FIPS 140-2/3).
We then focus on key generation—the process of creating cryptographic keys from random material. We discuss the requirements for generating keys of different types (symmetric, asymmetric, and ephemeral) and the key lifecycle management process: generation, distribution, storage, usage, revocation, and destruction. Finally, we examine real-world failures (such as the Debian OpenSSL RNG vulnerability) and the lessons learned.
Understanding random number generation is essential for designing secure cryptographic systems. Without a reliable source of randomness, even the strongest encryption algorithm is vulnerable to attack.
In Tutorials 2.1–2.7, we studied cryptographic algorithms and modes. This tutorial explains how the keys and nonces used in those algorithms are generated. Tutorial 2.9 will cover hash functions, which also rely on random salts and other random values for security.
Cryptographic randomness is required for many purposes:
If the randomness is weak, an attacker can:
For example, a 128-bit key should have 128 bits of entropy, meaning all 2¹²⁸ possible keys are equally likely. If the key is generated from a source with only 32 bits of entropy, an attacker can guess it in 2³² attempts.
Estimating Entropy: Entropy is measured in bits. For a random variable X with possible values x₁, x₂, ..., xₙ and probabilities p₁, p₂, ..., pₙ, the Shannon entropy is:
H(X) = –∑ pi log₂ pi
For a uniform distribution over 2n values, H(X) = n bits.
In practice, entropy sources (e.g., mouse movements, keystrokes, hardware noise) are measured to estimate how much random data they provide.
A TRNG generates random numbers from physical phenomena that are inherently unpredictable. Examples:
TRNGs produce bits that are statistically independent and unpredictable, even if the generation process is known. However, they are typically slow (low bit rate) and require careful design to avoid biases and correlations.
A PRNG is an algorithm that takes a random seed as input and produces a deterministic sequence of numbers that appears random. The sequence is completely determined by the seed; if the seed is known, the entire sequence is known.
PRNGs are fast and produce a long stream of values from a small seed. They are used extensively in cryptography, but they are not unpredictable if the seed is known or guessed.
Seed: The initial input to a PRNG. The seed must contain sufficient entropy to make the output unpredictable.
| Feature | TRNG | PRNG |
|---|---|---|
| Source | Physical phenomena | Algorithmic |
| Unpredictability | Fundamentally unpredictable | Deterministic; predictable if seed known |
| Speed | Slow (kbps to Mbps) | Very fast (Gbps) |
| Bias/Correlation | May have bias, needs conditioning | Uniform if well-designed |
| Reproducibility | Not reproducible | Reproducible with same seed |
| Use | Seeding PRNGs | Generating keys, nonces, etc. |
PRNGs are widely used in cryptography because they are fast, reproducible (useful for testing), and can generate long sequences from a small seed. However, they must be carefully designed to be cryptographically secure.
Common PRNG Algorithms:
A CSPRNG is a PRNG with the property that its output is unpredictable to an attacker who does not know the seed. More formally, given the first k bits of output, an attacker cannot predict the next bit with probability significantly greater than 1/2.
Properties of CSPRNGs:
NIST specifies three Deterministic Random Bit Generators (DRBGs):
These DRBGs use a seed (entropy input) and produce a stream of random bits. They are designed to be resilient to various attacks and are suitable for cryptographic key generation.
A simple but secure CSPRNG can be built using a cryptographic hash function:
State = Seed (initialized with entropy) Output = Hash(State) State = State + 1 (or increment counter)
This is essentially the Hash_DRBG simplified. The output is unpredictable if the seed has sufficient entropy and the hash function is strong.
Entropy is the raw randomness from physical or system-level sources. The quality of entropy directly affects the security of the generated keys.
Entropy sources often produce biased or correlated bits. The raw data must be conditioned (e.g., hashed) to produce a uniform random string. Cryptographic hash functions are commonly used for this purpose.
Entropy Pool: Many systems maintain an entropy pool (e.g., /dev/random on Linux) that collects entropy from various sources and provides random numbers when requested.
Key generation is the process of creating cryptographic keys from random material. The requirements depend on the type of key:
A symmetric key (e.g., AES key) should be a uniformly random bit string of the appropriate length (128, 192, or 256 bits). The generation process is simply to take random bits from a CSPRNG.
Workflow:
1. Obtain entropy from a trusted source (HRNG or system RNG). 2. Use a CSPRNG (e.g., CTR_DRBG) to generate the required number of bits. 3. Optionally, verify that the key is not a weak key (for algorithms with weak keys, though AES has no weak keys).
Asymmetric key generation involves finding primes (RSA) or random points (ECC). The randomness must be of high quality because the security depends on the randomness of the chosen primes or private keys.
RSA Key Generation:
The random primes must be generated from a CSPRNG with sufficient entropy to make them unpredictable.
Sometimes keys are derived from passwords or other shared secrets. Key derivation functions (KDFs) like PBKDF2, bcrypt, or HKDF are used to transform a low-entropy secret into a cryptographic key. These functions incorporate salt and iterated hashing to slow down brute-force attacks.
Key management is the set of processes for handling cryptographic keys from creation to destruction. The key lifecycle includes:
Several standards define random number generation and key management:
| Standard | Description |
|---|---|
| NIST SP 800-90A | Recommendation for Random Number Generation Using Deterministic Random Bit Generators (DRBG). |
| NIST SP 800-90B | Recommendation for the Entropy Sources Used for Random Bit Generation. |
| NIST SP 800-90C | Recommendation for Random Bit Generator (RBG) Constructions. |
| FIPS 140-2/3 | Security Requirements for Cryptographic Modules (includes RNG requirements). |
| ISO/IEC 18031 | Random bit generation. |
| RFC 4086 | Randomness Requirements for Security. |
These standards provide guidance on designing, testing, and validating random number generators for cryptographic use. For example, FIPS 140-2 requires that the RNG be validated through a rigorous testing process.
In 2008, a serious vulnerability was discovered in the OpenSSL library used in Debian and Ubuntu Linux distributions. The vulnerability was introduced by a change in the OpenSSL code that removed the entropy sources for the random number generator.
The Bug: In Debian's version of OpenSSL, the maintainer removed a line of code that initialized the RNG with entropy from various system sources. This was done to silence a warning about uninitialized memory. As a result, the RNG used only the process ID as the source of randomness. The process ID typically has only 15 bits of entropy (on 32-bit systems, about 2¹⁵ possible values).
Impact: The effective key space was reduced to 2¹⁵ possible keys. An attacker could generate all possible keys and break any encryption or signing keys generated on affected systems. SSL/TLS certificates, SSH keys, and other cryptographic materials were compromised.
Consequences:
Lessons Learned:
A password is chosen uniformly from a set of 106 possible passwords. What is the entropy of the password in bits?
Entropy H = log₂(number of possibilities) = log₂(10⁶) ≈ 19.93 bits.
So the password has about 20 bits of entropy.
Suppose a PRNG is seeded with the current time in seconds (UNIX timestamp) and the process ID (PID). The UNIX timestamp has 31 bits (up to 2¹⁰³⁰?) Actually, about 31 bits (up to year 2038 issue) and PID typically 16 bits. What is the maximum entropy of the seed? If an attacker can guess the time within a 1-hour window, how many guesses are needed?
Maximum entropy = 31 + 16 = 47 bits (if both are perfectly uniform and independent).
If the attacker knows the time within a 1-hour window (3600 seconds), that reduces the time entropy to about log₂(3600) ≈ 11.8 bits. Total ≈ 27.8 bits, so about 2²⁸ ≈ 2.7×10⁸ guesses needed.
This demonstrates that predictable seeds reduce the effective key space.
Explain why a linear congruential generator (LCG) is not suitable for generating cryptographic keys. What property of an LCG makes it predictable?
An LCG has the form Xn+1 = (a·Xn + c) mod m. Given a few outputs, an attacker can solve for the parameters (a, c, m) and predict future outputs. This makes it completely predictable, violating the unpredictability requirement of a CSPRNG.
You are tasked with storing a private RSA key for a web server. What are the security considerations for storing this key? What methods would you recommend?
Considerations: The private key must be protected from unauthorized access. It should not be stored in plaintext. It should be stored in a secure location with access controls. Recommendations: Store the key in an encrypted form (e.g., using a passphrase or encrypted with a master key). Use a hardware security module (HSM) for high-security environments. Ensure that the key is accessible only to the web server process (least privilege). Regularly back up the key securely.
List three sources of entropy that a system could use. For each, explain a potential weakness or attack.
Read the NIST SP 800-90A standard (or a summary) and write a 500-word summary that explains:
Complete answer would describe each DRBG's construction, how it uses the seed, and how it generates output. It would also discuss the importance of reseeding with additional entropy to maintain forward secrecy. It would mention that the security strength is tied to the underlying primitive (e.g., AES-256 provides 256-bit strength for CTR_DRBG).
Research the Debian OpenSSL RNG vulnerability (CVE-2008-0166) in depth. Write a 600-word report that covers:
Complete answer would include that the bug was introduced in 2006 and affected all keys generated on Debian/Ubuntu until 2008. It would explain the removal of entropy sources and the reduction of the key space to 2¹⁵. The impact included SSL certificates, SSH keys, and GPG keys. The fix restored entropy collection and advised regenerating all keys.
Design a key management policy for a small organization that uses encryption for data at rest and in transit. Include:
Complete answer would outline a policy with specific requirements: keys must be generated from a validated CSPRNG; stored encrypted with a master key in a secure vault; distributed via secure channels; rotated annually (or upon compromise); revoked if compromised; destroyed securely (e.g., overwritten multiple times). It would also include audit and accountability measures.
Describe a method for estimating the entropy of a physical source (e.g., mouse movements). What factors can reduce the entropy estimate, and how can you ensure that the estimate is conservative?
One method is to use a statistical test (e.g., the chi-square test) to measure the distribution of samples. Factors that reduce entropy include correlations between samples, deterministic patterns, and low resolution. To ensure conservatism, use a lower bound (e.g., min-entropy) rather than Shannon entropy, and apply conditioning (e.g., hashing) to extract a uniform random string.
Implement a simple CTR_DRBG using AES-128 in CTR mode (or use your chosen library). Generate 1024 random bytes and test them for statistical randomness using a tool like `ent` or NIST's statistical test suite. Write a report on your implementation, the test results, and any challenges encountered.
Complete answer would include code (or a description), test results (e.g., p-values from NIST tests), and a discussion of the implementation details (seeding, incrementing the counter, etc.). It would also explain why the output passes randomness tests, indicating a good DRBG.
This tutorial has provided a comprehensive examination of random number generation and key management in cryptography. We began by establishing the critical importance of randomness: cryptographic security depends on the unpredictability of keys, nonces, salts, and other values. We defined entropy as a measure of unpredictability and discussed how to estimate and collect it from physical and system sources.
We distinguished between true random number generators (TRNGs), which use physical noise, and pseudorandom number generators (PRNGs), which are algorithmic. We emphasized that only cryptographically secure PRNGs (CSPRNGs) should be used for security purposes, and we described the NIST-approved DRBGs (Hash_DRBG, HMAC_DRBG, CTR_DRBG) as examples.
We examined the key lifecycle management process, covering generation, distribution, storage, usage, revocation, and destruction. We discussed best practices and common pitfalls, such as the importance of sufficient entropy, the dangers of predictable seeds, and the risks of using non-cryptographic PRNGs.
The case study of the Debian OpenSSL RNG vulnerability illustrated the catastrophic consequences of weak randomness and the importance of proper entropy collection. The lessons from this incident remain relevant today: always use validated CSPRNGs, rely on operating system RNGs, and never compromise on entropy quality.
With this foundation, you are now equipped to generate cryptographic keys and random values securely, and to manage them throughout their lifecycle.
In Tutorial 2.9: Hash Functions and Data Integrity, we will explore cryptographic hash functions—another essential primitive that often relies on randomness (e.g., salts in password hashing). Hash functions also play a role in randomness generation (e.g., in Hash_DRBG).