This is a writeup for how we solved the notifico 35c3 CTF challenge.

The task:

We are presented with a tar file which contains another tar file, an executable named check, and the python script check.py.
The tar file contains 225 folders, each of which contains one regular file and between 42 and 56 links to similar files in other folders.

The script check.py (python3) runs the check executable on the folder, checks that its result is 15, concatenates “magic” from the alphabetically ordered regular file’s modes (file_mode & 00777), takes the sha256 of the magic as a key and decrypts the encrypted flag with the digest. If the result contains the standard flag prefix (35C3) and the flag is made of alphanumeric characters it prints the flag.

The check executable performs 4 actions:
• runs on the folders, and creates inotify watch with mask 9 (IN_ACCESS | IN_CLOSE_WRITE) on all the regular files. Note that IN_ACCESS means that “File was accessed (e.g., read(2), execve(2)).”. During creating watchers it checks the mode of each regular file. If its write permission ^ execute permission for the owner is not 0 or if it has any of rwx permissions for other users the executable returns 255.
• Opens and closes all the regular files (which should cause IN_CLOSE_WRITE notification)
• Tries to execute all the symbolic links (which should cause IN_ACCESS notification if the file is executable)
• Reads and analyses the inotify watch results. If something was executed, it returns 255, otherwise it returns the number of close notifications received.

Initial analysis:

If we want to have something decrypted, we should find such a set of 15 folders, and links in which are not pointing to files in this set, set on files inside these folders +wx permission, and run check.py in order to check results.
In this stage it is still unclear how many combinations of this kind exist. The order in the combination doesn’t matter.
It seems like we should check results of all these sets for decryptability.

As per hint (we’ll not need it), the graph received here resembles the problem of enumeration of 15 Queens on 15×15 chess board, where the folders are places on the board [a-f][1-15].
I wasn’t able to map all the folders to exact places on the board (only the center one and main diagonals), but we don’t really need it.

We’ll bruteforce it.

The bruteforce:

During any bruteforce we usually have 3 main problems:
• performance
• performance
• and once again performance.

As far as I remember what I read somewhere, the number of unique solutions for this problem on N sized board has its own sequence name (A000170, Number of ways of placing n nonattacking queens on an n X n board
(Formerly M1958 N0775)) and can be found here: https://oeis.org/A000170
For the board 15×15 it is 365596, which is not too much, the problem is finding these solutions in reasonable time and avoiding duplicates.
I have a good workstation at home, and I can afford parallel bruteforcing, so let’s do it.

1 – Let’s construct some kind of representation of the graph.

Inside the chall folder let’s run the following shell commands:

# unpack the folder
tar -xf *.tar.gz			 
cd chall
# get list of folders into folders.txt
ls -l | cut -d" " -f 9 > ../folders.txt
cd ..
# create a listing of the folder in corresponding .fld file
for i in `cat folders.txt`; do ls -l ./chall/$i > $i.fld ; done

Now we have all the links.

2 – Let’s get the alphabetically ordered folders exactly as they are in the script

We just remove from the check script execution of the check executable, and add a print of the file name in the loop that creates the “magic”.

Here is what we got after some small editor massaging:

ind2fold = {
	0 : "APFLtDMGfSvLChWH",
	1 : "ASzhPMFMNmpBMEOm",
	2 : "AYenxPNbHIIxFaBs",
	3 : "AkpRSKtliwhtjBLO",
	4 : "AlUQWFAVMYyANtGl",
	5 : "BpFkWrUBXvwAVywH",
	6 : "BsPQryqrPSPUniAt",

	...
	...
	...

	218 : "zIzNJPYLPMyBuaWj",
	219 : "zNkvKHFVpILKhGee",
	220 : "zQiyomzHVpITGMFx",
	221 : "zUfpdFqENVnMqMbh",
	222 : "zWvRJALKMjTnoaxf",
	223 : "zoPhogrElBntiQUN",
	224 : "zsEGaUEJXslKOiZP",
}

fold2ind = {}

for i in ind2fold:
	fold2ind[ind2fold[i]] = i

3 – Let’s read the folder structure for building some graph representation:

Let’s read all the “.fld” files created earlier and analyze them as follows:

xrefto = {}
xreffrom = {}

folders_found = []
folders_dict = {}

# we get all the fld files via command line

for n in sys.argv[1:]:
	f = open(n, "r")
	res = []
	current_folder = n.replace(".fld", "")
	folders_found.append(current_folder)
	folders_dict[current_folder] = True
	for l in f:
		if l.find("-> ../") != -1: #analyzing a link
			splitted = l.split()
			res.append( splitted[-1].split('/')[1]) # getting a folder to which it points
	xrefto[current_folder] = sorted(res)
	# creating an opposite direction
	for r in sorted(res):
		if not r in xreffrom:
			xreffrom[r] = [current_folder]
		else:
			xreffrom[r].append(current_folder)
	f.close()

In this piece of code we have 2 dictionaries that represent where exactly the links point to (xrefto) and are pointed from (xreffrom).

4 – Let’s add some multiprocessing and start to avoid duplicates:

Since the order inside the combination doesn’t matter, we can conclude the following:
• We should define some order inside the combination. Alphabetical order is OK, we’ll call all combinations ordered in another way unordered which we’ll skip.
• This gives us a possibility to multi-process: during the brute-force we can start from different folders (i.e. cells of the board) and exclude what we don’t need.

This gives us the following bruteforce run:

import multiprocess
...
...
...

processes = []

folders_found = sorted(folders_found)

for i in range(len(folders_found) - 15):
	res_stack = []
	processes.append(multiprocessing.Process(target = bruteforce, args = (folders_dict.copy(), xreffrom, xrefto, 0, res_stack[:], True)))
	folders_dict.pop(folders_found[i], None) 
# note that we running on the different set each time, and removing 1 starting folder 

# per bruteforcing instance
for p in processes:
	p.start()

5 – Let’s write bruteforcing itself

# sorry, the code is ugly

def bruteforce(current_set, # places on the board left
	xrf, # xrefs from and to the places of the board collected earlier
	xrt,
	level, # current recursion level
	variant, # current variant 
	only_first): # dirty hack: see the usage

	variant = variant[:]
	current_set = current_set.copy() # copy the current set, we'll have to change it
	if level == 15:
		check(sorted(variant)) 
		# if we arrived to recursion level 15 then we have a variant, let's check it
		return False

	for f in sorted(current_set.keys()):
		# iterating the current set of places left unbeaten in alphabetical order
		new_set = current_set.copy()
		new_set.pop(f, None) # exclude current cell from the set

		# exclude fields beaten by the current cell 
		for x in xrt[f]:
			new_set.pop(x, None)

		# exclude fields that doesn't fit to alphabetical sequence

		test_set = new_set.copy()
		for t in test_set:
			if t < f:
				new_set.pop(t, None)

		if (len(new_set.keys()) + level) < 15:
			# get out if there is no enough places
			return False

		variant.append(f)
		# go down with the recursion
		bruteforce(new_set, xrf, xrt, level + 1, variant, False)
		variant.remove(f)
		if only_first:
			# on the first level we want to check only one variant
			# all others will be checked in other instances
			print("Bruteforce started from", f, " finished")
			return False
	return False

6 – Let’s copy out the checking from the check.py and fix it

#!/usr/bin/env python3
from sys import argv
import re
from hashlib import sha256
from Crypto.Cipher import AES

def check (variant):
	res = ""
	enc_flag = b'\x99|8\x80oh\xf57\xd4\x81\xa5\x12\x92\xde\xf5y\xbc\xc0y\rG\xa8#l\xb6\xa1/\xfeE\xc5\x7f\x85\x9a\x82\x0b\x02Y{\xd9/\x92X>p\\\xb7H\xb1{\xcf\x8b/r=\x87-#\xae\x95\xb6\xd1\r\x03\x13'
	flag_fmt = r"35C3_[\w]*"

	global ind2fold
	global fold2ind
	cnt = 0
	# creating the magic
	for i in range(len(ind2fold.keys())):
		if ind2fold[i] in variant:
			cnt += 1
			res += "700"
		else:
			res += "400"

	# checking for obvious mistakes,
	# we should have 15 queens and 225 cells at all

	if cnt != 15 or len(res) != 225*3:
		print ("Error!Error!Error!Error!Error!Error!Error!Error!Error!Error!Error!")
		exit(1)

	magic = res
	try:
		flag = AES.new(sha256(magic.encode()).digest(), AES.MODE_ECB).decrypt(enc_flag)
		if flag.decode().find("35C3_") != -1:
			hexdump.hexdump(flag)
		if re.fullmatch(flag_fmt, flag.decode()) is not None:
			print("Looks good, here is your output: {}".format(flag))
			# exit(0)
			# we remove the original exit because we want to know how 
# much time the full bruteforce takes
	except Exception:
		pass

	return res

7 – Let’s run it.

Actually running it with python3 may be a bit slower then we need. Let’s run it with pypy3:

pypy3.5-6.0.0-linux_x86_64-portable/bin/pypy3 multi_dict.py *.fld

It yields the flag b’35C3_congr4ts_th0se_were_s0m3_truly_w3ll_pl4c3d_perm1ssions_Sir_’

It takes some hours on my home workstation, but if we did everything right, it should fit.

Timing of the bruteforce

In order to get the flag I left this executing before going to sleep.
However I was curious about how much time exactly should it take, so I added some prints and run it again.
It appears that getting a flag takes about an hour, and full bruteforce takes about 2 hours on my computer (Ubuntu 18.0.1, i7 CoffeLake, 64G RAM)

See the output of the script below:

╰─$ ../pypy3/pypy3.5-6.0.0-linux_x86_64-portable/bin/pypy3 ./multi_dict.py *.fld
Starting
2018-12-31 21:19:26.262807
Length is 225
Bruteforce started from mEXeTszvrPQxLSIM finished
.
< - cut - >
.
Bruteforce started from FacVEEUFvQtVfjcj finished
Bruteforce started from ISOYfrwvVOMZveHE finished
Ending
2018-12-31 22:21:36.675702
400400400400400400400400400400700400400400400400400400400400400400400400400400400400700400400400400400400700400400400400400400400400400400700700400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400700400700400400400400400400400400400400400400400400400400400400400400400700400400400700400400400400400400400400400400400400400400400400700400400700400400400400700400400400400400400400400700400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400400700400700400400400400400400
00000000: 33 35 43 33 5F 63 6F 6E 67 72 34 74 73 5F 74 68 35C3_congr4ts_th
00000010: 30 73 65 5F 77 65 72 65 5F 73 30 6D 33 5F 74 72 0se_were_s0m3_tr
00000020: 75 6C 79 5F 77 33 6C 6C 5F 70 6C 34 63 33 64 5F uly_w3ll_pl4c3d_
00000030: 70 65 72 6D 31 73 73 69 6F 6E 73 5F 53 69 72 5F perm1ssions_Sir_
Looks good, here is your output: b'35C3_congr4ts_th0se_were_s0m3_truly_w3ll_pl4c3d_perm1ssions_Sir_'
Bruteforce started from FsiBPvyjOwaioLBP finished
Bruteforce started from ExCZSjfztnUcXCqh finished
Bruteforce started from GmSNArrbwMYaJsND finished
Bruteforce started from FLsGyEZReOEFwvqm finished
Bruteforce started from EQsvyIRczZVqeYkD finished
Bruteforce started from DvixmyIxrLeiXeZv finished
Bruteforce started from DqOgFKUtvPDxcDhA finished
Bruteforce started from FbLGtlhVWXDzMEEv finished
Bruteforce started from CIMHMvnbzSHPSZzw finished
Bruteforce started from DTGRkOyLvIRXOcFA finished
Bruteforce started from DvEdLxkYtbjDeMmI finished
Bruteforce started from DQiHxMFfQxEjRzak finished
Bruteforce started from BuuhlRIKIUKQixNn finished
Bruteforce started from DBdOhoYdrCrzteVm finished
Bruteforce started from AlUQWFAVMYyANtGl finished
Bruteforce started from DRlKwGefVbUJbweg finished
Bruteforce started from BsPQryqrPSPUniAt finished
Bruteforce started from BxztQECAmlZiVgLd finished
Bruteforce started from AkpRSKtliwhtjBLO finished
Bruteforce started from BpFkWrUBXvwAVywH finished
Bruteforce started from ASzhPMFMNmpBMEOm finished
Bruteforce started from AYenxPNbHIIxFaBs finished
Bruteforce started from APFLtDMGfSvLChWH finished
╭─[cenzored]@[cenzored] ~/ctfs/notifico
╰─$ date
Mon Dec 31 23:01:46 IST 2018