首页
论坛
课程
招聘
[原创]中娅之戒KCTF2020秋季赛题目第二题 异常信号 设计思路
2020-11-13 12:23 5651

[原创]中娅之戒KCTF2020秋季赛题目第二题 异常信号 设计思路

2020-11-13 12:23
5651

大家好!我们又见面了!这一次我们奉上的作品是:密室逃脱系列之三——异常信号

题目描述

“破晓”已载着人类最后的希望驶向安全地带。通过地球上的监控摄像头,你们亲眼见证了地球的毁灭,“破晓”系统也再也无法检测到地球的存在。你悲痛不已,随身设备却检测拦截到异常信号波动,信号竟来自于太阳系?!

 

信号来自于一群围绕太阳的新行星

 

每一颗行星与别的行星之间都有一个虫洞必须穿过每个虫洞才能回到地球

 

记住:虫洞是奇异的一旦穿过了曾经穿过的虫洞你将永远迷失在次元空间中

算法设计思路

要求给出一个列表a,其中包括不少于n=12个不同的非负整数,其最小值为0,最大值不大于w=89,使得任意两个数之差的绝对值都不相同。

 

程序中过滤了对称解。

 

在输入上,通过设置random的种子构造了一个输出为16bit的哈希函数H;在第i位(每“位”为一个16bit的数字)上,若为H(i)则表示列表a中包含数字i;否则,若第i位为H(-i)则表示列表a中不包含数字i;否则,判定为输入格式错误。

解题思路

要在[0, w]范围内寻找n个数字,使其中任意2个数字之距离是不重复的。显然,w越大/n越小,这个问题越容易解决。

 

但是此题限制了n≥12,w≤89。显然破解者应该试图在12/89的限制下去寻找解。更大的n和更小的w,都会使得求解更难。

 

然而在限制条件(12, 89)下遍历所有可能,也是个天文数字。直接穷举是不明智的。

 

于是,可以采用多种启发式搜索、截支、动态规划等方法来加速。最终得到结果:此题是无解的!
(cm中也已经对此给出了提示。这就要看你信不信了)

 

此题就如同天龙八部中的“珍珑局”,众多棋盘高手都无法破局,而唯独虚竹,起手便将一片活棋下成死棋,而最终却获得了满盘的胜利。

 

要破解此题,也需要这种“向死而生”的觉悟!

 

通过简单分析,一般人直觉上会认为:更大的n和更小的w,都会使得求解更难。但此题设计巧妙之处正是:w为89是无解的,但w<89时却未必。

 

如果你愿意在89穷举失败之后,愿意继续尝试88、87、86……也许你还愿意继续尝试n=13、14、15……

 

你就会发现此题的解:
[0,2,6,24,29,40,43,55,68,75,76,85]
675E7A02004E86190D659330197C9F472513B036296BB8753E41C40C4A58D023566F7E5A6306E9516F1DF5687B340100884B0E1794621A2EA0792645AE04335CB9273F73C53E4B0AD1555821DE6C6438EA03704F647A7D660332D2170F4995141B60A12B2877AE42340EBA594025C6700E59D3075953DF1E656A705F7101F84C7E1804648A2F107B96461D12A35D2929AF743540BB0B4157C8224E6ED4390110E050661CED67E861F97EDC4A
但是,这并不是此题的解。
由于此题具有对称性,所以还有一个对称解;cm中过滤掉了对称解的其中一个,所以下面这个才是正确序列号:
[0,9,10,17,30,42,45,56,61,79,83,85]
675E7A025B4786190D65933042199F472513AB5E312AB8753E41C40C4A58D023566FDD3A6306E9516F1DF5687B340100D3490E1794621A2EA0793450AD10335CB9273F73C53E4B0AD1555821DE6C64387111704FF61ADE2E0332897D0F4995141B60A12B2877AE42340EBA59402594244D3CD3075953DF1E656AEB357101F84C7E1804648A2F107BC44E1D12A35D2929AF743540BB0B193E93724E6ED4395A05E050661CED677333F97EDC4A

脱壳思路

老规矩,我们也安排了科锐的在读学员利用所学对本题EXE加壳了。虽不敌看雪大佬,但也希望能拿出来给各位同行品鉴一下。下面是脱壳描述:

定位OEP

首先定位到程序的入口点
图片描述
使用工具进行dump
图片描述

修复IAT表和重定位表

定位到壳中的IAT表和重定位表的位置,根据其来修复脱壳后程序的重定位表和导入表。
定位到重建后的IAT表的位置。
图片描述

 

壳中填充完毕后的IAT表。
图片描述

 

这里的IAT表进行了加密
图片描述

 

定位到重定位表
图片描述

 

据此上信息,修复IAT表和复制导入表到dump后的程序即可。

修复原程序

修复后nop掉原程序中调用壳中函数的代码。
图片描述

 

nop掉第二处
图片描述

 

处理完后,这里就是加密算法的执行流程了。
图片描述

 

到此壳的保护机制完全去除,继续进行加密算法的破解即可。


【公告】欢迎大家踊跃尝试高研班11月试题,挑战自己的极限!

最后于 2020-11-21 14:44 被kanxue编辑 ,原因:
上传的附件:
收藏
点赞0
打赏
分享
最新回复 (6)
雪    币: 607
活跃值: 活跃值 (216)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
修仙大能 活跃值 2020-11-23 14:50
2
0
图不清楚,看不起
雪    币: 7514
活跃值: 活跃值 (1034)
能力值: ( LV5,RANK:77 )
在线值:
发帖
回帖
粉丝
qux 活跃值 2020-11-24 00:08
3
0
菜鸟想问一下,这个OEP是怎么定位到的呀?
雪    币: 6
活跃值: 活跃值 (83)
能力值: ( LV3,RANK:25 )
在线值:
发帖
回帖
粉丝
某字哮天 活跃值 2020-11-24 09:39
4
1

图不清楚

最后于 2020-11-24 09:43 被某字哮天编辑 ,原因:
雪    币: 5
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
wrong-123 活跃值 2020-12-27 17:44
5
0
提供源码吗。。
雪    币: 391
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
n0rthwater 活跃值 2021-1-5 21:28
6
0
同问,怎么定位到这个OEP
雪    币: 206
活跃值: 活跃值 (139)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
灰灰Hui 活跃值 2021-3-9 11:25
7
0
在space区段下执行断点来断到OEP
游客
登录 | 注册 方可回帖
返回