首页
论坛
课程
招聘
【2021 KCTF 春季赛】寻回宝剑设计思路
2021-3-26 00:45 2220

【2021 KCTF 春季赛】寻回宝剑设计思路

2021-3-26 00:45
2220

基本信息

团队名称

崇文路大专

队长ID

古月浪子

参赛题目

寻回宝剑

题目答案

见“flag.txt”

设计思路

程序本体

源码见“题目源码/KCTF/main.cpp”

 

题目设计了一个巧妙的数学问题,既考察了各位选手的代码审计能力,又对信息收集能力与编程解题能力有一定的要求

 

首先程序会问36乘49等于多少,这是对题目算法内容的一种暗示:36×49=42×42

 

接着程序会读取输入,输入不允许出现0-9、A-Z、"+-*/%="以外的其他字符

 

然后程序会检查输入的长度是否为84,如果满足则把输入的字符两两一组以四十二进制的方式解析成42个整数,存放在数组里,其中这42个整数必须是按照严格递增的顺序被输入

 

接下来,用一个42×42的二维数组来抽象一个42×42个格子的棋盘,然后将该二维数组一维化,将输入的整数数组中的每个整数当作下标,将对应下标的元素设置为true(两位的四十二进制刚好不会超过棋盘的大小)

 

若某数组元素为true,则代表棋盘中该元素对应的格子里放了一颗棋子,反之则没有放任何东西

 

接下来检查,是否每一行、每一列均只有一颗棋子(即:同一行/列中不能有多颗棋子,因为只可以放42颗棋子,所以刚好可以每行每列放一个)

 

我规定某两颗棋子的连线称作它们的相对偏移线段(比如:第一行第一列的棋子和第二行第二列的棋子的相对偏移线段是一条长度为根号二、斜率为负一的线段),若两条相对偏移线段的长度和斜率均相等,则称它们相等

 

后面的代码是检验是否任意两颗棋子之间的相对偏移线段均不相等(注:相对偏移线段没有“方向”这个概念,也就是说,“棋子A与棋子B的相对偏移线段”和“棋子B与棋子A的相对偏移线段”视作同一条相对偏移线段)

 

若检验通过,则判断输入的开头14个字符是否与指定的字符串相等,换句话说我指定了棋盘上前7颗棋子的位置(按从左到右、从上到下的顺序)

 

若检验全通过,则输出成功,否则输出错误

 

程序采用Release x64模式编译,所用编译器为Visual Studio 2019可选安装的LLVM - clang-cl(版本为10.0),设置了生成调试信息:否、优化:已禁用、启用内部函数:否、优选大小或速度:均不,编译环境为Windows10 2004

 

由于题目要求不允许使用第三方壳或VM,我认为ollvm或许会被认定为第三方,因此没有采用ollvm方式编译,题目难度稍有降低

原创混淆器

源码:GitHub

 

本次比赛出题使用了我自己开发的“COP”混淆器

 

COP可以打开并解析一个PE文件,针对32/64位分别进行处理

 

COP要求所给文件必须具有.text段、.reloc段,且不含有花指令

 

COP使用Capstone解析出程序文件的所有汇编指令,将指令进行混淆,并且随机打乱,膨胀后的指令无法塞进原.text段,因此将多余的部分放入新的.cop段中

 

顺序被完全打乱的指令需要用某种方式连接它们,让它们顺序执行,我将非跳转指令用“call+pop+add/xor+push+ret”的方式连接,将跳转指令进行了不同程度的变形

 

此外,COP还将程序所有基于相对偏移的指令进行了修复,通过重定位表将所有基于绝对地址的命令进行了修复,对64位程序的基于rip寻址的指令进行了修复

 

COP自行维护了一个独立的重定位表,混淆后仍可以开启地址随机化

 

为了提高混淆强度,对64位程序还将清空其.pdata段的内容

 

COP还支持嵌套混淆(简称套娃),进一步提高混淆强度

 

用户可以选择保留.reloc段或者去除,去除以后会进一步提高混淆强度,但不支持继续嵌套混淆,且会关闭地址随机化

 

我使用COP将编译出的程序进行了2次混淆,得到最终附件,考察了各位选手编写脚本的能力

解题思路

拿到的附件使用IDA打开,发现有非常多的重复的代码,且动态调试的时候有效指令出现的频率极低,因此可以考虑使用脚本对文件进行初步处理

 

1

 

先拿到call后面的pop rax的地址,提取xor的第二个操作数,即可计算出下一条指令的位置

 

计算相对偏移,将第一个push rax改成jmp到下一条指令

 

这里比较方便的是使用IDAPython编写脚本,因为IDA提供了很多有用的API

 

如此操作完以后,可以发现还嵌套了一层混淆

 

2

 

这里可以采用的方法很多,我采用的顺序遍历+特征匹配的方式定位被jmp连起来的代码碎块,若一系列遍历下去发现指令与模式匹配,则认为它是一个混淆指令块,取pop rax的地址和add的第二个操作数(内层是add,外层是xor),计算下一条指令的位置,并把匹配的指令序列的第一个指令改成jmp,可以把代码还原成由jmp连接起来的零碎指令

 

3

 

再用IDA打开去混淆后的程序,从字符串的交叉引用定位主函数

 

4

 

但是可以看到可能因为我的去混淆代码写得不是很好,IDA的F5插件仍然无能为力,这里可以考虑使用Capstone或者IDA自带的API修一下代码,或许能提高反编译的质量和准确率

 

在去混淆到这种程度后,一个好办法是动静结合,再根据F5的部分残破的语句,可以大致还原整个算法(因为没有开编译器优化,因此可读性比较强)

 

拿到算法后,可以选择写代码跑出结果,也可以上网进行信息收集

 

我们不难得知,前人已经对该问题进行过研究了,人们把它叫做科斯塔斯阵列(Costas Arrays)

 

参考链接:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.8983&rep=rep1&type=pdf

 

已经有许多高效的算法被前人发明,我们通过模仿与借鉴这些代码就能求出最终的结果

 

最后,将求出的结果转化成42个整数,以四十二进制的方式转换后即是最终flag


2022 KCTF春季赛【最佳人气奖】火热评选中!快来投票吧~

最后于 2021-5-19 14:27 被kanxue编辑 ,原因:
上传的附件:
收藏
点赞0
打赏
分享
最新回复 (2)
雪    币: 1038
活跃值: 活跃值 (9862)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 活跃值 8 2021-3-26 11:17
2
0
题目收到,评委讨论一下,近期联系你沟通,可能一些地方要调整。
游客
登录 | 注册 方可回帖
返回