首页
论坛
课程
招聘
虽然没看懂题,但还是跑出来了
2021-11-24 23:55 7716

虽然没看懂题,但还是跑出来了

xym 活跃值
3
2021-11-24 23:55
7716

老实说一看到是安卓题我还是挺怵的,因为算法一般都是arm类型的so文件,而我一直都没有一个合适的arm调试环境。
不管怎么样,先上手用jadx查看一下吧。jadx查看
果然,界面直接导入了kctf2021这个动态库并声明了stringFromJNI这个native函数,并且直接用它对输入进行了判断。
用IDA打开libkctf2021.so,定位到目标函数 jadx查看
看来关键算法就在sub_39998这个函数里了。在ida里看到这个函数这么清晰明白的显示出来,我的第一感觉是哪里又藏着hook会修改这个函数,于是先简单检查了一下,确定so没有预加载可疑的函数。
jadx查看
关键函数逻辑很清楚,当输入字符串长度为14时,初始化一个表(这个表对我解题并没有用,下面略过不说),然后将输入每4bit转成一个dword,变成一个长为28的数组。
然后调用sub_39658处理一个固定字符串,根据字符串的首行搜索可以得知是这是boost的一个序列化。为了弄清楚反序列化后的对象是什么东西,我这里有两个选择:1是下载boost开发库开发实验一下,2是找个东西模拟运行一下。
因为unidbg比boost更快下载完,因此我最终模拟运行了这个反序列化函数并打印了对象的内存 jadx查看
序列化后的对象v13继续使用sub_39910进行处理 jadx查看
首次看这个函数并没有看懂,只能推断他应该是一个很多层的递归处理,并且会根据输入去反序列化其他16个序列化对象中的一个。
jadx查看
结合sub_39614函数可以分析出v13这个对象应该是一个比较大的类似二叉树一样的结构,具有非常多的节点,但是每个节点非常简单,只占16个字节内存。这里发现了一个比较复杂的函数sub_39570(但是这个函数同样对我解题并没有用,下面略过不说……因为我最后都没看懂这个函数)。
最后看一下本题check的逻辑:结尾虽然有一堆的判断跳转,实际归纳起来就是判断最终的v13是不是只有3个特定节点了。
因此梳理一下这道题的思路:作者定制了一棵非常大的二叉树,然后用sub_39910把拆为4bit后的28个输入转为16棵小树中的一颗并插入到二叉树值为122的对应节点中,形成一棵不带122节点的树。然后使用sub_39614对这个树的所有节点进行删减,如果最后只剩3个节点就算成功(3个节点应该是这道题理论上能删减到的最少节点吧)。
那么这道题的破题之处就在于,因为用户输入选择的分支必然是散布到整棵树的不同部位,那对其中某分支能独自占据的最大分支来说,其删减结果其实都与其他输入无关。因此用户的每个输入相对其他输入很可能都是独立的,整个大题可以拆分成为28道相同的小题,而每道小题的解合起来就是整个大题的解。因此我们的目标转换为了在保持27个输入不变时,求剩下那个输入能使最终节点数最少的值。
因为unidbg在运行UXTB16指令时会报错,因此模拟执行的办法在这里就中断了。
jadx查看
jadx查看
幸好整个程序可以转为等效的C代码,通过查询arm汇编指令集,把clz和UXTB16转为相应的函数或代码,实现了每个输入的暴力破解。实际代码中分成两次,第一次是所有的低4bit,第二次是所有的高4bit(因为可见字符最高位为0,所以其实只有3bit),实际使用的指标也不是节点数最少,而是二叉树层数最少(从结果看应该是等效的)。
jadx查看


[注意] 欢迎加入看雪团队!base上海,招聘CTF安全工程师,将兴趣和工作融合在一起!看雪20年安全圈的口碑,助你快速成长!

上传的附件:
收藏
点赞2
打赏
分享
最新回复 (4)
雪    币: 4812
活跃值: 活跃值 (2629)
能力值: ( LV10,RANK:160 )
在线值:
发帖
回帖
粉丝
sunfishi 活跃值 3 2021-11-25 13:57
2
0
好思路,另辟蹊径。学到了。
雪    币: 213
活跃值: 活跃值 (694)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
kakasasa 活跃值 2021-11-26 18:32
3
0
原题文件放上来就更好了,不用去找
雪    币: 1631
活跃值: 活跃值 (477)
能力值: ( LV4,RANK:45 )
在线值:
发帖
回帖
粉丝
wx_Dispa1r 活跃值 2021-11-29 10:31
4
0
好棒!学到了
雪    币: 164
活跃值: 活跃值 (1585)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
ookkaa 活跃值 2021-11-29 12:03
5
0
好思路,另辟蹊径。学到了。
游客
登录 | 注册 方可回帖
返回