Tags: chess symlink tar 

Rating: 5.0

**Description**

> veni, vidi, notifici
>
> Notes: - only chmod, no touch - no root user, please - tar --no-same-owner -xhzf chall.tar.gz
>
> [Challenge files](https://archive.aachen.ccc.de/35c3ctf.ccc.ac/uploads/notifico-b568d7b9b60a42e7e06471e2f9cb0883.tar.gz)
>
> **HINT**: The graph is a move graph for a certain type of chess piece.

**Files provided**

- [notifico.tar.gz](https://archive.aachen.ccc.de/35c3ctf.ccc.ac/uploads/notifico-b568d7b9b60a42e7e06471e2f9cb0883.tar.gz)

**Solution**

In the `tar` archive, we see three files:

- `chall.tar` - another archive containing 225 directories with some 40-50 files each, although all but one in each directory are symlinks
- `check.py` - flag decryption script invoking `check` in the process
- `check` - ELF executable to verify a given directory

The first step was to look into `check.py`. The important bit was:

```python
VAL = 15

# ...

res = subprocess.call(["./check", basedir])

if res == 255 or res != VAL:
print("This looks no good...")
exit(-1)
else:
print("A worthy try, let's see if it yields something readable...")
```

So whatever directory we give it as our "solution", it will invoke the `check` executable on it. `check` in turn must return `VAL`, i.e. `15` for the solution to be considered valid. The SHA-256 hash of the UNIX permissions of the files in our solution directory is then used to decrypt a flag encrypted using AES. Given that there are `225` "regular" files and hundreds of symlinks in the `chall.tar` archive which forms the template for our solution, brute-force is infeasible.

The hint given in the challenge description spoils what `chall.tar` is completely, so much so that I am surprised this challenge didn't have many more solutions after the hint was released. We can gain a similar understanding of `chall.tar` from how the `check` executable works and the general structure of the archive.

Using IDA Pro we can find that `check` does roughly the following:

- sets up `inotify` watchers on all regular (non-symlink) files in each of the `225` directories
- try to `fopen` each of the `225` regular files in read/write mode, then `fclose`
- set `result` to `0`
- handle all triggered `inotify` events:
- increment `result` by `1`
- for each `IN_CLOSE_WRITE` event (i.e. file closed after write access), try to `execve` all the symlinks in the just-closed file's directory
- exit with exit code `result`

Note that `execve` will only succeed when the file referenced by the symlink can be executed; if `execve` succeeds, the program will crash, because there are no valid executables in the `chall.tar` directory (each regular file is only 1 byte long).

In other words, `check` counts the regular files it can open whose "neighbours" (i.e. files referenced by the symlink it that file's directory) are not executable.

One more extremely important hint: the number of directories in `chall.tar` is `225`, which is `15 * 15`, a perfect square. `VAL` is also `15`.

We can also count how many files there are in each of the `225` directories. If we simply extract the archive and go through the directories in alphabetical order, the result is rather chaotic. However, the directories are contained in `chall.tar` in a particular order. We can see this with:

```bash
$ tar -tvf chall.tar
drwxr-xr-x 0 notifico notifico 0 Dec 22 14:06 chall/
drwxr-xr-x 0 notifico notifico 0 Dec 22 14:06 chall/NrTOYjZgBjJHfNLu/
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/NrTOYjZgBjJHfNLu/clxAKWStzqRKyxql -> ../eAvSLhONEWpXqnwu/JHFulfjgaQGnmOPx
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/NrTOYjZgBjJHfNLu/OfTFUEFIyGMZMoan -> ../HdWkyeWugdUHdzuU/rUXgDUpTytwSoWon
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/NrTOYjZgBjJHfNLu/drwKLoWvVcjNdMiX -> ../zoPhogrElBntiQUN/ThQhbYJgbiSZbykb
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/NrTOYjZgBjJHfNLu/zvXOjUgOepbQeCoe -> ../ISOYfrwvVOMZveHE/jroOyZVjiUCJCHgf
...
...
...
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/fXWIMMRZvMSweIId/GIlMJUgUbXbYmdSE -> ../pNuhEkCjuZfTZWvi/JFhCuAbdlsMRpcNo
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/fXWIMMRZvMSweIId/KdDQXPXYBqQARKQc -> ../QdyTwLeNTUDvXTFI/DJLuDDWviVrYegVM
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/fXWIMMRZvMSweIId/MCOiuhLUCuCoPZvn -> ../vruPGIPvYbkWqNzX/MHinNnRcKtLLeEXV
lrwxrwxrwx 0 notifico notifico 0 Dec 22 14:06 chall/fXWIMMRZvMSweIId/ufIYqBqbfCgGIspR -> ../vqPxvKvBQGHntyiv/aYPWRwJUyOyHRILd
-r-------- 0 notifico notifico 1 Dec 22 14:06 chall/fXWIMMRZvMSweIId/KYtdUumqvnfClEMF
```

If we count the symlinks in the directories in this order and arrange them in a `15 * 15` square, we get a very neat result:

42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42
42, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 42
42, 44, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 44, 42
42, 44, 46, 48, 48, 48, 48, 48, 48, 48, 48, 48, 46, 44, 42
42, 44, 46, 48, 50, 50, 50, 50, 50, 50, 50, 48, 46, 44, 42
42, 44, 46, 48, 50, 52, 52, 52, 52, 52, 50, 48, 46, 44, 42
42, 44, 46, 48, 50, 52, 54, 54, 54, 52, 50, 48, 46, 44, 42
42, 44, 46, 48, 50, 52, 54, 56, 54, 52, 50, 48, 46, 44, 42
42, 44, 46, 48, 50, 52, 54, 54, 54, 52, 50, 48, 46, 44, 42
42, 44, 46, 48, 50, 52, 52, 52, 52, 52, 50, 48, 46, 44, 42
42, 44, 46, 48, 50, 50, 50, 50, 50, 50, 50, 48, 46, 44, 42
42, 44, 46, 48, 48, 48, 48, 48, 48, 48, 48, 48, 46, 44, 42
42, 44, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 44, 42
42, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 42
42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42

It is symmetric and there are more symlinks in the "central" directories.

Maybe you can see where all of this (+ the explicit hint) is leading to. Chess! More specifically, a chess puzzle, the [N queens problem](https://en.wikipedia.org/wiki/Eight_queens_puzzle). The famous eight queens puzzle is a chess puzzle where the goal is to arrange `8` queens on a regular (`8 * 8`) chessboard without any of them being able to see one another (queens can move and see horizontally, vertically, and diagonally). In this case we have a `15` queens puzzle.

Consider for example the top-left directory in the table above. It has `42` symlinks:

Q, X, X, X, X, X, X, X, X, X, X, X, X, X, X
X, X, ., ., ., ., ., ., ., ., ., ., ., ., .
X, ., X, ., ., ., ., ., ., ., ., ., ., ., .
X, ., ., X, ., ., ., ., ., ., ., ., ., ., .
X, ., ., ., X, ., ., ., ., ., ., ., ., ., .
X, ., ., ., ., X, ., ., ., ., ., ., ., ., .
X, ., ., ., ., ., X, ., ., ., ., ., ., ., .
X, ., ., ., ., ., ., X, ., ., ., ., ., ., .
X, ., ., ., ., ., ., ., X, ., ., ., ., ., .
X, ., ., ., ., ., ., ., ., X, ., ., ., ., .
X, ., ., ., ., ., ., ., ., ., X, ., ., ., .
X, ., ., ., ., ., ., ., ., ., ., X, ., ., .
X, ., ., ., ., ., ., ., ., ., ., ., X, ., .
X, ., ., ., ., ., ., ., ., ., ., ., ., X, .
X, ., ., ., ., ., ., ., ., ., ., ., ., ., X

Count the squares that the queen (`Q`) can see (`X`) and there are 42 of them. In fact, each of those `X`'s in the actual `chall.tar` is a symlink to that particular directory.

Unfortunately, there are thousands of solutions to the 15 queens problem. Fortunately, we can generate them systematically with a script and hence decrypt the flag. Once again, we can adapt a program from [Rosetta Code](http://rosettacode.org/wiki/N-queens_problem).

[Adapted C program here](https://github.com/EmpireCTF/empirectf/blob/master/writeups/2018-12-27-35C3-CTF/scripts/queens.c)

We let this C program generate all the solutions to the problem and have a Python script change each solution to a list of UNIX permissions in the order the original `check.py` script used (it sorted the directories alphabetically), SHA-256 hash it, and try to decrypt the flag.

[Python decoder here](https://github.com/EmpireCTF/empirectf/blob/master/writeups/2018-12-27-35C3-CTF/scripts/queens.py)

(As per the challenge description, each "queen" would be marked by a regular file with `700` permissions, each non-queen would remain at `400` permissions, as provided in the `chall.tar` template.)

`35C3_congr4ts_th0se_were_s0m3_truly_w3ll_pl4c3d_perm1ssions_Sir_`

x0r19x91 – Jan. 16, 2019, 2:17 p.m.

Nice !