算法之MD5

发表于 更新于 分类于 ， Waline： 阅读次数： 本文字数： 4.7k 阅读时长 ≈ 8 分钟

MD5 即Message-Digest Algorithm 5 (信息-摘要算法5)。MD5 使用little-endian(小端模式)，输入任意不定长度信息，以 512-bit 进行分组，生成四个32-bit 数据，最后联合输出固定 128-bit 的信息摘要。

MD5 不是足够安全的。Hans Dobbertin在1996年找到了两个不同的512-bit 块,它们 在MD5 计算下产生相同的hash 值。至今还没有真正找到两个不同的消息，它们的MD5 的hash 值相等。

基本流程

md5

MD5 算法的基本过程为：

填充padding

在长度为Kbits 的原始消息数据尾部填充长度为Pbits 的标识 100…0，1< P <=512 (即至少要填充1个bit)，使得填充后的消息位 数为：(K + P) mod 512=448。注意到当K mod 512 =448时，需要P= 512。

填充长度

再向上述填充好的消息尾部附加K 值的低64位 (即K mod 2^64)， 最后得到一个长度位数为K + P+ 64= 0 (mod 512) 的消息。

把填充后的消息结果分割为L个512-bit 分组：Y0, Y1, …, YL-1。分组结果也可表示成N个32-bit 字M0, M1, …, MN-1，N= L * 16。

缓冲区初始化

初始化一个128-bit 的MD 缓冲区，记为CVq，表示成4个32-bit 寄存器(A, B, C,D)；CV0= IV。迭代在MD 缓冲区进行，最后一 步的128-bit 输出即为算法结果。

初始状态为:

1
2
3
4
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

16进制数：

1
2
3
4
int a := 0x67452301
int b := 0xEFCDAB89
int c := 0x98BADCFE
int d := 0x10325476

循环压缩

我们首先定义了四个辅助函数，每个函数都输入三个 32 位数字并产生一个 32 位数字作为输出。

1
2
3
4
F = (B and C) or ((not B) and D)
G= (D and B) or ((not D) and C)
H= B xor C xor D
I= C xor (B or (not D))

然后使用正弦函数构建64元素的表K:

1
2
for i from 0 to 63
    K[i] = floor(232 × abs (sin(i + 1)))

计算结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 }

还有偏移量 s数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// rotation constants
private static final int S11 = 7;
private static final int S12 = 12;
private static final int S13 = 17;
private static final int S14 = 22;
private static final int S21 = 5;
private static final int S22 = 9;
private static final int S23 = 14;
private static final int S24 = 20;
private static final int S31 = 4;
private static final int S32 = 11;
private static final int S33 = 16;
private static final int S34 = 23;
private static final int S41 = 6;
private static final int S42 = 10;
private static final int S43 = 15;
private static final int S44 = 21;

伪码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 上述填充后的消息长度为N
For i = 0 to N/16-1 do

     /* Copy block i into X. */
     For j = 0 to 15 do
       Set X[j] to M[i*16+j].
     end /* of loop on j */

     /* Save A as AA, B as BB, C as CC, and D as DD. */
     AA = A
     BB = B
     CC = C
     DD = D

     /* Round 1. */
     /* Let [abcd k s i] denote the operation
          a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
     /* Do the following 16 operations. */
     [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
     [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
     [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
     [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

     /* Round 2. */
     /* Let [abcd k s i] denote the operation
          a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
     /* Do the following 16 operations. */
     [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
     [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
     [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
     [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]

     /* Round 3. */
     /* Let [abcd k s t] denote the operation
          a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
     /* Do the following 16 operations. */
     [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
     [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
     [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
     [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]

     /* Round 4. */
     /* Let [abcd k s t] denote the operation
          a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
     /* Do the following 16 operations. */
     [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
     [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
     [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
     [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]

     /* Then perform the following additions. (That is increment each
        of the four registers by the value it had before this block
        was started.) */
     A = A + AA
     B = B + BB
     C = C + CC
     D = D + DD

   end /* of loop on i */

得出结果。

以 A 的低字节开始，以D的高字节结束的 ABCD 就是产出的消息摘要。

MD5的碰撞概率

在分析MD5的碰撞概率前先介绍下生日问题：

在随机选择的一群人当中有两人的生日相同的概率。如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%；对于60或者更多的人，这种概率要大于99%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。

假设有n个人在同一房间内，不考虑特殊因素，例如闰年、双胞胎，并且假设一年365日出生概率是均匀分布的。首先计算每个人的生日日期都不同的概率为：

1
(365 * 364 *... *(635-n+1)) /(365^n)

当n=23时，p(23,365)大约是0.507。

对于MD5 碰撞问题：平均而言，如果不尝试故意创建冲突，则需要对大约 2^64 个值进行哈希处理才能获得它们之间的单个冲突。如果看两个任意值，碰撞概率只有2^128。

但是已经有密码学家编写了MD5 碰撞生成器的例子。虽然这个生成器仅仅用于构造两个文件, MD5相同但内容不同,不是从MD5值逆推出的,但是说明MD5碰撞不可靠已经足以了。(也就是说，单纯的将MD5(PassWord) 作为验证手段是不安全的。此时在工程角度来看，这正说明了加盐MD5(Password+salt)的重要作用)。

参考资料