Small Seed Space in PRNG

Description

Small Seed Space in PRNG is a vulnerability that occurs when a Pseudo-Random Number Generator (PRNG) is seeded with a value from a space that is too small, making it susceptible to brute force attacks. Since PRNGs are deterministic algorithms that produce predictable output sequences based on their seed value, attackers who can collect PRNG outputs can attempt to determine the seed by testing all possible seed values against the observed output. When the seed space is limited (for example, a 32-bit or 48-bit seed), attackers can exhaustively test all possible seeds in a feasible amount of time. Even with modern CPUs testing millions of seeds per second, a 128-bit or 256-bit seed space remains computationally infeasible to brute force, while a 48-bit seed can be exhausted in hours.

Risk

A small seed space fundamentally limits the security of any PRNG-based mechanism regardless of how the random values are used. Java's java.util.Random uses only a 48-bit seed, meaning all its output is constrained to only 2^48 (about 281 trillion) possible sequences. While this sounds large, it's trivially searchable with modern computing resources. Attackers who capture even a small amount of PRNG output can test all possible seeds to find one that produces matching output, then predict all future outputs. This enables session hijacking when session tokens are generated from small-seeded PRNGs, credential prediction for generated passwords, and cryptographic key recovery. The vulnerability is particularly insidious because the PRNG output may appear random and pass statistical tests while being entirely predictable.

Solution

Use well-vetted PRNG algorithms with adequate seed lengths. A minimum 256-bit seed provides a solid foundation for security-sensitive applications. Use cryptographically secure PRNGs (CSPRNGs) that are designed with appropriately large internal state spaces. In Java, use SecureRandom instead of Random. In Python, use the secrets module or os.urandom(). In C, use RAND_bytes() from OpenSSL or getrandom(). Ensure the seed is derived from high-quality entropy sources with at least as much entropy as the seed size requires. Follow FIPS 140-2 or FIPS 140-3 guidelines for approved random number generators. Never truncate or reduce the effective size of PRNG seeds.

Common Consequences

Impact	Details
Access Control	Scope: Access Control Attackers can enumerate all possible seeds to predict authentication tokens, session IDs, and passwords, bypassing authentication controls.
Confidentiality	Scope: Confidentiality Cryptographic keys generated from small-seeded PRNGs can be recovered through seed enumeration, compromising encrypted data.
Integrity	Scope: Integrity Integrity mechanisms using PRNG-generated values (CSRF tokens, nonces) become predictable and forgeable.

Example Code

Vulnerable Code (Java/Python)

The following examples demonstrate small seed space vulnerabilities:

// Vulnerable: Small seed space in Java
import java.util.Random;

public class VulnerableSmallSeed {

    // Vulnerable: java.util.Random has only 48-bit seed
    public String vulnerableToken() {
        // Vulnerable: Only 2^48 possible sequences
        Random rand = new Random();
        byte[] bytes = new byte[32];
        rand.nextBytes(bytes);
        return bytesToHex(bytes);
    }

    // Vulnerable: Explicit 32-bit seed
    public String vulnerableSmallSeed() {
        // Vulnerable: Only 2^32 possible sequences
        int seed = (int) System.currentTimeMillis();  // 32-bit
        Random rand = new Random(seed);
        return Long.toHexString(rand.nextLong());
    }

    // Vulnerable: Short seed from truncation
    public String vulnerableTruncatedSeed() {
        // Vulnerable: Truncating to 16 bits
        short seed = (short) System.nanoTime();  // Only 2^16 possibilities!
        Random rand = new Random(seed);
        return Long.toHexString(rand.nextLong());
    }

    // Vulnerable: Using RandomStringUtils with weak Random
    public String vulnerableRandomString() {
        // Vulnerable: org.apache.commons.lang.RandomStringUtils uses Random
        // which has only 48-bit seed
        return org.apache.commons.lang3.RandomStringUtils.randomAlphanumeric(32);
    }

    // Vulnerable: Password from weak Random
    public String vulnerablePassword() {
        // Vulnerable: Passwords limited to 2^48 possibilities
        Random rand = new Random();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 16; i++) {
            sb.append(chars.charAt(rand.nextInt(chars.length())));
        }
        return sb.toString();
    }

    private String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

# Vulnerable: Small seed space in Python
import random

# Vulnerable: random module seed (varies but typically 32-bit on many systems)
def vulnerable_small_seed():
    # Vulnerable: System default seeding may use limited entropy
    return random.getrandbits(256)  # Looks secure but limited by seed

# Vulnerable: Explicit small seed
def vulnerable_explicit_small_seed():
    import time
    # Vulnerable: Only 32 bits of seed
    seed = int(time.time()) % (2**32)
    random.seed(seed)
    return format(random.getrandbits(128), '032x')

# Vulnerable: Truncated seed
def vulnerable_truncated_seed():
    import os
    # Vulnerable: Truncating entropy defeats its purpose
    full_entropy = os.urandom(32)
    truncated = int.from_bytes(full_entropy[:4], 'big')  # Only 32 bits!
    random.seed(truncated)
    return random.getrandbits(256)

# Vulnerable: Seed from limited source
def vulnerable_limited_source():
    import socket
    # Vulnerable: Hostname has very limited entropy
    hostname = socket.gethostname()
    random.seed(hash(hostname) & 0xFFFFFFFF)  # 32-bit
    return format(random.getrandbits(128), '032x')

# Vulnerable: Counter-limited seed
class VulnerableCounterSeed:
    counter = 0

    @classmethod
    def generate(cls):
        cls.counter += 1
        # Vulnerable: Counter as seed is completely enumerable
        random.seed(cls.counter & 0xFFFF)  # Only 16 bits!
        return random.getrandbits(128)

// Vulnerable: Small seed space in C
#include <stdlib.h>
#include <time.h>

// Vulnerable: srand() takes only 32-bit seed
void vulnerable_srand() {
    // Vulnerable: Only 2^32 possible sequences
    srand(time(NULL));
}

// Vulnerable: Even smaller seed
void vulnerable_short_seed() {
    // Vulnerable: 16-bit seed = 65536 possibilities
    unsigned short seed = (unsigned short)time(NULL);
    srand(seed);
}

// Vulnerable: Custom PRNG with small seed
typedef struct {
    unsigned int state;  // Vulnerable: Only 32-bit state
} WeakPRNG;

void weak_prng_seed(WeakPRNG *prng, unsigned int seed) {
    prng->state = seed;
}

unsigned int weak_prng_next(WeakPRNG *prng) {
    // Vulnerable: 32-bit state limits all output
    prng->state = prng->state * 1103515245 + 12345;
    return prng->state;
}

// Vulnerable: Truncating good entropy
void vulnerable_truncate(unsigned char *output, size_t len) {
    unsigned char full_entropy[32];
    // Assume we got 256 bits of good entropy here

    // Vulnerable: Truncating to 32 bits for seed
    unsigned int seed = *(unsigned int*)full_entropy;
    srand(seed);

    for (size_t i = 0; i < len; i++) {
        output[i] = rand() % 256;
    }
}

Fixed Code (Java/Python)

// Fixed: Adequate seed space in Java
import java.security.SecureRandom;
import java.security.NoSuchAlgorithmException;

public class SecureAdequateSeed {

    // Fixed: SecureRandom has large internal state
    public String secureToken() throws NoSuchAlgorithmException {
        // Fixed: SecureRandom uses 160+ bit seed from system entropy
        SecureRandom sr = SecureRandom.getInstanceStrong();
        byte[] bytes = new byte[32];
        sr.nextBytes(bytes);
        return bytesToHex(bytes);
    }

    // Fixed: Explicit large seed
    public String secureLargeSeed() throws NoSuchAlgorithmException {
        // Fixed: 256-bit seed
        SecureRandom sr = new SecureRandom();
        byte[] seed = sr.generateSeed(32);  // 256 bits
        sr.setSeed(seed);
        byte[] bytes = new byte[32];
        sr.nextBytes(bytes);
        return bytesToHex(bytes);
    }

    // Fixed: Using SecureRandom for strings
    public String secureRandomString(int length) throws NoSuchAlgorithmException {
        // Fixed: SecureRandom instead of Random
        SecureRandom sr = SecureRandom.getInstanceStrong();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(chars.charAt(sr.nextInt(chars.length())));
        }
        return sb.toString();
    }

    // Fixed: Secure password generation
    public String securePassword(int length) throws NoSuchAlgorithmException {
        // Fixed: Full entropy
        SecureRandom sr = SecureRandom.getInstanceStrong();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(chars.charAt(sr.nextInt(chars.length())));
        }
        return sb.toString();
    }

    // Fixed: If Apache Commons needed, wrap SecureRandom
    public String secureApacheStyle(int length) throws NoSuchAlgorithmException {
        // Fixed: Don't use RandomStringUtils for security
        return secureRandomString(length);
    }

    private String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

# Fixed: Adequate seed space in Python
import secrets
import os

# Fixed: Using secrets module (no manual seeding, uses system CSPRNG)
def secure_token():
    # Fixed: System entropy, large state
    return secrets.token_hex(32)

# Fixed: If seeding random needed, use full entropy
def secure_seeded_random():
    import random
    # Fixed: 256-bit seed from system entropy
    seed_bytes = os.urandom(32)
    # Use SystemRandom which doesn't rely on seed
    return secrets.SystemRandom()

# Fixed: Use SystemRandom class
def secure_system_random():
    # Fixed: SystemRandom uses OS entropy directly
    rng = secrets.SystemRandom()
    return format(rng.getrandbits(256), '064x')

# Fixed: Secure password generation
def secure_password(length=16):
    # Fixed: secrets module
    chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*'
    return ''.join(secrets.choice(chars) for _ in range(length))

# Fixed: Counter with secure random component
class SecureGenerator:
    def __init__(self):
        self.counter = 0

    def generate(self):
        self.counter += 1
        # Fixed: Counter is just identifier, security comes from secrets
        token = secrets.token_hex(16)
        return f"{self.counter}:{token}"

# Fixed: Full entropy key
def secure_key():
    # Fixed: 256 bits from system entropy
    return os.urandom(32)

// Fixed: Adequate seed space in C
#include <openssl/rand.h>
#include <string.h>

// Fixed: Use OpenSSL RAND which has large internal state
int secure_random(unsigned char *buffer, size_t len) {
    // Fixed: RAND_bytes uses large state seeded from system entropy
    return RAND_bytes(buffer, len) == 1 ? 0 : -1;
}

// Fixed: Proper seeding with full entropy
int secure_init() {
    unsigned char seed[32];  // 256 bits

    // Get full entropy from system
    if (RAND_bytes(seed, sizeof(seed)) != 1) {
        return -1;
    }

    // Add to entropy pool (RAND_bytes already seeded, this adds more)
    RAND_seed(seed, sizeof(seed));

    // Clear seed from memory
    OPENSSL_cleanse(seed, sizeof(seed));

    return 0;
}

// Fixed: Custom PRNG with large state (if needed)
typedef struct {
    unsigned char state[64];  // 512-bit state
    int position;
} SecurePRNG;

int secure_prng_init(SecurePRNG *prng) {
    // Fixed: Seed with 512 bits of entropy
    if (RAND_bytes(prng->state, sizeof(prng->state)) != 1) {
        return -1;
    }
    prng->position = 0;
    return 0;
}

// Fixed: Never truncate entropy
int secure_key(unsigned char *key, size_t len) {
    // Fixed: Use full system entropy
    return RAND_bytes(key, len) == 1 ? 0 : -1;
}

// Fixed: Using getrandom with adequate buffer
#ifdef __linux__
#include <sys/random.h>

int secure_getrandom(unsigned char *buffer, size_t len) {
    // Fixed: Full entropy from kernel
    ssize_t result = getrandom(buffer, len, 0);
    return result == (ssize_t)len ? 0 : -1;
}
#endif

The fix uses CSPRNGs with large internal state spaces (256+ bits) that cannot be brute-forced.

---

Exploited in the Wild

Apache Commons RandomStringUtils (CVE-2019-10908)

A product generated passwords using org.apache.commons.lang.RandomStringUtils, which internally uses java.util.Random with only a 48-bit seed, making generated passwords predictable.

• https://nvd.nist.gov/vuln/detail/CVE-2019-10908

Session Token Prediction

Numerous web applications using java.util.Random for session tokens have been exploited through seed enumeration attacks.

• https://owasp.org/

---

Tools to Test/Exploit

• untwister — Can recover seeds from observed PRNG output.

• Seed enumeration scripts — Brute force 32-bit and 48-bit seed spaces.

• JavaSnoop — Can observe Random usage in Java applications.

---

CVE Examples

• CVE-2019-10908 — RandomStringUtils using 48-bit seeded Random for passwords.

---

References

1. MITRE Corporation. "CWE-339: Small Seed Space in PRNG." Common Weakness Enumeration. https://cwe.mitre.org/data/definitions/339.html

2. NIST. "Recommendation for Random Number Generation." SP 800-90A. https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final

3. Java Documentation. "java.util.Random - Implementation Notes." https://docs.oracle.com/javase/8/docs/api/java/util/Random.html