阿里云CTF逆向題“歐拉”詳細Writeup

題目來源：阿里云CTF
題目類型：逆向
題目描述：

歐拉歐拉歐拉歐拉！
[attachment](Euler.exe)

題目解析：
使用IDA打開，F5，整體先看一遍，100多行，沒有混淆

先看變量定義這里：

char Str1[16]; // [rsp+20h] [rbp-40h] BYREF
__int128 v21; // [rsp+30h] [rbp-30h]
__int128 v22; // [rsp+40h] [rbp-20h]
__int16 v23; // [rsp+50h] [rbp-10h]

反編譯有一點瑕疵，需要將Str1變量的數組長度調整為50
選中Str1右鍵，Set lvar type，修改為 char Str1[50]
Why?
雙擊Str1，可以跳轉到Stack of main頁面查看

-0000000000000040 Str1            db 16 dup(?)
-0000000000000030 var_30          xmmword ?
-0000000000000020 var_20          xmmword ?
-0000000000000010 var_10          dw ?

其中：

Str1 是一個包含 16 個字節的數組，其中的值尚未初始化。
var_30 和 var_20 是未初始化的 XMMWORD 變量，每個變量占用 128 位（16 字節）。
var_10 是一個 double word 變量，占用 2 個字節。

備注：

DB和DW是匯編的偽指令，分別用來定義字節和字（兩個字節）的變量
DUP也是匯編偽指令，用于指示在聲明變量時重復多個相同的值。
XMMWORD 是一種數據類型，是指處理器寄存器中的 128 位數據（16字節）。

所以：16byte + 128bit + 128bit + 16bit = 16 + 16 + 16 + 2 = 50 byte

繼續往下看：

*(_OWORD *)Str1 = 0LL;
v23 = 0;
v21 = 0LL;
v22 = 0LL;

這里對應的匯編代碼是：

.text:00000001400010FB                 xorps   xmm0, xmm0
.text:0000000140001105                 xor     eax, eax
.text:0000000140001107                 movups  xmmword ptr [rbp+Str1], xmm0
.text:000000014000110B                 mov     [rbp+var_10], ax
.text:000000014000110F                 movups  [rbp+var_30], xmm0
.text:0000000140001113                 movups  [rbp+var_20], xmm0

一個xmm0寄存器是128位，ax寄存器是16位
可以和上面的Str1的數組長度對照
當修改Str1的變量類型后，會重新反編譯，這里就自動變成了 memset(str,0,50)

將 Str1 變量重命名為 input_flag
將 sub_140001020 函數重命名為 printf
將 sub_140001080 函數重命名為 scanf

v4 = -1i64;
do
  ++v4;
while ( input_flag[v4] );
if ( v4 != 29 || strncmp(input_flag, "aliyunctf{", '\n') || input_flag[28] != '}' )

這四行代碼說明v4是input_flag長度需要為29，且flag格式為aliyunctf{xxxxxxxxxxxxxxxxxx}，中間有18個未知字符

繼續往下：

v3 = -1i64;
v5 = 0;
while ( input_flag[v3++ + 11] != 0 ) ;
if ( v3 != 1 )
{
	v7 = &input_flag[10];
	while ( (unsigned __int8)(*v7 - '0') <= 8u )
	{
		++v5;
		++v7;
		if ( v5 >= (unsigned __int64)(v3 - 1) )
		goto LABEL_12;
	}
	printf("Wrong\n");
	exit(0);
}

第一個while語句，執行結束后得到的v3，其實表示的是，整個intput_flag，出去aliyunctf{}之外的字符個數，其實就是18，后面用來循環中間的18個未知字符
下面v7就是遍歷18個未知字符，每個字符的范圍是 '0' - '8'

  if ( input_flag[11] > input_flag[12]
    && input_flag[13] < input_flag[14]
    && input_flag[10] == input_flag[18]
    && input_flag[21] == input_flag[25]
    && input_flag[20] > input_flag[15]
    && input_flag[13] < input_flag[23]
    && input_flag[17] < input_flag[14]
    && input_flag[24] == '7'
    && input_flag[27] == '4' )

這里的一堆判斷就是18個字符的約束條件
intput_flag[0-28] aliyunctf{xxxxxxxxxxxxxxxxxx}
intput_flag[10-27] xxxxxxxxxxxxxx7xx4

v10 = dword_140004040;

雙擊 dword_140004040 可以發現是一個 81 個元素的數組，每個元素是 0 或 1
其實這可以理解一個二維數組e[i][j]，表示在一個圖中，節點i和節點j是否有邊

.data:0000000140004040 dword_140004040 dd 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1
.data:0000000140004088                 dd 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1
.data:00000001400040D0                 dd 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1
.data:0000000140004118                 dd 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1
.data:0000000140004160                 dd 1, 1, 0, 1, 0, 1, 1, 1, 0

寫成數組就是（使用二維數組來理解）

e[9][9] = [
	0, 0, 1, 0, 0, 1, 0, 0, 1, 
	0, 0, 0, 1, 1, 1, 0, 0, 1,
	1, 0, 0, 1, 0, 0, 1, 1, 0, 
	0, 1, 1, 0, 1, 0, 0, 0, 1,
	0, 1, 0, 1, 0, 0, 1, 0, 0, 
	1, 1, 0, 0, 0, 0, 1, 0, 1,
	0, 0, 1, 0, 1, 1, 0, 0, 1, 
	0, 0, 1, 0, 0, 0, 0, 0, 1,
	1, 1, 0, 1, 0, 1, 1, 1, 0
]

繼續看后面的代碼

v8 = 17;
v9 = 0;
v11 = &input_flag[11];
while ( 1 )
{
	v12 = *(v11 - 1) - '0';
	v13 = *v11 - '0';
	if ( dword_140004040[9 * v12 + v13] != 1 ) goto LABEL_33;
	if ( dword_140004040[v12 + 9 * v13] != 1 ) goto LABEL_33;
	++v9;
	++v11;
	dword_140004040[9 * v12 + v13] = 0;
	dword_140004040[v12 + 9 * v13] = 0;
	if ( v9 >= v8 ) goto LABEL_26;
}

intput_flag[10-27] xxxxxxxxxxxxxx7xx4
簡單調整下代碼，可以理解為，對于intput_flag[11-27]的每個input_flag[i]
X = intput_flag[i-1]，Y = intput_flag[i]，e[X][Y] 和 e[Y][X] 都需要等于1，然后將這兩個都置為0，一共遍歷17次，最后跳轉至 LABEL_26

do {
	v16 = 0;
	v17 = v10;
	do {
	if ( *v17 ) goto LABEL_33;
	++v16;
	++v17;
	} while ( v16 < 9 );
	v10 += 9;
} while ( v10 < &unk_140004184 );
v18 = "Right\n";

注意，這里的V10和V17都是指針，代碼的含義是要遍歷 dword_140004040 這個數組，如果每個元素都是0，則符合預期

到這里反匯編的代碼基本分析完了，我們要做的就是根據邏輯逆推，算出 intput_flag[10-27]

這里將 input_flag[10-27] 簡化為 flag[0-17]，逆推的邏輯就是：

設計 dfs(idx, value) 函數，表示假設 flag[idx]=value，通過以下兩個條件去嘗試確認 flag[idx+1] 的值
- e[flag[idx]][flag[idx+1]] = 1
- e[flag[idx+1]][flag[idx]] = 1
直到 idx=17，這時根據 check_flag 函數檢查flag，如果不通過，則進行回溯。
初始從 flag[0] 開始嘗試，for v in range(0,9): dfs(0, v)

代碼示例如下：

arr = [
    0, 0, 1, 0, 0, 1, 0, 0, 1,
    0, 0, 0, 1, 1, 1, 0, 0, 1,
    1, 0, 0, 1, 0, 0, 1, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 0, 1,
    0, 1, 0, 1, 0, 0, 1, 0, 0,
    1, 1, 0, 0, 0, 0, 1, 0, 1,
    0, 0, 1, 0, 1, 1, 0, 0, 1,
    0, 0, 1, 0, 0, 0, 0, 0, 1,
    1, 1, 0, 1, 0, 1, 1, 1, 0
]

flag = [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]

def check_flag():
    if flag[1] > flag[2] \
        and flag[3] < flag[4] \
        and flag[0] == flag[8] \
        and flag[11] == flag[15] \
        and flag[10] > flag[5] \
        and flag[3] < flag[13] \
        and flag[7] < flag[4] \
        and flag[14] == 7 \
        and flag[17] == 4:
        return True
    return False

def dfs(idx, value):
    # if idx == 14 and value != 7: return
    flag[idx] = value
    print(idx, flag)
    if idx == 17:
        # input("...:")
        if check_flag():
            print("Finish")
            print(flag)
            exit()
        flag[idx] = -1
        return
    for i in range(0,9):
        j = value
        if arr[9*i+j] == 1 and arr[9*j+i] == 1:
            arr[9*i+j] = 0
            arr[9*j+i] = 0
            dfs(idx+1, i)
            arr[9*i+j] = 1
            arr[9*j+i] = 1
    flag[idx] = -1

for v in range(0,9):
    dfs(0, v)   # test flag[0]=v

運行結果為：
[0, 8, 5, 1, 3, 4, 6, 2, 0, 5, 6, 8, 3, 2, 7, 8, 1, 4]
所以 input_flag 就是 aliyunctf{085134620568327814}

官方題解說這道題就是計算歐拉路徑的，想了半天有點理解了
flag[0-17] 的每個元素范圍都是 0-8 說明在這個圖中有 8 個節點
flag[0-17] 就表示這 8 個節點的歐拉路徑
觀察二維數組e，每個元素e[i][j]理解為節點i到節點j是否有邊
可以發現第0行和第4行的和是單數，也就是說節點0和節點4是歐拉路徑的起點和終點
根據約束條件發現，flag[17]=4，所以flag[0]=0
這樣，可以直接執行 dfs(0, 0)
重點是能根據代碼邏輯理解是在干什么，并且知道這是和歐拉路徑有關聯。
但其實題目名稱已經有提示了……

graph LR 0 <--> 8 8 <--> 5 5 <--> 1 1 <--> 3 3 <--> 4 4 <--> 6 6 <--> 2 2 <--> 0 0 <--> 5 5 <--> 6 6 <--> 8 8 <--> 3 3 <--> 2 2 <--> 7 7 <--> 8 8 <--> 1 1 <--> 4

其他writeup：

https://bbs.kanxue.com/thread-281088.htm
https://xz.aliyun.com/t/14190#toc-19
https://wx.zsxq.com/dweb2/index/topic_detail/5122181218224444

posted @ 2024-04-30 18:22 Cathon 閱讀(231) 評論(0) 收藏舉報

刷新頁面返回頂部

Cathon

阿里云CTF逆向題“歐拉”詳細Writeup

公告