ACTF2025 unstoppable 题解教学文档

ACTF2025 unstoppable 题解教学文档 题目概述 这是一道关于二叉搜索树和密码学结合的逆向工程题目，要求通过分析程序逻辑，找到正确的输入序列，最终计算出正确的哈希值作为flag。 主函数分析 输入处理 程序接受2703个输入数字 输入范围限制在0~5004之间 输入首先进入 sub_555555559560 函数进行处理 输入验证 程序对输入进行去重处理：如果输入的数字已经在树中出现过，会将该输入置0再插入树中 输入被存储在二叉搜索树结构中 二叉搜索树结构 结构体特征 程序使用结构体存储输入数据 结构体包含大量互相指向的指针 通过动态调试可以确认这是一个二叉搜索树(BST)结构 排序验证 程序对输入进行排序处理（二叉搜索树的中序遍历就是有序数列） 通过patch减少输入数量可以验证排序逻辑 核心算法分析 查表操作 程序使用两个查表函数： sub_55555555A5B0 ：从静态全局量中查表（实际上是质数表） 另一个查表函数从 chiperlist 中获取数据（5005×30的数组） 数学运算 程序对排序后的输入依次处理： 通过第一个查表函数获取值 a （质数表中对应下标的数） 通过第二个查表函数获取值 b 计算 a^b （使用快速幂算法 qpow ） 将结果累乘到变量 v25 上 哈希计算 使用 MurmurHash3_x64_128 算法 以累乘结果 v25 作为种子 对字符串"congratulations"进行哈希计算 最终哈希值就是flag 解题步骤 1. 爆破合法输入 发现 b 的获取算法在每次执行是独立的 使用Frida进行爆破： 每次启动新进程（因为错误输入会导致程序卡死） 设置超时限制（建议10秒）区分正确输入和卡死 及时杀掉拉起的进程防止CPU过载 可以将5005个可能的输入分成多片并行处理 2. 计算种子 爆破得到合法的2703组输入后 使用Frida主动调用程序实现的 qpow 和 mod 函数 结合素数表计算出最终的种子值 v25 3. 获取flag 在哈希函数调用前设置断点 手动修改 v25 的值为计算得到的种子 跳过前面的输入循环（避免卡死） 程序会直接输出flag 关键点总结 输入处理 ：识别二叉搜索树结构和对输入的排序处理 查表操作 ：理解两个查表函数的用途和数据来源 数学运算 ：快速幂算法和累乘计算 哈希算法 ：识别并利用MurmurHash3算法 爆破策略 ：使用Frida进行高效爆破，注意进程管理和超时设置 种子计算 ：确保使用程序自身的实现避免兼容性问题 flag获取 ：通过动态调试直接修改内存值获取结果 注意事项 爆破过程可能需要较长时间（半天左右） 确保正确杀死Frida拉起的进程，防止系统资源耗尽 验证查表函数的实现是否正确，避免计算错误 动态调试时注意跳过会导致卡死的代码段