Introduction to PRNGs
When it comes to vulnerabilities in web applications, there’s a lot of attention given to things like SQL injection, RCE vectors, and arbitrary file reads—and for good reason. These issues are often easy to spot, have straightforward exploitation paths, and can yield serious results. But one vulnerability class that doesn’t get much attention is the use of cryptographically insecure pseudo-random number generators (PRNGs).
There are a few reasons why this might be the case. PRNGs tend to have a fairly limited scope in most web applications; they’re typically only used in specific scenarios like session management or cryptographic operations. Many web frameworks and programming languages also provide secure defaults, so developers don’t usually need to write their own random number generation logic. Even when insecure PRNGs are used, exploiting them often requires deep technical knowledge if no prior research is publicly available on the PRNG at hand, like reverse-engineering the algorithm to predict future outputs, which raises the barrier to entry. Attackers also tend to prioritize more accessible and widely exploitable vulnerabilities over something as niche as PRNG misuse. Lastly and (in my opinion) most importantly, exploiting insecure PRNGs is challenging without access to the source code (more on that later).
In this post, we’ll shed some light on insecure PRNG vulnerabilities and walk through a real-world example of how such a vulnerability could be (theoretically) exploited without access to the vulnerable web application’s source code, highlighting both the risks and the nuances involved.
CSPRNGs
Before we dive into the details, it’s important to understand the characteristics of cryptographically secure PRNGs (CSPRNGs). A CSPRNG is designed to generate random numbers that are unpredictable, even if an attacker knows the algorithm and can see some of the output. These generators meet strict criteria, ensuring that the numbers they produce are resistant to attacks like state prediction or backtracking.
On the other hand, an insecure PRNG doesn’t meet the strict standards needed for secure applications. While it may produce numbers that appear random at first glance, it can be vulnerable to exploitation due to several weaknesses:
Predictable or brute-forceable seed values
Many PRNGs rely on a seed value to initialize their random number generation. If this seed is derived from a predictable source, such as the current timestamp, an attacker can guess or brute-force it. For example, imagine a web application that generates session tokens using a PRNG seeded with the current time down to the second. If an attacker knows approximately when the token was generated, they can test all possible seed values within that timeframe to reproduce the token and potentially hijack a session. Additionally, if the seed has a relatively small set of possible values (e.g., a 32-bit), modern hardware can brute-force all possible seeds in a reasonable amount of time.Insufficient entropy in the random number generation process
Entropy refers to the randomness or unpredictability used to generate numbers. If a PRNG is fed with insufficient entropy, its outputs can become predictable. For instance, a PRNG used in an embedded device with limited access to hardware-based randomness might rely on fixed inputs or repetitive patterns, making it easier for an attacker to analyse and predict the generated values. This issue is especially problematic in IoT devices or other resource-constrained environments.Use of algorithms with known vulnerabilities
Some PRNGs use outdated algorithms with well-documented weaknesses. For example, the Linear Congruential Generator (LCG), a simple PRNG often used in older software, can be easily reverse-engineered if an attacker sees a few outputs. By observing consecutive outputs of an LCG, the attacker can calculate the internal state and predict future values.
Real Life Example
In a recent white-box assessment we did for a client, we came across the following code:
import java.util.Random;
public class RandomId {
static char[] symbols;
private static Random random = new Random();
static {
StringBuilder sb = new StringBuilder();
for (char ch = '2'; ch <= '9'; ch++) {
sb.append(ch);
}
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch == 'l') {
// leave out
} else {
sb.append(ch);
}
}
for (char ch = 'A'; ch <= 'Z'; ch++) {
if (ch == 'I' || ch == 'O') {
//leave it out
} else {
sb.append(ch);
}
}
symbols = sb.toString().toCharArray();
}
public static String newId(int n) {
char[] buf = new char[n];
for (int i = 0; i < buf.length; i++) {
buf[i] = symbols[random.nextInt(symbols.length)];
}
return new String(buf);
}
// ...
This code defines a utility class called RandomId, which generates random strings from characters of the symbols array (composed of alphanumeric characters, excluding certain easily confused characters like 0, O, I, 1, and l). The newId method generates a random string of a specified length (n) by selecting characters from the symbols array. It uses a single instance of Java’s java.util.Random class to pick random characters from the set.
In the web application, this RandomId class is used throughout the codebase to generate various types of random strings, including session tokens, temporary passwords, password reset tokens, and object IDs. For example:
public UserSession(String uid, String em) {
userId = uid;
email = em;
id = RandomId.newId(24);
// ...
Weaknesses in java.util.Random
The main issue with the code above lies in the use of a single instance of java.util.Random to generate random strings. While java.util.Random might seem like an easy and convenient choice for generating random values, it has a significant vulnerability due to its underlying implementation. Specifically, java.util.Random uses a Linear Congruential Generator (LCG) to generate random numbers. LCGs are known for being predictable, especially when the internal state is exposed or can be inferred by an attacker.
Over the years, there have been numerous research efforts and discussions around attacking LCGs and, more specifically, the java.util.Random class. These have demonstrated how weaknesses in LCGs can be exploited to predict future outputs based on previously observed values with varying degrees of efficiency.
In our case, the vulnerable code was utilizing the Random.nextInt(int bound) function to generate random numbers that were less than the size of the symbols array (in order to randomly select characters from the array). We found that most techniques for abusing said function were only applicable to when the bound argument was an even number; we have the odd number of 57 (the length of the symbols array).
In 2023 however, elttam released a blog post which describes a new (and efficient) method they had discovered for restoring the state of the RandomStringUtils class from the Apache Commons project, RandomStringUtils being dependent on the java.util.Random class. This method was applicable to when the bound argument of the Random.nextInt() function was odd. They even publicly released a tool called rsu-cracker for abusing both RandomStringUtils.randomAlphanumeric() and Random.nextInt() (kudos to them).
Assuming we know that the java.util.Random class is in use, we have access to the symbols array, and we can observe some output from the PRNG (e.g. from session tokens), then we can restore the internal state of the PRNG and predict future randomized strings using rsu-cracker. This created a path to various exploits within the web application, such as session hijacking and password reset token prediction.
Proof-of-Concept
The following script was written to automate the process of exploiting the insecure PRNG highlighted above by utilising rsu-cracker:
import requests, subprocess
# Authenticate and retrieve a session cookie
login_url = "https://redacted.com/auth/login"
headers = {
"User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:135.0) Gecko/20100101 ",
"Content-Type": "application/json"
}
login_body = '{"email":"user@redacted.com","password":"Password123!"}'
resp = requests.post(login_url, data=login_body, headers=headers)
if resp.status_code != 200:
print('something went wrong')
exit(1)
cookie = resp.cookies.get("session")
print("cookie:", cookie)
# Reverse the cookie to PRNG indices
symbols = "23456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"
cookie_numbers = []
for i in cookie:
cookie_numbers.append(str(symbols.index(i)))
# Restore the PRNG’s state and predict future numbers with rsu-cracker
command = ["rsu-cracker", "next-int", "-n", "57", "-c", "1000", " ".join(cookie_numbers)]
print("command:", " ".join(command))
result = subprocess.run(
command,
stdout=subprocess.PIPE,
stderr=subprocess.DEVNULL,
text=True
)
next_numbers = [int(i) for i in result.stdout.split("\n") if len(i.strip()) > 0]
#print("next_numbers:", next_numbers)
next_characters = "".join([symbols[i] for i in next_numbers])
#print("next_characters:", next_characters)
settings_url = "https://redacted.com/settings"
input("wait for users to login and press enter..")
# Test predicted cookies
print("predicting session cookies..")
for i in range(len(next_characters) - 24):
potential_cookie = next_characters[i:i+24]
print("trying", potential_cookie)
headers["Cookie"] = "session={};".format(potential_cookie)
resp = requests.get(settings_url, headers=headers)
# if the session cookie is valid, the web application returns a 200 response
# otherwise we get a 401
if resp.status_code == 200:
print("found valid session cookie:", potential_cookie)
exit(0)
The script logs into the application with valid credentials and retrieves the session cookie generated by the vulnerable RandomId class.
Since we know the symbols array used to create the session cookies, the script maps the characters of the cookie back to the indices they represent in the array. This effectively gives us a sequence of numbers generated by the PRNG.
Using these numbers, the script leverages elttam’s rsu-cracker to restore the internal state of the PRNG. With the restored state, the rsu-cracker predicts the next sequence of random numbers generated by the PRNG. The reason why a lot of numbers are generated (specified in rsu-cracker‘s -c option) is because the RandomId.nextId() function could have been called multiple times as a result of other users’ interactions with the application without any of the calls being for generating session cookie strings. It maps these numbers back to the symbols array to generate possible future session cookies.
Finally, the script iterates through the predicted session cookies, sending requests to a protected endpoint. If one of the cookies is valid, the script halts.
Potential for Blackbox Exploitation
With access to the vulnerable application’s source code, detecting this vulnerability is trivial. Realistically though, an attacker won’t have access to the source code and would instead have to rely on a range of educated guesses and assumptions before attempting an exploit. Here’s how an attacker might go about this:
Detecting the use of a PRNG
An attacker’s first step would be to determine whether the application relies on a PRNG for generating random strings. This could be done by observing strings that consist of seemingly random characters in various parts of the application, such as:- Response headers: For example, session cookies.
- Response bodies: Such as object IDs or other identifiers.
- Emails: For example, password reset tokens. These strings wouldn’t just reveal the existence of a PRNG but could also serve as the input for cracking tools, like
rsu-cracker, to reverse-engineer the PRNG’s state (in cases such asjava.util.Random).
Guessing how random strings are generated
The attacker would next need to hypothesize how the application generates these random strings. A common approach in many applications is to generate random numbers using a PRNG and use these numbers as indices to select characters from a predefined array (e.g. thesymbolsarray in our example).
Another method involves generating random bytes using a PRNG, which are then encoded into strings using schemes like Base64. The specific approach used by the application would need to be guessed based on observed behavior or trial and error.Identifying the insecure PRNG
Once the attacker suspects that an insecure PRNG is in use, they’d need to deduce which PRNG is likely behind the random numbers. In our example, the fact that the application used a Java-based framework could be inferred from the presence of a cookie calledJSESSIONID. Based on this, the attacker could focus on popular insecure PRNGs in Java, such asjava.util.Random.
Additionally, the attacker might analyze sequences of numbers generated by the PRNG (reconstructed from strings) to narrow down which PRNG is in use. This step requires advanced skills, as recognizing patterns unique to specific PRNG has its challenges which are beyond the scope of this post.Determining the character set and order
To crack random strings, the attacker must also determine the set of characters used in those strings. This can be done by collecting a large number of samples (e.g., by repeatedly logging into the application or triggering token generation).
In our case, the attacker could reasonably deduce that certain characters, such as “0”, “1”, “l”, “I”, and “O”, were excluded due to their visual similarity to other characters.
The order of the character set would also need to be guessed. For example, the following permutations might make sense based on conventional practices:abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ23456789(lowercase + uppercase + digits)ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz23456789(uppercase + lowercase + digits)23456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ(digits + lowercase + uppercase)23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz(digits + uppercase + lowercase)
Testing vector and PRNG instance usage The attacker would need to identify which strings in the application are generated by which PRNG, especially in cases where multiple PRNG instances might be in use. For example, session cookies, object IDs, and password reset tokens might each be generated by separate PRNG objects, complicating the attack. Additionally, some applications might instantiate a new PRNG for every generated string (though this is generally considered poor development practice). The safest option here would be to use the same vector for obtaining sample numbers as for testing exploitation, ensuring consistency in targeting the correct PRNG instance (assuming a single PRNG instance is used). For example, we used the session cookie in our exploit above. The attacker would also need to account for the expiration periods of tokens or cookies, as expired values would no longer be valid for testing during the exploitation phase.
All in all, while an attacker can make educated guesses about the application’s behaviour, they’re largely “firing in the dark” until they succeed. Without access to the source code, the process becomes one of trial and error, requiring them to repeatedly test their hypotheses about the PRNG, character set, generation method and testing vector until they find a combination that works. While this increases the difficulty and effort required, the deterministic nature of insecure PRNGs ensures that success is ultimately possible if the target application is vulnerable. Other vulnerabilities within the application that allow for reading the source code (directly or indirectly) would significantly ease the process of exploitation.
Remediation
To mitigate vulnerabilities stemming from insecure PRNGs, cryptographically secure pseudorandom number generators (CSPRNGs) should always be used, especially when generating values for security-critical operations such as session cookies, password reset tokens, or temporary passwords. CSPRNGs are designed to produce output that is unpredictable and resistant to common attacks, ensuring they remain secure even if an attacker has access to partial information or output.
In our example, the java.util.Random class should be replaced with java.security.SecureRandom, which is a CSPRNG provided by the Java standard library:
private static SecureRandom secureRandom = new SecureRandom();
public static String newId(int n) {
char[] buf = new char[n];
for (int i = 0; i < buf.length; i++) {
buf[i] = symbols[secureRandom.nextInt(symbols.length)];
}
return new String(buf);
}