目录
前言
题目描述
WriteUp
静态分析
解题思路
代码
总结
前言
算法分析题是CTF逆向题目中出现最频繁，花样最多的一类题目，本文先讲解某CTF比赛逆向真题（原题在攻防世界题库中），最后总结一下算法分析题的一般思路
题目描述
题目只给了一个附件，附件中内容如下
WriteUp
静态分析
针对这种文件没有拓展名的情况，我们需要先分析一下文件类型，这里我用的是Linux的file指令
可以看到，该文件是一个Linux下的ELF可执行文件，64位，下面先尝试执行一下看看效果
这道题就很有意思，输入之前没有任何的提示信息，输入错误了也没有任何的反馈，没办法，下面只能直接用IDA进行静态分析（若有提示信息则往往可以根据提示信息定位到关键代码，IDA快捷键为shift+F12）
用IDA进行反汇编和反编译，得到伪C代码，找到main函数
main函数中主要干两个事：先执行sub_11B4函数，再进入do-while循环，循环中执行sub_940函数，函数的返回值等于1或-1时退出循环，程序结束
下面我们需要分别看一下sub_11B4函数和sub_940函数在干什么
sub_11B4函数
把dword_202AB0赋值为0，其他什么也不干
sub_940函数
我们在这个函数里发现了puts("success! the flag is flag{md5(your input)}")，那么不用犹豫，这就是我们要找的关键代码，接下来根据逆向思维，我们需要分析当达到什么样的条件时会输出这句话，这句话成功输出了说明我们的输入是正确的（这句puts还告诉我们flag的值是输入字符串的md5值）
接下来分析这个函数，主要流程是：
（1）v4初始化为0，用户输入input
（2）双层循环，外层while循环的终止条件是dword_202AB0==2，内层do-while循环的终止条件是v3==1，重点放在do-while循环中，因为外层循环的dword_202AB0只是起到计数作用（这个变量在sub_11B4函数中被初始化为0），并不牵扯操作细节
这里需要先有一个目标意识，即：要使得程序输出"success! the flag is flag{md5(your input)}"，我们需要让外层while循环正常退出，而这需要让内层do-while循环正常退出三次，则我们需要让v3的值等于1三次
do-while循环中，每次循环先进入sub_86C函数，内容如下
sub_86C函数
该函数用于找到dword_202020数组（.data段中提前定义好了）中值为3的一个位置，并用dword_202AB4和dword_202AB8分别记录行号和列号
之后，根据用户的输入采取不同的操作：
若用户输入的ASCII码为100（即字符'd'），调用sub_E23()函数；输入的ASCII码为115（即字符's'），调用sub_C5A；输入字符w，调用sub_A92；输入字符a，调用sub_FEC
到这里我们还需要看一下这四个函数是干什么的，以sub_E23函数为例
sub_E23函数
可以看到，这个函数使用了上一步中dword_202AB4和dword_202AB8保存的行号 i 和列号 j 来寻址，那也就是说此时 dword_202020[dword_202AB8 + 15LL * dword_202AB4 + 225LL * dword_202AB0] == 3，这里 if 中表达的是3的右边一个位置，如果这个位置的值是1，则交换3和1的位置（相当于把3向右移动了一位），如果不是则再判断是不是4，不是4则什么都不干，返回0，是4则返回1（返回1是我们想要的）
到这里需要有一些想象力，我们输入什么的时候会调用sub_E23函数？没错，是输入字符 d 的时候，键盘上的WASD键，按下D像不像把3的位置向右移动了一格？有了这样的猜测，再看后面的几个函数就明白了
我们再看一个字符 s 调用的函数sub_C5A
sub_C5A
我想已经不用我多说了，我们的猜测是正确的，不过要注意这里用的是15乘行号，也就是说这很可能是一个一行有15列的二维数组
解题思路
分析到这里该拿的信息已经拿到了，接下来梳理一下思路：
在一个二维数组中，先定位到3的位置，再从这个位置出发，用WASD键控制上左下右移动，最终把这个3移动到4的位置，按下的WASD键就是输入的字符，这算一次成功的移动，我们共需要有三次才能输出puts语句
这里面有几个问题：
（1）为什么是移动到4？
因为在sub_C5A等移动函数中，当移动到4会返回1，而do-while循环中v3等于1后就退出do-while循环，使dword_202AB0++，dword_202AB0加3次后就会退出while循环，执行puts语句
（2）不是随便用WASD键移动！
我们再看一眼sub_E23函数，if 语句中是dword_202020[dword_202AB8 + 1 + 15LL * dword_202AB4 + 225LL * dword_202AB0] == 1，也就是说只有移动方向上那个位置是1才能移动，其他值都是不行的，这也保证了答案的唯一性
（3）二维数组如何构造？
dword_202020数组在内存中的定义如下：
在内存中，这是一个一维数组（data）的形式，我们可以用Python代码将其转换为一行有15列的二维数组（array_2d），例如：
# 转换为15列的二维数组
rows = 675 // 15
array_2d = []
for i in range(rows):
start_idx = i * 15
end_idx = min(start_idx + 15, len(data))
row = data[start_idx:end_idx]
array_2d.append(row)
二维数组构造完成之后可以将其转成Dateframe对象，打印出来更好看一些
第一个3到4的移动路径如下图
对应的输入字符串为ddsssddddsssdss
代码
这里给出完整代码，输出的md5值就是flag值
import hashlib
import pandas as pd
# 一维数组
data = []
# dd 5 dup(1), 0Ah dup(0), 5 dup(1), 0, 3, 2 dup(1), 6 dup(0)
data.extend([1]*5) # 5个1
data.extend([0]*10) # 0Ah = 10个0
data.extend([1]*5) # 5个1
data.append(0) # 0
data.append(3) # 3
data.extend([1]*2) # 2个1
data.extend([0]*6) # 6个0
# dd 5 dup(1), 3 dup(0), 1, 6 dup(0), 5 dup(1), 3 dup(0)
data.extend([1]*5) # 5个1
data.extend([0]*3) # 3个0
data.append(1) # 1
data.extend([0]*6) # 6个0
data.extend([1]*5) # 5个1
data.extend([0]*3) # 3个0
# dd 1, 6 dup(0), 5 dup(1), 3 dup(0), 5 dup(1), 2 dup(0)
data.append(1) # 1
data.extend([0]*6) # 6个0
data.extend([1]*5) # 5个1
data.extend([0]*3) # 3个0
data.extend([1]*5) # 5个1
data.extend([0]*2) # 2个0
# dd 5 dup(1), 7 dup(0), 1, 2 dup(0), 5 dup(1), 7 dup(0)
data.extend([1]*5) # 5个1
data.extend([0]*7) # 7个0
data.append(1) # 1
data.extend([0]*2) # 2个0
data.extend([1]*5) # 5个1
data.extend([0]*7) # 7个0
# dd 1, 2 dup(0), 5 dup(1), 7 dup(0), 2 dup(1), 0, 5 dup(1)
data.append(1) # 1
data.extend([0]*2) # 2个0
data.extend([1]*5) # 5个1
data.extend([0]*7) # 7个0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*5) # 5个1
# dd 8 dup(0), 1, 0, 5 dup(1), 8 dup(0), 4, 0, 4Dh dup(1)
data.extend([0]*8) # 8个0
data.append(1) # 1
data.append(0) # 0
data.extend([1]*5) # 5个1
data.extend([0]*8) # 8个0
data.append(4) # 4
data.append(0) # 0
data.extend([1]*0x4D) # 4Dh = 77个1
# dd 0Dh dup(0), 2 dup(1), 0, 3, 5 dup(1), 6 dup(0), 2 dup(1)
data.extend([0]*0x0D) # 0Dh = 13个0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.append(3) # 3
data.extend([1]*5) # 5个1
data.extend([0]*6) # 6个0
data.extend([1]*2) # 2个1
# dd 0, 2 dup(1), 3 dup(0), 1, 6 dup(0), 2 dup(1), 6 dup(0)
data.append(0) # 0
data.extend([1]*2) # 2个1
data.extend([0]*3) # 3个0
data.append(1) # 1
data.extend([0]*6) # 6个0
data.extend([1]*2) # 2个1
data.extend([0]*6) # 6个0
# dd 1, 6 dup(0), 2 dup(1), 0, 2 dup(1), 3 dup(0), 5 dup(1)
data.append(1) # 1
data.extend([0]*6) # 6个0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*2) # 2个1
data.extend([0]*3) # 3个0
data.extend([1]*5) # 5个1
# dd 2 dup(0), 2 dup(1), 0, 2 dup(1), 7 dup(0), 1, 2 dup(0)
data.extend([0]*2) # 2个0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*2) # 2个1
data.extend([0]*7) # 7个0
data.append(1) # 1
data.extend([0]*2) # 2个0
# dd 2 dup(1), 0, 2 dup(1), 7 dup(0), 1, 2 dup(0), 2 dup(1)
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*2) # 2个1
data.extend([0]*7) # 7个0
data.append(1) # 1
data.extend([0]*2) # 2个0
data.extend([1]*2) # 2个1
# dd 0, 2 dup(1), 5 dup(0), 4 dup(1), 0, 2 dup(1), 0, 2 dup(1)
data.append(0) # 0
data.extend([1]*2) # 2个1
data.extend([0]*5) # 5个0
data.extend([1]*4) # 4个1
data.append(0) # 0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*2) # 2个1
# dd 5 dup(0), 1, 2 dup(0), 1, 0, 2 dup(1), 0, 2 dup(1)
data.extend([0]*5) # 5个0
data.append(1) # 1
data.extend([0]*2) # 2个0
data.append(1) # 1
data.append(0) # 0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*2) # 2个1
# dd 5 dup(0), 1, 4 dup(0), 2 dup(1), 0, 6 dup(1), 0, 1
data.extend([0]*5) # 5个0
data.append(1) # 1
data.extend([0]*4) # 4个0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*6) # 6个1
data.append(0) # 0
data.append(1) # 1
# dd 0, 2 dup(1), 0, 2 dup(1), 0, 0Bh dup(1), 0, 2 dup(1)
data.append(0) # 0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*2) # 2个1
data.append(0) # 0
data.extend([1]*0x0B) # 0Bh = 11个1
data.append(0) # 0
data.extend([1]*2) # 2个1
# dd 0Bh dup(0), 4, 0, 1Eh dup(1), 10h dup(0), 3, 2 dup(1)
data.extend([0]*0x0B) # 0Bh = 11个0
data.append(4) # 4
data.append(0) # 0
data.extend([1]*0x1E) # 1Eh = 30个1
data.extend([0]*0x10) # 10h = 16个0
data.append(3) # 3
data.extend([1]*2) # 2个1
# dd 0Eh dup(0), 1, 0, 3 dup(1), 0Ah dup(0), 3 dup(1), 0
data.extend([0]*0x0E) # 0Eh = 14个0
data.append(1) # 1
data.append(0) # 0
data.extend([1]*3) # 3个1
data.extend([0]*0x0A) # 0Ah = 10个0
data.extend([1]*3) # 3个1
data.append(0) # 0
# dd 1, 0Bh dup(0), 1, 2 dup(0), 1, 8 dup(0), 2 dup(1), 0
data.append(1) # 1
data.extend([0]*0x0B) # 0Bh = 11个0
data.append(1) # 1
data.extend([0]*2) # 2个0
data.append(1) # 1
data.extend([0]*8) # 8个0
data.extend([1]*2) # 2个1
data.append(0) # 0
# dd 1, 2 dup(0), 1, 9 dup(0), 3 dup(1), 2 dup(0), 1, 0Eh dup(0)
data.append(1) # 1
data.extend([0]*2) # 2个0
data.append(1) # 1
data.extend([0]*9) # 9个0
data.extend([1]*3) # 3个1
data.extend([0]*2) # 2个0
data.append(1) # 1
data.extend([0]*0x0E) # 0Eh = 14个0
# dd 1, 0Eh dup(0), 4 dup(1), 0Eh dup(0), 1, 0Eh dup(0)
data.append(1) # 1
data.extend([0]*0x0E) # 0Eh = 14个0
data.extend([1]*4) # 4个1
data.extend([0]*0x0E) # 0Eh = 14个0
data.append(1) # 1
data.extend([0]*0x0E) # 0Eh = 14个0
# dd 1, 0Eh dup(0), 1, 0Eh dup(0), 4 dup(1), 0Eh dup(0)
data.append(1) # 1
data.extend([0]*0x0E) # 0Eh = 14个0
data.append(1) # 1
data.extend([0]*0x0E) # 0Eh = 14个0
data.extend([1]*4) # 4个1
data.extend([0]*0x0E) # 0Eh = 14个0
# dd 1, 0Eh dup(0), 4, 0
data.append(1) # 1
data.extend([0]*0x0E) # 0Eh = 14个0
data.append(4) # 4
data.append(0) # 0
# 转换为15列的二维数组
rows = 675 // 15
array_2d = []
for i in range(rows):
start_idx = i * 15
end_idx = min(start_idx + 15, len(data))
row = data[start_idx:end_idx]
array_2d.append(row)
nums_df=pd.DataFrame(array_2d)
print(nums_df)
index4=[i for i, x in enumerate(data) if x == 4]
index3=[i for i, x in enumerate(data) if x == 3]
print(index4)
print(index3)
flag='ddsssddddsssdss'+'dddddsssddddsssaassssddds'+'ddssddwddssssssdddssssdddss'
md5_hash = hashlib.md5(flag.encode()).hexdigest()
print(f"MD5加密结果: {md5_hash}")
总结
对于逆向中的算法分析题目，有一些基本套路，总结如下：
（1）拿到附件文件先分析是Linux ELF文件还是Windows PE文件，32位还是64位
（2）尝试直接运行，看看有没有提示信息，提示信息往往可以作为定位关键代码的依据
（3）使用IDA静态分析，重点分析从输入到输出的一系列流程，这部分算法花样众多，需要具体问题具体分析
（4）如果需要绕过某些保护措施，则可结合Linux下的GDB和Windows下的OD调试工具绕过
（5）涉及变量较多的时候，用纸笔记录下关键变量的值和关键函数的用途是一个不错的方法
