在经过2天紧张激励的比拼后，第二题历时2天，最终落下帷幕，并于21日中午12点正式关闭攻击通道。
此题共有4004人围观，并在开赛后的9小时左右，由崇文路大专战队夺下首旗，获取一血额外加分。TLJ战队和dotsu_战队则位列第2、3位。截止赛题关闭，累计共有13支战队攻破成功！恭喜！
设计思路由作者 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
首先定位到程序的入口点：
使用工具进行dump：
修复IAT表和重定位表
定位到壳中的IAT表和重定位表的位置，根据其来修复脱壳后程序的重定位表和导入表。
定位到重建后的IAT表的位置：
壳中填充完毕后的IAT表：
这里的IAT表进行了加密：
定位到重定位表：
据此上信息，修复IAT表和复制导入表到dump后的程序即可。
修复原程序
修复后nop掉原程序中调用壳中函数的代码：
nop掉第二处：
处理完后，这里就是加密算法的执行流程了：
到此壳的保护机制完全去除，继续进行加密算法的破解即可。
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}
fill [ebp-78], 0, 100short 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}}}
赛场风云变幻，不到最后输赢难见分晓。
现在第四题已经开放，快来继续挑战自己吧！
你的好友秀秀子拍了拍你
并请你点击阅读原文，参与挑战！
本文始发于微信公众号（看雪学院）：2020 KCTF秋季赛 | 第二题设计及解题思路
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论