消息认证与杂凑算法.ppt

现代密码理论,-UESTC,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,消息认证与杂凑算法,抗击被动攻击,：,加密,抗击主动攻击：,消息认证,消息认证是一个过程，用以验证接收消息的,真实性和完整性,，同时还用于验证消息的,顺序性和时间性,。,消息认证机制需要产生,认证符,。,认证符：,用于认证消息的数值。,认证符的产生方法：,消息认证码,MAC,（message authentication code）,和,杂凑函数,（,hash function）,两大类。,消息认证码:,指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值,或称为密码校验和。,此时需要通信双方,A,和,B,共享一密钥,K。,5,.1 消息认证码,5,.1.1 消息认证码的定义及使用方式,如果仅收发双方知道,K，,且,B,计算得到的,MAC,与接收到的,MAC,一致，则这一就实现了以下功能：,接收方相信发送方发来的消息未被篡改。,接收方相信发送方不是冒充的。,MAC,函数与加密算法类似，不同之处为,MAC,函数,不必是可逆的,，因此与加密算法相比更不易被攻破。,上述过程中，由于消息本身在发送过程中是明文形式，所以这一过程只提供认证性而未提供保密性。,图,5,.1,MAC,的基本使用方式,5,.1.2 产生,MAC,的函数应满足的要求,(1),消息认证码的穷搜索攻击的代价比使用相同长度密钥的加密算法的穷搜索攻击还要大。,攻击者可假冒发假消息 给接收方。,(2),有些攻击法却不需要寻找产生,MAC,所使用的密钥。,先说明两点，然后给出,MAC,函数应满足的要求。,第1轮,已知,M,1,、MAC,1,，,其中,MAC,1,=C,K,(M,1,)。,对所有2,k,个可能的密钥计算,MAC,i,=C,Ki,(M,1,)，,得2,k-n,个可能的密钥。,第2轮,已知,M,2,、MAC,2,，,其中,MAC,2,=C,K,(M,2,)。,对上一轮得到的2,k-n,个可能的密钥计算,MAC,i,=C,Ki,(M,2,)，,得2,k-2n,个可能的密钥。,如此下去，如果,k=n，,则上述攻击方式平均,需要,轮,。例如，密钥长为80比特，,MAC,长为32比特，则第1轮将产生大约2,48,个可能密钥，第2轮将产生2,1,6,个可能的密钥，第3轮即可找出正确的密钥。,攻击,MAC(,找,K):,例如:,设,M=(X,1,X,2,X,m,),是由,6,4比特长的分组,X,i,(i=1,m),链接得到的，其消息认证码由以下方式得到：,其中 表示异或运算，加密算法是电码本模式的,DES。,因此，密钥长为5,6,比特，,MAC,长为,6,4比特，如果敌手得到,MC,K,(M),，,那么敌手使用穷搜索攻击寻找,K,将需做2,5,6,次加密。,然而敌手还可用以下方式攻击系统：,且,M,的,MAC,与原消息,M,的,MAC,相同。,考虑到,MAC,所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数,C，,但不知道密钥,K：,如果敌手得到,M,和,C,K,(M)，,则构造一满足,C,K,(M)=C,K,(M),的新消息,M,在计算上是不可行的。,C,K,(M),在以下意义下是均匀分布的：随机选取两个消息,M、M，PrC,K,(M)=C,K,(M)=2,-n,，,其中,n,为,MAC,的长。,若,M,是,M,的某个变换，即,M=f(M)，,例如,f,为插入一个或多个比特，那么,P,r,C,K,(M)=C,K,(M)=2,-n,。,数据认证算法：,最为广泛使用的,消息认证码,中的一个,。,算法基于,CBC,模式的,DES,算法,，其初始向量取为零向量。需被认证的数据被分为,6,4比特长的分组,D,1,，D,2,，,，D,N,，,其中最后一个分组不够,6,4比特的话，可在其右边填充一些0，然后按以下过程计算数据认证码：,5,.1.3 数据认证算法,图,5,.2 数据认证算法,其中,E,为,DES,加密算法，,K,为密钥。,数据认证码或者取为,O,N,或者取为,O,N,的最左,M,个比特，其中1,6,M64。,杂凑函数,H,是一公开函数,：用于将任意长的消息,M,映射为较短的、固定长度的一个值,H(M)。,作为认证符。,称函数值,H(M),为杂凑值、杂凑码、消息摘要，,hash,值、散列值。,杂凑码是消息中所有比特的函数，因此提供了一种,错误检测能力,，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。,5,.2 杂凑函数,5,.2.1 杂凑函数的定义及使用方式,认证函数：,Hash,函数（续）,哈希函数的基本用法（,a,）,M,|,H(M),H,K,H,M,比较,E,K,M,D,M,Bob,Alice,提供认证,提供保密,E,K,(M|H(M),认证函数：,Hash,函数（续）,哈希函数的基本用法（,b,）,M,|,K,E,K,(H(M),H,H,M,比较,E,D,Bob,Alice,提供认证,K,认证函数：,Hash,函数（续）,哈希函数的基本用法（,c,）,M,|,K,b,D,Kb,(H(M),H,H,M,比较,D,E,Bob,Alice,提供,认证,K,b,认证函数：,Hash,函数（续）,哈希函数的基本用法,(d),M,|,K,D,Kb,(H(M),H,H,M,比较,E,D,Bob,Alice,提供认证,提供保密,K,M,M,D,K,b,E,K,b,E,k,(M|D,Kb,(H(M),认证函数：,Hash,函数（续）,哈希函数的基本用法（,e,）,M,|,H(M|S),|,H,M,比较,Bob,Alice,提供认证,S,S,|,H,认证函数：,Hash,函数（续）,哈希函数的基本用法（,f,）,M,|,H(M|S),|,K,H,M,比较,E,K,M,D,M,Bob,Alice,提供认证,提供保密,E,K,(M|H(M|S),S,S,|,H,杂凑函数的目的是为需认证的数据产生一个,“,指纹,”,。为了能够实现对数据的认证，杂凑函数应满足以下条件：,函数的输入可以是任意长。,函数的输出是固定长。,已知,x，,求,H(x),较为容易，可用硬件或软件实现。,已知,h，,求使得,H(x)=h,的,x,在计算上是不可行的，这一性质称为函数的单向性，称,H(x),为,单向杂凑函数,。,已知,x，,找出,y(yx),使得,H(y)=H(x),在计算上是不可行的。,如果单向杂凑函数满足这一性质，则称其为,弱单向杂凑函数,。,找出任意两个不同的输入,x、y，,使得,H(y)=H(x),在计算上是不可行的。,强单向杂凑函数,。,5,.2.2 杂凑函数应满足的条件,1.相关问题,已知一杂凑函数,H,有,n,个可能的输出，,H(x),是一个特定的输出，如果对,H,随机取,k,个输入，则至少有一个输入,y,使得,H(y)=H(x),的概率为0.5时，,k,有多大？,以后为叙述方便，称对杂凑函数,H,寻找上述,y,的攻击为,第类生日攻击,。,5,.2.3 生日攻击,因为,H,有,n,个可能的输出，所以输入,y,产生的输出,H(y),等于特定输出,H(x),的概率是1/,n，,反过来说,H(y)H(x),的概率是1-1/,n。y,取,k,个随机值而函数的,k,个输出中没有一个等于,H(x)，,其概率等于每个输出都不等于,H(x),的概率之积，为1-1/,n,k,，,所以,y,取,k,个随机值得到函数的,k,个输出中至少有一个等于,H(x),的概率为1-1-1/,n,k,。,由(1+,x),k,1+kx，,其中|,x|365，,则不可能使得任意两个数据都不相同，因此假定,k365。k,个数据项中任意两个都不相同的所有取值方式数为,MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC 1320，1321）称为MD5。,1 杂凑函数的定义及使用方式,1 消息认证码的定义及使用方式,认证函数：Hash函数（续）,若取n=365，则 。,CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVq,压缩函数HMD5中有4轮处理过程，每轮又对缓冲区ABCD进行16步迭代运算，每一步的运算形式:,可不经修改使用现有hash函数,接收方相信发送方不是冒充的。,考虑到MAC所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数C，但不知道密钥K：,哈希函数的基本用法（c）,以分组为单位对消息进行处理：每一分组Yq都经一压缩函数处理，压缩函数由4轮处理过程（如图5.,如果去掉任意两个都不相同这一限制条件，可得,k,个数据项中所有取值方式数为3,6,5,k,。,所以可得,当,k=23,时，,P(365,23)=0.5073，,即上述问题只需23人，人数如此之少。若,k,取100，则,P(365,100)=0.9999997，,即获得如此大的概率。之所以称这一问题是悖论是因为当人数,k,给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。,将生日悖论推广为下述问题：,已知一个在1到,n,之间均匀分布的整数型随机变量，若该变量的,k,个取值中至少有两个取值相同的概率大于0.5，则,k,至少多大？,与上类似，,，,令,P(n,k)0.5，,可得,。,若取,n=365，,则,。,3.生日攻击,生日攻击基于结论：设杂凑函数,H,有2,m,个可能的输出（即输出长,m,比特），如果,H,的,k,个随机输入中至少有两个产生相同输出的概率大于0.5，则,。,第类生日攻击：,寻找函数,H,的具有相同输出的两个任意输入的攻击方式。,A,B,敌手对,M,产生出2,m/2,个变形消息:,敌手还准备一个假冒的消息,M，,产生出2,m/2,个变形的消息:,将 提交给,A,请求签字,A,B,A,B,第类生日攻击方式：,第类生日攻击方式：,设用户将用图,(,c),所示的方式发送消息，即,A,用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往接收者。,敌手对,A,发送的消息,M,产生出2,m/2,个变形的消息,，同时,敌手还准备一个假冒的消息,M，,并对假冒的消息产生出2,m/2,个变形的消息。,敌手在产生的两个消息集合中，找出杂凑值相同的一对消息,，,由上述讨论可知敌手成功的概率大于0.5。如果不成功，则重新产生一个假冒的消息，并产生2,m/2,个变形，直到找到杂凑值相同的一对消息为止。,敌手将 提交给,A,请求签字,，由于 与 的杂凑值相同，所以可将,A,对 的签字当作对,的签字，将此签字连同,一起发给意欲的接收者。,将一个消息变形为具有相同含义的另一消息的方法有很多。,例如：对文件，敌手可在文件的单词之间插入很多,“,space-space-backspace,”,字符对，然后将其中的某些字符对替换为,“,space-backspace-space,”,就得到一个变形的消息。,目前使用的大多数杂凑函数其结构都是迭代型的，如下图所示。,5,.2.4 迭代型杂凑函数的一般结构,图,5,.4 迭代型杂凑函数的一般结构,CV,0,=IV=n,比特长的初值；,CV,i,=f(CV,i-1,Y,i-1,)1iL；,H(M)=CV,L,CV,i-1,，,称为,链接变量,通常,bn,，,称函数,f,为压缩函数,分析时需要先,找出,f,的碰撞,MD4,是,MD5,杂凑算法的前身，由,Ron Rivest,于1990年10月作为,RFC,提出，1992年4月公布的,MD4,的改进（,RFC 1320，1321）,称为,MD5。,5,.3,MD5,杂凑算法,MD5,算法采用图,5,.4描述的,迭代型杂凑函数,的一般结构，算法的框图如图,5,.5所示。,输入：,任意长,的消息,（图中为,K,比特）,分组：,512,比特,输出：,128,比特的消息摘要。,5,.3.1 算法描述,图,5,.5,MD5,的算法框图,对消息填充：,对消息填充，使得其比特长在模512下为448，即填充后消息的长度为512的某一倍数减,6,4，留出的,6,4比特备第2步使用。,步骤是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为448比特，则需填充512比特，使其长度变为9,6,0，因此,填充的比特数大于等于1而小于等于512,。,填充方式是:,第1位为1，其后各位皆为0,。,处理过程有以下几步：,附加消息的长度：用留出的,6,4比特以,little-endian,方式来表示消息被填充前的长度,。如果消息长度大于2,6,4,，则以2,6,4,为模数取模。,消息的长度为,512的倍数,（设为,L,倍）,消息分,Y,0,，Y,1,，,，Y,L-1,每一分组为,1,6,个32比特长的字,消息中的,总字数为,N=L16,消息,按,字,表示,为,M0,N-1。,Little-endian,将,最低有效字节,存于,低地址字节,。,相反的存储方式称为,big-endian,方式。,对,MD,缓冲区初始化：,算法使用128比特长的缓冲区存储中间结果和最终杂凑值。,缓冲区表示为,4个32比特长的寄存器,(A，B，C，D),，,每个寄存器都以,little endian,方式存储数据。,其初值取为（以存储方式）,A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210,实际上为,6,7452301，,EFCDAB89，98BADCFE，10325476。,以分组为单位对消息进行处理：,每一分组,Y,q,(q=0,L-1),都经一压缩函数,H,MD5,处理。,H,MD5,是算法的核心，其中又有4轮处理过程，如图所示。,输出：,消息的,L,个分组都被处理完后，最后一个,H,MD5,的输出即为产生的消息摘要。,MD5,的分组处理框图,CV,0,=IV;,CV,q+1,=CV,q,+RF,I,Y,q,RF,H,Y,q,RF,G,Yq,RF,F,Y,q,CV,q,MD=CV,L,处理过程总结如下：,CV,0,=IV;,CV,q+1,=CV,q,+RF,I,Y,q,RF,H,Y,q,RF,G,Yq,RF,F,Y,q,CV,q,MD=CV,L,IV,:,缓冲区,ABCD,的初值,Y,q,:,消息的第,q,个512比特长的分组,L,:,消息经过处理后的分组数,CV,q,:,消息的第,q,个分组时输入的链接变量,RF,x,:,使用基本逻辑函数,x,的轮函数,+,:,对应字的模2,32,加法,MD,:,最终的杂凑值。,5,.3.2,MD5,的压缩函数,压缩函数,H,MD5,中有4轮处理过程，每轮又对缓冲区,ABCD,进行1,6,步迭代运算，每一步的运算形式:,压缩函数中的一步迭代示意图,ab+CLSs(a+g(b,c,d)+Xk+Ti),a、b、c、d,:,缓冲区的4个字，运算后再右循环一个字，即得这一步迭代的输出,g,:,基本逻辑函数,F、G、H、I,之一,CLSs,:左循环移,s,位，,s,的取值由表,5,.2给出,。,Ti,:表,T,中的第,i,个字，+为模2,32,加法。,Xk=Mq16+k,:,消息第,q,个分组中的第,k,个字（,k=1,16）。,4,轮处理过程中，每轮以不同的次序使用1,6,个字,第1轮,以字的初始次序使用。,第2轮到第4轮,分别对字的次序,i,做置换后得到一个新次序，然后以新次序使用1,6,个字。,3个置换分别为:,2,(i)=(1+5i)mod 16,3,(i)=(5+3i)mod 16,4,(i)=7i mod 16,4轮处理过程分别使用,不同的基本逻辑函数,F、G、H、I,，,输入,为3个32比特的字,输出,是一个32比特的字,运算,为逐比特的逻辑运算，分别是逻辑与、逻辑或、逻辑非和异或运算。,轮数,基本逻辑函数,g,(,b,c,d,),1,2,3,4,F,(,b,c,d,),G,(,b,c,d,),H,(,b,c,d,),I,(,b,c,d,),CV0=IV=n比特长的初值；,将 提交给A请求签字,Kt：加法常量,其中镶嵌的hash函数可易于替换为更快和更安全的hash函数,考虑到MAC所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数C，但不知道密钥K：,L:消息经过处理后的分组数,第2轮 已知M2、MAC2，其中MAC2=CK(M2)。,输出：消息的L个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要。,Ti:表T中的第i个字，+为模232加法。,1 消息认证码的定义及使用方式,先说明两点，然后给出MAC函数应满足的要求。,函数的输入可以是任意长。,+:对应字的模232加法,CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVq,例如，密钥长为80比特，MAC长为32比特，则第1轮将产生大约248个可能密钥，第2轮将产生216个可能的密钥，第3轮即可找出正确的密钥。,CLSs：左循环移s位,以简单方式使用和处理密钥,MD5,的安全性,安全杂凑算法(,S,ecure,H,ash,A,lgorithm,SHA,),由美国,NIST,设计，于1993年作为联邦信息处理标准公布。,SHA,是基于,MD4,的算法，其结构与,MD4,非常类似。,5,.4 安全杂凑算法,算法的输入：,小于2,6,4,比特长的任意消息，分为512比特长的分组。,算法的输出：,1,6,0,比特长的消息摘要。,算法的框图与,MD5,一样，但杂凑值的长度和链接变量的长度为1,6,0比特。,5,.4.1 算法描述,1,6,0,bit,摘要,K,K,2,64,bit,1,6,0,SHA,SHA,SHA,SHA,1,6,0,1,6,0,1,6,0,算法的处理过程有以下几步：,对消息填充:,与,MD5,的步骤完全相同。,附加消息的长度:,与,MD5,的步骤类似，不同以,big-endian,方式表示填充前消息的长度。,对,MD,缓冲区初始化:,使用1,6,0比特长的缓冲区存储中间结果和最终杂凑值。,缓冲区可表示为,5个32比特长,的寄存器(,A,B,C,D,E)，,每个寄存器都以,big-endian,方式存储数据。,初始值分别为,A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0,。,以分组为单位对消息进行处理：,每一分组,Y,q,都经一压缩函数处理，压缩函数由4轮处理过程（如图,5,.8所示）构成，每一轮又由20步迭代组成。,5,.8,SHA,的分组处理框图,第4轮的输出（即第80步迭代的输出）再与第1轮的输入,CV,q,相加，以产生,CV,q+1,，,其中加法是缓冲区5个字中的每一个字与,CV,q,中相应的字模2,32,相加。,输出消息的,L,个分组都被处理完后，最后一个分组的输出即为1,6,0比特的消息摘要。,步骤到步骤的处理过程可总结如下：,CV,0,=IV;,CV,q+1,=SUM,32,(CV,q,ABCDE,q,);,MD=CV,L,IV,：,缓冲区,ABCDE,的初值。,ABCDE,q,：,第,q,个消息分组经最后一轮处理过程处 理后的输出,L：,是消息(包括填充位和长度字段)的分组数,SUM,32,：,是对应字的模2,32,加法,MD,：,最终的摘要值。,SHA,的压缩函数由4轮处理过程组成，每轮处理过程20步迭代运算组成，每一步迭代运算的形式为,A，B，C，D，E,：,缓冲区的5个字,t：,迭代的步数（0,t79）,f,t,(B,C,D)：,第,t,步迭代使用的基本逻辑函数,CLSs,：,左循环移,s,位,W,t,：,由当前512比特长的分组导出的一个32比特长的字,K,t,：,加法常量,+：,模2,32,加法。,5,.4.2,SHA,的压缩函数,一步迭代示意图,基本逻辑函数,的输入为3个32比特的字，输出是一个32比特的字。表中,分别是与、或、非、异或4个逻辑运算。,定义,函数名,迭代的步数,下面说明如何由当前的输入分组（512比特长）导出,W,0,W,1,W,15，,W,16,W,17,W,79,）,图,5,.10,SHA,分组处理所需的80个字的产生过程,由于,SHA,与,MD5,都是由,MD4,演化而来，所以两个算法极为相似。,1.抗穷搜索攻击的强度,由于,SHA,和,MD5,的消息摘要长度分别为1,6,0和128，,SHA,抗击穷搜索攻击的强度高于,MD5,抗击穷搜索攻击的强度。,5,.4.3,SHA,与,MD5,的比较,2.抗击密码分析攻击的强度,由于,SHA,的设计准则未被公开，所以它抗击密码分析攻击的强度较难判断，似乎高于,MD5,的强度。,3.速度,由于两个算法的主要运算都是模2,32,加法，因此都易于在32位结构上实现。但比较起来,SHA,的迭代步数(80步)多于,MD5,的迭代步数（,6,4步），所用的缓冲区（1,6,0比特）大于,MD5,使用的缓冲区（128比特），因此在相同硬件上实现时，,SHA,的速度要比,MD5,的速度慢。,4.简洁与紧致性,两个算法描述起来都较为简单，实现起来也较为简单，都不需要大的程序和代换表。,5.数据的存储方式,MD5,使用,little-endian,方式，,SHA,使用,big-endian,方式。两种方式相比看不出哪个更具优势，之所以使用两种不同的存储方式是因为设计者最初实现各自的算法时，使用的机器的存储方式不同。,HMAC,算法,HMAC,的设计目标,Hash,函数不使用密钥，不能直接用于,MAC,HMAC,要求,可不经修改使用现有,hash,函数,其中镶嵌的,hash,函数可易于替换为更快和更安全的,hash,函数,保持镶嵌的,hash,函数的最初性能，不因适用于,HAMC,而使其性能降低,以简单方式使用和处理密钥,在对镶嵌的,hash,函数合理假设的基础上，易于分析,HMAC,用于认证时的密码强度,谢谢观看,谢谢观看,