消息认证和杂凑函数省公共课一等奖全国赛课获奖课件.pptx

第第第第6 6章章章章 消息认证和杂凑函数消息认证和杂凑函数消息认证和杂凑函数消息认证和杂凑函数郝艳华郝艳华郝艳华郝艳华漳州师范学院计算机科学与工程系漳州师范学院计算机科学与工程系漳州师范学院计算机科学与工程系漳州师范学院计算机科学与工程系10/10/1第1页6.1 消息认证码消息认证码6.2 杂凑函数杂凑函数6.3 MD5杂凑算法杂凑算法6.4 安全杂凑算法安全杂凑算法6.5 HMAC10/10/2第2页第第1章曾介绍过信息安全所面临基本攻击类型，章曾介绍过信息安全所面临基本攻击类型，包含被动攻击和主动攻击。抗击被动攻击方法是包含被动攻击和主动攻击。抗击被动攻击方法是前面已介绍过加密，本章介绍前面已介绍过加密，本章介绍消息认证则是用来消息认证则是用来抗击主动攻击抗击主动攻击。消息认证是一个过程，用以验证接收消息消息认证是一个过程，用以验证接收消息真实性真实性（确实是由它所声称实体发来）和（确实是由它所声称实体发来）和完整性完整性（未被（未被篡改、插入、删除），同时还用于验证消息篡改、插入、删除），同时还用于验证消息次序次序性性和和时间性时间性（未重排、重放、延迟）。（未重排、重放、延迟）。除此之外，在考虑信息安全时还需考虑业务除此之外，在考虑信息安全时还需考虑业务不可不可否定性否定性，即预防通信双方中某一方对所传输消息，即预防通信双方中某一方对所传输消息否定。实现消息不可否定性可经过数字签字，数否定。实现消息不可否定性可经过数字签字，数字签字也是一个认证技术，它也可用于抗击主动字签字也是一个认证技术，它也可用于抗击主动攻击。攻击。10/10/3第3页消息认证机制和数字签字机制都有产生认消息认证机制和数字签字机制都有产生认证符基本功效，这一基本功效又作为认证证符基本功效，这一基本功效又作为认证协议一个组成部分。协议一个组成部分。认证符是用于认证消息数值，它产生方法认证符是用于认证消息数值，它产生方法又分为又分为消息认证码消息认证码MAC（message authentication code）杂凑函数杂凑函数（hash function）10/10/4第4页6.1 消息认证码消息认证码6.1.1 消息认证码定义及使用方式消息认证码定义及使用方式 消息认证码是指消息被一密钥控制公开函消息认证码是指消息被一密钥控制公开函数作用后产生、用作认证符、固定长度数数作用后产生、用作认证符、固定长度数值值，也称为密码校验和。，也称为密码校验和。此时需要通信双方此时需要通信双方A和和B共享一密钥共享一密钥K。设。设A欲发送给欲发送给B消息是消息是M，A首先计算首先计算MAC=CK(M)，其中，其中CK()是密钥控制公是密钥控制公开函数，然后向开函数，然后向B发送发送MMAC，B收到后收到后做与做与A相同计算，求得一新相同计算，求得一新MAC，并与收，并与收到到MAC做比较做比较10/10/5第5页图图6.1 MAC基本使用方式基本使用方式10/10/6第6页假如仅收发双方知道假如仅收发双方知道K，且，且B计算得到计算得到MAC与接收到与接收到MAC一致，则这一系统一致，则这一系统就实现了以下功效：就实现了以下功效：接收方相信发送方发来消息未被篡改接收方相信发送方发来消息未被篡改，这，这是因为攻击者不知道密钥，所以不能够在是因为攻击者不知道密钥，所以不能够在篡改消息后对应地篡改篡改消息后对应地篡改MAC，而假如仅篡，而假如仅篡改消息，则接收方计算新改消息，则接收方计算新MAC将与收到将与收到MAC不一样。不一样。接收方相信发送方不是冒充接收方相信发送方不是冒充，这是因为除，这是因为除收发双方外再无其它人知道密钥，所以其收发双方外再无其它人知道密钥，所以其它人不可能对自己发送消息计算出正确它人不可能对自己发送消息计算出正确MAC。10/10/7第7页MAC函数与加密算法类似，不一样之处为函数与加密算法类似，不一样之处为MAC函数无须是可逆，所以与加密算法相函数无须是可逆，所以与加密算法相比更不易被攻破。比更不易被攻破。上述过程中，因为消息本身在发送过程中上述过程中，因为消息本身在发送过程中是明文形式，所以这一过程只提供认证性是明文形式，所以这一过程只提供认证性而未提供保密性。而未提供保密性。为提供保密性可在为提供保密性可在MAC函数以后或以前进函数以后或以前进行一次加密，而且加密密钥也需被收发双行一次加密，而且加密密钥也需被收发双方共享。方共享。10/10/8第8页10/10/9第9页6.1.2 产生产生MAC函数应满足要求函数应满足要求使用加密算法（单钥算法或公钥算法）加密使用加密算法（单钥算法或公钥算法）加密消息时，其安全性普通取决于密钥长度。消息时，其安全性普通取决于密钥长度。假如加密算法没有弱点，则敌手只能使用穷假如加密算法没有弱点，则敌手只能使用穷搜索攻击以测试全部可能密钥。假如密钥长搜索攻击以测试全部可能密钥。假如密钥长为为k比特，则穷搜索攻击平均将进行比特，则穷搜索攻击平均将进行2k-1个测个测试。尤其地，对惟密文攻击来说，敌手假如试。尤其地，对惟密文攻击来说，敌手假如知道密文知道密文C，则将对全部可能密钥值，则将对全部可能密钥值Ki执行执行解密运算解密运算Pi=DKi(C)，直到得到有意义明文。，直到得到有意义明文。10/10/10第10页对对MAC来说，因为产生来说，因为产生MAC函数普通都函数普通都为多到一映射，假如产生为多到一映射，假如产生n比专长比专长MAC，则函数取值范围即为则函数取值范围即为2n个可能个可能MAC，函，函数输入可能消息个数数输入可能消息个数N2n，而且假如函，而且假如函数所用密钥为数所用密钥为k比特，则可能密钥个数为比特，则可能密钥个数为2k。假如系统不考虑保密性，即敌手能获。假如系统不考虑保密性，即敌手能获取明文消息和对应取明文消息和对应MAC，那么在这种情，那么在这种情况下要考虑敌手使用穷搜索攻击来获取产况下要考虑敌手使用穷搜索攻击来获取产生生MAC函数所使用密钥。函数所使用密钥。10/10/11第11页假定假定kn，且敌手已得到，且敌手已得到M1和和MAC1，其中，其中MAC1=CK1（M1），敌手对全部可能密钥值），敌手对全部可能密钥值Ki求求MACi=CKi(M1)，直到找到某个，直到找到某个Ki使得使得MACi=MAC1。因为不一样密钥个数为。因为不一样密钥个数为2k，所，所以将产生以将产生2k个个MAC，但其中仅有，但其中仅有2n个不一样，个不一样，因为因为2k2n，所以有很多密钥（平都有，所以有很多密钥（平都有2k/2n=2k-n个）都可产生出正确个）都可产生出正确MAC1，而敌手，而敌手无法知道进行通信两个用户用是哪一个密钥，无法知道进行通信两个用户用是哪一个密钥，还必须按以下方式重复上述攻击：还必须按以下方式重复上述攻击：10/10/12第12页第第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轮即可找出正确轮即可找出正确密钥。密钥。10/10/13第13页假如密钥长度小于假如密钥长度小于MAC长度，则第长度，则第1轮就轮就有可能找出正确密钥，也有可能找出多个有可能找出正确密钥，也有可能找出多个可能密钥，假如是后者，则仍需执行第可能密钥，假如是后者，则仍需执行第2轮搜索。轮搜索。所以对消息认证码穷搜索攻击比对使用相所以对消息认证码穷搜索攻击比对使用相同长度密钥加密算法穷搜索攻击代价还要同长度密钥加密算法穷搜索攻击代价还要大。大。有些攻击法却不需要寻找产生有些攻击法却不需要寻找产生MAC所使所使用密钥。用密钥。10/10/14第14页比如，设比如，设比如，设比如，设M=(XM=(X1 1XX2 2XXmm)是由是由是由是由6464比专长分组比专长分组比专长分组比专长分组X Xi i(i=1,m)(i=1,m)链接得到，其消息认证码由以下方式链接得到，其消息认证码由以下方式链接得到，其消息认证码由以下方式链接得到，其消息认证码由以下方式得到：得到：得到：得到：其中其中其中其中表示异或运算，加密算法是电码本模式表示异或运算，加密算法是电码本模式表示异或运算，加密算法是电码本模式表示异或运算，加密算法是电码本模式DESDES。所以，密钥长为所以，密钥长为所以，密钥长为所以，密钥长为5656比特，比特，比特，比特，MACMAC长为长为长为长为6464比特，假如比特，假如比特，假如比特，假如敌手得到敌手得到敌手得到敌手得到MCMCKK(M)(M)，那么敌手使用穷搜索攻击寻找，那么敌手使用穷搜索攻击寻找，那么敌手使用穷搜索攻击寻找，那么敌手使用穷搜索攻击寻找KK将需做将需做将需做将需做2 25656次加密。然而敌手还可用以下方式攻击次加密。然而敌手还可用以下方式攻击次加密。然而敌手还可用以下方式攻击次加密。然而敌手还可用以下方式攻击系统：系统：系统：系统：将将将将X X1 1到到到到X Xm-1m-1分别用自己选取分别用自己选取分别用自己选取分别用自己选取Y Y1 1到到到到Y Ym-1m-1替换，替换，替换，替换，求出求出求出求出Y Ymm=Y=Y1 1Y Y2 2Y Ym-1m-1(M)(M)，并用，并用，并用，并用Y Ymm替换替换替换替换X Xmm。所以敌手可成功伪造一新消息。所以敌手可成功伪造一新消息。所以敌手可成功伪造一新消息。所以敌手可成功伪造一新消息M=YM=Y1 1Y Ymm，且，且，且，且MMACMMAC与原消息与原消息与原消息与原消息MMACMMAC相同。相同。相同。相同。10/10/15第15页考虑到考虑到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)=2-n。10/10/16第16页第第1个要求是针对上例中攻击类型，此要求个要求是针对上例中攻击类型，此要求是说敌手不需要找出密钥是说敌手不需要找出密钥K而伪造一个与而伪造一个与截获截获MAC相匹配新消息在计算上是不可行。相匹配新消息在计算上是不可行。第第2个要求是说敌手假如截获一个个要求是说敌手假如截获一个MAC，则伪造一个相匹配消息概率为最小。则伪造一个相匹配消息概率为最小。最终一个要求是说函数最终一个要求是说函数C不应在消息某个不应在消息某个部分或一些比特弱于其它部分或其它比特，部分或一些比特弱于其它部分或其它比特，不然敌手取得不然敌手取得M和和MAC后就有可能修改后就有可能修改M中弱部分，从而伪造出一个与原中弱部分，从而伪造出一个与原MAC相匹相匹配新消息。配新消息。10/10/17第17页6.1.3 数据认证算法数据认证算法数据认证算法是最为广泛使用消息认证码数据认证算法是最为广泛使用消息认证码中一个，已作为中一个，已作为FIPS Publication（FIPS PUB 113）并被）并被ANSI作为作为X9.17标准。标准。算法基于算法基于CBC模式模式DES算法，其初始向量算法，其初始向量取为零向量。需被认证数据（消息、统计、取为零向量。需被认证数据（消息、统计、文件或程序）被分为文件或程序）被分为64比专长分组比专长分组D1，D2，DN，其中最终一个分组不够，其中最终一个分组不够64比特比特话，可在其右边填充一些话，可在其右边填充一些0，然后按以下过，然后按以下过程计算数据认证码程计算数据认证码10/10/18第18页图图图图6.2 6.2 数据认证算法数据认证算法数据认证算法数据认证算法10/10/19第19页其中其中其中其中E E为为为为DESDES加密算法，加密算法，加密算法，加密算法，KK为密钥。为密钥。为密钥。为密钥。数据认证码或者取为数据认证码或者取为数据认证码或者取为数据认证码或者取为OON N或者取为或者取为或者取为或者取为OON N最左最左最左最左MM个比特，个比特，个比特，个比特，其中其中其中其中16M6416M64。10/10/20第20页6.2 杂凑函数杂凑函数6.2.1 杂凑函数定义及使用方式杂凑函数定义及使用方式杂凑函数杂凑函数H是一公开函数，用于将任意长消是一公开函数，用于将任意长消息息M映射为较短、固定长度一个值映射为较短、固定长度一个值H(M)，作为认证符，称函数值作为认证符，称函数值H(M)为杂凑值、杂为杂凑值、杂凑码或消息摘要。凑码或消息摘要。杂凑码是消息中全部比特函数，所以提供杂凑码是消息中全部比特函数，所以提供了一个了一个错误检测错误检测能力，即改变消息中任何能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改一个比特或几个比特都会使杂凑码发生改变。变。10/10/21第21页杂凑函数用来提供消息认证基本使用方式杂凑函数用来提供消息认证基本使用方式共有共有6种种1.消息与杂凑码链接后用单钥加密算法加密。消息与杂凑码链接后用单钥加密算法加密。因为所用密钥仅为收发双方因为所用密钥仅为收发双方A、B共享，所以共享，所以可确保消息确实来自可确保消息确实来自A而且未被篡改。同时而且未被篡改。同时还因为消息和杂凑码都被加密，这种方式还还因为消息和杂凑码都被加密，这种方式还提供了保密性提供了保密性2.用单钥加密算法仅对杂凑码加密。这种方式用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性情况下，可降低处理负担。用于不要求保密性情况下，可降低处理负担。注意这种方式和图注意这种方式和图6.1(a)MAC结果完全一样，结果完全一样，即将即将EKH(M)看作一个函数，函数输入为消看作一个函数，函数输入为消息息M和密钥和密钥K，输出为固定长度，输出为固定长度10/10/22第22页10/10/23第23页3.用公钥加密算法和发送方秘密钥仅加密用公钥加密算法和发送方秘密钥仅加密杂凑码。和杂凑码。和一样，这种方式提供认证一样，这种方式提供认证性，又因为只有发送方能产生加密杂凑性，又因为只有发送方能产生加密杂凑码，所以这种方式还对发送方发送消息码，所以这种方式还对发送方发送消息提供了数字签字，实际上这种方式就是提供了数字签字，实际上这种方式就是数字签字数字签字4.消息杂凑值用公钥加密算法和发送方秘消息杂凑值用公钥加密算法和发送方秘密钥加密后与消息链接，再对链接后结密钥加密后与消息链接，再对链接后结果用单钥加密算法加密，这种方式提供果用单钥加密算法加密，这种方式提供了保密性和数字签字了保密性和数字签字10/10/24第24页10/10/25第25页5.使用这种方式时要求通信双方共享一个秘密使用这种方式时要求通信双方共享一个秘密值值S，A计算消息计算消息M和秘密值和秘密值S链接在一起杂凑链接在一起杂凑值，并将此杂凑值附加到值，并将此杂凑值附加到M后发往后发往B。因。因B也也有有S，所以可重新计算杂凑值以对消息进行认，所以可重新计算杂凑值以对消息进行认证。因为秘密值证。因为秘密值S本身未被发送，敌手无法对本身未被发送，敌手无法对截获消息加以篡改，也无法产生假消息。这截获消息加以篡改，也无法产生假消息。这种方式仅提供认证种方式仅提供认证6.这种方式是在这种方式是在中消息与杂凑值链接以后再中消息与杂凑值链接以后再增加单钥加密运算，从而又可提供保密性增加单钥加密运算，从而又可提供保密性1.因为加密运算速度较慢，代价较高，而且很因为加密运算速度较慢，代价较高，而且很多加密算法还受到专利保护，所以在不要求多加密算法还受到专利保护，所以在不要求保密性情况下，方式保密性情况下，方式和和将比其它方式更将比其它方式更具优势。具优势。10/10/26第26页10/10/27第27页6.2.2 杂凑函数应满足条件杂凑函数应满足条件杂凑函数目标是为需认证数据产生一个杂凑函数目标是为需认证数据产生一个“指纹指纹”。为了能够实现对数据认证，。为了能够实现对数据认证，杂凑函数应满足以下条件：杂凑函数应满足以下条件：1.函数输入能够是任意长。函数输入能够是任意长。2.函数输出是固定长。函数输出是固定长。3.已知已知x，求，求H(x)较为轻易，可用硬件或软件较为轻易，可用硬件或软件实现。实现。4.已知已知h，求使得，求使得H(x)=hx在计算上是不可行，在计算上是不可行，这一性质称为函数单向性，称这一性质称为函数单向性，称H(x)为为单向杂单向杂凑函数凑函数。10/10/28第28页5.已知已知x，找出，找出y(yx)使得使得H(y)=H(x)在计算在计算上是不可行。假如单向杂凑函数满足这上是不可行。假如单向杂凑函数满足这一性质，则称其为一性质，则称其为弱单向杂凑函数。弱单向杂凑函数。6.找出任意两个不一样输入找出任意两个不一样输入x、y，使得，使得H(y)=H(x)在计算上是不可行。假如单向在计算上是不可行。假如单向杂凑函数满足这一性质，则称其为杂凑函数满足这一性质，则称其为强单强单向杂凑函数向杂凑函数。第第和第和第个条件给出了杂凑函数无碰个条件给出了杂凑函数无碰撞性概念，假如杂凑函数对不一样输入撞性概念，假如杂凑函数对不一样输入可产生相同输出，则称该函数可产生相同输出，则称该函数含有碰撞含有碰撞性性。10/10/29第29页以上以上6个条件中，前个条件中，前3个是杂凑函数能用于消息个是杂凑函数能用于消息认证基本要求。认证基本要求。第第4个条件（即单向性）则对使用秘密值认证个条件（即单向性）则对使用秘密值认证技术技术(见图见图6.3(e)极为主要。假如杂凑函数不极为主要。假如杂凑函数不含有单向性，则攻击者截获含有单向性，则攻击者截获M和和C=H(SM)后，后，求求C逆逆SM，就可求出秘密值，就可求出秘密值S。第第5个条件使得敌手无法在已知某个消息时，个条件使得敌手无法在已知某个消息时，找到与该消息含有相同杂凑值另一消息。这找到与该消息含有相同杂凑值另一消息。这一性质用于杂凑值被加密情况时一性质用于杂凑值被加密情况时(见图见图6.3(b)和和图图6.3(c)预防敌手伪造，因为在这种情况下，预防敌手伪造，因为在这种情况下，敌手可读取传送明文消息敌手可读取传送明文消息M，所以能产生该消，所以能产生该消息杂凑值息杂凑值H(M)。10/10/30第30页但因为敌手不知道用于加密杂凑值密钥，但因为敌手不知道用于加密杂凑值密钥，他就不可能既伪造一个消息他就不可能既伪造一个消息M，又伪造这，又伪造这个消息杂凑值加密后密文个消息杂凑值加密后密文EKH(M)。然而，假如第然而，假如第5个条件不成立，敌手在截个条件不成立，敌手在截获明文消息及其加密杂凑值后，就可按以获明文消息及其加密杂凑值后，就可按以下方式伪造消息：首先求出截获消息杂凑下方式伪造消息：首先求出截获消息杂凑值，然后产生一个含有相同杂凑值伪造消值，然后产生一个含有相同杂凑值伪造消息，最终再将伪造消息和截获加密杂凑值息，最终再将伪造消息和截获加密杂凑值发往通信接收方。发往通信接收方。第第6个条件用于抵抗生日攻击。个条件用于抵抗生日攻击。10/10/31第31页6.2.3 生日攻击生日攻击1.相关问题相关问题已知一杂凑函数已知一杂凑函数H有有n个可能输出，个可能输出，H(x)是是一个特定输出，假如对一个特定输出，假如对H随机取随机取k个输入，个输入，则最少有一个输入则最少有一个输入y使得使得H(y)=H(x)概率为概率为0.5时，时，k有多大？有多大？以后为叙述方便，称对杂凑函数以后为叙述方便，称对杂凑函数H寻找上述寻找上述y攻击为攻击为第第类生日攻击类生日攻击。10/10/32第32页因为因为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/nk，所以，所以y取取k个随机值得到函个随机值得到函数数k个输出中最少有一个等于个输出中最少有一个等于H(x)概率为概率为1-1-1/nk。由由(1+x)k1+kx，其中，其中|x|365k365，则不可能使得任意两个数据都不相同，则不可能使得任意两个数据都不相同，则不可能使得任意两个数据都不相同，则不可能使得任意两个数据都不相同，所以假定所以假定所以假定所以假定k365k365。k k个数据项中任意两个都不相同个数据项中任意两个都不相同个数据项中任意两个都不相同个数据项中任意两个都不相同全部取值方式数为全部取值方式数为全部取值方式数为全部取值方式数为10/10/34第34页 即第即第即第即第1 1个数据项可从个数据项可从个数据项可从个数据项可从365365个中任取一个，第个中任取一个，第个中任取一个，第个中任取一个，第2 2个数据个数据个数据个数据项可在剩下项可在剩下项可在剩下项可在剩下364364个中任取一个，依次类推，最终一个中任取一个，依次类推，最终一个中任取一个，依次类推，最终一个中任取一个，依次类推，最终一个数据项可从个数据项可从个数据项可从个数据项可从365-k+1365-k+1个值中任取一个。个值中任取一个。个值中任取一个。个值中任取一个。假如去掉任意两个都不相同这一限制条件，可得假如去掉任意两个都不相同这一限制条件，可得假如去掉任意两个都不相同这一限制条件，可得假如去掉任意两个都不相同这一限制条件，可得k k个数据项中全部取值方式数为个数据项中全部取值方式数为个数据项中全部取值方式数为个数据项中全部取值方式数为365365k k。所以可得。所以可得。所以可得。所以可得10/10/35第35页10/10/36第36页当当k=23时，时，P(365,23)=0.5073，即上述问，即上述问题只需题只需23人。人。若若k取取100，则，则P(365,100)=0.9999997，即，即取得如此大概率。取得如此大概率。之所以称这一问题是悖论是因为当人数之所以称这一问题是悖论是因为当人数k给定时，得到最少有两个人生日相同概率给定时，得到最少有两个人生日相同概率比想象要大得多。这是因为在比想象要大得多。这是因为在k个人中考个人中考虑是任意两个人生日是否相同，在虑是任意两个人生日是否相同，在23个人个人中可能情况数为中可能情况数为C223=253。10/10/37第37页将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在1 1到到到到n n之间之间之间之间均匀分布整数型随机变量，若该变量均匀分布整数型随机变量，若该变量均匀分布整数型随机变量，若该变量均匀分布整数型随机变量，若该变量k k个取值中最个取值中最个取值中最个取值中最少有两个取值相同概率大于少有两个取值相同概率大于少有两个取值相同概率大于少有两个取值相同概率大于0.50.5，则，则，则，则k k最少多大？最少多大？最少多大？最少多大？与上类似，与上类似，与上类似，与上类似，令，令，令，令P(n,k)0.5P(n,k)0.5，可得，可得，可得，可得 。若取若取若取若取n=365n=365，则，则，则，则 。10/10/38第38页3.3.生日攻击生日攻击生日攻击生日攻击生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数HH有有有有2 2mm个可能输出（即输出长个可能输出（即输出长个可能输出（即输出长个可能输出（即输出长mm比特），假如比特），假如比特），假如比特），假如HkHk个随个随个随个随机输入中最少有两个产生相同输出概率大于机输入中最少有两个产生相同输出概率大于机输入中最少有两个产生相同输出概率大于机输入中最少有两个产生相同输出概率大于0.50.5，则，则，则，则 。称寻找函数称寻找函数称寻找函数称寻找函数HH含有相同输出两个任意输入攻含有相同输出两个任意输入攻含有相同输出两个任意输入攻含有相同输出两个任意输入攻击方式为击方式为击方式为击方式为第第第第类生日攻击类生日攻击类生日攻击类生日攻击。10/10/39第39页第第类生日攻击可按以下方式进行：类生日攻击可按以下方式进行：设用户将用图设用户将用图6.3(c)所表示方式发送消息，即所表示方式发送消息，即A用自己秘密钥对消息杂凑值加密，加密结果作用自己秘密钥对消息杂凑值加密，加密结果作为对消息签字，连同明文消息一起发往接收者。为对消息签字，连同明文消息一起发往接收者。敌手对敌手对A发送消息发送消息M产生出产生出2m/2个变形消息，个变形消息，每个变形消息本质上含义与原消息相同，同时每个变形消息本质上含义与原消息相同，同时敌手还准备一个假冒消息敌手还准备一个假冒消息M，并对假冒消息产，并对假冒消息产生出生出2m/2个变形消息。个变形消息。敌手在产生两个消息集合中，找出杂凑值相同敌手在产生两个消息集合中，找出杂凑值相同一对消息一对消息,，由上述讨论可知敌手成功，由上述讨论可知敌手成功概率大于概率大于0.5。假如不成功，则重新产生一个假。假如不成功，则重新产生一个假冒消息，并产生冒消息，并产生2m/2个变形，直到找到杂凑值个变形，直到找到杂凑值相同一对消息为止。相同一对消息为止。10/10/40第40页敌手将敌手将 提交给提交给A请求签字，因为请求签字，因为 与与 杂凑值相同，所以可将杂凑值相同，所以可将A对对 签字看成对签字看成对 签字，将此签字连同签字，将此签字连同 一起发给意欲接收者。一起发给意欲接收者。上述攻击中假如杂凑值长为上述攻击中假如杂凑值长为64比特，则敌手比特，则敌手攻击成功所需时间复杂度为攻击成功所需时间复杂度为O(232)。将一个消息变形为含有相同含义另一消息方将一个消息变形为含有相同含义另一消息方法有很多，比如对文件，敌手可在文件单词法有很多，比如对文件，敌手可在文件单词之间插入很多之间插入很多“space-space-backspace”字字符对，然后将其中一些字符对替换为符对，然后将其中一些字符对替换为“space-backspace-space”就得到一个变形就得到一个变形消息。消息。10/10/41第41页6.2.4 迭代型杂凑函数普通结构迭代型杂凑函数普通结构当前使用大多数杂凑函数如当前使用大多数杂凑函数如MD5、SHA，其结构都是迭代型，其中函数输入其结构都是迭代型，其中函数输入M被分被分为为L个分组个分组Y0,Y1,YL-1，每一个分组长度，每一个分组长度为为b比特，最终一个分组长度不够话，需对比特，最终一个分组长度不够话，需对其做填充。其做填充。最终一个分组中还包含整个函数输入长度最终一个分组中还包含整个函数输入长度值，这么一来，将使得敌手攻击更为困难，值，这么一来，将使得敌手攻击更为困难，即敌手若想成功地产生假冒消息，就必须即敌手若想成功地产生假冒消息，就必须确保假冒消息杂凑值与原消息杂凑值相同，确保假冒消息杂凑值与原消息杂凑值相同，而且假冒消息长度也要与原消息长度相等。而且假冒消息长度也要与原消息长度相等。10/10/42第42页图图图图6.4 6.4 迭代型杂凑函数普通结构迭代型杂凑函数普通结构迭代型杂凑函数普通结构迭代型杂凑函数普通结构10/10/43第43页算法中重复使用一压缩函数算法中重复使用一压缩函数f，f 输入有两项：输入有两项：一项是上一轮（第一项是上一轮（第i-1轮）输出轮）输出n比特值比特值CVi-1，称为链，称为链接变量接变量另一项是算法在本轮（第另一项是算法在本轮（第i轮）轮）b比特输入分组比特输入分组Yi。f 输出为输出为n比特值比特值CVi，CVi又作为下一轮输入。又作为下一轮输入。算法开始时还需对链接变量指定一个初值算法开始时还需对链接变量指定一个初值IV，最，最终一轮输出链接变量终一轮输出链接变量CVL即为最终产生杂凑值。即为最终产生杂凑值。通常有通常有bn，所以称函数，所以称函数f为压缩函数。算法可表为压缩函数。算法可表示以下：示以下：CV0=IV=n比专长初值；比专长初值；CVi=f(CVi-1,Yi-1)；1iL；H(M)=CVL10/10/44第44页算法关键技术是设计无碰撞压缩函数算法关键技术是设计无碰撞压缩函数f，而敌手对算法攻击重点是而敌手对算法攻击重点是f 内部结构，因内部结构，因为为f 和分组密码一样是由若干轮处理过程和分组密码一样是由若干轮处理过程组成，所以对组成，所以对f 攻击需经过对各轮之间位攻击需经过对各轮之间位模式分析来进行，分析过程经常需要先找模式分析来进行，分析过程经常需要先找出出f 碰撞。碰撞。因为因为f 是压缩函数，其碰撞是不可防止，是压缩函数，其碰撞是不可防止，所以在设计所以在设计f 时就应确保找出其碰撞在计时就应确保找出其碰撞在计算上是不可行。算上是不可行。下面介绍几个主要迭代型杂凑函数。下面介绍几个主要迭代型杂凑函数。10/10/45第45页6.3 MD5杂凑算法杂凑算法MD4是是MD5杂凑算法前身，由杂凑算法前身，由Ron Rivest于于1990年年10月作为月作为RFC提出，提出，1992年年4月月公布公布MD4改进（改进（RFC 1320，1321）称为）称为MD5。10/10/46第46页6.3.1 算法描述算法描述MD5算法采取迭代型杂凑函数普通结构算法采取迭代型杂凑函数普通结构算法输入为任意长消息（图中为算法输入为任意长消息（图中为K比特），比特），分为分为512比专长分组，输出为比专长分组，输出为128比特消息摘比特消息摘要。要。10/10/47第47页图图图图6.5 MD56.5 MD5算法框图算法框图算法框图算法框图10/10/48第48页处理过程有以下几步：处理过程有以下几步：对消息填充，对消息填充，使得其比专长在模使得其比专长在模512下为下为448，即填充后消息长度为，即填充后消息长度为512某一倍数减某一倍数减64，留出，留出64比特备第比特备第2步使用。步使用。步骤步骤是必需，即使消息长度已满足要求，仍是必需，即使消息长度已满足要求，仍需填充。比如，消息长为需填充。比如，消息长为448比特，则需填充比特，则需填充512比特，使其长度变为比特，使其长度变为960，所以填充比特数，所以填充比特数大于等于大于等于1而小于等于而小于等于512。填充方式是固定，即第填充方式是固定，即第1位为位为1，其后各位皆为，其后各位皆为0。10/10/49第49页 附加消息长度附加消息长度 用步骤用步骤留出留出64比特以比特以little-endian方式来表示消息被填充前长度。假如消方式来表示消息被填充前长度。假如消息长度大于息长度大于264，则以，则以264为模数取模。为模数取模。little-endian方式是指按数据最低有效字节方式是指按数据最低有效字节（byte）（或最低有效位）优先次序存放数据，即）（或最低有效位）优先次序存放数据，即将最低有效字节（或最低有效位）存于低地址字节将最低有效字节（或最低有效位）存于低地址字节（或位）。相反存放方式称为（或位）。相反存放方式称为big-endian方式。方式。前两步执行完后，消息长度为前两步执行完后，消息长度为512倍数（设为倍数（设为L倍），则可将消息表示为分组长为倍），则可将消息表示为分组长为512一系一系列分组列分组Y0，Y1，YL-1，而每一分组又可表，而每一分组又可表示为示为16个个32比专长字，这么消息中总字数为比专长字，这么消息中总字数为N=L16，所以消息又可按字表示为，所以消息又可按字表示为M0,N-1。10/10/50第50页 对对MD缓冲区初始化缓冲区初始化 算法使用算法使用128比专长缓冲比专长缓冲区以存放中间结果和最终杂凑值，缓冲区可表示区以存放中间结果和最终杂凑值，缓冲区可表示为为4个个32比专长存放器（比专长存放器（A，B，C，D），每个），每个存放器都以存放器都以littleendian方式存放数据，其初值方式存放数据，其初值取为（以存放方式）取为（以存放方式）A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210，实际上为，实际上为67452301，EFCDAB89，98BADCFE，10325476。以分组为单位对消息进行处理以分组为单位对消息进行处理 每一分组每一分组Yq(q=0,L-1)都经一压缩函数都经一压缩函数HMD5处理。处理。HMD5是算法关键，其中又有是算法关键，其中又有4轮处理过程。轮处理过程。输出输出 消息消息L个分组都被处理完后，最终一个个分组都被处理完后，最终一个HMD5输出即为产生消息摘要。输出即为产生消息摘要。10/10/51第51页10/10/52第52页10/10/53第53页HMD54轮处理过程结构一样，但所用逻辑函数轮处理过程结构一样，但所用逻辑函数不一样，分别表示为不一样，分别表示为F、G、H、I。每轮输入。每轮输入为当前处理消息分组为当前处理消息分组Yq和缓冲区当前值和缓冲区当前值A、B、C、D，输出仍放在缓冲区中以产生新，输出仍放在缓冲区中以产生新A、B、C、D。每轮处理过程还需加上常数表每轮处理过程还需加上常数表T中四分之一个中四分之一个元素，分别为元素，分别为T116,T1732,T3348,T4964。表。表T有有64个元素，第个元素，第i个元素个元素Ti为为232abs(sin(i)整数部分，其中整数部分，其中sin为正弦函数，为正弦函数，i以弧度为单位。因为以弧度为单位。因为abs(sin(i)大于大于0小于小于1，所以所以Ti可由可由32比特字表示。比特字表示。第第4轮输出再与第轮输出再与第1轮输入轮输入CVq相加，相加时将相加，相加时将CVq看作看作4个个32比特字，每个字与第比特字，每个字与第4轮输出对轮输出对应字按模应字按模232相加，相加结果即为压缩函数相加，相加结果即为压缩函数HMD5输出。输出。10/10/54第54页步骤步骤到步骤到步骤处理过程可总结以下：处理过程可总结以下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL 其中其中IV是步骤是步骤所取缓冲区所取缓冲区ABCD初值，初值，Yq是是消息第消息第q个个512比专长分组，比专长分组，L是消息经过步骤是消息经过步骤和步骤和步骤处理后分组数，处理后分组数，CVq为处理消息第为处理消息第q个个分组时输入链接变量（即前一个压缩函数输出）分组时输入链接变量（即前一个压缩函数输出），RFx为使用基本逻辑函数为使用基本逻辑函数x轮函数，轮函数，+为对应字为对应字模模232加法，加法，MD为最终杂凑值。为最终杂凑值。10/10/55第55页6.3.2 MD5压缩函数压缩函数压缩函数压缩函数HMD5中有中有4轮处理过程，每轮又对轮处理过程，每轮又对缓冲区缓冲区ABCD进行进行16步迭代运算，每一步步迭代运算，每一步运算形式为运算形式为ab+CLSs(a+g(b,c,d)+Xk+Ti)其中其中a、