这是一个创建于 4643 天前的主题，其中的信息可能已经有所发展或是发生改变。
起因大家都懂得，这里只是做个简单的计算，判断什么的我不会写的。
大前提是：MD5 是迄今为止没有算法上的太大漏洞，而且要求是逆向（不是寻找碰撞）。
1. 彩虹表有用吗？
在这个特定的情形下，没有。解释如下：
MD5 是一种摘要散列算法，任意大小的原文都会转化为定长的密文。
彩虹表是一种预先计算的原文到密文的映射，如果密文在彩虹表的覆盖空间里，那么就可以反查到原文。而原文空间理论上无限大，完全运算并存储这些映射非常消耗资源，所以，彩虹表更多的是一种“空间时间消耗都可以接受”的算法加上数据集合。
很显然，某个 MD5 运算结果不可能在常见的彩虹表覆盖空间里。
（注，一个9位以内数字组合的彩虹表大概要接近 1TB 而由于算法链式验证的原因，实际计算次数要数倍于穷举运算，参见 http://project-rainbowcrack.com/table.htm ）
2. 爆破怎么做？
爆破就是拼运算力了。
手机号字段大概有 1e7 种组合，而后面还有随机字符串，不知道有多长，姑且算作 5 位吧，字母数字组合，就简化作 1e8 种组合好了。
现在假设你运气足够好，其他位全都猜对了，比如你知道要把 v2ex 逆序之类的，需要验证 1e15 次吧。
（这是一个非常简单的估算，纯粹估算下限）
3. GPU 通用运算能力到底有多强？
最强的通用计算单元 ATI HD6990 大概运算力是 1e10 次，cpu 相对于 gpu 小太多数量级，所以可以不考虑了。
假如你能够调用 100 显卡的某超算集群，一个小时的运算力大概是 1e15 次验证。
（参见 http://golubev.com/gpuest.htm ）
4. 一些细节
￥ 这个字符是 unicode 字符，而 md5 并没有针对 unicode 的特定实现。
实际的实现是先转换成 utf8/utf16/ansi 等等编码形式再进行计算。
（某些特定程序支持传入 unicode 字符串，但依旧需要内部进行编码转换）
这一条的意义是说，如果加密者的编码是 utf8 而你的运算程序是 ansi 编码，那就不用想了，永远都不会有结果。
MD5 算法是 16-byte 分段，可以认为运算时间正比于原文长度，目测待解密的原文是 32-byte 左右，即实际运算能力可能要减半。
（假设非常多的时候，参见 http://en.wikipedia.org/wiki/Occam's_razor ）
大前提是：MD5 是迄今为止没有算法上的太大漏洞，而且要求是逆向（不是寻找碰撞）。
1. 彩虹表有用吗？
在这个特定的情形下，没有。解释如下：
MD5 是一种摘要散列算法，任意大小的原文都会转化为定长的密文。
彩虹表是一种预先计算的原文到密文的映射，如果密文在彩虹表的覆盖空间里，那么就可以反查到原文。而原文空间理论上无限大，完全运算并存储这些映射非常消耗资源，所以，彩虹表更多的是一种“空间时间消耗都可以接受”的算法加上数据集合。
很显然，某个 MD5 运算结果不可能在常见的彩虹表覆盖空间里。
（注，一个9位以内数字组合的彩虹表大概要接近 1TB 而由于算法链式验证的原因，实际计算次数要数倍于穷举运算，参见 http://project-rainbowcrack.com/table.htm ）
2. 爆破怎么做？
爆破就是拼运算力了。
手机号字段大概有 1e7 种组合，而后面还有随机字符串，不知道有多长，姑且算作 5 位吧，字母数字组合，就简化作 1e8 种组合好了。
现在假设你运气足够好，其他位全都猜对了，比如你知道要把 v2ex 逆序之类的，需要验证 1e15 次吧。
（这是一个非常简单的估算，纯粹估算下限）
3. GPU 通用运算能力到底有多强？
最强的通用计算单元 ATI HD6990 大概运算力是 1e10 次，cpu 相对于 gpu 小太多数量级，所以可以不考虑了。
假如你能够调用 100 显卡的某超算集群，一个小时的运算力大概是 1e15 次验证。
（参见 http://golubev.com/gpuest.htm ）
4. 一些细节
￥ 这个字符是 unicode 字符，而 md5 并没有针对 unicode 的特定实现。
实际的实现是先转换成 utf8/utf16/ansi 等等编码形式再进行计算。
（某些特定程序支持传入 unicode 字符串，但依旧需要内部进行编码转换）
这一条的意义是说，如果加密者的编码是 utf8 而你的运算程序是 ansi 编码，那就不用想了，永远都不会有结果。
MD5 算法是 16-byte 分段，可以认为运算时间正比于原文长度，目测待解密的原文是 32-byte 左右，即实际运算能力可能要减半。
（假设非常多的时候，参见 http://en.wikipedia.org/wiki/Occam's_razor ）
 |
1
momou 2012-03-09 13:50:36 +08:00
学习，等高人。。。
|
 |
2
GordianZ MOD 关于￥我插一个嘴，如果已经开始爆破了，估计就没用编码直接上HEX了。而且原文应该不在彩虹表里面。
再且，9位数字的彩虹表用不了1GB啊。 1e9种组合，原文2字节，散列16字节 = 18e9 bytes = 18GB. 但是不可否认包含这次的明文的彩虹表肯定不止1TB. |
 |
3
zhuang OP @GordianZ
MD5 计算不是说一段一段的，是要形式如： md5(moc.xe2v1861xxxxxxx￥0XXXXX)=32-hash 这种作为一个待运算的整体对待的。 拿到密文的人现场计算彩虹表和爆破是没有区别的，做表运算量更大。 |
 |
4
lch21 2012-03-09 14:14:20 +08:00
8位任意字符组合，半个小时搞定。
100张显卡集群 实践检验过的 |
 |
5
d5d 2012-03-09 14:14:46 +08:00
b0ba5f33e8a56957f7700e3ad2158c4d:60
|
|
6
zhuang OP |
|
9
zhuang OP @lch21
应该说这个站点里第一个因为 bitcoin 挣到钱的就是我了，而那个时候中文环境没有任何关于 bitcoin 的介绍。v2ex/twitter 上很多人都应该对此有印象。还有我是 bitcoin 黑。 另外，我还接触过前几年曾经的中国第一超算集群。我个人的体会是，要充分调用集群的运算能力，需要的准备工作很麻烦。比如配置你的任务调度系统，再比如实际调用之前的反复验证。 至于 100 张显卡的集群，我真的只能笑一笑。 |
 |
11
cooka 2012-03-09 14:58:41 +08:00
@zhuang 破解者设计密码字典(含v2ex,186)对这个(20位以上字符串)反向计算有没有用处呢?
或者说对反向的帮助有多大? |
|
13
zhuang OP |
 |
15
Shared 2012-03-11 02:32:24 +08:00
@GordianZ 不同编码的HEX值是不同的，即使是同样的￥使用Unicode的不同编码方式（UTF8,UTF16等等）得到的结果也不同。所以破解的人最后还得注意一下编码问题？要不然很可能得到的结果是一堆乱码，哈哈
|
 |
16
afterain 2012-03-11 14:42:11 +08:00 via Android
回顾整个事件，这个帖子无论是从技术还是态度上来说都是非常值得学习的。
其他的…… |
 |
17
aristotle9 2012-03-11 16:03:09 +08:00
10个节点的cpu+gpu集群对计算能力的提升大概在2个数量级.
http://www.bnu.edu.cn/xzhd/32239.htm 集群的规模对计算能力之数量级的提升基本上是对数函数(lg n),即使出现gpu集群,现有的运算能力还不足以对现行的密码体系造成决定性的打击. 大神打架是拼数量级的. |
 |
18
sigone 2012-03-11 16:04:37 +08:00 via Android
舍得 舍得 ... 呵呵
|
|
19
sigone 2012-03-11 16:07:46 +08:00 via Android
其实我说的是一句密文，哪位童鞋能算出他的愿意!
|
 |
20
Livid MOD 谢谢 @zhuang 的这个帖子，受教了。
昨天晚上自己做了一些实验，这个事情我想应该接近得出结论了。 http://www.v2ex.com/t/29393 我喜欢并且感谢大家从理科角度来论证这个问题。:) |
 |
21
haha1903 2012-03-12 09:33:06 +08:00
而且要求是逆向（不是寻找碰撞），这一句，我理解就是不可能的。
|
 |
22
ofan 2012-03-12 10:09:20 +08:00
md5是不可逆的，所谓破解都是找碰撞
|
|
23
zhuang OP |
 |
24
hq5261984 2012-03-12 12:12:23 +08:00
关于MD5逆向你去请教王小云吧。听说她老人家逆向不用计算机直接在纸上演算，至于时间就不晓得了。
|
 |
28
Ricepig 2012-03-12 20:25:51 +08:00
|
|
30
Ricepig 2012-03-12 20:41:41 +08:00
@zhuang
其实CPU的峰值与GPU峰值差距已经没有那么大了，i7 920的峰值已经在100Gflops左右。最多比显卡低一个数量级而已，所以并不能忽略。当控制语句较多时，CPU和GPU的差距将会进一步缩小。当前很多论文的比较都是将GPU优化的实现与CPU未优化的实现甚至是单核CPU相比。 当然，就暴力法破解md5来说，GPU相对会有点优势，但是优势也不如你说的“CPU小太多数量级”这么多了。 |
|
31
zhuang OP @Ricepig
你说得很对，我本来是想说 cpu 相对于 gpu 运算能力是数量级的差别，在分析这个问题的时候就像数学上说的低阶无穷小，可以被忽略。 不过 flops 确实不太适合用来简化评价 cpu/gpu 的性能差别，不过现在硬件厂商普遍标注的是等效 x86 flops 效能。 这是因为 cpu/gpu 是两种不同的架构，针对每个时钟周期而言（per clock）： core i7 920 每个物理核心可以通过 AVX-256bit 执行 4 次 32bit 浮点指令 AMD 6970 通过 1536 shader 单元可以执行 1536 次 32bit 浮点指令 考虑到时钟频率： core i7 920 @ 2.66GHz x 4 cores AMD 6970 @ 880MHz 这样 AMD 6970 GPU 相对于 core i7 920 大概是 32 倍左右。 core i7 920 @ 0.1Tflops / AMD 6970 @ 2.7Tflops 基本表明了这一点。 |
|
32
Ricepig 2012-03-13 06:23:28 +08:00
@zhuang 其实拿6970和i7 920比已然不太合适了，一个是08年底上市的，一个是10年底上市的，已经不是同一个半导体时代了。
其次，AMD的GPU有一个特点，就是狂堆ALU，采用SIMD+VLIW的结构，造成峰值非常高（一直比NV同档次的GPU高），但是实际效率就一般了，稍有分支的话实际性能就下降的很快。 如果拿常用做GPGPU的NVIDIA的显卡来比，差距会进一步缩小。 据我查找到的与I7 920同时代的GTX 280的峰值性能，大概在700Gflops+，很符合我上面贴的一个数量级的说法。 不过，其实GPU和CPU可以协同的。。。不用白不用哇。而且，考虑到CPU上烂实现很多，而GPU上大家都会特别为GPU结构优化，所以GPU的效率往往还是要高的。只是不如很多人想的那么多。 |
|
33
Ricepig 2012-03-13 06:25:56 +08:00
@zhuang 再另外，其实GPU的等效x86 flops会比它自己所标识的flops要低，尤其是针对双精度和整数。整数要看GPU的架构，有些慢得不太多。双精度就要低很多了，因为x86的双精度运算是内部80位外部64位的。
|
 |
34
liyandong 2012-03-13 07:57:23 +08:00
只听说一牛人租了重量级的亚马逊云碰撞Md5，字母数字符号复杂密码，6小时
|
 |
35
0bit 2012-03-13 08:34:37 +08:00
@Ricepig 我怎么记得王小云只是能构造两个md5相同的原文，而不是根据已有的md5来构造出来原文呢。如果根据md5构造原文能实现的话，那现在被广泛应用的这种基于md5等hash的密码存储体系，可真的就要崩溃了。（虽然现在也快崩溃了）
|
 |
36
sinxccc 2012-03-13 08:44:15 +08:00
@0bit 您的理解是对的。所以现在都提倡用 SHA-256 或者更高级的算法，不仅仅是 MD5，SHA1 也已经不安全了。
|
|
37
0bit 2012-03-13 15:45:09 +08:00
@sinxccc 我们老大说，想要抵御彩虹表，一定要做到一用户一salt。以现在硬件的发展速度，指望着高级算法或者慢速hash，都是不太靠谱的啊。
|
 |
38
leocheng 2012-03-13 17:17:53 +08:00
google的安全工程师早就为数据密码安全做准备了,目标是 以现在的硬件发展速度,争取现在的加密方式10年后不被破解,保证数据安全.
|
Select Language