Search Engine - 9447 2015

Published:

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

Codeforces Beta Round #44 (Div. 2)

Published:

I participated in the above-mentioned contest by the virtual contest system of CF.

Submission

From today, I’m going to participate in virtual contests often.

A. Triangular numbers

Given an integer n, find x such that x(x+1)/2 = n.
If there’s no solution, print “Impossible”.

Just do it.
But I used the binary search method.

B. Coins

Given the relations of weight between three coins A, B, and C, arrange these coins in ascending order.
If that relations are contradictory to each other, print “Impossible”.

Just do it.

C. Crossword

Given six strings, create a crossword puzzle made of those in the form of a rectangular “eight” or infinity sign.
If you can’t, print “Impossible”.

Crap.
Sure, I don’t like constructive algorithms.
But, besides it, this problem disgusts me because it doesn’t define “the lexicographically minimum” strictly.

D. Safe

Given an integer n(<=35) which represents the length of the password, an integer m(<=10) which represents the number of attempts of entering a password, each passwords entered and each system responses(how many positions stand the right numbers), then answer how many possible passwords that don’t contradict the m system responses are left.

Meet-in-the-middle attack!! Just do MITM.
BTW, in Japanese, MITM is called “half of all listing”.

E. Cannon

Given the n angles at which the n cannon balls will be fired, and the m positions of the walls, for every ball, answer the coordinates of its landing point.

Typical Geometry.
I didn’t have enough time to write the code of this problem, but the solution is simple.

  1. For each wall, calculate the range of angle at which a ball will hit it.
  2. Calculate “which angle at that a ball will hit which wall”.
  3. Calculate its landing point for each ball.

Today's solved

Published:

CodeForces #114 Div.1 B Wizards abd Huge Prize

  • Good DP Problem. It would get buggy easily. Make sure to define the recurrence equation accurately and not to misread the problem sentence.
  • solution

CodeForces #121 Div.1 E Thwarting Demonstrations

POJ 1113 Wall

POJ 3246 Game

  • This problem is bad. It has too weak testcases since my solution should not be passed(O(n^(5/3)logn)). The essence is how to calculate differences smartly.
  • solution

movie_talk - SECUINSIDE 2013

Published:

I always wonder if there is any good solution for I/O blocking on local exploit.
I tried sock.setblocking(False) and fcntl(fd, F_SETFL, flag | O_NONBLOCK), but both didn’t work.
pexpect module does non-blocking read(maybe it’s because of tty), but its output contains junk and input becomes corrupted(doesn’t support binary data?).
So please tell me if you know something.

exploit(consequently I did without reading): https://gist.github.com/potetisensei/9af8150d66031035cc10

Today's solved

Published:

CodeForces #109 Div.1 C Double Profiles

POJ 1759 Garland

  • Straightforward. But floating-point is fearful.
  • solution

POJ 2100 Graveyard Design

  • Just Do It. But since on POJ, you can’t use O(NlogN) methods like binary search. Use Inchworm Method(I don’t how to say in English. Is this correct?).
  • solution

CodeForces #119 Div.1 C Weak Memory and Aizu Online Judge 1150 Cliff Climbing

  • Easy. Remember Single-Source Shortest Path problem on unweighted graph can be solved by Breadth First Search. In some cases, it could be faster than dijkstra.
  • solution
  • solution

POJ 3180 The Cow Prom

  • READING HARD. Why don’t you describe in simple words, simple sentences?? Just Strongly Connected Component algorithm.
  • solution

POJ 1180 Batch Scheduling

  • A bit easy. But this is a good example of convex hull tric on DP.
  • solution