Intro

This year our friends at FRA did something new and hosted a sort of Christmas crafts competition, aptly named "FRA-knäck". A nice play on words since knäck is a traditional Christmas candy and also means crack as in cracking a password or challenge. This competition consisted of four challenges, ranging from a Web CTF challenge to mapping out terrorist cells.

In this post, I'll share my solutions and methods for these challenges. I'll also try to expand a bit on some of the challenges, generalizing the underlying problems and showing how cheating was possible in some cases!

Challenges

FRA-knäck 1 - CTF

Link to original challenge: FRA-knäck - Hitta de tre flaggorna

The first challenge was a simple web page containing only a search bar similar to Google and three bullet points (translations are mine). The goal is to find all three flags by interacting with this web page.

Flagga1: Närmare än vad du tror (closer than you think)
Flagga2: En sökning bort (One search away)
Flagga3: I developers home (In developer's home)

One interesting thing with this challenge is that the VM running this challenge is shared by all users. Making for interesting communications attempts between competitors and even cheating, sometimes by mistake, as explained in Behind-the-scene / Cheating.

Solutions

Flag 1

The first is flag simply part of the HTML source code. You can view it with devtools (CTRL+SHIFT+I), right-click and "View Page Source", or simply curl.

Flag 2

Next, we need to start interacting with the web page. Trying some normal queries like "test", "secret", "flag", etc didn't give anything. Many special characters were blocked too, for example, <, > and ' resulting in:

We've detected that you've attempted to break into our search box. #Shame #Shame #Shame

(The actual check being used is [^a-zA-ZåäöÅÄÖ0-9:;* "\?\-\/\/], but we don't know this yet 😉 ). Similarly, some strings like shutdown and rm were blocked too.

Finally, testing semicolon ; gave an error, making command injection a possibility. Exploring this we are indeed able to execute ls, for example, by searching for ; ls. From this, we learn about a file called Flagga2 which upon reading, either with cat or just requesting from the web server, we get the second flag!

Flag 3

The final flag was quite tricky. As the hint says we should look in "developer's home". Checking /etc/passwd we note that developer is indeed the username and their home directory is /home/developer. However, we don't have any read access here. I think a lot of competitors got stuck here. The trick was to check sudo -l, which returns (developer) NOPASSWD: /usr/bin/curl. This means that we, apache as we are executing as, can run curl as developer without a password! This was also an important part of a previous FRA Challenge, you can check out my blog post on it: FRA Challenge 2019-1.

While most people use curl to fetch data online, it can also be used to read local files by using the FILE URL scheme, i.e. file://. We still don't know exactly which file to read but since it's the third flag and in developers home, a good guess would be to read /home/developer/Flagga3. The full search query would be:

; sudo -u developer curl file:///home/developer/Flagga3

Behind-the-scene / Cheating

One of the most fascinating things about this challenge was watching other people trying to solve the challenge.

Cheat 1 - Nothing is temporary

Now a common thing to do after post-exploitation, i.e. when you find the command injection, is to look for directories you can write to. One such folder a lot of people found was /tmp/. Here you would find some funny files from different competitors:

Nov 26 22:43 yo-lite-klia-sig-i-huvet-ändå-:D  (Makes you scratch your head)
Nov 26 23:16 Jag-Är-Helt-Lost-På-Nr3-Jävla-Permissions (I'm totally lost on Flag 3, ******* permissions)
Dec  2 13:43 hi-m-this-is-d
Dec  2 14:36 macke-ring-aklagarn (Swedish meme)

While these were innocent and fun, someone sadly decided to write the last flag to the /tmp/ directory. I doubt that it was a mistake as there were 100 copies of the file with similar names.

I did remove these spoilers in /tmp. Here is a mini-challenge, how do you overwrite and/or remove a file without using rm or <, >?

Both write access to /tmp/ and all the files were quickly removed by the admins. But after a restart of the server one day, write access was temporarily restored. As you note above, some files were from Nov 26, and some form after a restart on Dec 2nd.

Cheat 2 - I see what you did there

If you run ps aux on a Linux machine you can see all active processes. I was not surprised that the server crashed as there were multiple instances of processes running commands like grep -rnw / -e *Flagga3*, which would search all files in the entire filesystem to find anything containing "Flagga3".

While the server was down I made sure to check it regularly waiting for the restart. Running ps aux soon after the reboot I found someone running this command:

sh -c /usr/bin/find ./ -name ; bash -c \"sudo -u developer /usr/bin/curl file:///home/developer/Flagga3\" 2>&1

This means that any competitor that couldn't find the answer themselves could watch ps aux in the hope of someone else leaking the correct query.

Cheat 3 - "That's not developer's home"

This is really just a version of the first cheat but there is a funny story to it.

On the last day I reached out to another competitor to check on their progress, let's call the person E. Here is a snippet of our conversation:

E: I think I found it!
B: Nice! Did you end up using sudo?
E: No sudo.
B: Wait what? How then!?
E: grep -r flagga /dev
B: That's not developer's home. 

E was well aware that /dev/ was not the intended directory. However, I tried it too and it worked... After doing some more digging I found the full path /dev/shm/superjanne and similarly to /tmp in the beginning, competitors could write files to /dev/shm/. This was a bit unfortunate as other competitors would find this file instead of the intended one. But using recursive grep in this way is pretty clever too!

Misc

Running netstat showed IPs connected to the server including both SSH and HTTP. Could be nice to track if you want to map IPs interested in this type of challenge 😉.

FRA-knäck 2 - Morse Code

Link to original challenge: FRA-knäck 2 – Tyd morsesignalerna

The second challenge was very straightforward in comparison to the first. You got a sound file with an audio message in morse code and then asked to convert it back to text. While you can listen to it, I prefer to open it in audacity and simply view the short and long pulses. The image below shows a snippet of the message. You can see the pulses: short-short-long-short (F), short-long-short (R), short-long (A).

FRA-knäck 3 - Terrorist Cell

Link to original challenge: FRA-knäck 3 – Lös analytiker­testet

If Die Hard is your type of Christmas movie then this challenge is for you. Here you need to answer four questions about a terrorist cell and you only have 40 minutes!

The information you get is a list of who-calls-who in the group. Below are the first few entries

A calls G, H and K 
B calls C, D and M 
C calls B and D
...

And the questions (translated by me):

Question 1 - Who is the leader of the organization?
Question 2 - Who is the second in command?
Question 3 - In how many cities do they have local groups?
Question 4 - Which two terrorists are probably living together?

Solutions

I wrote a short python snippet to draw the graph using graphviz. The generated graph is shown below.

As E is in the center and calls the other (as opposed to getting called by the others) I would believe they are giving commands rather than receiving them, making E a plausible leader.

Since G is the only one calling E, I think they have a more equal standing perhaps and therefore G would be a good second in command.

Visually it is easy to see that there are three groups. From a graph-theoretical perspective, we also have three strongly connected components. However, this would include E in a local group which is probably not the case.

Finally, C and M are the ones living together. If you look at the local groups you'll see that everyone talks with everyone, except these two. This is because they can communicate at home.

FRA-knäck 4 - Psychotechnical Test

Link to original challenge: FRA-knäck 4 - Bilda fem ord

In this final challenge, we need to create five valid Swedish words using the table below. Each column represents the position of the letter, so sien could be a word for example if it was also a valid Swedish word. You are also only allowed to use each cell once. Sadly, I can't really translate this one in a meaningful way.

First	Second	Third	Fourth
s	i	e	n
t	k	r	m
u	t	g	l
v	k	a	a
ö	a	a	n

Solutions

My wife and I did this one together and we didn't really have any systematic approach. We used a spreadsheet to color each letter based on which word they were part of. This made it easy to backtrack and keep track of which letters we had already used. After a few minutes we ended up with: SKAL, TIGA, UTAN, VARM, ÖKEN.

First	Second	Third	Fourth
s	i	e	n
t	k	r	m
u	t	g	l
v	k	a	a
ö	a	a	n

Automatic

This section is about how this challenge can be solved automatically. If you don't care about my babbling, you can just download the code here: simulate.py (slow) and letterBudget.py (fast) and don't forget the word list. You can also use generate.py to generate your own challenge. I've included my own generated challenge at the end.

Naturally, at this point, I had two questions: Is this the only solution? and can we find solutions automatically? In short, no and yes, to some extent. The reason for to some extent is because we get a combinatorial explosion as the table grows in size.

To do this automatically, we need a word list first of all. I use the following Swedish word list with over 400,000 words. My first approach was to use recursive backtracking. This allows us incrementally build the words by analyzing one column at a time and quickly discarding any partial words that do not work. Below are two examples where partial words are discarded because one of the partial words has an invalid prefix. We can know these prefixes are invalid by querying the word list. An efficient way of doing this is to create a set() with all possible prefixes from the word list. This is of course a memory-speed tradeoff.

(s, t, u, v, ö) -> (si, tk, ut, vk, öa) -> None (No 4-letter word starts with tk)
(s, t, u, v, ö) -> (sk, ti, ut, va, ök) -> (ske, tir, utg, vaa, öka) -> None (No 4-letter word starts with tir)

Running this we get the two possible solutions:

skal,tarm,utan,viga,öken
skal,tiga,utan,varm,öken

The problem here is that for each column we need to generate all permutations of a column, for the challenge that would be 5! = 120 permutations. Not too bad. But then, in the worst case where all partial words are valid, we need to multiple this for each column, i.e. 5! * 5! * 5! = 1,728,000 (the first column is constant). In general, this algorithm has a worst-case time complexity of O((n!)^m) for n rows and m columns. Horrendous!

This is a nice example of "In Theory There Is No Difference Between Theory and Practice, While In Practice There Is". Because for the given data, the letters in the table and the word list, we only check 4920 cases, much less than the worst-case 1,728,000. If we take a closer look we see that only 4 cases make it to the third column and only 36 make it to the last. Therefore, 4*5! + 36*5! + 5! = 4920.

That's not good enough!

I want to solve a bigger one. A 7x7. The worst-case here is on the order of 10^22 and in practice, well in practice my computer is too weak.

With my new approach, I solve the problem "backward" in some sense. I look at all the combinations of the words in the word list and see which fits the table. At first glance, this seems insane, just picking two words from a word list of 400,000 words can be done in about 80 billion ways, never mind 5 or even 7 words!

The key here is that the filtering can be much more aggressive. First of all, we can remove all words that do not have the correct letter in the correct column. Going back to the main example, the word must start with either s, t, u, v, or ö. The second letter must be i, k, t, or a. etc. This takes us from 400,000 words to 3245 words of the correct length and finally only 21 words with the correct characters.

Next, we create a letter budget and use divide and conquer to add more and more words. A letter budget in this case is just a simple count of how many of each letter we have in each column. For example, the first word we pick could be stel and the second utan. On their own, both are valid, but together they are not because there is only one t in the second column. I.e. the letter budget for t would become -1.

Below is the case if we pick skal as the first word. We then get 12 words that work with skal. This is the divide and conquer step as now we have one of the five words and only need to find four words using a word list of only 12 words. Easy! In round 2, tiga is the only possible one. Note, that from the table we know that the second word starts with t.

# Round 1
skal {'tiga', 'vira', 'tian', 'taga', 'öken', 'viga', 'vagn', 'utan', 'vara', 'vaga', 'varm', 'tarm'}

# Round 2
['skal'] tiga {'varm', 'utan', 'öken'}

# Round 3
['skal', 'tiga'] utan {'öken', 'varm'}

# Round 4
['skal', 'tiga', 'utan'] varm {'öken'}

# Round 5
['skal', 'tiga', 'utan', 'varm'] öken set()

Here is also a run where the first word is not correct.

# Round 1
stel {'tian', 'taga', 'vara', 'tiga', 'vira', 'varm', 'viga', 'vaga', 'vagn', 'tarm'}

# Round 2
['stel'] tian {'vara', 'varm', 'vagn', 'vaga'}
['stel'] taga set()
['stel'] tiga {'varm'}
['stel'] tarm {'viga'}

While this approach has the same combinatorial explosion problem and terrible time complexity, it's still much faster in practice because of the constraints of the problem allowing for aggressive filtering.

I'll leave you with a 7x7 challenge below. It has somewhat of a theme related to FRA :)

c	n	l	f	i	e	r
k	o	i	s	a	l	n
a	i	m	i	n	g	t
m	h	r	t	a	e	r
s	ö	s	l	f	ä	t
h	e	i	o	t	m	r
f	p	d	n	v	a	r

Conclusions

All in all, I think this set of challenges was really interesting. They both covered a nice range of topics and were accessible for people with different skill sets. I hope this becomes a new Christmas tradition! God Jul!

---

Write your comment!

Submit

Comments