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

md5

一天

可逆

73 条回复 • 1970-01-01 08:00:00 +08:00

1

Livid

MOD

2014-04-10 21:53:41 +08:00

这件事情很多年前已经发生了。

现在用 MD5 的场合已经非常少了。

2

rannnn

2014-04-10 21:55:06 +08:00

21

全宇宙最强的压缩算法诞生了，任意字节数据都可以压缩到128bits

3

YY

2014-04-10 21:55:12 +08:00

完全没什么影响。

4

atan

OP

2014-04-10 21:55:33 +08:00

大部分数据库的密码还是再用md5（salt＋密码）吧

5

azhao

2014-04-10 22:00:07 +08:00

1

想当年大家都还用明文来存密码呢，也不是这样过了

6

webjin

2014-04-10 22:02:18 +08:00 via Android

@rannnn ？？？？

7

rannnn

2014-04-10 22:07:42 +08:00

@webjin 楼主说的是『如果可逆了怎么办』

8

gelupk

2014-04-10 22:09:44 +08:00

2

根据摘要就能把论文全文推导出来，碉堡了

9

davidli

2014-04-10 22:18:29 +08:00

1

几年前就有一位山大女教授说自己破解了MD5，但不知道后续怎么样了。
至于根据密文推断明文，肯定不可能，1个密文对应无限多个明文。

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，就可以得到这个文件，现在的网盘基本上都是如此了

至于楼主说的“怎么办”，那只能更换新的算法，如果是密码，则还需要更换新的密码。被破解的加密算法，不能用作于安全手段。

11

zzh0410

2014-04-10 22:47:06 +08:00

@davidli 不是破解，只是找到一种理论方法，使得a字符串和b字符串的md5值一致，这样即使不知道a的明文，只要找到b的话，一样可以进入系统。

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之类的。

当然最重要的是，任何加密算法都阻止不了暴力破解，除非本机不参与加密过程，比如现在互联网上最常用的验证算法，他的名字叫“验证码”，错一次就报废的“加密算法”。

13

lfyzjck

2014-04-10 23:23:34 +08:00

3

如果md5可逆，下电影就再也不用焦急的看着进度条了，只要一个32位的md5就好（^_^）

14

ejin

2014-04-10 23:35:12 +08:00

@lfyzjck
@rannnn

白解释这么多了，无语

15

rannnn

2014-04-10 23:41:29 +08:00

@ejin
@lfyzjck
我们只是借楼主「可逆」这个假设来开个玩笑，并不是不懂这个原理。。。。。。
感谢解释

16

sneezry

2014-04-11 00:24:42 +08:00 via iPhone

md5的有效碰撞已经实现了，md5已经不安全了，可以使用复合加密。

17

a3587556

2014-04-11 00:34:44 +08:00 via iPhone

@davidli 你说的那个女教授是王小云吧她是通过hash碰撞找到两个加密后hash是一样的数据当时很轰动

18

Precious

2014-04-11 00:48:39 +08:00 via iPhone

加密算法为什么不可逆，是因为解密是NP问题或者比NP更难。
如果P与NP的关系被证明了一定是轰动世界的。很难解决的…不用想了

19

dorentus

2014-04-11 01:19:50 +08:00

你没发现很多年前，各开源软件下载的地方提供的 checksum，都已经不用 md5 或者不光光用 md5 了么……

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

所以根本没影响吧。

20

dorentus

2014-04-11 01:20:22 +08:00

@dorentus s/建议这是这么做/建议只是这么做/

21

dndx

2014-04-11 01:28:27 +08:00

密码用 bcrypt ，签名用 SHA256

MD5 的确不应该再用了

22

chlx

2014-04-11 01:38:46 +08:00 via Android

要可逆，就是P=NP，不止MD5，很多东西都跟着崩溃

23

marklrh

2014-04-11 01:56:22 +08:00

@ejin 感谢解释

24

likuku

2014-04-11 02:02:00 +08:00

2

不是可逆，而是可以在「没得到原版金钥匙的情况下，伪造一把可以开同一把锁的铁钥匙」

25

XadillaX

2014-04-11 02:22:42 +08:00

可逆不可能吧！毕竟MD5是一对多的。一个MD5加密后的密码可以对应好几个明文密码。是哈希就一定存在冲突的，所以不存在可逆这么一说啊。

26

qq286735628

2014-04-11 02:30:52 +08:00 via iPhone

MD5是摘要，不是用来加密的

27

atan

OP

2014-04-11 08:21:51 +08:00 via iPad

那么当计算机的性能达到可以轻松完成穷举的时候呢

28

jimrok

2014-04-11 08:30:45 +08:00

如果那天到了，大概所有的资料只需要存储个MD5，非常节省存储空间。火星和地球间的通信非常快速，发送一个MD5，就可以将整个火星的信息猜测出来，无需传送上T的数据。

29

echo1937

2014-04-11 08:39:38 +08:00

@qq286735628 +1

30

rrfeng

2014-04-11 08:46:45 +08:00

@ejin
你最后那个离线下载的例子是不恰当的。你通过查找 hash ，根据 hash/文件对应表来获得一个文件（的地址）然后下载，跟压缩/可逆一点儿关系也没有，取决于hash的唯一性。

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

当然这只是个玩笑。

另外 md5 碰撞生成器貌似网上就能下到了……

31

RelativeLayout

2014-04-11 08:47:41 +08:00 via iPhone

1

请搜索山东大学王小云

32

tarsier

2014-04-11 08:54:41 +08:00 via Android

md5什么时候成了压缩算法了？顶多算一个信息摘要算法吧

33

raincious

2014-04-11 08:57:10 +08:00

@ejin 楼上很明显Lost point了嗯。 @rannnn 的意思是这样的：任何文件都能用128bit进行压缩，然后“解压缩”（如果MD5被破解）。那么自然MD5就是宇宙最强的压缩算法了。

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

不过玩笑嘛，得到笑点，笑笑就好。

34

teddy1004

2014-04-11 09:06:15 +08:00 via iPhone

不是已经被中国女博士搞定了吗

35

kstsca

2014-04-11 09:07:10 +08:00

@raincious 超出多少字节肯定是截断的，譬如他可能只作用于1024前字节进行运算。所以MD5会有出现相同的，这一点没有说MD5 100%唯一。

36

towser

2014-04-11 09:12:21 +08:00

@lfyzjck 然后看着还原原文的进度条。。。

37

skyworker

2014-04-11 09:22:32 +08:00

即使不能破解，如果不用salt的话，很多常见的MD5都被做成了彩虹表了，不是太复杂的MD5都能通过彩虹表的数据库逆向获取。

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条是我的想法，没看过确切的资料，不敢断论，有什么问题欢迎探讨

39

bakac

2014-04-11 09:39:09 +08:00

md5本身就是有损算法,出生那一刻注定不可逆,但是可以通过碰撞的方法猜测一些字符串,那些就是所谓的彩虹表.但是现在大多数网站都不直接md5,而是使用加盐,或者多次分段md5的方法hash

40

jnriver

2014-04-11 09:46:32 +08:00

@lfyzjck 然后等解压比下载还慢。。想想也蛮带感的，节省流量！

41

ichou

2014-04-11 10:15:55 +08:00

MD5 是一种加密算法？加密算法？加密算法？！！
讨论了这么多，好像大家都爱这么说

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之后的结果相同

43

nocoo

2014-04-11 10:18:36 +08:00

1

一句话，信息熵。
只能碰撞，无法真正破解。因为大量信息在hash过程中损失掉了。

44

Smartype

2014-04-11 10:34:13 +08:00

@Livid 你可能说的是山东大学的王小云，那应该只是发现了碰撞而已。

45

garipan

2014-04-11 10:37:27 +08:00 via Android

2004年，山东大学教授王小云公布了md5的破解报告，但是，这一报告只是证明存在一种可以产生强特定碰撞的方法，但是要伪造数字签名必须能产生弱特定碰撞。

46

garipan

2014-04-11 10:40:41 +08:00 via Android

我想说，比特币用的就是MD5

47

XDA

2014-04-11 10:43:40 +08:00

作为校友现场听过王小云展涛的讲座，没记错的话二人均师从潘承洞。

48

ntower

2014-04-11 10:55:00 +08:00

@dorentus , 求那个密码保存策略的文章. v2ex上没搜到.

49

xoxo

2014-04-11 10:57:52 +08:00

量子计算机诞生的时候，MD5也许100%可逆

50

Ever

2014-04-11 11:30:32 +08:00

@garipan btc用的sha256.

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/ 加盐密码哈希：如何正确使用

52

wy315700

2014-04-11 11:49:40 +08:00

@garipan 不是sha256吗

53

explon

2014-04-11 12:58:32 +08:00

怎么逆? 我hash一个1G的文件你倒是逆出来给我看看啊

54

stackpop

2014-04-11 13:07:17 +08:00

@explon 别人不是说的如果么，哈哈，所以说全宇宙最牛逼的压缩算法诞生了啊，100Ｇ都能给你逆出来

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

假设这样的情况，某公司发布了一个版本，并提供了一个hash，用来防止文件被篡改。但是假如我们发现了一种构造碰撞的方法，就可以把恶意代码植入进去，并保证hash没有变。使用md5做完整性校验没有意义了。

55

stackpop

2014-04-11 13:09:35 +08:00

数据压缩是有极限的，香农好像有证明，忘了

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