MD5

MD5是由麻省理工学院的Ronald Rivest (Rivest，1992)教授设计的一系列消息摘要算法之一。当分析工作表明MD5的前身MD4很可能不安全时，瑞文斯特在1991年设计了MD5作为安全的替代算法。（Hans Dobbertin后来确实发现了MD4的弱点。)

1993年，虽然存在局限性，登布尔和博瑟莱尔斯给出了一个早期的发现MD5压缩函数的“伪碰撞“的结果；也就是说，存在两种不同的初始化向量产生相同的摘要。

1996年，多伯汀发表了一个MD5压缩函数的冲突(多伯汀，1996)。虽然这不是对完整MD5散列函数的攻击，但对于密码学家来说，这足以建议切换到一个替代的函数，例如SHA-1或者RIPEMD-160。

哈希值的大小(128位)小到足以考虑生日攻击。MD5CRK是一个始于2004年3月的分布式项目，旨在通过使用生日攻击发现冲突来证明MD5实际上是不安全的。

MD5CRK于2004年8月17日结束，当时完整的MD5碰撞由王小云，冯登国，来学嘉和于洪波共同发表。^[4][5] 据报道，他们在IBM p690集群进行的分析攻击只花了一个小时。^[6]

2005年3月1日，阿尔金·伦斯特拉, 王小云和本·德·韦格演示了两个具有不同公钥和相同MD5哈希值X.509证书，这是一个明显的实际冲突。^[7]该结构包括两个公钥的私钥。几天后，Vlastimil Klima描述了一种改进的算法，能够在几个小时内在单台笔记本电脑上构建MD5冲突。^[8]2006年3月18日，克利马发布了一种算法，可以在一分钟内在一台笔记本电脑上找到碰撞，他称之为隧道。^[9]

各种与MD5相关的RFC勘误表已经出版。2009年美国网络司令部使用他们使命宣言的MD5哈希值作为官方标志的一部分。^[10]

2010年12月24日，谢涛和冯登国宣布首次发布单块(512位)MD5冲突。^[11] (以前的碰撞发现依赖于多块攻击。)出于“安全原因”，谢和冯没有透露新的攻击方法。他们向密码社区发起挑战，并向2013年1月1日前第一个发现不同的64字节冲突的人提供10,000美元的奖励。马克·史蒂文斯响应了这个挑战并发布了冲突单块消息以及构建算法和源码。^[12]

2011年，信息RFC 6151^[13] 被批准更新MD5和HMAC MD5中的安全注意事项^[14][15]

MD5哈希函数的安全性受到严重损害。碰撞攻击在搭载2.6GHz的奔腾4处理器的计算机上可以在几秒钟内找到冲突(复杂度为2^24.1)。^[16] 此外，还有使用现成计算硬件的选择前缀冲突攻击(复杂度为2³⁹)。^[17]现成GPU的使用极大地辅助了寻找碰撞的能力。在英伟达GeForce 8400GS图形处理器上，每秒可以计算1600万到1800万个散列。英伟达GeForce 8800 Ultra每秒可以计算超过2亿个散列。^[18]

这些散列和冲突攻击已经在各种情况下公开展示，包括冲突文档文件^[19][20]和数字证书。^[21]截至2015年，MD5仍被广泛使用，特别是被安全研究和防病毒公司使用。^[22]

2.1 安全问题概述

1996年，MD5的设计中发现了一个缺陷。虽然这在当时并不被认为是致命的弱点，但密码学家开始推荐使用其他算法，例如SHA-1，后来发现它也很脆弱。^[23]2004年，MD5被表明不是耐碰撞的。^[24]因此，MD5不适用于以下应用SSL证书 或者数字签名依赖这一属性实现数字安全的。同样在2004年，MD5中发现了更严重的缺陷，使得出于安全目的进一步使用该算法成为问题；具体来说，一组研究人员描述了如何创建一对共享相同MD5的文件 校验和。^[4][25] 2005年、2006年和2007年在破解MD5方面取得了进一步进展。^[26] 2008年12月，一组研究人员使用这种技术来伪造SSL证书的有效性。^[21][27]

截至2010年CMU软件工程研究所认为MD5“密码损坏，不适合进一步使用”，^[28]大多数美国政府应用程序现在都要求使用SHA-2散列函数族。^[29]2012年Flame恶意软件利用MD5的弱点假冒微软数字签名。

2.2 碰撞漏洞

1996年，在MD5的压缩函数中发现了冲突，Hans Dobbertin将它写在RSA实验室技术简讯中，“目前的攻击还没有威胁MD5的实际应用，但已经相当接近了...今后MD5将不再被实行...其中需要防冲突散列函数。”^[30]

2005年，研究人员能用相同的散列创造成对的附言文档^[31]和X.509证书^[32]。2005年年末，MD5的设计者罗恩·瑞文斯特(Ron Rivest)写道，“MD5和sha1都明显被破坏了(在耐碰撞方面)”。^[33]

2008年12月30日，一组研究人员在第25届混沌通信大会上宣布他们如何使用MD5冲突来创建一个中间证书颁发机构的证书，当通过MD5哈希进行检查时，该证书看起来是合法的。^[21]研究人员在洛桑，瑞士^[34]的EPFL上使用了一组索尼PlayStation 3单元集群，以将一个由RapidSSL颁发的普通SSL证书更改为该发行商的合法CA证书，然后可以用来创建其他合法并由RapidSSL颁发的证书。 RapidSSL证书的发行者VeriSign表示，一旦漏洞被公布，他们就停止使用MD5作为RapidSSL的校验和算法来发行新证书。^[35]虽然VeriSign拒绝撤销使用MD5签名的现有证书，但攻击的作者(Alexander Sotirov, 马克·史蒂文斯, Jacob Appelbaum, 阿尔金·伦斯特拉戴维·莫尔纳尔、达戈·阿恩·奥斯维克和本·德·韦格)认为它们的回应足够充分。^[21]布鲁斯·施奈尔(Bruce Schneier)写道，这次攻击“我们已经知道MD5是一个损坏的散列函数”，并且“没有人应该再使用MD5了”。^[36]SSL研究人员写道，“我们希望的影响是，证书颁发机构将停止在颁发新证书时使用MD5。我们也希望MD5在其他应用中的使用也能得到重新考虑。”^[21]

2012年，根据微软的消息，Flame恶意软件的作者使用MD5冲突伪造了一个视窗代码签名证书。^[37]

MD5使用Merkle-Damgard结构因此，如果可以构造具有相同散列的两个前缀，则可以向这两个前缀添加一个公共后缀，以使冲突更有可能被使用它的应用程序接受为有效数据。此外，当前的冲突发现技术允许指定任意的前缀。攻击者可以创建两个以相同内容开头的冲突文件。攻击者生成两个冲突文件所需的只是一个模板文件，该文件包含128字节的数据块，在64字节的边界对齐，冲突查找算法可以自由更改。两个消息相差6位的MD5冲突示例如下:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

两者都产生MD5散列 79054025255fb1a26e4bc422aef54eb4。^[38]两个样本之间的区别在于，每个半字节中的前导位被取反了。例如，顶部样本0x87中的第20个字节(偏移量0x13)是二进制的10000111。字节的前导位(也是第一个半字节的前导位)翻转为00000111，即0x07，如下图所示。

后来，人们还发现有可能用单独选择的前缀来构造两个文件之间的冲突。这种技术在2008年被用于创建流氓证书。一种使用消息传递接口的新的并行碰撞搜索变体由安东·库兹涅佐夫在2014年提出，它允许在11小时内在计算集群上发现碰撞。^[39]

2.3 映像前漏洞

2009年4月，对MD5的原像攻击发布，这打破了MD5的原像阻力。这种攻击只是理论上的，对完整的原像来讲，计算的复杂度为2^123.4 。^[40][41]

MD5摘要在软件中广泛用于提供传输的文件已经完好无损地到达的保证。例如，文件服务器通常提供预先计算的MD5(称为 md5sum)校验和以便用户可以比较下载文件的校验和。大多数基于unix的操作系统在其分发包中包含MD5求和实用程序；Windows用户可以使用包含的PowerShell函数“Get-FileHash”，安装一个微软实用程序，^[42][43] 或者使用第三方应用程序。安卓ROM也使用这种校验和。

由于生成MD5冲突很容易，创建文件的人有可能创建具有相同校验和的第二个文件，因此这种技术无法防止某些形式的恶意篡改。在某些情况下，校验和是不可信的(例如，它是通过与下载文件相同的通道获得的)，在这种情况下MD5只能提供错误检查功能:它将识别损坏或不完整的下载，这在下载较大文件时变得更有可能。

历史上，MD5一直用于存储密码，通常与密钥延伸共同使用。^[44][45]NIST在其推荐的密码存储哈希列表中不包含MD5。^[46]

MD5也用于电子档案查询领域，以便为法律查询过程中交换的每个文档提供唯一标识符。此方法可用于替换贝茨编号在纸质文件交换过程中使用了几十年的编号系统。如上所述，由于碰撞攻击容易，不推荐使用。

MD5将可变长度的消息处理成128位的固定长度输出。输入消息被分成512位块的块(十六个32位字)；信息被增补，这样它的长度可以被512整除。增补的工作方式如下:首先，在消息的末尾附加一个位1。接下来是尽可能多的零，以使消息长度达到比512的倍数少64位。剩余的比特用64比特填充，表示原始消息的长度，模2⁶⁴。

主要的MD5算法在128位状态下运行，分为四个32位字，表示为 A, B, C，和 D。这些被初始化为某些固定常数。然后，主算法依次使用每个512位消息块来修改状态。消息块的处理由四个类似的阶段组成，称为回合；每一轮由16个基于非线性函数F的类似操作组成模块化加法和左旋转。图1显示了一轮中的一个操作。有四种可能的功能；每轮使用不同的:

 分别表示 、异或, 与, 或和非运算。

4.1 伪代码

MD5哈希是根据该算法计算的。所有值按小端顺序排列。

//Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int[64], s, K
var int i

//s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

//Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63
    K[i] := floor(232 × abs(sin(i + 1)))
end for
//(Or just use the following precomputed table):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

//Initialize variables:
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

//Pre-processing: adding a single 1 bit
append "1" bit to message 
// Notice: the input bytes are considered as bits strings,
//  where the first bit is the most significant bit of the byte.[47]

//Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)
append original length in bits mod 264 to message

//Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
    //Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    //Main loop:
    for i from 0 to 63
        var int F, g
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31 then
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47 then
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63 then
            F := C xor (B or (not D))
            g := (7×i) mod 16
        //Be wary of the below definitions of a,b,c,d
        F := F + A + K[i] + M[g]
        A := D
        D := C
        C := B
        B := B + leftrotate(F, s[i])
    end for
    //Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 //(Output is in little-endian)

//leftrotate function definition
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));

注意:以下内容可用于提高效率，而不是原始RFC 1321中包含的公式(如果使用汇编语言很有用，否则编译器通常会优化上述代码)。由于这些公式中的每个计算都依赖于另一个，这通常比上述nand/and可并行的方法慢):

( 0 ≤ i ≤ 15): F := D xor (B and (C xor D))
(16 ≤ i ≤ 31): F := C xor (D and (B xor C))

128位(16字节)MD5哈希(也称为消息摘要)通常表示为长度32的十六进制的数字。下面演示了一个43字节的美国信息交换标准码输入和相应的MD5哈希:

MD5("The quick brown fox jumps over the lazy dog”=
9e107d9d372bb6826bd81d3542a419d6

即使是消息中的一个小变化也会(以压倒性的概率)导致一个大部分不同的散列，这是由于雪崩效应。例如，在句尾添加一个句点:

MD5("The quick brown fox jumps over the lazy dog.”=
e4d909c290d0fb1ca068ffaddf22cbd0

零长度字符串的哈希是:

MD5("" =
d41d8cd98f00b204e9800998ecf8427e

MD5算法是为包含任意位数的消息指定的；它不限于八位的倍数(八比特, 字节)。一些MD5实现，例如md5sum可能限于八字节，也可能不支持对于初始时未确定长度的消息流。

下面是支持MD5的加密库列表:

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• Libgcrypt
• Nettle
• OpenSSL
• wolfSSL