看雪论坛
发新帖
9

[讨论]爆破算法优化

无聊的菜鸟 2015-8-5 13:36 8099
算法如下:
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不便透露……
本主题帖已收到 0 次赞赏,累计¥0.00
最新回复 (9)
1
瀚海云烟 2015-8-5 16:31
2
另外更优算法不便透露
ztxb 2015-8-5 17:46
3
幽默了.哈哈哈.
9
无聊的菜鸟 2015-8-5 22:03
4
const1~5是特征码,写出来容易被物理定位……
1
瀚海云烟 2015-8-6 10:53
5
很多v2、v3是中间变量,可以整在一起,怎么看也看不明白最后结果是v2、v3里面的数据结合呢还是就只要一个,你还是弄个完整的输入输出函数比较方便,这一小片段优化很容易优化出问题的。IDA F5出来的东西,还是直接贴汇编更符合我习惯
6
MistHill 2015-8-7 12:15
6
可理解为:已知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也必须匹配,那就只能祈祷了。
没有姓名 2015-8-11 18:56
7
建议楼主做一下查分分析,计算一个f(x0),然后在此基础上计算f(x1),就是要分析一下f(x0)和f(x1)之间的差分关系。

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

楼主贴的是这个对称算法的加密代码,解密代码在程序中。
取值空间不是0x20~0x7E,而是0x60~0xF4,所以计算量增加了很多,仅用编成穷举基本上不可能得到结果,需要新的算法或基础研究。
wx_Core 2017-8-9 17:20
10
楼主  方便留个联系方式吗?有事急求。
返回



©2000-2017 看雪学院 | Based on Xiuno BBS | 域名 加速乐 保护 | SSL证书 又拍云 提供 | 微信公众号:ikanxue
Time: 0.013, SQL: 10 / 京ICP备10040895号-17