KCTF2022 第二题 盗贼作乱 分析

1天前 116

丢进 IDA 逆几个函数，可以发现程序整体上实现了一套大数运算，包括 62 进制字符串转大数、比大小、+-*/%&|^、左移等等。
我们需要提供两个数字，然后总体的逻辑看起来不太复杂，在若干次循环中，只要完成共 10 次 a==part1 或 b==part2，就成功。

挑战可以化为：

也就是

对这个式子，要找到两种 input，对应我们输入的两个数字，使得 k 一共有 10 个解 （$k<=0x200000$）

这件事情结合一点有限域知识，就感觉不太可能，一个 input 按理最多一个解，估计是有诈。

这里命名的所有变量基本都是全局的。大部分运算函数中，除了实现原本的运算功能，还都有类似后门的功能，在一定条件下，会修改 ab 的值。在乘除法里甚至还会修改 modulus。

但是仔细分析，由于对 ab 经常出现直接赋值，很多后门都是可以忽略的，比如 main 函数对 a 的 set sub compare，set 无后门，sub 仅改 b，compare 的后门不影响比较结果。b 同理（add 仅改 a），所以如果只考虑走进两个 success 的分支条件，不需要考虑其他关于 ab 的后门，所以接下来看看关于 modulus 的后门。

在两个 success 的分支里面会调用乘除法，涉及 modulus 的修改，关注一下 modulus 的规则就可以了。

其实这里 ab 也都是固定的，a=4，b=32，就是要求 modulus.data[32] == 32，才会进入这个分支。但是 modulus 是 0x8ac7230489e80000，不存在 0x20 这个值，这里按理是不会进去的。

也就是说，所有的后门好像都没啥用，一度没有思路，然后还想过 +1 -1 会不会发生溢出。然后确认了一下程序实现的大数是 256 位无符号的，结构体是

然后猛然回过神，前面说的要求 modulus.data[32] == 32 越界了！赶紧看看全局变量的布局，原来这里判断的是 loop == 32。也就是说在第 32 次循环走进乘除法，会进入改 modulus 的分支。

改 modulus 的位置其实也是确定的 modulus.data[36] += 4 ，这其实又越界到了 success_cnt 上。那么我们只需要让两部分输入都在第 32 轮走进来，本身成功了两次，后门又做了两次 += 4，总共刚好十次！

所以回到前面给的公式，只需要令 k = 32 解一下就行了：

输出是

转换一下格式，ZSxZerX4xb40-jyvP7x12lI7，成功！

[2022冬季班]《安卓高级研修班(网课)》月薪三万班招生中～

最后于 1天前 被tkmk编辑 ，原因： 128->256