首页
社区
课程
招聘
[讨论]爆破算法优化
2015-8-5 13:36 13337

[讨论]爆破算法优化

2015-8-5 13:36
13337
算法如下:
v1 = 0
v2 = k1
v3 = k2
{
v1 += const1

v2 += v3<<4
v2 += v3^const2
v2 += (v3>>5)^v1
v2 += const3

v3 += v2<<4
v3 += v2^const4
v3 += (v2>>5)^v1
v3 += const5
}循环32次

k1,k2,const2~5全为0x20-0x7e中任意字符的任意组合,const1为任意非0十六进制数。

目前通过取消循环体,速度为15s算完一个k1k2(0x20202020)到(k1+1)k2(0x7f7f7f7f)区间。

求更快的算法。

另外,const1~5不便透露……

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界

收藏
点赞1
打赏
分享
最新回复 (9)
雪    币: 293
活跃值: (232)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
瀚海云烟 1 2015-8-5 16:31
2
0
另外更优算法不便透露
雪    币: 217
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
ztxb 2015-8-5 17:46
3
0
幽默了.哈哈哈.
雪    币: 622
活跃值: (294)
能力值: ( LV13,RANK:410 )
在线值:
发帖
回帖
粉丝
无聊的菜鸟 9 2015-8-5 22:03
4
0
const1~5是特征码,写出来容易被物理定位……
雪    币: 293
活跃值: (232)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
瀚海云烟 1 2015-8-6 10:53
5
0
很多v2、v3是中间变量,可以整在一起,怎么看也看不明白最后结果是v2、v3里面的数据结合呢还是就只要一个,你还是弄个完整的输入输出函数比较方便,这一小片段优化很容易优化出问题的。IDA F5出来的东西,还是直接贴汇编更符合我习惯
雪    币: 624
活跃值: (668)
能力值: ( LV9,RANK:270 )
在线值:
发帖
回帖
粉丝
MistHill 6 2015-8-7 12:15
6
0
可理解为:已知8字节16进制数(Hash值,0x00~0xFF/BYTE) v2v3 及哈希函数,求8字节可打印字符原文(0x20~0x7E/BYTE) k1k2。

由于哈希函数不可逆,和MD5、SHA1等一样,基本上是不可能完成的任务。
有利的是,输入的长度和取值范围是已知的。另外,在这种Shift cipher + XOR cipher的哈希计算中,循环是必须的,否则在有限的步数内是可逆的。

试了一下,在一个几年前的双核笔记本上:k1不变,k2=0x20202020~0x7E7E7E7E,循环32次,需要15703ms,取消循环969ms,注释掉v2的计算578ms。
检查编译后的汇编代码,确认循环体里,变量v1、v2、v3都在寄存器中。
再计算跑完 k1=0x20202020~0x7E7E7E7E 的次数:
0x5F^4 = 0x04DAD681 ≡ 81,450,625 次,按15s/次,大概需要38年!!!
所以,别小看这个简单的函数!

也正因为函数的每一步都是最基本的计算(加、移位、异或),而且都是必须的,优化的余地很小。
从函数本身看,v2是中间变量,v3是最终结果。如果只需要v3匹配,运气好的话,在可忍受的时间内也许能找到一个碰撞;如果要求v2也必须匹配,那就只能祈祷了。
雪    币: 67
活跃值: (30)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
没有姓名 2015-8-11 18:56
7
0
建议楼主做一下查分分析,计算一个f(x0),然后在此基础上计算f(x1),就是要分析一下f(x0)和f(x1)之间的差分关系。

如果是做攻击的话,一般可以做概率性的算法,只要保证几乎都是正确的就可以了。
雪    币: 622
活跃值: (294)
能力值: ( LV13,RANK:410 )
在线值:
发帖
回帖
粉丝
无聊的菜鸟 9 2015-8-13 20:10
8
0
搜索了论坛一个旧帖子,现在改用层级爆破。单线程可以最大16分钟内完成逆推,目前算法上还有一些问题。但是时间上估计不会改变太多了。
雪    币: 624
活跃值: (668)
能力值: ( LV9,RANK:270 )
在线值:
发帖
回帖
粉丝
MistHill 6 2015-10-8 12:20
9
0
不知楼主有什么进展没有。
过节无聊,玩个东西也遇到这个问题,才明白楼主说的是啥。

楼主贴的是这个对称算法的加密代码,解密代码在程序中。
取值空间不是0x20~0x7E,而是0x60~0xF4,所以计算量增加了很多,仅用编成穷举基本上不可能得到结果,需要新的算法或基础研究。
游客
登录 | 注册 方可回帖
返回