2020 KCTF秋季赛 | 第三题设计及解题思路

  • A+
所属分类:逆向工程

2020 KCTF秋季赛 | 第三题设计及解题思路


11月22日中午12点,第三题《重返地球》结束。14支战队用时1天,速战速决,结束本题的战斗。

2020 KCTF秋季赛 | 第三题设计及解题思路
  
本题围观人数1986人,T.O 战队率先攻击成功,获得一血加分!总排名上升至第13名。technictec 战队以465秒之差遗憾位列第二位。


2020 KCTF秋季赛 | 第三题设计及解题思路

接下来我们就一起来看看本题的设计思路和解析吧!



2020 KCTF秋季赛 | 第三题设计及解题思路
一.题目简介

破解出的信息似乎是在求救。难道刚才检测系统出错,地球上还有人幸存?你的手指在虚拟键盘上飞速敲击,反复确认信号的真实来源。


信号的确来自地球,还是在你所居住的那座城市。顿时,你心中重新燃起了希望的火光。难道是“他”?!


你刚开始思索该如何掩盖自己伪造邀请函登船的事实,又能有理有据地让“破晓”总指挥官相信自己,派人返航地球确认实情时,警报声再一次响起。


你幼小的心灵一天之内已经不起这样坐过山车一般的大起大落。但下一秒,你裂开了。你听到了自己的公民ID号……


“经系统检测,ID号为xxxxxxx的公民伪造虚假邀请函,未经允许私自登船,立即对该违规人员实施抓捕!立即对该违规人员实施抓捕!”大厅里,训练有素的士兵开始集结,一一排查仍滞留在大厅的人群。


三十六计走为上计,你镇定地以人群为掩护悄悄离开大厅,来到人迹罕至的紧急逃生舱准备先躲过这一阵的搜捕。


但不多久,你就警觉地听到外面的脚步声在不断向这里靠近!


看着一艘艘严阵以待的紧急逃生飞船,你的大脑开始飞速运转。现在继续留在“破晓”也解决不了任何问题,一旦被捕也不会有人相信一个偷溜上船的不法分子所说的话。


既然这样,不如就搏一搏,用紧急逃生飞船离开“破晓”,自己返回地球调查!

* 上下滑动查看


2020 KCTF秋季赛 | 第三题设计及解题思路
二.出题团队简介


2020 KCTF秋季赛 | 第三题设计及解题思路


2020 KCTF秋季赛 | 第三题设计及解题思路
三.设计思路


设计思路由作者 holing 提供





0x00 前言



最近刚好学习了racket这门语言,发现挺有意思的,尤其是通过Continuation Passing Style可以把racket程序转换成C。而且把racket程序CPS之后的可读性变得更差了,而函数式编程语言的逆向相对而言也非常少,于是便有了这道题目。函数式编程向来都以奇异为特点(相对于中规中矩的C/Java/Python),于是最适合的题目名称我认为是《异常信号》。




0x01 源代码



程序的逻辑很简单,就是一个标准的有限域的矩阵相乘。因为这道题目重点在于逆向racket而不在于算法,所以没有选择复杂的算法。racket源代码是chall.rkt。因为是一步一步从普通racket程序改的,所以我把每个步骤都commit了一次,详情可以看git log。

Python文件用于生成数据,即用来相乘的矩阵,output.txt是从Python生成的输出数据。parenthec.rkt和pc2c.rkt是转换所需要用到的工具,详情见论文:parenthec。因为生成的C源码存在一些需要自己定义的函数,比如说获取输入数据(不然会链接错误),所以modify.c实现了这些函数,用于直接复制到chall.c中。




0x02 逆向



因为程序是registerization过的,所以所有的racket函数的参数都由全局变量传递。而这些regster可以是一个结构体的指针,也可以是一个int整形。分析程序逻辑的关键点在于识别出continuation的结构体,以及其中的union结构,这样才能在apply-k的switch中分析原本的递归逻辑。
 
flag: KCTF{r4Ck3t_M4tr|X_W1tH_CP5_YqBHxjWX}


2020 KCTF秋季赛 | 第三题设计及解题思路
四.解析过程

本解析过程由作者 淡然他徒弟 提供

丢到IDA里面分析,发现会把输入的字符放到一个链表里,然后会进入一个类似虚拟机的指令分发流程。

第一个是统计链表长度。如果链表长度为37则进入下面流程。

然后是一大堆数据的初始化,生成了37+1个链表。然后进入指令分发流程,得出一个新的链表后,跟最后一个链表对比。

跟踪流程,得出流程为:
(mat[1][1]*x[1] + mat[1][2]*x[2] + … + mat[1][n]*x[n]) % MOD =mat[1][n+1]

乘法由加法完成,求模为减法实现,所以在指令分发流程里面。没有发现乘法跟除法的指令码。

总结为37元一次模方程求解,百度了下,发现有在ACM中考察过,编号为 poj2947。

使用高斯消元法进行求解,把系数扣下来以后,构建一个martix。因为链表为倒序,所以最后打印flag时候要倒序打印。

2020 KCTF秋季赛 | 第三题设计及解题思路

最后得出flag为:KCTF{r4Ck3t_M4tr|X_W1tH_CP5_YqBHxjWX}

2020 KCTF秋季赛 | 第三题设计及解题思路

现在第四题正在进行中,快来加入战局吧!

越早提交答案,得分越高哦!
立即扫码加入战斗!

2020 KCTF秋季赛 | 第三题设计及解题思路

华为全面屏智能电视、Xbox One X、JBL 无线蓝牙耳机等你来拿哦!



赛题回顾

2020 KCTF秋季赛 | 第三题设计及解题思路

2020 KCTF秋季赛 | 第一题点评及解题思路

出题战队:七星战队

2020 KCTF秋季赛 | 第三题设计及解题思路

2020 KCTF秋季赛 | 第二题设计及解题思路

出题战队:中娅之戒



2020 KCTF秋季赛 | 第三题设计及解题思路


2020 KCTF秋季赛 | 第三题设计及解题思路

你的好友秀秀子拍了拍你

并请你点击阅读原文,查看更多赛题解析!

本文始发于微信公众号(看雪学院):2020 KCTF秋季赛 | 第三题设计及解题思路

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: