# Notifico

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

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