Breaking Java Random PRNG: UYBHYS 2022 challenge Writeup
A little challenge was introduced on twitter to win a ticket to Unlock Your Brain 2022 conference. This article is a write-up of the solution and explores the implementation of Java Random PRNG.
Disclaimer: I am not a cryptographic expert, just a security enthousiast.
The conference
The conference Unlock Your Brain Harden Your System aka “Unlock” or #UYBHYS is organized since 2015 by the Cantine numérique Brest and DIATEAM in Brest (France). During 2 days, participants will have the opportunity to attend to a day of conferences, 2 to 4 workshops and a 4 hours CTF, most of the time attack-defense style on Sea surf monsters theme. Last time, it was an OSINT CTF.
The challenge
Formind support this nice and friendly event since 2018 and offered to win a conference ticket on twitter by solving a challenge:
No more tickets for the conf @UYBHYS? 😭 No panic! The first to solve this little challenge win its ticket! 🤩 Send in DM the 3rd result of this secured password generator, knowing that the 2 first leaked: 7EHPFygG2gq2, 7M7y9YTHt800 your keyboards ready go! #cybersecurity
package com.formind;
import java.util.Random;
class SecurePassword {
// speed up the algorithm by not re-creating the PRNG
public Random random = new Random();
public String generatePassword() {
StringBuilder password = new StringBuilder();
while (true) {
// generate a real random 32-bits signed int, ex: 447603982
int i = this.random.nextInt();
// convert integer to base36 (lower case + digits), ex: "7ehpfy"
String passwordPart = Long.toString(i, 36);
// we have signed integers, remove the "minus" sign
passwordPart = passwordPart.replace("-", "");
// append the result to the existing password
password.append(passwordPart);
// ANSSI says password length should be 9 minimum
// stop if we got the minimum complexity
if (password.length() > 10) {
break;
}
}
// now we have a lower case+digit password, ex: "7ehpfygg2gq2"
// raise the complexity to have upper case letters
StringBuilder result = new StringBuilder();
for (int i = 0; i < password.length(); i++) {
// if we have a letter from ascii code + 1 chance out of 2
if (password.charAt(i) > 96 && this.random.nextInt() % 2 == 0) {
// convert the lower case letter to upper case
char x = (char) (password.charAt(i) - 32);
result.append(x);
} else {
// just keep the initial character
result.append(password.charAt(i));
}
}
return result.toString();
}
public static void main(String[] args) {
SecurePassword generator = new SecurePassword();
System.out.println(generator.generatePassword());
//7EHPFygG2gq2
System.out.println(generator.generatePassword());
//7M7y9YTHt800
System.out.println(generator.generatePassword());
// ????
}
}
The solution
The first step is to analyse the source code and understand what it’s really doing. Note that the first version of the challenge did not contain the comments. However, it was decided to include them to make it as accessible as possible for everyone.
The java.util.Random PRNG
Password generator sounds like crypto challenge or equivalent. For a person used to CTF/code reviews, first line of the code will strike the reader:
import java.util.Random;
It is known that java.util.Random is not a cryptographically secured pseudo-random number generator (PRNG), especially for any operation that implies security, like password generation. The java source code of the class is pretty easy to read and this challenge is a good occasion to dive into this PRNG internal implementation (JDK7+):
- The whole processed is based on an initial seed (
S0) - New seeds (
Sn) are sequencially computed from prevous seeds (Sn-1) - The inner state of the seed is 48-bits long
- To compute the next seed, Java uses 2 constants: a
multiplierand anaddend - When a random value is required (byte, int, bool…), the next seed is computed and the random value derived from it
- In the case of the nextInt(), the next random integer is just the current seed modulus 2^32:
Sn mod 2^32which is equivalent toSn >>> (48 - 32) - So at every
nextInt()call, we loose 16 bits of data between the last seed and the current seed: a seed of 48 bits modulus 2^32.
If you read the java.util.Random, you can summarize the operations with the following pseudo-code :
// constants
multiplier = 0x5DEECE66DL;
addend = 0xBL;
mask = (1L << 48) - 1; // 48-bits mask
// compute initial seed
S0 = (seedInParam ^ multiplier) & mask; // seedInParam is: new Random(seedInParam)
// compute next seed
Sn = (Sn-1 * multiplier + addend) & mask;
So what we learnt:
- For each instanciated
Random, random values are computed from a sequence. - If you know the initial seed, you can reverse the generated random values.
- Between each random int, we loose 16 bits of data between 2 seeds, so 65536 values.
So, if you can get 2 integer values, then you can bruteforce the seed with 65536 iterations.
Understanding the algorithm and the problem
Come back to the challenge. The first part of the password generation loop on nextInt() until the integers converted to base36 is at least a string of 10 characters:
while (true) {
// generate a real random 32-bits signed int, ex: 447603982
int i = this.random.nextInt();
// convert integer to base36 (lower case + digits), ex: "7ehpfy"
String passwordPart = Long.toString(i, 36);
// we have signed integers, remove the "minus" sign
passwordPart = passwordPart.replace("-", "");
// append the result to the existing password
password.append(passwordPart);
// ANSSI says password length should be 9 minimum
// stop if we got the minimum complexity
if (password.length() > 10) {
break;
}
}
Integers converted to base36 will produce between 1 and 7 characters (log36(2^32) = 6.18). If you test the code several times, you will see that nextInt() converted to base36 produces most of the time a string of length 6 but also that there is a minus sign in front of the base36 since the int is signed.
Why so often 6 characters? Because between 36^6 and 36^5, you get most of the 2^32 / 2 values (/2 because it’s signed integer):
36^1 = 36
36^2 = 1296
36^3 = 46656
36^4 = 1679616
36^5 = 60466176
36^6 = 2176782336
So the probability it will be 6 characters is 98%:
(36^6 - 36^5) / (2^32 / 2) = 0,985
So we will make the assumption that we will have 2 integers of 6 characters in base36. We can still make other hypothesis later if this one does not verify. The loop will stop if the password length is more than 10. Then, we see that the minus sign is removed. We loose 1 bit of information for each integer, so 2 bits for them.
Then the rest of the code just randomly set the letters uppercase or lowercase randomly, based on the same PRNG:
StringBuilder result = new StringBuilder();
for (int i = 0; i < password.length(); i++) {
// if we have a letter from ascii code + 1 chance out of 2
if (password.charAt(i) > 96 && this.random.nextInt() % 2 == 0) {
// convert the lower case letter to upper case
char x = (char) (password.charAt(i) - 32);
result.append(x);
} else {
// just keep the initial character
result.append(password.charAt(i));
}
}
This last part is not important. Since if we can reverse the seed, we will be able to know certainly what characters will be set upper or lower case afterwards.
With the first 2 passwords, we have the first 4 numbers. We will use the first one to reverse the seed and the 2 last to verify that the seed obtained is good.
Now we split the first password into 2 parts, lower it and convert it back to long:
long i1 = Long.valueOf("7ehpfy", 36);
long i2 = Long.valueOf("gg2gq2", 36);
Then, we need to bruteforce the upper 16-bits of the 48-bits seed since with have the lower 32-bits (remember Sn = (Sn-1 * multiplier + addend) & mask;):
long seed = 0L;
for (int i = 0; i < 65536; i++) {
seed = i1 * 65536 + i;
if (next(seed) == i2) {
// a matching seed is found here!
break;
}
}
To compute the next state of the seed, we just copy the protected int next(int bits) function of Random:
public static int next(long seed) {
int bits=32;
long seed2 = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
return (int)(seed2 >>> (48 - bits));
}
So, when a seed is found, we need to check with the 2nd password value and inject our seed in the SecurePassword class. The seed is not directly injected into the Random construstor but a computation is made to replicate the intiialScramble() function: (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1). We make 10 calls to the nextInt() before injecting it because, this is the number of calls that will be made for upper and lower case computation in the generatePassword() method.
Random random = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48) - 1));
random.nextInt();
for (int i=0;i<9;i++) random.nextInt();
SecurePassword generator = new SecurePassword();
generator.random = random;
System.out.println(generator.generatePassword());
And finally, remember that the minus sign is removed. So we need to bruteforce this minus sign for each integer i1 and i2:
for (int j = 0; j < 4; j++) {
i1 = i1 * -1L;
if (j == 2) i2 = i2 * -1L;
for (int i = 0; i < 65536; i++) {
seed = i1 * 65536 + i;
if (next(seed) == i2) {
break;
}
}
// check if seed is good
...
}
So if we put all the parts together:
package com.formind;
import java.util.Random;
class Solution {
public static int next(long seed) {
int bits=32;
long seed2 = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
return (int)(seed2 >>> (48 - bits));
}
public static void main(String[] args) {
long i1 = Long.valueOf("7ehpfy", 36);
long i2 = Long.valueOf("gg2gq2", 36);
long seed = 0L;
for (int j = 0; j < 4; j++) {
i1 = i1 * -1L;
if (j == 2) i2 = i2 * -1L;
for (int i = 0; i < 65536; i++) {
seed = i1 * 65536 + i;
if (next(seed) == i2) {
break;
}
}
Random random = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48) - 1));
random.nextInt();
for (int i=0;i<9;i++) random.nextInt();
SecurePassword generator = new SecurePassword();
generator.random = random;
String nextPassword = generator.generatePassword();
if (nextPassword.equals("7M7y9YTHt800")) {
System.out.println("Matching seed found! The next password will be:");
System.out.println(generator.generatePassword());
break;
}
}
}
}
And we get in the output the solution of the challenge:
Matching seed found! The next password will be:
CwBwk9F379wo
Side note about the auto-generated seed
You may wondered: when Random is instantiated with no parameters, like new Random(), where does the initial seed comes from?
It is computed from a static long called seedUniquifier, XORed with current nano time (10^-9 seconds): System.nanoTime(). This seedUniquifier has an initial value of 8682522807148012L and multiplied with 1181783497276652981L for each new instance of Random.
This could be simplified with this pseudo-code:
// first instance of Random() with no argument is equivalent to:
new Random(8682522807148012L ^ System.nanoTime())
// second instance of Random()
new Random((8682522807148012L * 1181783497276652981L) ^ System.nanoTime())
// third intsance of Random()
new Random((8682522807148012L * 1181783497276652981L * 1181783497276652981L) ^ System.nanoTime())
....
With this simple example, you can see that the auto-generated seed of the class Random is not that random in fact… It’s just a sequence of long and nano time. For nano time, you still got around 10^9 values to guess if you know the creation datetime of the secret which can be achieved in 1 min on a nowadays workstation CPU.
But it’s not the end! The previous statement is valid with JDK7+, but you may encounter JDK6 in pentest and this gets even worst with the :
public Random() { this(++seedUniquifier + System.nanoTime()); }
private static volatile long seedUniquifier = 8682522807148012L;
Yes yes, you read that correcly: auto-generated seed in Java 6 is just an integer incremented added (not XORed) with nanotime:
// first instance of Random() with no argument is equivalent to:
new Random(8682522807148012L + System.nanoTime())
// second instance of Random()
new Random((8682522807148012L + 1L) + System.nanoTime())
// third intsance of Random()
new Random((8682522807148012L + 1L + 1L) ^ System.nanoTime())
....
It means that with this version, you do not have to bruteforce the seedUniquifier for each nano time. When bruteforcing each nano time, you actually take into account sequences of seedUniquifier by just adding a few more loop iterations.
There do not seem to be CVE on this issue, but it clearly shows the weakness of Random class for security related operations.
Lessons learnt
java.security.SecureRandommust be used for cryptographically secured PRNG (see javadoc) and similar functions is other languages.- Password complexity must meet security best practices like ANSSI and best solution is to use MFA.
- 2 sequential random numbers of
java.util.Randommay be enough to reverse the seed of the instance - 1 random number of
java.util.Randomand the number generateion time may be enough to reverse the seed of the instance
