MD5流程以及安全性分析，MD5加盐，MD6，笔记

我就是我 2022-05-26 02:17 343阅读 0赞

# 版权归其所有论文作者所有。 #

并没写原始的地址，因为这是我整合的，作者太多，包括我。太匆忙，原作者可以联系我。

# 简介 #

MD5适用于数据完整性校验的。将任意长度的字节串(所以是基于底层的二进制串的)，映射成为一个128位的大整数2^128种可能性。同样的内容经过md5，会得到同样的128位码。本质上是散列算法，有损的信息压缩，并且是不可逆的。

MD5广泛用于加密和解密技术上，在很多操作系统中，用户的密码是以MD5值（或类似的其它算法）的方式保存的，用户Login的时候，系统是把用户输入的密码计算成MD5值，然后再去和系统中保存的MD5值进行比较，而系统并不“知道”用户的密码是什么。

一个安全的散列算法具有如下特点：

（1）仅从散列值无法反推出原信息；

（2）两个不同数字信息产生同样的散列值的概率是非常小的，几乎为零；

（3）原信息的微小改变（哪怕只改变一位），将导致散列值的很大变化。

线性同余随机数服从均匀分布

# 2 实现步骤 #

## 2.1 填充 ##

在MD5算法中，首先需要对信息进行填充，使其字节长度对512求余数的结果等于448。因此，信息的字节长度（Bits Length）将被扩展至N\*512+448，即N\*64+56个字节（Bytes），N为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后再在这个结果后面附加一个以64位二进制表示的填充前的信息长度。经过这两步的处理，现在的信息字节长度=N\*512+448+64=(N+1)\*512，即长度恰好是512的整数倍数。这样做的原因是为满足后面处理中对信息长度的要求。

## 2.2 设置链接变量 ##

MD5中有四个32位被称作链接变量（ChainingVariable）的整数参数，他们分别为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。当设置好这四个链接变量后，就开始进入算法的四轮循环运算，循环的次数是信息中512位信息分组的数目。

## 2.3 进行主循环 ##

接着进行算法的主循环，循环的次数是消息中512位消息分组的数目。

将上面四个变量复制到别外的变量中：A到a，B到b，C到c，D到d。

主循环有四轮（MD4只有三轮），每轮很相拟。第一轮进行16次操作。每次操作对a，b，c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a，b，c或d中之一。最后用该结果取代a，b，c或d中之一。

### 2.3.1 以一下是每次操作中用到的四个非线性函数（每轮一个）。 ###

F(X,Y,Z)=(X&Y)|((~X)&Z)

G(X,Y,Z)=(X&Z)|(Y&(~Z))

H(X,Y,Z)=X^Y^Z

I(X,Y,Z)=Y^(X|(~Z))

(&是与,|是或,~是非,^是异或)

这些函数是这样设计的：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。

函数F是按逐位方式操作：如果X，那么Y，否则Z。函数H是逐位奇偶操作符。

设Mj表示消息的第j个子分组（从0到15），<<< s表示循环左移s位，则四种操作为：

FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<<<s)

GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<<<s)

HH(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti)<<<s)

II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)<<<s)

这四轮（64步）具体表示请看附录。

### 2.3.2 常数ti可以如下选择： ###

在第i步中，ti是4294967296\*abs(sin(i))的整数部分,i的单位是弧度。

(2的32次方)

所有这些完成之后，将A，B，C，D分别加上a，b，c，d。然后用下一分组数据继续运行算法，最后的输出是A，B，C和D的级联。

# 3 MD5的安全性 #

虽然应该先吹一波MD5如何安全，如何均匀，但是，MD5是不安全的。

对于两个不同数字信息产生同样的散列值的概率是非常小的，几乎为零，需要明确的是，散列算法是一个将无穷维空间的信息映射到有限维空间的变换，不是一个一一映射。实际上一个散列值可能对应有无穷多个数字信息，换言之，会有无穷多个数字信息产生同样一个散列值。产生相同散列值的两个不同的消息被称为碰撞（Collision），所以，散列函数存在碰撞是必然的。我们定义一个“安全”的散列算法，主要是指在以下三种意义上是“计算安全”的：

其一：//Preimage Attack（原像攻击）

给定明文M1，找到另一明文M2(不等于M1），使得hash(M1)=hash(M2)；

其二： //Second Preimage Attack（二次原像攻击）

给定明文M1，找到另一明文M2(不等于M1），使得hash(M1)=hash(M2)；

其三：//CollisionAttack(碰撞攻击)

找到两个不同的M1和M2，使得hash(M1)=hash(M2)。

对于原像攻击（Preimage Attack），实际应用中最常见的是采用“字典法”，将明文和密文对存储起来，使用时只需查询出来即可。这种方法看似技术含量不高，事实上确实最具威胁性。目前互联网上已经有近百个此类查询站点了。

对于次原像攻击（Second Preimage Attack），目前密码学界尚未有突破性进展，可以认为是MD5算法是“计算安全”的。

MD5的输出为128位，若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2128，用每秒可试验1000000000个消息的计算机需时1.07×1022年。若采用生日攻击法，寻找有相同Hash值的两个消息需要试验264个消息，用每秒可试验1000000000个消息的计算机需时585年。

不过事实上，2004年，王小云教授证明MD5数字签名算法可以产生碰撞，2009年，冯登国、谢涛二人利用差分攻击，将MD5的碰撞算法复杂度从王小云的2^42进一步降低到2^21，极端情况下甚至可以降低至2^10。仅仅2^21的复杂度意味着即便是在2008年的计算机上，也只要几秒便可以找到一对碰撞。

# 4 MD5加盐 #

还有一种增加安全性的手段是，MD5加盐，就是在Md5码上加上别的字符串（盐），所以即使有暴力破解的手段，不知道盐，依旧不能得到真正的Md5码。

通过密码加盐，密码的安全性已经提高了不少。但是还可以进一步改进。

假设字符串拼接算法、盐值已外泄，上面的代码至少存在下面问题：

短盐值：需要穷举的可能性较少，容易暴力破解，一般采用长盐值来解决。

盐值固定：类似的，攻击者只需要把常用密码+盐值的hash值表算出来，就完事大吉了。

短盐值自不必说，应该避免。对于为什么不应该使用固定盐值，这里需要多解释一下。很多时候，我们的盐值是硬编码到我们的代码里的（比如配置文件），一旦坏人通过某种手段获知了盐值，那么，只需要针对这串固定的盐值进行暴力穷举就行了。

## 4.1 随机盐值。 ##

密码一样，由于采用了随机盐值，前后运算得出的结果是不同的。这样带来的好处是，多个用户，同样的密码，攻击者需要进行多次运算才能够完全破解。同样是纯数字3位短盐值，随机盐值破解所需的运算量，是固定盐值的1000倍。

# 5 MD6 #

MD5被攻破后，在Crypto2008上， Rivest提出了MD6算法，该算法的Blocksize为512 bytes(MD5的Block Size是512 bits), Chaining value长度为1024 bits, 算法增加了并行 机制，适合于多核CPU。 在安全性上，Rivest宣称该算法能够抵抗截至目前已知的所有的 攻击（包括差分攻击）。

# 附录： #

第一轮

FF(a,b,c,d,M0,7,0xd76aa478)

FF(d,a,b,c,M1,12,0xe8c7b756)

FF(c,d,a,b,M2,17,0x242070db)

FF(b,c,d,a,M3,22,0xc1bdceee)

FF(a,b,c,d,M4,7,0xf57c0faf)

FF(d,a,b,c,M5,12,0x4787c62a)

FF(c,d,a,b,M6,17,0xa8304613)

FF(b,c,d,a,M7,22,0xfd469501)

FF(a,b,c,d,M8,7,0x698098d8)

FF(d,a,b,c,M9,12,0x8b44f7af)