V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zhuang
V2EX  ›  信息安全

逆向一条 MD5-32 大概需要多少运算能力?

  •  
  •   zhuang · 2012-03-09 13:36:14 +08:00 · 12120 次点击
    这是一个创建于 4623 天前的主题,其中的信息可能已经有所发展或是发生改变。
    起因大家都懂得,这里只是做个简单的计算,判断什么的我不会写的。
    大前提是: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
    39 条回复    1970-01-01 08:00:00 +08:00
    momou
        1
    momou  
       2012-03-09 13:50:36 +08:00
    学习,等高人。。。
    GordianZ
        2
    GordianZ  
    MOD
       2012-03-09 13:53:59 +08:00
    关于¥我插一个嘴,如果已经开始爆破了,估计就没用编码直接上HEX了。而且原文应该不在彩虹表里面。

    再且,9位数字的彩虹表用不了1GB啊。
    1e9种组合,原文2字节,散列16字节 = 18e9 bytes = 18GB.
    但是不可否认包含这次的明文的彩虹表肯定不止1TB.
    zhuang
        3
    zhuang  
    OP
       2012-03-09 14:03:56 +08:00
    @GordianZ

    MD5 计算不是说一段一段的,是要形式如:
    md5(moc.xe2v1861xxxxxxx¥0XXXXX)=32-hash
    这种作为一个待运算的整体对待的。

    拿到密文的人现场计算彩虹表和爆破是没有区别的,做表运算量更大。
    lch21
        4
    lch21  
       2012-03-09 14:14:20 +08:00
    8位任意字符组合,半个小时搞定。

    100张显卡集群

    实践检验过的
    d5d
        5
    d5d  
       2012-03-09 14:14:46 +08:00
    b0ba5f33e8a56957f7700e3ad2158c4d:60
    zhuang
        6
    zhuang  
    OP
       2012-03-09 14:33:47 +08:00
    @lch21

    8 位没有什么意义……这个解密本质上是近似于 15 位纯数字量级。
    话说您真见过 100 张显卡的集群吗?呵呵。
    lch21
        7
    lch21  
       2012-03-09 14:46:17 +08:00
    @zhuang 你了解 Bitcoin 挖矿吗?呵呵
    bruce
        8
    bruce  
       2012-03-09 14:49:30 +08:00
    @zhuang 有些事,看看就算了,没必要那么认真
    zhuang
        9
    zhuang  
    OP
       2012-03-09 14:55:18 +08:00
    @lch21

    应该说这个站点里第一个因为 bitcoin 挣到钱的就是我了,而那个时候中文环境没有任何关于 bitcoin 的介绍。v2ex/twitter 上很多人都应该对此有印象。还有我是 bitcoin 黑。

    另外,我还接触过前几年曾经的中国第一超算集群。我个人的体会是,要充分调用集群的运算能力,需要的准备工作很麻烦。比如配置你的任务调度系统,再比如实际调用之前的反复验证。

    至于 100 张显卡的集群,我真的只能笑一笑。
    zhuang
        10
    zhuang  
    OP
       2012-03-09 14:56:08 +08:00
    @bruce

    谢谢指教。
    cooka
        11
    cooka  
       2012-03-09 14:58:41 +08:00
    @zhuang 破解者设计密码字典(含v2ex,186)对这个(20位以上字符串)反向计算有没有用处呢?
    或者说对反向的帮助有多大?
    lch21
        12
    lch21  
       2012-03-09 15:01:49 +08:00
    @zhuang "中国第一超算集群", 你NB,呵呵
    zhuang
        13
    zhuang  
    OP
       2012-03-09 15:10:46 +08:00
    @cooka

    不是很理解你的问题,我猜你是想问,爆破用的字典有什么作用吧?

    前面说过 MD5 是一个从“有限信息”去猜“原始信息”的过程,爆破过程就是,我不知到原文是什么,但是我知道原文的可能组合是什么,把这些所有的组合写下来,一一尝试比对即可。
    为了加快速度,这个可能的组合要尽量少,但是还一定要保证不把原文排除掉。

    一般来说,最难的就是常见的“大小写特殊符号加数字组合”。在这个例子里,假如我知道密码构成是 v2ex.com+11 位手机号的格式,实际的运算量和纯粹计算 11 位手机号组合差不多。
    zhuang
        14
    zhuang  
    OP
       2012-03-09 16:22:41 +08:00
    @GordianZ

    发现我写错了,引用来源里有,应该是9位以内数字字母混合的是 800GB+ 。
    Shared
        15
    Shared  
       2012-03-11 02:32:24 +08:00
    @GordianZ 不同编码的HEX值是不同的,即使是同样的¥使用Unicode的不同编码方式(UTF8,UTF16等等)得到的结果也不同。所以破解的人最后还得注意一下编码问题?要不然很可能得到的结果是一堆乱码,哈哈
    afterain
        16
    afterain  
       2012-03-11 14:42:11 +08:00 via Android
    回顾整个事件,这个帖子无论是从技术还是态度上来说都是非常值得学习的。
    其他的……
    aristotle9
        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集群,现有的运算能力还不足以对现行的密码体系造成决定性的打击.
    大神打架是拼数量级的.
    sigone
        18
    sigone  
       2012-03-11 16:04:37 +08:00 via Android
    舍得 舍得 ... 呵呵
    sigone
        19
    sigone  
       2012-03-11 16:07:46 +08:00 via Android
    其实我说的是一句密文,哪位童鞋能算出他的愿意!
    Livid
        20
    Livid  
    MOD
       2012-03-12 09:08:22 +08:00
    谢谢 @zhuang 的这个帖子,受教了。

    昨天晚上自己做了一些实验,这个事情我想应该接近得出结论了。

    http://www.v2ex.com/t/29393

    我喜欢并且感谢大家从理科角度来论证这个问题。:)
    haha1903
        21
    haha1903  
       2012-03-12 09:33:06 +08:00
    而且要求是逆向(不是寻找碰撞),这一句,我理解就是不可能的。
    ofan
        22
    ofan  
       2012-03-12 10:09:20 +08:00
    md5是不可逆的,所谓破解都是找碰撞
    zhuang
        23
    zhuang  
    OP
       2012-03-12 11:40:31 +08:00
    @ofan @haha1903
    你们说得都很对,我这里表述不清楚。hash 函数一般要求尽量“散”,即原文变化很小,hash 结果要差距比较大。在原文空间受限的情况下,可以认为那个“碰撞结果”就是原文,不过说到底就是碰撞而已。
    hq5261984
        24
    hq5261984  
       2012-03-12 12:12:23 +08:00
    关于MD5逆向你去请教王小云吧。听说她老人家逆向不用计算机直接在纸上演算,至于时间就不晓得了。
    tokki
        25
    tokki  
       2012-03-12 12:36:49 +08:00
    @hq5261984 这个太牛掰了吧-。-
    hq5261984
        26
    hq5261984  
       2012-03-12 19:26:48 +08:00
    @tokki 我看过她的介绍,据说她不会编程虾米的,电脑也用得不好。
    tokki
        27
    tokki  
       2012-03-12 20:10:26 +08:00
    @hq5261984 我也看了 科学家啊 就是不一样啊
    Ricepig
        28
    Ricepig  
       2012-03-12 20:25:51 +08:00
    @hq5261984 她的研究使md5基本上宣告完蛋。

    其实给定一个md5,她的算法可以找到一个串,使得这个串的md5等于给定的那个

    但是这个串不一定是原来那个串
    iwege
        29
    iwege  
       2012-03-12 20:30:23 +08:00
    @hq5261984
    那个不是逆向,那个是碰撞 md5碰撞,不算是可逆,只是让md5验证失效而已。
    Ricepig
        30
    Ricepig  
       2012-03-12 20:41:41 +08:00
    @zhuang
    其实CPU的峰值与GPU峰值差距已经没有那么大了,i7 920的峰值已经在100Gflops左右。最多比显卡低一个数量级而已,所以并不能忽略。当控制语句较多时,CPU和GPU的差距将会进一步缩小。当前很多论文的比较都是将GPU优化的实现与CPU未优化的实现甚至是单核CPU相比。

    当然,就暴力法破解md5来说,GPU相对会有点优势,但是优势也不如你说的“CPU小太多数量级”这么多了。
    zhuang
        31
    zhuang  
    OP
       2012-03-12 21:18:47 +08:00
    @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 基本表明了这一点。
    Ricepig
        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的效率往往还是要高的。只是不如很多人想的那么多。
    Ricepig
        33
    Ricepig  
       2012-03-13 06:25:56 +08:00
    @zhuang 再另外,其实GPU的等效x86 flops会比它自己所标识的flops要低,尤其是针对双精度和整数。整数要看GPU的架构,有些慢得不太多。双精度就要低很多了,因为x86的双精度运算是内部80位外部64位的。
    liyandong
        34
    liyandong  
       2012-03-13 07:57:23 +08:00
    只听说一牛人租了重量级的亚马逊云碰撞Md5,字母数字符号复杂密码,6小时
    0bit
        35
    0bit  
       2012-03-13 08:34:37 +08:00
    @Ricepig 我怎么记得王小云只是能构造两个md5相同的原文,而不是根据已有的md5来构造出来原文呢。如果根据md5构造原文能实现的话,那现在被广泛应用的这种基于md5等hash的密码存储体系,可真的就要崩溃了。(虽然现在也快崩溃了)
    sinxccc
        36
    sinxccc  
       2012-03-13 08:44:15 +08:00
    @0bit 您的理解是对的。所以现在都提倡用 SHA-256 或者更高级的算法,不仅仅是 MD5,SHA1 也已经不安全了。
    0bit
        37
    0bit  
       2012-03-13 15:45:09 +08:00
    @sinxccc 我们老大说,想要抵御彩虹表,一定要做到一用户一salt。以现在硬件的发展速度,指望着高级算法或者慢速hash,都是不太靠谱的啊。
    leocheng
        38
    leocheng  
       2012-03-13 17:17:53 +08:00
    google的安全工程师早就为数据密码安全做准备了,目标是 以现在的硬件发展速度,争取现在的加密方式10年后不被破解,保证数据安全.
    haha1903
        39
    haha1903  
       2012-03-14 09:37:02 +08:00
    @Ricepig @hq5261984
    你们肯定是没看过王小云的论文,根本不是这样的,实际上是 @0bit 说得才对,即使是这样,已经让所有基于 md5 的数字证书和签名没什么用处了,但通过 md5 加密的密文,还是依然没问题的,你还是没办法直接找到碰撞。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   987 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 45ms · UTC 22:12 · PVG 06:12 · LAX 14:12 · JFK 17:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.