in ,

[DSCTF 2019] CPU Adventure – Unknown CPU Reversing, Hacker News

[DSCTF 2019] CPU Adventure – Unknown CPU Reversing, Hacker News


or: reverse-engineering a custom, unknown CPU from a single program

tl ; dr: We reverse-engineered a program written for a completely custom, unknown CPU architecture, without any documentation for the CPU (no emulator, no ISA reference, nothing) in the span of ten hours. Read on to find out how we did it…

This past weekend, I participated in Dragon Sector’s 2019 Teaser CTF with the CMU PPP team, as a way of de-stressing after a manicCHI)Deadline. Dragon Sector is a well-respected Polish team with a history of interesting CTFs, so I wanted to see what they had in store.

After solving “ummmfpu”, a challenge that involved reversing bytecode for the Micromega uM-FPU floating-point unit, I decided to tackle the CPU Adventure challenge, which at that point had not been solved by any teams (we would eventually be the only team to solve that challenge).

Here’s the description for the CPU Adventure problem:

My grandfather used to design computers back in the 60 s. While cleaning out his attic, I found a strange machine. Next to the machine, I found a deck of punched cards labeled “Dragon Adventure Game”. After some time, I managed to hook it up to modern hardware, but the game is too hard and I cannot get to the end without cheating. Can you help me?

I’m attaching a transcription of the punched cards used by the machine. The machine proudly claims to have 4 general purpose registers, 1kiB of data memory, and 32 kiB of instruction memory.

To play the game, connect to the server as follows:
socat tcp4-connect: cpuadventure.hackable.software: 1234 fd: 0, rawer

Hint: this is a custom CPU, don’t bother googling it.

game.bin

Connecting to the server gives us the following output:

THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.  SELECT AN OPTION:  - GO (N) ORTH - GO (E) AST - (T) ALK TO VALIS - (D) RINK - SHOW (I) NVENTORY  YOUR CHOICE:

Nice. It’s an old-school adventure game. Playing with it for a bit suggests that we can fight enemies and get a flag off this Valis character if we can make him happy:

YOUR CHOICE: T  YOU ENTER THE TAVERN AND APPROACH VALIS.  - HEY, I WAS WONDERING IF YOU COULD HELP ME FIND THE FLAG? - THE FLAG? MAYBE, BUT FIRST, I NEED A REDBULL. - I ... I DON'T HAVE A REDBULL. - WELL THEN, MAKE YOURSELF USEFUL AND FIND ONE.  THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.  SELECT AN OPTION:  - GO (N) ORTH - GO (E) AST - (T) ALK TO VALIS - (D) RINK - SHOW (I) NVENTORY  YOUR CHOICE:

First Steps

I didn’t play with the game for too long, figuring that reversing thegame.binfile was probably more important. I popped it open in a hex editor, expecting binary – imagine my surprise when this is what it looked like:

110011111101000000111100110010001110000011001101000000000000110010011101010000001101001111100001111111001100111000000011 ...

It’sliterallya binary file – a text file containing nothing but ASCII 1s and 0s. We know this is probably machine code for their custom CPU – but besides the fact that it has 4 registers, 1 KiB of data memory and 32 KiB of program memory, we know literallynothingelse about this CPU. So our first big task is to figure out the unit size of this binary file (egis it 8-bit aligned? Or maybe it’s 12 – bit or 18 – bit aligned like someancient architectures?)

To figure out the alignment of an unknown file, I turn to an age-old trick – resizing a text window until the line-wrap length matches the file alignment. This works wonders for things like repeating-XOR ciphertext, unknown (uncompressed) file formats, and code from an unknown CPU:

Resizing a text window

So, from this quick test I figured out that the unit size of this file must divide 20 (the width of the window at alignment). To nail down the exact unit size, I wrote a quick script to look for long repeated strings (figuring that any code would have repeated stereotypical sequences). The longest repeated string was the following 425 – bit block, which appeared at positions 43625 and 44510:

10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100

Since the distance between the repeats was 885, we concluded that the unit size must be 5 bits – ie the unknown CPU must have 5-bit “bytes”. Progress!

We looked for 5-bit punch card encodings, and quickly settled on the historical (Baudot code) encoding. Indeed, when we used an online decoder to decode some snippets, we got readable text!

⇩DRAGON⇩HERE⇧; ⇧⇧⇩SHE⇩APPEARS⇩TO⇩BE⇩GUARDING⇩
SOME⇩KIND⇩OF⇩A⇩BOTTLE⇧; &. &. ⇩␀THERE⇩IS⇩A⇩B

decoding of the 425 – bit code above using LSB Baudot ITA 1

When we tried to decode the whole file using Baudot code, we got gibberish for the first 20, 00 0 bits or so, after which we got completely readable text. This suggested that the first part of the file corresponded to a “code” section, which was followed by a “data” section containing constant strings. We guessed that the machine probably used Baudot code for I / O, which is why it also stored constant strings in memory using Baudot encoding. To make the code segment more readable, I decided to encode it using a base – 32 encoding, similar to hexadecimal encoding but extended to the alphabet 0-9a-v. Here’s what the game.bin file looks like, with the first part base – 32 encoded and the second half Baudot decoded (full file here:game.b 32):

PV  (PI) ****************************************************************************** pk 00 p7a0qfgvpjg3f0kf 13 f 28 p5f3pv  (pk) *********************************************************************************** (PN)  f0sf1sf 24 p5f3r9c 11 qad0f0sf1 DF 26 P5F  (C) ******************************************************************************************* (qad0f)  F1ff 26 P5F 39 C 41 qad0f  (f1df)  P5F  (c)  qad0f0hf1ef 26 p5f3r1c  (Qaq) *********************************************************************************************** (C) ******************************************************************************************** (QCL0F)  f1of 27 p5f3p3g3psf  (C)  qal0f 02 F1NF 27 p5f3p3g3psf3rf0hf1nf 27 p5f3f 05 f 16 f 27 p5f3rf  (f) ************************************** (FL0F)  f  (QA) *********************************************************************************** b) ***************************************** (QA) *********************************************************************************** (B) ********************************************************* (f)  f 95 k9m0k9m0k9m  (QA) *********************************************************************************** (b) ****************************************** (QA) *********************************************************************************** (b)  Ruougf 10 f 20 g0i9g0i  (b)  u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1on0ooff  odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df 24 p5f3r9c  (QA)  [...] 93 E9N 59 ka8fo 87 r 85 g8ui8ml8ed 87 B9H 89 u  (U)  abcdb

Brave Browser
Read More

What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *

GIPHY App Key not set. Please check settings

Ellie's Brutal The Last of Us Part II Revenge Story Lands Next February, Crypto Coins News

Ellie's Brutal The Last of Us Part II Revenge Story Lands Next February, Crypto Coins News

Trump impeachment: Pelosi launches formal inquiry into Ukraine claims – BBC News, Bbc.com

Trump impeachment: Pelosi launches formal inquiry into Ukraine claims – BBC News, Bbc.com