1. 基本概念
1.1 Hash函数的概念
Hash函数也称哈希函数/散列函数、杂凑函数,是一个从消息空间到像空间的不可逆映射,可将“任意”长度的输入经过变换以后得到固定长度的输出。它是一种单向密码体制,即只有加密过程,不存在解密过程。
Hash函数的单向性和输出长度固定的特征使其可生成消息的“数字指纹”(Digital Fingerprint),也称消息摘要(MD,Message Digest)或哈希值/散列值(Hash Value),主要应用于消息认证、数字签名、口令的安全传输与存储、文件完整性校验等方面。
哈希值的生成过程表示为:h = H ( M ) h=H(M)h=H(M),其中
- M MM为任意长度的消息
- H HH为哈希(Hash)函数或称杂凑函数、散列函数
- h hh为固定长度的哈希值
1.2 Hash函数的性质
- (1)输入消息为任意有限长度,输出哈希值是固定长度。
- (2)易计算:对于任意给定的消息M MM,易计算其哈希值h = H ( M ) h=H(M)h=H(M)。
- (3)单向性:又称为抗原像性(Preimage Resistance),对任意给定的散列值h hh,找到满足H ( M ) = h H(M)=hH(M)=h的消息M MM在计算上是不可行的。
- (4)抗弱碰撞性:又称为抗第二原像性(Second Preimage Resistance),对任何给定的消息M MM,找到满足M ≠ M ′ M \neq M^{'}M=M′且H ( M ) = H ( M ′ ) H(M)=H(M')H(M)=H(M′)的消息M ′ M'M′在计算上是不可行的。
- (5)抗强碰撞性:找到任何满足H ( M ) = H ( M ′ ) H(M)=H(M')H(M)=H(M′)的偶对( M , M ′ ) (M,M')(M,M′)在计算上是不可行的。
此外,Hash 函数应具有雪崩效应,即当消息的输入位发生变化时,输出的散列值至少有一半发生变化。
1.3 Hash函数的结构
Hash函数的一般结构称为迭代Hash函数结构,由Merkle和amgảrd分别独立提出。Hash函数将输入消息分为L LL个固定长度的分组,每一分组长为b bb位,最后一个分组包含输入消息的总长度,若最后一个分组不足b bb位时,需要将其填充为b bb位。
散列算法迭代使用一个压缩函数f ff,压缩函数f ff是散列算法的核心,它有两个输人:一个是前一次迭代的位输出,称为链接变量;另一个为消息的b bb位分组,并产生一个n ( n < b ) n(n<b)n(n<b)位的输出。第一迭代输入的链接变量又称为初值变量,由算法在开始时指定,最后一次迭代的输出即为散列值。
2. MD5算法
MD5算法由美国麻省理工学院著名密码学家Rivest设计,他于1992年向IETF提交的RFC1321中对MD5作了详尽的阐述。MD5是在MD2、MD3、MD4的基础上发展而来,由于在MD4上增加了Safety-Belts,MD5又被称为是“系有安全带的MD4”。
2.1 算法结构
MD5算法的输入是最大长度小于2 64 2^{64}264bit的消息,输入消息以512 bit的分组为单位处理,输出为128 b i t 128bit128bit的消息摘要。
输入消息长度为N NN,Y i ( i = 0 , 1 , . . . , L − 1 ) Y_i(i=0,1,...,L-1)Yi(i=0,1,...,L−1)为消息分组,其中L LL为消息扩充后分组个数
I V IVIV表示初始链接变量,由4个32位的寄存器A、B、C、D构成
C V i CV_iCVi是链接变量,即是每个分组处理单元的出,也是下个分组处理单元的输人
C V N CV_NCVN是最后单元的输出,即消息的散列值
(1)附加填充位
填充一个“ 1 ” “1”“1”和若干个“ 0 ” “0”“0”使其长度模512 512512与448 448448 同余,然后再将消息的真实长度以64 6464bit表示附加在填充结果的后面,使得消息长度恰好为512 512512bit的整数倍,即512 × L 512\times L512×Lbit。
(2)分组处理(迭代压缩)
MD5算法的分组处理(压缩函数)由4轮组成,512bit的消息分组M i M_iMi被均分为16个子分组(每个子分组32bit)参与每16步函数运算。每步的输入是4个32bit的链接变量和一个32bit的消息子分组,输出为32位值。经过4轮共64步后,得到的4个寄存器值分别输入链接变量进行模加,即是当前消息的中间散列值。
2.2 压缩函数
MD5的步函数,即压缩函数,先取向量( A , B , C , D ) (A,B,C,D)(A,B,C,D)中的后3个作一次非线性函数运算,然后将所得的结果依次加上第1个变量、M [ j ] M[j]M[j]、T [ i ] T[i]T[i],再将所得结果循环左移s ss位,并加上( A , B , C , D ) (A,B,C,D)(A,B,C,D)中的第2个变量B BB,最后把新值赋给向量中的第1个变量。
详细过程如下所示,其中M [ j ] M[j]M[j]为消息分组M i M_iMi的第j ( 0 ≤ j ≤ 15 ) j(0≤j≤15)j(0≤j≤15)个32bit子分组
(1)伪随机常数
T [ i ] = ⌊ 2 32 × a b s ( sin ( i ) ) ⌋ T[i] =\lfloor 2^{32} \times abs (\sin(i))\rfloorT[i]=⌊232×abs(sin(i))⌋(i ii为弧度, 1 ≤ i ≤ 64 1\leq i \leq 641≤i≤64)用来消除输入数据的规律性。 如:T [ 28 ] = ⌊ 4294967296 × a b s ( sin ( 28 ) ) ⌋ ≈ ⌊ 1163531501.0793967247 ⌋ = 1163531501 T[28]= \lfloor 4294 967 296\times abs(\sin(28)) \rfloor \approx \lfloor 1163531501.0793967247 \rfloor = 1163531501T[28]=⌊4294967296×abs(sin(28))⌋≈⌊1163531501.0793967247⌋=1163531501
再将1163531501 11635315011163531501转化为十六进制455 A 14 E D 455A14ED455A14ED。
(2)循环左移
**< < < s <<<s<<<s**表示循环左移s ss位,共有16个常量数值:
r o u n d 1 : 7 , 12 , 17 , 22 r o u n d 2 : 5 , 9 , 14 , 20 r o u n d 3 : 4 , 11 , 16 , 23 r o u n d 4 : 6 , 10 , 15 , 21 round 1: 7, 12, 17, 22 \\ round 2: 5, 9, 14, 20 \\ round 3: 4, 11, 16, 23 \\ round 4: 6, 10, 15, 21round1:7,12,17,22round2:5,9,14,20round3:4,11,16,23round4:6,10,15,21
(3)非线性函数
MD5的4轮操作分别使用4个不同的非线性函数(每轮操作中的16步使用同一函数):F 、 G 、 H 、 I F、G、H、IF、G、H、I,定义如下:
第一轮:F ( x , y , z ) = ( x ∧ y ) ∨ ( ¬ x ∧ z ) F(x,y,z)=(x\wedge y)\lor (\lnot x\land z)F(x,y,z)=(x∧y)∨(¬x∧z)第二轮:G ( x , y , z ) = ( x ∧ z ) ∨ ( y ∧ ¬ z ) G(x,y,z)=(x\land z)\lor (y\land \lnot z)G(x,y,z)=(x∧z)∨(y∧¬z)第三轮:H ( x , y , z ) = x ⊕ y ⊕ z H(x,y,z)=x\oplus y \oplus zH(x,y,z)=x⊕y⊕z第四轮:I ( x , y , z ) = y ⊕ ( x ∨ ¬ z ) I(x,y,z)=y\oplus (x\lor \lnot z)I(x,y,z)=y⊕(x∨¬z)
其中,x 、 y 和 z x、y和zx、y和z是3个32bit的输入变量,输出是一个32bit变量;∧ 、 ∧ 、 ¬ 、 ⊕ \wedge、\land、\lnot、\oplus∧、∧、¬、⊕分别表示与、或、非和异或逻辑运算。
如第一轮中,F F ( a , b , c , d , M [ j ] , s , T [ i ] ) FF(a,b,c,d,M[j],s,T[i])FF(a,b,c,d,M[j],s,T[i]) 表示:a = b + ( ( a + ( F ( b , c , d ) + M [ j ] + T [ i ] ) < < < s ) a=b+((a+(F(b,c,d)+M[j]+T[i])<<<s)a=b+((a+(F(b,c,d)+M[j]+T[i])<<<s)其中,0 ≤ j ≤ 15 , 1 ≤ i ≤ 64 0≤j≤15, 1\leq i \leq 640≤j≤15,1≤i≤64,16步如下:
FF(A,B,C,D,M[0],7,T[1]) | FF(D,A,B,C,M[1],12,T[2]) | FF(C,D,A,B,M[2],17,T[3]) | FF(B,C,D,A,M[3],22,T[4]) |
FF(A,B,C,D,M[4],7,T[5]) | FF(D,A,B,C,M[5],12,T[6]) | FF(C,D,A,B,M[6],17,T[7]) | FF(B,C,D,A,M[7],22,T[8]) |
FF(A,B,C,D,M[8],7,T[9]) | FF(D,A,B,C,M[9],12,T[10]) | FF(C,D,A,B,M[10],17,T[11]) | FF(B,C,D,A,M[11],22,T[12]) |
FF(A,B,C,D,M[12],7,T[13]) | FF(D,A,B,C,M[13],12,T[14]) | FF(C,D,A,B,M[14],17,T[15]) | FF(B,C,D,A,M[15],22,T[16]) |
第4轮最后一步完成后,执行如下运算:A ≡ ( A + A A ) m o d 2 32 , B ≡ ( B + B B ) m o d 2 32 A \equiv (A+AA)\bmod 2^{32},B \equiv (B+BB)\bmod 2^{32}A≡(A+AA)mod232,B≡(B+BB)mod232C ≡ ( C + C C ) m o d 2 32 , D ≡ ( D + D D ) m o d 2 32 C \equiv (C+CC)\bmod 2^{32} ,D \equiv (D+DD)\bmod 2^{32}C≡(C+CC)mod232,D≡(D+DD)mod232然后把A 、 B 、 C 、 D A、B、C、DA、B、C、D的值作为下一个迭代的初始值,直到最后一个消息分组的输出( A ∣ ∣ B ∣ ∣ C ∣ ∣ D ) (A||B||C||D)(A∣∣B∣∣C∣∣D)就是128bit的消息Hash值。
3. SHA1算法
1993年,美国国家标准技术研究所NIST公布了安全散列算法SHA0(Secure Hash Algorithm)标准,1995年4月17日,公布的修改版本称为SHA-1,是数字签名标准中要求使用的算法。
2002年,NIST在FIPS 180-1的基础上发布了FIPS 180-2,这个标准中除SHA1之外还新增加了SHA256、SHA384和SHA512三个散列算法标准。它们的消息摘要长度分别是256 bit、384 bit 和 512 bit,以便与 AES的使用相匹配。
4种Hash算法的相关属性区别(单位:bit):
SHA1 | SHA256 | SHA384 | SHA512 | |
消息摘要长度 | 160 | 256 | 384 | 512 |
消息长度 | < 2 64 <2^{64}<264 | < 2 64 <2^{64}<264 | < 2 128 <2^{128}<2128 | < 2 128 <2^{128}<2128 |
分组长度 | 512 | 512 | 1024 | 1024 |
字长度 | 32 | 32 | 64 | 64 |
步数 | 80 | 64 | 80 | 80 |
3.1 算法结构
SHA1算法的输入是最大长度小于2 64 2^{64}264bit的消息,输入消息以512 bit的分组为单位处理,输出为160 160160bit的消息摘要,因此抗穷举性更好。
SHA-1设计基于MD4,它有5个参与运算的32位寄存器,消息分组和填充方式与MD5相同,主循环也同样是4轮,但每轮进行20次操作,非线性运算、移位和加法运算也与MD5类似,但非线性函数、加法常数和循环左移操作的设计有一些区别。
(1)附加填充位
填充一个“ 1 ” “1”“1”和若干个“ 0 ” “0”“0”使其长度模512 512512与448 448448同余,然后再将消息的真实长度以64 6464bit表示附加在填充结果的后面,使得消息长度恰好为512 512512bit的整数倍,即512 × L 512\times L512×Lbit。
(2)分组处理(迭代压缩)
SHA1以512位的分组为单位处理消息,算法核心是一个包含4个循环的模块,每个环由20个步骤组成,每个循环使用的步函数相同,不同的循环中步函数包含不同的非线性函数(Ch、Parity、Maj、Parity)。
每一步函数的输入也不相同,除了寄存器A 、 B 、 C 、 D A、B、C、DA、B、C、D和E EE外,还有额外常数K KK、与消息分组相关的W [ t ] W[t]W[t],其中t ( 0 ≤ t ≤ 79 ) t(0 \leq t \leq 79)t(0≤t≤79)为步数。
每一循环均以当前正在处理的512 512512 bit的Y q Y_qYq和160 160160bit的缓存值A 、 B 、 C 、 D A、B、C、DA、B、C、D和E EE为输入,然后更新缓存的内容。最后一步的输模2 32 2^{32}232加上第一循环的输入C V q CV_qCVq产生C V q + 1 CV_{q+1}CVq+1。全部512 512512bit数据块处理完毕后,输出160 160160bit的Hash值。
3.2 压缩函数
SHA1的步函数,即压缩函数每一轮循环的形式如下,其中t ( 0 ≤ t ≤ 79 ) t(0 \leq t \leq 79)t(0≤t≤79)为步数。
A = ( R O T L 5 ( A ) + f t ( B , C , D ) + E + W t + K t ) m o d 2 32 A=(ROTL^5(A)+f_t(B,C,D)+E+W_t+K_t)\bmod 2^{32}A=(ROTL5(A)+ft(B,C,D)+E+Wt+Kt)mod232B = A B=AB=AC = R O T L 30 ( B ) m o d 2 32 C=ROTL^{30}(B) \bmod 2^{32}C=ROTL30(B)mod232D = C D=CD=CE = D E=DE=D
(1)常数K t K_tKt
K的4 44个取值分别为2 、 3 、 5 2、3、52、3、5和10 1010的平方根,然后再乘以2 30 2^{30}230=1073741824,最后取结果整数部分的十六进制。
步数t tt | K t K_tKt值 |
0 ≤ t ≤ 19 0\leq t \leq 190≤t≤19 | 0 x 5 A 827999 0x5A8279990x5A827999 |
20 ≤ t ≤ 39 20\leq t \leq 3920≤t≤39 | 0 x 6 E D 9 E B A 1 0x6ED9EBA10x6ED9EBA1 |
40 ≤ t ≤ 59 40\leq t \leq 5940≤t≤59 | 0 x 8 F 1 B B C D C 0x8F1BBCDC0x8F1BBCDC |
60 ≤ t ≤ 79 60\leq t \leq 7960≤t≤79 | 0 x C A 62 C 1 D 6 0xCA62C1D60xCA62C1D6 |
以计算K t ( 60 ≤ t ≤ 79 ) K_t(60\leq t \leq 79)Kt(60≤t≤79)为例,⌊ 10 × 2 30 ⌋ = 3395469782 \lfloor \sqrt{10}\times 2^{30} \rfloor = 3395469782⌊10×230⌋=3395469782
再将3395469782 33954697823395469782转化为十六进制C A 62 C 1 D 6 CA62C1D6CA62C1D6。
(2)循环左移
R O T L n ( x ) = ( x < < n ) ROTL^n(x) = (x<<n)ROTLn(x)=(x<<n)表示对32bit的变量x xx循环左移n nnbit。
(3)生成字W t W_tWt
32bit的字W t W_tWt从512bit消息分组中导出,在前16步处理中W t W_tWt值等于消息分组中的相应字:
W t = M t i , 0 ≤ t ≤ 15 W_t=M^{i}_t, 0\leq t \leq 15Wt=Mti,0≤t≤15
而余下的64步操作中,其值是由前面的4个值相互异或后再循环移位得到:
W t = R O T L 1 ( W t − 3 ⊕ W t − 8 ⊕ W t − 14 ⊕ W t − 16 ) 16 ≤ t ≤ 79 W_t=ROTL^1(W_{t-3}\oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16}) 16\leq t \leq 79Wt=ROTL1(Wt−3⊕Wt−8⊕Wt−14⊕Wt−16)16≤t≤79
上述操作增加了被压缩分组的冗余性和相互依赖性,故对于相同分组的消息找出具有相同压缩结果的消息会非常困难。
4. Hash函数的攻击
散列函数的安全性主要体现在其良好的单向性和对碰撞的有效避免。由于散列变换是一种消息收缩型变换,当消息和散列值长度相差较大时,仅知散列值难以给恢复消息提供足够的信息,因此仅通过散列值来恢复消息的难度,大于对相同分组长度的分组密码进行唯密文攻击的难度。
对于Hash函数攻击的主要目标不是恢复原始的消息,而是用相同散列值的非法消息进行伪造和欺骗,这就要求散列函数必须抵抗碰撞攻击。
对输出长度是128 128128bit的散列函数,能够满足H ( M ) = H ( M ′ ) H(M)=H(M')H(M)=H(M′)的概率是2 128 2^{128}2128。
则,满足H ( M ) ≠ H ( M ) H(M)≠H(M)H(M)=H(M)的概率是:1 − 2 128 1-2^{128}1−2128尝试k kk个任意消息而没有一个能够满足H ( M ) = H ( M ′ ) H(M)=H(M')H(M)=H(M′)的概率是( 1 − 2 − 128 ) k (1-2^{-128})^k(1−2−128)k至少有一个M ′ M'M′满足H ( M ) = H ( M ′ ) H(M)= H(M')H(M)=H(M′)的概率是1 − ( 1 − 2 − 128 ) k 1-(1-2^{-128})^k1−(1−2−128)k
由二项式定理可知,攻击者至少要尝试2 127 2^{127}2127个消息,伪造成功的概率才能超过0.5 0.50.5,现有的计算能力还难以在2 127 2^{127}2127这个空间内进行穷举搜索,可以看出输出长度是128 128128bit的散列函数似乎是安全的。但事实上,攻击者通过其他攻击方法,如生日攻击,可以实现碰撞。
目前的攻击方式对于输出长度是160 160160bit以上的散列函数还是计算不可行的,一般认为160 160160bit以上的散列函数是安全的。
4.1 生日悖论
生日悖论问题:假定每个人的生日是等概率的,每年365天,若k kk个人中至少有两个人的生日相同的概率大于1 / 2 1/21/2,最小k kk值是多少?
将每个人的生日看作[ 1 , 365 ] [1,365][1,365]的随机变量,k kk个人的生日不重复的概率:p k = p 365 k 36 5 k = 365 × 364 × … ( 365 − k + 1 ) 36 5 k p_k=\frac{p^{k}_{365}}{365^k}=\frac{365\times 364\times…(365-k+1)}{365^k}pk=365kp365k=365k365×364×…(365−k+1)当k = 23 k=23k=23时,p k ≈ 0.4927 p_k\approx 0.4927pk≈0.4927,从而23 2323个人的生日至少有一个重复的概率为1 − p k ≈ 0.5073 1-p_k\approx 0.50731−pk≈0.5073。
当k = 100 k=100k=100时,1 − p k ≈ 0.9999997 1-p_k \approx 0.99999971−pk≈0.9999997,即100 100100个人的生日至少有一个重复的概率基本为必然事件概率,这个结果与人们的直觉不太一致,这就是生日悖论(Birthday Paradox)。
其实从k kk个人中抽出一个人,这个人与其他人具有相同生日的人的概率只有1 365 \frac{1}{365}3651。但若仅仅是找两个生日相同的人(即不指定特定的日期),在相同的范围内的概率就大得多。
对于输出长度128 128128bit的散列函数求碰撞,类似于上述情况。要找到与特定的消息具有相同散列值的另一个消息的概率很小.但若在两组消中找到具有相同散列值的两个消息(即不指定散列值),就会容易很多。
4.2 集合相交问题
两个k元集合X = x 1 , x 2 , … , x k , Y = y 1 , y 2 , … , y k X={x_1,x_2,…,x_k},Y={y_1,y_2,…,y_k}X=x1,x2,…,xk,Y=y1,y2,…,yk,其中x i , y i , 1 ≤ i , j ≤ k x_i,y_i,1 \leq i,j \le kxi,yi,1≤i,j≤k是( 1 , 2 , … , n ) (1,2,…,n)(1,2,…,n)上的均匀分布的随机变量。
取定x i x_ixi,若y j = x i y_j=x_iyj=xi,则称y j y_jyj与x i x_ixi匹配。固定i , j i,ji,j,y j y_jyj与x i x_ixi匹配的概率是1 n \frac{1}{n}n1
则y j ≠ x i y_j \neq x_iyj=xi的概率为:1 − 1 n 1-\frac{1}{n}1−n1Y YY中所有k kk个随机变量都不等于x i x_ixi的概率为:( 1 − 1 n ) k (1-\frac{1}{n})^k(1−n1)k若X , Y X,YX,Y中的k kk个随机变量两两互不相同,则X XX与Y YY中不存在任何匹配的概率为:( 1 − 1 n ) k 2 (1-\frac{1}{n})^{k^2}(1−n1)k2因此,X XX与Y YY中至少有一个匹配的概率:p = 1 − ( 1 − 1 n ) k 2 p=1-(1-\frac{1}{n})^{k^2}p=1−(1−n1)k2当x ≥ 0 x \ge 0x≥0时,必然有( 1 − x ) ≤ e − x (1-x) \le e^{-x}(1−x)≤e−x,故得:p = 1 − ( 1 − 1 n ) k 2 > 1 − ( e 1 n ) k 2 p=1-(1-\frac{1}{n})^{k^2}>1-(e^{\frac{1}{n}})^{k^2}p=1−(1−n1)k2>1−(en1)k2若想要p > 0.5 p>0.5p>0.5,令1 − ( e 1 n ) k 2 = 0.5 1-(e^{\frac{1}{n}})^{k^2}=0.51−(en1)k2=0.5,可求出:k = n ln 2 ≈ 0.83 n ≈ n k=\sqrt{n\ln 2} \approx 0.83 \sqrt{n} \approx \sqrt{n}k=nln2≈0.83n≈n
4.3 生日攻击
假设散列函数H HH输出长度为m mm,全部可能的输出有2 m 2^m2m个,接收k kk个随机输入产生X XX,接收另外k kk个随机输入产生Y YY。
根据“两个集合相交”问题,当k = 2 m / 2 k=2^{m/2}k=2m/2时,X XX与Y YY至少存在一对匹配(即散列函数产生碰撞)的概率大于0.5 0.50.5。因此,2 m / 2 2^{m/2}2m/2将决定输出长度为m mm的散列函数H HH抗碰撞的强度。
生日攻击也称为平方根攻击。其原理如下:
- 攻击者首先产生一份合法消息,通过加入空格等方式改变写法或格式(保持含义不变)产生2 m / 2 2^{m/2}2m/2个不同的消息变形,即产生一个合法消息组。
- 攻击者再产生一份要伪造签名的非法消息组
- 分别对以上两组消息产生散列值
- 在两组消息中找出具有相同散列值的一对消息。若未找到,则增加每组消息变形数目,直至找到为止。
由生日悖论可知,其成功的可能性非常大,从而使攻击者可以找到一个与合法消息具有相同散列值的非法消息,也就是找到了散列碰撞。
目前对于Hash函数攻击最有效的攻击方法是模差分方法,又称“比特追踪法”,由王小云等人在分析MD4系列散列函数时首次提出。模差分方法是结合整数模差分和XOR差分而定义的一种新的差分,相较于单一的一种差分,两种差分结合能够表达更多信息。
5. 消息认证
信息安全一方面要实现消息的保密传送,使其可以抵抗被动攻击,如窃听攻击等;另一方面还要防止攻击者对系统的主动攻击,如伪造或篡改消息等。
认证(Authentication)是对抗主动攻击的主要方法,分为实体认证和消息认证两种:
- 实体认证:验证实体的身份
- 消息认证:验证消息的真实性
- 验证消息来源的真实性,一般称之为信息源认证
- 验证消息的完整性,即验证消息在传输和存储过程中没有被篡改、伪造等
5.1 消息认证码
消息认证的基础是生成消息认证码(MAC,Message Authentication Code),用来检查消息是否被恶意修改。
认证码与通信学中的检错码不同:
- 检错码是用来检测由于通信的缺陷而导致消息发生错误的特殊代码
- 认证码是用来防止攻击者恶意篡改或伪造消息
消息认证码利用消息和双方共享的密钥通过认证函数来生成一个固定长度的短数据块,并将该数据块附加在消息后。
5.2 HMAC
利用DES、AES等对称分组密码体制的密码分组链接模式(CBC)一直是构造MAC的最常见的方法,如FIPS PUB 113中定义的CBC-MAC。
由于MD5、SHA-1等Hash函数软件执行速度比DES等对称分组密码算法要快,目前提出了许多基于Hash函数的消息认证算法。其中,HMAC(RFC 2014)已作为FIPS 198标准发布,并且在SSL中用于消息认证。
HMAC结构如下:
其中,
- K KK表示密钥,密钥长度可以是任意长度,最小推荐长度为n nnbit,因为小于n nnbit会显著降低函数的安全性,大于n nnbit也不会增加安全性
- M MM表示HMAC的消息输入
- L LL表示消息M MM中的分组数
- Y i Y_iYi表示消息M MM的第i ii个分组
- b bb表示每个分组包含的比特数
- n nn表示嵌入的散列函数产生的散列码长度
- I V IVIV表示初始链接变量
- ipad表示字节0x36重复b / 8 b/8b/8次后的结果
- opad表示字节0x5C重复b / 8 b/8b/8次后的结果
HMAC可描述为:H M A C ( K , M ) = H [ ( K + ⊕ o p a d ) ∣ ∣ ( K + ⊕ i p a d ) ∣ ∣ M ] HMAC(K,M)=H[(K^+ \oplus opad)||(K^+ \oplus ipad)||M]HMAC(K,M)=H[(K+⊕opad)∣∣(K+⊕ipad)∣∣M]
操作流程如下:
- (1)密钥K KK的左边填充0 00,以产生一个b bb比特长的K + K^+K+(例如K KK的长为160 160160比特,b = 512 b=512b=512,则需填充44 4444个零字节0 x 00 0x000x00)。
- (2)K + K^+K+与ipad逐比特异或产生b比特的分组S 1 S_1S1
- (3)将消息M MM附加到S 1 S_1S1后
- (4)将Hash函数H HH作用于步骤(3)的结果,生成消息摘要
- (5)K + K^+K+与opad逐比特异或产生b比特的分组S 0 S_0S0
- (6)将步骤(4)生成的消息摘要链接在S 0 S_0S0后
- (7)将Hash函数H HH作用于步骤(6)的结果,生成消息摘要,并输出最终结果
实现HMAC更有效的方法如下图所示,其中f ( I V , ( K + ⊕ i p a d ) ) f(IV,(K^+ \oplus ipad))f(IV,(K+⊕ipad))和f ( I V , ( K + ⊕ o p a d ) ) f(IV,(K^+ \oplus opad))f(IV,(K+⊕opad))是预计算的两个值,式中f ff为散列函数的压缩函数,其输入是n nn位的链接变量和b bb位的分组,输出是n nn位的链接变量。上述值只有在初始化或密钥改变时才需要计算,这些预先计算的值取代了函数的初始值I V IVIV。在输入HMAC函数的消息都都较短的情况下,这种实现意义极大。