V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
atan
V2EX  ›  程序员

如果突然有一天 MD5 算法被破解了,可逆了怎么办

  •  
  •   atan ·
    tanshiqi · 2014-04-10 21:51:19 +08:00 · 18592 次点击
    这是一个创建于 3859 天前的主题,其中的信息可能已经有所发展或是发生改变。
    由这次的SSL事件想到的,只是一个假设,如果真有那么一天,互联网世界会怎么样?
    73 条回复    1970-01-01 08:00:00 +08:00
    Livid
        1
    Livid  
    MOD
       2014-04-10 21:53:41 +08:00
    这件事情很多年前已经发生了。

    现在用 MD5 的场合已经非常少了。
    rannnn
        2
    rannnn  
       2014-04-10 21:55:06 +08:00   ❤️ 21
    全宇宙最强的压缩算法诞生了,任意字节数据都可以压缩到128bits
    YY
        3
    YY  
       2014-04-10 21:55:12 +08:00
    完全没什么影响。
    atan
        4
    atan  
    OP
       2014-04-10 21:55:33 +08:00
    大部分数据库的密码还是再用md5(salt+密码)吧
    azhao
        5
    azhao  
       2014-04-10 22:00:07 +08:00   ❤️ 1
    想当年大家都还用明文来存密码呢,也不是这样过了
    webjin
        6
    webjin  
       2014-04-10 22:02:18 +08:00 via Android
    @rannnn ????
    rannnn
        7
    rannnn  
       2014-04-10 22:07:42 +08:00
    @webjin 楼主说的是『如果可逆了怎么办』
    gelupk
        8
    gelupk  
       2014-04-10 22:09:44 +08:00   ❤️ 2
    根据摘要就能把论文全文推导出来,碉堡了
    davidli
        9
    davidli  
       2014-04-10 22:18:29 +08:00   ❤️ 1
    几年前就有一位山大女教授说自己破解了MD5,但不知道后续怎么样了。
    至于根据密文推断明文,肯定不可能,1个密文对应无限多个明文。
    ejin
        10
    ejin  
       2014-04-10 22:45:26 +08:00   ❤️ 3
    楼上的回答楼主可能不太理解,其实很简单

    如果md5“可逆”,那么现在用于验证密码,或者验证文件的hash将毫无意义,相当于明文保存了密码,现在所谓的md5破解,一般是用穷举法,穷举法是任何一种加密算法都无法避免的,除非这种算法非常慢,假如算一次要一年,那你设置一个非常用的密码,就算只有8位,可能别人也无法破解出来

    如果md5可逆
    比如你得到了一个网站的数据库,无论密码是否加了盐,都可以直接破解出明文,嗯,前提是你已经知道加盐的规则,因为加盐本身不是md5算法自带的,相当于加了一层算法,多了一个钥匙而已,但是加再多的钥匙,也永远逃不出md5逆推回来的可能,因为前提是md5算法已经破解,那么推算回去根本不是问题

    还有一种情况就是用来验证文件是否被修改,数字签名技术,如果是采用md5算法,那么在md5算法被破解后,那将存在伪造的可能。谁都无法证明这个文件是否被修改过

    就好像最简单的1+x=5,1+x=6,算法是死的,那么当你的x是4的时候结果是5,因为直接看算法,逆推就行了,不管结果是什么,只要一看前面的算法,就能算出x是什么,这便是md5破解后的情况。


    @rannnn 你所说的压缩算法,根本无需等到md5被破解,比如说qq旋风客户端的离线下载的网址,就是通过md5算法的hash来下载对应文件的,只要这文件被qq旋风下载过,那就可以直接下载到,而且网盘也运用了这种技术,所以你只要有一个hash,就可以得到这个文件,现在的网盘基本上都是如此了

    至于楼主说的“怎么办”,那只能更换新的算法,如果是密码,则还需要更换新的密码。被破解的加密算法,不能用作于安全手段。
    zzh0410
        11
    zzh0410  
       2014-04-10 22:47:06 +08:00
    @davidli 不是破解,只是找到一种理论方法,使得a字符串和b字符串的md5值一致,这样即使不知道a的明文,只要找到b的话,一样可以进入系统。
    ejin
        12
    ejin  
       2014-04-10 23:10:39 +08:00   ❤️ 3
    补充一下 还有一种就是 @zzh0410 说的情况,因为md5再强大,其结果也只有十几个字母数字的可能而已,所以“破解”出来的原文,最多也用16位的字母数字组合就完全够了,再多位数,再大的文件,也只是重复这个结果而已。所以md5理论是用来“验证”的,不是用来“加密”的,加密算法被破解是可以获得原文的,但是md5属于单项加密,只是一个摘要而已。

    所谓摘要,请拿起任意一本书,打开“目录”部分,每个目录的条目和页码,页码也是摘要的一种表现方式
    难道说破解了目录的摘要算法,就能得到任何一本书的内容了吗 这当然是不可能的 呵呵呵

    我之前举例的情况里比如qq旋风下载,比如网盘通过md5来直接获得该hash文件,都避免不了一个情况,那就是“重复”,一个md5结果可以有无数种可能的原文,所以如果想通过md5来获得原文不是破解md5所能做到的。你得到的只是其中一个,或者多个而已

    让我们再回到md5的介绍里,我们会发现,这是一个单向加密算法,是一个内容摘要的算法,这并非是加密算法,而是用作于验证的算法,如果md5被破解,可逆之后不能再用于验证。

    所以被破解后,无需再纠结什么,换加密算法吧,比如说sha1之类的。

    当然最重要的是,任何加密算法都阻止不了暴力破解,除非本机不参与加密过程,比如现在互联网上最常用的验证算法,他的名字叫“验证码”,错一次就报废的“加密算法”。
    lfyzjck
        13
    lfyzjck  
       2014-04-10 23:23:34 +08:00   ❤️ 3
    如果md5可逆,下电影就再也不用焦急的看着进度条了,只要一个32位的md5就好(^_^)
    ejin
        14
    ejin  
       2014-04-10 23:35:12 +08:00
    @lfyzjck
    @rannnn

    白解释这么多了,无语
    rannnn
        15
    rannnn  
       2014-04-10 23:41:29 +08:00
    @ejin
    @lfyzjck
    我们只是借楼主「可逆」这个假设来开个玩笑,并不是不懂这个原理。。。。。。
    感谢解释
    sneezry
        16
    sneezry  
       2014-04-11 00:24:42 +08:00 via iPhone
    md5的有效碰撞已经实现了,md5已经不安全了,可以使用复合加密。
    a3587556
        17
    a3587556  
       2014-04-11 00:34:44 +08:00 via iPhone
    @davidli 你说的那个女教授是王小云吧 她是通过hash碰撞 找到两个加密后hash是一样的数据 当时很轰动
    Precious
        18
    Precious  
       2014-04-11 00:48:39 +08:00 via iPhone
    加密算法为什么不可逆,是因为解密是NP问题或者比NP更难。
    如果P与NP的关系被证明了一定是轰动世界的。很难解决的…不用想了
    dorentus
        19
    dorentus  
       2014-04-11 01:19:50 +08:00
    你没发现很多年前,各开源软件下载的地方提供的 checksum,都已经不用 md5 或者不光光用 md5 了么……

    密码 digest 就算用 md5,也肯定要加盐的(而且正常情况下没人会建议这是这么做;大概上个月论坛这边有人发过一篇讲保存密码策略的文章吧,里面说得比较详细)。

    所以根本没影响吧。
    dorentus
        20
    dorentus  
       2014-04-11 01:20:22 +08:00
    @dorentus s/建议这是这么做/建议只是这么做/
    dndx
        21
    dndx  
       2014-04-11 01:28:27 +08:00
    密码用 bcrypt ,签名用 SHA256

    MD5 的确不应该再用了
    chlx
        22
    chlx  
       2014-04-11 01:38:46 +08:00 via Android
    要可逆,就是P=NP,不止MD5,很多东西都跟着崩溃
    marklrh
        23
    marklrh  
       2014-04-11 01:56:22 +08:00
    @ejin 感谢解释
    likuku
        24
    likuku  
       2014-04-11 02:02:00 +08:00   ❤️ 2
    不是可逆,而是可以在「没得到原版金钥匙的情况下,伪造一把可以开同一把锁的铁钥匙」
    XadillaX
        25
    XadillaX  
       2014-04-11 02:22:42 +08:00
    可逆不可能吧!毕竟MD5是一对多的。一个MD5加密后的密码可以对应好几个明文密码。是哈希就一定存在冲突的,所以不存在可逆这么一说啊。
    qq286735628
        26
    qq286735628  
       2014-04-11 02:30:52 +08:00 via iPhone
    MD5是摘要,不是用来加密的
    atan
        27
    atan  
    OP
       2014-04-11 08:21:51 +08:00 via iPad
    那么当计算机的性能达到可以轻松完成穷举的时候呢
    jimrok
        28
    jimrok  
       2014-04-11 08:30:45 +08:00
    如果那天到了,大概所有的资料只需要存储个MD5,非常节省存储空间。火星和地球间的通信非常快速,发送一个MD5,就可以将整个火星的信息猜测出来,无需传送上T的数据。
    echo1937
        29
    echo1937  
       2014-04-11 08:39:38 +08:00
    rrfeng
        30
    rrfeng  
       2014-04-11 08:46:45 +08:00
    @ejin
    你最后那个离线下载的例子是不恰当的。 你通过查找 hash ,根据 hash/文件 对应表来获得一个文件(的地址)然后下载,跟压缩/可逆一点儿关系也没有,取决于hash的唯一性。

    『最强压缩算法』的重点在于可以有 hash 逆推出源文件内容,所以就是你根本不用去服务器搞什么离线下载啊,网页上复制一串字符,往自己电脑一个程序里一丢,10G 的电影就出现了……

    当然这只是个玩笑。

    另外 md5 碰撞生成器貌似网上就能下到了……
    RelativeLayout
        31
    RelativeLayout  
       2014-04-11 08:47:41 +08:00 via iPhone   ❤️ 1
    请搜索 山东大学 王小云
    tarsier
        32
    tarsier  
       2014-04-11 08:54:41 +08:00 via Android
    md5什么时候成了压缩算法了?顶多算一个信息摘要算法吧
    raincious
        33
    raincious  
       2014-04-11 08:57:10 +08:00
    @ejin 楼上很明显Lost point了嗯。 @rannnn 的意思是这样的:任何文件都能用128bit进行压缩,然后“解压缩”(如果MD5被破解)。那么自然MD5就是宇宙最强的压缩算法了。

    这个玩笑开得简明扼要,那个……长篇大论来驳斥没必要……,再有,你的假定也是以MD5还没破解为前提。

    不过玩笑嘛,得到笑点,笑笑就好。
    teddy1004
        34
    teddy1004  
       2014-04-11 09:06:15 +08:00 via iPhone
    不是已经被中国女博士搞定了吗
    kstsca
        35
    kstsca  
       2014-04-11 09:07:10 +08:00
    @raincious 超出多少字节肯定是截断的,譬如他可能只作用于1024前字节进行运算。所以MD5会有出现相同的,这一点没有说MD5 100%唯一。
    towser
        36
    towser  
       2014-04-11 09:12:21 +08:00
    @lfyzjck 然后看着还原原文的进度条。。。
    skyworker
        37
    skyworker  
       2014-04-11 09:22:32 +08:00
    即使不能破解,如果不用salt的话,很多常见的MD5都被做成了彩虹表了,不是太复杂的MD5都能通过彩虹表的数据库逆向获取。
    Sherlockhlt
        38
    Sherlockhlt  
       2014-04-11 09:36:59 +08:00
    1. MD5是摘要,不是加密算法
    2. 摘要不可能可逆的,信息不够
    3. 几年前国内教授发表了产生和目标MD5摘要值一样的算法,这个问题是挺严重的,因为MD5摘要通常用来判断数据是否被篡改过,现在就是可以篡改后用算法使得MD5值不变
    4. 数据库中存储用户密码的MD5值,是为了防止入侵者从数据库得到用户密码明文后去登陆用户的其他账号,还有入侵者拿到MD5值后也无法直接用md5(密码明文)假装成用户登陆他的账号,因为服务器代码会进行一次md5求值后和数据库的md5(密码明文)值对比,他使用md5(密码明文)值去登陆后只会得到MD5(md5(密码明文))。当然他也可以用3里面的算法去获得一个和密码明文有同样md5值的字符串。

    以上第4条是我的想法,没看过确切的资料,不敢断论,有什么问题欢迎探讨
    bakac
        39
    bakac  
       2014-04-11 09:39:09 +08:00
    md5本身就是有损算法,出生那一刻注定不可逆,但是可以通过碰撞的方法猜测一些字符串,那些就是所谓的彩虹表.但是现在大多数网站都不直接md5,而是使用加盐,或者多次分段md5的方法hash
    jnriver
        40
    jnriver  
       2014-04-11 09:46:32 +08:00
    @lfyzjck 然后等解压比下载还慢。。 想想也蛮带感的,节省流量!
    ichou
        41
    ichou  
       2014-04-11 10:15:55 +08:00
    MD5 是一种加密算法? 加密算法? 加密算法?!!
    讨论了这么多,好像大家都爱这么说
    200
        42
    200  
       2014-04-11 10:18:17 +08:00
    hash算法可以把任意长度的内容 编码到固定长度的hash 无穷种输入对应有穷种输出 简单的抽屉原理就明白这个过程不是一一映射 既然不是一一映射那怎么可能有可逆的方法呢
    优秀的hash算法基本上要满足对于下面三种任务都很难实现
    1、给定y 找x 使得hash(x)=y
    2、给定x 找x' 使得hash(x')=hash(x)
    3、任意找到x1 x2 使得hash(x1)=hash(x2)
    王小云教授所做的对于md5的研究 主要是解决了第三个问题 可以在相对较短的时间内构造出来两个内容不同的原文 使得这两个原文md5之后的结果相同
    nocoo
        43
    nocoo  
       2014-04-11 10:18:36 +08:00   ❤️ 1
    一句话,信息熵。
    只能碰撞,无法真正破解。因为大量信息在hash过程中损失掉了。
    Smartype
        44
    Smartype  
       2014-04-11 10:34:13 +08:00
    @Livid 你可能说的是山东大学的王小云,那应该只是发现了碰撞而已。
    garipan
        45
    garipan  
       2014-04-11 10:37:27 +08:00 via Android
    2004年,山东大学教授王小云公布了md5的破解报告,但是,这一报告只是证明存在一种可以产生强特定碰撞的方法,但是要伪造数字签名必须能产生弱特定碰撞。
    garipan
        46
    garipan  
       2014-04-11 10:40:41 +08:00 via Android
    我想说,比特币用的就是MD5
    XDA
        47
    XDA  
       2014-04-11 10:43:40 +08:00
    作为校友现场听过王小云 展涛的讲座,没记错的话二人均师从潘承洞。
    ntower
        48
    ntower  
       2014-04-11 10:55:00 +08:00
    @dorentus , 求那个密码保存策略的文章. v2ex上没搜到.
    xoxo
        49
    xoxo  
       2014-04-11 10:57:52 +08:00
    量子计算机诞生的时候,MD5也许100%可逆
    Ever
        50
    Ever  
       2014-04-11 11:30:32 +08:00
    @garipan btc用的sha256.
    mdjhny
        51
    mdjhny  
       2014-04-11 11:35:43 +08:00   ❤️ 2
    @ntower
    英文原版: https://crackstation.net/hashing-security.htm Salted Password Hashing - Doing it Right
    中文翻译版: http://blog.jobbole.com/61872/ 加盐密码哈希:如何正确使用
    wy315700
        52
    wy315700  
       2014-04-11 11:49:40 +08:00
    @garipan 不是sha256吗
    explon
        53
    explon  
       2014-04-11 12:58:32 +08:00
    怎么逆? 我hash一个1G的文件你倒是逆出来给我看看啊
    stackpop
        54
    stackpop  
       2014-04-11 13:07:17 +08:00
    @explon 别人不是说的如果么,哈哈,所以说全宇宙最牛逼的压缩算法诞生了啊,100G都能给你逆出来

    md5不是加密算法,是hash,更像是数据的指纹而不是数据本身的另一种存在形式, 其实能构造出碰撞就算破解了。

    假设这样的情况,某公司发布了一个版本,并提供了一个hash,用来防止文件被篡改。但是假如我们发现了一种构造碰撞的方法,就可以把恶意代码植入进去,并保证hash没有变。使用md5做完整性校验没有意义了。
    stackpop
        55
    stackpop  
       2014-04-11 13:09:35 +08:00
    数据压缩是有极限的,香农好像有证明,忘了
    stackpop
        56
    stackpop  
       2014-04-11 13:14:02 +08:00
    曾与王小云共同攻破完整 MD5 算法的中科院的冯登国与长沙国防科大的谢涛最近在 IACR
    上发布了一篇题为《仅用一个消息块实现 MD5 碰撞》的文章。出于安全因素的考虑,文
    章中并未公开具体实现方法,但他们向全球密码学爱好者发出挑战:第一个在 2013 年 1
    月 1 日之前找出新的单块碰撞的人将获得一万美元的奖励。

    他们公布的产生碰撞的消息块为:

    0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,0x854f709e,
    0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a

    0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,0x854f749e,
    0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0xdc15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a

    这两个消息块有两处不同,但 MD5 均为 0xf999c8c9 0xf7939ab6 0x84f3c481 0x1457cb2
    3
    loading
        57
    loading  
       2014-04-11 13:30:17 +08:00 via iPhone   ❤️ 1
    根据pi(对,3.1415…)的无限不循环,有人提出任何字符串在pi里都有,然后当时我就想,下电影不就是pi起始位和末位加格式么…哈哈

    还有个快速定位的牛逼算法呢…
    marginleft
        58
    marginleft  
       2014-04-11 16:07:36 +08:00
    @rannnn 所以,应该不可能。
    nicai000
        59
    nicai000  
       2014-04-11 17:25:54 +08:00
    @rannnn
    decken
        60
    decken  
       2014-04-11 19:29:02 +08:00
    @loading
    "下电影不就是pi起始位和末位加格式么"
    这句话什么意思呢?
    binux
        61
    binux  
       2014-04-11 19:34:01 +08:00
    @loading 你有没有想过起始位加结束位有几G,电影那么大?
    loading
        62
    loading  
       2014-04-11 20:26:31 +08:00 via iPhone
    @binux 想过的,目前还是比较难解决,哈
    nanpuyue
        63
    nanpuyue  
       2014-04-11 20:49:48 +08:00
    @loading 有没有想过,如果真有这么一回事,或许用来描述起始位或结束位的数字的容量都会大过文件本身。
    liuyl
        64
    liuyl  
       2014-04-11 20:51:56 +08:00
    @loading 你这理论就跟有人说“世界上有那么一串0,1的组合是我跟Emma Watson和Jeniffer Lawrence玩双飞的视频”一样。。
    loading
        65
    loading  
       2014-04-11 21:16:26 +08:00 via iPhone
    @liuyl 不是我的想法,是别人的,当时还有在线应用,我还查了我名字在第几位…

    现在找不到了

    @nanpuyue 别太认真,起始最难是找出那段对应的,不是么?
    poboy
        66
    poboy  
       2014-04-11 21:29:10 +08:00
    没有最安全,只有更安全,尽力就好吧
    julyclyde
        67
    julyclyde  
       2014-04-11 22:13:30 +08:00
    无限数量的输入产生有限数量的输出,则必然存在信息损失,则必然存在多输入对一输出,则必然不可逆
    Quaintjade
        68
    Quaintjade  
       2014-04-11 23:32:26 +08:00 via Android
    SSL证书已经不用MD5来签名了,准确地说是浏览器会认定MD5算法签名的证书不安全。
    Quaintjade
        69
    Quaintjade  
       2014-04-12 00:02:23 +08:00 via Android
    像SHA哈希算法,是有预定使用年限的,比如20~30年。SHA-1年限不多了,以后会用SHA-2, SHA-3。需要指出的是,SHA-0,1,2,3是完全不同的算法。

    而像RSA加密算法,则完全依靠大数因数分解的难度。
    SSL目前用的RSA最低长度已经从128bit升为256bit。
    xcc7624
        70
    xcc7624  
       2014-04-12 00:36:29 +08:00
    MD5本身就已经不怎么安全了。
    lincanbin
        71
    lincanbin  
       2014-04-12 08:57:10 +08:00 via Android
    MD5加密过程信息丢失,所以不可逆
    msg7086
        72
    msg7086  
       2014-04-12 17:40:23 +08:00
    一直到43楼才有人道出重点
    sdpfoue
        73
    sdpfoue  
       2014-04-12 22:27:55 +08:00
    如果打码片可以去码了,这个世界会更好吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1117 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 19:24 · PVG 03:24 · LAX 12:24 · JFK 15:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.