Google CTF 2020 - sprint Writeup
因為工作性質的關係，最近研究的內容不太適合公開，所以也好久沒更新部落格了，剛好這次打 Google CTF 的時候難得碰到一題好玩的 reverse 就決定貼上來跟大家分享
老實說因為分析起來相當有趣，如果沒玩過的建議先不要看以防劇透
SPRINT
這題最後值 173pt，共有 65 個隊伍解出來
初見題目
拖進 IDA 後發現 binary 本身並沒有甚麼好分析的，
首先題目會先做一次 mmap，並將一大堆 format string 複製過去
因為字串尾有 \0 所以 IDA 解出來會看起來只有一個字串，實際上有這麼多 (後面還有)
做好一些初始化後，就用 while 不斷執行 sprintf 直到退出
看到這裡我第一個想到的是 carlini 的大作 printf-tac-toe，他只用 printf 就實做出一個 tic-tac-toe 遊戲，非常有趣，推薦有興趣的人去玩看看
順帶一提，我查了一下今年的 IOCCC 得獎作，赫然發現他有在上面，恭喜XD
Best of show - abuse of libc (by Nicholas Carlini)
然後 Endoh 大法師今年又上了三個
回到題目上，一開始我花了不少時間在搞懂他是怎麼運作的，總之先來看看他都 print 些甚麼吧，下面是執行起來後 sprintf 使用的第一個格式化字串
%1$00038s%3$hn%1$65498s%1$28672s%9$hn因為會有很多事情發生在一行內，這邊我來幫各位複習一下這該怎麼讀
%1$00038s: 以%s印出第一個參數，共 38 bytes%3$hn: 將目前總共輸出的字元數寫入至第三個參數所指的位置 (hn: word pointer)%1$65498s: 以%s印出第一個參數，共 65498 bytes%9$hn: 將目前總共輸出的字元數寫入至第九個參數所指的位置 (hn: word pointer)
上面提到的第幾個參數都是對於格式化字串來說的，在 printf 家族中
$n代表放在格式化字串後的第 n 個參數
因為第三個參數是 &format，所以第一次的寫入很明顯地是在更新下一個要用的 format string，不過第二次的寫入就不知道在做些甚麼了，只能看出是對 stack 上的內容寫值
注意到
format的值有 8 bytes (0x6000000)，而寫入時只會寫掉底下 2 bytes，所以不會影響上面的 0x600
與第一個 format string 類似的字串很多，不過捲到下方會發現還有另一個變種
%14$c%1$00419s%2$c%4$s%1$65499s%3$hn剛開始看的時候覺得前面的 %14$c 跟 %2$c 都是混淆，跟單純寫 %c 一樣沒有差別，所以整句就只是
%14$c%1$00419s%2$c: 印出 221 個字元%4$s: 印出 0x6000000 位置的字串 (sprintf 的 output buffer，也就是上一次印出的字串)%1$65499s: 印出 65499 個字元%3$hn: 更新 format string address
然後我就看不懂，卡住了
digging harder
當然上面是我大錯特錯，過了兩小時我才突然醒悟到那東西實際上是一個 if…else 的 branch (!)
要先從這個 sprintf 程式怎麼運作的開始講起，
每次 sprintf 被呼叫時，帶在後面的那堆意義不明的參數實際上是被作為暫存器來使用的，例如說 *v5、v5、&v5 因為有取值所以就是用來做指標存取的，v6-13、&v6-13 就是作為一般暫存器使用，程式會利用指向變數的指標(&v6)把值寫入，下個指令再把值(v6)取出來使用
還有一點是 sprintf 會一邊解析字串一邊將要印出的字串寫入到 buffer 中
所以這段 format string 應該這樣理解
%14$c: 印出v9暫存器中的值 (寫入 1 byte，可能是\0)%1$00419s: 印出 419 個字元 (寫入 419 byte)%2$c: 印出 1 byte (寫入 null byte，第二個參數永遠是 0)%4$s: 印出 buffer 上的字串%1$65499s: 印出 65499 個字元%3$hn: 更新 format string address
所以當 v9 != 0 的時候，%4$s 總共會印出 1+419 chars (%2$c 會截斷後面的字串)，所以總共印出 1+419+1+420+65499 chars，format 會被更新為 0x6000804
另一方面當 v9 == 0 的時候，因為一開始就遇到 null byte，%4$s 不會印出任何字元，總共印出 1+419+1+0+65499 chars，這次 format 被更新為 0x6000617
賽中我是一邊分析一邊想辦法寫一個 emulator 來分析/debug 這些 format string，不過後來發現我只需要一個 lifter/interpreter 把它轉譯到 x86 上，再來交給 IDA 就可以了
import re
from pwn import *
context.arch = 'amd64'
compiled = '''
mov r8, 0
mov r9, 0
mov r10, 0
mov r11, 0
mov r12, 0
mov r13, 0
mov r14, 0
mov r15, 0
mov rax, 0
mov rbx, 0
mov rcx, 0
mov rdx, 0
mov rdi, 0
mov rsi, 0
'''
# omitted format string here, it's seperated by '\n'
s = '''
...
'''
pc = 0
for now in s.split('\n'):
compiled += f'L{pc}:'
cnt = 0
for sub_str in now.split('%')[1:]:
matched = re.match('^([0-9]*\$)?(\*[0-9]*\$)?([0-9]*)?([schn]*)', sub_str)
reg_idx, length_idx, length, action = matched.groups()
reg_idx = int(reg_idx[:-1])
if action[-1] == 's':
if length_idx:
# *???$
idx = int(length_idx[1:-1])
# access stack registers
if idx >= 8:
if idx % 2:
raise
else:
reg_num = (idx-8)//2
# compiled += f'movzx stack_reg{reg_num}, stack_reg{reg_num}w\n'
cnt = f'{cnt}+stack_reg{reg_num}'
# access *ptr
elif idx == 5:
compiled += 'mov tmpw, WORD PTR [ptr]\n'
cnt = f'{cnt}+tmp'
# access ptr
elif idx == 6:
raise NotImplemented
# access &ptr
elif idx == 7:
raise NotImplemented
else:
raise NotImplemented
elif length:
if type(cnt) == int:
cnt = (cnt + int(length)) & 0xffff
else:
cnt = f'{cnt}+{int(length)}'
else:
if reg_idx == 4:
# fix it on %hn part
cnt = f'{cnt}+BRANCH'
else:
raise NotImplemented
elif action[-1] == 'c':
if reg_idx >= 8:
reg_num = (reg_idx-8)//2
compiled += f'test stack_reg{reg_num}b, stack_reg{reg_num}b\n'
if type(cnt) == int:
cnt = (cnt + 1) & 0xffff
else:
cnt += '+1'
elif action[-1] == 'n':
if type(cnt) == str:
if reg_idx == 3:
# %14$c%1$00419s%2$c%4$s%1$65499s%3$hn
# if 14$ != 0:
# # %2$c will put a \0 on output buffer so %4$s outputs 420 bytes
# jmp 1(%14$c) + 419(%1$00419s) + 1(%2$c) + 420(%4$s) + 65499
# else:
# jmp 1 + 419 + 1 + 0 + 65499
matched = re.match('([0-9]*)\+BRANCH\+([0-9]*)', cnt)
if matched:
a, b = matched.groups()
set_pc = f'jnz L{(int(a)*2-1+int(b)) & 0xffff}\n' # TRUE
# set_pc = f'jz L{(int(a)+int(b)) & 0xffff}\n' # FALSE always fall through
else:
set_pc = f'FIX PC = {cnt}\n' # manually deal with this case
# access ptr
elif reg_idx == 6:
compiled += f'lea tmp, [{cnt}]\n'
compiled += f'mov WORD PTR [ptr], tmpw\n'
# access &ptr
elif reg_idx == 7:
compiled += f'lea ptr, [{cnt}]\n'
# access stack registers
elif reg_idx >= 8:
reg_num = (reg_idx-8)//2
if reg_idx % 2:
compiled += f'lea stack_reg{reg_num}, [{cnt}]\n'
compiled += f'movzx stack_reg{reg_num}, stack_reg{reg_num}w\n'
else:
compiled += f'lea tmp, [{cnt}]\n'
compiled += f'mov WORD PTR [stack_reg{reg_num}], tmpw\n'
else:
compiled += f'FIX {reg_idx=} = {cnt}\n'
else:
if reg_idx == 3:
set_pc = f'jmp L{cnt}\n'
elif reg_idx == 6:
compiled += f'mov WORD PTR [ptr], {cnt}\n'
elif reg_idx == 7:
compiled += f'mov ptr, {cnt}\n'
elif reg_idx >= 8:
reg_num = (reg_idx-8)//2
if reg_idx % 2:
compiled += f'mov stack_reg{reg_num}w, {cnt & 0xffff}\n'
else:
compiled += f'mov WORD PTR [stack_reg{reg_num}], {cnt & 0xffff}\n'
else:
compiled += f'FIX {reg_idx=} = {cnt}\n'
else:
raise NotImplemented
compiled += set_pc
pc += len(now) + 1
compiled += '''
L65534:
ret
'''
compiled = compiled.replace('stack_reg0', 'r8')
compiled = compiled.replace('stack_reg1', 'r9')
compiled = compiled.replace('stack_reg2', 'r10')
compiled = compiled.replace('stack_reg3', 'r11')
compiled = compiled.replace('stack_reg4', 'r12')
compiled = compiled.replace('stack_reg5', 'r13')
# compiled = compiled.replace('stack_reg6', 'r14') not used
compiled = compiled.replace('stack_reg7', 'r14')
compiled = compiled.replace('tmp', 'r15')
compiled = compiled.replace('ptr', 'rax')
assert(not 'FIX' in compiled)
open('./compiled', 'wb').write(make_elf(asm(compiled)))怎麼還沒解
對，這題在分析完落落長的 format string 後還沒結束，把 format string 轉譯成 x86 後，拖進 IDA 發現還有一坨很醜的玩意要分析…
賽後發現有隊伍把格式化字串轉成 python pseudocode 直接分析，敬佩之意油然而生…
void __fastcall start()
{
__int64 v0; // r15
__int64 v1; // r9
__int64 i; // r10
__int64 v3; // r8
__int16 v4; // r9
__int64 v5; // r8
__int64 v6; // r9
__int64 v7; // r10
__int16 v8; // r11
__int16 v9; // r15
__int64 v10; // r12
__int64 v11; // r15
__int64 v12; // r8
__int64 v13; // r9
__int16 v14; // r11
__int64 v15; // r10
__int16 v16; // r15
v0 = 0LL;
MEMORY[0x7000] = 1;
MEMORY[0x7002] = 1;
v1 = 2LL;
do
{
if ( !*(_WORD *)(2 * v1 + 0x7000) )
{
for ( i = 2 * v1; ; i += v1 )
{
v0 = i;
MEMORY[0xFFEF] = i;
if ( MEMORY[0xFFF0] )
break;
*(_WORD *)(2 * i + 0x7000) = 1;
}
}
++v1;
}
while ( (_WORD)v1 );
v3 = 0xE000;
v4 = 0;
while ( *(_WORD *)v3 )
{
--v4;
++v3;
}
if ( v4 != -254 )
goto LABEL_45;
v5 = 0LL;
v6 = 0LL;
LOWORD(v0) = MEMORY[0xF100];
v7 = v0;
v8 = 1;
while ( 1 )
{
v9 = *(_WORD *)(v5 + 0xE000);
if ( !v9 )
break;
++v5;
switch ( v9 )
{
case 'u':
v10 = 0xFFF0LL;
break;
case 'r':
v10 = 1LL;
break;
case 'd':
v10 = 16LL;
break;
case 'l':
v10 = 0xFFFFLL;
break;
default:
v8 = 0;
v10 = 0LL;
break;
}
v7 += v10;
v11 = v7;
MEMORY[0xFFEF] = v7;
if ( MEMORY[0xFFF0] )
return;
MEMORY[0xFFEF] = *(_WORD *)(v7 + 0xF000);
MEMORY[0xFFF0] = 0;
LOWORD(v11) = MEMORY[0xFFEF];
if ( *(_WORD *)(2 * v11 + 0x7000) )
{
v8 = 0;
}
else if ( !(unsigned __int8)(*(_WORD *)(v6 + 0xF103) + (_WORD)v7) )
{
++v6;
}
}
if ( v8 && (_WORD)v6 == 9 )
{
v12 = 0LL;
v13 = 0LL;
while ( (_WORD)v12 != 39 )
{
v14 = 4;
v15 = 0LL;
do
{
v15 *= 4LL;
v16 = *(_WORD *)(v13 + 0xE000);
if ( v16 != 'u' )
{
switch ( v16 )
{
case 'r':
++v15;
break;
case 'd':
v15 += 2LL;
break;
case 'l':
v15 += 3LL;
break;
default:
goto LABEL_45;
}
}
++v13;
--v14;
}
while ( v14 );
*(_WORD *)(v12 + 0xE800) = *(_WORD *)(v12 + 0xF10C) + v15;
++v12;
}
*(_WORD *)(v12 + 0xE800) = 0;
}
else
{
LABEL_45:
MEMORY[0xE800] = 0;
}
}其實也不是特別難看，從 u、r、d、l 可以看出來這應該是個迷宮，會先在 0x7000 開始的 array 中寫入一些固定值，接著會確認輸入長度是否為 254 bytes，再來用 0xF000 跟 0x7000 兩個 array 去構造迷宮讓使用者走，最後移動路徑上要走到 0xF10C array 規定的 9 個 byte 即可
但那時候已經是早上六點，於是我就犯了一些低級錯誤，沒能把迷宮成功 print 出來，當然也就沒在賽中解出題目了…
躺了一下午晚上才開始解題的下場就是這樣
例如說，沒想到這代表 i >= 0x100 要 break
MEMORY[0xFFEF] = i;
if ( MEMORY[0xFFF0] )
break;沒發現這代表 MEMORY[0xFFEF] = *(__int8 *)(v7 + 0xF000);
MEMORY[0xFFEF] = *(_WORD *)(v7 + 0xF000);
MEMORY[0xFFF0] = 0;後來想了想可能是因為 0xFFEF 跟 0xFFF0 這個組合很奇怪沒有向 2 對齊，才讓我腦袋轉不過來沒想到 (其實就是太笨了)
礙於篇幅限制，我就不放印出迷宮的腳本上來了，詳細的解題腳本可以到我的 Github repo 看
Solve
只要把迷宮印出來接下來就簡單了，題目限制是 254 個 byte，起始地點在左上角，很明顯就是走最短路徑按照順序走過那 9 個位置就好
大家知道這時候該用什麼工具記錄移動路徑嗎？
.
.
.
.
.
.
.
.
.
.
.
.
.
沒錯就是VIM啦!
這裡就教各位如何方便快速的紀錄移動路徑:
- 開啟 vim
- 把地圖貼進文件中
- 游標移動到起始位置
- 按
qa使用 record 模式開始記錄按鍵到aregister - 走迷宮…
- 按
q結束 record 模式 - 移動游標到空白行
- 按
"ap將aregister 的值印出
順便推廣一下之前跟朋友一起做的 Vim 教學XD
Slides
再來把 hjkl 轉換成 ldur 後就會得到
ddrrrrrrddrrrrrrrrddllrruullllllllddddllllllddddrrrrrrrruurrddrrddrrlluulluullddlllllllluuuurrrrrruuuuuulllllldduurrrrrrddddddllllllddddrrrrrruuddlllllluuuuuurruuddllddrrrrrruuuurrrrrruurrllddllllllddddllllllddddrrddllrruulluuuurrrrrruullrruurruuuurrrrrr最後貼到題目裡解出 flag，只能說這題解起來真是過癮!
Flag: CTF{n0w_ev3n_pr1n7f_1s_7ur1ng_c0mpl3te}