简介

MD5,即Message-Digest Algorithm 5MD5信息摘要算法。

这是一种典型的哈希函数/散列函数,会将任意消息内容变为长度固定的散列值,任何输入内容都将被输出一个长度固定为128bitMD5值,同一个输入消息的输出结果始终相同。

MD5数据的128bit散列值分为4部分,用4个幻数设定其初始值,4个幻数在内存地址上从低到高为:

幻数内存地址
A01 23 45 67
B89 ab cd ef
Cfe dc ba 98
D76 54 32 10

标准幻数总共为4*32=128bit。

MD5算法生成散列值的过程总共分为三步:1、填充对齐;2、分块;3、多轮压缩。

1、填充补齐:需要将数据补充为512bit的整数倍,在补齐数据中采用小端格式,最后64bit固定用于表示原始数据大小,中间剩下的bit第一个填1,其余均为0。若数据为1000bit,不足够存放64bit表示原始数据大小的数据,则补齐到512的三倍即可。

2、分块:分为512bit的数据块。

3、多轮压缩:将当前散列值的4部分各复制一份,分别用a、b、c、d表示,压缩共有4轮,每轮压缩过程使用数据块和a、b、c、d进行一系列与、或、非、循环移位的位操作,将a、b、c、d各自更新4次,4轮压缩一共更新16次。完成4轮压缩后,将最后得到的a、b、c、d分别加回到当前散列值的4个部分,散列值被更新。之所以叫压缩,是因为这个过程实际上在使用512bit的数据块来更新128bit的散列值,信息被压缩了,然后再使用后续大块进行相同操作,唯一不同点在于此时散列值初始值为前一个大块的最终值。

在所有大块上完成多轮压缩后,散列值更新为最终输出的MD5值,将这4部分合起来并变换为大端数即为最终输出的MD5值。

MD5信息摘要算法于1992年公开,其主要目的在于取代MD4算法,1996年后MD5算法被证实存在弱点,可以被加以破解,2004年MD5算法被证实无法防止碰撞,不适用于SSL公开密钥、数字签名等安全性认证。

应用场景

文件校验

数据库字段加密

如何攻击

MD5只是一个产生消息摘要的散列函数,而非加密算法,这个过程有信息损失且不可逆推。举例:1 | 1 = 1,但是不能倒推原始数据。

以鸽笼原理举例,一定会有同一个笼子至少有两只鸽子,引申出碰撞的概念。

原像攻击

这是对MD5的第一个基本安全要求,即找到任意一个能产生这个MD5值的消息,不过到今天也没有一个通用的可行方案。

暴力穷举:MD5值的范围在0~2^128^之间,理论上可行,但工程上不现实。

第二原像攻击

如果给定一个消息,能不能再找到另外一个MD5值相同的消息呢?

抗第二原像攻击(抗弱碰撞性)是对MD5的第二个基本安全性要求,除了在MD4弱消息上可行,对于MD5目前并没有有效的可行方案。

抗碰撞性(最不具安全性)

也叫抗强碰撞性,是对MD5的第三个基本安全性要求。

这个特性继续放宽了攻击标准,不指定MD5值和消息,只要找出两个MD5值相同的消息即可。

之前的研究很长时间都困在“伪碰撞”的范围,真正的突破在2005年山东大学王小云团队的"How to Break MD5 and Other Hash Functions"论文,研究思路为基于模块化差分,大体思路为先找到局部碰撞,然后分析差分如何传播,找到差分路径,再利用消息修改技术得到能产生碰撞的消息对。

MD5算法本身相比,寻找碰撞的方法要抽象、复杂得多,但这也正是信安领域的魅力。

这个方法在大约15~60min内找到了碰撞,从学术角度看,MD5大势已去,但从工程角度而言,虽然可以快速找到大量MD5碰撞,但这两个碰撞的消息是根据差分路径和消息修改精心构造而来,基本上都是没有实际意义的乱码,很难想象会对MD5的工程应用造成什么直接影响。

在王小云团队的研究基础上,2007年Marc Stevens在硕士论文中交付了两项新成果:1、用一个内容在几秒钟内生成另外两个MD5值一样,但内容不同的消息,重要的是生成的内容可以有意义,该成果有一个叫fastcoll的软件,可通过该软件生成MD5值相同且可以正常打开的图片,但仔细观察文本就会发现其结尾数据并不相同,这被称为相同前缀碰撞,原始内容作为前缀,然后不断尝试构造两个不同的后缀数据,直到最后两者MD5相同,前缀数据保留了内容本身的意义。换个概念来讲,若用可执行程序作为前缀,攻击者可绕过审核发布钓鱼软件,只需让软件内部做一个判定,如本程序最后1bit为1执行正常行为,0执行恶意行为,正常版本通过检测后再用恶意版本进行替换,若只依赖于MD5值判断的话将无法检测到替换的发生。相同前缀生成的可执行文件代码一样,只是触发条件不同,但是在杀毒过程中还是有可能发现可疑行为,所以最好情况是正常版本和恶意版本为两个不相干的程序;2、自由选择前缀消息内容,生成两个MD5值一样但前缀内容不同的文件,称之为选择前缀碰撞,其还会对使用MD5的数字签名产生巨大威胁。

文章许可:本文采用CC BY-NC-SA 4.0许可协议,转载请注明出处。