Pseudo-Random Number Generation Bugs (PRN) Examples
CVE-2001-1141
BF Taxonomy
Cause:
Improper PRNG Algorithm (C md_rand - the secret PRNG state is updated with portion,
as small as on byte, of the PRNG's previous output, which is not secret)
Attributes:
Function: Mixing (back into entropy pool)
Algorithm: Hash Function ( SHA-1 used for PRNG output and to
update its internal secret state)
Used For: Generation (of cryptographic keying material - nonces, cryptographic keys)
Pseudo-Randomness Requirement: Sufficicent Space Size and
Unpredictability (can be predicted from previous value through brute force)
Consequence:
KMN>Generate with IEX of future keying
BF Description
Use of improper PRNG algorithm (C md_rand uses SHA-1 for
mixing back in the entropy pool portion, as small as one byte, of previous output to
update PRNG’s state), allows generation of cryptographic keying material (nonces and
cryptographic keys) that does not satisfy the sufficient space size and
unpredictability (can be predicted from previous values through brute force) pseudo-randomness
requirements, which leads to KMN>Generate and IEX of
future keying material.
Analysis
A PRNG used for cryptography does not satisfy the requirement of unpredictability from previous values,
because the internal state can be determined from number of output requests. Possible consequences include: IEX
of future PRNG output (CVE-2001-1141) (which is KMN>Generation failure) and weak encryption, confidentiality
compromise (which is ENC>Confidentiality failure).
The entropy accumulation implementation (entropy pool and associated mixing function) allows reconstruction of
the PRNG internal state . The mixing hash function for md (in the C md_rand) gets half of the
previous value of md and bytes from the PRNG internal state. Wrongly, the half used is the one with the PRNG’s
previous output (failed implementation relative to specification). Also, the number of used state bytes depends
on the number of bytes requested as output, which could be as small as one byte. This enables a brute-force
attack. The PRNG state could be reconstructed from the output of one large PRNG request (large enough to gain
knowledge on md) followed by consecutive 1-byte PRNG requests.
Source Code
| Code With Bug |
Code With Fix |
Source Code Not Available
|
|
Source Code Not Available
|
|
CVE-2008-4107
BF Taxonomy
Cause:
Improper PRNG Algorithms (not cryptographically strong PHP 5 rand and
mt_rand)
Attributes:
Function: Generate (pseudo-random numbers)
Algorithms: e.g., LCG or LSFR, Mersenne Twister
Used For: Generation (of passwords)
Pseudo-Randomness Requirement: Unpredictability/Indistinguishability and
Prediction Resistance
Consequence:
IEX (of password), leading to ATN
BF Description
Improper PRNG algorithms (not cryptographically strong PHP 5 rand> and
mt_rand, based on algorithms such as LCG or LFSR, and Mersenne Twister) used
to generate pseudo-random numbers, allow generation of passwords
that do not satisfy the unpredictability/ indistinguishability and prediction
resistance pseudo-randomness requirements and may be exploited for IEX
of password, leading to ATN.
Analysis
PHP’s rand() usually uses LCG or LFSR, which is weak. PHP 5 mt_rand() uses Mersenne
Twister, which is weak as well. It enables finding the internal state and all future values from 624 values.
This vulnerability can be used for password guessing (CVE-2008-4107).
Source Code
| Code With Bug |
Code With Fix |
Source Code Not Available
|
|
Source Code Not Available
|
|