crypto4c-ch11-消息认证和Hash函数.ppt

《crypto4c-ch11-消息认证和Hash函数.ppt》由会员分享，可在线阅读，更多相关《crypto4c-ch11-消息认证和Hash函数.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、B第第11章章 消息认证和散列函数消息认证和散列函数11.1 对认证的要求对认证的要求11.2 认证函数认证函数11.3 消息认证码消息认证码MAC11.4 散列函数散列函数11.5 散列函数和散列函数和MAC的安全性的安全性B消息消息认证认证认证和加密不同。认证和加密不同。消息认证消息认证是验证消息完整性的一种机制，能是验证消息完整性的一种机制，能发现对消息的篡改或假冒。发现对消息的篡改或假冒。使用对称算法可产生消息认证码使用对称算法可产生消息认证码MAC使用公钥算法可对消息进行签名使用公钥算法可对消息进行签名身份认证是鉴别通信对方的身份是否属实。身份认证是鉴别通信对方的身份是否属实。散列函

2、数散列函数是一个单向的消息摘要函数，在产是一个单向的消息摘要函数，在产生生MAC、签名中有重要用途。、签名中有重要用途。B11.1 认证需求认证需求对网络通信的攻击对网络通信的攻击窃听窃听流量分析流量分析伪装（假冒）伪装（假冒）篡改内容篡改内容修改顺序修改顺序修改时间（包括重放）修改时间（包括重放）发送方抵赖（拒绝承认曾发出过某消息）发送方抵赖（拒绝承认曾发出过某消息）接收方抵赖接收方抵赖B11.2 认证函数认证函数用于用于产生认证符产生认证符的函数类型的函数类型1.对称加密对称加密2.公钥加密公钥加密3.消息认证码消息认证码（MAC）4.散列函数散列函数（Hash）B对称加密能否提供认证对称

3、加密能否提供认证由于密钥没有第三方知道，所以接收方应该由于密钥没有第三方知道，所以接收方应该可以确信消息的来源真实性。可以确信消息的来源真实性。这这并不绝对并不绝对，因为存在一种可能性，是对密，因为存在一种可能性，是对密文的篡改。文的篡改。问题：对密文的篡改，能否一定被察觉？问题：对密文的篡改，能否一定被察觉？除非已知加密前明文的结构特征除非已知加密前明文的结构特征(比如是通常文比如是通常文本本)，而且篡改恰好导致解密后明文丧失了原有，而且篡改恰好导致解密后明文丧失了原有特征，则可怀疑有篡改特征，则可怀疑有篡改B篡改密文，察觉？篡改密文，察觉？CBC模式加密得到密文模式加密得到密文某处被窜改，

4、导致其后续部分解密失败某处被窜改，导致其后续部分解密失败RC4加密中加密中对密文部分比特的篡改导致明文对应部分解密对密文部分比特的篡改导致明文对应部分解密错误（如何察觉？）错误（如何察觉？）随意伪造的密文有可能恰好解密为有效的随意伪造的密文有可能恰好解密为有效的明文明文结论：结论：加密并不能完全抵抗篡改或假冒加密并不能完全抵抗篡改或假冒B教训：对密文的保护教训：对密文的保护在加密之前，给明文在加密之前，给明文添加结构特征添加结构特征M|H(M)加密加密E(M|H(M),K)=C传输有可能出错或被篡改传输有可能出错或被篡改C会变为会变为C解密解密判断恢复的明文是否符合判断恢复的明文是否符合M|H

5、(M)的结构特征的结构特征B公钥加密公钥加密提供保密性提供保密性A使用使用B的公钥加密消息，这不能提供认证。的公钥加密消息，这不能提供认证。提供认证提供认证A使用自己的私钥加密消息，这不能提供保密性。使用自己的私钥加密消息，这不能提供保密性。同时提供保密性和认证同时提供保密性和认证A可以先使用自己的私钥加密消息（即签名），再可以先使用自己的私钥加密消息（即签名），再用用B的公钥加密。的公钥加密。亦需要给明文消息添加结构特征亦需要给明文消息添加结构特征B11.4 Hash函数函数输入是变长的消息输入是变长的消息M，输出是，输出是定长的散列码定长的散列码H(M)，也称为散列值，不使用密钥。也称为散

6、列值，不使用密钥。Hash函数的函数的用途用途给明文增加结构特征以保护密文给明文增加结构特征以保护密文产生认证符，用于消息认证产生认证符，用于消息认证数字签名数字签名从口令衍生密钥从口令衍生密钥挑战挑战-应答认证协议中应答认证协议中也用来产生随机数也用来产生随机数B散列函数的基本用途散列函数的基本用途M|EHMDH(M)密文HM|EHMDE(K,H(M)HM|EHMDE(PRa,H(M)H(1)(2)(3)B散列函数的基本用途散列函数的基本用途M|EHMDE(PRa,H(M)HE密文DKPRaM|H|HSMH(M|S)|SM|H|HE密文DSMH(M|S)|S(4)(5)(6)B散列函数散列函

7、数 h=H(x)函数参数函数参数输入：可以任意长度输入：可以任意长度输出：固定长度输出：固定长度n比特，一般比特，一般n=128、160位位函数特性函数特性单向性单向性：给定：给定h，要找，要找x使使H(x)h是困难的是困难的抗弱碰撞性抗弱碰撞性：对于给定的对于给定的x，找找y，使，使H(y)H(x)是困难的是困难的抗强碰撞性抗强碰撞性：找找x和和y，使，使H(x)H(y)是困难的是困难的*如果碰撞则意味着数字签名容易被伪造如果碰撞则意味着数字签名容易被伪造/欺骗欺骗B单向性单向性若若h=H(M)不满足单向性，则由不满足单向性，则由h可计算出可计算出M。对于使用秘密值对于使用秘密值S的方法，攻

8、击者可通过截获消息得的方法，攻击者可通过截获消息得到到S。攻击者观察到攻击者观察到H(M|S)，计算出计算出M|S，由于由于M以明文以明文形式传输，则攻击者得到形式传输，则攻击者得到S。M|H|HSMH(M|S)|SB抗弱碰撞性抗弱碰撞性若若h=H(M)不满足抗弱碰撞性，则攻击者可伪造消息不满足抗弱碰撞性，则攻击者可伪造消息而不被察觉。而不被察觉。攻击者截获传输中的消息攻击者截获传输中的消息M|E(K,H(M)，由明文形由明文形式的式的M计算出计算出H(M)，再伪造另一条消息，再伪造另一条消息M，使，使H(M)=H(M)，再把，再把M|E(K,H(M)传给接收方。传给接收方。M|EHMDE(K

9、,H(M)HB简单散列函数简单散列函数散列函数运算过程散列函数运算过程输入：输入：n位分组的序列位分组的序列输出：输出：n位散列值位散列值每次处理一个分组，直到所有分组都被处理完每次处理一个分组，直到所有分组都被处理完最简单的散列函数最简单的散列函数将每个分组的相应位异或，即将每个分组的相应位异或，即不满足抗弱碰撞性不满足抗弱碰撞性加以改进加以改进每处理完一个分组后每处理完一个分组后将散列值移位一次将散列值移位一次B改进的简单散列函数改进的简单散列函数运算过程运算过程n位散列值的初值为位散列值的初值为0依次处理每个依次处理每个n位分组：位分组：将当前的散列值循环左移一次将当前的散列值循环左移一

10、次将该分组与散列值异或将该分组与散列值异或不满足抗弱碰撞性不满足抗弱碰撞性很容易产生一条新消息，使之与给定的消息具有很容易产生一条新消息，使之与给定的消息具有相同的散列码相同的散列码设传输中的消息为设传输中的消息为M|E(K,H(M)，则攻击者由则攻击者由M计算出计算出H(M)，将将H(M)循环左移一次循环左移一次，得到得到H(M)，再产生一个再产生一个新分组新分组bx，使使H(M)bx=H(M)。B简单散列函数简单散列函数若对明文消息若对明文消息M和其散列值都加密，则能否保证数据和其散列值都加密，则能否保证数据完整性？完整性？下述加密方法下述加密方法：将每个分组的相应位异或，生成散列码，即将

11、每个分组的相应位异或，生成散列码，即利用利用CBC方式对消息和散列码都加密，生成密文方式对消息和散列码都加密，生成密文B生日攻击生日攻击发送方对消息发送方对消息M“签名签名”，用其私钥对用其私钥对n位散列码加密位散列码加密并将加密后的散列码附于消息之后。并将加密后的散列码附于消息之后。攻击者产生攻击者产生M的的2n/2种变式种变式，且每种变式表达相同的，且每种变式表达相同的意义。攻击者再伪造一条消息意义。攻击者再伪造一条消息M，并产生，并产生M的的2n/2种种变式，攻击者准备用变式，攻击者准备用M替代替代M。比较上述两个集合，找出产生相同散列码的一对消比较上述两个集合，找出产生相同散列码的一对

12、消息。根据息。根据生日悖论生日悖论，找到这对消息的概率大于，找到这对消息的概率大于0.5。攻击者将攻击者将M的有效变式提供给发送方签名，将该签名的有效变式提供给发送方签名，将该签名附于附于M的有效变式之后，发送给接收方。由于两个的有效变式之后，发送给接收方。由于两个变式的散列码相同，所以它们产生的签名也相同。变式的散列码相同，所以它们产生的签名也相同。B生日问题生日问题最多找最多找365+1个人，则必有至少两个人生日相同个人，则必有至少两个人生日相同问：平均找多少个人，能以问：平均找多少个人，能以1/2的概率找到两人生日相同？的概率找到两人生日相同？（不考虑（不考虑2月月29日）日）若若k个人

13、生日均不相同，则可能的情况有个人生日均不相同，则可能的情况有若允许相同，则可能的情况有若允许相同，则可能的情况有365k种种k个人中至少有两人生日相同的概率为个人中至少有两人生日相同的概率为当当k=23时，上式的值为时，上式的值为0.5037当当k=100时，上式的值为时，上式的值为0.9999997B生日悖论生日悖论B生日攻击生日攻击设使用设使用n位散列码，则最多尝试位散列码，则最多尝试2n1条消息，必有条消息，必有至少一对碰撞至少一对碰撞问：平均尝试多少条消息，可以以问：平均尝试多少条消息，可以以1/2的概率找到一的概率找到一对碰撞？对碰撞？2n/2产生消息的变式产生消息的变式改变词的顺序

14、改变词的顺序用同义词或近义词替代原词用同义词或近义词替代原词结论结论散列码应较长散列码应较长BHash函数设计考虑函数设计考虑奇偶校验奇偶校验异或异或只能检出奇数个比特错误只能检出奇数个比特错误CRC常用于帧校验常用于帧校验仍有很高的概率不能检出传输比特错误仍有很高的概率不能检出传输比特错误*不能满足单向性和抗碰撞性不能满足单向性和抗碰撞性复杂的密码学专用散列函数复杂的密码学专用散列函数MD5/SHAB分组链接技术分组链接技术现有散列函数大多基于现有散列函数大多基于CBC，但不用密钥，但不用密钥一种散列函数设计方法一种散列函数设计方法(基于某种加密算法基于某种加密算法)将消息将消息M分成定长的

15、分组分成定长的分组M1,M2,MN使用对称加密体制，计算散列码使用对称加密体制，计算散列码H0=初始值初始值Hi=E(Mi,Hi-1)G=HN该方法也易受生日攻击该方法也易受生日攻击B生日攻击实例生日攻击实例设攻击者能截获一条已签名的消息设攻击者能截获一条已签名的消息M|E(K,H(M)，散列码长度为散列码长度为m位。攻击过程如下：位。攻击过程如下：用上述方法用上述方法由明文由明文M计算出散列码计算出散列码G。构造任何形为构造任何形为 Q1,Q2,QN-2 的消息的消息。对对1i(N-2)，计算算 Hi=E(Qi,Hi-1)。攻击者产生攻击者产生 2m/2 个随机分组，对每个分组个随机分组，对

16、每个分组X，计算计算 HN-1=E(X,HN-2)。再产生再产生 2m/2 个随机分组，对每个分组个随机分组，对每个分组Y，计算计算D(Y,G)，其中其中D是对应是对应E的解密函数的解密函数。根据生日悖论根据生日悖论，X和和Y满足满足E(X,HN-2)=D(Y,G)的概率的概率较大较大构造消息构造消息 Q1,Q2,QN-2,X,Y。该消息的散列码也是该消息的散列码也是G，因此可以将该消息与截获的签名一起发送因此可以将该消息与截获的签名一起发送。B11.3 消息认证码消息认证码 MAC（假定双方共享密钥）（假定双方共享密钥）发送方利用密钥从明文产生一个固定长度的短数据发送方利用密钥从明文产生一个

17、固定长度的短数据块块(MAC)，和消息一起传输。，和消息一起传输。接收方利用密钥计算产生新的接收方利用密钥计算产生新的MAC，与接收到的，与接收到的MAC进行比较。进行比较。消息未被修改消息未被修改消息来自真正的发送方消息来自真正的发送方与加密函数的区别与加密函数的区别不要求可逆不要求可逆更不易被攻破更不易被攻破BMAC函数函数MAC函数是函数是多对一函数多对一函数定义域：变长的消息定义域：变长的消息M值域：值域：MAC值和密钥值和密钥K若消息长度为若消息长度为100位位，MAC值长度为值长度为10位位，密钥长密钥长度为度为5位位，则有则有2100条可能的消息条可能的消息，有有210种可能的种

18、可能的MAC值值，和和25种可能的密钥种可能的密钥。每一种每一种MAC值可以由值可以由2100/210=290条消息产生条消息产生。从消息集合到从消息集合到MAC值的集合有值的集合有25种不同的映射种不同的映射。BMAC的基本用途的基本用途M|CMC(K1,M)CE密文DK2K1M|CMC(K,M)CKM|C密文密文C(K1,E(K2,M)CEDK2K1M(1)(2)(3)B关于加密和认证分离关于加密和认证分离加密能提供某种程度的认证加密能提供某种程度的认证认证和加密的分离带来灵活性认证和加密的分离带来灵活性只要认证而不需保密只要认证而不需保密如公文，软件完整性鉴别如公文，软件完整性鉴别(防病

19、毒防病毒)、网络管理广播、网络管理广播报文报文(如如SNMP)等等不能加密的场合（如法规限制）不能加密的场合（如法规限制）存档期间的保护（而不仅是传输期间）存档期间的保护（而不仅是传输期间）通信某一方负荷很大，没有时间解密所有消息，通信某一方负荷很大，没有时间解密所有消息，但要求能随机认证但要求能随机认证B避免使用加密方法产生避免使用加密方法产生MAC生成生成MAC没有必要整个消息被加密没有必要整个消息被加密速度慢、成本高速度慢、成本高有时不需保密消息有时不需保密消息不需要能恢复明文，但保证明文真实可靠不需要能恢复明文，但保证明文真实可靠Key是必要的是必要的从消息产生认证符的数学方法：散列函

20、数从消息产生认证符的数学方法：散列函数先计算认证符，再把认证符加密的思想先计算认证符，再把认证符加密的思想把散列函数和把散列函数和Key结合，即为结合，即为MACE(K,H(M)相当于相当于 C(K,M)BMAC讨论讨论为了方便，为了方便，MAC码码通常较短通常较短实现实现MAC函数不排斥使用对称加密算法函数不排斥使用对称加密算法实现实现MAC函数希望使用比加密更高效的方法函数希望使用比加密更高效的方法为防止重放攻击，加注时间、消息序号为防止重放攻击，加注时间、消息序号对称对称MAC不能提供签名不能提供签名因为产生因为产生MAC的密钥为两方所有的密钥为两方所有B对对MAC的穷举攻击的穷举攻击如

21、何对如何对MAC使用的使用的K进行穷举攻击进行穷举攻击？假定攻击者可访问假定攻击者可访问M|C(K,M)，且且K的长度的长度k比比MAC值的长度值的长度n要长，即要长，即kn攻击者对每个可能的密钥攻击者对每个可能的密钥Ki，选择截获的第一个明文及选择截获的第一个明文及其其MAC值值M|C(K,M)，计算计算M对应的对应的MAC值值C(Ki,M)。由于产生的由于产生的MAC值有值有2k个个，而实际的而实际的MAC值只有值只有2n个个，因此因此有多个密钥会产生正确的有多个密钥会产生正确的MAC值值。攻击者对剩余的密钥，选择截获的第二个明文及其攻击者对剩余的密钥，选择截获的第二个明文及其MAC值值，

22、进行第二轮的穷举攻击进行第二轮的穷举攻击。依此类推，直到依此类推，直到剩下唯一的密钥剩下唯一的密钥。若若K为为80位位，n为为32位位，则需测试则需测试3轮才能成功轮才能成功。B对对MAC的其它攻击的其它攻击假定消息假定消息M被分成被分成m个个64位的分组位的分组Xi(M)=X1X2XmC(K,M)=E(K,(M)E为DES加密算法加密算法，则K为56位位，MAC值为64位位若攻若攻击者能截者能截获M|C(K,M)，则他可以他可以伪造一条消息造一条消息Y，使之与使之与M具有相同的具有相同的MAC值。攻攻击者生成者生成Y1,Y2,Ym-1计算算Ym=Y1Y2Ym-1(M)将将Y1,Y2,Ym-1

23、,Ym作作为伪造的消息造的消息，连同原同原MAC值一起一起发送送给接收方接收方。B对对MAC函数的要求函数的要求若攻击者已知若攻击者已知 M 和和 C(K,M)，则他构造满足则他构造满足C(K,M)=C(K,M)的消息的消息 M 在计算上是不可在计算上是不可行的行的。C(K,M)应当是应当是均匀分布均匀分布的的，即对任何随机选即对任何随机选择的消息择的消息 M 和和 M，C(K,M)=C(K,M)的概率的概率是是 2-n，其中其中n是是MAC值的位数值的位数。设设 M是是 M的某个已知的变换的某个已知的变换，即即 M=f(M)，则则 C(K,M)=C(K,M)的概率是的概率是 2-n。BCBC

24、模式最后分组做为模式最后分组做为MACFIPS 113B11.5 Hash和和MAC安全性安全性对对Hash函数函数/MAC码的攻击方法码的攻击方法穷举攻击穷举攻击密码分析密码分析B对对Hash的攻击的攻击穷举攻击（输出为穷举攻击（输出为n位的位的Hash函数）函数）抗弱碰撞性的能力为抗弱碰撞性的能力为 2n抗强碰撞性的能力为抗强碰撞性的能力为 2n/2对对MD5的密码分析的密码分析已有重大进展，可以在数小时至数分钟内产生一已有重大进展，可以在数小时至数分钟内产生一对碰撞（攻击抗强碰撞性）对碰撞（攻击抗强碰撞性）一般认为一般认为128位太短，位太短，160位也不够安全位也不够安全B散列函数的典

25、型结构散列函数的典型结构将输入的消息分为将输入的消息分为L个固定长度的分组，每个分组长个固定长度的分组，每个分组长为为b位，不足时需填充，位，不足时需填充，且最后一个分组包含输入的且最后一个分组包含输入的总长度总长度。重复使用重复使用压缩函数压缩函数f，其输入是上一步的，其输入是上一步的n位结果（称位结果（称为链接变量）及当前处理的为链接变量）及当前处理的b位分组，输出一个位分组，输出一个n位位分组。分组。bn，称为压缩。，称为压缩。B散列算法的总体结构散列算法的总体结构B对对MAC码的攻击码的攻击穷举攻击穷举攻击穷举产生穷举产生MAC码的密钥，计算复杂度码的密钥，计算复杂度2k穷举穷举MAC码，计算复杂度码，计算复杂度2nB小结加密可以抵抗窃听，而认证是为了保证消息(进一步身份)的真实性。如果加密时使用合适的方法，也可以把认证特性加入进去，但是把认证和加密分离具有更好的灵活性。认证码的产生需要密钥。为了效率，可以使用Hash函数。从概念上MAC码可以这样产生：Hash（Message|Key）