Merkle–Damgård结构
Merkle–Damgård结构(简称MD结构)一般用于从抗碰撞单向压缩函数中构建出抗碰撞的哈希算法。对于一个抗碰撞单向压缩函数\(f:\{0,1\}^\{n+b\}\mapsto\{0,1\}^n\)(其中\(n\)为输出长度,\(b\)是消息块长度),使用MD结构计算消息\(M\)的哈希值流程如下:
- 将消息\(M\)填充到长度为消息块长度\(b\)的整数倍,一般填充格式为\(M||1||0^{k}||len(M)\)
- 将填充后的消息分为\(L\)个长度为\(b\)的消息块\(M_1,M_2,\ldots,M_L\)
- 设定长度为\(n\)的初始链接变量\(H_0=IV\)
- 迭代计算\(H_{i}=f(H_{i-1}||M_i)\)(\(i=1,2,\ldots,L\)),最终得到的\(H_{L}\)就是消息\(M\)的哈希值
常见的使用了MD结构的哈希算法有MD5、SHA-0、SHA-1、SHA-256以及SM3等,下面详述这五种哈希算法:
MD5
本节涉及到的字节序均为小端序
MD5算法的输出长度为128位(即16字节),消息块长度为512位(即64字节),使用MD5算法计算消息\(M\)的哈希值流程如下:
首先将消息按如下格式填充至长度为512位的整数倍:
\[
M||1||0^k||L
\]
其中\(k=448-len(M)-1\mod{512},L=len(m)\mod{64}\),之后将填充后的消息分为若干个512位的分组\(M_1,M_2,\ldots,M_L\).
定义初始状态\(H_0=A||B||C||D\),其中:
\[
\begin{aligned}
&A = \texttt{67452301}\\
&B = \texttt{EFCDAB89}\\
&C = \texttt{98BADCFE}\\
&D = \texttt{10325476}\\
\end{aligned}
\]
然后对每个512位消息块\(M_t\)(\(t=1,2,\ldots,L\)),将其拆分为16个32位的字\(M_t[0],M_t[1],\ldots,M_t[15]\),之后对该消息块执行4轮、每轮16步的运算:
\[
\begin{cases}
A’=D\\
B’=B+\text{leftrotate}(A+F(B,C,D)+M_t[g]+K[i],s[i])\\
C’=B\\
D’=C
\end{cases}
\]
其中每一轮用到的非线性函数\(F\)不同,具体如下:
\[
F(B,C,D)=\begin{cases}
(B\land C)\lor(\lnot B\land D)&,\text{第1轮}(0\le i<16)\\
(D\land B)\lor(\lnot D\land C)&,\text{第2轮}(16\le i<32)\\
B\oplus C\oplus D&,\text{第3轮}(32\le i<48)\\
C\oplus(B\lor\lnot D)&,\text{第4轮}(48\le i<64)\\
\end{cases}
\]
每轮中\(g\)的选择如下:
\[
g=\begin{cases}
i&,\text{第1轮}(0\le i<16)\\
(5i+1)\mod{16}&,\text{第2轮}(16\le i<32)\\
(3i+5)\mod{16}&,\text{第3轮}(32\le i<48)\\
7i\mod{16}&,\text{第4轮}(48\le i<64)\\
\end{cases}
\]
\(K[i]\)为常量,定义为:
\[
K[i]=\left\lfloor2^{32}\times|\sin(i+1)|\right\rfloor
\]
可以用如下数组直接表示:
K = [
0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
]\(s[i]\)为常量表示循环左移的次数,具体数值为:
s = [
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
]处理完一个块之后将计算结果加入到先前的结果中更新的\(A,B,C,D\)(仅需截取结果的低32位),之后再进行下一个块的处理,直到所有块被处理完.
综上可以得到其Python实现如下:
import struct
K = [
0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
]
s = [
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
]
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
class MD5:
def __init__(self):
self.A = A
self.B = B
self.C = C
self.D = D
@staticmethod
def _rotl32(x, n):
x &= 0xffffffff
return ((x << n) | (x >> (32 - n))) & 0xffffffff
def checksum(self, msg: bytes):
L = (len(msg) * 8) & 0xffffffffffffffff
msg = msg + b'\x80'
while len(msg) % 64 != 56:
msg += b'\x00'
msg += struct.pack('<Q', L)
for offset in range(0, len(msg), 64):
chunk = msg[offset: offset+64]
M = struct.unpack("<16I", chunk)
regA, regB, regC, regD = self.A, self.B, self.C, self.D
for i in range(64):
if i >= 0 and i < 16:
F = (regB & regC) | ((~regB) & regD)
g = i
elif i >= 16 and i < 32:
F = (regD & regB) | ((~regD & regC))
g = (5 * i + 1) % 16
elif i >= 32 and i < 48:
F = regB ^ regC ^ regD
g = (3 * i + 5) % 16
else:
F = regC ^ (regB | (~regD))
g = 7 * i % 16
tmp = (F + regA + K[i] + M[g]) & 0xffffffff
newA = (regB + self._rotl32(tmp, s[i])) & 0xffffffff
regA, regB, regC, regD = regD, newA, regB, regC
self.A = (self.A + regA) & 0xffffffff
self.B = (self.B + regB) & 0xffffffff
self.C = (self.C + regC) & 0xffffffff
self.D = (self.D + regD) & 0xffffffff
return struct.pack("<4I", self.A, self.B, self.C, self.D).hex()SHA-0
本节涉及到的字节序均为大端序
SHA-0算法的输出长度为160位(即20字节),消息块长度为512位(即64字节),使用SHA-0算法计算消息\(M\)的哈希值流程如下:
首先将消息按如下格式填充至长度为512位的整数倍:
\[
M||1||0^k||L
\]
其中\(k=448-len(M)-1\mod{512},L=len(m)\mod{64}\),之后将填充后的消息分为若干个512位的分组\(M_1,M_2,\ldots,M_L\).
定义初始状态\(H_0=A||B||C||D||E\),其中:
\[
\begin{aligned}
&A = \texttt{67452301}\\
&B = \texttt{EFCDAB89}\\
&C = \texttt{98BADCFE}\\
&D = \texttt{10325476}\\
&E = \texttt{C3D2E1F0}\\
\end{aligned}
\]
然后对每个512位消息块\(M_t\)(\(t=1,2,\ldots,L\)),将其拆分为16个32位的字\(W_t[0],W_t[1],\ldots,W_t[15]\),之后进行如下递推将字串长度扩展到80个字:
\[
W_t[i]=W_t[i-3]\oplus W_t[i-8]\oplus W_t[i-14]\oplus W_t[i-16]
\]
其中\(i=16,17,\ldots,79\).
之后对该串执行4轮、每轮20步的运算:
\[
\begin{cases}
A’=\text{leftrotate}(A,5)+F(B,C,D)+E+W_t[i]+K[i]\\
B’=A\\
C’=\text{leftrotate}(B, 30)\\
D’=C\\
E’=D
\end{cases}
\]
其中每一轮用到的非线性函数\(F\)不同,具体如下:
\[
F(B,C,D)=\begin{cases}
(B\land C)\lor(\lnot B\land D)&,\text{第1轮}(0\le i<20)\\
B\oplus C\oplus D&,\text{第2轮}(20\le i<40)\\
(B\land C)\lor(B\land D)\lor(C\land D)&,\text{第3轮}(40\le i<60)\\
B\oplus C\oplus D&,\text{第4轮}(60\le i<80)\\
\end{cases}
\]
在每一轮也会用到不同的常量\(K[i]\),具体如下:
\[
K[i]=\begin{cases}
\texttt{5A827999}&,\text{第1轮}(0\le i<20)\\
\texttt{6ED9EBA1}&,\text{第2轮}(20\le i<40)\\
\texttt{8F1BBCDC}&,\text{第3轮}(40\le i<60)\\
\texttt{CA62C1D6}&,\text{第4轮}(60\le i<80)\\
\end{cases}
\]
处理完一个块之后将计算结果加入到先前的结果中更新的\(A,B,C,D,E\)(仅需截取结果的低32位),之后再进行下一个块的处理,直到所有块被处理完.
综上可以得到其Python实现如下:
import struct
K = [0x5a827999 for _ in range(20)] + [0x6ed9eba1 for _ in range(20)] + [0x8f1bbcdc for _ in range(20)] + [0xca62c1d6 for _ in range(20)]
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
E = 0xc3d2e1f0
class SHA0:
def __init__(self):
self.A = A
self.B = B
self.C = C
self.D = D
self.E = E
@staticmethod
def _rotl32(x, n):
x &= 0xffffffff
return ((x << n) | (x >> (32 - n))) & 0xffffffff
def checksum(self, msg: bytes):
L = (len(msg) * 8) & 0xffffffffffffffff
msg = msg + b'\x80'
while len(msg) % 64 != 56:
msg += b'\x00'
msg += struct.pack('>Q', L)
for offset in range(0, len(msg), 64):
chunk = msg[offset: offset + 64]
W = list(struct.unpack(">16I", chunk))
for i in range(16, 80):
W.append(W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16])
regA, regB, regC, regD, regE = self.A, self.B, self.C, self.D, self.E
for i in range(80):
if i >= 0 and i < 20:
F = (regB & regC) | ((~regB) & regD)
elif i >= 20 and i < 40:
F = regB ^ regC ^ regD
elif i >= 40 and i < 60:
F = (regB & regC) | (regB & regD) | (regC & regD)
else:
F = regB ^ regC ^ regD
newA = (self._rotl32(regA, 5) + F + regE + W[i] + K[i]) & 0xffffffff
regA, regB, regC, regD, regE = newA, regA, self._rotl32(regB, 30), regC, regD
self.A = (self.A + regA) & 0xffffffff
self.B = (self.B + regB) & 0xffffffff
self.C = (self.C + regC) & 0xffffffff
self.D = (self.D + regD) & 0xffffffff
self.E = (self.E + regE) & 0xffffffff
return struct.pack(">5I", self.A, self.B, self.C, self.D, self.E).hex()SHA-1
SHA-1算法的输出长度为160位(即20字节),消息块长度为512位(即64字节),其与SHA-0算法的唯一区别在于对字串进行扩展一步增加了循环左移一位的操作,即将长度为16字节的字串\(W_t[0],W_t[1],\ldots,W_t[15]\)通过如下规则扩展到80个字:
\[
W_t[i]=\text{leftrotate}(W_t[i-3]\oplus W_t[i-8]\oplus W_t[i-14]\oplus W_t[i-16], 1)
\]
所以可以得到其Python实现如下:
import struct
K = [0x5a827999 for _ in range(20)] + [0x6ed9eba1 for _ in range(20)] + [0x8f1bbcdc for _ in range(20)] + [0xca62c1d6 for _ in range(20)]
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
E = 0xc3d2e1f0
class SHA1:
def __init__(self):
self.A = A
self.B = B
self.C = C
self.D = D
self.E = E
@staticmethod
def _rotl32(x, n):
x &= 0xffffffff
return ((x << n) | (x >> (32 - n))) & 0xffffffff
def checksum(self, msg: bytes):
L = (len(msg) * 8) & 0xffffffffffffffff
msg = msg + b'\x80'
while len(msg) % 64 != 56:
msg += b'\x00'
msg += struct.pack('>Q', L)
for offset in range(0, len(msg), 64):
chunk = msg[offset: offset + 64]
W = list(struct.unpack(">16I", chunk))
for i in range(16, 80):
W.append(self._rotl32(W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16], 1))
regA, regB, regC, regD, regE = self.A, self.B, self.C, self.D, self.E
for i in range(80):
if i >= 0 and i < 20:
F = (regB & regC) | ((~regB) & regD)
elif i >= 20 and i < 40:
F = regB ^ regC ^ regD
elif i >= 40 and i < 60:
F = (regB & regC) | (regB & regD) | (regC & regD)
else:
F = regB ^ regC ^ regD
newA = (self._rotl32(regA, 5) + F + regE + W[i] + K[i]) & 0xffffffff
regA, regB, regC, regD, regE = newA, regA, self._rotl32(regB, 30), regC, regD
self.A = (self.A + regA) & 0xffffffff
self.B = (self.B + regB) & 0xffffffff
self.C = (self.C + regC) & 0xffffffff
self.D = (self.D + regD) & 0xffffffff
self.E = (self.E + regE) & 0xffffffff
return struct.pack(">5I", self.A, self.B, self.C, self.D, self.E).hex()SHA-256
本节涉及到的字节序均为大端序
SHA-256算法的输出长度为256位(即32字节),消息块长度为512位(即64字节),使用SHA-256算法计算消息\(M\)的哈希值流程如下:
首先按照与SHA-0完全一致的填充方式对消息进行填充并将填充后的消息分为若干个512位的分组\(M_1,M_2,\ldots,M_L\).
定义初始状态\(H_s=H_0||H_1||\cdots||H_7\),其中:
\[
\begin{aligned}
&H_0=\texttt{6a09e667}\\
&H_1=\texttt{bb67ae85}\\
&H_2=\texttt{3c6ef372}\\
&H_3=\texttt{a54ff53a}\\
&H_4=\texttt{510e527f}\\
&H_5=\texttt{9b05688c}\\
&H_6=\texttt{1f83d9ab}\\
&H_7=\texttt{5be0cd19}
\end{aligned}
\]
然后对每个512位消息块\(M_t\)(\(t=1,2,\ldots,L\)),将其拆分为16个32位的字\(W_t[0],W_t[1],\ldots,W_t[15]\),之后进行如下递推将字串长度扩展到64个字:
\[
W_t[i]=\sigma_1(W_t[i-2])+W_t[i-7]+\sigma_0(W_t[i-15])+W_t[i-16]
\]
其中\(i=16,17,\ldots,63\),非线性函数\(\sigma_0\)以及\(\sigma_1\)的定义如下:
\[
\begin{aligned}
&\sigma_0(x)=\text{rightrotate}(x,7)\oplus\text{rightrotate}(x,18)\oplus\text{rightshift}(x,3)\\
&\sigma_1(x)=\text{rightrotate}(x,17)\oplus\text{rightrotate}(x,19)\oplus\text{rightshift}(x,10)
\end{aligned}
\]
之后对该串执行64轮运算:
首先分别用临时变量\(a,b,c,d,e,f,g,h\)来存储\(H_0,H_1,\ldots,H_7\),然后对第\(i\)(\(i=0,1,\ldots,63\))轮,计算中间变量\(T_1,T_2\):
\[
\begin{aligned}
&T_1=h+\Sigma_1(e)+\text{Ch}(e,f,g)+K[i]+W_t[i]\\
&T_2=\Sigma_0(a)+\text{Maj}(a,b,c)
\end{aligned}
\]
其中用到的函数分别为:
\[
\begin{aligned}
&\Sigma_0(x)=\text{rightrotate}(x,2)\oplus\text{rightrotate}(x,13)\oplus\text{rightrotate}(x,22)\\
&\Sigma_1(x)=\text{rightrotate}(x,6)\oplus\text{rightrotate}(x,11)\oplus\text{rightrotate}(x,25)\\
&\text{Ch}(e,f,g)=(e\land f)\oplus(\lnot e\land g)\\
&\text{Maj}(a,b,c)=(a\land b)\oplus(a\land c)\oplus(b\land c)
\end{aligned}
\]
而第\(i\)轮用到的常量\(K[i]\)来源于第\(i+1\)个质数的立方根的小数部分的前32位,具体数值如下:
K = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
]之后并行更新:
\[
\begin{cases}
a’=T_1+T_2\\
b’=a\\
c’=b\\
d’=c\\
e’=d + T_1\\
f’=e\\
g’=f\\
h’=g\\
\end{cases}
\]
处理完一个块之后将计算结果加入到先前的结果中更新\(H_0,H_1,\ldots,H_7\)(仅需截取结果的低32位),之后再进行下一个块的处理,直到所有块被处理完.
综上可以得到其Python实现如下:
import struct
K = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
]
H0= 0x6a09e667
H1= 0xbb67ae85
H2= 0x3c6ef372
H3= 0xa54ff53a
H4= 0x510e527f
H5= 0x9b05688c
H6= 0x1f83d9ab
H7= 0x5be0cd19
class SHA256:
def __init__(self):
self.H0 = H0
self.H1 = H1
self.H2 = H2
self.H3 = H3
self.H4 = H4
self.H5 = H5
self.H6 = H6
self.H7 = H7
@staticmethod
def _rotr32(x, n):
x &= 0xffffffff
return ((x >> n) | (x << (32 - n))) & 0xffffffff
@staticmethod
def _shr32(x, n):
x &= 0xffffffff
return (x >> n) & 0xffffffff
@staticmethod
def _sigma0(x):
x &= 0xffffffff
return SHA256._rotr32(x, 7) ^ SHA256._rotr32(x, 18) ^ SHA256._shr32(x, 3)
@staticmethod
def _sigma1(x):
x &= 0xffffffff
return SHA256._rotr32(x, 17) ^ SHA256._rotr32(x, 19) ^ SHA256._shr32(x, 10)
@staticmethod
def _big_sigma0(x):
x &= 0xffffffff
return SHA256._rotr32(x, 2) ^ SHA256._rotr32(x, 13) ^ SHA256._rotr32(x, 22)
@staticmethod
def _big_sigma1(x):
x &= 0xffffffff
return SHA256._rotr32(x, 6) ^ SHA256._rotr32(x, 11) ^ SHA256._rotr32(x, 25)
def checksum(self, msg: bytes):
L = (len(msg) * 8) & 0xffffffffffffffff
msg = msg + b'\x80'
while len(msg) % 64 != 56:
msg += b'\x00'
msg += struct.pack('>Q', L)
for offset in range(0, len(msg), 64):
chunk = msg[offset: offset + 64]
W = list(struct.unpack(">16I", chunk))
for i in range(16, 64):
newW = (self._sigma1(W[i - 2]) + W[i - 7] + self._sigma0(W[i - 15]) + W[i - 16]) & 0xffffffff
W.append(newW)
a = self.H0
b = self.H1
c = self.H2
d = self.H3
e = self.H4
f = self.H5
g = self.H6
h = self.H7
for i in range(64):
Ch = (e & f) ^ (~e & g)
Maj = (a & b) ^ (a & c) ^ (b & c)
T1 = (h + self._big_sigma1(e) + Ch + K[i] + W[i]) & 0xffffffff
T2 = (self._big_sigma0(a) + Maj) & 0xffffffff
a, b, c, d, e, f, g, h = (T1 + T2) & 0xffffffff, a, b, c, (d + T1) & 0xffffffff, e, f, g
self.H0 = (self.H0 + a) & 0xffffffff
self.H1 = (self.H1 + b) & 0xffffffff
self.H2 = (self.H2 + c) & 0xffffffff
self.H3 = (self.H3 + d) & 0xffffffff
self.H4 = (self.H4 + e) & 0xffffffff
self.H5 = (self.H5 + f) & 0xffffffff
self.H6 = (self.H6 + g) & 0xffffffff
self.H7 = (self.H7 + h) & 0xffffffff
return struct.pack(">8I", self.H0, self.H1, self.H2, self.H3, self.H4, self.H5, self.H6, self.H7).hex()SM3
本节涉及到的字节序均为大端序
SM3算法的256位(即32字节),消息块长度为512位(即64字节),使用SM3算法计算消息\(M\)的哈希值流程如下:
首先按照与SHA-0完全一致的填充方式对消息进行填充并将填充后的消息分为若干个512位的分组\(M_1,M_2,\ldots,M_L\).
定义初始状态\(H_0=A||B||C||D||E||F||G||H\),其中:
\[
\begin{aligned}
&A=\texttt{7380166f}\\
&B=\texttt{4914b2b9}\\
&C=\texttt{172442d7}\\
&D=\texttt{da8a0600}\\
&E=\texttt{a96f30bc}\\
&F=\texttt{163138aa}\\
&G=\texttt{e38dee4d}\\
&H=\texttt{b0fb0e4e}
\end{aligned}
\]
然后对每个512位消息块\(M_t\)(\(t=1,2,\ldots,L\)),将其拆分为16个32位的字\(W_t[0],W_t[1],\ldots,W_t[15]\),之后进行如下递推将字串长度扩展到68个字:
\[
W_{t}[i]=P_{1}(\text{leftrotate}(W_t[i-3],15)\oplus W_t[i-9]\oplus W_t[i-16])\oplus W_t[i-6]\oplus \text{leftrotate}(W_t[i-13],7)
\]
其中\(i=16,17,\ldots,67\),该步骤中用到的压缩函数\(P_1\)定义如下:
\[
P_1(x)=x\oplus\text{leftrotate}(x,15)\oplus\text{leftrotate}(x,23)
\]
然后通过下面的算法将前面得到的68个字进一步计算得到一个长度为64字节的串:
\[
W_t'[i]=W_t[i]\oplus W_t[i+4]
\]
其中\(i=0,1,2,\ldots,63\),最终得到一个132字节长的串:
\[
W_t[0],W_t[1],\ldots,W_t[67],W_t'[0],W_t'[1],\ldots,W_t'[63]
\]
之后对该串执行64轮运算,对第\(i\)(\(i=0,1,\ldots,63\))轮,首先计算中间变量:
\[
\begin{aligned}
&SS1=\text{leftrotate}(\text{leftrotate}(A,12)+E+\text{leftrotate}(T[i],i\mod{32}),7)\\
&SS2=SS1\oplus\text{leftrotate}(A,12)\\
&TT1=FF(A,B,C)+D+SS2+W_t'[i]\\
&TT2=GG(E,F,G)+H+SS1+W_t[i]
\end{aligned}
\]
其中每一轮用到的布尔函数\(FF,GG\)的定义如下:
\[
\begin{aligned}
&FF(x,y,z)=\begin{cases}
x\oplus y\oplus z&,0\le i\le15\\
(x\land y)\lor(x\land z)\lor(y\land z)&,16\le i\le63
\end{cases}\\
&GG(x,y,z)=\begin{cases}
x\oplus y\oplus z&,0\le i\le15\\
(x\land y)\lor(\lnot x\land z)&,16\le i\le63
\end{cases}\\
\end{aligned}
\]
而第\(i\)轮用到的常量\(T[i]\)为:
\[
T[i]=\begin{cases}
\texttt{79cc4519}&,0\le i\le15\\
\texttt{7a879d8a}&,16\le i\le63
\end{cases}
\]
之后并行更新:
\[
\begin{cases}
A’=TT1\\
B’=A\\
C’=\text{leftrotate}(B,9)\\
D’=C\\
E’=P_0(TT2)\\
F’=E\\
G’=\text{leftrotate}(F,19)\\
H’=G
\end{cases}
\]
其中:
\[
P_0(x)=x\oplus\text{leftrotate}(x,9)\oplus\text{leftrotate}(x,17)
\]
处理完一个块之后将计算结果\(A||B||C||D||E||F||G||H\)与先前的结果进行异或,之后再进行下一个块的处理,直到所有块被处理完.
综上可以得到其Python实现如下:
import struct
T = [0x79cc4519 for _ in range(16)] + [0x7a879d8a for _ in range(16, 64)]
A = 0x7380166f
B = 0x4914b2b9
C = 0x172442d7
D = 0xda8a0600
E = 0xa96f30bc
F = 0x163138aa
G = 0xe38dee4d
H = 0xb0fb0e4e
class SM3:
def __init__(self):
self.A = A
self.B = B
self.C = C
self.D = D
self.E = E
self.F = F
self.G = G
self.H = H
@staticmethod
def _rotl32(x, n):
x &= 0xffffffff
return ((x << n) | (x >> (32 - n))) & 0xffffffff
@staticmethod
def _p0(x):
x &= 0xffffffff
return (x ^ SM3._rotl32(x, 9) ^ SM3._rotl32(x, 17)) & 0xffffffff
@staticmethod
def _p1(x):
x &= 0xffffffff
return (x ^ SM3._rotl32(x, 15) ^ SM3._rotl32(x, 23)) & 0xffffffff
def checksum(self, msg: bytes):
L = (len(msg) * 8) & 0xffffffffffffffff
msg = msg + b'\x80'
while len(msg) % 64 != 56:
msg += b'\x00'
msg += struct.pack('>Q', L)
for offset in range(0, len(msg), 64):
chunk = msg[offset: offset + 64]
W = list(struct.unpack(">16I", chunk))
for i in range(16, 68):
newW = self._p1(self._rotl32(W[i - 3], 15) ^ W[i - 9] ^ W[i - 16]) ^ W[i - 6] ^ self._rotl32(W[i - 13], 7)
W.append(newW)
W_ = []
for i in range(64):
newW_ = W[i] ^ W[i + 4]
W_.append(newW_)
regA = self.A
regB = self.B
regC = self.C
regD = self.D
regE = self.E
regF = self.F
regG = self.G
regH = self.H
for i in range(64):
if i >= 0 and i < 16:
FF = regA ^ regB ^ regC
GG = regE ^ regF ^ regG
else:
FF = (regA & regB) | (regA & regC) | (regB & regC)
GG = (regE & regF) | ((~regE) & regG)
tmp = (self._rotl32(regA, 12) + regE + self._rotl32(T[i], i & 0x1f)) & 0xffffffff
SS1 = self._rotl32(tmp, 7)
SS2 = SS1 ^ self._rotl32(regA, 12)
TT1 = (FF + regD + SS2 + W_[i]) & 0xffffffff
TT2 = (GG + regH + SS1 + W[i]) & 0xffffffff
regA, regB, regC, regD, regE, regF, regG, regH = TT1, regA, self._rotl32(regB, 9), regC, self._p0(TT2), regE, self._rotl32(regF, 19), regG
self.A = self.A ^ regA
self.B = self.B ^ regB
self.C = self.C ^ regC
self.D = self.D ^ regD
self.E = self.E ^ regE
self.F = self.F ^ regF
self.G = self.G ^ regG
self.H = self.H ^ regH
return struct.pack(">8I", self.A, self.B, self.C, self.D, self.E, self.F, self.G, self.H).hex()针对Merkle–Damgård结构的哈希长度扩展攻击
在Merkle–Damgård结构中,消息先按规则填充,再由压缩函数逐块更新链接变量,最终哈希通常是最后一个链接变量经输出编码得到。长度扩展攻击利用的是:若已知消息\(M\)的长度\(L\)和哈希值\(H(M)\),但不知道\(M\),则可将\(H(M)\)解析为吸收完\(M||\text{pad}(M)\)后的链接变量,并以此为初始状态继续压缩附加数据,从而在不知道\(M\)的情况下伪造新消息
\[
M’=M||\text{pad}(M)||P
\]
的哈希值\(H(M’)\),具体流程如下:
首先攻击者先计算\(M\)的拼接\(\text{pad}(M)\),然后选取需要拼接的\(P\)构造\(M’=M||\text{pad}(M)||P\),然后再计算新消息的填充\(\text{pad}(M’)\),之后以已知的\(H(M)\)对应的链接变量出发继续对\(P||\text{pad}(M’)\)做压缩,最后进行编码输出得到:
\[
H’=H(M||\text{pad}(M)||P)=H(M’)
\]
一般的应用场景为针对使用Merkle–Damgård结构的哈希算法\(H(x)\),将\(H(secret||msg)\)直接用作消息验证码(MAC)对消息的完整性以及真实性进行验证的场景,若攻击者知道\(secret\)的长度,那么他就可以直接构造新消息:
\[
M=msg||\text{pad}(secret||msg)||msg’
\]
(其中\(msg’\)是攻击者选取的)并通过长度扩展攻击来基于\(H(secret||msg)\)直接计算哈希值\(H(secret||M)\)的方式来伪造新消息的MAC,将新消息\(M\)以及伪造的MAC值\(H(secret||M)\)发送给服务端之后,服务端验证\(H(secret||M)\)会通过,此时攻击者就成功伪造了合法的消息.