首页
论坛
专栏
课程
1

[原创]看雪2018国庆题 叹息之墙 解题思路(出题者提供)

看场雪 2018-10-8 11:56 756

叹息之墙 解题思路

 

解题分为4个阶段:逆向、分析、逆推、编程

 

逆向:
代码有混淆
出题者预想的正确解题方法是:破解者根据代码混淆规则 编写优化器 解除混淆
但是实际上 破解者‘手撸’的能力远远超出了出题者的预期
佩服!
(下次再出题 要么不混淆 要么会升级混淆策略)

 

分析:
逆向之后可知 输入的序列号进入了3个流程
1)合法性判断:判断顺序 判断是否越界(351) 判断格式
2)数据抽取:依据输入的这些数作为下标 从指定数组(命名为elist)取出若干个32位无符号整型 并求和(可能超过32位)
3)验证:以"2xue"作为底数 以和作为指数 以0xFFA1CF8F作为模数 求模幂 判断结果是否是"4kan",如果是 则显示输入正确
"4kan"和"2xue"显然主要是看雪的拼音 与解题方法无直接关系
所以 有用信息只有2个数:数组长度351和模数0xFFA1CF8F

 

已知模数后 可求解阶 可分解阶
分解阶后 会发现有9个素因子 且全是小素因子(随机条件下出现这种情况的概率极低 所以可以断定 这是出题者有意为之 这里一定有名堂!)
分析素因子会发现 所有素因子之和是360。正好是 360=351+9
因此可以猜想 对数组访问的下标 是模幂运算的指数对9个素因子分别的余数(或者余数的一一映射)且针对每个余数去掉了1个数
去掉的是哪一个数呢?暂且伏笔

 

逆推:
根据底数和模幂结果 求解最小指数解 是容易的 (采用BabyStepGiantStep方法 大约耗时1秒)
只要从elist中挑出的所有数字之和 与最小指数解 对阶同余 就算解题正确
由于从elist中挑出的每个数会针对阶的某一个素因子 因此 这个数一定要保证与其它素因子所构成的基底正交 否则此题将难解或者多解
也就是说 这个数必须不会影响模幂结果在其它素因子构建的子群上的计算结果 必须在其它素因子所对应的乘法子群上表现为单位1

 

编程:
对elist里的每个数进行搜索 利用费马小定理 找到其针对的素因子和对应余数 大约耗时1秒
其结果正好能遍历所有可能的余数,只是少了余数为0的那个(这也回答了前面搁置的那个‘少了哪一个数?’的问题)
剩下的工作就简单了
根据最小指数解对每个小素因子的余数 一共从elist中挑出9个数 排序 按照格式构造出输入序列号即可

 

最终正确解只有1个:17x27x60x97x133x161x243x292x309X

 

题目下载:https://ctf.pediy.com/game-team_fight-71.htm



快讯:看雪智能设备漏洞挖掘公开课招生中!

最后于 2018-10-8 13:35 被kanxue编辑 ,原因:
最新回复 (0)
返回