The Achilles' heel of cryptography: how PRNGs can ruin your security

A02:2021 - Cryptographic failures – Pseudorandom Number Generators (PRNG)

Introduction

The generation of random numbers in programming is crucial for many applications, especially in cryptography. A random number is one that cannot be predicted or anticipated, which ensures security in the generation of keys, tokens, or any sensitive value that must remain secret.

There are two main types of random number generators (RNG):

1. Pseudorandom Number Generators (PRNG): They use deterministic algorithms that, although they produce sequences of numbers that appear random, are predictable if the initial state or seed is known. This is dangerous in cryptographic contexts, as an attacker could replicate the sequence and anticipate sensitive values.

2. True Random Number Generators (TRNG): Based on unpredictable physical phenomena, such as electromagnetic radiation or thermal noise, these generators are much more secure, as they are not predictable.

Vulnerability arises when insecure or poorly implemented PRNGs are used in cryptographic systems. If an attacker can predict the generated numbers, they can break the security of the systems, derive cryptographic keys, intercept secure communications, or access protected resources.

This relationship between randomness and security is one of the reasons why OWASP includes failures in cryptography, such as the generation of insecure random numbers, among the top security concerns (A02:2021 Cryptographic Failures).

Technical Introduction

A Pseudorandom Number Generation (PRNG) algorithm is a deterministic system that transforms an initial value known as seed through a predefined mathematical function to produce a sequence of numbers that, on the surface, appear random. However, this randomness is only superficial, as the sequence is completely determined by the initial seed. This implies that two instances of the same algorithm, if initialized with the same seed, will generate an identical sequence of numbers. While this property can be useful in certain contexts, such as in reproducible simulations, it is highly problematic in cryptography, where predictability undermines the fundamental principles of security.

From the perspective of cryptographic security, it largely depends on the quality and unpredictability of the random numbers used in processes such as key generation, initialization vectors, and nonces. Traditional PRNGs, such as linear congruential generators (LCG), are vulnerable to attacks due to their simple mathematical structure and the low entropy used in the seeds. These generators often rely on predictable values, such as timestamps, that an attacker can infer.

Unlike traditional PRNGs, cryptographically secure pseudo-random number generators (CSPRNG) are designed to withstand attacks even if their internal state is partially exposed or if multiple outputs from the sequence are intercepted. CSPRNGs use more robust entropy sources, which can be a hardware pseudo-random number generator or even unpredictable system processes, and apply advanced cryptographic algorithms, such as those based on block ciphers or hash functions, to ensure the unpredictability of the sequence.

Main vulnerabilities

Predictability in Cryptographic Key Generation: The predictability of insecure PRNGs compromises the generation of cryptographic keys. If an attacker is able to infer the seed used S_0, either through analysis of the generator's outputs or by guessing a seed based on a predictable value such as a timestamp, they can reconstruct the associated private key and decrypt messages or perform fraudulent signatures. This problem has historically affected algorithms such as RSA and ECC, where the quality of the keys directly depends on the quality of the random numbers.

Reused or predictable nonces: In cryptographic systems like AES-GCM or ChaCha20-Poly1305, the reuse of the same nonce (a unique number per message) compromises the confidentiality and integrity of the data. If a PRNG generates predictable nonces or reuses values due to collisions in a reduced space, an attacker can perform attacks such as plaintext recovery through differential analysis. A notable case is the reuse of nonces in the implementation of WPA2, which allowed attacks like KRACK.

Vulnerable JWT Sessions: JSON Web Tokens (JWT) rely on unique and random values to prevent them from being replicated or guessed. If an insecure PRNG generates session identifiers or predictable signature values, an attacker could forge valid tokens to access protected systems. For example, an HMAC signature based on keys derived from predictable pseudorandom numbers could allow for a spoofing attack with reduced computational effort.

Problems in handshake protocols: Protocols like TLS and SSH rely on random values to ensure that sessions are unique and cannot be reproduced by an attacker. If the pseudo-random numbers used in the handshake are predictable, an attacker could execute "replay" attacks or force the renegotiation of weak keys, compromising the confidentiality of the channel. This was evidenced in older versions of SSL/TLS that used deficient PRNGs.

Comparison of safe vs. unsafe generation

The generation can be divided into three main steps:

1. Obtaining the initial seed:

In insecure generation, the seed often derives from easily predictable sources, such as a timestamp, the process identifier (PID), or even a constant value. For example, a linear congruential generator may use the current time in seconds, which drastically reduces the search space for an attacker. On the other hand, in secure generation, the seed comes from a robust entropy source, such as internal states collected by the operating system. This ensures that the seed is neither predictable nor reproducible.

2. Calculation of the internal state:

An insecure PRNG transforms the initial seed through simple mathematical operations, such as multiplications or modular additions, which, although they generate seemingly random numbers, exhibit detectable patterns with sufficient analysis. In contrast, a secure generator applies cryptographic algorithms such as hash functions or block ciphers, which have a high resistance to reversing the internal state.

3. Production of the sequence of numbers:

Insecure PRNGs generate each number in the sequence using fast but deterministic formulas, which allows future outputs to be predicted if the current state is known. For example, by observing some consecutive outputs, an attacker could deduce the algorithm and predict the next ones (in extremely simple cases). In comparison, secure generators produce numbers using transformations that depend on both the internal state and additional entropy collected during operation, making each output practically unpredictable.

Let's go to the code...

               
#include (stdio .h="")
#include (stdlib.h="")
#include (time .h="")

int generate_random_number() {
    static int initialized = 0;
       if (!initialized) {
        srand((unsigned int)time(NULL)); // (-- Use of the timestamp as a seed
        initialized = 1;
    }

    return a random number between 0 and 99;
}

int main() {
    printf(Generating pseudo-random numbers:
);
    for (int i = 0; i < 5; i++) {
        print the generated random number followed by a newline.
    }
    return 0;
}

      

#include (fcntl.h)
#include (errno.h)
#include (string.h)
#include 
#include (sys/syscall.h)

int generate_secure_random_number() {
    uint32_t random_number;

    // Usar syscall getrandom para obtener un número aleatorio seguro
    if (syscall(SYS_getrandom, random_number, sizeof(random_number), 0) == -1) {
        perror("Error generating a secure random number");
        exit(EXIT_FAILURE);
    }

    return random_number modulo 100;
}

int main() {
    printf("Generating secure random numbers:\n");
    for (int i = 0; i < 5; i++) {
        print the generated secure random number in decimal format followed by a new line.
    }
    return 0;
}