首页
论坛
课程
招聘
[原创]第六题 一尺之棰
2020-4-26 20:47 2495

[原创]第六题 一尺之棰

xym 活跃值
2
2020-4-26 20:47
2495
首先看文件大小,75k。看起来很精悍的样子,是我喜欢的题目类型。系统要求WIN10/64,但是我在WIN7/64下运行也很正常,没有影响解题。
题目基本所有关键代码都在main函数中,不需要花费太多精力在流程跳转上。
输入在转换为16进制数后会进入了一个16次的大循环,每次循环结束都会将输出转为输入继续下一轮。整个循环结束后判断输出长度是否为0x38A并与循环前初始化的一个疑似大数进行比较,如果验证通过则输出成功信息。 大循环里面还有输入长度加5次的中循环,中循环里面还有256次小循环。
进一步分析可以发现输出的前2个字节为前一次输入的长度,所以最后一次的输入(即倒数第二次的输出)应该是0x305字节。256次的小循环是产生与输入无关的固定随机数,中循环逐个字节读取输入并产生若干比特的输出,该输出长度可以为0。
根据题目的输出模式,很容易理解每个循环的输入和输出之间存在着很强的前后对应关系,而且题目运算最耗费时间的是产生固定随机数。如果使用爆破方法,在去掉产生固定随机数的算法后,还可以按照顺序用输出对输入进行逐个字节校正,从而加快爆破速度。
题目比较耗费时间的就是正向算法的重构,还是由于所有关键代码都在main函数中,所以大量变量都在一起,很难区分。最关键的是浮点运算的精度控制寄存器在printf调用的output_l函数里被改变了,导致固定随机数与题目计算的对不上,最后解决办法是在代码开始处加上_mm_setcsr(_mm_getcsr() | 0x4000);
恢复算法之后,构造数据结构存储每一个字节的所有路径,对最后一次的输入采用深度优先算法进行遍历。在优化算法后对0x305字节的遍历速度在10分钟以内,对整个16轮的遍历不到半个小时。最后得到的结果为:504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C。
typedef struct PathStr {
	WORD MaxNum;
	WORD CurNum;
	BYTE Path[0x100];
}PathStr;
PathStr Paths[0x400];

[看雪官方培训] Unicorn Trace还原Ollvm算法!《安卓高级研修班》2021年秋季班火热招生!!

最后于 2020-4-26 23:53 被xym编辑 ,原因:
收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回