logo

Use of Predictable Algorithm in Random Number Generator

Draft Base
Structure: Simple
Description

This vulnerability occurs when a device or application relies on a predictable algorithm to generate pseudo-random numbers, making the output sequence foreseeable.

Extended Description

Pseudo-random number generators (PRNGs) create numbers using deterministic algorithms, meaning they have a finite internal state that will eventually repeat. This predictability makes them vulnerable to attacks where an adversary can analyze past outputs to deduce future values or uncover the generator's internal state, compromising the security of any system that depends on this randomness. For robust security, especially in encryption, key generation, or session tokens, it's critical to use hardware-based True Random Number Generators (TRNGs). TRNGs derive randomness from unpredictable physical processes like electrical noise, producing outputs that are unbiased, independent, and fundamentally unpredictable, thereby providing a much stronger foundation for security-critical operations.
Common Consequences 1
Scope: Confidentiality

Impact: Read Application Data
Potential Mitigations 2
Phase: Architecture and Design
A true random number generator should be specified for cryptographic algorithms.
Phase: Implementation
A true random number generator should be implemented for cryptographic algorithms.
Demonstrative Examples 2
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 6+x 4+x 3+1 is shown in the figure.

Code Example:

Bad
Verilog

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.
  
Observed Examples 1
CVE-2021-3692PHP framework uses mt_rand() function (Marsenne Twister) when generating tokens
  
References 1
rng_16.v
2021
https://github.com/HACK-EVENT/hackatdac21/blob/main/piton/design/chip/tile/ariane/src/rand_num/rng_16.v#L12-L22(2023-07-15)
ID: REF-1370
 
  
    
 
 
Applicable Platforms 
 
 
 
  
  
 
 
Technologies:
 
 
 System on Chip : Undetermined 
 
 
 
  
 
 
Modes of Introduction 
 
 
 
 
 
  Architecture and Design  
 
  Implementation  
 
 
 
  
Related Attack Patterns 
        
 
 
Related Weaknesses 
 
 
 
 
  ChildOf:
 Use of Insufficiently Random Values (CWE-330) 
 
 
 
   
Notes 
MaintenanceAs of CWE 4.5, terminology related to randomness, entropy, and predictability can vary widely. Within the developer and other communities, "randomness" is used heavily. However, within cryptography, "entropy" is distinct, typically implied as a measurement. There are no commonly-used definitions, even within standards documents and cryptography papers. Future versions of CWE will attempt to define these terms and, if necessary, distinguish between them in ways that are appropriate for different communities but do not reduce the usability of CWE for mapping, understanding, or other scenarios.