T-dc-ron
September 17, 2023
• by cavefxa
• 6 min read
Challenge Description
I have a snake in my bootsector!
Solution
We will first reverse engineer the bootsector file, and recover symbols. We can get something like:
; Decrypt the flag using and xor mod flag len
mov si, flag_contents
mov di, [points]
and di, 15
add si, di
mov byte ch, [si]
mov byte dh, [pellet_x]
xor ch, dh
mov byte [si], ch
; Increment the points
inc byte [points]
The flag seems to be 15 characters long. It is encrypted using the x coordinate for the “cheese” that the snake needs to eat, to gain points.
We would like to understand how the pellets are generated, if possible we want to re-implement the algorithm in Python. We can continue reversing the binary to find out where the pellets are generated:
get_pellet:
inc byte [pellets]
call random
mov cx, [rand_value]
and cx, 255
mov word [pellet_x], cx
call random
mov dx, [rand_value]
and dx, 63
mov word [pellet_y], dx
mov al, 0x05
mov ah, 0x0C
mov bh, 0x00
int 0x10
ret
Here we see a byte is incremented at the [pellets] location, then there’s a call to random, which is anded with 0xff. Later this is moved into the pellet’s x-coordinate. The y-coordinate is also generated by random, but is anded with the value 0x3f.
Is there a random number generator in the bootsector? We can analyze this function:
random:
mov ax, 75
mov bx, [rand_value]
mul bx
add ax, 74
and ax, 0xffff
inc ax
mov [rand_value], ax
ret
Ah, a simple linear congruential generator of the form:
k_n = ((75 * k_{n-1} + 74) & 0xffff) + 1.
Simplifying we get: k_n = 75 * k_{n-1} + 75. If we don’t exceed 0xffff, this should be fine.
We can make a python script to recover the flag based on this deterministic RNG:
r = 1
def rng():
global r
r = r * 75 + 75
return r
flag = bytearray(bytes([
48, 4, 132, 153, 159, 113, 117, 31, 51, 112, 240, 31, 38, 149, 142, 225
]))
at = 0
_next = 1
while at < 0x1a4:
if at != _next:
at += 1
x = rng() & 0xff; rng()
else:
flag[_next & 0xf] ^= x
_next += 1
print("TDCNET{" + flag.decode() + "}")
And we get the flag: TDCNET{pRnG_15_s00_fUN!}
Source code
; Referencee used for system calls: http://www.ctyme.com/intr/rb-1754.htm
[bits 16] ; Tells the assembler that its a 16 bit code
[org 0x7c00] ; Constant, tells the assembler where the code
; is located in memory
; This is a constant for the boot sectors location
_start:
; Set graphics mode. Clears screen
mov ah, 0x00
mov al, 0x13
int 0x10
; Get the first pellet and then begin the game
call get_pellet
call game_loop
jmp $
game_loop:
; Get keyboard input WASD
call get_key
; Compare pellets to 420
mov byte cx, [pellets]
mov byte dx, [points]
cmp cx, 420
je win
; Compare pellets and points
cmp cx, dx
; If they are equal, there's a pellet
je print_map
; Otherwise get a new pellet
call get_pellet
; Move the player
print_map:
mov al, 0x09 ; Color of the player
call move_player
jmp game_loop
print_pixel:
mov ah, 0x0C
mov bh, 0x00
mov cx, [curr_x]
mov dx, [curr_y]
int 0x10
ret
get_pellet:
inc byte [pellets]
call random
mov cx, [rand_value]
and cx, 255
mov word [pellet_x], cx
call random
mov dx, [rand_value]
and dx, 63
mov word [pellet_y], dx
mov al, 0x05
mov ah, 0x0C
mov bh, 0x00
int 0x10
ret
random:
mov ax, 75
mov bx, [rand_value]
mul bx
add ax, 74
and ax, 0xffff
inc ax
mov [rand_value], ax
ret
check_pixel:
mov ah, 0x0d
mov bh, 0x00
mov cx, [curr_x]
mov dx, [curr_y]
int 0x10
cmp al, 0x09
je lose
ret
move_player:
; Print the player at the current x and y
call print_pixel
; Compare to max y (Is the player hitting the map border)
mov word si, [max_y]
cmp si, [curr_y]
je lose
; Compare to max x (Is the player hitting the map border)
mov word si, [max_x]
cmp si, [curr_x]
je lose
; Compare to min y (Is the player hitting the map border)
xor si, si
cmp si, [curr_y]
je lose
; Compare to min x (Is the player hitting the map border)
cmp si, [curr_x]
je lose
; Compare player pos to pellet, should probably read pixel
mov word si, [pellet_y]
cmp si, [curr_y]
jne single_ret
mov word si, [pellet_x]
cmp si, [curr_x]
jne single_ret
; Decrypt the flag using and xor mod flag len
mov si, flag_contents
mov di, [points]
and di, 15
add si, di
mov byte ch, [si]
mov byte dh, [pellet_x]
xor ch, dh
mov byte [si], ch
; Increment the points
inc byte [points]
ret
; There's definitely a smarter way of doing this
single_ret:
ret
; Move up, check for collision before changing the direction
move_up:
dec dword [curr_y]
call check_pixel
mov byte [curr_direction], 0x00
jmp move_player
move_down:
inc dword [curr_y]
call check_pixel
mov byte [curr_direction], 0x01
jmp move_player
move_left:
dec dword [curr_x]
call check_pixel
mov byte [curr_direction], 0x02
jmp move_player
move_right:
inc dword [curr_x]
call check_pixel
mov byte [curr_direction], 0x03
jmp move_player
; Moves the player in the current direction
move_current:
mov si, curr_direction
mov al, [si]
cmp al, 0x00
je move_up
cmp al, 0x01
je move_down
cmp al, 0x02
je move_left
cmp al, 0x03
je move_right
; Get keyboard input using bios syscall
get_key:
call sleep_some
; Check if there's a new keypress
mov ah, 0x01
int 0x16
; No new keypress, move current direction
jz move_current
; Otherwise we will get the new keypress
xor ah, ah
int 0x16
cmp al, 'w'
je move_up
cmp al, 's'
je move_down
cmp al, 'a'
je move_left
cmp al, 'd'
je move_right
jmp lose
; Just a simple sleep so that drawing is not instant, uses
; [CX:DX] for the sleep. Currently using only dx.
sleep_some:
mov ah, 0x86
mov cx, 0x00
mov dx, 0xF246
int 0x15
ret
; For printing to screen
teletype:
mov ah, 0x0e
int 0x10
; Print string at address in SI
print_str:
lodsb ; Load the byte at si into AL
or al, al ; Check for null
jz exit
call teletype
; Just print lose forever
lose:
mov si, lose_str
jmp print_str
jmp lose
; Print win forever
win:
mov si, flag
jmp print_str
jmp win
exit:
jmp exit
data:
curr_y:
dw 100
curr_x:
dw 160
max_x:
dw 320
max_y:
dw 200
curr_direction:
db 0x0
rand_value:
dw 0x01
pellets:
dw 0x00
pellet_x:
dw 0x00
pellet_y:
dw 0x00
points:
dw 0x01
win_str:
db "You win!", 0
lose_str:
db "You lose!", 0
flag:
db "TDCNET{"
; The encrypted flag
flag_contents:
db '0', 0x04, 0x84, 0x99, 0x9f, 'q', 'u', 0x1f, '3', 'p', 0xf0, 0x1f, '&', 0x95, 0x8e, 0xe1
flag_end:
db "}", 0
; To ensure that the length is 512 bytes (510 excluding the magic)
times 510 - ($ - $$) db 0
dw 0xaa55
And a Makefile for easier development:
CXX := nasm
CXXFLAGS := -f bin -o game.bin
default:
$(CXX) $(CXXFLAGS) game.asm
clean:
rm -f game.bin
.PHONY:
clean