深入理解 MD5 消息摘要算法和在密码存储中的应用及安全隐患

MD5 算法相信很多开发人员都听说过, 一个最常见的使用到它的地方就是密码的存储.

当然, 很多人会说, 这个算法已经不太安全了, 确实如果你想更安全的保存密码, 则应该考虑其它更安全的算法, 不过这不属于此次讨论的主题.

什么是 MD5

MD5 是一种算法, MD5 中的 MD 代表 Message Digest, 也即信息摘要.

至于数字 5, 则因它是从更早的 MD4 算法改进而来, 因此得名 MD5.

所以 MD5 即是信息摘要算法第五版.

什么是信息摘要算法

那什么又是信息摘要算法呢? 它本质上就是一个哈希函数(hash function).

又叫散列函数.

那什么又是哈希函数呢? 它是指这样一种函数: 它能把任意大小的数据映射(map)为一个固定大小的值.

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

哈希函数所返回的这个值称为哈希值(hash value), 又称为哈希码(hash codes), 或直接简称为哈希(hash).

具体例子

单纯地这样去讲会比较抽象, 因此这里引入具体例子来说明, 以 Java 为例, 可以这样去计算 MD5:

public void rawMd5() throws NoSuchAlgorithmException {byte[] bytes = "hello".getBytes(StandardCharsets.UTF_8);MessageDigest md = MessageDigest.getInstance("MD5");byte[] md5 = md.digest(bytes);
}

注: 以上代码计算了"hello"这个字符串对应的 utf-8 字节数组的 md5 的值.

另注: 因为摘要计算的输入是一个字节数组, 如果要计算字符串的摘要值, 则要转成某种编码的字节数组, 为保持一致, 应始终显式使用同一种编码, 比如 utf-8.

从以上代码中也不难看出, 一个 MD5 函数的输入和输出都是字节数组 byte[].

而代码中不能直接体现的一点则是: 输入可以是任意大小的字节数组, 输出则是固定大小的字节数组.

对于 MD5 算法而言, 这个输出值是一个固定大小为 16 字节的数组, 然后因为每个字节(byte)有 8 个位(bit), 所以最终的输出值是一个 16 × 8 = 128 位的二进制数. MD5 的值就是一个 128 位的二进制大整数.

比如下面就是一个具体的 MD5 的值, 以原始的 128 位二进制形式表示:
10001000100100011001000111110000100011111000000111010010110010101100010111101010000110011011110000111011111101111101100110111110

这个 MD5 值实际是对我的网站域名 xiaogd.net 作摘要的结果.

这个值的二进制形式实在是长得不要不要的, 所以一般会转换为十六进制形式, 共 16 组具体为: 88 91 91 f0 8f 81 d2 ca c5 ea 19 bc 3b f7 d9 be. 依然还是很长, 但比二进制好多了.

随便说一句, IPv6 的地址也是 128 bit 的, 所以也是像这般变态的长, 写成 16 进制也还是很长, 压根记不住…

最后通常还会去掉空格写成一个紧凑的 32 个字符的字符串的形式: 889191f08f81d2cac5ea19bc3bf7d9be, 也即是我们最常见到的 MD5 值的形式.

但请不要误解, MD5 的值并不是一个字符串, 更不是什么字母都能出现在里边的.

一个完整的代码示例如下, 使用 apache commons-codec 工具包的 Hex 工具类将字节数组转为 16 进制字符串形式:

package net.xiaogd.demo.basic;import org.apache.commons.codec.binary.Hex;
import org.junit.Assert;
import org.junit.Test;import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;public class Md5Test {@Testpublic void calcMd5() {Assert.assertEquals("889191f08f81d2cac5ea19bc3bf7d9be", md5("xiaogd.net"));}public static String md5(String input) {try {byte[] bytes = input.getBytes(StandardCharsets.UTF_8);MessageDigest md = MessageDigest.getInstance("MD5");byte[] hash = md.digest(bytes);// use apache commons-codec util jarreturn Hex.encodeHexString(hash);} catch (NoSuchAlgorithmException e) {throw new RuntimeException("md5 not support!", e);}}
}

所以如果你直接存储这个整数值的字节数组, 你只需要 16 字节的空间, 但如果你存储转为 16 进制表示的字符串, 因为最终结果是 32 个字符, 那么就至少需要 32 字节(ASCII) 空间了.

在数据库存储时, 通常会存为固定长度的 char(32), 编码选 ASCII, 因为所有字符都是 ASCII 字符, 而 ASCII 字符每个只需一字节空间去保存, 如果用其它字符集, 需要的空间可能会翻倍, 甚至三倍, 四倍.

MD5 算法的特性

其实从上面的结果中, 我们已知道了 MD5 算法的一个特性, 那就是它的结果是一个固定 16 字节数组的值.

也就是说不管你的输入是多长, 输出的结果都是那么长. 你输入是一个字节, 输出也是 16 字节, 你输入是 100 个字节, 输出也还是 16 字节.

因为 MD5 算法经常用在密码保存方面, 有些人就认为它是一种加密算法, 那么这种理解其实是有问题的. MD5 的所谓"加密"效果显然与一般的加密-解密算法中的加密不是一回事.

MD5 是做摘要, 而不是加密, 如果它是加密, 之后还能解密的那种算法, 一个很自然的问题就是, 它输出是固定的, 这就带来一个问题, 就像前面说的, 输入 100 个字节, 输出还是 16 字节, 假如我的密码就是一个很变态的 100 个字符长度的, 经过你的 MD5 所谓"加密"后, 成了一个 32 字符的值, 字符变少了, 信息肯定发生了丢失, 你怎么可能从更少的 32 字符解密回去 100 个字符呢? 显然是不可能办到的.

另外一个显然的问题则是, 加解密算法是要求密钥的(或是一般意义上的密码), 然后在加密以及解密的过程, 密钥是要作为参数参与方法调用的, 而我们看前述 MD5 值生成的代码, 并没有涉及密钥.

而以上讨论又自然引出了 MD5 的又一特性, MD5 的所谓"加密", 实际上是 “one-way hash”, 也即是单向的不可逆的 hash 过程, 也即是不管你的输入字节数是比输出字节数大还是小, 你都不可能从输出值去反推到输入值.

这是 MD5 作为一种 密码学哈希函数(CHF: Cryptographic Hash Function) 所必须具备的一个特性.

不严谨的说法就是它是无法"解密"的, 但前面说了, 既然它都不是"加密", 也没有密钥, 也自然就无所谓解密了.

当然, 说到这里, 有人可能又要争辩说, MD5 是可以通过暴力方式解密的, 有所谓的 彩虹表(rainbow table) 可以倒推出原始的密码.

嗯, 这么说也确实是事实, 但具体解析这是怎么回事, 包括使彩虹表成为可能的, 则与 MD5 算法的另一个特性有很大关系: 那就是它是一种 确定性(deterministic) 的算法.

所谓确定性, 就是对于同样的输入, 总是产生同样的输出.

来看一个具体的代码示例:

@Test
public void recalcMd5() {Assert.assertEquals("889191f08f81d2cac5ea19bc3bf7d9be", md5("xiaogd.net"));Assert.assertEquals("889191f08f81d2cac5ea19bc3bf7d9be", md5("xiaogd.net"));
}

注: md5 工具方法见前述代码示例, 此处略

可以看到两次对 xiaogd.net 这个字符串进行 MD5 的结果都是一样的. 你不会碰到说, 同一个字符串第一次这个结果, 下一次又是另一个结果, 这样就乱套了.

MD5 保证不会发生这样的情况, 而这个确定性的特性也使得用 MD5 来存储密码成为可能.

具体而言整个流程是这样去实现的, 就比如说我准备注册用户 xgd, 然后用我的域名 xiaogd.net 作为对应的密码吧, 那么在第一次用户注册的时候, 就把用户名 xgd 和根据密码 xiaogd.net 算出的 MD5 的值 889191f08f81d2cac5ea19bc3bf7d9be 存起来:

xgd --> 889191f08f81d2cac5ea19bc3bf7d9be

而密码 xiaogd.net 本身则丢弃了, 不保存在数据库中.

这样的方案还是有问题的, 但这里的目的不是要讨论怎么安全的存储密码, 而是探讨 MD5 存储密码的原理, 因而采用了一个简单的有缺陷的方案.

后续, 当用户再次登录时, 自然, 用户还是传过来 xgd 这个用户名和 xiaogd.net 这个密码, 而数据库里并没有这个密码, 怎么去验证呢?

答案也很简单, 就是再次对用户输入的密码进行 MD5 计算, 然后与数据库保存的 MD5 值进行比较. 那么根据算法的确定性的特征, 如果用户输入的还是同样的密码, MD5 后的值自然也还是同样的 889191f08f81d2cac5ea19bc3bf7d9be, 这样就能与数据库先前保存的值匹配上了, 也就可以判定允许用户登录了;

而用户再次传过来的密码值在完成 MD5 运算后依然会被丢弃而不会存起来.

安全的做法必然是这样去要求的, 那就是永远都不要明码保存用户的密码, 另一方面, 这也导致了"找回密码"功能并不会真正让你找回密码, 只能让你重新设置密码, 然后覆盖掉原有的哈希值.

反之, 假如用户输入了错误的密码, 那么经 MD5 计算就会产生不一样的值:

事实上, 哪怕只有一点点的不同, 结果也会剧烈的变化, 有点像是 蝴蝶效应(Butterfly Effect) 或是 雪崩效应(Avalanche Effect) 那样, 这也可以算是 MD5 算法的一个特性.

比如缺了点的 xiaogdnet, 可谓字面意义上的有一"点"不同, MD5 的结果就会变成这样: dc0c594ffbc99b8a8d5a6fa022738ad6, 对比原来的 889191f08f81d2cac5ea19bc3bf7d9be, 结果可谓天差地别.

也就无法与数据库保存的值匹配上, 这种情况下登录就被拒绝了.

当然, 你可能好奇, 有没有可能输入了一个错误的密码, 却产生了相同的 MD5 值呢? 这实际就是所谓的 MD5 的 碰撞(Collision) 问题了, 我们留待后面再分析. 简单讲就是理论上是可能的, 这种可能性甚至有无数种, 但实际上, 想产生一个碰撞却并不容易.

综上, 此种密码存储及验证方案, 在安全性上有两个优势:

1. 没有存储用户的原始的明文密码, 所以即便是内鬼也不可能知道用户的密码;
2. MD5 算法是不可逆的, 即便内鬼要捣乱或者数据库泄露了, 也无法倒推出用户的密码.

既然如此, 所谓的暴力破解及彩虹表又是怎么回事呢? 这就多少涉及到人性了.

安全界早就有这种共识: 那就是系统安全最薄弱的环节往往就是人本身.

在其它很多方面, 人的问题也常常出现, 见此处的一个调侃: PEBKAC

首先, 倒推确实是不可能, 但根据 MD5 算法的确定性, 却可以进行正推.

所谓正推, 就好比你知道 xiaogd.net 经 MD5 会生成 889191f08f81d2cac5ea19bc3bf7d9be, 那么当你拿到 889191f08f81d2cac5ea19bc3bf7d9be, 你反过来就知道了原始的密码是 xiaogd.net.

咋一看时, 密码的组合是无穷无尽的, 这使得正推存在很大的困难, 可问题也恰恰出在这里, 很多用户经常使用很简单的弱密码, 比如只使用 6 位的数字, 则所有的可能不过是 100 万种而已.

那么假如此时我想去破解, 我就先把 000000 ~ 999999 的一百万个 MD5 值全部先算出来, 然后存到一个数据库的表里:

md5(‘000000’) --> 670b14728ad9902aecba32e22fa4f6bd;

md5(‘000001’) --> 04fc711301f3c784d66955d98d399afb;

…

…

md5(‘999998’) --> 755af25720023b2f852105910b125ecc;

md5(‘999999’) --> 52c69e3a57331081823331c4e69d3f2e;

此时, 假如某个泄露的用户数据库里有条记录的 md5 值为 755af25720023b2f852105910b125ecc, 我不知道密码, 但我反过来一查我的表, 发现这个 MD5 值正好与 md5(‘999998’) 的值相同, 那么显然这个用户的密码就是 999998 了.

理论上讲, 因为存在碰撞的可能, 用户的密码也可能是另一个, 但从登录的原理上看, 用 999998 也是可以登录的, 产生碰撞的两个或多个均能通过登录校验.

而这样的一个表, 即是所谓的 彩虹表(rainbow table) 了, 如果你有足够的资源, 对于位数有限的密码组合, 是完全可能穷举完的, 这种穷举式的正向 暴力破解(brute-force attack) 是很难防止的.

当然, 从以上叙述中也不难明白, 所谓破解, 不是真的破解, 另外, 它只能破解常见的以及较短的弱密码. 如果你使用一个位数很长, 又包含各种大写小字母, 各种特殊符号的强密码, 那么一般来说, 即便有彩虹表也无法奈你何, 毕竟要穷举如此之多的记录是不可能的.

为抵御这种彩虹表攻击, 可以在系统中透明地为用户的密码额外拼接上一个随机的字符串值, 即所谓的 盐值(salt), 然后再计算密码加盐后的 md5 值并保存, 这个过程称为 加盐.

验证的过程也是类似的, 同样是把再次传过来的密码加上盐值去计算 md5, 并与数据库保存的值去验证.

举个具体例子, 先生成一个随机的字符串, 也即盐值, 比如"e3f$8%0"

为叙述方便, 这里用了一个较短的随机值, 实际中可以考虑更长的随机值.

如果张三此时用了一个简单的密码 666666, 拼接后计算的是 666666e3f$8%0 的 md5 值, 那么这个串在那些暴力破解的彩虹表里就不一定有了.

李四用了一个简单的密码 888888, 拼接后计算的是 888888e3f$8%0 的 md5 值, 同样的这个串在那些暴力破解的彩虹表里也不一定有.

更加安全的做法是为每个用户都生成专属的随机串, 然后把这个盐值存在对应用户记录中, 也即存储"用户名 | 随机盐值 | 密码+随机盐值的 md5 值".

举个例子, 王五用了 123456 作为密码, 赵六也用了 123456 作为密码, 为王五生成他专门的随机盐值 a&58#93, 为赵六也生成他专属的随机盐值 b78!967, 虽然他们都用了相同的密码, 但拼上不同的盐值后, 计算到的 md5 自然也不同了.

对于王五, 算的是 123456a&58#93 的 md5 值, 对于赵六, 算的是 123456b78!967 的 md5 值, 数据库里存储的记录是这样的:

用户名 | 随机盐值 | 密码+随机盐值的 md5 值

王五 | a&58#93 | eed2402dbd1605cb1fa8fe5a270a1849

赵六 | b78!967 | fcbb4aa14c17bd8970e664e23c0fd87c

这样一个数据库即便被泄露了, 攻击者也很难倒推出密码, 他也无从知道谁谁谁是否使用了相同的密码.

注意, 实践中也有人采取二次 md5 的做法, 比如对于 123456 这个密码, 存储的是 md5(md5(‘123456’)), 这种方式其实是不安全的!!

攻击者也完全可以对那些简单的密码进行二次 md5 计算, 这个计算量不过翻了一倍而已, 完全可以再构建一个这样的表.

md5(‘123456’) = e10adc3949ba59abbe56e057f20f883e;

md5(‘e10adc3949ba59abbe56e057f20f883e’) = 14e1b600b1fd579f47433b88e8d85291;

如果攻击者发现一条记录值是 14e1b600b1fd579f47433b88e8d85291, 则第一次查表他得到了 ‘e10adc3949ba59abbe56e057f20f883e’, 问题是谁会去用如此复杂的密码呢? 于是他猜测也许用了多次的 md5, 于是他用 e10adc3949ba59abbe56e057f20f883e 再次去反查, 就得到了最终的密码 123456.

最后说说所谓的碰撞问题. 事实上, 从固定 16 字节的输出结果来看, 而另一方面输入的可能性则是无限的, 那么这就从原理上决定了碰撞是无可避免的.

吾生也有涯，而知也无涯。以有涯随无涯，殆已! --<<庄子·养生主>>

有一个所谓的抽屉原理, 举个简单的例子来说, 你有 10 个苹果, 要放到 9 个抽屉里, 然后我不需要知道你到底是怎么放的, 我都可以断言, 至少有一个抽屉里面至少有两个苹果.

为啥我可以这么断言呢? 很简单, 即便前 9 个苹果你放得非常均匀, 9 个抽屉每个都恰好放一个, 你手里还是会剩下一个无处可去, 而每个抽屉此时都放了有苹果, 因此最后无论你把这仅剩的苹果放在哪个抽屉里, 那那个抽屉里就有两个苹果, 因此就得出了前述的结论: 至少有一个抽屉里面至少有两个苹果. 萝卜太多, 坑位不够, 还能咋地?

如果放得不均匀, 有些抽屉里最后可能还不止两个苹果, 三个, 四个乃至更多都有可能.

那么对于 MD5 来说, 原理是类似的, 因为输出是固定的 128 比特, 也就限制了所有可能的值是 2^128(2 的 128 次方) 种, 也就是值的范围是从 0 ~ 2^128-1, 撑死了就这么多不同种输出.

注: 其实这个值相当大了, 它约等于 3.4×10^38, 340万亿亿亿亿.

尽管这个空间是非常非常的大, 但输入的可能性更大, 是无穷的, 就好比你有一个相当大数目的抽屉, 可我却有无穷多个苹果, 我怎么都能把你的抽屉给塞满了.

一个很简单的方式就是, 我就从 md5(‘0’), md5(‘1’), md5(‘2’)… 一直算到 md5(‘2^128’)(注: 展开后的值, 这里为简化才写成指数形式), 那么我就有了 2^128+1 种不同输入, 而输出受固定位的影响最多也只有 2^128 种不同结果, 那么根据抽屉原理, 里面就至少发生了一次碰撞, 也即必然有两个不同的输入值, 最后产生了相同的输出值.

当然了, 实际上要产生一个碰撞则是很困难的, 一方面是这个空间非常大, 另一方面则是哈希函数的特性了, 还记得它也叫 散列函数 吗? 可以理解为它就是尽量把值分得散散的.

可以这么去认为, 对于两个不同的字符串进行各自进行 md5 的值, 就相当于在这个空间随机返回两个数. 哪怕就是在 0~100 间随机返回两个数, 相同的概率也不高, 何况如此之大的一个范围呢.

尽管碰撞是如此之难, 但算法毕竟不是完美的, 还是有人根据 md5 算法的一些缺陷构建出了一些碰撞的例子.

下面是一个具体碰撞的例子(注意有两处加粗的部分是不同的, 另注: 是它们所代表的字节数组而不是字符串, 这是两个十六进制的大数):

4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2

4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2

但它们都会生成这个相同的 md5 值: 008ee33a9d58b51cfeb425b0959121c9.

以下为测试的相关代码:

@Test
public void md5Collision() throws Exception {byte[] b1 = Hex.decodeHex("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2");byte[] b2 = Hex.decodeHex("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2");MessageDigest md = MessageDigest.getInstance("MD5");byte[] h1 = md.digest(b1);byte[] h2 = md.digest(b2);String h1Str = Hex.encodeHexString(h1);String h2Str = Hex.encodeHexString(h2);//System.out.println(h1Str);//System.out.println(h2Str);Assert.assertEquals(h1Str, h2Str);
}

注意: 是直接取 16 进制字符串代表的字节数组, 即 Hex.decodeHex 中的做法, 而不是取字符串的 string.getBytes, 直接转换与 string.getBytes 得到的字节数组是不一样的.

关于 md5 的介绍就到这里.