上周末独自尝试了阿里云2024的CTF，只做出了Reverse的第一题，记录一下。

题目

是一个cmd exe可执行文件，需要input一个字符串。

解题工具

解题需要用到的工具包括

x64dbg：Windows平台的程序动态调试工具
IDA64：可执行文件、动态链接库的程序静态分析工具
通义千问：用于分析反编译生成的伪代码，并根据逻辑生成解题的脚本

解题记录

首先使用x64dbg，执行程序到等待输入处。打开字符串常量表，可以看到和flag相关的内容：aliyunctf{和Right、Wrong。

追踪一下用到aliyunctf{的代码处，发现这里主要是判定输入的内容是否以aliyunctf{开始并以}结束。

打开IDA64，找到引用到该常量的代码，如下图所示：

此时把代码拿去问问通义千问，程序逻辑基本清晰，主要分解为以下几个逻辑：

判断字符串长度是否为29
判定除了前缀和后缀的每个字符是否在0~8之间（48是字符串0的ASCii码），说明这是个数字，减去前缀和后缀11位，这是个18位的整数。
判定这个18位整数是否满足一些约束条件。
设相邻的两位为a和b，需要满足9a+b和9b+a的值在指定范围内，并且34个值不重复。（由代码if ( dword_149994G4[u17] != 1 )看出，这里可以看到这里的内容是个数组，并且其中的元素有80个（9a+b的最大值），其中有34个1（18个内容，共有17对相邻数字，刚好是34个））

以上条件需要全部满足，否则输出Wrong。

把内存中的这个bitmap拿出来

值为1的索引列表如下：

json

1	[2, 5, 8, 12, 13, 14, 17, 18, 21, 24, 25, 28, 29, 31, 35, 37, 39, 42, 45, 46, 51, 53, 56, 58, 59, 62, 65, 71, 72, 73, 75, 77, 78, 79]

通过输入一串满足前两个条件的随机数字，在x64dbg在if语句中打断点，观察内存和寄存器，可以进一步得出这串18位数字的约束条件。

第2位大于第3位
第4位小于第5位
第1位和第9位相同
第16位和第12位相同
第6位小于第11位
第14位大于第4位
第8位小于等于第5位
第15位是7
第18位是4

这个数字让人来找肯定是不行的，约束条件过多，只能写程序来找。

不使用框架，考虑裸解的思路主要是dfs打表+减枝优化。于是梳理一下思路：由于最后一位是固定的，所以从最后一位开始向前进行深度优先搜索，前面的数字基于后面的数字作为约束条件，减少判断条件。

写一段promote给通义千问：

Code

写一串python代码，查找满足条件的18位以下10进制数字。该数字需要满足以下条件（位数是10进制的位数从左边开始为1）:
1. 第2位大于第3位
2. 第4位小于第5位
3. 第1位和第9位相同
4. 第16位和第12位相同
5. 第6位小于第11位
6. 第14位大于第4位
7. 第8位小于等于第5位
8. 第15位是7
9. 第18位是4
10. 每一位都在0-8之间
11. 相邻的两位满足其中一位的9倍加上另一位的和（求两次，设一位为a，另一位为b，则需要计算9a+b和9b+a）出现在[2, 5, 8, 12, 13, 14, 17, 18, 21, 24, 25, 28, 29, 31, 35, 37, 39, 42, 45, 46, 51, 53, 56, 58, 59, 62, 65, 71, 72, 73, 75, 77, 78, 79]范围之间（离散的），并且18位数字的34个和中不出现重复。
由于第15位和第18位是确定的，所以可以写一个递归，从第18位（最后一位）开始深度优先遍历。具体逻辑为：将确定的15和18位作为初始状态（状态可以用一个长度为18的列表来表示），从第18位开始，求出满足条件的第17位（要求两个和在上述列表中，并且没有被占用过），作为新的状态，并记录下两个占用过的和，传入下次递归中。从17位递归继续寻找满足条件的第16位（此时需要考虑第15位已存在），若找不到则回溯，尝试17位的另一个选择，以此类推。直到所有位数都填上，就可以输出最终数字了。

通义千问生成的代码并没有考虑剪枝，而且还有点bug

python

根据您的描述，这是一个复杂的约束问题，需要使用回溯算法解决。但是由于问题的复杂性以及Python实现的限制（如运行时间、内存消耗等），直接在这里编写完整代码可能不太实际。下面是一个简化的框架示例，您可以基于此进行扩展和优化：

def is_valid(num, pos, used_sums):
    # 判断num是否满足各个条件
    # 这里仅作演示，您需要根据题目条件完善这部分逻辑
    conditions = [
        num[1] > num[2],
        num[3] < num[4],
        num[0] == num[8],
        num[15] == num[11],
        num[5] < num[10],
        num[13] > num[3],
        num[7] <= num[4],
        num[14] == 7,
        num[17] == 4,
        all(0 <= digit <= 8 for digit in num),
        (9 * num[pos - 1] + num[pos] in allowed_sums and 
         9 * num[pos] + num[pos - 1] in allowed_sums) and
         (9 * num[pos - 1] + num[pos], 9 * num[pos] + num[pos - 1]) not in used_sums
    ]
    
    return all(conditions)

allowed_sums = [2, 5, 8, 12, 13, 14, 17, 18, 21, 24, 25, 28, 29, 31, 35, 37, 39, 42, 45, 46, 51, 53, 56, 58, 59, 62, 65, 71, 72, 73, 75, 77, 78, 79]
num = [None] * 18
num[14], num[17] = 7, 4

def backtrack(pos=-1, used_sums=set()):
    if pos == -1:
        pos = 17

    if pos == -2:
        # 所有位置已填充，检查结果
        if is_valid(num, pos, used_sums):
            print(''.join(str(digit) for digit in num))
        return

    for digit in range(9):
        num[pos] = digit
        if pos != 17:  # 对于非最后一位，检查相邻两位的和
            if (9 * num[pos - 1] + num[pos], 9 * num[pos] + num[pos - 1]) in used_sums:
                continue
            used_sums.update((9 * num[pos - 1] + num[pos], 9 * num[pos] + num[pos - 1]))
        
        if pos >= 15 and num[pos] == 7:  # 跳过第15位为7的情况（已经固定）
            continue
        if pos == 1 and num[pos] != num[8]:  # 第1位和第9位必须相同
            continue

        backtrack(pos - 1, used_sums.copy())

backtrack()

请注意，这个简化的框架并没有完全实现所有条件的检查，并且对于大型数据集可能会非常耗时或无法找到解。针对这个问题，可能需要更高级的算法策略或者利用并行计算等技术提高效率。此外，因为允许的和值范围较大，且不允许重复，这大大增加了搜索空间的复杂性，可能导致算法难以在合理时间内找到解。

于是我们改优化一下，最终的解题代码是：

python

allowed_sums = set([2, 5, 8, 12, 13, 14, 17, 18, 21, 24, 25, 28, 29, 31, 35, 37, 39, 42, 45, 46, 51, 53, 56, 58, 59, 62, 65, 71, 72, 73, 75, 77, 78, 79])
nums = [None] * 18

def bit_allow_range(bit, num):
    if bit == 0:
        return range(num[8], num[8]+1)
    elif bit == 1:
        return range(num[2]+1, 9)
    elif bit == 3:
        return range(min(num[4], num[13]))
    elif bit == 4:
        return range(num[7], 9)
    elif bit == 5:
        return range(num[10])
    elif bit == 11:
        return range(num[15], num[15]+1)
    elif bit == 14:
        return range(7, 8)
    elif bit == 17:
        return range(4, 5)
    else:
        return range(9)

def backtrack(num, pos=17, used_sums=set()):
    if pos == -1:
        # 所有位置已填充，检查结果
        print(''.join(str(i) for i in num))
        return

    for digit in bit_allow_range(pos, num):
        num[pos] = digit
        sub_used_sums = used_sums.copy()
        if pos != 17:  # 对于非最后一位，检查相邻两位的和
            sum1 = 9 * num[pos + 1] + num[pos]
            sum2 = 9 * num[pos] + num[pos + 1]
            # 两个结果不和已有的结果重复，且都在范围内
            if sum1 in used_sums or sum2 in used_sums or \
              sum1 not in allowed_sums or sum2 not in allowed_sums:
                num[pos] = None
                continue
            sub_used_sums.add(sum1)
            sub_used_sums.add(sum2)
            # 向前填充搜索
        backtrack(num, pos - 1, sub_used_sums)

backtrack(nums)

最终计算出的18位数字只有一个

085134620568327814

题解为

aliyunctf{085134620568327814}

Bingo！