DownUnderCTF 2021 was held the weekend of September 25, 2021. bullet hell was an interesting reversing challenge. It was essentially an ASCII game in which the player was required to dodge an onslaught of bullets, reminiscent of a “bullet hell” video game. The only thing is, the bullets were invisible.
The challenge
We’re given the following:
bullet hell
medium
Can you survive in this land of illusions?
SSH password:
ductfAuthor: joseph#8210
ssh ductf@pwn-2021.duc.tf -p 31911
We’re also given a binary named bullet_hell:
% sha256sum bullet_hell
fdbe8686b1f8b94149d717c8784b13163997bdad352c5c7b7235dbd3f1e15b1e bullet_hell
% file bullet_hell
bullet_hell: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV),
dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2,
BuildID[sha1]=0135b62c466cb5ea9f1767a765df1bf4fed2cf28, for GNU/Linux 4.4.0, not
stripped
Upon SSH’ing to the provided server we’re greeted with the message Enter a key to start...
Upon pressing a key we’re presented with a TUI which appears to be an ASCII-based game.
┌─────────────────────────────┐
│ │
│ │ score: 1
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ p │
│ │
│ │
│ │
│ │
│ │
│ │
└─────────────────────────────┘
If no keys are pressed, absolutely nothing happens until the score reaches 62 before dumping us back to our own local shell with the message You lose :(.
The binary
Throwing bullet_hell into Ghidra we see that it imports libc.so.6 and libncursesw.so.6 (giving us the TUI game environment).
main() decompiles to:
undefined8 main(void)
{
srand(0);
initscr();
cbreak();
noecho();
keypad(stdscr,1);
printw("Enter a key to start...\n");
wgetch(stdscr);
wrefresh(stdscr);
play();
return 0;
}
Of particular interest is the call to srand() with a constant (zero) value. rand(3) says:
The
srand()function sets its argument as the seed for a new sequence of pseudo-random integers to be returned byrand(). These sequences are repeatable by callingsrand()with the same seed value.
And so we know off the bat that if this game calls rand() at any point, the values that it returns will be identical across different executions of the game. To be sure of this, we can look for xrefs to srand() in the binary and can check that the only call happens from main().
thunk void srand(uint __seed)
Thunked-Function: <EXTERNAL>::srand
void <VOID> <RETURN>
uint EDI:4 __seed
<EXTERNAL>::srand XREF[1]: main:00101c87(c)
[... SNIP ...]
No xrefs aside from within main(). Excellent.
Tidying up the decompilation of the play() function gives us the following:
void play(void)
{
int rc;
int user_input;
state_struct *state;
undefined8 game_field;
undefined8 uVar1;
int tick;
/* allocate game state struct */
state = (state_struct *)malloc(0x20);
/* initialise game state */
state->player_x = 15;
state->player_y = 33;
/* set up game field */
uVar1 = 0x101a38;
game_field = newwin(0x29,0x1f,0,0);
wborder(game_field,0,0,0,0,0,0,0,0,uVar1);
wrefresh(game_field);
/* Set a wgetch timeout of 1 second */
wtimeout(stdscr,1000);
tick = 0;
do {
/* main game loop */
tick = tick + 1;
if (tick % 25 == 0) {
generate_bullets(state);
}
wclear(game_field);
mvprintw(2,0x20,"score: %d\n",state->score);
update_bullets(game_field,state);
uVar1 = 0x101b3e;
rc = wmove(game_field,state->player_y,state->player_x);
if (rc != -1) {
uVar1 = 0x101b54;
winsch(game_field,0x70);
}
wborder(game_field,0,0,0,0,0,0,0,0,uVar1);
wmove(stdscr,0,0);
wrefresh(game_field);
/* Get input from player */
user_input = wgetch(stdscr);
if (user_input == L'h') {
/* move left */
if (1 < state->player_x) {
state->player_x = state->player_x + -1;
}
}
else {
if (user_input == L'j') {
/* move down */
if (state->player_y < 39) {
state->player_y = state->player_y + 1;
}
}
else {
if (user_input == L'k') {
/* move up */
if (1 < state->player_y) {
state->player_y = state->player_y + -1;
}
}
else {
if ((user_input == L'l') && (state->player_x < 29)) {
/* move right */
state->player_x = state->player_x + 1;
}
}
}
}
state->score = state->score + 1;
if (1336 < state->score) {
/* exit vim */
win();
}
} while( true );
}
This function does the following:
- Initialises what I’m calling the game “state”, putting the user at position (15, 33)
- Draws the screen
- Does
wtimeout(stcscr, 1000);(wtimeout(3)) to set an input timeout of 1000 milliseconds. Note that Ghidra did not initially identify the second parameter towtimeout()- this had to be fixed up. - Kicks off the main game loop
The main game loop does the following:
- Increments the tick count
- If the tick count is a multiple of 25, “generate” some bullets
- Draws/redraws the game screen, printing the current score in the process and “updating” the bullets. Interestingly, the score within the
state_structappears to be a use of uninitialised memory :eyes: luckily thestate_structwasmalloc()’d very early on in the process’ lifetime, so it’s getting fresh memory? - Gets a character of input from the player using
wgetch(). Due to the earlier call towtimeout(), if the player doesn’t input anything for 1000 milliseconds, this will beERR. - Moves the player
- If they pressed
hand their current x coordinate is > 1, decrement their x coordinate by one - Else if they pressed
jand their current y coordinate is < 39, increment their y coordinate by one - Else if they pressed
kand their current y coordinate is > 1, decrement their y coordinate by one - Else if they pressed
land their current x coodinate is < 29, increment their x coordinate by one - Else do nothing
- If they pressed
- Increments the user’s score by one
- If the user’s score is >= 1337, call
win()
The win() function simply prints the contents of a file named flag.txt
The generate_bullets() function, untouched, is as follows:
void generate_bullets(state_struct *state)
{
int iVar1;
uint uVar2;
int iVar3;
int *piVar4;
undefined4 *puVar5;
uint uVar6;
int local_5c;
int local_58;
int local_54;
int local_50;
int local_4c;
int local_48;
void *local_30;
local_5c = (int)state->field_0x18;
if (state->field_0x10 == (void *)0x0) {
local_30 = calloc(0x46,8);
}
else {
local_30 = (void *)reallocarray(state->field_0x10,(long)(local_5c + 0x23),8);
}
iVar1 = rand();
uVar6 = (uint)(iVar1 >> 0x1f) >> 0x1e;
uVar2 = iVar1 + uVar6 & 3;
iVar1 = uVar2 - uVar6;
if (uVar2 == uVar6) {
for (local_58 = 0; local_58 < 0x23; local_58 = local_58 + 1) {
piVar4 = (int *)malloc(0x10);
iVar1 = rand();
*piVar4 = iVar1 % 0x1d + 1;
iVar1 = rand();
piVar4[1] = iVar1 % 0xd + 1;
piVar4[2] = 0;
piVar4[3] = 1;
*(int **)((long)local_5c * 8 + (long)local_30) = piVar4;
local_5c = local_5c + 1;
}
}
else {
if (iVar1 == 1) {
for (local_54 = 1; local_54 < 0x23; local_54 = local_54 + 1) {
puVar5 = (undefined4 *)malloc(0x10);
uVar2 = rand();
if ((uVar2 & 1) == 0) {
*puVar5 = 1;
puVar5[2] = 1;
}
else {
*puVar5 = 0x1d;
puVar5[2] = 0xffffffff;
}
puVar5[1] = local_54;
puVar5[3] = 1;
*(undefined4 **)((long)local_5c * 8 + (long)local_30) = puVar5;
local_5c = local_5c + 1;
}
}
else {
if (iVar1 == 2) {
iVar1 = rand();
iVar3 = rand();
for (local_50 = 1; local_50 < 0x1e; local_50 = local_50 + 1) {
if ((local_50 != iVar1 % 0x1d + 1) && (local_50 != iVar3 % 0x1d + 1)) {
piVar4 = (int *)malloc(0x10);
*piVar4 = local_50;
piVar4[1] = 1;
piVar4[2] = 0;
piVar4[3] = 1;
*(int **)((long)local_5c * 8 + (long)local_30) = piVar4;
local_5c = local_5c + 1;
}
}
}
else {
if (iVar1 == 3) {
for (local_4c = 0; local_4c < 4; local_4c = local_4c + 1) {
iVar1 = rand();
iVar3 = rand();
for (local_48 = 0; local_48 < 8; local_48 = local_48 + 1) {
piVar4 = (int *)malloc(0x10);
*piVar4 = iVar1 % 0x1d + 1;
piVar4[1] = iVar3 % 0x27 + 1;
switch(local_48) {
case 0:
piVar4[2] = 1;
piVar4[3] = 0;
break;
case 1:
piVar4[3] = 1;
piVar4[2] = piVar4[3];
break;
case 2:
piVar4[2] = 0;
piVar4[3] = 1;
break;
case 3:
piVar4[2] = -1;
piVar4[3] = 1;
break;
case 4:
piVar4[2] = -1;
piVar4[3] = 0;
break;
case 5:
piVar4[3] = -1;
piVar4[2] = piVar4[3];
break;
case 6:
piVar4[2] = 0;
piVar4[3] = -1;
break;
case 7:
piVar4[2] = 1;
piVar4[3] = -1;
}
*(int **)((long)local_5c * 8 + (long)local_30) = piVar4;
local_5c = local_5c + 1;
}
}
}
}
}
}
state->field_0x10 = local_30;
state->field_0x18 = (long)local_5c;
return;
}
Gross.
The update_bullets() function, also untouched, is as follows:
void update_bullets(undefined8 game_field,state_struct *state)
{
int *__ptr;
void *pvVar1;
int local_24;
int local_20;
int local_1c;
if (state->field_0x10 != (void *)0x0) {
for (local_24 = 0; (ulong)(long)local_24 < state->field_0x18; local_24 = local_24 + 1) {
__ptr = *(int **)((long)local_24 * 8 + (long)state->field_0x10);
if (__ptr != (int *)0x0) {
if ((*__ptr == state->player_x) && (__ptr[1] == state->player_y)) {
die();
}
*__ptr = *__ptr + __ptr[2];
__ptr[1] = __ptr[1] + __ptr[3];
if ((((*__ptr < 1) || (0x1d < *__ptr)) || (__ptr[1] < 1)) || (0x27 < __ptr[1])) {
free(__ptr);
*(undefined8 *)((long)local_24 * 8 + (long)state->field_0x10) = 0;
}
}
}
pvVar1 = calloc((long)local_24,8);
local_20 = 0;
for (local_1c = 0; local_1c < local_24; local_1c = local_1c + 1) {
if (*(long *)((long)local_1c * 8 + (long)state->field_0x10) != 0) {
*(undefined8 *)((long)local_20 * 8 + (long)pvVar1) =
*(undefined8 *)((long)state->field_0x10 + (long)local_1c * 8);
local_20 = local_20 + 1;
}
}
free(state->field_0x10);
state->field_0x10 = pvVar1;
}
return;
}
Almost as gross.
Of particular note is the fact that the generate_bullets() function calls rand(), and the update_bullets() function will, if the player’s x and y coordinates match some particular value (likely the x and y coordinates of a bullet), call die(). The die() function simply does puts("You lose :("); and exit(1);.
At this point, we know that we need to have the score (which increments each tick) reach 1337 in order to print the flag. We can move using the hjkl keys, and if we press a key that is not in this list then the game will advance one tick without changing our position. We get the sense that the positions of bullets are being randomly generated every 25 ticks according to a statically seeded random number generator, and that if we collide with a bullet we die.
We get the sense that, if we can discover a sequence of movements that allows us to dodge the bullets for 1337 ticks of an instance of the game, this sequence of movements should win for every instance of a game, thanks to the statically seeded random number generator. It should also work on the challenge server provided it uses an identically seeded random number generator. This is easily proven; by running the binary locally and simply holding down each of h, j, k and l we get the scores 76, 62, 198 and 48 respectively. By connecting to the challenge server and doing the same, we get the same results.
A few ways we could proceed are as follows:
- We could attempt to understand how
generate_bullets()works and discover a sequence of movements that avoids the generated bullets. - We could patch or instrument the local binary to make the bullets visible and could discover a sequence of movements that avoids the generated bullets.
- We could locally brute-force a sequence of movements that avoids the generated bullets.
Given a sequence of movements that locally avoids the generated bullets, replaying this sequence against the challenge server should also avoid the bullets remotely and should result in the flag.
I didn’t feel like doing either 1 or 2.
Brute force“Machine learning” go brr
My plan was to do the following:
- Send random inputs to a local instance of the game. I decided to include a non-movement key in the choices of what were sent, to induce some occasional “stay still” behaviour
- Read the score that the random inputs achieved
- Send a similar input to what was just sent, but take a few steps “backwards” from when a bullet was collided with and then add more random movements
- Repeat until a random set of movements is discovered which dodges all the bullets
First of all we had to create a “run the game locally with a given sequence of movements” capability.
To start with I created a random local flag:
% echo 'DUCTF{sample_flag}' > flag.txt
I wrote some regular expressions that matched the game’s score output, as well as this flag format (which is also the format used in the contest):
import re
re_score = re.compile(b"score: (\\d+)\r")
re_flag = re.compile(b"DUCTF\\{.*?\\}")
And I implemented a function that will take a stream of movements (represented as integers) and will play a game with those movements. If a complete flag is seen it will immediately return the reached score and the seen flag, else it will play until it runs out of movements, or until it dies, and will return just the score that was reached.
from collections import namedtuple
import itertools
import pwn
from typing import Iterable
PlayResult = namedtuple("PlayResult", ["score", "flag"])
@pwn.context.quietfunc
def play_locally(movements: Iterable[int]) -> PlayResult:
"""
Play a local game according to the given movements until flag or death
Return the score reached, and the flag (if found)
"""
movements_iter = iter(movements)
movements_chunk_size = 64
score = 0
with pwn.process(["bullet_hell"]) as t:
# Start the game
t.sendlineafter(b"Enter a key to start...", b"")
# Send movements until the game ends
try:
while t.connected():
# Send the next chunk of movements
movements_chunk = bytes(itertools.islice(movements_iter,
movements_chunk_size))
t.send(movements_chunk)
# Read some data
data = t.clean()
# Check to see if we just read a score
# If so, update score to be the last-seen score.
# h/t <https://stackoverflow.com/a/2988680>
score_match = None
for score_match in re_score.finditer(data):
pass
if score_match is not None:
score_read = int(score_match.groups()[0])
score = score_read if score_read > score else score
# Check to see if we read a flag
for flag_match in re_flag.finditer(data):
# Winner winner
return PlayResult(score, flag_match.group())
# Put some data back in the tube in case we partially
# read a score or flag
t.unrecv(data[-128:])
except StopIteration:
print("Ran out of movements :(")
# We've either died or run out of movements
return PlayResult(score, None)
We can use this function with our repeated “h”, “j”, “k” and “l” test cases from earlier to check that we get the same results.
def main():
for direction in ["h", "j", "k", "l"]:
pwn.info(f"Playing a game with repeated {direction} input")
score, _ = play_locally(itertools.repeat(ord(direction)))
print(f"Got score: {score}")
print()
% ./solve_bullethell.py
[*] Playing a game with repeated h input
Got score: 75
[*] Playing a game with repeated j input
Got score: 61
[*] Playing a game with repeated k input
Got score: 197
[*] Playing a game with repeated l input
Got score: 47
Hmm. We’re seeing scores that are one less than the results we saw earlier when manually playing the game. This is strange, but at least it’s a consistent difference!
How fast does the game play, given random inputs?
import time
import random
possible_movements = list(map(ord, ["h", "j", "k", "l"]))
def main():
num_games = 200
high_score = 0
now = time.time()
for _ in range(num_games):
movements = [random.choice(possible_movements) for _ in range(1337)]
score, flag = play_locally(movements)
high_score = max(high_score, score)
print(f"Played {num_games} games in {time.time() - now:0.02f} seconds. Got a high score of {high_score}")
% ./solve_bullethell.py
Played 200 games in 13.70 seconds. Got a high score of 228
Not bad, but not good. Recall that the play_locally() function chunks its input into 64-byte chunks before sending them as a massive blob of movements. Increasing this value gives us a considerable increase in performance, up to a certain limit - probably until the average game is sending the entire stream of movements in one or two chunks. Let’s bump this chunk size up to 2048, well in excess of the 1337 movements we need to win the game.
@pwn.context.quietfunc
def play_locally(movements: Iterable[int]) -> PlayResult:
"""
Play a local game according to the given movements. Return the score
"""
movements_iter = iter(movements)
movements_chunk_size = 2048
% ./solve_bullethell.py
Played 200 games in 4.67 seconds. Got a high score of 177
That will hopefully do. Do our original values still show sensible results?
def main():
for direction in ["h", "j", "k", "l"]:
pwn.info(f"Playing a game with repeated {direction} input")
score, _ = play_locally(itertools.repeat(ord(direction)))
print(f"Got score: {score}")
print()
% time ./solve_bullethell.py
[*] Playing a game with repeated h input
Got score: 75
[*] Playing a game with repeated j input
Got score: 61
[*] Playing a game with repeated k input
Got score: 197
[*] Playing a game with repeated l input
Got score: 47
./solve_bullethell.py 0.49s user 0.08s system 121% cpu 0.469 total
Looks good to me!
Gradual improvement
Now to implement our “smart” brute-force algorithm. Recall that we want to:
- Send random inputs, including a non-movement key to induce occasional “stay still” behaviour
- Read the score that the random inputs achieved
- Send a similar input to what was just sent, but take a few steps “backwards” from where we died (i.e. backwards from our score’th movement)
- Repeat until a random set of movements is discovered which dodges all the bullets and causes the flag to be printed
Let’s take a small but random number of steps backwards in step 3, to prevent us from getting stuck in exceptionally dangeorus areas of the playing field.
This gives us:
possible_movements = list(map(ord, ["h", "j", "k", "l"]))
possible_inputs = possible_movements + [ord("a")]
def main():
movements_length = 1337
movements = [random.choice(possible_inputs) for _ in range(movements_length)]
for i in itertools.count(1):
score, flag = play_locally(movements)
if flag:
print(f"Final score: {score}")
pwn.success(f"Flag: {flag.decode()}")
return
if i % 10 == 0:
print(f"{i} rounds played. Latest score: {score}")
movements = movements[:score - random.randint(1, 10)]
movements.extend([random.choice(possible_inputs) for _ in
range(movements_length - len(movements))])
% time ./solve_bullethell.py
10 rounds played. Latest score: 175
20 rounds played. Latest score: 301
30 rounds played. Latest score: 397
40 rounds played. Latest score: 428
50 rounds played. Latest score: 497
60 rounds played. Latest score: 648
70 rounds played. Latest score: 796
80 rounds played. Latest score: 1248
90 rounds played. Latest score: 1297
Final score: 1335
[+] Flag: DUCTF{sample_flag}
./solve_bullethell.py 21.77s user 6.32s system 192% cpu 14.564 total
We have our local flag! Again, our local playing of the game is not giving us the score we expect to see (1337), but it’s close enough and a flag’s a flag.
Now if we replay the locally winning sequence of movements against the challenge server, we should be home and hosed.
I’m having issues getting pwnlib.tubes.ssh.ssh to work with the challenge server. I think pwntools expects the SSH server to give us a real shell, rather than a game. In light of this, I’m sending the movements to the challenge server in a stupid way - but it’s not stupid if it works.
First of all, have our local solver print the winning movements:
def main():
movements_length = 1337
movements = [random.choice(possible_inputs) for _ in range(movements_length)]
pwn.info("Locally discovering winning movements")
for i in itertools.count(1):
score, flag = play_locally(movements)
if flag:
pwn.success(f"Got local flag: {flag}")
pwn.info("Locally winning movements:")
print(movements.decode())
return
if i % 10 == 0:
print(f"{i} rounds played. Latest score: {score}")
movements = movements[:score - random.randint(1, 10)]
movements.extend([random.choice(possible_inputs) for _ in
range(movements_length - len(movements))])
% time ./solve_bullethell.py
[*] Locally discovering winning movements
10 rounds played. Latest score: 103
20 rounds played. Latest score: 231
30 rounds played. Latest score: 284
40 rounds played. Latest score: 532
50 rounds played. Latest score: 585
60 rounds played. Latest score: 584
70 rounds played. Latest score: 608
80 rounds played. Latest score: 610
90 rounds played. Latest score: 825
100 rounds played. Latest score: 1017
110 rounds played. Latest score: 1196
[+] Got local flag: b'DUCTF{sample_flag}'
[*] Locally winning movements:
ajhkkaahhjjjallakjhlkjaahhhjakllkljhlklaalahakkhkaaakkhhhjajajkjllallhlkaajhkajjhahlkhkjllkhhjhhljllhalhjjllhkakjkhlajhjklhakkllaalhllkjjaaljlakjhhhjhjlkkjhkahjkkljaaajjkjljlahaaalkljkaalkkjhkjhjahlkakajkhlajjalaajjhljahlaakjkhhlhklkkjjjahjklakjaajljjaahlhlkhjlkjkhajllhjhlhaalllhaaahjajjjhaljhhjllaklahkhklhklkajlajahjakjlhhlkkahllkhkahhhlaahaakahjajlkhjjajkjaaalkljhhjjhhkhjjjhklhhjaakjljhjhjllakhalhahhhkahlajahjaajjjjakkhhljakhjkalhhllhkakjalakllljahaahjakjhahaakallkhkljhalkljlalkljajaljljakhjkjalljhhaklkkklkhhjllljkllllkaalllajhaaakjkakaakjaljjhljhhlkhlljlllhjlljkhhlhhlhalkjllkjjkkahhjjahjajhjjljahkahljkjjjhhahjkljalhahjjjkjkhlaljjallhlhllaakalhaakljlakhjhhjhlahkhjjklllkallkjajjjlllhkahhhjhhjlaalhlhjhljjakkhhhlhhjllahkhkjhhkjhjlahkjlklalalkjjkljkakjalakllkllhahkljljhhljjjjllkljhkklakkjlkajaajjhajkakkakjklahljkkaahajlhhkkahlkjklkhhahhjkjjlllkhkaaaaahjljkhaljajlajjjklhhlahklaalkhkjljjkhhhaakakahjjjjlhjkahajhhhhkkkhllahhkkajkhlhllkaklhkalaakljhalkhkkljhkkljjllhkkahahaljljjhklkhlhhlakjkalalhlhhhjklaklhlljajhjaahhlajhaallajklaajhajjjhhhakaahlkallkjhjkhhahhklaahajajkljlkjhkjkajlkkkklkhkljkjahklajkllllaaljjhhahlkhkajakaljllllkakajklljljlkjaalljkhjhhjlahjaljlljkhllhajhjjhjkallhallhklkkjaakljhhakaklakjlahaahlhjlkhkakljjakhajlljjkakhhjahakllkjhklahkakljhahhlklkhkjljjaakhaklahkkaklaaljahkhhalallkhhalhajakajahklhlkjjlklljkkhka
./solve_bullethell.py 26.97s user 8.05s system 193% cpu 18.133 total
And shove them down the gullet of the challenge server:
% time (echo; echo 'ajhkkaahhjjjallakjhlkjaahhhjakllkljhlklaalahakkhkaaakkhhhjajajkjllallhlkaajhkajjhahlkhkjllkhhjhhljllhalhjjllhkakjkhlajhjklhakkllaalhllkjjaaljlakjhhhjhjlkkjhkahjkkljaaajjkjljlahaaalkljkaalkkjhkjhjahlkakajkhlajjalaajjhljahlaakjkhhlhklkkjjjahjklakjaajljjaahlhlkhjlkjkhajllhjhlhaalllhaaahjajjjhaljhhjllaklahkhklhklkajlajahjakjlhhlkkahllkhkahhhlaahaakahjajlkhjjajkjaaalkljhhjjhhkhjjjhklhhjaakjljhjhjllakhalhahhhkahlajahjaajjjjakkhhljakhjkalhhllhkakjalakllljahaahjakjhahaakallkhkljhalkljlalkljajaljljakhjkjalljhhaklkkklkhhjllljkllllkaalllajhaaakjkakaakjaljjhljhhlkhlljlllhjlljkhhlhhlhalkjllkjjkkahhjjahjajhjjljahkahljkjjjhhahjkljalhahjjjkjkhlaljjallhlhllaakalhaakljlakhjhhjhlahkhjjklllkallkjajjjlllhkahhhjhhjlaalhlhjhljjakkhhhlhhjllahkhkjhhkjhjlahkjlklalalkjjkljkakjalakllkllhahkljljhhljjjjllkljhkklakkjlkajaajjhajkakkakjklahljkkaahajlhhkkahlkjklkhhahhjkjjlllkhkaaaaahjljkhaljajlajjjklhhlahklaalkhkjljjkhhhaakakahjjjjlhjkahajhhhhkkkhllahhkkajkhlhllkaklhkalaakljhalkhkkljhkkljjllhkkahahaljljjhklkhlhhlakjkalalhlhhhjklaklhlljajhjaahhlajhaallajklaajhajjjhhhakaahlkallkjhjkhhahhklaahajajkljlkjhkjkajlkkkklkhkljkjahklajkllllaaljjhhahlkhkajakaljllllkakajklljljlkjaalljkhjhhjlahjaljlljkhllhajhjjhjkallhallhklkkjaakljhhakaklakjlahaahlhjlkhkakljjakhajlljjkakhhjahakllkjhklahkakljhahhlklkhkjljjaakhaklahkkaklaaljahkhhalallkhhalhajakajahklhlkjjlklljkkhka') \
| sshpass -p ductf ssh ductf@pwn-2021.duc.tf -p 31911 -tt \
| grep -Poa 'DUCTF{.*?}'
DUCTF{i_th1nk_w3're_g0nna_n33d_a_lunatic_d1fficul7y}
Connection to pwn-2021.duc.tf closed.
( echo; echo ; ) 0.00s user 0.00s system 42% cpu 0.002 total
sshpass -p ductf ssh ductf@pwn-2021.duc.tf -p 31911 -tt 0.13s user 0.10s system 12% cpu 1.909 total
grep --color=auto -Poa 'DUCTF{.*?}' 0.02s user 0.04s system 3% cpu 1.909 total
Success!
Our final local solver script is:
#!/usr/bin/env python3
from collections import namedtuple
import itertools
import pwn
import random
import re
from typing import Iterable
re_score = re.compile(b"score: (\\d+)\r")
re_flag = re.compile(b"DUCTF\\{.*?\\}")
PlayResult = namedtuple("PlayResult", ["score", "flag"])
@pwn.context.quietfunc
def play_locally(movements: Iterable[int]) -> PlayResult:
"""
Play a local game according to the given movements. Return the score
"""
movements_iter = iter(movements)
movements_chunk_size = 2048
score = 0
with pwn.process(["bullet_hell"]) as t:
# Start the game
t.sendlineafter(b"Enter a key to start...", b"")
# Send movements until the game ends
try:
while t.connected():
# Send the next chunk of movements
movements_chunk = bytes(itertools.islice(movements_iter,
movements_chunk_size))
t.send(movements_chunk)
# Read some data
data = t.clean()
# Check to see if we just read a score
# If so, update score to be the last-seen score.
# h/t <https://stackoverflow.com/a/2988680>
score_match = None
for score_match in re_score.finditer(data):
pass
if score_match is not None:
score_read = int(score_match.groups()[0])
score = score_read if score_read > score else score
# Check to see if we read a flag
for flag_match in re_flag.finditer(data):
# Winner winner
return PlayResult(score, flag_match.group())
# Put some data back in the tube in case we partially
# read a score or flag
t.unrecv(data[-128:])
except StopIteration:
print("Ran out of movements :(")
# We've either died or run out of movements
return PlayResult(score, None)
possible_movements = list(map(ord, ["h", "j", "k", "l"]))
possible_inputs = possible_movements + [ord("a")]
def main():
movements_length = 1337
movements = [random.choice(possible_inputs) for _ in range(movements_length)]
pwn.info("Locally discovering winning movements")
for i in itertools.count(1):
score, flag = play_locally(movements)
if flag:
pwn.success(f"Got local flag: {flag}")
pwn.info("Locally winning movements:")
print(bytes(movements).decode())
return
if i % 10 == 0:
print(f"{i} rounds played. Latest score: {score}")
movements = movements[:score - random.randint(1, 10)]
movements.extend([random.choice(possible_inputs) for _ in
range(movements_length - len(movements))])
if __name__ == "__main__":
main()
Big thanks to the DUCTF team for an incredible CTF, I’d highly encourage you to put it on the calendar for next year. Thanks also to Joseph, the author of this challenge and many other great challenges. Joseph has published some notes on this challenge which are well worth reading - an intended solution was to have re-implemented the game in a way that makes the bullets visible, and then to play it by hand to deduce a winning sequence of moves. uint0 has published an alternative solution in which the binary is patched and the process is inspected to discover the placement of the bullets, and to plot a path through them. Finally, Joseph’s writeup has a depiction of what the bullets looks like when made visible, shown below. I had assumed that the bullets would be randomly “raining” from the top of the screen, but they’re an absolute mess. It’s a wonder my local script was able to find a safe path through them at all, let alone as quickly as it did!
Source: Joseph