any% ssg

LACTF 2024
,

Check out this new open-source version of Minecraft my friend is making! They started working on it yesterday, but I want to speedrun it before anyone else can … can you find me a seed that makes the end portal complete? Run the game with java -jar my-new-game.jar.
Send your seed to nc chall.lac.tf 31170 to get the flag.

So we are given a bootleg Minecraft seed generator in a .jar file. Opening it, we can see that after entering a seed, it will generate a “world”, which contains an end portal.

The end portal is the squares around the big orange square, (there are 16). If the circle is black, its not filled, if its green, its filled. We need to fill all 16 squares to win.

Generation

Lets take a look at how they generate the world:

Game.java
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private void generateBoard(){
    for (int i = 0; i<sizeX; i++) {
        for (int j = 0; j<sizeY; j++) {
            board.setTile(i,j,new Tile("grass"));
        }
    }

    for (int i = 0; i<5; i++) {


        board.generateCircle(r,new Tile("stone"));


    }


    for (int i = 0; i<3; i++) {


        board.generateCircle(r,new Tile("water"));


    }


    board.generateStronghold(r);

    board.updatePlayer();
}

First, it generates 5 stone circles, then 3 water circles, then finally the stronghold. Now, we look at how these are internally implemented. generateCircle:

Board.java
113
114
115
116
117
118
119
120
121
122
123
124
public void generateCircle(CustomRandom r, Tile t) {
    int radius = Math.floorMod((int) r.nextLong(), 15);
    int circleX = Math.floorMod((int) r.nextLong(), sizeX);
    int circleY = Math.floorMod((int) r.nextLong(), sizeY);
    for (int i = circleX - radius; i<= circleX + radius; i++) {
        for (int j = circleY - radius; j<=circleY+radius; j++) {
            if (i >= 0 && i < sizeX && j >= 0 && j < sizeY && (Math.pow(i-circleX,2) + Math.pow(j-circleY,2))<=Math.pow(radius,2)) {
                setTile(i,j,t);
            }
        }
    }
}

It calls nextLong(), which is a customly implemented RNG, 3 times, for the x-, y- coordinates, and the radius (not important lol). Since we generate 8 circles, thats 24 calls so far to nextLong(). Now, generateStronghold:

Board.java
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
111
public void generateStronghold(CustomRandom r) {
    boolean[] filledEyes = new boolean[16];
    int strongholdLocationX = Math.floorMod((int)r.nextLong(), sizeX-5);
    int strongholdLocationY = Math.floorMod((int)r.nextLong(), sizeY-5);
    boolean allFilled = true;
    for (int i = 0; i<16; i++) {
        long n = r.nextLong();
        if (n > (9 * (1L << 52)/10L)) {
            filledEyes[i] = true;
        }
        else {
            filledEyes[i] = false;
            allFilled = false;
        }
    }

75-110

}

After 2 calls to nextLong() for the coordinates, the next 16 calls to nextLong() determine whether each eye has to be filled. Each output has to be greater than (9 * (1L << 52)/10L) which is basically 910252\frac{9}{10} 2^{52} .

CustomRandom

So, how exactly does nextLong() work?

CustomRandom.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.time.Instant;
public class CustomRandom {
    private long seed;
    private final long i = 3473400794307473L;

    public CustomRandom() {
        this.seed = Instant.now().getEpochSecond() ^ i;
    }

    public void setSeed(long seed) {
        this.seed = seed ^ i;
    }

    public long nextLong() {
        long m = 1L << 52;
        long c = 4164880461924199L;
        long a = 2760624790958533L;
        seed = (a *seed+ c) & (m -1L);
        return seed;
    }
}

So, you input a seed, and every time it needs to generate a new output, it does seed = (a *seed+ c) & (m -1L) and returns seed, so some sort of funny recurrence relation. This looks suspiciously like an LCG.

Upon closer exception, m-1L is just 1<<52 - 1 which is 111⋯1⏟51 1’s\underbrace{111\cdots1}_\textrm{51 1's}, so taking & with that takes the last 51 bits of (a*seed+c). If you think about it, taking the last 3 digits of a number in decimal is the same as taking (mod103)\pmod{10^3}, so similarly, taking the last 51 bits is the same as taking (mod252)\pmod{2^{52}}.

Now, we have seed = (a*seed + c) % (2**52) which is actually an LCG. This means, that what we need to do is find a seed such that after 24+2=2624+2=26 calls, the next 16 LCG outputs are all within the range 910252<x<252\frac{9}{10} 2^{52}<x<2^{52}.

LLL

LLL is a lattice reduction algorithm which finds a basis with short, nearly orthogonal vectors when given an integer lattice basis as input.

An integer lattice with a basis {v1,⋯ ,vn}\{v_1, \cdots, v_n\} is

{∑i=1naivi∣ai∈Z}\bigg\{\sum_{i=1}^n a_iv_i \bigg| a_i \in \mathbb{Z} \bigg\}

So for example with n=2, you would get a bunch of regularly spaced dots in 2D space.

Since the algorithm finds a basis, it finds vectors that are a linear combination of the existing basis. It tries to find a short basis as well, which means one whose vectors have a small absolute value. So, to apply this in a cryptographic context, we can supply LLL with vectors {v1,⋯ ,vn}\{v_1, \cdots, v_n\} and expect a linear combination of those vectors which is roughly minimized.