0CTF/TCTF 2019 Quals: Sixology solution

_solve.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <string>
#include <iostream>
#include <iomanip>

uint64_t arr0[] = {
    0xFA730603, 0xF8084C29, 0xF4290A55, 0xF17A02CD,
    0xF1E59BC4, 0xF41ABBF1, 0xFDF84718, 0xF0083FD1,
    0xF1BAED2B, 0xFA2AEAC7, 0xF652CC03, 0xF178B08D,
    0xF1198EB5, 0xF0672595, 0xF1753690, 0xF2E67825,
    0xF2B0197A, 0xF84C8755, 0xFB72A68F, 0xF656D307,
    0xFC005E80, 0xF350372A, 0xF27B843E, 0xF1AE2E9B,
    0xF2ECB793, 0xF2CF233D, 0xFDAB487F, 0xFB7989EE,
    0xF585E8A7, 0xFB155234, 0xF8615835, 0xFE982EE1,
    0xF6C42E3E, 0xF96E377C, 0xF102A7E0, 0xFE2391E8,
    0xFA7500A5, 0xF640F391, 0xF1E1670F, 0xF9D0235F,
    0xF7C12D7D, 0xF863762C, 0xFBED5B8A, 0xFDB8DEC7,
    0xF186136E, 0xF2DFACF3, 0xFE5D1AC8, 0xF25E770D,
    0xFB56D6DD, 0xF33EB123, 0xF4B7FADA, 0xF6242889,
    0xF59F048F, 0xFC86FA29, 0xFCD04769, 0xF14B8063,
    0xFAA6F222, 0xF0D23990, 0xF6846A8C, 0xF3CD8234,
    0xFA440DE1, 0xF5DE4EE7, 0xF40C2BCA, 0xF0590358,
    0xF4A968CB, 0xF65A2DFF
};

uint64_t arr1[] = {
    0x2FA2377,  0x6D1C33E,  0x1B22D44,  0x171F345,
    0x183FF47,  0x2879609,  0x36EB9D7,    0x811BB,
     0xC12DB0,  0x1B7DB20,  0x54F2EC9,  0x11A893B,
     0x48DB44,   0x1F61D0,   0x8B7372,  0x1A717EF,
    0x167692A,  0x55ACE9B,  0x47D0923,   0x9E4F8E,
    0x2036162,  0x2F9AC19,  0x1E0DBF7,  0x1852D9B,
    0x26D4EBA,  0x20E3486,  0xBB0F702,  0x3E40DF6,
     0x24284B,  0x447418E,  0x7BB11A6,  0x6A330BC,
     0xC5815A,  0x2EFAA0D,   0xC1E170,  0x628F151,
    0x1C629CF,  0x2E04C82,   0x15445D,  0x1BDE2A7,
    0x46ABA70,  0x11A1341,  0xB733982,  0x6E87A60,
     0xF7715D,  0x24F3682,  0x181C131,  0x23AA7F6,
     0xA44B51,  0x29E1B4F,   0x2686A1,  0x1956047,
    0x214B4AC,    0xF3BF0,   0x9701B3,   0x1C3E00,
     0x6B4AAF,   0x773A9A,  0x2BCB4D1,  0x1690AF8,
    0x4139BD8,   0xE04630,  0x17E5300,   0x473799,
    0x401B105,  0x373A611
};

uint8_t arr2[] = {
    0x4E, 0xE4, 0x4C, 0x7A, 0xFE, 0xC9, 0xB7, 0x4E, 0xFE, 0xF1,
    0x1E, 0x3B, 0xBE, 0x41, 0xB3, 0x5A, 0xD6, 0xBB, 0x52, 0x37,
    0x62, 0xEE, 0x67, 0x32, 0xF6, 0x03, 0x55, 0x0B, 0x56, 0xB4,
    0x12, 0x59, 0x13, 0xA6, 0x8E, 0x56, 0x04, 0x74, 0x6A, 0x12,
    0xE5, 0xC3, 0x3F, 0x97, 0xF4, 0x82, 0x47, 0xA6, 0xCB, 0x46,
    0x97, 0xBD, 0x65, 0x13, 0x07, 0xF0, 0x2E, 0xDE, 0x36, 0x4C,
    0x44, 0x26, 0x02, 0xFB, 0xA3, 0x42
};

uint8_t arr3[] = {
    0x97, 0x15, 0x43, 0x98, 0x11, 0x2F, 0x3E, 0x06, 0x6D, 0x12,
    0x45, 0x33, 0x58, 0x0F, 0x6A, 0x8E, 0x84, 0x23, 0x3E, 0xAD,
    0x4D, 0x79, 0x21, 0x1D, 0x7B, 0x40, 0x1C, 0xC8, 0x8F, 0x11,
    0x6A, 0x18, 0x37, 0x97, 0x2E, 0x82, 0x2D, 0x2E, 0x28, 0x7C,
    0x3C, 0x8B, 0x0C, 0x68, 0x14, 0x7D, 0x49, 0x35, 0x37, 0x63,
    0x54, 0x13, 0x73, 0xCC, 0x9C, 0x54, 0x7C, 0x1F, 0x19, 0x59,
    0x40, 0x30, 0x13, 0x20, 0xCE, 0x64
};

uint64_t f(uint64_t r0, uint64_t r1)
{
    std::string s = "1";
    for (size_t i = 0; i < r0; ++i)
    {
        if (s.find(':') != -1)
        {
            std::cout << s << std::endl;
            exit(0);
        }
        if (i == r1 - 1)
            return std::stoull(s);
        auto t = s + '0';
        if (std::stoull(t) <= r0)
        {
            s = t;
            continue;
        }
        int it = s.length() - 1;
        while (it >= 0 && s[it] == '9')
            --it;
        if (it < 0)
            break;
        if (it != s.length() - 1)
            s = s.substr(0, it + 1);
        s = s.substr(0, s.length() - 1) + char(int(s[s.length() - 1]) + 1);
        if (std::stoull(s) > r0)
        {
            s = s.substr(0, s.length() - 1);
            s = s.substr(0, s.length() - 1) + char(int(s[s.length() - 1]) + 1);
        }
    }
    return -1;
}

int main(int argc, char **argv)
{
    std::string flag = "";
    for (size_t i = 0; i < 66; ++i)
    {
        auto a = arr2[i];
        auto b = f(arr0[i], arr1[i]) & 0xFF;
        auto c = arr3[i];
        uint8_t res;
        if ((a & 3) < 2)
            res = (a ^ b) + c;
        else
            res = (a ^ b) - c;
        std::cout << (uint32_t)res << std::endl;
        flag += char(res);
    }
    std::cout << flag << std::endl;
}

_solve.py

#!/usr/bin/env python3
import sys

arr0 = (
    0xFA730603, 0xF8084C29, 0xF4290A55, 0xF17A02CD,
    0xF1E59BC4, 0xF41ABBF1, 0xFDF84718, 0xF0083FD1,
    0xF1BAED2B, 0xFA2AEAC7, 0xF652CC03, 0xF178B08D,
    0xF1198EB5, 0xF0672595, 0xF1753690, 0xF2E67825,
    0xF2B0197A, 0xF84C8755, 0xFB72A68F, 0xF656D307,
    0xFC005E80, 0xF350372A, 0xF27B843E, 0xF1AE2E9B,
    0xF2ECB793, 0xF2CF233D, 0xFDAB487F, 0xFB7989EE,
    0xF585E8A7, 0xFB155234, 0xF8615835, 0xFE982EE1,
    0xF6C42E3E, 0xF96E377C, 0xF102A7E0, 0xFE2391E8,
    0xFA7500A5, 0xF640F391, 0xF1E1670F, 0xF9D0235F,
    0xF7C12D7D, 0xF863762C, 0xFBED5B8A, 0xFDB8DEC7,
    0xF186136E, 0xF2DFACF3, 0xFE5D1AC8, 0xF25E770D,
    0xFB56D6DD, 0xF33EB123, 0xF4B7FADA, 0xF6242889,
    0xF59F048F, 0xFC86FA29, 0xFCD04769, 0xF14B8063,
    0xFAA6F222, 0xF0D23990, 0xF6846A8C, 0xF3CD8234,
    0xFA440DE1, 0xF5DE4EE7, 0xF40C2BCA, 0xF0590358,
    0xF4A968CB, 0xF65A2DFF
)

arr1 = (
    0x2FA2377,  0x6D1C33E,  0x1B22D44,  0x171F345,
    0x183FF47,  0x2879609,  0x36EB9D7,    0x811BB,
     0xC12DB0,  0x1B7DB20,  0x54F2EC9,  0x11A893B,
     0x48DB44,   0x1F61D0,   0x8B7372,  0x1A717EF,
    0x167692A,  0x55ACE9B,  0x47D0923,   0x9E4F8E,
    0x2036162,  0x2F9AC19,  0x1E0DBF7,  0x1852D9B,
    0x26D4EBA,  0x20E3486,  0xBB0F702,  0x3E40DF6,
     0x24284B,  0x447418E,  0x7BB11A6,  0x6A330BC,
     0xC5815A,  0x2EFAA0D,   0xC1E170,  0x628F151,
    0x1C629CF,  0x2E04C82,   0x15445D,  0x1BDE2A7,
    0x46ABA70,  0x11A1341,  0xB733982,  0x6E87A60,
     0xF7715D,  0x24F3682,  0x181C131,  0x23AA7F6,
     0xA44B51,  0x29E1B4F,   0x2686A1,  0x1956047,
    0x214B4AC,    0xF3BF0,   0x9701B3,   0x1C3E00,
     0x6B4AAF,   0x773A9A,  0x2BCB4D1,  0x1690AF8,
    0x4139BD8,   0xE04630,  0x17E5300,   0x473799,
    0x401B105,  0x373A611
)

arr2 = (
    0x4E, 0xE4, 0x4C, 0x7A, 0xFE, 0xC9, 0xB7, 0x4E, 0xFE, 0xF1, 
    0x1E, 0x3B, 0xBE, 0x41, 0xB3, 0x5A, 0xD6, 0xBB, 0x52, 0x37, 
    0x62, 0xEE, 0x67, 0x32, 0xF6, 0x03, 0x55, 0x0B, 0x56, 0xB4, 
    0x12, 0x59, 0x13, 0xA6, 0x8E, 0x56, 0x04, 0x74, 0x6A, 0x12, 
    0xE5, 0xC3, 0x3F, 0x97, 0xF4, 0x82, 0x47, 0xA6, 0xCB, 0x46, 
    0x97, 0xBD, 0x65, 0x13, 0x07, 0xF0, 0x2E, 0xDE, 0x36, 0x4C, 
    0x44, 0x26, 0x02, 0xFB, 0xA3, 0x42
)

arr3 = (
    0x97, 0x15, 0x43, 0x98, 0x11, 0x2F, 0x3E, 0x06, 0x6D, 0x12, 
    0x45, 0x33, 0x58, 0x0F, 0x6A, 0x8E, 0x84, 0x23, 0x3E, 0xAD, 
    0x4D, 0x79, 0x21, 0x1D, 0x7B, 0x40, 0x1C, 0xC8, 0x8F, 0x11, 
    0x6A, 0x18, 0x37, 0x97, 0x2E, 0x82, 0x2D, 0x2E, 0x28, 0x7C, 
    0x3C, 0x8B, 0x0C, 0x68, 0x14, 0x7D, 0x49, 0x35, 0x37, 0x63, 
    0x54, 0x13, 0x73, 0xCC, 0x9C, 0x54, 0x7C, 0x1F, 0x19, 0x59, 
    0x40, 0x30, 0x13, 0x20, 0xCE, 0x64
)

def m(x):
    return x & 0xFFFFFFFF

def f(r0, r1):
    arr = []
    for i in range(r0):
        arr.append(((r1 + i) % r0) + 1)
    for i in range(r0 - 1):
        for j in range(r0 - i - 1):
            if str(arr[j]) >= str(arr[j + 1]):
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr[r1 - 1]

def g(r0, r1):
    i = 0
    num = '1'
    for i in range(r0):
        if i == r1 - 1:
            return int(num)
        t = num + '0'
        if int(t) <= r0:
            num = t
            continue
        it = 0
        while it < len(num) and num[-it - 1] == '9':
            it += 1
        if it == len(num):
            break
        if it:
            num = num[:-it]
        num = num[:-1] + chr(ord(num[-1]) + 1)
        if int(num) > r0:
            num = num[:-1]
            num = num[:-1] + chr(ord(num[-1]) + 1)
    return res

def main():
    flag = []
    for i in range(66):
        print('{}: {} from {}'.format(i, arr1[i], arr0[i]), end=' ')
        sys.stdout.flush()
        b = g(arr0[i], arr1[i])
        print('=', b)
        a = arr2[i]
        b = b & 0xFF
        c = arr3[i]
        if a & 3 in (0, 1):
            flag.append((a ^ b) + c)
        else:
            flag.append((a ^ b) - c)
        print(flag)
    print(''.join(map(chr, flag)))

if __name__ == '__main__':
    main()

ida_script.py

reg_names = ['r{}'.format(i) for i in range(40)]
# reg_names[29] = '???'          # `leave` changes this
# reg_names[30] = '???'          # `enter` and `leave` change this
reg_names[31] = 'sp'
reg_names[38] = 'cs'
reg_names[39] = 'ds'

def FixInsn():
    addr = here()
    insn = Dword(addr)
    opcode = (insn >> 12) & 0x1F
    if opcode in (3, 31):       # store, load.m
        t = (insn >> 17) & 3
        if t == 1:
            MakeRptCmt(addr, '[{}]'.format(reg_names[(insn >> 22) & 0x1F]))
        elif t == 2:
            MakeRptCmt(addr, '[{}+{:X}]'.format(reg_names[(insn >> 22) & 0x1F], insn & 0xFFF))
        elif t == 3:
            MakeRptCmt(addr, '[{:X}]'.format(insn & 0xFFF))
        else:
            MakeRptCmt(addr, 'INVALID MODE 0')
    elif opcode in (20, 27):    # cmp, strcmp
        t = (insn >> 27) & 3
        cmt = ''
        cmt += reg_names[32 + ((insn >> 30) & 3)]
        cmt += ', '
        cmt += ('<', '==', '>', 'INVALID MODE 3')[t]
        MakeRptCmt(addr, cmt)
    else:
        pass

hotkey = 'Ctrl-Shift-F'
idaapi.CompileLine('static FixInsn() { RunPythonStatement("FixInsn()"); }')
DelHotkey(hotkey)
AddHotkey(hotkey, 'FixInsn')
print '[*] Hotkey is set to', hotkey

patch_processor.py

from idaapi import *
from idc import *
from idautils import *

reg_names = ['r{}'.format(i) for i in range(40)]
# reg_names[29] = '???'          # `leave` changes this
# reg_names[30] = '???'          # `enter` and `leave` change this
reg_names[31] = 'sp'
reg_names[38] = 'cs'
reg_names[39] = 'ds'

for i, new_name in enumerate(reg_names):
    addr = 0x00000001800062F0 + i * 8       # reg_names
    addr = Qword(addr)
    for j in range(len(new_name)):
        PatchByte(addr + j, ord(new_name[j]))
    PatchByte(addr + len(new_name), 0)
    MakeUnknown(addr, 1, 0)
    create_strlit(addr, BADADDR)


op_names = ['op{}'.format(i) for i in range(32)]
# unused: 0 1 6 9 10 13 15 18 21 22 25 28 
op_names[2] = 'enter'   # get_sp_change
op_names[3] = 'store'   # ana (1: O_PHRASE, 2: O_DISPL, 3: O_MEM)
op_names[4] = 'swap'
op_names[5] = 'leave'   # get_sp_change
op_names[7] = 'lpbeg'   # start loop
op_names[8] = 'add'     # get_sp_change track_possible_values_cfg
op_names[11] = 'load.i'
op_names[12] = 'nor'    # get_sp_change track_possible_values_cfg
op_names[14] = 'sub'    # get_sp_change track_possible_values_cfg
op_names[16] = 'load.r'
op_names[17] = 'call'
op_names[19] = 'jmp'
op_names[20] = 'cmp'    # track_possible_values_cfg (0: <, 1: ==, 2: >)
op_names[23] = 'lpend'  # wrap loop
op_names[24] = 'div'    # track_possible_values_cfg
op_names[26] = 'switch'
op_names[27] = 'strcmp' # track_possible_values_cfg (0: <, 1: ==, 2: >)
op_names[29] = 'ret'
op_names[30] = 'jnz'
op_names[31] = 'load.m'  # track_possible_values_cfg, ana (1: O_PHRASE, 2: O_DISPL, 3: O_MEM)

for i, new_name in enumerate(op_names):
    addr = 0x00000001800090A0 + i * 16       # instruc
    addr = Qword(addr)
    for j in range(len(new_name)):
        PatchByte(addr + j, ord(new_name[j]))
    PatchByte(addr + len(new_name), 0)
    MakeUnknown(addr, 1, 0)
    create_strlit(addr, BADADDR)

# PatchDword(0x00000001800013E3 + 2, 0)           # xor imms with '0CTF' in `ana`
# PatchDword(0x0000000180003BB2 + 1, 0)           # xor with '0CTF' in `emu`
PatchDword(0x000000018000421F + 1, 0)           # xor imms with '0cTf' in `out_operand`

PatchByte(0x0000000180006EE0 + 0, ord('#'))     # op flag output format (like in cmp)
PatchByte(0x0000000180006EE0 + 1, ord('%'))
PatchByte(0x0000000180006EE0 + 2, ord('d'))
PatchByte(0x0000000180006EE0 + 3, 0)