-
-
KCTF2022 第二题 盗贼作乱 分析
-
2022-11-16 16:30
-
丢进 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 位无符号的，结构体是
1 2 3 4 | struct BigInt { int length; uint8 data[32];} |
然后猛然回过神，前面说的要求 modulus.data[32] == 32 越界了！赶紧看看全局变量的布局，原来这里判断的是 loop == 32。也就是说在第 32 次循环走进乘除法，会进入改 modulus 的分支。
改 modulus 的位置其实也是确定的 modulus.data[36] += 4 ，这其实又越界到了 success_cnt 上。那么我们只需要让两部分输入都在第 32 轮走进来，本身成功了两次，后门又做了两次 += 4，总共刚好十次！
所以回到前面给的公式，只需要令 k = 32 解一下就行了：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def encode(n): charset = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz' result = [] while n > 0: r = n % 62 n //= 62 result.append(charset[r]) return ''.join(result) or '0'a = pow(31, -1, 10**19)b = pow(-31, -1, 10**19)print(a, b)print(encode(a))print(encode(b)) |
输出是
1 2 3 | 3870967741935483871 6129032258064516129ZSxZerX4xb4jyvP7x12lI7 |
转换一下格式，ZSxZerX4xb40-jyvP7x12lI7，成功！
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
