Calc was a pwn challenge with a stack underflow bug in a reverse Polish notation calculator. The C++ std::vector used for the stack didn’t validate size before operations, allowing us to pop from an empty vector and corrupt heap metadata.

We exploited this by carefully traversing heap structures to leak ASLR-defeating pointers through the corrupted vector’s back() method. After leaking the xor function handler address, we overwrote it with __errno_location@plt to leak libc base addresses. The final step required guessing one byte of the leaked pointer (1/256 success rate) to call system() and get the flag.

The bug

After decompiling the binary, we get roughly the following C++ code (rewritten as pseudocode for clarity):

unordered_map<string, function<int(int, int)>> ops = ...;

int main()
{
    while(true)
    {
        cout << "--- Enter code: ---\n";
        vector<int> stack;
        string cmd;
        for(;;)
        {
            cin >> cmd;
            if(cmd == "end")
                break;
            else if(cmd == "quit")
                return 0;
            auto it = ops.find(cmd);
            if(it != ops.end())
            {
                int a = stack.back();
                stack.pop_back();
                int b = stack.back();
                stack.pop_back();
                stack.push_back(it->second(a, b));
            }
            else
                stack.push_back(stoi(cmd));
        }
        cout << "Result: " << stack.back() << endl;
    }
}

We see that the app implements a simple reverse Polish notation interpreter with several predefined operations (add, sub, mul, div, and, or, xor). The stack is stored inside a C++ std::vector, and the code never checks that there are enough operands for the operation. This means, that we can make the code pop from an empty vector.

C++ vectors are represented as 3 pointers, here I’ll name them start, stop, cap (I don’t remember the actual glibcxx field names). start points to the start of the buffer (i.e. the same as the begin() iterator), stop points to the past-the-last element (same as end()), and cap points to the end of the actually allocated buffer. Crucially, std::vector never shrinks the underlying allocation unless specifically told to do so.

To exploit the bug, we have to do the following:

  1. Push some integer (0) to the stack, so that the pointers become non-NULL.
  2. Perform some operations on the stack, and let stop become less than start. These operations might corrupt the heap somewhere below the vector’s buffer.
  3. Perform an end command. This will leak a single dword from the heap (wherever back() happens to point) and free the vector (this won’t cause any issues as long as the heap structures are intact, since the start pointer still points to the actual start of the buffer)

Heap layout

Fortunately for us, although the binary has ASLR, relative layout of the heap is still completely deterministic. This means that we can look at it in the debugger, to see if we can find a useful pointer to leak.

(gdb) p {void*[264]}(({void*}$rdi) - 264 * 8)
$3 = {0x5602a9791dbf <std::_Function_handler<int (int, int), ops[abi:cxx11]::{lambda(int, int)#7}>::_M_invoke(std::_Any_data const&, int&&, int&&)>, 0xb3b3ec7f4e05e105, 0x0, 0x411, 0x65746e45202d2d2d,
  0x2d2065646f632072, 0xa2d2d, 0x0 <repeats 126 times>, 0x411, 0x6e65206464612030, 0xa64, 0x0 <repeats 127 times>, 0x21}

Here:

  • 0x411 and 0x21 are glibc heap block sizes, which are not very interesting to us
  • 0x6e65206464612030, 0xa64 is our input string "0 add end\n" (this is the std::cin buffer)
  • 0x65746e45202d2d2d, 0x2d2065646f632072, 0xa2d2d is the string "--- Enter code: ---\n" (this is the std::cout buffer)
  • 0x5602a9791dbf is the function handler for the xor operation (we want to leak this to defeat ASLR, and later overwrite it for exploitation)
  • 0xb3b3ec7f4e05e105 is the hash of the string "xor" (we’ll want to restore that one)

It turned out that the heap layout on the server differs a bit, so I had to bruteforce some of the offsets to make it work, but in the end it worked just fine.

Actually leaking stuff

Unfortunately, we can’t go through the heap with our stack interpreter without corrupting data. Or can we?

  • If back() is zero, we can use or (or add) to pop it off without corrupting the next dword
  • If back() is nonzero, but the next dword is zero, we can use and (or mul) to pop it off without corrupting the zero

These two facts let us slip through the heap metadata without corrupting it (since the heap is deterministic, we can just hardcode the commands here). Also, we don’t have to preserve the cout buffer — at worst, it will make the output gibberish, but even that does not seem to actually happen. But, we do have to preserve the cin buffer, since it’s where our commands are being parsed from.

To do that, I came up with the following:

  1. Send data to the application in chunks of 512 bytes, wait until the latest fragment has been TCP ACKed before sending any more fragments. This ensures that the location of the cin buffer is a) well-known and b) its size is a multiple of 4.
  2. When passing through the cin buffer, do it using "or " commands (note the extra space). The extra space is needed so that all dwords in the cin buffer are equal, and or operations do not corrupt the buffer.
  3. Once we have passed the 0x411 that follows the hash table, zero out the hash using two and operation, pop the bottom zero using an extra or, and leak the high dword of the pointer as the “calculation” result.
  4. Repeat the leak with one extra and to zero the upper dword and leak the lower one. We do not use the xor operation in our exploit, so temporarily corrupting the structure is not a problem.

Now we’ve defeated ASLR by leaking the pointer to the xor std::function handler. We can also trivially overwrite the pointer, by zeroing it first, then or‘ing in the lower half, then pushing a bunch of other dwords we want to restore (at the very least, upper half of that pointer & the hash).

If only we had a one_gadget right in the main binary…

Leaking libc

Unfortunately, the heap does not seem to contain libc pointers that can be leaked with our primitive. A teammate suggested that I could cause pressure to the allocator to cause it to leak some libc pointers to the heap, but since the only operation we can really do is reallocating the vector during push_back, that one is a no-go. I decided to search through the binary’s PLT to see if it contains a useful function. And sure it does!

The abi of the std::function handlers, as used by the binary, is int(void*, int*, int*). This means that we can call any function with a single partially controlled argument (the first argument is the std::function itself, 0x18 bytes before the pointer). And there is a useful function in the imports: int* __errno_location(void). Through my experiments, I observed that the address it returns, although not lying directly inside libc, is always at a constant offset from it, so it can be used to leak the libc base (and thus the address of system).

Now, if we overwrite the 0x5602a9791dbf pointer with a pointer to __errno_location@plt inside the binary, and execute an innocent 1 2 xor end, we get a truncated pointer as a result. Knowing the 32 lowest bits of the pointer, we can assume that the 5th byte (bits 40-47) is 0x7f (was always the case on my machine, at the very least), and assume a random value for the 4th byte. This will make the exploit have only a 1/256 chance of success, but it’s better than nothing.

Calling system()

Now that we’ve leaked (hopefully!) the address of system, we can use the same heap write primitive to write "cat /flag*; sleep inf" to the start of our std::function, also overwriting its handler with system(), then execute 1 2 xor again to get the flag. At this point, we either crash (if our guessed byte was incorrect), or get the flag and hang up.

I then put the exploit on repeat, and after about 10 minutes it gave me the flag.