Hash函数与消息认证

Hash函数与消息认证一、Hash函数概述二、Hash函数MD5三、安全Hash算法SHA四、基于分组密码与离散对数的Hash函数五、消息认证

2023/2/31一、Hash函数概述

Hash函数单向函数函数f(x):A→B若满足下面两个条件，则称为单向函数对于任意x*∈A计算y=f(x)是容易的，其中y∈B。对于x∈A，求y∈B使满足y=f(x)是计算上不可能的。2023/2/33

Hash函数Hash函数设H：将A*映射到An，H满足：H是单向函数。已知x,找x*∈A*，使H(x)=H(x*)在计算上是不可能的。找一对x

和x*，x≠x*，使H(x)=H(x*)在计算上也是不可能的。H称为安全的Hash函数。

2023/2/34

Hash函数Hash函数的分类根据安全水平：弱无碰撞：散列函数H称为是弱无碰撞的，是指对给定消息，在计算上几乎找不到异于x的x*使H(x)=H(x*)。•强无碰撞：散列函数H被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x

，x*使得H(x)=H(x*)。2023/2/35

Hash函数Hash函数的分类根据是否使用密钥带秘密密钥的Hash函数:消息的散列值由只有通信双方知道的秘密密钥K来控制。此时Hash值称作MAC。不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥。此时Hash值称作MDC。2023/2/36

Hash函数Hash函数的用途•消息的完整性检测•数字签名2023/2/37Hash函数hh发送者对h(x)进行加密接收者对y进行解密不安全信道不安全信道xxyxyh(x)h(x)h(x)相等？2023/2/38Hash函数使用Hash函数进行数字签名的好处•提高数字签名的速度。•无需泄露签名所对应的消息，可将签名泄露，如对消息x的签名是Sig(x)，其z=H(x)可将(z,y)公开，而保密x。•可将签名变换和加密变换分开，可以在OSI的不同层提供消息的完整性和机密性。2023/2/39Hash函数

Hash函数的安全性：Hash函数的安全性取决于其抗击各种攻击的能力，对手的目标是找到两个不同消息映射为同一杂Hash值。一般假定对手知道Hash算法，采用选择明文攻击法。2023/2/310Hash函数对Hash函数的基本攻击方法穷举攻击法：给定H=H(H0,M)，其中H0为初值，攻击者在所有可能的M中寻求有利于攻击者的M’，使H(H0,M’)=H(H0,M)，由于限定了目标H(H0,M)来寻找H(H0,M’)，这种攻击法称为目标攻击。若对算法的初值H0不限定，使其H(H0,M)等于H(H0,M’)，则称这种攻击法为自由起始目标攻击。2023/2/311Hash函数对Hash函数的基本攻击方法

生日攻击：这种攻击法不涉及Hash算法的结构，可用于攻击任何Hash算法。强无碰撞函数正是基于生日悖论一类的攻击法定义的。穷举和生日攻击都属选择明文攻击。生日攻击给定初值H0寻找MM’，使H(H0,M’)=H(H0,M)，也可对初始值H0不加限制，即寻找H0’,M’使满足h(H0’,M’)=h(H0,M)。2023/2/312Hash函数生日悖论在一个会场参加会议的人中，找一个与某人生日相同的概率超过0.5时，所需参会人员为183人。但要问使参会人员中至少有两个同日生的概率超过0.5的参会人数仅为23人。这是因为，对于与某个已知生日的人同日生的概率为1/365，若房中有t人，则至少找到一人与此人同日生的概率为。易于解出当t183时可使p>0.5。

2023/2/313

Hash函数Hash函数的迭代构造将不限定长度的输入数据压缩成定长输出的Hash值过程：将输入数字串划分成固定长的段如m比特段将此m比特映射成n比特，称完成此映射的函数为迭代函数。对一段m比特输入做类似映射，以此类推，直到全部输入数字串完全做完，以最后的输出值作为整个输入的Hash值。2023/2/314

Hash函数将mbit到nbit的分组映射或迭代函数的三种选择

m>n。有数据压缩，例如：MD4、MD5SHA等算法。是不可逆映射。

m=n。无数据压缩，亦无数据扩展，通常分组密码采用这类。

m<n。有数据扩展的映射。认证码属于此类。

2023/2/315

Hash函数迭代函数以E表示，一般E又都是通过基本轮函数的多轮迭代实现的，因此，轮函数的设计是Hash函数设计的核心。迭代Hash函数的构造方法安全迭代函数E消息M划分成组M1,M2,…,Mi,…,Mt选定密钥为K，H0为初始向量IV，2023/2/316

Hash函数Rabin法：

H0=IV；Hi=E(Mi,Hi-1)i=1,…,t；H(M)=Ht。密码分组链接(CBC)法：

H0=IV；Hi=E(K,MiHi-1)i=1,2,…,t；H(M)=Ht。密码反馈(CFB)法：

Hi=E(K,Hi-1Mi)，i=1,2,…,t；H(M)=Ht

2023/2/317

Hash函数组合明/密文链接法：

Mt+1=IV；Hi=E(K,MiMi-1Hi-1)i=1,2,…,t；H(M)=Ht+1。修正Daveis-Meyer法：

H0=IV；Hi=E(Hi-1,Mi,Hi-1)(Hi和Mi共同作为密钥)

2023/2/318

Hash函数

B.Preneel总结的下述12种基本方式构造的分组迭代Hash函数。令E是迭代函数，它可以是一种分组加密算法，E(K,X)，K是密钥，X是输入数据组或某种压缩算法。令消息分组为M1,…,Mi,…,H0=I为初始值。

Hi=E(Mi,Hi-1)Hi-1Hi=E(Hi-1,Mi)MiHi-1

Hi=E(Hi-1,MiHi-1)Mi

2023/2/319

Hash函数Hi=E(Hi-1,MiHi-1)MiHi-1Hi=E(Hi-1,Mi)MiHi=E(Mi,MiHi-1)MiHi-1Hi=E(Mi,Hi-1)MiHi-1

Hi=E(Mi,MiHi-1)Hi-1Hi=E(MiHi-1,Mi)MiHi=E(MiHi-1,Hi-1,)Hi-1[Brown等1990]Hi=E(MiHi-1,Mi)Hi-1Hi=E(MiHi-1,Hi-1)Mi

2023/2/320二、Hash函数MD5Hash函数MD5设计目标：

MD5是R.Rivest在MIT开发研究的Hash函数输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位2023/2/322Hash函数MD5

MD5算法对明文输入按512bit分组，最后要填充使其成为512bit的整数倍，且最后一组的后64bit用来表示消息长在mod264下的值K，故填充位数为1～512

bit，填充数字图样为(100…0)，得Y0,Y1,…，YL-1。其中，Yl为512

bit，即16个长为32bit的字，按字计消息长为N=L×16。。2023/2/323Hash函数MD5

MD5算法每轮输出为128bit，可用下述4个32

bits字表示：A，B，C，D。其初始存数以十六制表示为：

A=01234567B=89ABCDEFC=FEDCBA98D=76543210。2023/2/324Hash函数MD5MD5算法HMD5的运算，对512bit(16-字)组进行运算，Yq表示输入的第q组512

bit数据，在各轮中参加运算。T[1,…,64]为64个元素表，分四组参与不同轮的计算。T[i]为232×abs(Sine(i))的整数部分，i是弧度。T[i]可用32bit二元数表示，T是32bit随机数源。

2023/2/325Hash函数MD5

MD5是四轮运算，各轮逻辑函数不同。每轮又要进行16步迭代运算，4轮共需64步完成。每步完成

ab＋CLSS(a＋g(B,C,D)＋X[k]＋T[i])其中a,b,c,d=缓存器中的四个字，按特定次序变化。g=基本逻辑函数F,G,H,I中之一，算法的每一轮用其中之一。2023/2/326ABCD＂fI(ABCD,Yq,T[49…64])++++ABCD＂fF(ABCD,Yq,T[1…16])ABCD＂fH(ABCD,Yq,T[33…48])ABCD＂fH(ABCD,Yq,T[33…48])MDq,128ABCDABCDABCDABCDYq512MDq+1,1282023/2/327+gabcd+++CLSSX[k]T[i]2023/2/328

Hash函数CLSs：32-bit存数循环左移s位。X[k]=M[q×16＋k]：消息的第q-512-bit组的第k个32-bit字T[i]：232×abs(sin(i))的整数部分。＋：模232加法。

T[i]由sin函数构造。每个输入的32bit字被采用4次，每轮用一次，而T[i]中每个元素恰只用一次。每一次，ABCD中只有4个字节更新，共更新16次，在最后第17次产生此组的最后输出。2023/2/329Hash函数表-1各轮的逻辑函数2023/2/330Hash函数表-2逻辑函数的真值表bcdFGHI000000100110100100110011100110000111010101110110011111102023/2/331

Hash函数

MD0=IV（ABCD缓存器的初始矢量）

MDq+1=MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]]MD=MDL—1（最终输出值）。

2023/2/332

Hash函数

MD5的安全性：求具有相同Hash值的两个消息在计算上是不可行的。MD-5的输出为128-bit，若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2128。若采用生日攻击法，寻找有相同Hash值的两个消息需要试验264个消息。差分攻击对MD5的安全性不构成威胁。

2023/2/333

Hash函数

MD5的安全性：对单轮MD5已有攻击结果。与Snefru比较，两者均为32bits字运算。Snefru采用S-BOX，XOR函数，MD5用mod232加。最近山东大学的王小云教授利用用差分分析的方法研究MD5，得到了比较好的算法使MD5能够产生碰撞。因此MD5的安全性还需要进一步提高。2023/2/334三、安全Hash算法SHA安全Hash算法SHA

SHA是美国NIST和NSA设计的一种标准算法SHA(SecureHashAlgorithm)，用于数字签字标准算法DSS(DigitalSignatureStandard)，亦可用于其它需要用Hash算法的情况。SHA具有较高的安全性。输入消息长度小于264bit输出压缩值为160bit2023/2/336安全Hash算法SHA

SHA的描述输入长度少于264比特，输出160比特。输入分成512比特块。附加信息位使长度mod512与448同余。一组64比特附在后面，看作是64比特的整数，包含原来未加附加位的信息长度。2023/2/337安全Hash算法SHA

SHA的描述MD缓冲器初始化。缓冲区分为５个寄存器(A,B,C,D,E)，每个32比特，初始值分别为：

A=67453210B=EFCDAB89C=98BADCFED=10325476E=C3D2E1F0

2023/2/338安全Hash算法SHA对512比特组的信息的处理：算法的核心是４轮操作，每轮20步，每轮的结构类似但是逻辑函数不同，分别为f1,f2,f3,f4

每轮输入512比特，输出160比特。

2023/2/339安全Hash算法SHA对512比特组的信息的处理：

ABCDE,每轮用的常数Kt,,0≤t≤79,其实只有4个不同的常数

5A8279990≤t≤196ED9EBA120≤t≤39Kt＝8F1BDBDC40≤t≤59CA62C1D660≤t≤79当L组运算结束后，由第L步的输出160比特作H(m)。2023/2/340＋＋＋＋＋P1,K,W[0…19]P2,K,W[20…39]P3,K,W[40…59]P4,K,W[60…79]51216032ACDBEACDBEACDBEACDBE1602023/2/341安全Hash算法SHASHA每一步是如下计算的：(A,B,C,D,E)←((E+f(t,B,C,D))+S5(A)+Wt),A,S30(B),C,D)t为步数，f(t,B,C,D)为第t步的逻辑函数。Sk为左旋转移位k位。Wt为由512比特的输入组导出32比特的第t块。Kt为附加的常数。+为mod232的加法。2023/2/342AEDCBAEDCBfS5S30++++WtKt2023/2/343安全Hash算法SHA

每个函数的输入为32比特，输出是一个32比特字，有一系列逻辑运算而得到的。输出的第n位为BCD3输入第n位的函数。

(B∧C)∨(B∧D)0≤t≤19BCD20≤t≤39f(t,B,C,D)=(B∧C)∨(B∧D)∨(C∧D)40≤t≤59BCD60≤t≤792023/2/344安全Hash算法SHA

SHA与MD5的比较最主要不同点，SHA比MD5长了32比特，如果采用强行攻击，SHA显然比MD5抗攻击能力强。MD5已有了密码分析的攻击方法，顾较脆弱。MD5效率比SHA高。两者都比较容易实现。R.L.Rivest公开了MD-5的设计决策，但SHA的设计者则不愿公开。2023/2/345四、基于分组密码与离散对数的Hash函数基于分组密码的Hash函数利用DES构造Hash函数我们将介绍利用DES构造Hash函数的若干模式，实际上也是利用和DES类似的明文、密文长度和密钥长度一样的分组密码来构造Hash函数的模式。设m=m1m2…ml,m=m1m2…ml

都是64比特的明文块，k是密钥，也是64比特。2023/2/347基于分组密码的Hash函数第1种构造模式S1:i←1,K←k;S2:K←DESk(mi),i←i+1;S3:若i≤l,则转S2,否则作Hk(m)←KkDESDESDESm1m2ml…Hk(m)2023/2/348基于分组密码的Hash函数第2种构造模式S1:i←1,S←S0;S2:mi←miS,S←DESk(mi),S3:若i≤l;则转S2,否则作Hk(m)←SS0DESDESDESm1m2ml…kkk2023/2/349基于分组密码的Hash函数第3种构造模式S1:i←1,mi←0,H0←0,mh+1←V;S2:H0←DESk(mi

mi-1

Hi-1),i←i+1；S3:若i≤l+1;则转S2,否则作Hk(m)←Hi+1；其中V为和k类似的参数，H0

和M0

都取为零2023/2/350基于分组密码的Hash函数DESDESDESm1m2ml…kkk…2023/2/351基于离散对数的Hash函数

2023/2/352五、消息认证消息认证认证目的：验证信息的发送者是真的、而不是冒充的，此为实体认证，包括信源、信宿等的认证和识别；验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟等。认证的理论与技术：认证和认证系统、Hash函数、数字签名、身份证明、认证协议。2023/2/354消息认证认证系统一个纯认证系统的模型如图所示。在这个系统中的发送者通过一个公开信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过窜改。系统中的密码分析者不仅要截收和分析信道中传送的密报，而且可伪造密文送给接收者进行欺诈，称其为系统的干扰者(Tamper)更加贴切。实际认证系统可能还要防止收、发之间的相互欺诈。2023/2/355消息认证信道干扰者认证编码器认证译码器信源信宿密钥源认证信道纯认证系统模型2023/2/356消息认证认证系统的组成鉴别编码器和鉴别译码器可抽象为鉴别函数。