Yesterday, I went to an event hosted by BAE Systems: Capture the Flag. The basic idea behind any Capture the Flag (CTF) game is to score points based on challenges completed (i.e. flags captured). The challenges can be anything from cryptanalysis to website vulnerability exploits, and they're scored based on difficulty. In this competition, there were also hints we could unlock -- but they reduced the number of points you could get for completing the challenge.

In the end, our team placed 5th - not a bad result for our first ever CTF as a bunch of first-years!

One of the challenges I was happiest to complete was called Matryoshka -- I didn't realise at the time, but Matryoshka is the name for nested Russian dolls, which is exactly what I'd have to deal with. It started out innocuously enough, with a file download (rehosted here) paired with a single instruction: "Get to the key. This might be much easier on Linux!".

I downloaded it into a new folder on my Ubuntu partition using wget, and used the *nix file command to get a best-guess at the real file format (since ".bin" is pretty ambiguous at the best of times). The output wasn't too worrying: "Zip archive data, at least v2.0 to extract". I slapped a ".zip" extension on it and ran unzip.

Another file appeared, this time just called "out". I ran file on it again; this time it was "gzip compressed data, from Unix". Just like last time, I renamed it and unzipped, this time using tar.

To cut a long story short, this kept going. For so long I thought I'd genuinely never finish. After the gzip, there was bz2, then 7zip, and then something a little different: "Linux rev 1.0 ext2 filesystem data". For that, I googled around a bit, and eventually found the command mount -o loop ./out.rev_filesystem /mnt. I headed to /mnt, and found a "lost+found" folder along with a single out file... clearly I wasn't done yet.

Turns out, this next "out" file was a cpio archive. Inside that was a Microsoft ".cab", and inside the cabinet file was an ARJ archive. Although the cpio archive was pretty obscure, the ARJ file was the first format I'd never heard of even once! And I wasn't the only one: my trusty dtrx didn't know how to handle it either. With a quick google, I figured out I'd have to install a program called arj and use the command arj e out.arj to extract the next file along.

This was where it started to get interesting: the next file showed up as "ASCII Text". I was convinced I'd reached the end: that I'd found the key file. Holding my breath, I opened it with less out...

... only to discover something that looked like this:

Didn't look very much like a key - or at least not a particularly human-readable one!

Luckily, it wasn't too long till I figured out what was going on: this was the result of taking a binary file - presumably some kind of archive - and Base64-encoding it. To get the original file back, I ran base64 --decode out.txt > out.

This next file also stumped dtrx, despite being an archive format; file's output read "Zoo archive data, v2.10". I found the zoo program in the Ubuntu repositories, and luckily it had pretty much the same syntax as most other archivers: zoo e out.zoo did the trick, and spat out what file told me was "MS Compress archive data".

This one was a bit trickier. Silly as it might seem, I couldn't find the actual file extension used for MS Compress archives, so for the first time, after checking absolutely every other option, I had to resort to using Windows. Luckily, it was short-lived: as soon as I downloaded and used a free tool called msexpand, I got an ISO image: quick enough that I could double-click to mount it, then copy its contents over onto my USB stick to continue working on Linux.

Note: I later found that mscompress (which includes the msexpand utility) is in the Ubuntu repositories. I don't know how I missed it.

The contents were pretty strange: 383 files, all called KEY_XXX, where XXX were contiguous integers from 0 to 382. Curious to see where this would go, I ran file on KEY_000. The output was surprising: I'd expected a RAR archive (since I've seen that kind of file-fragmentation with ".r00" files before), but what I got was "JPEG image data, JFIF standard 1.01". Interested, I tried to open it with my standard image viewer, but just got a message telling me that "This file cannot be displayed". My next thought was to try concatenating all the files: I ran "cat KEY_* > out.jpg", and opened the resulting image.

Funnily enough, that was the end of the challenge! I was expecting a cunningly-hidden zip file inside the image's padding bytes, or maybe a final kick-in-the-teeth steganography puzzle -- maybe even a URL to download the next multi-nested archive -- but there in front of me was the key, on a backdrop of the original Matryoshka dolls.

In any case, it was one of the most fun puzzles I've ever solved! In another post, I might describe my other favourite puzzle: an SQL injection on a faux bank's website.