Catisfiability

Catisfiability

back to puzzle

When you log into this server, you find an interactive restricted shell with the locale set to Catalan.

Your user tse has limited ability to do anything, but needs to somehow look at the contents of flag/flag.txt, which is owned by user macavity.

You can run ls and cat, which should help you look around a little bit; you’ll see

bin cat-flag flag gats and wrapper.c

where bin contains cat, ls, script, and wrapper, while cat-flag is just the command cat flag/flag.txt. The gats directory contains files with various T. S. Eliot cat names, each with a different size.

-rw-r--r-- 1 tse tse 408882 Oct  5  1939 bombalurina
-rw-r--r-- 1 tse tse  68123 Oct  5  1939 carbucketty
-rw-r--r-- 1 tse tse  31147 Oct  5  1939 cassandra
-rw-r--r-- 1 tse tse  12913 Oct  5  1939 coricopat
-rw-r--r-- 1 tse tse  58019 Oct  5  1939 deuteronomy
-rw-r--r-- 1 tse tse 198120 Oct  5  1939 griddlebone
-rw-r--r-- 1 tse tse 912014 Oct  5  1939 grizzabella
-rw-r--r-- 1 tse tse  81291 Oct  5  1939 growltiger
-rw-r--r-- 1 tse tse 284011 Oct  5  1939 jellylorum
-rw-r--r-- 1 tse tse 123819 Oct  5  1939 jemima
-rw-r--r-- 1 tse tse 221810 Oct  5  1939 jennyanydots
-rw-r--r-- 1 tse tse 902124 Oct  5  1939 mistoffeles
-rw-r--r-- 1 tse tse   4891 Oct  5  1939 mongojerrie
-rw-r--r-- 1 tse tse   1892 Oct  5  1939 munkustrap
-rw-r--r-- 1 tse tse 178123 Oct  5  1939 pouncival
-rw-r--r-- 1 tse tse 319873 Oct  5  1939 quaxo
-rw-r--r-- 1 tse tse 172831 Oct  5  1939 rumpleteazer
-rw-r--r-- 1 tse tse   4839 Oct  5  1939 rumtumtugger
-rw-r--r-- 1 tse tse  80012 Oct  5  1939 sillabub
-rw-r--r-- 1 tse tse  73183 Oct  5  1939 skimbleshanks
-rw-r--r-- 1 tse tse   1921 Oct  5  1939 tantomile
-rw-r--r-- 1 tse tse 489124 Oct  5  1939 tumblebrutus
-rw-r--r-- 1 tse tse 758012 Oct  5  1939 victoria

By looking at wrapper.c and script, you can eventually figure out that the only significant command you’re allowed to run here will be

wrapper ./bin/script

followed by some list of cat names from gats (Catalan for “cats”). Following the script’s rules, each cat may be used at most once, and no other input sources may be provided.

When the combined size of those files is exactly 982832 (hexadecimal EFF30!), this command will go on to run the command cat flag/flag.txt under the user account macavity (due to the wrapper running setuid macavity). But if the size is anything else, you’ll get an error due to skipping too many or too few bytes. (If the input size is too small, dd will skip over the cat flag/flag.txt command, while if the input size is too large, it will contain one or more X characters which will render the cat flag/flag.txt command syntatically invalid. If the input size is just right, however, the cat flag/flag.txt command will get interpreted by a shell running as user macavity, and will succeed.)

So, the question is what combination of cat sizes would exactly equal 982832. This is an instance of the SUBSET SUM problem in computer science, which is an NP-complete problem asymptotically as difficult as SATISFIABILITY (hence the name of this challenge). However, fortunately for you, this instance of the problem is small enough that you can easily solve it by brute force by writing your own script to try all possible subsets of the cats. The number of cases to be examined by brute force would be 2²³ or 8388608, which should not take much time at all on a modern computer. One example of a brute force solution in Python is

#!/usr/bin/env python

import itertools

cats = [408882, 68123, 31147, 12913, 58019, 198120, 912014, 81291, 284011, 123819, 221810, 902124, 4891, 1892, 178123, 319873, 172831, 4839, 80012, 73183, 1921, 489124, 758012,]

for n in range(1, len(cats)+1):
    for c in itertools.combinations(cats, n):
        if sum(c) == 0xEFF30:
            print (n, c)

The correct answer is

wrapper ./bin/script gats/bombalurina gats/cassandra gats/deuteronomy gats/jennyanydots gats/pouncival gats/rumtumtugger gats/sillabub

although the order of the cats doesn’t matter and any other order is also valid.

Running this produces the following output

***********
Enhorabona!
***********

La resposta és quatre mil milions dos-cents sis milions cinc-cents quaranta-sis mil sis-cents sis.

This means

****************
Congratulations!
****************

The answer is four billion two hundred six million five hundred forty-six thousand six hundred six.

so your hexadecimal answer is FABACEAE.