# BucketCTF 2023 Writeup

## Rev - Maze (Hard, 478 pts)

Team: `cursedCTF`
Author: `sahuang#6271`

### Description

> After you solved my last challenge I have upped my game. This time there is no way you will find the flag. Im so confident you will lose that I will give you the file to the game. Good luck! You're gonna need it.
>
> Attachment: https://storage.ebucket.dev/Maze.class

### Initial Analysis

In this reverse engineering challenge, we were provided with a Java class file `Maze.class`. As usual, let's first decompile it - I used [Decompilers online](http://www.javadecompilers.com/) and this gave me the following source code:

import java.io.FileNotFoundException;
import java.util.Scanner;
import java.io.File;
import java.util.Random;

// 
// Decompiled by Procyon v0.5.36
// 

public class Maze
{
    public static char[][] maze;
    public static Random random;
    
    public static String getFlag() {
        try {
            return new Scanner(new File("flag.txt")).nextLine();
        }
        catch (FileNotFoundException ex) {
            System.out.println("There has been an unexpected error. Please report this to the CTF admins.");
            return "";
        }
    }
    
    public static void initMap() {
        System.out.println("I've learned from my mistakes and this time I will construct a full maze you will never be able to break out of!!!");
        Maze.maze = new char[41][41];
        for (int i = 1; i <= 20; ++i) {
            if (i % 2 == 1) {
                for (int j = 20 - i; j <= 20 + i; ++j) {
                    for (int k = 20 - i; k <= 20 + i; ++k) {
                        if (j == 20 - i || j == 20 + i || k == 20 - i || k == 20 + i) {
                            Maze.maze[j][k] = '#';
                        }
                    }
                }
            }
        }
        for (int l = 0; l < Maze.maze.length; ++l) {
            for (int n = 0; n < Maze.maze[l].length; ++n) {
                if (Maze.maze[l][n] != '#') {
                    Maze.maze[l][n] = ' ';
                }
                System.out.print(Maze.maze[l][n]);
            }
            System.out.println();
        }
        for (int n2 = 0; n2 < 10; ++n2) {
            final int bound = 3 + n2 * 4;
            final int nextInt = Maze.random.nextInt(bound);
            switch (Maze.random.nextInt(4)) {
                case 0: {
                    Maze.maze[20 + bound / 2][20 - bound / 2 + nextInt] = ' ';
                    break;
                }
                case 1: {
                    Maze.maze[20 - bound / 2 + nextInt][20 + bound / 2] = ' ';
                    break;
                }
                case 2: {
                    Maze.maze[20 - bound / 2][20 - bound / 2 + nextInt] = ' ';
                    break;
                }
                case 3: {
                    Maze.maze[20 - bound / 2 + nextInt][20 - bound / 2] = ' ';
                    break;
                }
            }
        }
        Maze.maze[20][20] = 'X';
    }
    
    public static void main(final String[] array) {
        initMap();
        int n = 20;
        int n2 = 20;
        try {
            final Scanner scanner = new Scanner(System.in);
            while (true) {
                final char char1 = scanner.next().charAt(0);
                if (char1 == 'Q') {
                    if (Maze.maze[n - 1][n2 - 1] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[--n][--n2] = 'X';
                }
                if (char1 == 'W') {
                    if (Maze.maze[n - 1][n2] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[--n][n2] = 'X';
                }
                if (char1 == 'E') {
                    if (Maze.maze[n - 1][n2 + 1] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[--n][++n2] = 'X';
                }
                if (char1 == 'D') {
                    if (Maze.maze[n][n2 + 1] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[n][++n2] = 'X';
                }
                if (char1 == 'C') {
                    if (Maze.maze[n + 1][n2 + 1] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[++n][++n2] = 'X';
                }
                if (char1 == 'S') {
                    if (Maze.maze[n + 1][n2] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[++n][n2] = 'X';
                }
                if (char1 == 'Z') {
                    if (Maze.maze[n + 1][n2 - 1] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[++n][--n2] = 'X';
                }
                if (char1 == 'A') {
                    if (Maze.maze[n][n2 - 1] == '#') {
                        break;
                    }
                    Maze.maze[n][n2] = ' ';
                    Maze.maze[n][--n2] = 'X';
                }
                if (char1 == 'R') {
                    System.out.println("Here is a random number for you since i'm nice: " + Maze.random.nextDouble());
                }
            }
            scanner.close();
            System.out.println("YOU LOSE I WIN! BETTER LUCK NEXT TIME!");
        }
        catch (Exception ex) {
            if (ex instanceof ArrayIndexOutOfBoundsException) {
                System.out.println(getFlag());
            }
        }
    }
    
    static {
        Maze.random = new Random();
    }
}

Now we can dive into the source code and try to understand what the goal is.

1. `initMap`

Maze.maze = new char[41][41];
for (int i = 1; i <= 20; ++i) {
    if (i % 2 == 1) {
        for (int j = 20 - i; j <= 20 + i; ++j) {
            for (int k = 20 - i; k <= 20 + i; ++k) {
                if (j == 20 - i || j == 20 + i || k == 20 - i || k == 20 + i) {
                    Maze.maze[j][k] = '#';
                }
            }
        }
    }
}
for (int l = 0; l < Maze.maze.length; ++l) {
    for (int n = 0; n < Maze.maze[l].length; ++n) {
        if (Maze.maze[l][n] != '#') {
            Maze.maze[l][n] = ' ';
        }
        System.out.print(Maze.maze[l][n]);
    }
    System.out.println();
}

In the first half, a 41 by 41 matrix is generated, representing a Maze. We could easily connect to remote server and see what it is like:


Well, it doesn't seem like the maze is solvable... And the next code block is particularly interesting:

for (int n2 = 0; n2 < 10; ++n2) {
    final int bound = 3 + n2 * 4;
    final int nextInt = Maze.random.nextInt(bound);
    switch (Maze.random.nextInt(4)) {
        case 0: {
            Maze.maze[20 + bound / 2][20 - bound / 2 + nextInt] = ' ';
            break;
        }
        case 1: {
            Maze.maze[20 - bound / 2 + nextInt][20 + bound / 2] = ' ';
            break;
        }
        case 2: {
            Maze.maze[20 - bound / 2][20 - bound / 2 + nextInt] = ' ';
            break;
        }
        case 3: {
            Maze.maze[20 - bound / 2 + nextInt][20 - bound / 2] = ' ';
            break;
        }
    }
}
Maze.maze[20][20] = 'X';

A few random numbers are generated, and in each level of the maze square, one of the `#` will be replaced by a space, leaving the maze escapable. `java.util.Random` is the package used for Random Number Generator.

In the end, this new Maze will not be printed, therefore we have to somehow "predict" where are the holes for us to escape the Maze. Here is a visualization if you want to see how actual Maze looks like:


2. `main`

The program accepts different keyboard inputs to decide the next move of our player, labelled "X". In each move, we check if the grid to move to is valid (i.e. not `#`), if so, updates the position.

- Q: top-left
- W: up
- E: top-right
- D: right
- C: bottom-right
- S: down
- Z: bottom-left
- A: left

You could edit the source code to make the program print Maze state after each input - this helps you understand where we are.

**The key option is the "R" command** - it allows program to generate a random double and print on screen. We can get as many doubles as we want to.


With the analysis above, the goal seems very clear now:

- Using output from `Maze.random.nextDouble()`, predict the current RNG state;
- Using this state, propagate backwards and get the outputs of `Maze.random.nextInt(num)`. This includes `num=bound` and `num=4`.
- Get the actual Maze with holes in each square and get a path out.

### Cracking Java Random

As you might alreayd know, Java random class is essentially a linear congruential generator. The `Random` class uses a 48-bit seed, which is modified using some LCG formula. We can look up the [Java doc](https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#nextDouble--) to see how `nextDouble()` generates the double:

public double nextDouble() {
    return (((long)next(26) << 27) + next(27)) 
    / (double)(1L << 53);
}

The definition of `next`:

protected int next(int bits)

Generates the next pseudorandom number. 

The method next is implemented by class Random by atomically updating the seed to

(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

and returning

(int)(seed >>> (48 - bits)).

I also found a Github Repo that replicates Java random prediction: [ReplicatedRandom](https://github.com/fta2012/ReplicatedRandom/blob/9afc08ad5f5aa67808b8b6a9f3a3523ea99e1e57/ReplicatedRandom.java#L6). This allows us to use Python to rewrite the whole Java LCG in Python, then use ReplicatedRandom to verify that our code is correct. ReplicatedRandom will basically use `double nextDouble` to obtain possible seeds (likely unique), then use this seed to predict the next double/int/float etc.

In our case, we actually only care about the **past state** instead of next values. But well, let's just implement this and see if we get the seed right.

def replicateState1(nextDouble):
    numerator = int(nextDouble * (1 << 53))
    first26 = int(numerator >> 27)
    last27 = int(numerator & ((1 << 27) - 1))
    return replicateState(first26, 26, last27, 27)

def replicateState(nextN, n, nextM, m):
    multiplier = 0x5DEECE66D
    addend = 0xB
    mask = (1 << 48) - 1

    upperMOf48Mask = ((1 << m) - 1) << (48 - m)
    oldSeedUpperN = (nextN << (48 - n)) & mask
    newSeedUpperM = (nextM << (48 - m)) & mask

    possibleSeeds = []
    for oldSeed in range(oldSeedUpperN, (oldSeedUpperN | ((1 << (48 - n)) - 1))+1):
        newSeed = (oldSeed * multiplier + addend) & mask
        if (newSeed & upperMOf48Mask) == newSeedUpperM:
            possibleSeeds.append(oldSeed)
    return possibleSeeds

And we feed in one of the values from remote to check the seed:

seed = replicateState1(0.05969299174878506)[0]
print(f"Seed: {seed}")

# Seed: 16802083600713

Is this correct? Now we write Java code using ReplicatedRandom:

ReplicatedRandom rr = new ReplicatedRandom();
if (rr.replicateState(Double.parseDouble("0.05969299174878506"))) {
    for (int j = 0; j < 10; j++)
        System.out.println(rr.nextDouble());
}

If we run it, we will also get printed seed 16802083600713, which is exactly the same!

Now, the only challenge is to predict the past values. Recall that we wanted to get previous integers, because we used `Maze.random.nextInt(num)`. The order is reverse order of how they are generated, therefore, we need to get the valuesd of:

- `rev_nextInt(4)`
- `rev_nextInt(9 * 4 + 3)`
- `rev_nextInt(4)`
- `rev_nextInt(8 * 4 + 3)`
- ...
- `rev_nextInt(4)`
- `rev_nextInt(0 * 4 + 3)`

Once we got these we can recover the original Maze. Here's how `nextInt` is defined in Java:

public int nextInt(int bound) {
    if ((bound & -bound) == bound)  // i.e., bound is a power of 2
        return (int)((bound * (long)next(31)) >> 31);

int bits, val;
do {
    bits = next(31);
    val = bits % bound;
} while (bits - val + (bound-1) < 0);

return val;
}

Perfect. Although ReplicatedRandom has no such implementation, we do it in Python as well:

def rev_next(bits, seed):
    old_seed = (seed - 0xB) * pow(0x5DEECE66D, -1, 1 << 48) & ((1 << 48) - 1)
    return old_seed, (old_seed >> (48 - bits))

def rev_nextInt(bound, seed):
    if (bound & -bound) == bound:
        seed, bits = rev_next(31, seed)
        return seed, (bound * bits) >> 31

    bits, val = 0, 0
    while True:
        seed, bits = rev_next(31, seed)
        val = bits % bound
        if bits - val + (bound-1) >= 0:
            break
    return seed, val

With this, taking the seed from above, we can reverse and get all `nextInt` values:

seed = 16802083600713

ps = []
for i in range(9, -1, -1):
    seed, val1 = rev_nextInt(4, seed)
    print(f"old_seed: {seed}, val: {val1}")

    seed, val2 = rev_nextInt(i * 4 + 3, seed)
    print(f"old_seed: {seed}, val: {val2}")

    ps.append([val2, val1])

ps = ps[::-1]
print([i[0] for i in ps])
print([i[1] for i in ps])

Debugging locally, we can verify that the values are exactly the same between Python-reversed and Java source code.

old_seed: 2312753278838, val: 0
old_seed: 35002972104247, val: 36
old_seed: 203418350588764, val: 2
old_seed: 223349942034933, val: 21
old_seed: 133579993923410, val: 1
old_seed: 31427043671043, val: 1
old_seed: 173462913093848, val: 2
old_seed: 176917702105057, val: 20
old_seed: 221982420961646, val: 3
old_seed: 174305012092175, val: 14
old_seed: 177757292883604, val: 2
old_seed: 209928807433997, val: 14
old_seed: 244852744759754, val: 3
old_seed: 147293911917915, val: 11
old_seed: 119957769660560, val: 1
old_seed: 106656706222969, val: 2
old_seed: 245075847494758, val: 3
old_seed: 222938578325735, val: 1
old_seed: 18132760623820, val: 0
old_seed: 58245770952997, val: 1
[1, 1, 2, 11, 14, 14, 20, 1, 21, 36]
[0, 3, 1, 3, 2, 3, 2, 1, 2, 0]

### Solve

The final step is relatively easy. Because we have the original Maze, I simply split opened two terminals on my screen. On the left side, I connected to server. On the right side, I editted source code to print the player location after each movement, and then replicate it on server.

This step is purely manual, it is definitely better with a program but why code if you can use manpower :)


This gives the final flag. Pretty interesting challenge to learn about Java randomness. A simple known double can be exploited and we can recover or predict anything!