哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　1、1,散列函数,现代密码学第7章,2,本章主要内容,1、消息认证码 2、散列函数 3、MD5杂凑算法 4、安全杂凑算法 5、HMAC算法 习题,3,曾介绍过信息安全所面临的基本攻击类型，包括被动攻击（获取消息的内容、业务流分析）和主动攻击（假冒、重放、消息的篡改、业务拒绝）。抗击被动攻击的方法是前面已介绍过的加密，本章介绍的消息认证则是用来抗击主动攻击的。 消息认证是一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未重排、重放、延迟）。,攻击的类型,4,除此之外，在考虑信息安全时还需考虑业务的不可否认性，即防

　　2、止通信双方中的某一方对所传输消息的否认。实现消息的不可否认性可通过数字签字，数字签字也是一种认证技术，它也可用于抗击主动攻击。,攻击的类型,5,攻击的类型,攻击,主动攻击,被动攻击,获取消息的内容,业务流分析,假冒 重放 篡改,6,用来验证消息的真实性。 用来验证消息的完整性。 用来验证消息的顺序性和时间性。 用来验证消息的不可否认性。 认证是一个过程，消息认证机制需要有产生认证符的基本功能。认证符用来判断消息的真实性。认证符的产生有消息认证码（MAC)和散列函数(hash)两大类。,认证的功能,7,消息认证包括: 消息完整性 身份识别 不可否认性,消息认证的含义,8,消息认证码是指消息被一密

　　3、钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密码校验和。此时需要通信双方A和B共享一密钥K。设A欲发送给B的消息是M，A首先计算MAC=CK(M)，其中CK()是密钥控制的公开函数，然后向B发送MMAC，B收到后做与A相同的计算，求得一新MAC，并与收到的MAC做比较，如图1（a）所示。,1.消息认证码,1.1 消息认证码的定义及使用方式,9,如果仅收发双方知道K，且B计算得到的MAC与接收到的MAC一致，则这一系统就实现了以下功能： 接收方相信发送方发来的消息未被篡改，这是因为攻击者不知道密钥，所以不能够在篡改消息后相应地篡改MAC，而如果仅篡改消息，则接收方计算的新M

　　4、AC将与收到的MAC不同。 接收方相信发送方不是冒充的，这是因为除收发双方外再无其他人知道密钥，因此其他人不可能对自己发送的消息计算出正确的MAC。,消息认证码的定义及使用方式,10,MAC函数与加密算法类似，不同之处为MAC函数不必是可逆的，因此与加密算法相比更不易被攻破。 上述过程中，由于消息本身在发送过程中是明文形式，所以这一过程只提供认证性而未提供保密性。为提供保密性可在MAC函数以后(如图1(b)或以前(如图1(c)进行一次加密，而且加密密钥也需被收发双方共享。在图1(b)中，M与MAC链接后再被整体加密，在图1(c)中，M先被加密再与MAC链接后发送。通常希望直接对明文进行认证，因

　　5、此图1(b)所示的使用方式更为常用。,消息认证码的定义及使用方式,11,message authentication code (MAC) 签名的电子等价形式 与消息同时发送 通过一些算法, 依赖于消息及双方共享的秘密 消息可以是不任意长 MAC 可以是任意长,但常选固定长度 这需要hash function “压缩”消息成固定长度,1.消息认证码,12,MAC的基本使用方式,13,消息认证过程,14,利用对称密码进行认证,利用对称密码加密的消息可以作为认证内容 因为只有密钥的拥有者才可以生成 (要求消息有一定的冗余度) 但不能解决消息的不可否认性 （无法证明谁生成的消息）,15,使用加密算法

　　6、（单钥算法或公钥算法）加密消息时，其安全性一般取决于密钥的长度。如果加密算法没有弱点，则敌手只能使用穷搜索攻击以测试所有可能的密钥。如果密钥长为k比特，则穷搜索攻击平均将进行2k-1个测试。特别地，对惟密文攻击来说，敌手如果知道密文C，则将对所有可能的密钥值Ki执行解密运算Pi=DKi(C)，直到得到有意义的明文。,1.2 产生MAC的函数应满足的要求,16,对MAC来说，由于产生MAC的函数一般都为多到一映射，如果产生n比特长的MAC，则函数的取值范围即为2n个可能的MAC，函数输入的可能的消息个数N2n，而且如果函数所用的密钥为k比特，则可能的密钥个数为2k。 如果系统不考虑保密性，即敌手

　　7、能获取明文消息和相应的MAC，那么在这种情况下要考虑敌手使用穷搜索攻击来获取产生MAC的函数所使用的密钥。,1.2 产生MAC的函数应满足的要求,17,假定kn，且敌手已得到M1和MAC1，其中MAC1=CK1（M1），敌手对所有可能的密钥值Ki求MACi=CKi(M1)，直到找到某个Ki使得MACi=MAC1。由于不同的密钥个数为2k，因此将产生2k个MAC，但其中仅有2n个不同，由于2k2n，所以有很多密钥（平均有2k/2n=2k-n个）都可产生出正确的MAC1，而敌手无法知道进行通信的两个用户用的是哪一个密钥，还必须按以下方式重复上述攻击：,1.2 产生MAC的函数应满足的要求,18,第

　　8、1轮 已知M1、MAC1，其中MAC1=CK(M1)。对所有2k个可能的密钥计算MACi=CKi(M1)，得2k-n个可能的密钥。 第2轮已知M2、MAC2，其中MAC2=CK(M2)。对上一轮得到的2k-n个可能的密钥计算MACi=CKi(M2)，得2k-2n个可能的密钥。 如此下去，如果k=n，则上述攻击方式平均需要轮。例如，密钥长为80比特，MAC长为32比特，则第1轮将产生大约248个可能密钥，第2轮将产生216个可能的密钥，第3轮即可找出正确的密钥。,1.2 产生MAC的函数应满足的要求,19,如果密钥长度小于MAC的长度，则第1轮就有可能找出正确的密钥，也有可能找出多个可能的密钥，

　　9、如果是后者，则仍需执行第2轮搜索。 所以对消息认证码的穷搜索攻击比对使用相同长度密钥的加密算法的穷搜索攻击的代价还要大。然而有些攻击法却不需要寻找产生MAC所使用的密钥。,1.2 产生MAC的函数应满足的要求,20,例如，设M=(X1X2Xm)是由64比特长的分组Xi(i=1,m)链接得到的，其消息认证码由以下方式得到： 其中表示异或运算，加密算法是电码本模式的DES。,1.2 产生MAC的函数应满足的要求,21,因此，密钥长为56比特，MAC长为64比特，如果敌手得到MCK(M)，那么敌手使用穷搜索攻击寻找K将需做256次加密。然而敌手还可用以下方式攻击系统： 将X1到Xm-1分别用自己选取

　　10、的Y1到Ym-1替换，求出Ym=Y1Y2Ym-1(M)，并用Ym替换Xm。因此敌手可成功伪造一新消息M=Y1Ym，且M的MAC与原消息M的MAC相同。,1.2 产生MAC的函数应满足的要求,22,考虑到MAC所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数C，但不知道密钥K： 如果敌手得到M和CK(M)，则构造一满足CK(M)=CK(M)的新消息M在计算上是不可行的。 CK(M)在以下意义下是均匀分布的： 随机选取两个消息M、M，PrCK(M)=CK(M)=2-n，其中n为MAC的长。 若M是M的某个变换，即M=f(M)，例如f为插入一个或多个比特，那么PrCK(M)=CK(M

　　11、) = 2-n。,1.2 产生MAC的函数应满足的要求,23,第1个要求是针对上例中的攻击类型的，此要求是说敌手不需要找出密钥K而伪造一个与截获的MAC相匹配的新消息在计算上是不可行的。 第2个要求是说敌手如果截获一个MAC，则伪造一个相匹配的消息的概率为最小。 最后一个要求是说函数C不应在消息的某个部分或某些比特弱于其他部分或其他比特，否则敌手获得M和MAC后就有可能修改M中弱的部分，从而伪造出一个与原MAC相匹配的新消息。,1.2 产生MAC的函数应满足的要求,24,数据认证算法是最为广泛使用的消息认证码中的一个，已作为FIPS Publication（FIPS PUB 113）并被ANS

　　12、I作为X9.17标准。 算法基于CBC模式的DES算法，其初始向量取为零向量。需被认证的数据（消息、记录、文件或程序）被分为64比特长的分组D1，D2，DN，其中最后一个分组不够64比特的线，然后按以下过程计算数据认证码（见图2）：,1.3 数据认证算法,25,数据认证算法,26,其中E为DES加密算法，K为密钥。 数据认证码或者取为ON或者取为ON的最左M个比特，其中16M64。,27,散列函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，因此提供了一种错

　　13、误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。,2.散列函数,2.1 散列函数的定义及使用方式,28,图3 表示散列函数用来提供消息认证的基本使用方式，共有以下6种（见142页图3）： 消息与杂凑码链接后用单钥加密算法加密。由于所用密钥仅为收发双方A、B共享，因此可保证消息的确来自A并且未被篡改。同时还由于消息和杂凑码都被加密，这种方式还提供了保密性，见图3(a)。,散列函数的使用方式,29, 用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性的情况下，可减少处理负担。注意这种方式和图1(a)的MAC结果完全一样，即将EKH(M)看作一个函数，函数的输入为消息M和密钥

　　14、K，输出为固定长度，见图3(b)。,散列函数的使用方式,30, 用公钥加密算法和发送方的秘密钥仅加密杂凑码。和一样，这种方式提供认证性，又由于只有发送方能产生加密的杂凑码，因此这种方式还对发送方发送的消息提供了数字签字，事实上这种方式就是数字签字，见图3(c)。 消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接后的结果用单钥加密算法加密，这种方式提供了保密性和数字签字，见图3(d)。,散列函数的使用方式,31, 使用这种方式时要求通信双方共享一个秘密值S，A计算消息M和秘密值S链接在一起的杂凑值，并将此杂凑值附加到M后发往B。因B也有S，所以可重新计算杂凑值以对消息进行认证

　　15、。由于秘密值S本身未被发送，敌手无法对截获的消息加以篡改，也无法产生假消息。这种方式仅提供认证，见图3(e)。 这种方式是在中消息与杂凑值链接以后再增加单钥加密运算，从而又可提供保密性，见图3(f)。,散列函数的使用方式,32,由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要求保密性的情况下，方式和将比其他方式更具优势。,散列函数的使用方式,33,散列函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，散列函数应满足以下条件： 函数的输入可以是任意长。 函数的输出是固定长。 已知x，求H(x)较为容易，可用硬件或软件实现。,2.2 散列函数应满足的

　　16、条件,34, 已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函数。 已知x，找出y(yx)使得H(y)=H(x)在计算上是不可行的。如果单向散列函数满足这一性质，则称其为弱单向散列函数。 找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。,2.2 散列函数应满足的条件,35,如果单向散列函数满足这一性质，则称其为强单向散列函数。 第和第个条件给出了散列函数无碰撞性的概念，如果散列函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。,2.2 散列函数应满足的条件,36,以上6个条件中，前3个是散列函数能用于消息认证的基本

　　17、要求。第4个条件（即单向性）则对使用秘密值的认证技术(见图3(e)极为重要。 假如散列函数不具有单向性，则攻击者截获M和C=H(SM)后，求C的逆SM，就可求出秘密值S。第5个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。 这一性质用于杂凑值被加密情况时(见图3(b)和图3(c)防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息M，因此能产生该消息的杂凑值H(M)。,2.2 散列函数应满足的条件,37,但由于敌手不知道用于加密杂凑值的密钥，他就不可能既伪造一个消息M，又伪造这个消息的杂凑值加密后的密文EKH(M)。 然而，如果第5个条件不成立，敌手在截获明文消

　　18、息及其加密的杂凑值后，就可按以下方式伪造消息：首先求出截获的消息的杂凑值，然后产生一个具有相同杂凑值的伪造消息，最后再将伪造的消息和截获的加密的杂凑值发往通信的接收方。 第6个条件用于抵抗生日攻击。,2.2 散列函数应满足的条件,38,1. 相关问题 已知一散列函数H有n个可能的输出，H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？ 以后为叙述方便，称对散列函数H寻找上述y的攻击为第类生日攻击。,2.3 生日攻击,39,因为H有n个可能的输出，所以输入y产生的输出H(y)等于特定输出H(x)的概率是1/n，反过来说H(y)H

　　19、(x)的概率是1-1/n。y取k个随机值而函数的k个输出中没有一个等于H(x)，其概率等于每个输出都不等于H(x)的概率之积，为1-1/nk，所以y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为1-1-1/nk。,2.3 生日攻击,40,由(1+x)k1+kx，其中x1，可得 1-1-1/nk1-1-k/n=k/n 若使上述概率等于0.5，则k=n/2。特别地，如果H的输出为m比特长，即可能的输出个数n=2m，则k=2m-1。,2.3 生日攻击,41,2. 生日悖论 生日悖论是考虑这样一个问题：在k个人中至少有两个人的生日相同的概率大于0.5时，k至少多大？,生日悖论,42

　　20、,为了回答这一问题，首先定义下述概率：设有k个整数项，每一项都在1到n之间等可能地取值，则k个整数项中至少有两个取值相同的概率为P(n, k)。 因而生日悖论就是求使得P(365,k)0.5的最小k，为此首先考虑k个数据项中任意两个取值都不同的概率，记为Q(365, k)。如果k365，则不可能使得任意两个数据都不相同，因此假定k365。k个数据项中任意两个都不相同的所有取值方式数为,生日悖论,43,即第1个数据项可从365个中任取一个，第2个数据项可在剩余的364个中任取一个，依次类推，最后一个数据项可从365-k+1个值中任取一个。如果去掉任意两个都不相同这一限制条件，可得k个数据项中所有

　　21、取值方式数为365k。所以可得,生日悖论,44,当k=23时，P(365,23)=0.5073，即上述问题只需23人，人数如此之少。若k取100，则P(365,100)=0.9999997，即获得如此大的概率。之所以称这一问题是悖论是因为当人数k给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。 这是因为在k个人中考虑的是任意两个人的生日是否相同，在23个人中可能的情况数为C223=253。,生日悖论,45,将生日悖论推广为下述问题：已知一个在1到n之间均匀分布的整数型随机变量，若该变量的k个取值中至少有两个取值相同的概率大于0.5，则k至少多大？ 与上类似， ， 令P(n, k)0

　　22、.5，可得 。 若取n=365，则 。,生日悖论,46,3. 生日攻击 生日攻击是基于下述结论：设散列函数H有2m个可能的输出（即输出长m比特），如果H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则 。 称寻找函数H的具有相同输出的两个任意输入的攻击方式为第类生日攻击。,生日攻击,47,第类生日攻击可按以下方式进行： 设用户将用图3(c)所示的方式发送消息，即A用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往接收者。 敌手对A发送的消息M产生出2m/2个变形的消息，每个变形的消息本质上的含义与原消息相同，同时敌手还准备一个假冒的消息M，并对假冒的消息

　　23、产生出2m/2个变形的消息。,生日攻击,48, 敌手在产生的两个消息集合中，找出杂凑值相同的一对消息, ，由上述讨论可知敌手成功的概率大于0.5。如果不成功，则重新产生一个假冒的消息，并产生2m/2个变形，直到找到杂凑值相同的一对消息为止。 敌手将 提交给A请求签字，由于 与 的杂凑值相同，所以可将A对 的签字当作对 的签字，将此签字连同 一起发给意欲的接收者。,生日攻击,49,上述攻击中如果杂凑值的长为64比特，则敌手攻击成功所需的时间复杂度为O(232)。 将一个消息变形为具有相同含义的另一消息的方法有很多，例如对文件，敌手可在文件的单词之间插入很多“space-space-backspa

　　24、ce”字符对，然后将其中的某些字符对替换为“space-backspace-space ”就得到一个变形的消息。,生日攻击,50,目前使用的大多数散列函数如MD5、SHA，其结构都是迭代型的，如图4所示。其中函数的输入M被分为L个分组Y0,Y1,YL-1，每一个分组的长度为b比特，最后一个分组的长度不够的话，需对其做填充。 最后一个分组中还包括整个函数输入的长度值，这样一来，将使得敌手的攻击更为困难，即敌手若想成功地产生假冒的消息，就必须保证假冒消息的杂凑值与原消息的杂凑值相同，而且假冒消息的长度也要与原消息的长度相等。,2.4 迭代型散列函数的一般结构,51,迭代型散列函数的一般结构,52,

　　25、IV = 初始值 CV = 链接值 Yi = 第i 个输入数据块 f = 压缩算法 n = 散列码的长度 b = 输入块的长度,安全杂凑算法的一般结构,CV0=IV = initial n-bit value CVi=f(CVi-1, Yi-1) (1 i L) H(M) = CVL,53,算法中重复使用一压缩函数f（注意，有些书将散列函数也称为压缩函数，在此用压缩函数表示散列函数中的一个特定部分），f 的输入有两项，一项是上一轮（第i-1轮）输出的n比特值CVi-1，称为链接变量，另一项是算法在本轮（第i轮）的b比特输入分组Yi。f 的输出为n比特值CVi，CVi又作为下一轮的输入。,迭代型

　　26、散列函数的一般结构,54,算法开始时还需对链接变量指定一个初值IV，最后一轮输出的链接变量CVL即为最终产生的杂凑值。 通常有bn，因此称函数f为压缩函数。算法可表达如下： CV0=IV=n比特长的初值； CVi=f(CVi-1,Yi-1)；1iL； H(M)=CVL,迭代型散列函数的一般结构,55,算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f 的内部结构，由于f 和分组密码一样是由若干轮处理过程组成，所以对f 的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f 的碰撞。由于f 是压缩函数，其碰撞是不可避免的，因此在设计f 时就应保证找出其碰撞在计算上是

　　27、不可行的。 下面介绍几个重要的迭代型散列函数。,迭代型散列函数的一般结构,56,Hash Functions,把任意长的消息“压缩”成固定长的消息的算法 数字签名时，常被使用 通常，HASH 函数是公开的 输出长度应足够大，防止生日攻击 64-bits 认为太小 通常 128-512bits,57,Hash 函数设计原理,H能用于任何大小的数据分组; H产生定长输出; 对任意给定的x, H(x)要相对易于计算,使得软硬件实现都实际可行; 对任意给定的码h, 寻求x使得H(x)=h在计算上是不可行的(单向性); 任意给定分组x, 寻求不等于x的y, 使得H(y)= H(x)在计算上不可行(弱抗攻

　　28、击性); 寻求对任何的(x,y)对使得H(x)=H(y)在计算上不可行(强抗攻击性);,58,生日攻击(基于生日悖论) 在k个人中,找一个与某人生日相同的人的 概率超过0.5时,只需k183; 而在此人群中, 至少有两个人生日相同的概率超过0.5,只需 k23.,Hash 函数设计原理,59,MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC 1320，1321）称为MD5。,3. MD5杂凑算法,60,MD5算法采用图4描述的迭代型散列函数的一般结构，算法的框图如图5所示。算法的输入为任意长的消息（图中为K比特），分

　　29、为512比特长的分组，输出为128比特的消息摘要。,3.1 算法描述,61,MD5的算法框图,62,128-bit 摘要,MD5产生报文摘要的过程,63,处理过程有以下几步： 对消息填充对消息填充，使得其比特长在模512下为448，即填充后消息的长度为512的某一倍数减64，留出的64比特备第2步使用。 步骤是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为448比特，则需填充512比特，使其长度变为960，因此填充的比特数大于等于1而小于等于512。 填充方式是固定的，即第1位为1，其后各位皆为0。,MD5算法描述,64, 附加消息的长度用步骤留出的64比特以little-endia

　　30、n方式来表示消息被填充前的长度。如果消息长度大于264，则以264为模数取模。 Little-endian方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字节（或位）。 相反的存储方式称为big-endian方式。,MD5算法描述,65,前两步执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y0，Y1，YL-1，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为M0,N-1。,MD5算法描述,66, 对MD缓冲区初始化算法使用128比特长

　　31、的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器（A，B，C，D），每个寄存器都以littleendian方式存储数据，其初值取为（以存储方式）A=01234567，B=89ABCDEF， C=FEDCBA98，D=76543210， 实际上为67452301，EFCDAB89， 98BADCFE，10325476。,MD5算法描述,67, ：处理消息块（512位 = 16个32位字）。一个压缩函数是本算法的核心(HMD5)。它包括4轮处理。四轮处理具有相似的结构,但每次使用不同的基本逻辑函数，记为F,G,H,I。每一轮以当前的512位数据块(Yq)和128位缓冲值AB

　　34、能函数。 MD = 最终消息摘要结果 SUM32=分别按32位字计算的模232加法结果。,MD5算法描述,72,MD5的分组处理框图,73,+ is mod 232,单个 512-bit 分组的 MD5 处理过程,74,HMD5的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。每轮处理过程还需加上常数表T中四分之一个元素，分别为T116, T1732, T3348, T4964。表T有64个元素，见表6.1，第i个元素Ti为232abs(sin(i)的整数部分，其

　　35、中sin为正弦函数，i以弧度为单位。,MD5算法描述,75,由于abs(sin(i)大于0小于1，所以Ti可由32比特的字表示。第4轮的输出再与第1轮的输入CVq相加，相加时将CVq看作4个32比特的字，每个字与第4轮输出的对应的字按模232相加，相加的结果即为压缩函数HMD5的输出。（见151页表6.1）,MD5算法描述,76,步骤到步骤的处理过程可总结如下： CV0=IV; CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVq MD=CVL 其中IV是步骤所取的缓冲区ABCD的初值，Yq是消息的第q个512比特长的分组，L是消息经过步骤和步骤处理后的分组数，CVq为处

　　36、理消息的第q个分组时输入的链接变量（即前一个压缩函数的输出），RFx为使用基本逻辑函数x的轮函数，+为对应字的模232加法，MD为最终的杂凑值。,MD5算法描述,77,压缩函数HMD5中有4轮处理过程，每轮又对缓冲区ABCD进行16步迭代运算，每一步的运算形式为（见图7） ab+CLSs(a+g(b,c,d)+Xk+TI) 其中a、b、c、d为缓冲区的4个字，运算完成后再右循环一个字，即得这一步迭代的输出。g是基本逻辑函数F、G 、H、I之一。CLSs是左循环移s位，s的取值由表6.2给出。（见152页表6.2）,3.2 MD5的压缩函数,78,2i = (1+5i) mod 16 3i =

　　38、(1+5i) mod 16 3(i)=(5+3i) mod 16 4(i)=7i mod 16,压缩函数中的一步迭代,81,4轮处理过程分别使用不同的基本逻辑函数F、G、H、I，每个逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特的逻辑运算，即输出的第n个比特是3个输入的第n个比特的函数，函数的定义由表6.3给出，其中，-，分别是逻辑与、逻辑或、逻辑非和异或运算，表6.4是四个函数的线年10月作为RFC1320发表) by Ron Rivest at MIT,MD4的设计目标 安

　　39、全性： 速度：32位体系结构下计算速度快. 简明与紧凑：易于编程. 有利的小数在前的结构(Intel 80 xxx, Pentium ) MD4与MD5的区别 MD4用3轮,每轮16 步,MD5用4轮,每轮16步. MD4中第一轮没有常量加；MD5中64步每一步用了一个不同的常量 Ti； MD5用了四个基本逻辑函数，每轮一个；MD4用了三个. MD5每轮加上前一步的结果；MD4没有.,83,MD5有这样一个性质，即杂凑码中的每一个比特是所有输入比特的函数，因此获得了很好的混淆效果，从而使得不可能随机选择两个具有相同杂凑值的消息。 Rivest猜想作为128比特长的杂凑值来说，MD5的强度达到了

　　40、最大，比如说找出具有相同杂凑值的两个消息需执行O(264)次运算，而寻找具有给定杂凑值的一个消息需要执行O(2128)次运算。,3.3 MD5的安全性,84,目前对MD5的攻击已取得以下结果： 对单轮MD5使用差分密码分析，可在合理的时间内找出具有相同杂凑值的两个消息。但这种攻击还未能成功地推广到4轮MD5。 可找出一个消息分组和两个相关的链接变量（即缓冲区变量ABCD），使得算法产生出相同的输出。目前这种攻击还未能成功地推广到整个算法。,3.3 MD5的安全性,85, 对单个512比特长的消息分组已成功地找出了碰撞，即可找出另一个消息分组，使得算法对两个消息分组的128比特长的输出相同。目前

　　41、这种攻击还未成功推广到在有初值IV时对整个消息运行该算法。,3.3 MD5的安全性,86,因此从密码分析的角度来看，MD5被认为是易受攻击的。 而从穷搜索的角度来看，第类生日攻击需进行O(264)次运算，因此认为MD5易受第类生日攻击的威胁。 所以必须寻找新的杂凑算法，以使其产生的杂凑值更长，且抵抗已知密码分析攻击的能力更强。下面要介绍的SHA即为这样的一个算法。,3.3 MD5的安全性,87,安全杂凑算法(secure hash algorithm, SHA)由美国NIST设计，于1993年作为联邦信息处理标准（FIPS PUB 180）公布。SHA是基于MD4的算法，其结构与MD4非常类似

　　42、。,4. 安全杂凑算法(SHA),88,算法的输入为小于264比特长的任意消息，分为512比特长的分组，输出为160比特长的消息摘要。算法的框图与图5一样，但杂凑值的长度和链接变量的长度为160比特。,4.1 算法描述,89,算法的处理过程有以下几步： 对消息填充与MD5的步骤完全相同。 附加消息的长度与MD5的步骤类似，不同之处在于以big-endian方式表示填充前消息的长度。即步骤留出的64比特当作64比特长的无符号整数。,SHA算法描述,90, 对MD缓冲区初始化算法使用160比特长的缓冲区存储中间结果和最终杂凑值，缓冲区可表示为5个32比特长的寄存器(A, B, C, D, E)，每

　　43、个寄存器都以big-endian方式存储数据，其初始值分别为 A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。,SHA算法描述,91, 以分组为单位对消息进行处理每一分组Yq都经一压缩函数处理，压缩函数由4轮处理过程（如图8所示）构成，每一轮又由20步迭代组成。4轮处理过程结构一样，但所用的基本逻辑函数不同，分别表示为f1,f2,f3,f4。,SHA算法描述,92,每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A,B,C,D,E，输出仍放在缓冲区以替代A,B,C,D,E的旧值，每轮处理过程还需加上一个加法常量Kt，其中0t79表

　　44、示迭代的步数。80个常量中实际上只有4个不同取值，如表6.5所示，其中 为x的整数部分。（见155页表6.5）,SHA算法描述,93,SHA的分组处理框图,94,第4轮的输出（即第80步迭代的输出）再与第1轮的输入CVq相加，以产生CVq+1，其中加法是缓冲区5个字中的每一个字与CVq中相应的字模232相加。 输出消息的L个分组都被处理完后，最后一个分组的输出即为160比特的消息摘要。,SHA算法描述,95,步骤到步骤的处理过程可总结如下： CV0=IV; CVq+1=SUM32(CVq,ABCDEq); MD=CVL 其中IV是步骤定义的缓冲区ABCDE的初值，ABCDEq是第q个消息分组经

　　45、最后一轮处理过程处理后的输出，L是消息（包括填充位和长度字段）的分组数，SUM32是对应字的模232加法，MD为最终的摘要值。,SHA算法描述,96,如上所述，SHA的压缩函数由4轮处理过程组成，每轮处理过程又由对缓冲区ABCDE的20步迭代运算组成，每一步迭代运算的形式为（见图9） 其中A，B，C，D，E为缓冲区的5个字，t是迭代的步数（0t79），ft(B,C,D)是第t步迭代使用的基本逻辑函数，CLSs为左循环移s位，Wt是由当前512比特长的分组导出的一个32比特长的字（导出方式见下面），Kt是加法常量，+是模232加法。,4.2 SHA的压缩函数,97,SHA的压缩函数中一步迭代示意

　　46、图,98,基本逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特逻辑运算，即输出的第n个比特是3个输入的相应比特的函数。函数的定义如表6.6。表中, ,分别是与、或、非、异或4个逻辑运算，函数的线）,SHA的压缩函数中一步迭代,99,下面说明如何由当前的输入分组（512比特长）导出Wt（32比特长）。前16个值（即W0,W1,W15）直接取为输入分组的16个相应的字，其余值（即W16,W17,W79）取为 见图10。与MD5比较，MD5直接用一个消息分组的16个字作为每步迭代的输入，而SHA则将输入分组的16个

　　47、字扩展成80个字以供压缩函数使用，从而使得寻找具有相同压缩值的不同的消息分组更为困难。,SHA的压缩函数中一步迭代,100,SHA分组处理所需的80个字的产生过程,101,由于SHA与MD5都是由MD4演化而来，所以两个算法极为相似。 1. 抗穷搜索攻击的强度 由于SHA和MD5的消息摘要长度分别为160和128，所以用穷搜索攻击寻找具有给定消息摘要的消息分别需做O(2160)和O(2128)次运算，而用穷搜索攻击找出具有相同消息摘要的两个不同消息分别需做O(280)和O(264)次运算。因此SHA抗击穷搜索攻击的强度高于MD5抗击穷搜索攻击的强度。,4.3 SHA与MD5的比较,102,2.

　　48、 抗击密码分析攻击的强度 由于SHA的设计准则未被公开，所以它抗击密码分析攻击的强度较难判断，似乎高于MD5的强度。,SHA与MD5的比较,103,3. 速度 由于两个算法的主要运算都是模232加法，因此都易于在32位结构上实现。但比较起来,SHA的迭代步数(80步)多于MD5的迭代步数（64步），所用的缓冲区（160比特）大于MD5使用的缓冲区（128比特），因此在相同硬件上实现时，SHA的速度要比MD5的速度慢。,SHA与MD5的比较,104,4. 简洁与紧致性 两个算法描述起来都较为简单，实现起来也较为简单，都不需要大的程序和代换表。 5. 数据的存储方式 MD5使用little-end

　　49、ian方式，SHA使用big-endian方式。两种方式相比看不出哪个更具优势，之所以使用两种不同的存储方式是因为设计者最初实现各自的算法时，使用的机器的存储方式不同。,SHA与MD5的比较,105,以前曾介绍过一个MAC的例子数据认证算法，该算法反映了传统上构造MAC最为普遍使用的方法，即基于分组密码的构造方法。但近年来研究构造MAC的兴趣已转移到基于密码散列函数的构造方法，这是因为： 密码散列函数(如MD5、SHA)的软件实现快于分组密码(如DES)的软件实现；密码散列函数的库代码来源广泛； 密码散列函数没有出口限制，而分组密码即使用于MAC也有出口限制。,5. HMAC算法,106,散列

　　50、函数并不是为用于MAC而设计的，由于散列函数不使用密钥，因此不能直接用于MAC。 目前已提出了很多将散列函数用于构造MAC的方法，其中HMAC就是其中之一，已作为RFC2104被公布，并在IPSec和其他网络协议(如SSL)中得以应用。,107,RFC2104列举了HMAC的以下设计目标： 可不经修改而使用现有的散列函数，特别是那些易于软件实现的、源代码可方便获取且免费使用的散列函数。 其中镶嵌的散列函数可易于替换为更快或更安全的散列函数。,5.1 HMAC的设计目标,108, 保持镶嵌的散列函数的最初性能，不因用于HMAC而使其性能降低。 以简单方式使用和处理密钥。 在对镶嵌的散列函数合理假

　　51、设的基础上，易于分析HMAC用于认证时的密码强度。,HMAC的设计目标,109,其中前两个目标是HMAC被公众普遍接受的主要原因，这两个目标是将散列函数当作一个黑盒使用，这种方式有两个优点: 第一，散列函数的实现可作为实现HMAC的一个模块，这样一来，HMAC代码中很大一块就可事先准备好，无需修改就可使用； 第二，如果HMAC要求使用更快或更安全的散列函数，则只需用新模块代替旧模块，例如用实现SHA的模块代替MD5的模块。,HMAC的设计目标,110,最后一条设计目标则是HMAC优于其他基于散列函数的MAC的一个主要方面，HMAC在其镶嵌的散列函数具有合理密码强度的假设下，可证明是安全的。,H

　　52、MAC的设计目标,111,图11是HMAC算法的运行框图，其中H为嵌入的散列函数(如MD5、SHA)，M为HMAC的输入消息(包括散列函数所要求的填充位)，Yi(0iL-1)是M的第i个分组，L是M的分组数，b是一个分组中的比特数，n为由嵌入的散列函数所产生的杂凑值的长度，K为密钥，如果密钥长度大于b，则将密钥输入到散列函数中产生一个n比特长的密钥，K+是左边经填充0后的K，K+的长度为b比特，ipad为b/8个00110110，opad为b/8个01011010。,5.2 HMAC算法描述,112,HMAC的算法框图,113,算法的输出可如下表示:,HMAC算法描述,114,算法的运行过程可

　　53、描述如下： K的左边填充0以产生一个b比特长的K+ （例如K的长为160比特，b=512，则需填充44个零字节0 x00）。 K+与ipad 逐比特异或以产生b比特的分组Si。 将M链接到Si后。,HMAC算法描述,115, 将H作用于步骤产生的数据流。 K+与opad逐比特异或,以产生b比特长的分组S0。 将步骤得到的杂凑值链接在S0后。 将H作用于步骤产生的数据流并输出最终结果。,HMAC算法描述,116,注意，K+与ipad逐比特异或以及K+与opad逐比特异或的结果是将K中的一半比特取反，但两次取反的比特的位置不同。而Si和S0通过散列函数中压缩函数的处理，则相当于以伪随机方式从K产生

　　54、两个密钥。,HMAC算法描述,117,在实现HMAC时，可预先求出下面两个量 （见图12，虚线以左为预计算）： 其中f(cv，block)是散列函数中的压缩函数，其输入是n比特的链接变量和b比特的分组，输出是n比特的链接变量。这两个量的预先计算只在每次更改密钥时才需进行。事实上这两个预先计算的量用于作为散列函数的初值IV。,HMAC算法描述,118,HMAC的有效实现,119,基于密码散列函数构造的MAC的安全性取决于镶嵌的散列函数的安全性，而HMAC最吸引人的地方是它的设计者已经证明了算法的强度和嵌入的散列函数的强度之间的确切关系，证明了对HMAC的攻击等价于对内嵌散列函数的下述两种攻击之一

　　55、： 攻击者能够计算压缩函数的一个输出，即使IV是随机的和秘密的。 攻击者能够找出散列函数的碰撞，即使IV是随机的和秘密的。,5.3 HMAC的安全性,120,在第一种攻击中，可将压缩函数视为与散列函数等价，而散列函数的n比特长IV可视为HMAC的密钥。对这一散列函数的攻击可通过对密钥的穷搜索来进行，也可通过第类生日攻击来实施，通过对密钥的穷搜索攻击的复杂度为O（2n），通过第类生日攻击又可归结为上述第二种攻击。,HMAC的安全性,121,第二种攻击指攻击者寻找具有相同杂凑值的两个消息，因此就是第类生日攻击。对杂凑值长度为n的散列函数来说，攻击的复杂度为O(2n/2)。因此第二种攻击对MD5的攻

　　56、击复杂度为O(264)，就现在的技术来说，这种攻击是可行的。但这是否意味着MD5不适合用于HMAC？,HMAC的安全性,122,回答是否定的，原因如下：攻击者在攻击MD5时，可选择任何消息集合后脱线寻找碰撞。由于攻击者知道杂凑算法和默认的IV，因此能为自己产生的每个消息求出杂凑值。然而，在攻击HMAC时，由于攻击者不知道密钥K，从而不能脱线产生消息和认证码对。,HMAC的安全性,123,所以攻击者必须得到HMAC在同一密钥下产生的一系列消息，并对得到的消息序列进行攻击。对长128比特的杂凑值来说，需要得到用同一密钥产生的264个分组（273比特）。在1Gbit/s的链路上，需250000年，因

　　57、此MD5完全适合于HMAC，而且就速度而言，MD5要快于SHA作为内嵌散列函数的HMAC。,HMAC的安全性,124,1. 数据认证算法是由CBC模式的DES定义的，其中初始向量取为0，试说明使用CFB模式也可获得相同结果。,习题,125,2. 有很多散列函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将消息M分成分组M1,M2,MN，H0=初值，迭代关系为Hi=EMi(Hi-1)Hi-1(i=1,2,N)，杂凑值取为HN，其中E是分组加密算法。 (1) 设E为DES，我们知道如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即如果Y=DESK(X

　　58、)，那么Y=DESK(X)。利用这一结论证明在上述散列函数中可对消息进行修改但却保持杂凑值不变。 (2) 若迭代关系改为Hi=EHi-1(Mi)Mi，证明仍可对其进行上述攻击。,126,3. 考虑用公钥加密算法构造散列函数，设算法是RSA，将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。设一消息被分成两个分组B1和B2，其杂凑值为H(B1，B2)=RSA(RSA(B1)B2)。证明对任一分组C1可选C2，使得H(C1,C2)=H(B1,B2)。证明用这种攻击法，可攻击上述用公钥加密算法构造的散列函数。,习题,127,4. 在图10中，假定有80个32比

　　59、特长的字用于存储每一Wt，因此在处理消息分组前，可预先计算出这80个值。为节省存储空间，考虑用16个字的循环移位寄存器，其初值存储前16个值（即W0,W1,W15），设计一个算法计算以后的每一Wt。 5. 对SHA，计算W16,W17,W18,W19。,习题,128,6. 设a1a2a3a4是32比特长的字中的4个字节，每一ai可看作由二进制表示的0到255之间的整数，在big-endian结构中，该字表示整数a1224+a2216+a328+a4，在little-endian结构中，该字表示整数a4224+a3216+a228+a1。 (1) MD5使用little-endian结构，因消息的摘要值不应依赖于算法所用的结构，因此在MD5中为了对以big-endian结构存储的两个字X=x1x2x3x4和Y=y1y2y3y4进行模2加法运算，必须对这两个字进行调整，试说明如何调整？ (2) SHA使用big-endian结构，试说明如何对以little-endian结构存储的两个字X和Y进行模2加法运算。,129,THE END！,