reverse engineering, 15 teams solved

What is this program emulating? Given an executable and a fake flag.

Reverse the binary

The binary first open flag.txt. Then, it allocates 624 integers and init them using mt19937. The seed is the production of each char in the flag.

The main function also allocates a 2D vector. The vector has a fixed size of 14×14, though the caluclations in the binary are very annoying.

Later, it setup an environment and continuously update the environment until a stop. There is an environment object allocated on the stack of main. The structure looks like this:

env at main:local_13e8 (from ghidra)
env[0] init value=14
env[1] init value=14
env[2] is int (padded for alignment), store the max progress in each update
env[3] is start pointer of the outer vector
env[4] is the end pointer
env[5] is the size of outer vector
...

The deobfuscated meanings:
Env:
long dim_y  // This is the length of the second axis of the 2D vector
long dim_x  // This is the length of the first axis of the 2D vector
int progress  // If this is at least 0xe=14, we get the flag
// padded 4 bytes for 8-alignment
vector<vector<int> > a  [long, long, long]  // The grid
mt19937  = long mt[624], long index_mt  // The rng sequence

The meaning of each address is decoded in ghidra by renaming some of them into meaningful name and inspect the code.

In the Environment namespace, there are three functions: set, update and react. At first I ignored the set, but it is crucial to the interaction.

The set function gets two random numbers from the mt19937 rng, and only use the last two bits. The two 2-bits numbers are added by 1 so that we get two numbers between 1 and 4. Then it write the two numbers to the output, using raw bytes, and read two raw bytes from input. Here comes the interaction: the first byte is the column we want to modify, and the second byte is the direction. The four different directions all place the two numbers previous generated to the highest row and the user-input column of the grid.

Say, a0 and a1 are the random numbers generated between 1 and 4. If direction is 0, and user-input column is col, the game will place a0 at the highest row and col column, and a1 at the second highest row and col column. The other 3 directions are similar.

Then set returns to update. Part of the function performs a tighting operation, which means for each column, it put the non-zero values at the start, leaving the rest zerod. The other part of the function performs a call to react.

By now, I already spent 5 hours inspecting the meaning of each line. To avoid reading more code, here is the trick that saved my life

Make assumptions

The emulator probably is a game. Each time, a tile of 1×2 with two colors drop from the top. There are a total of 4 colors. Just feed these information to ChatGPT, and we quickly get the name of the game: Puyo Puyo.

The prompt is:

what is the game that has four colors, each time given two colors and you drop it from top ?

Then we can entirely skip the react function. It eliminates a block of at least four same color.

The goal of the emulator is to use one move to make 14 chain reactions.

Construction

At first, it seems very hard to construct it manually. One method generally applicable to such games is dfs. However, under such strict and strange scenario, my sense of competitive programming tells me that dfs is not going to work even with lots of optimizations.

The solution is to construct something like this:

    1
    v
1222
2111
1444
4111
1333
3111
1222
2111
1444
4111
1333
3111
1222
2111 ........

or

zyyy
yxxx

At the end of the game, drop a 1 to the fifth column and we get a chain of 14 reactions.

Given the static nature of the problem, we can first record the game inputs.

Because the numbers are random, we cannot guarantee that there exists an order to place the blocks exactly like what we expect. In fact, we only have to make sure that there are no adjacent identical numbers.

Solution

First generate a sequence of 15 numbers without adjacent identical numbers.

Then, construct the first column using a greedy matching algo. Do it for the second column as well.

For the third and fourth column, combine them together and use a greedy matching algo as well.

However, since tiles with the same numbers are rare, the third and fourth column often fails. To address this issue, we can fix a prefix of the sequence of 15 numbers to an already-exist sequence in the game inputs.

For each of the garbage inputs, tile them at the right side of the grid.

from pwn import *

a = []

with open("./input_server.txt", "r") as fp:
    for i in range(98-0):
        x, y = fp.readline().split(" ")
        x = int(x)
        y = int(y)
        a.append((x, y))


waste_row = 0
waste_col = 5

s = [
4,
3,
4,
3,
2,
4,
1,
2,
1,
4,
]
# s = [random.randint(1, 4)]
while len(s) < 15:
    while (t:=random.randint(1, 4)) == s[-1]:
        pass
    s.append(t)

print(s)

# First column, use s[1:15]
res = [None] * 92
w = 0
for i in range(1, 15, 2):
    t1, t2 = s[i], s[i+1]
    while w < len(res):
        if res[w] is None:
            if a[w] == (t1, t2):
                res[w] = (0, 2)
                break
            elif a[w] == (t2, t1):
                res[w] = (0, 0)
                break
        w += 1
    if w == len(res):
        print("fail")
        exit()

# Second column, use s[0:14]
w = 0
for i in range(0, 14, 2):
    t1, t2 = s[i], s[i+1]
    while w < len(res):
        if res[w] is None:
            if a[w] == (t1, t2):
                res[w] = (1, 2)
                break
            elif a[w] == (t2, t1):
                res[w] = (1, 0)
                break
        w += 1
    if w == len(res):
        print("fail")
        exit()

# Third and fourth column, use s[0:14]
"""
4 4
3 3
4 4
3 3
2 2
4 4
1 1
2 2
1 1
4 4
"""


w = 0
for i in range(14):
    while w < len(res):
        if res[w] is None:
            if a[w] == (s[i], s[i]):
                res[w] = (2, 1)
                break
        w += 1
    print(f"3-4 columns  i {i} w {w}")
    if w == len(res):
        print("fail")
        exit()

last_one = None
for i in range(len(res)):
    if res[i] is None:
        res[i] = (waste_col, 0)
        waste_row += 2
        if waste_row == 14:
            waste_row = 0
            waste_col += 1
    else:
        last_one = i

for i in range(last_one+1, len(res)):
    if a[i][0] == s[0]:
        res[i] = (4, 2)
        break
    elif a[i][1] == s[0]:
        res[i] = (4, 0)
        break
    if i+1==len(res):
        print("fail")
        exit()

# print(res)
# exit()
p = remote("reaction.seccon.games", 5000)
# p = process("./chemic")
# input(f"{p.pid}")

for i, (col, op) in enumerate(res):
    b = p.recv(2)
    print(b[0], b[1])
    if b[0] > 4 or b[1] > 4:
        break
    # if True or i >= last_one:
    #     input()
    p.send(bytes([col, op]))

print(p.recvall(1))

I’m so excited to solve this problem in the last hour, as a freshman !!