0CTF 2016 Quals - trace

follow the trace trace.log
the flag is at 0x400D80
(uint32_t)0x00410EA0 == 0x400D80

這是一個沒有 binary 的 reverse 題…
題目只提供了一個 mips binary 的 runtime trace log

整個 trace log 約有 24800 行,分析起來不太方便,因此先寫個腳本將 log 重組,照 address 排序並移除重複的 instruction:

#!/usr/bin/env python
from pprint import pprint

with open("./trace_8339a701aae26588966ad9efa0815a0a.log") as f:
    code = {}
    lines = f.readlines()
    for l in lines:
        addr, ins = l.replace("[INFO]", "").strip().split(" ", 1)
        code[addr] = ins

    pprint(code)

接著開始進行人肉反編譯,逆向 mips assembly ,分析其中的函數:
https://gist.github.com/L4ys/97163a2624d4c2dfd762

透過分析 strlen() 中的迴圈次數可以得知 flag 長度應為 26:

#!/usr/bin/env python

# load trace
code = []
with open("./trace_8339a701aae26588966ad9efa0815a0a.log") as f:
    lines = f.readlines()
    for l in lines:
        addr, ins = l.replace("[INFO]", "").strip().split(" ", 1)
        code.append({"addr": addr, "ins": ins})

# trace strlen
strlen = 0
for ins in code:
    if ins["addr"] == "00400770":
        strlen = 0
    elif ins["addr"] == "004007c8":
        print "strlen() = %d" % strlen
    elif ins["addr"] == "004007ac":
        strlen += 1

再進一步將整個程式用 C 還原:

char flag[27] = "<FLAG>";

void qsort(char* data, int len)
{
    if ( len < 2 )
        return;

    int j = 1;
    for ( int i = 1; i < len; ++i )
        if ( data[i] < data[0] ) {
            char t = data[j];
            data[j] = data[i];
            data[i] = t;
            j++;
        }

    char t = data[0];
    data[0] = data[j-1];
    data[j-1] = t;

    qsort(data,j-1);
    qsort(data+j,len-j);
}

int main() 
{
    char data[91] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}";
    
    strlen(flag);
    strcpy(data+64, flag);
    qsort(data);

    int s = 0;
    for ( int i = 0; i < strlen(data) - 1; ++i )
        if ( data[i] != data[i+1] )
            s++;
    if ( s != 63 )
        ...
}

了解程式行為後就可以從 trace 反推出 flag
由於 quick sort 函數中包含遞迴呼叫,用靜態分析的方式會非常難做

比較好的方式是透過 trace log 模擬整個 quick sort 的執行過程,在關鍵的 instruction 上做紀錄
產生出跟程式一樣的 sort 結果:

[0]0[19][11]1[7]23[8]4[23][18]5[17][9][13]6[16]78[21]9[15]ABCDEFGHIJKLMNOPQRSTUVWXYZab[1]cde[3]fghij[12]k[22][14]lm[10]n
opq[24][6]r[20]s[2][5]tuvwxyz[4]{}[25]

其中 [0] ~ [25] 代表 flag[0] ~ flag[25]
在這一步我們可以得到 flag 每一個字元所在的位置

而透過分析程式中最後一個迴圈,可以得知排序完後,相鄰的兩個字元是否相等
結合這兩個條件,就能推出原始 flag:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import string

# load trace
code = []
with open("./trace_8339a701aae26588966ad9efa0815a0a.log") as f:
    lines = f.readlines()
    for l in lines:
        addr, ins = l.replace("[INFO]", "").strip().split(" ", 1)
        code.append({"addr": addr, "ins": ins})

# trace strlen
strlen = 0
for ins in code:
    if ins["addr"] == "00400770":
        strlen = 0
    elif ins["addr"] == "004007c8":
        print "strlen() = %d" % strlen
    elif ins["addr"] == "004007ac":
        strlen += 1

# trace quick sort to generate sorted data with unknown flag char
flag = ''.join(chr(i) for i in range(0,26)) # flag[0] is 0, flag[1] is 1 ...
data = bytearray(string.ascii_lowercase+string.ascii_uppercase+string.digits+"{}" + flag)

stack = []
for ins in code:
    if ins["addr"] == "00400b5c":   # qsort(data, 90) in main()
        stack.append({"i":1, "j": 1, "start": 0, "len": 90})
        print "call qsort(data, 90) from main()"
    elif ins["addr"] == "004009cc": # leave qsort()
        stack.pop()
    elif ins["addr"] == "00400924": # i ++
        stack[-1]["i"] += 1
    elif ins["addr"] == "00400918": # j ++
        stack[-1]["j"] += 1
    elif ins["addr"] == "004008cc": # swap data[i], data[j]
        i, j, start = stack[-1]["i"], stack[-1]["j"], stack[-1]["start"]
        data[start+i], data[start+j] = data[start+j], data[start+i]
        print "swap(data[%d], data[%d])" % (start+i, start+j)
    elif ins["addr"] == "00400970": # swap data[0], data[j-1]
        j = stack[-1]["j"]
        start = stack[-1]["start"]
        data[start], data[start+j-1] = data[start+j-1], data[start]
        print "swap(data[%d], data[%d])" % (start, start+j-1)
    elif ins["addr"] == "00400990": # recursive call qsort(data, j - 1)
        j = stack[-1]["j"]
        start = stack[-1]["start"]
        stack.append({"i":1, "j": 1, "start": start, "len": j - 1})
        print "call qsort(data, %d)" % (j - 1)
    elif ins["addr"] == "004009b4": # recursive call qsort(data + j, len - j)
        j = stack[-1]["j"]
        start = stack[-1]["start"]
        l = stack[-1]["len"]
        stack.append({"i":1, "j": 1, "start": start + j, "len": l - j})
        print "call qsort(data + %d, %d)" % (start + j, l - j)

# trace the final compare loop, generate original sorted data
d = bytearray(string.digits + string.uppercase + string.lowercase + "{}")
sorted_data = bytearray("?" * 90)
i = 0
j = 0

same = True
for ins in code:
    if ins["addr"] == "00400bbc": # data[i] != data[i+1]
        print "data[%d] != data[%d]" % (i, i + 1)
        sorted_data[i], sorted_data[i+1] = d[j], d[j+1]
        same = False
        j += 1
    elif ins["addr"] == "00400bcc": # i ++
        if same:
            print "data[%d] == data[%d]" % (i, i + 1)
            sorted_data[i] = sorted_data[i+1] = d[j]
        same = True
        i += 1

# map flag
flag = bytearray("?" * 26)
for i, c in enumerate(data):
    if c < 26:
        flag[c] = sorted_data[i]
print flag

Flag: 0ctf{tr135m1k5l96551s9l5r}