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}