《现代密码学-第5章Hash函数与消息认证-20091110(1).ppt》由会员分享，可在线阅读，更多相关《现代密码学-第5章Hash函数与消息认证-20091110(1).ppt（83页珍藏版）》请在三一办公上搜索。
1、1,现代密码学,21世纪高等学校计算机规划教材,Modern Cryptography,彭代渊 信息科学与技术学院 2009.9-2010.1,作 者：何大可 彭代渊 唐小虎 何明星 梅其祥 出版社：人民邮电出版社,2,现代密码学 Modern Cryptography,彭代渊 信息科学与技术学院 2009年11月,第5章 Hash函数与消息认证,3,第5章 Hash函数与消息认证,5.1 Hash函数概述5.2 Hash函数MD55.3 安全Hash算法SHA1 5.4 基于分组密码与离散对数的Hash函数5.5 消息认证,4,5.1 Hash函数概述,5.1.1 Hash函数定义5.1.2
2、 Hash函数的安全性5.1.3 Hash函数的迭代构造法,5,5.1.1 Hash函数定义,数据安全机密性完整性认证性密码技术主要保证数据的机密性Hash函数能保证数据的完整性和认证性,6,5.1.1 Hash函数定义,Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。,将h称为一个Hash函数（hash function），或称为哈希函数、散列函数。对于任何消息x，将h(x)称为x的Hash值、散列值、消息摘要（message digest）。,7,5.1.1 Hash函数定义,Hash函数的碰撞（collision）设x、x是两个不同的消息，
3、如果 h(x)=h(x)则称x和x是Hash函数h的一个（对）碰撞.,8,5.1.1 Hash函数定义,Hash函数的分类单向Hash函数（oneway）给定一个Hash值y，如果寻找一个消息x，使得y=h(x)是计算上不可行的，则称h是单向Hash函数.弱抗碰撞Hash函数（weakly collisionfree）任给一个消息x，如果寻找另一个不同的消息x，使得h(x)=h(x)是计算上不可行的，则称h是弱抗碰撞Hash函数.强抗碰撞Hash函数（strongly collisionfree）如果寻找两个不同的消息x和x，使得h(x)=h(x)是计算上不可行的，则称h是强抗碰撞Hash函数
4、.,9,5.1.1 Hash函数定义,安全Hash函数h应具有以下性质：对任意的消息x，计算h(x)是容易的；h是单向的；h是弱抗碰撞的，或是强抗碰撞的。,10,5.1 Hash函数概述,5.1.1 Hash函数定义5.1.2 Hash函数的安全性5.1.3 Hash函数的迭代构造法,11,5.1.2 Hash函数的安全性,对Hash函数的攻击是指寻找一对碰撞消息的过程生日悖论（birthday paradox）生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？k人生日都不同的概率是：,有P(365,23)=0.5073。
5、即在23个人中，至少有两个人生日相同的概率大于0.5，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。,12,生日攻击法 生日悖论原理可以用于构造对Hash函数的攻击设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。,5.1.2 Hash函数的安全性,13,5.1.2 Hash函数的安全性,生日攻击法分别把消息m和M表示成r和R个变形的消息,14,生日攻击法计算真消息m的变形与假消息M的变形发生碰
6、撞的概率 由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M共有R个变形，所以M的全部变形都不与mi碰撞的概率是：,因为消息m共有r个变形，因此m的变形与M的变形都不碰撞的概率是：,m的变形与M的变形发生碰撞的概率是：,5.1.2 Hash函数的安全性,15,生日攻击法,当r=R=2n/2时，P(n)=1e10.63。对于Hash值长度为64比特的Hash函数，生日攻击的时间复杂度约为232，所以是不安全的。,为了抵抗生日攻击，建议Hash值长度至少为128 比特.,5.1.2 Hash函数的安全性,16,中间相遇攻击（in-t
7、he-middle attack）用于攻击一类具有特殊结构的Hash函数分析Hash函数运算的中间值相等的概率讨论一类利用加密变换构造的Hash函数 设加密体制为：,对于消息m=(m1,m2)，其散列值的计算分以下两步：（1）h1=EK(m1,IV)；（2）d=h(m)=EK(m2,h1)，其中IV是加密变换的初始值。这类Hash函数将遭受中间相遇攻击。,5.1.2 Hash函数的安全性,17,中间相遇攻击（in-the-middle attack）用于攻击一类具有特殊结构的Hash函数分析Hash函数运算的中间值相等的概率讨论一类利用加密变换构造的Hash函数,攻击方式:假设攻击者要找出一个
8、假消息M=(M1,M2)，使得M与m是一个碰撞。设m的散列值都为d。攻击者首先产生消息M1的r个变形，消息M2的R个变形.,5.1.2 Hash函数的安全性,18,5.1.2 Hash函数的安全性,h1=EK(m1,IV)d=h(m)=EK(m2,h1),19,5.1.2 Hash函数的安全性,这里DK是解密变换。假设加密变换EK是随机的，那么可以使用生日攻击法来分析集合H1和H2中出现相同元素的概率。如果集合H1与H2有相同元素，例如h1,i=h2,j=DK(M2,j,d)，则有d=EK(M2,j,h1,i)，即M与m有相同的散列值d。,h1=EK(m1,IV)d=h(m)=EK(m2,h1
9、),20,5.1 Hash函数概述,5.1.1 Hash函数定义5.1.2 Hash函数的安全性5.1.3 Hash函数的迭代构造法,21,5.1.3 Hash函数的迭代构造法,压缩函数（compression function）,迭代技术 设x是一个长度为L的比特串。重复应用压缩函数f，对消息x进行多次压缩，最后得到x的散列值,22,5.1.3 Hash函数的迭代构造法,计算消息x的散列值h(x)的步骤 预处理:用一个公开算法在消息x右方添加若干比特，得到比特串y，使 得y的长度为t的倍数。即有 y=x|pad(x)=y1|y 2|yr,其中|yi|=t(i=1,2,r)，pad(x)称为填
10、充函数。典型的填充函数是先添加x长度|x|的值，再添加若干比特（例如0）。迭代过程:设H0=IV是一个长度为m的初始比特串，重复使用压缩函数f，依次计算 Hi=f(Hi1|yi)(i=1,2,r).输出变换:设g:0,1m0,1t是一个公开函数，令 h(x)=g(Hr).,23,5.1.3 Hash函数的迭代构造法,用上述方法构造的Hash函数称为迭代Hash函数。大多数实用Hash函数都是迭代Hash函数在预处理阶段，必须保证变换xy是单射。因为如果预处理变换xy不是单射，则存在xx使得y=y，从而h(x)=h(x)，即能够找到h的碰撞。对于任意无碰撞的压缩函数，都可以使用迭代技术构造一个无
11、碰撞的Hash函数。,24,第5章 Hash函数与消息认证,5.1 Hash函数概述5.2 Hash函数MD55.3 安全Hash算法SHA1 5.4 基于分组密码与离散对数的Hash函数5.5 消息认证,25,5.2 Hash函数MD5,MD5(MD:message digest,消息摘要)1990年10月,著名密码学家R.L.Rivest在MIT(Massachusetts Institute of Technology)提出了一种Hash函数,作为RFC 1320(RFC:互联网研究和开发机构工作记录)公开发表,称为MD4.MD5是MD4的改进版本,于1992年4月作为RFC 1321公
12、开发表.MD5特性直接构造法:不依赖任何密码系统和假设条件 算法简洁计算速度快特别适合32位计算机软件实现倾向于使用低端结构.,26,5.2.1 MD5算法,MD5算法的输入可以是任意长度的消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为五个步骤。步骤1:增加填充位在消息x右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。即使消息本身已经满足上述长度要求，仍然需要进行填充。例如，若消息长为448，则仍需要填充512位使其长度为960位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。,
13、27,5.2.1 MD5算法,步骤2:附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之。若填充前消息长度大于264，则只使用其低64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。步骤1与步骤2一起称为消息的预处理 经预处理后，原消息长度变为512的倍数设原消息x经预处理后变为消息 Y=Y0 Y1 YL1，其中Yi（i=0,1,L1）是512比特在后面的步骤中，将对512比特的分组Yi进行处理,28,5.2.1 MD5算法,例5.1 假设消息为:x=“abcde”=01100001 01100010 01100011 011
14、00100 01100101=(61 62 63 64 65)16,|x|=40=(28)16.步骤1在x的右边填充1个“1”和407个“0”，将x变成448比特的x1:x1=x|1|0(407个)=x|800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.=61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 0
15、0000000 00000000 00000000 00000000 00000000.,29,5.2.1 MD5算法,例5.1 假设消息为:x=“abcde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16,|x|=40=(28)16.经步骤2处理后的比特串为（16进制表示）：x2=x1|28(64位)=61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 0000000
16、0 00000000 00000000 28000000 00000000.,30,5.2.1 MD5算法,步骤3:初始化MD缓冲区 MD5算法的中间结果和最终结果都保存在128位的缓冲区里，缓冲区用4个32位的寄存器表示。4个缓冲区记为A、B、C、D，其初始值为下列32位整数（16进制表示）：A=67 45 23 01,B=EF CD AB 89,C=98 BA DC FE,D=10 32 54 76.上述初始值以小端格式存储(字的最低有效字节存储在低地址位置)为：字A=01 23 45 67,字B=89 AB CD EF,字C=FE DC BA 98,字D=76 54 32 10.,31,
17、5.2.1 MD5算法,步骤4:以512位的分组(16个字)为单位处理消息 MD5是迭代Hash函数,其压缩函数为:,步骤4是MD5算法的主循环，它以512比特作为分组，重复应用压缩函数HMD5，从消息Y的第一个分组Y1开始，依次对每个分组Yi进行压缩，直至最后分组YL1，然后输出消息x的Hash值。可见，MD5的循环次数等于消息Y中512比特分组的数目L。,32,MD5压缩函数HMD5,HMD5由四轮处理组成加法是指缓冲区中的4个字与CVi中对应的4个字分别模232相加,33,MD5压缩函数HMD5,HMD5的四轮处理过程的算法结构相同，每一轮要对缓冲区ABCD进行16次迭代，每次迭代的运算
18、形式为:,其中a、b、c、d分别为缓冲区A、B、C、D中的字，运算结束后再将（a、b、c、d）循环右移一个字。,34,MD5压缩函数HMD5,HMD5的基本逻辑函数g每一轮使用一个基本逻辑函数g，每个基本逻辑函数的输入是三个32位的字，输出是一个32位的字，它执行位逻辑运算，即输出的第n位是其三个输入的第n位的函数基本逻辑函数g的定义 符号、和分别表示逻辑操作AND、OR、NOT和XOR,35,MD5压缩函数HMD5,HMD5的基本逻辑函数g基本逻辑函数g的真值表,36,MD5压缩函数HMD5,字组X 把当前处理的512比特的分组Yi依次分成16个32比特的字,分别记为X0,1,15.在每一轮
19、的16步迭代中,每一步迭代使用一个字,迭代步数不同使用的字也不相同.因此,16步迭代恰好用完16个字.,37,MD5压缩函数HMD5,对于不同轮处理过程,使用16个字的顺序不一样.第一轮中，使用顺序为X0,1,15。第二轮中使用顺序由下列置换确定:2(i)=(1+5i)mod 16第三轮中使用顺序由下列置换确定:3(i)=(5+3i)mod 16第四轮中使用顺序由下列置换确定:4(i)=7i mod 16.例如:第三轮处理过程的第i步迭代使用字 X3(i)=X(5+3i)mod 16;第8步迭代使用字 X3(8)=X(5+38)=X29=X23.,38,MD5压缩函数HMD5,常数表T：64个
20、32位常数 Ti=232abs(sin(i)的整数部分(i=1,2,64).,39,MD5压缩函数HMD5,常数表T：64个32位常数 Ti=232abs(sin(i)的整数部分(i=1,2,64).常数表T的作用是“随机化”32位的输入数据，即消除输入数据的规律性。HMD5的第k轮处理过程使用常数表T的元素 T16(k1)+1,16(k1)+2,16k(k=1,2,3,4)，第k轮的第i次迭代使用元素 T16(k1)+i(i=1,2,16).,40,MD5压缩函数HMD5,循环左移位数s Ls(v)表示对32位的变量v循环左移s位。s的值与轮数和迭代步数有关。,41,5.2.1 MD5算法,
21、步骤5:输出 依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。可将MD5的处理过程归纳如下：CV0=IVCVi+1=SUM32CVi,RFI(Yi,RFH(Yi,RFG(Yi,RFF(Yi,CVi)(i=0,1,L1)MD=CVL1.IV=第三步定义的缓冲区ABCD的初值L=消息经第一步和第二步处理后分组的个数Yi=消息的第i个512位分组RFu=使用基本逻辑函数u的轮函数SUM32=对输入字的模232相加MD=散列值.,42,5.2.2 MD5的安全性,Rivest猜测，MD5可能是128位Hash函数中强度最大的。目前，对MD5的攻击已取得以
22、下结果：T.Berson（1992）已经证明，对单轮的MD5算法，利用差分密码分析，可以在合理的时间内找出散列值相同的两条消息。这一结果对MD5四轮运算的每一轮都成立。但是，目前尚不能将这种攻击推广到具有四轮运算的MD5上.B.Boer和A.Bosselaers（1993）说明了如何找到消息分组和MD5两个不同的初始值,使它们产生相同的输出.也就是说,对一个512位的分组,MD5压缩函数对缓冲区ABCD的不同值产生相同的输出,这种情况称为伪碰撞（pseudo-collision）.目前尚不能用该方法成功攻击MD5算法.,43,5.2.2 MD5的安全性,H.Dobbertin（1996）找到了
23、MD5无初始值的碰撞(pseudo-collision).给定一个512位的分组,可以找到另一个512位的分组,对于选择的初始值IV0,它们的MD5运算结果相同.到目前为止,尚不能用这种方法对使用MD5初始值IV的整个消息进行攻击.我国山东大学王小云教授（2004）提出的攻击对MD5最具威胁。对于MD5的初始值IV，王小云找到了许多512位的分组对，它们的MD5值相同.国际密码学家Lenstra利用王小云等提供的MD5碰撞，伪造了符合X.509标准的数字证书.MD5算法抗密码分析能力较弱,对MD5的生日攻击所需代价为264数量级.所以,必须设计新的Hash算法,使其与MD5相比具有更长的散列值
24、和更高的安全性.,44,第5章 Hash函数与消息认证,5.1 Hash函数概述5.2 Hash函数MD55.3 安全Hash算法SHA1 5.4 基于分组密码与离散对数的Hash函数5.5 消息认证,45,5.3 安全Hash算法SHA1,安全Hash算法SHA（secure hash algorithm）由美国标准与技术研究所（NIST）设计并于1993年作为联邦信息处理标准（FIPS 180）发布修改版于1995年发布（FIPS 1801），通常称之为SHA1。该标准称为安全Hash函数。RFC 3174也给出了SHA1，它基本上是复制FIPS 1801的内容，但增加了C代码实现。SHA
25、1算法的输入是长度小于264的任意消息x，输出160位的散列值。,46,5.3.1 SHA1算法步骤,SHA1处理消息的过程与MD5类似，对输入消息按512位的分组为单位进行处理，整个算法分为五个步骤步骤1:增加填充位 在消息右边增加若干比特，使其长度与448模512同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在1到512之间。填充比特的第一位是“1”，其它均为“0”。步骤2:附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。步骤1与步骤2一起称为消息的预处理 经预处理后，原消息长度变为512的倍数。设原消息x经预处理后变为消息Y=Y0 Y1
26、YL1，其中Yi（i=0,1,L1）是512比特。在后面的步骤中，将对512比特的分组Yi进行处理。,47,5.3.1 SHA1算法步骤,步骤3:初始化缓冲区 SHA1算法的中间结果和最终结果保存在160位的缓冲区里，缓冲区用5个32位的寄存器表示。5个缓冲区记为A、B、C、D、E，其初始值为下列32位整数（16进制表示）：A=67 45 23 01,B=EF CD AB 89,C=98 BA DC FE,D=10 32 54 76,E=C3 D2 E1 F0.其中，前4个初始值与MD5的初始值相同。SHA1以大端格式存储缓冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为
27、（十六进制）：字A=67 45 23 01,字B=EF CD AB 89,字C=98 BA DC FE,字D=10 32 54 76,字E=C3 D2 E1 F0.,48,5.3.1 SHA1算法步骤,步骤4:以512位的分组（16个字）为单位处理消息SHA1是迭代Hash函数，其压缩函数为：,步骤4是SHA1算法的主循环，它以512比特作为分组，重复应用压缩函数HSHA，从消息Y的第一个分组Y1开始，依次对每个分组Yi进行压缩，直至最后分组YL1，然后输出消息x的Hash值。SHA1循环次数等于消息Y中512比特分组的数目L。,49,SHA1的压缩函数HSHA,由四轮处理组成加法是模232相
28、加,50,SHA1的压缩函数HSHA,压缩函数HSHA的四轮处理过程的算法结构相同，每一轮要对缓冲区ABCDE进行20次迭代，每次迭代的运算形式为,其中A、B、C、D、E分别为五个缓冲区中的字，运算结束后再将（A、B、C、D、E）循环右移一个字。,51,SHA1的压缩函数HSHA,基本逻辑函数f每一轮使用一个基本逻辑函数f，每个基本逻辑函数的输入是三个32位的字，输出是一个32位的字，它执行位逻辑运算，即输出的第n位是其三个输入第n位的函数。,52,SHA1的压缩函数HSHA,基本逻辑函数f基本逻辑函数f的真值表,53,SHA1的压缩函数HSHA,字组Wt t（0t79）代表迭代步数，依次表示
29、第一、二、三、四轮处理过程进行的迭代次序Wt(0t79)是32比特的字，它的前面16个字W0,W1,W15依次取自当前输入分组Yi，其余字为,加法常数表Kt,54,5.3.1 SHA1算法步骤,步骤5:输出第L个分组处理后的输出值即是消息x的散列值MD(x)SHA1的处理过程归纳如下：CV0=IV CVi+1=SUM32(CVi,ABCDEi)(i=0,1,L1)MD=CVL1其中：IV=第三步定义的缓冲区ABCDE的初值ABCDEi=处理第i个消息分组时最后一轮的输出L=消息经第一步和第二步处理后分组的个数SUM32=对输入字的模232相加MD=散列值.,55,5.3.2 SHA1和MD5的
30、比较,SHA1与MD5的算法类似，所以它们的性质极为相似抗穷举攻击的能力SHA1抗穷举攻击的能力比MD5强 用穷举攻击方法产生具有给定散列值的消息MD5需要的代价为2128数量级SHA1需要的代价为2160数量级 用穷举攻击方法产生两个具有相同散列值的消息 MD5需要的代价为264数量级SHA1需要的代价为280数量级 抗密码分析的能力 MD5算法抗密码分析的能力较弱SHA1算法抗密码分析的能力似乎并不弱,56,5.3.2 SHA1和MD5的比较,速度 SHA1执行的速度比MD5的速度慢得多 简洁性 SHA1和MD5两种算法都易于描述和实现，不需要使用大的程序和置换表 数据的存储方式 MD5使
31、用littleendian方式，SHA1使用bigendian方式。这两种方式没有本质的差异,57,第5章 Hash函数与消息认证,5.1 Hash函数概述5.2 Hash函数MD55.3 安全Hash算法SHA1 5.4 基于分组密码与离散对数的Hash函数5.5 消息认证,58,5.4 基于分组密码与离散对数的Hash函数,Hash函数的间接构造法利用已有的密码算法构造Hash函数如果密码算法是安全的，那么利用它所构造的Hash函数也是安全的,59,5.4.1 利用分组密码算法构造Hash函数,已知条件 设Ek是一个分组长度为n的分组密码的加密算法，密钥为k，对于任意的消息x，首先对x进行
32、分组，每组的长度为n。设消息x为:x=x1 x2xL,其中xi GF(2)n（1 i L）.,60,5.4.1 利用分组密码算法构造Hash函数,基于分组密码CBC工作模式构造Hash函数首先选取一个初始值:y0=IVGF(2)n，然后依次计算:最后定义Hash值为:hCBC(x)=yL.,61,基于分组密码CFB工作模式构造Hash函数首先选取一个初始值:y0=IVGF(2)n，然后依次计算:最后定义Hash值为:hCFB(x)=yL.,5.4.1 利用分组密码算法构造Hash函数,在密钥公开的情况下，基于分组密码CBC工作模式和CFB工作模式构造的Hash函数是不安全的，它们甚至不是弱无碰
33、撞的.,62,基于一些困难数学问题，诸如离散对数问题、因子分解问题、背包问题等可以构造出一些Hash函数，这些Hash函数的安全性依赖于对应数学问题的困难性Chaum、Heijst和Pfitzmann（1992年）提出的基于离散对数问题构造的Hash函数运行速度不是很快可以证明是安全的.ChaumHeijstPfitzmann Hash函数的构造 设p是一个大素数，q=(p1)/2是一个素数，和 是Zp的两个本原元。假设离散对数log是计算上不可行的。定义Hash函数h为：,5.4.2 基于离散对数问题的Hash函数,63,ChaumHeijstPfitzmann Hash函数是强抗碰撞的 用
34、反证法，如果Hash函数h有一对碰撞，那么可以证明离散对数log能被有效计算.设(x1,x2)，(x3,x4)是h的一对碰撞消息，即(x1,x2)(x3,x4)，h(x1,x2)=h(x3,x4)，那么,5.4.2 基于离散对数问题的Hash函数,记d=gcd(x4x2,p1)。因为p1=2q，且q是一个素数，所以d1,2,q,p1。下面对d的四个取值分别进行讨论。,64,ChaumHeijstPitzmann Hash函数是强抗碰撞的,5.4.2 基于离散对数问题的Hash函数,情况1：d=1 此时x4x2关于模p1有逆，设y=(x4x2)1 mod(p1)，则存在整数k，使得(x4x2)y
35、=1+(p1)k，则有,因此，可计算离散对数,65,5.4.2 基于离散对数问题的Hash函数,情况2：d=2 因为p1=2q,且q是奇数,所以gcd(x4x2,q)=1.设y=(x4x2)1 mod q，则存在整数k，使得(x4x2)y=1+qk,有,66,5.4.2 基于离散对数问题的Hash函数,情况3：d=q 因为 0 x2q1,0 x4q1(q1)x4x2q1 gcd(x4x2,q1)=q不成立.情况3不存在.,67,第5章 Hash函数与消息认证,5.1 Hash函数概述5.2 Hash函数MD55.3 安全Hash算法SHA1 5.4 基于分组密码与离散对数的Hash函数5.5
36、消息认证,68,5.5 消息认证,认证（authentication）是防止网络系统遭受主动攻击的重要技术认证的主要目的有两个第一，验证消息的发送者是真的，而不是冒充的，称为实体认证，包括信源、信宿等的认证和识别。第二，验证信息的完整性，即验证数据在传送或存储过程中未被篡改、重放或延迟，称为消息认证。,69,5.5.1 消息认证码,带密钥的Hash函数称为消息认证码(MAC：message authentication code).消息认证码是实现消息认证的重要工具.MAC有两个不同的输入，一个是消息x，另一个是密钥K.MAC产生定长的输出.实例:某一个大公司A想给它的客户发布一个新产品的广告
37、,A希望不对广告内容加密,但又希望其它公司不能修改广告内容或冒充公司A发布同样的广告,或者当广告内容被修改后能够发现.如果使用不带密钥的Hash函数,由于其它公司可能在修改广告内容后产生新的散列值,从而使A无法确认原广告是否被修改.设计MAC算法的要求 在不知道密钥的情况下，难以找到两个不同的消息具有相同的输出。,70,5.5.1 消息认证码,基于分组密码CBC工作模式构造MAC基于分组密码CBC工作模式构造MAC算法已经成为ISO/IEC 9797 标准，它使用密文链接和双密钥三重加密技术。设EK表示以K为密钥的加密算法，设K是一个与K不同的密钥，消息分组长度为n。首先把消息x分成L个n位块
38、 x=x1 x2xL，计算：hK是一个n位MAC.记为CBC-MAC.,71,5.5.1 消息认证码,基于Hash函数构造MAC设h是一个（不带密钥）Hash函数，K是密钥，x是消息，则定义消息认证码hK如下：,72,5.5.1 消息认证码,将密钥K扩展成3个16字节的子密钥K0，K1，K2，其中 把K0，K1分成4个32位的子串Kji（j=0,1,i=0,1,2,3）,对MD5进行修改：用K0代替MD5的4个32位寄存器ABCD.把K1i与MD5第i+1遍中每个常数232sin(j)进行模232加法.将512位的分组 链接到消息x右边，再按MD5的要求进行填充.,将上一步的结果输入到修改后的
39、MD5中，取其输出的前一半（64位）作为消息x的消息认证码MD5-MAC(x).MD5-MAC软件实现比较容易，其运算速度与MD5大体相近.,73,5.5.2 HMAC算法,消息认证码HMAC（keyed-hashing for message authentication code）是Bellare等人于1996年提出，1997年作为RFC 2104发表，成为事实上的Internet标准，包括IPSec协议在内的一些安全协议都使用了HMAC算法。HMAC算法利用已有的Hash函数，关键问题是如何使用密钥。使用不同的Hash函数，就可以得到不同的HMAC。选用MD5时的HMAC记为HMAC-M
40、D5，选用SHA-1时的HMAC记为HMAC-SHA1。,74,5.5.2 HMAC算法,HMAC算法描述设HMAC使用的Hash函数为h，每次处理的输入分组长度为b比特（使用MD5与SHA-1时，b=512），最后的输出长度为l比特（使用MD5时，l=128；使用SHA-1时，l=160）。如果HMAC的输入消息为x，则x=x1 x2xL，其中每一个分组xi（1iL）的长度为b比特。令HMAC使用的密钥为K，密钥K可以是任意的、长度不超过b比特的比特串（HMAC算法推荐密钥最小长度为l比特）。当密钥K的长度超过b比特时，使用Hash函数h对K进行压缩，把K作为h的输入，并将输出的l比特作为密
41、钥K。,75,5.5.2 HMAC算法,HMAC算法的流程图,76,5.5.2 HMAC算法,HMAC算法具体执行步骤(1)如果密钥K的长度小于b 比特，则在其右边填充一些“0”，使其成为长度为b比特的比特串，仍记为K。(2)计算Si=Kipad，其中ipad是HMAC算法中规定的一个长度为b比特的比特模式串，它等于将00110110重复b/8次后得到的比特串。(3)把HMAC的输入消息x=x1 x2xL附加在Si的右端，得到Si|x=Si|x1x2xL，将该比特串作为Hash函数h的输入，得到l比特的输出h(Si|x)。(4)计算So=Kopad，其中opad是HMAC算法中规定的另一个长度
42、为b比特的比特模式串，它等于将01011010重复b/8次后得到的比特串。(5)将第(3)步得到的h(Si|x)附加在So的右端，并以该比特串作为Hash函数h的输入，得到l比特的输出。(6)将第(5)步的输出作为HMAC算法的最终输出结果，即消息x的消息认证码HMAC(x)。,77,5.5.2 HMAC算法,HMAC的安全性建立在嵌入Hash函数基础上的所有MAC，其安全性在某种程度上都依赖于该Hash函数的强度。对于HMAC，可以给出HMAC的强度与所嵌入Hash函数强度之间的关系。根据伪造者在给定时间内伪造成功和用相同密钥产生给定数量的消息-MAC对的概率，可以用于描述MAC的安全性。B
43、ellare等人（1996年）已经证明，如果攻击者已知若干（时间、消息-MAC）对，则成功攻击HMAC的概率等价于对所嵌入Hash函数的下列攻击之一：(1)即使对于攻击者而言，IV是随机的、秘密的和未知的，攻击者也能计算压缩函数的输出。(2)即使IV是随机的和秘密的，攻击者也能找到Hash函数的碰撞。在目前的计算水平下，使用MD5和SHA-1等作为HMAC算法所嵌入的Hash函数，HMAC的安全性是可以保证的。,78,5.5.3 应用,数据完整性数据完整性是指数据在生成、传送或存储过程中没有被非法篡改.使用Hash函数可以保证数据的完整性使用MAC 设用户A将消息x发送给接收者B，A与B共享秘
44、密的MAC密钥K，hK是MAC。用户A计算x的MAC hK(x)，将数据C=x|hK(x)发送给B。B通过其它方法确定用户A的身份，分开接收到的数据x，使用共享密钥K计算hK(x)，并与接收到的hK(x)相比较。如果hK(x)=hK(x)，则B确定消息x是来自于具有密钥K的用户A，在传输过程中未被篡改。,79,5.5.3 应用,使用Hash函数和加密 设A与B共享分组密码的密钥K,EK是加密算法,h是公开的Hash函数.用户A计算C=EK(x|h(x),并将数据C发送给B.B利用密钥K进行解密,得到x和h(x)，然后计算h(x),并与接收到的h(x)相比较.如果h(x)=h(x),则B确定消息
45、x是真实的.由于这里对h(x)进行了加密,所以对Hash函数h的要求可以适当降低.,80,5.5.3 应用,加密使用MAC和加密 设A与B共享分组密码的密钥K和MAC的密钥K,EK是加密算法,hK是MAC。用户A计算C=EK(x|hK(x),并将数据C发送给B.B利用密钥K进行解密,得到x和hK(x),然后计算hK(x),并与接收到的hK(x)相比较.如果hK(x)=hK(x),则B确定消息x是真实的.该技术的优点是即使加密算法被攻破,MAC仍然能提供完整性保护作用.其缺点是需要管理K和K两个密钥.,81,5.5.3 应用,实现数据源认证数据源认证也称为消息认证,它是要求证实一个实体在过去某个
46、时刻建立的数据源.数据源认证也包括数据完整性.提供数据源认证的方法有:(1)使用消息认证码MAC;(2)对附加上散列值的消息进行加密.设用户A将消息x发送给接收者B,A与B共享密钥K,则用户A向B发送以下数据可实现数据源的认证.(1)EK(x|h(x):提供保密(仅双方共享K)和认证(加密保护散列值);(2)x|EK(h(x):提供认证（加密保护散列值）;(3)x|h(x|S)：提供认证（仅双方共享随机数S）；(4)EK(x|h(x|S)：提供保密和认证（仅双方共享K、S）。,82,5.5.3 应用,由于加密软件慢、硬件费用高、加密算法专利保护和出口限制等因素,人们倾向于不使用带有加密的认证方法,愿意使用方法(3)。数据源认证方案不能提供数据源的不可拒绝性，因为任何一方都可以使用共享密钥创建一个消息及其认证。如果需要解决这种潜在的争执，可以使用可信第三方或公钥技术。使用MAC能够确定数据是在过去某个时间由特定一方生成的，但是不能提供唯一性和时间上的保证，也不能发现消息是否重用或重发。为了解决这些问题，必须使用随时间变化的参数，例如时间戳、序列号和随机数等。,83,第5章 习 题,P.129-130,习题1-11.,
