首页
社区
课程
招聘
KCTF2022 第二题 盗贼作乱 分析
2022-11-16 16:30 8099

KCTF2022 第二题 盗贼作乱 分析

2022-11-16 16:30
8099

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

转换一下格式,ZSxZerX4xb40-jyvP7x12lI7,成功!
图片描述


[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界

最后于 2022-11-16 16:32 被tkmk编辑 ,原因: 128->256
收藏
点赞2
打赏
分享
最新回复 (1)
雪    币: 6051
活跃值: (1441)
能力值: ( LV15,RANK:1473 )
在线值:
发帖
回帖
粉丝
lelfei 23 2022-11-18 15:43
2
0
太厉害了,3个小时就被肢解得清清楚楚,佩服
游客
登录 | 注册 方可回帖
返回