2024 网鼎杯玄武组Reverse1 题解

金野喵君

比赛结束后一小时才做出来这道题，很遗憾。
首先将题目main文件拖入IDA中分析，分析main函数逻辑，该程序具有插入字符串（最多19个字符，最多进行15次插入）和搜索（也是最多进行15次）两个功能。

main函数中最先调用preprocessing函数，将本地的"flag.txt"文件读入到内存中，地址0x0064040处存储的就是flag，所以我们需要想办法读到这个内存地址。

接着分析负责插入功能的insert函数，发现插入用户输入的字符串的过程实质是构造一棵二叉树，且要求左子节点的值比右子节点的值大。


分析search函数，发现是遍历二叉树的过程。

我们可以发现search后，程序会puts打印找到的字符串。

全局变量a在内存中的地址为0x4040。当v6 = 0x4000时，&a + 24 * v6 等于0x0064040，也就是flag处。要想v6为0x4000需要输入一组数据，要求数值逐渐减小，并且小于0x6D7564206D612069，只有这样insert函数中的变量a1才会以2为底的指数增长，直到达到0x2000。我们可以将问题转化为，需要构造一棵只有左孩子节点的二叉树。
只要输入13次数据，就可以让0x2000处的节点填进数据，这样就可以和0x4000处的flag连到一起（作为左孩子节点）。
insert函数中，利用进程id和系统时间来生成随机数，并在用户每次插入字符串使用随机数进行&操作，这会导致可能随机发生树节点发生换位。这里挺阴间的，你即使知道正确的插入数据的序列，也需要一定的运气才能获得flag（每次输入时随机数计算都不触发换位的前提下，13轮输入，说实在得是欧皇才能快速成功）。
为了方便验证序列是正确的，我将a1>1的判断跳转修改为jmp，直接跳过换位操作。patch这部分代码只是避开运气的部分（强行欧皇），不影响程序的整体逻辑。


在本地运行修改后的main文件，说明一下这里测试的如“00000008aaaaaaaaaaa”在调试时，手动修改为“\x00\x00\x00\x00\x00\x00\x00\x5Faaaaaaaaaaa”（因为无法输入不可打印的ascii字符），完成13轮输入后，查询“wd”，成功获取到flag。


贴一下解题脚本


main.rar (4.41 KB, 下载次数: 7)

2024-11-6 11:42 上传

点击文件名下载附件
下载积分: 吾爱币 -1 CB

jindaxia

还有一种可能，因为环境是在容器内运行的，所以 pid固定为1，srand(pid*time)  那么随机数种子就固定在了当前启动时间，
在seed固定的情况下，当前时间戳，单位是秒，可以预测每一位产生的随机数， 另外程序给了一个就算插入到右节点，还能纠正的机会，即发生交换（最后一个异或，会交换左右节点）
所以与其赌命让13次生成的随机数都比前一次小（几乎不可能），不如根据随机数的值（是否会交换），选择插入的值是要比前一次大，还是前一次小
所以为了预留足够的间距容纳 比前一次大，又比前前一次小的数，两次插入的数组必须有足够长的间距，

node结构体

[Asm] 纯文本查看 复制代码

struct  AAA
{
  char str_data[16];
  __int64 random_num;
};

l5808

这么快就发出来了，厉害啊

十一七

有没有可能，赛时打的是远程，你直接 patch 二进制没啥用

金野喵君

十一七 发表于 2024-11-6 10:29
有没有可能，赛时打的是远程，你直接 patch 二进制没啥用

patch只是为了手动测试一遍过，不patch的话要看运气，需要13次输入都不触发交换。需要一直循环跑脚本去试，如果是倒霉蛋不配得到flag。

曟AI

学习学历

jindaxia

金野喵君 发表于 2024-11-6 11:19
patch只是为了手动测试一遍过，不patch的话要看运气，需要13次输入都不触发交换。需要一直循环跑脚本去试 ...

打成功的概率是多少？ 13次都在左边？

Susenliu

感谢楼主分享

金野喵君

jindaxia 发表于 2024-11-8 15:50
还有一种可能，因为环境是在容器内运行的，所以 pid固定为1，srand(pid*time)  那么随机数种子就固定在了当 ...

太强了。确实，如果pid为1，可以依据容器的启动时间来预测随机数。如果平台给出的容器启动时间和该进程时间不一致（没有精确到秒一致），只需要枚举误差内的时间去试出真正的大小顺序就行了。只能说这题太恶心了，不容易想到。

金野喵君

jindaxia 发表于 2024-11-8 15:44
打成功的概率是多少？ 13次都在左边？

是的，13次子节点的随机数都比根节点的随机数大，概率还蛮小的