I’ve participated in 9447 CTF 2015 as the team scryptos.
Though I hadn’t been a member of scryptos, I felt like helping them by participating together because they remind me of what my team used to be.
I had to contribute to the team somehow, so I solved the heavy pwn task, Search Engine.

Description

Ever wanted to search through real life? Well this won’t help, but it will let you search strings.
Find it at search-engine-qgidg858.9447.plumbing port 9447.

Introduction

Search Engine is quite a simple service which can register a sentence with the word list splitting it into words by ‘ ‘ and can search those sentences with a word.

The available commands are:

1. Search with a word: Search the registered sentences such that they contain the given word.
2. Index a sentence: Register the given sentence into the word list creating nodes for every word the sentence contains.
3. Quit: Simply return;

Here is the main parts of the implementation:

The vulnerability is self-evident: a typical UAF of node1->sentence caused by sharing node1->sentence with other nodes.
Let’s call this fundamental UAF “UAF1”.
Then, we can easily “spread” UAF to node2 by overlapping node1->sentence and node2 with UAF1 and then deleting node1->sentence again(I call this technique “UAF spreading”).
Let’s call this secondary UAF “UAF2”.
With UAF2, we can set all the members of struct WordList to any value.
Therefore we can leak an arbitrary address because node2->sentence will be output in SearchWord(void).
Yes, as you may see, this task is very typical and easy so far.
The problem is how to get ACE from here, for there is no process of re-inputting in node2->sentence once we create node2.
That means, at least, we cannot write an arbitrary value to an arbitrary address by UAF2 alone.

Observation

I consider it important to use a logical thinking process in writing exploits, so I’d like to write about what I thought at that moment although a concise article would be better.
First, I made a listing of what I could do using UAF2.
“What do I control?” is a significant question.

• Leak an arbitrary address at any length: as described above.
• Overwrite an arbitrary address at any length by ‘\x00’: memset(node->sentence, 0, node->sentence_size) does in line 53. However, because free(node->sentence) is always called after that, it must be crash when we pass the address which is not within a heap.
• Free an arbitrary address: we tend to pay attention to memset, but we also have the ability to free any address as we want. This is actually the key point.

Second, before thinking how to get ACE, I specified the libc used in this task by leaking because environment-dependent exploits might work and because we should always set up the environment as similar to the actual environment as possible for writing exploits. Then, it turned out that the libc is an ordinary libc-2.19 used in Ubuntu.

Third, I considered whether the null-byte overwrite could be used. Because of the restriction that passing non-heap addresses causes crash, the possible ways are to overwrite free@got.plt before it gets crash and to use heap addresses so that it won’t get crash. I realized the former couldn’t be used by checking the libc. And the latter actually could be useful because its situation was little different from that of plaiddb. It, however, was very complicated and I wanted a simpler method. So I gave up to use this overwrite.

Fourth, I focused on the third characteristic “Free an arbitrary address”. It is usually useless because to free invalid addresses causes abortion. But under a particular condition, it can work and becomes very useful. The condition is that an freed address is recognized as the chunk of fastbins. I hadn’t thought it could work, but I got confidence after I hit upon this idea and experimented with it.

Solution