题目来源：阿里云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]] = 1e[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)
重点是能根据代码逻辑理解是在干什么，并且知道这是和欧拉路径有关联。
但其实题目名称已经有提示了……
其他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