ACTF2025 unstoppable 题解
SGSG 发表于 浙江 CTF 180浏览 · 2025-04-28 05:41

主函数

进来先看主函数,输入有2703个,而且似乎有意对输入的范围做了检测,使其限定在0~5004
input先进入sub_555555559560这个函数,这个函数里面乱七八糟的一堆指针操作乱飞,下面那个重命名为get_arg2的也是一样,让人非常怀疑这个v26和v22是不是结构体(图片里是已经修复过结构体定义的,懒得重新从原附件开始写了),所以动调输入一些数检查下
每次输入后给v22指向的地址命名标记
可以看到确实是结构体,而且我们的输入也被存在了每个结构体中,另一个明显的特征是结构体里有大量互相指的指针,算法学的好的已经知道这是什么了,但万一我没打过acm怎么办呢,这里可以画图把每个结构体和他指向的对象连起来
这一眼二叉搜索树了,也就是我们的输入被扔进了一颗二叉搜索树里,然后v22,v26都是相关的树节点类型,可以怀疑是根节点之类的,在下面的while循环中也有使用,二叉搜索树的重要性质就是先序遍历就是有序数列,合理怀疑这是在对我们的输入进行排序,我们把输入的组数patch少一点,到while处的逻辑中验证猜想 另外注意到上面的循环会对我们的输入去重,如果输入的数已经在树中出现过就会把输入置0再插入树中

第二处循环

再get_Input处下断点,可以发现v18确实是按从小到大取出的,但这时发现程序会卡死,经过二分法下断点发现是sub_555555559890这个函数导致了卡死,但巧合的是输入1不会卡死,输入2会,因为输入是排序的,经过多次尝试发现1,3,5均不会卡死(试出来几个不会卡死的方便动调下面的函数),再来看这个函数的逻辑,他接受v17作为传参,而v17在前一个函数进行初始化,经检查v17是一个指针数组,上面那个函数是负责把chiperlist中的数据刷入v17中,发现在取偏移时是按30的倍数取的,检查发现chiperlist正好是5005*30组数据,和我们输入的限制对应 再看这个a是怎么出来的,sub_55555555A5B0的第一个参数是一个静态未初始化的全局量,第二个参数是我们取出的输入,我们查交叉引用看这个全局量哪来的
可以看到是一个质数表,而且长度正好也是5005,结合动调确认就是查表获得质数表对应下标的数,那也就是说a和b都是查表查出来的,我们的输入其实是2703个合法下标用于在两次查表中获取对应的结果,如果输入不对则会在获取b的时候卡死 在下面那个qpow就很清晰了,点进去直接能看出来是快速幂算法(看不出来我也没办法,和源码长得几乎完全一样了),下面那个函数是调用mod API进行取模操作 总的来说这块就是把输入从小到大取出,分别进行两次查表获取$a,b$,然后计算$a^b$并累乘到v25上

哈希

循环结束后有一个flatten过的函数,用d810解开后直接把整个函数体扔给ai识别,识别为MurmurHash3_x64_128哈希算法,不过他具体怎么样我们不关心,只要知道他会把v25作为种子,把congratulations的哈希值存入hashdest这个buffer即可,再看下面的输出格式,也就是flag主体其实就是这个hash

如何获取种子

种子是累乘得到的,a就是查质数,难点在于获取b,可以去赌他获取b的算法在每次执行都是独立的,可以尝试输入(1,3,5),(3,5),(1,5),(1,3)做尝试,发现确实是独立的,那么考虑用frida主动调用去爆破合法的2703组回显,然后再主动调用他实现的qpow和mod函数结合素数表算出种子,最后动调把种子patch进hash函数获取flag

爆破脚本

要注意的是使用frida爆破每次要重新起新进程,因为如果输入错了程序就会卡住,而主动调用是阻塞式的,然后每次起进程设置一个时限来分辨是正确输入还是卡死了,还要主动杀掉拉起的进程(不然跑5005轮马上cpu就爆了,frida不会主动杀掉自己拉起来的进程),至于这里为什么一次调用设10s时限就要问出题人的图灵机怎么写的这么卡了,可以把5005切成多片跑,以及做好要跑大半天的准备

调用qpow执行累乘

为了防止出题人实现的mod抄错,所以干脆也用frida

脚本里的blist就是b的取值,是[[value,i]....]的形式,有两千多条就不放出来了 最后跑完拿到种子


获取flag

然后断点打在hash进入前,把v25修掉就行,记得把前面的输入循环整个去掉,不然又在while里卡死了
flag直接就输出来了


0 条评论
某人
表情
可输入 255