Use of Predictable Algorithm in Random Number Generator

Description

Use of Predictable Algorithm in Random Number Generator occurs when a device employs an algorithm that generates pseudo-random numbers in a predictable manner. Pseudo-random number generators (PRNGs) have finite possible states, eventually leading to repeating patterns. This predictability allows various attacks such as reverse engineering or tampering and can compromise randomness or expose internal states. Security-critical applications require true random number generators (TRNGs) that leverage physical phenomena.

Risk

Predictable random numbers have severe security implications. Cryptographic keys may be predictable. Session tokens may be guessable. Nonces may repeat, breaking encryption. Authentication mechanisms may be bypassable. Future random values may be calculable from past observations. Encryption may be effectively nullified. PRNG state may be recoverable from output.

Solution

Use true random number generators (TRNGs) for security-critical applications. TRNGs leverage physical phenomena such as electrical noise as sources to generate random numbers. Combine multiple entropy sources for robustness. Use cryptographically secure PRNGs seeded from TRNGs. Implement NIST SP 800-90A/B compliant random number generation. Test randomness with statistical test suites. Avoid linear feedback shift registers (LFSRs) for security purposes.

Common Consequences

Impact	Details
Confidentiality	Scope: Confidentiality Read Application Data - Predictable random numbers allow attackers to determine cryptographic keys, tokens, and other security-critical values. High likelihood.

Example Code

Vulnerable Code

// Vulnerable: Linear Feedback Shift Register (LFSR) for random number generation

module vulnerable_lfsr_rng (
    input wire clk,
    input wire reset_n,
    input wire request_random,
    output reg [31:0] random_output,
    output reg random_valid
);

    // VULNERABLE: LFSR is deterministic and predictable
    reg [31:0] lfsr_state;

    // Polynomial: x^32 + x^22 + x^2 + x + 1
    wire feedback = lfsr_state[31] ^ lfsr_state[21] ^ lfsr_state[1] ^ lfsr_state[0];

    always @(posedge clk or negedge reset_n) begin
        if (!reset_n) begin
            // VULNERABLE: Fixed seed
            lfsr_state <= 32'h12345678;
            random_valid <= 1'b0;
        end
        else if (request_random) begin
            // VULNERABLE: Next state completely determined by current state
            lfsr_state <= {lfsr_state[30:0], feedback};
            random_output <= lfsr_state;
            random_valid <= 1'b1;
        end
    end

    // Attack: Observe 32 consecutive outputs to recover full state
    // All future outputs can then be predicted

endmodule

// Vulnerable: Simple counter-based "random"
module vulnerable_counter_rng (
    input wire clk,
    input wire request,
    output reg [31:0] random_output
);

    reg [31:0] counter;

    always @(posedge clk) begin
        counter <= counter + 1;

        if (request) begin
            // VULNERABLE: Just a counter - completely predictable!
            random_output <= counter;
        end
    end

endmodule

// Vulnerable: Time-based seed only
module vulnerable_time_seeded_rng (
    input wire clk,
    input wire reset_n,
    input wire [31:0] time_counter,
    output reg [31:0] random_output
);

    reg [31:0] lfsr;
    wire feedback = lfsr[31] ^ lfsr[22] ^ lfsr[2] ^ lfsr[1];

    always @(posedge clk or negedge reset_n) begin
        if (!reset_n) begin
            // VULNERABLE: Seed from system time - low entropy
            // Attacker who knows approximate reset time can guess seed
            lfsr <= time_counter;
        end
        else begin
            lfsr <= {lfsr[30:0], feedback};
            random_output <= lfsr;
        end
    end

endmodule

// Vulnerable: Using standard rand() for security purposes

#include <stdlib.h>
#include <time.h>

// VULNERABLE: rand() is not cryptographically secure
void vulnerable_generate_token(char* token, size_t len) {
    srand(time(NULL));  // Predictable seed!

    for (size_t i = 0; i < len; i++) {
        token[i] = 'A' + (rand() % 26);  // Predictable sequence
    }
}

// VULNERABLE: PHP-style mt_rand() is predictable
// CVE-2021-3692: PHP framework using mt_rand() for token generation
void vulnerable_session_id(char* session_id) {
    mt_srand(time(NULL));

    for (int i = 0; i < 32; i++) {
        session_id[i] = "0123456789abcdef"[mt_rand() % 16];
    }
}

// VULNERABLE: Linear congruential generator
uint32_t lcg_state = 1;

uint32_t vulnerable_lcg_random(void) {
    // Classic LCG - fully predictable from any output
    lcg_state = lcg_state * 1103515245 + 12345;
    return (lcg_state >> 16) & 0x7FFF;
}

Fixed Code

// Fixed: True Random Number Generator using ring oscillator

module secure_trng (
    input wire clk,
    input wire reset_n,
    input wire request_random,
    output reg [31:0] random_output,
    output reg random_valid,
    output reg entropy_low
);

    // Ring oscillator entropy source (simplified)
    // Real implementation uses multiple oscillators and sampling
    wire [7:0] ring_osc_outputs;

    // Multiple ring oscillators with different delays
    ring_oscillator #(.STAGES(3)) ro0 (.out(ring_osc_outputs[0]));
    ring_oscillator #(.STAGES(5)) ro1 (.out(ring_osc_outputs[1]));
    ring_oscillator #(.STAGES(7)) ro2 (.out(ring_osc_outputs[2]));
    ring_oscillator #(.STAGES(9)) ro3 (.out(ring_osc_outputs[3]));
    ring_oscillator #(.STAGES(11)) ro4 (.out(ring_osc_outputs[4]));
    ring_oscillator #(.STAGES(13)) ro5 (.out(ring_osc_outputs[5]));
    ring_oscillator #(.STAGES(15)) ro6 (.out(ring_osc_outputs[6]));
    ring_oscillator #(.STAGES(17)) ro7 (.out(ring_osc_outputs[7]));

    // Entropy accumulator
    reg [255:0] entropy_pool;
    reg [4:0] sample_count;

    // Health check
    reg [7:0] last_sample;
    reg [7:0] stuck_count;
    parameter STUCK_THRESHOLD = 100;

    always @(posedge clk or negedge reset_n) begin
        if (!reset_n) begin
            entropy_pool <= 256'h0;
            sample_count <= 5'h0;
            random_valid <= 1'b0;
            entropy_low <= 1'b0;
            stuck_count <= 8'h0;
        end
        else begin
            // Sample ring oscillators
            if (ring_osc_outputs == last_sample) begin
                stuck_count <= stuck_count + 1;
                if (stuck_count > STUCK_THRESHOLD) begin
                    entropy_low <= 1'b1;  // Health check failure
                end
            end else begin
                stuck_count <= 8'h0;
                entropy_low <= 1'b0;
            end
            last_sample <= ring_osc_outputs;

            // Accumulate entropy
            entropy_pool <= {entropy_pool[247:0], ring_osc_outputs};
            sample_count <= sample_count + 1;

            if (request_random && sample_count == 5'h1F && !entropy_low) begin
                // FIXED: Use hardware entropy, properly conditioned
                random_output <= condition_entropy(entropy_pool);
                random_valid <= 1'b1;
                sample_count <= 5'h0;
            end else begin
                random_valid <= 1'b0;
            end
        end
    end

    // Entropy conditioning (simplified - use SHA-256 in practice)
    function [31:0] condition_entropy;
        input [255:0] raw_entropy;
        begin
            // Cryptographic conditioning to remove bias
            condition_entropy = sha256_compress(raw_entropy)[31:0];
        end
    endfunction

endmodule

// Fixed: CSPRNG seeded from TRNG
module secure_csprng (
    input wire clk,
    input wire reset_n,
    input wire [255:0] trng_seed,
    input wire seed_valid,
    input wire request_random,
    output reg [31:0] random_output,
    output reg random_valid
);

    // Use AES-CTR or ChaCha20 as CSPRNG
    reg [255:0] state;
    reg [127:0] counter;
    reg seeded;

    always @(posedge clk or negedge reset_n) begin
        if (!reset_n) begin
            state <= 256'h0;
            counter <= 128'h0;
            seeded <= 1'b0;
            random_valid <= 1'b0;
        end
        else if (seed_valid) begin
            // Seed from TRNG
            state <= trng_seed;
            seeded <= 1'b1;
        end
        else if (request_random && seeded) begin
            // Generate using AES-CTR
            random_output <= aes_encrypt(counter, state[127:0]) ^
                            aes_encrypt(counter + 1, state[255:128]);
            counter <= counter + 2;
            random_valid <= 1'b1;

            // Reseed periodically
            if (counter[31:0] == 32'hFFFFFFFF) begin
                seeded <= 1'b0;  // Request new seed
            end
        end else begin
            random_valid <= 1'b0;
        end
    end

endmodule

// Fixed: Using cryptographically secure random number generation

#include <stdint.h>
#include <stdbool.h>

// On Linux/Unix
#include <sys/random.h>

// FIXED: Use OS-provided CSPRNG
int secure_generate_random(uint8_t* buffer, size_t len) {
    // getrandom() uses kernel entropy pool
    ssize_t result = getrandom(buffer, len, 0);
    return (result == (ssize_t)len) ? 0 : -1;
}

// FIXED: OpenSSL CSPRNG
#include <openssl/rand.h>

int secure_generate_token(char* token, size_t len) {
    uint8_t random_bytes[len];

    if (RAND_bytes(random_bytes, len) != 1) {
        return -1;  // Error
    }

    for (size_t i = 0; i < len; i++) {
        token[i] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
                   [random_bytes[i] % 62];
    }

    // Clear sensitive data
    OPENSSL_cleanse(random_bytes, len);
    return 0;
}

// FIXED: Generate cryptographically secure session ID
int secure_session_id(char* session_id, size_t len) {
    uint8_t random_bytes[len / 2];

    if (RAND_bytes(random_bytes, sizeof(random_bytes)) != 1) {
        return -1;
    }

    for (size_t i = 0; i < sizeof(random_bytes); i++) {
        sprintf(session_id + (i * 2), "%02x", random_bytes[i]);
    }

    OPENSSL_cleanse(random_bytes, sizeof(random_bytes));
    return 0;
}

// FIXED: Hardware RNG access (if available)
#ifdef __x86_64__
#include <immintrin.h>

int secure_hardware_random(uint64_t* value) {
    int retries = 10;

    while (retries--) {
        if (_rdrand64_step(value)) {
            return 0;
        }
    }
    return -1;  // RDRAND failed
}
#endif

// Windows
#ifdef _WIN32
#include <bcrypt.h>

int secure_generate_random_win(uint8_t* buffer, size_t len) {
    NTSTATUS status = BCryptGenRandom(NULL, buffer, len,
                                       BCRYPT_USE_SYSTEM_PREFERRED_RNG);
    return BCRYPT_SUCCESS(status) ? 0 : -1;
}
#endif

---

CVE Examples

• CVE-2021-3692: PHP framework using mt_rand() for token generation
• Various vulnerabilities in IoT devices using LFSRs for security

---

Related CWEs

• CWE-330: Use of Insufficiently Random Values (parent)
• CWE-1213: Random Number Issues (category member)
• CWE-1205: Security Primitives and Cryptography Issues (category member)
• CWE-338: Use of Cryptographically Weak PRNG (related)

---

References

1. MITRE Corporation. "CWE-1241: Use of Predictable Algorithm in Random Number Generator." https://cwe.mitre.org/data/definitions/1241.html
2. NIST SP 800-90A: Recommendation for Random Number Generation Using Deterministic RBGs
3. NIST SP 800-90B: Recommendation for the Entropy Sources Used for Random Bit Generation
4. REF-1370: LFSR Implementation in OpenPiton SoC (HACK@DAC'21)