CWE-1241: Use of Predictable Algorithm in Random Number Generator

Description

The device uses an algorithm that is predictable and generates a pseudo-random number.

Pseudo-random number generator algorithms are predictable because their registers have a finite number of possible states, which eventually lead to repeating patterns. As a result, pseudo-random number generators (PRNGs) can compromise their randomness or expose their internal state to various attacks, such as reverse engineering or tampering.

Potential Impact

Confidentiality

Read Application Data

Demonstrative Examples

Suppose a cryptographic function expects random value to be supplied for the crypto algorithm.
During the implementation phase, due to space constraint, a cryptographically secure random-number-generator could not be used, and instead  of using a TRNG (True Random Number Generator), a LFSR (Linear Feedback Shift Register) is used to generate a random value. While an LFSR will provide a pseudo-random number, its entropy (measure of randomness) is insufficient for a cryptographic algorithm.

The example code is taken from the PRNG inside the buggy OpenPiton SoC of HACK@DAC'21 [REF-1370]. The SoC implements a pseudo-random number generator using a Linear Feedback Shift Register (LFSR).

An example of LFSR with the polynomial function P(x) = x

Bad

reg in_sr, entropy16_valid;
						reg [15:0] entropy16;
						
						assign entropy16_o = entropy16;
						assign entropy16_valid_o = entropy16_valid;
						
						always @ (*)
						begin
						
							in_sr = ^ (poly_i [15:0] & entropy16 [15:0]);
						
						end

A LFSR's input bit is determined by the output of a linear function of two or more of its previous states. Therefore, given a long cycle, a LFSR-based PRNG will enter a repeating cycle, which is predictable.

Mitigations & Prevention

Architecture and Design

It is highly recommended to use a true random number generator (TRNG) to ensure the security of encryption schemes. Hardware-based TRNGs generate unpredictable, unbiased, and independent random numbers because they employ physical phenomena, e.g., electrical noise, as sources to generate random numbers.

Implementation

Real-World CVE Examples

CVE ID	Description
CVE-2021-3692	PHP framework uses mt_rand() function (Marsenne Twister) when generating tokens

Frequently Asked Questions

What is CWE-1241?

CWE-1241 (Use of Predictable Algorithm in Random Number Generator) is a software weakness identified by MITRE's Common Weakness Enumeration. It is classified as a Base-level weakness. The device uses an algorithm that is predictable and generates a pseudo-random number.

How can CWE-1241 be exploited?

Attackers can exploit CWE-1241 (Use of Predictable Algorithm in Random Number Generator) to read application data. This weakness is typically introduced during the Architecture and Design, Implementation phase of software development.

How do I prevent CWE-1241?

Key mitigations include: It is highly recommended to use a true random number generator (TRNG) to ensure the security of encryption schemes. Hardware-based TRNGs generate unpredictable, unbiased, and independent random number

What is the severity of CWE-1241?

CWE-1241 is classified as a Base-level weakness (Medium abstraction). It has been observed in 1 real-world CVEs.