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

admin 2021年4月8日17:58:50评论57 views字数 4520阅读15分4秒阅读模式

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


在经过2天紧张激励的比拼后,第二题历时2天,最终落下帷幕,并于21日中午12点正式关闭攻击通道。

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

此题共有4004人围观,并在开赛后的9小时左右,由文路大专战队夺下首旗,获取一血额外加分。TLJ战dotsu_战队则位列第2、3位。截止赛题关闭,累计共有13支战队攻破成功!恭喜!


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


接下来我们一起来看一下这道题的设计思路和详细解析吧。


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

第二题:异常信号


破晓”已载着人类最后的希望驶向远离地球的安全地带。漂泊在广袤无垠的宇宙中,人类今后该何去何从仍然是个问号。

时间一分一秒过去,“破晓”中央大厅的虚拟投射屏幕上,分析数据一行行变幻跳动着,悬浮的小窗口显示着地球各地的实时影像。很多人簇拥在中央大厅里屏息凝视着大荧幕,祈祷那一刻不要到来。

刹那间,警报声划破了如死一般的寂静。“警告!警告!x-63892号黑洞已进入地球轨道。”

在放大的悬浮窗口上,可以清晰地看到原本晴空万里的天幕上出现了一个突兀的黑点,裹挟着猛烈的风向地面席卷而来。伴随着黑点的边缘不断向外扩散,并开始缓缓地逆时针旋转,一个巨大的漩涡在空中形成,周围的一切都逐渐开始变得模糊,越发看不清边界,直到被漩涡中心强大的吸力卷入其中,与黑洞彻底融为一体。

黑洞贪婪地吞噬着地球上的一切,你和“破晓”上的幸存者们无助地看着来自世界各地的影像一个一个被黑暗所笼罩,伴随着刺耳的电流声和令人眼花的雪花屏,彻底失去信号。

在宇宙空间站传来的影像中,太阳系中那颗蔚蓝的星球消失了……

“已无法检测到来自地球的信号……”系统一遍遍机械地重复着检测结果,连绵不绝的呜咽声在大厅里回荡。

你盘腿坐在大厅一角,虚拟屏幕散发的蓝光映照在你的脸上,忽明忽暗。看着自己的微型计算机也得出与“破晓”相同的检测结论,你咬了咬牙,抬手把戴在头上的卫衣帽子又往下扯了扯。

正当你死了那条心,打算关闭计算机时,红光忽地亮了起来。定睛一看,你自制的信号接收系统拦截到了一段稍纵即逝的异常信号波动,追踪来源竟发现信号来自太阳系?!

信号来自于一群围绕太阳的新行星,每一颗行星与别的行星之间都有一个虫洞,必须穿过每个虫洞才能回到地球。

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

* 上下滑动查看

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


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

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


设计思路由作者 iiiiiiiiiiii 提供。


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





算法设计思路



要求给出一个列表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


首先定位到程序的入口点:

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

使用工具进行dump:

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

修复IAT表和重定位表


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


定位到重建后的IAT表的位置:

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

壳中填充完毕后的IAT表:

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

这里的IAT表进行了加密:

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

定位到重定位表:

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

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


修复原程序


修复后nop掉原程序中调用壳中函数的代码:

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

nop掉第二处:

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

处理完后,这里就是加密算法的执行流程了:

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

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


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

本解析过程由作者 Anakin Stone 提供。




输入处理



控制台程序是通过NtReadFile获取输入的,不出意外的化,会有一个线程处于NtReadFile的同步等待状态,依次查看线程当前EIP,看是否有这样的线程存在。

查看线程列表如下:
2020 KCTF秋季赛 | 第二题设计及解题思路
2020 KCTF秋季赛 | 第二题设计及解题思路
可以看到4号线程,就是我们要找的输入线程,在777E1E6C下断。输入测试注册码12345678,回车,不出意外,成功断下,观察栈:
2020 KCTF秋季赛 | 第二题设计及解题思路
地址0xCC3C30存放的就是读取到的我们输入的测试注册码。对其下硬件读断点,跟踪注册码处理。

保持对测试注册码的读取跟踪,直到下图所示位置:
2020 KCTF秋季赛 | 第二题设计及解题思路
通过上下问分析,sub_561270会从注册码中依次取一个字符放到'参数2'所指地址,暂且将其命名为get_char,继续跟踪:
2020 KCTF秋季赛 | 第二题设计及解题思路
ebp-1dc内存数据如下:
2020 KCTF秋季赛 | 第二题设计及解题思路
可以看到,561410行-561454行代码,读取验证码每一个字符直到'a'(不包括),做对应的ASCII-数值转换(从中也可以看出,是不支持小写字符的), 存放到缓冲区 ebp-36c,执行完毕后,ebp-36c内存数据如下:
2020 KCTF秋季赛 | 第二题设计及解题思路
紧随其后,再次转换:
2020 KCTF秋季赛 | 第二题设计及解题思路
上图代码将ebp-36c中数据重组,放到ebp-dc缓冲区,处理后结果如下图:
2020 KCTF秋季赛 | 第二题设计及解题思路




礼貌的开场白



第一个算法5614C0-5615BC,注意规避561523-561553之间的反调试代码:

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

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

根据索引算出hash值,hash算法如下:

unsigned short calc_hash(short val){    long _seed = val >= 0 ? val : 0x10000 + val;     for (size_t i = 0; i < 101; i++)    {        _seed *= 0x343FD;        _seed += 0x269EC3;    }     _seed >>= 0x10;    _seed &= 0x7fff;    return (unsigned short)_seed;}

等价逻辑:

short m = 0,n = 0for (m = 0, m < length:word:[ebp-dc], ++m){    if (word:[ebp-dc][m] == calc_hash(m))    {        dword:[ebp-4fc] = n    }    else if(word:[ebp-dc][m] == calc_hash(-m))    {        ++n    }    else    {        print "一个礼貌的开场白"        exit    }} if(n < 12){    print "行星太少了"    exit}

根据分析内容,做个礼貌的回应,构造一个最短长度的测试注册码:675EE1125B47D47B4E30C8644219BC4D3602B036296BA31F,再次执行,'开场白'已过,是时候进入真正的验证了。




有人说这题是无解的



分析随后的代码:
2020 KCTF秋季赛 | 第二题设计及解题思路
此时,ebp-4fc为上文中解析出的索引值集合,如下:
2020 KCTF秋季赛 | 第二题设计及解题思路
验证逻辑:

fill [ebp-78], 0, 100 short i = 0, j = 0;for (i = 0; i < length:dword:[ebp-4fc] - 1; ++i){     for (j = i + 1; j < length:dword:[ebp-4fc]; ++j)     {         dis = dword:[ebp-4fc][j] - dword:[ebp-4fc][i]         if(byte:[ebp-78][dis] == 0)         {              byte:[ebp-78][dis] = 1         }         else         {             print "此题无解"             exit         }           }}

那么根据上面的验证逻辑,什么样的注册码是满足条件的呢?

考虑这样一个数列:
一个最少包含12个数的自然数数列,其中任意两数的差都不相等。

如果这样的数列存在,那么题中的验证逻辑是可以满足的,那么是否存在这样的数列呢?百度一下。
2020 KCTF秋季赛 | 第二题设计及解题思路
已经找到了我们想要的答案,那就是: 0,2,6,24,29,40,43,55,68,75,76,85
上代码:
2020 KCTF秋季赛 | 第二题设计及解题思路




验证


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

完工。


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

赛场风云变幻,不到最后输赢难见分晓。

现在第四题已经开放,快来继续挑战自己吧!


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


越早提交答案,得分越高哦!
‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍立即扫码逆风翻盘!

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

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

大佬牛逼!!KCTF 就是坠吊的!你们耗子尾汁,我要开始发功了!!不攻下这面旗,我誓不罢休!!(ノ°ο°)ノ前方高能预警真香警告!我要得第
2020 KCTF秋季赛 | 第二题设计及解题思路



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

你的好友秀秀子拍了拍你

并请你点击阅读原文,参与挑战!

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

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2021年4月8日17:58:50
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   2020 KCTF秋季赛 | 第二题设计及解题思路http://cn-sec.com/archives/189420.html

发表评论

匿名网友 填写信息