《第6章-消息认证和杂凑函数》由会员分享，可在线阅读，更多相关《第6章-消息认证和杂凑函数（93页珍藏版）》请在金锄头文库上搜索。
1、6.1 消息认证码消息认证码6.2 杂凑函数杂凑函数6.3 MD5杂凑算法杂凑算法6.4 安全杂凑算法安全杂凑算法6.5 HMAC9/9/20241第第1章曾介绍过信息安全所面临的基本攻击类型，章曾介绍过信息安全所面临的基本攻击类型，包括被动攻击和主动攻击。抗击被动攻击的方法包括被动攻击和主动攻击。抗击被动攻击的方法是前面已介绍过的加密，本章介绍的是前面已介绍过的加密，本章介绍的消息认证则消息认证则是用来抗击主动攻击是用来抗击主动攻击的。的。消息认证是一个过程，用以验证接收消息的消息认证是一个过程，用以验证接收消息的真实真实性性（的确是由它所声称的实体发来的）和（的确是由它所声称的实体发来的）
2、和完整性完整性（未被篡改、插入、删除），同时还用于验证消（未被篡改、插入、删除），同时还用于验证消息的息的顺序性顺序性和和时间性时间性（未重排、重放、延迟）。（未重排、重放、延迟）。除此之外，在考虑信息安全时还需考虑业务的除此之外，在考虑信息安全时还需考虑业务的不不可否认性可否认性，即防止通信双方中的某一方对所传输，即防止通信双方中的某一方对所传输消息的否认。实现消息的不可否认性可通过数字消息的否认。实现消息的不可否认性可通过数字签字，数字签字也是一种认证技术，它也可用于签字，数字签字也是一种认证技术，它也可用于抗击主动攻击。抗击主动攻击。9/9/20242消息认证机制和数字签字机制都有产生认
3、消息认证机制和数字签字机制都有产生认证符的基本功能，这一基本功能又作为认证符的基本功能，这一基本功能又作为认证协议的一个组成部分。证协议的一个组成部分。认证符是用于认证消息的数值，它的产生认证符是用于认证消息的数值，它的产生方法又分为方法又分为消息认证码消息认证码MAC（message authentication code）杂凑函数杂凑函数（hash function）9/9/202436.1 消息认证码消息认证码6.1.1 消息认证码的定义及使用方式消息认证码的定义及使用方式 消息认证码是指消息被一密钥控制的公开消息认证码是指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定函数作
4、用后产生的、用作认证符的、固定长度的数值长度的数值，也称为密码校验和。，也称为密码校验和。此时需要通信双方此时需要通信双方A和和B共享一密钥共享一密钥K。设。设A欲发送给欲发送给B的消息是的消息是M，A首先计算首先计算MAC=CK(M)，其中，其中CK()是密钥控制的公是密钥控制的公开函数，然后向开函数，然后向B发送发送MMAC，B收到后收到后做与做与A相同的计算，求得一新相同的计算，求得一新MAC，并与，并与收到的收到的MAC做比较做比较9/9/20244图图6.1 MAC的基本使用方式的基本使用方式9/9/20245如果仅收发双方知道如果仅收发双方知道K，且，且B计算得到的计算得到的MAC
5、与接收到的与接收到的MAC一致，则这一系一致，则这一系统就实现了以下功能：统就实现了以下功能：接收方相信发送方发来的消息未被篡改接收方相信发送方发来的消息未被篡改，这是因为攻击者不知道密钥，所以不能够这是因为攻击者不知道密钥，所以不能够在篡改消息后相应地篡改在篡改消息后相应地篡改MAC，而如果仅，而如果仅篡改消息，则接收方计算的新篡改消息，则接收方计算的新MAC将与收将与收到的到的MAC不同。不同。接收方相信发送方不是冒充的接收方相信发送方不是冒充的，这是因为，这是因为除收发双方外再无其他人知道密钥，因此除收发双方外再无其他人知道密钥，因此其他人不可能对自己发送的消息计算出正其他人不可能对自己
6、发送的消息计算出正确的确的MAC。9/9/20246MAC函数与加密算法类似，不同之处为函数与加密算法类似，不同之处为MAC函数不必是可逆的，因此与加密算法函数不必是可逆的，因此与加密算法相比更不易被攻破。相比更不易被攻破。上述过程中，由于消息本身在发送过程中上述过程中，由于消息本身在发送过程中是明文形式，所以这一过程只提供认证性是明文形式，所以这一过程只提供认证性而未提供保密性。而未提供保密性。为提供保密性可在为提供保密性可在MAC函数以后或以前进函数以后或以前进行一次加密，而且加密密钥也需被收发双行一次加密，而且加密密钥也需被收发双方共享。方共享。9/9/202479/9/202486.1
7、.2 产生产生MAC的函数应满足的要求的函数应满足的要求使用加密算法（单钥算法或公钥算法）加密使用加密算法（单钥算法或公钥算法）加密消息时，其安全性一般取决于密钥的长度。消息时，其安全性一般取决于密钥的长度。如果加密算法没有弱点，则敌手只能使用穷如果加密算法没有弱点，则敌手只能使用穷搜索攻击以测试所有可能的密钥。如果密钥搜索攻击以测试所有可能的密钥。如果密钥长为长为k比特，则穷搜索攻击平均将进行比特，则穷搜索攻击平均将进行2k-1个个测试。特别地，对惟密文攻击来说，敌手如测试。特别地，对惟密文攻击来说，敌手如果知道密文果知道密文C，则将对所有可能的密钥值，则将对所有可能的密钥值Ki执行解密运算
8、执行解密运算Pi=DKi(C)，直到得到有意义，直到得到有意义的明文。的明文。9/9/20249对对MAC来说，由于产生来说，由于产生MAC的函数一般的函数一般都为多到一映射，如果产生都为多到一映射，如果产生n比特长的比特长的MAC，则函数的取值范围即为，则函数的取值范围即为2n个可能个可能的的MAC，函数输入的可能的消息个数，函数输入的可能的消息个数N2n，而且如果函数所用的密钥为，而且如果函数所用的密钥为k比比特，则可能的密钥个数为特，则可能的密钥个数为2k。如果系统不。如果系统不考虑保密性，即敌手能获取明文消息和相考虑保密性，即敌手能获取明文消息和相应的应的MAC，那么在这种情况下要考虑
9、敌，那么在这种情况下要考虑敌手使用穷搜索攻击来获取产生手使用穷搜索攻击来获取产生MAC的函的函数所使用的密钥。数所使用的密钥。9/9/202410假定假定kn，且敌手已得到，且敌手已得到M1和和MAC1，其中，其中MAC1=CK1（M1），敌手对所有可能的密钥值），敌手对所有可能的密钥值Ki求求MACi=CKi(M1)，直到找到某个，直到找到某个Ki使得使得MACi=MAC1。由于不同的密钥个数为。由于不同的密钥个数为2k，因，因此将产生此将产生2k个个MAC，但其中仅有，但其中仅有2n个不同，由个不同，由于于2k2n，所以有很多密钥（平均有，所以有很多密钥（平均有2k/2n=2k-n个）都可
10、产生出正确的个）都可产生出正确的MAC1，而敌手无法知，而敌手无法知道进行通信的两个用户用的是哪一个密钥，还道进行通信的两个用户用的是哪一个密钥，还必须按以下方式重复上述攻击：必须按以下方式重复上述攻击：9/9/202411第第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个可能的密
11、个可能的密钥。钥。如此下去，如果如此下去，如果k=n，则上述攻击方式平均需，则上述攻击方式平均需要要轮。例如，密钥长为轮。例如，密钥长为80比特，比特，MAC长为长为32比特，则第比特，则第1轮将产生大约轮将产生大约248个可能密钥，第个可能密钥，第2轮将产生轮将产生216个可能的密钥，第个可能的密钥，第3轮即可找出正轮即可找出正确的密钥。确的密钥。9/9/202412如果密钥长度小于如果密钥长度小于MAC的长度，则第的长度，则第1轮轮就有可能找出正确的密钥，也有可能找出就有可能找出正确的密钥，也有可能找出多个可能的密钥，如果是后者，则仍需执多个可能的密钥，如果是后者，则仍需执行第行第2轮搜索
12、。轮搜索。所以对消息认证码的穷搜索攻击比对使用所以对消息认证码的穷搜索攻击比对使用相同长度密钥的加密算法的穷搜索攻击的相同长度密钥的加密算法的穷搜索攻击的代价还要大。代价还要大。有些攻击法却不需要寻找产生有些攻击法却不需要寻找产生MAC所使所使用的密钥。用的密钥。9/9/202413例如，设例如，设例如，设例如，设M=(XM=(X1 1XX2 2XXmm) )是由是由是由是由6464比特长的分比特长的分比特长的分比特长的分组组组组X Xi i(i=1,m)(i=1,m)链接得到的，其消息认证码由以下链接得到的，其消息认证码由以下链接得到的，其消息认证码由以下链接得到的，其消息认证码由以下方式得
13、到：方式得到：方式得到：方式得到：其中其中其中其中表示异或运算，加密算法是电码本模式的表示异或运算，加密算法是电码本模式的表示异或运算，加密算法是电码本模式的表示异或运算，加密算法是电码本模式的DESDES。因此，密钥长为。因此，密钥长为。因此，密钥长为。因此，密钥长为5656比特，比特，比特，比特，MACMAC长为长为长为长为6464比特，比特，比特，比特，如果敌手得到如果敌手得到如果敌手得到如果敌手得到MCMCKK(M)(M)，那么敌手使用穷搜索攻击，那么敌手使用穷搜索攻击，那么敌手使用穷搜索攻击，那么敌手使用穷搜索攻击寻找寻找寻找寻找KK将需做将需做将需做将需做2 25656次加密。然而
14、敌手还可用以下方式次加密。然而敌手还可用以下方式次加密。然而敌手还可用以下方式次加密。然而敌手还可用以下方式攻击系统：攻击系统：攻击系统：攻击系统： 将将将将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 Y
15、mm，且，且，且，且MM的的的的MACMAC与原消息与原消息与原消息与原消息MM的的的的MACMAC相同。相同。相同。相同。9/9/202414考虑到考虑到MAC所存在的以上攻击类型，可所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道知它应满足以下要求，其中假定敌手知道函数函数C，但不知道密钥，但不知道密钥K：如果敌手得到如果敌手得到M和和CK(M)，则构造一满足，则构造一满足CK(M)=CK(M)的新消息的新消息M在计算上是不可在计算上是不可行的。行的。CK(M)在以下意义下是均匀分布的：在以下意义下是均匀分布的： 随机选随机选取两个消息取两个消息M、M，PrCK(M)=CK(M
16、)=2-n，其中，其中n为为MAC的长。的长。若若M是是M的某个变换，即的某个变换，即M=f(M)，例如，例如f为为插入一个或多个比特，那么插入一个或多个比特，那么PrCK(M)=CK(M)= 2-n。9/9/202415第第1个要求是针对上例中的攻击类型的，此个要求是针对上例中的攻击类型的，此要求是说敌手不需要找出密钥要求是说敌手不需要找出密钥K而伪造一而伪造一个与截获的个与截获的MAC相匹配的新消息在计算上相匹配的新消息在计算上是不可行的。是不可行的。第第2个要求是说敌手如果截获一个个要求是说敌手如果截获一个MAC，则伪造一个相匹配的消息的概率为最小。则伪造一个相匹配的消息的概率为最小。最
17、后一个要求是说函数最后一个要求是说函数C不应在消息的某不应在消息的某个部分或某些比特弱于其他部分或其他比个部分或某些比特弱于其他部分或其他比特，否则敌手获得特，否则敌手获得M和和MAC后就有可能修后就有可能修改改M中弱的部分，从而伪造出一个与原中弱的部分，从而伪造出一个与原MAC相匹配的新消息。相匹配的新消息。9/9/2024166.1.3 数据认证算法数据认证算法数据认证算法是最为广泛使用的消息认证数据认证算法是最为广泛使用的消息认证码中的一个，已作为码中的一个，已作为FIPS Publication（FIPS PUB 113）并被）并被ANSI作作为为X9.17标准。标准。算法基于算法基于
18、CBC模式的模式的DES算法，其初始向算法，其初始向量取为零向量。需被认证的数据（消息、量取为零向量。需被认证的数据（消息、记录、文件或程序）被分为记录、文件或程序）被分为64比特长的分比特长的分组组D1，D2，DN，其中最后一个分组不，其中最后一个分组不够够64比特的话，可在其右边填充一些比特的话，可在其右边填充一些0，然，然后按以下过程计算数据认证码后按以下过程计算数据认证码9/9/202417图图图图6.2 6.2 数据认证算法数据认证算法数据认证算法数据认证算法9/9/202418其中其中其中其中E E为为为为DESDES加密算法，加密算法，加密算法，加密算法，KK为密钥。为密钥。为密
19、钥。为密钥。数据认证码或者取为数据认证码或者取为数据认证码或者取为数据认证码或者取为OON N或者取为或者取为或者取为或者取为OON N的最左的最左的最左的最左MM个比个比个比个比特，其中特，其中特，其中特，其中16M6416M64。9/9/2024196.2 杂凑函数杂凑函数6.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式杂凑函数杂凑函数H是一公开函数，用于将任意长的是一公开函数，用于将任意长的消息消息M映射为较短的、固定长度的一个值映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值作为认证符，称函数值H(M)为杂凑为杂凑值、杂凑码或消息摘要。值、杂凑码或消息摘要。杂凑
20、码是消息中所有比特的函数，因此提杂凑码是消息中所有比特的函数，因此提供了一种供了一种错误检测错误检测能力，即改变消息中任能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生何一个比特或几个比特都会使杂凑码发生改变。改变。9/9/202420杂凑函数用来提供消息认证的基本使用方杂凑函数用来提供消息认证的基本使用方式共有式共有6种种1.消息与杂凑码链接后用单钥加密算法加密。消息与杂凑码链接后用单钥加密算法加密。由于所用密钥仅为收发双方由于所用密钥仅为收发双方A、B共享，因此共享，因此可保证消息的确来自可保证消息的确来自A并且未被篡改。同时并且未被篡改。同时还由于消息和杂凑码都被加密，这种方式还
21、还由于消息和杂凑码都被加密，这种方式还提供了保密性提供了保密性2.用单钥加密算法仅对杂凑码加密。这种方式用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性的情况下，可减少处理负用于不要求保密性的情况下，可减少处理负担。注意这种方式和图担。注意这种方式和图6.1(a)的的MAC结果完结果完全一样，即将全一样，即将EKH(M)看作一个函数，函数看作一个函数，函数的输入为消息的输入为消息M和密钥和密钥K，输出为固定长度，输出为固定长度9/9/2024219/9/2024223.用公钥加密算法和发送方的秘密钥仅加用公钥加密算法和发送方的秘密钥仅加密杂凑码。和密杂凑码。和一样，这种方式提供认一样，这
22、种方式提供认证性，又由于只有发送方能产生加密的证性，又由于只有发送方能产生加密的杂凑码，因此这种方式还对发送方发送杂凑码，因此这种方式还对发送方发送的消息提供了数字签字，事实上这种方的消息提供了数字签字，事实上这种方式就是数字签字式就是数字签字4.消息的杂凑值用公钥加密算法和发送方消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接的秘密钥加密后与消息链接，再对链接后的结果用单钥加密算法加密，这种方后的结果用单钥加密算法加密，这种方式提供了保密性和数字签字式提供了保密性和数字签字9/9/2024239/9/2024245.使用这种方式时要求通信双方共享一个秘密使用这种方式时要求
23、通信双方共享一个秘密值值S，A计算消息计算消息M和秘密值和秘密值S链接在一起的杂链接在一起的杂凑值，并将此杂凑值附加到凑值，并将此杂凑值附加到M后发往后发往B。因。因B也有也有S，所以可重新计算杂凑值以对消息进行，所以可重新计算杂凑值以对消息进行认证。由于秘密值认证。由于秘密值S本身未被发送，敌手无法本身未被发送，敌手无法对截获的消息加以篡改，也无法产生假消息。对截获的消息加以篡改，也无法产生假消息。这种方式仅提供认证这种方式仅提供认证6.这种方式是在这种方式是在中消息与杂凑值链接以后再中消息与杂凑值链接以后再增加单钥加密运算，从而又可提供保密性增加单钥加密运算，从而又可提供保密性由于加密运算
24、的速度较慢，代价较高，而且由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要很多加密算法还受到专利保护，因此在不要求保密性的情况下，方式求保密性的情况下，方式和和将比其他方将比其他方式更具优势。式更具优势。9/9/2024259/9/2024266.2.2 杂凑函数应满足的条件杂凑函数应满足的条件杂凑函数的目的是为需认证的数据产生杂凑函数的目的是为需认证的数据产生一个一个“指纹指纹”。为了能够实现对数据的。为了能够实现对数据的认证，杂凑函数应满足以下条件：认证，杂凑函数应满足以下条件：1.函数的输入可以是任意长。函数的输入可以是任意长。2.函数的输出是固定长。函数的输
25、出是固定长。3.已知已知x，求，求H(x)较为容易，可用硬件或软件较为容易，可用硬件或软件实现。实现。4.已知已知h，求使得，求使得H(x)=h的的x在计算上是不可行在计算上是不可行的，这一性质称为函数的单向性，称的，这一性质称为函数的单向性，称H(x)为为单向杂凑函数单向杂凑函数。9/9/2024275.已知已知x，找出，找出y(yx)使得使得H(y)=H(x)在计算在计算上是不可行的。如果单向杂凑函数满足上是不可行的。如果单向杂凑函数满足这一性质，则称其为这一性质，则称其为弱单向杂凑函数。弱单向杂凑函数。6.找出任意两个不同的输入找出任意两个不同的输入x、y，使得，使得H(y)=H(x)在
26、计算上是不可行的。如果单在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为向杂凑函数满足这一性质，则称其为强强单向杂凑函数单向杂凑函数。第第和第和第个条件给出了杂凑函数无碰个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称该函数入可产生相同的输出，则称该函数具有具有碰撞性碰撞性。9/9/202428以上以上6个条件中，前个条件中，前3个是杂凑函数能用于消息个是杂凑函数能用于消息认证的基本要求。认证的基本要求。第第4个条件（即单向性）则对使用秘密值的认个条件（即单向性）则对使用秘密值的认证技术证技术(见图见图6.3(e)极
27、为重要。假如杂凑函数极为重要。假如杂凑函数不具有单向性，则攻击者截获不具有单向性，则攻击者截获M和和C=H(SM)后，求后，求C的逆的逆SM，就可求出秘密值，就可求出秘密值S。第第5个条件使得敌手无法在已知某个消息时，个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。找到与该消息具有相同杂凑值的另一消息。这一性质用于杂凑值被加密情况时这一性质用于杂凑值被加密情况时(见图见图6.3(b)和图和图6.3(c)防止敌手的伪造，由于在这种情况防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息下，敌手可读取传送的明文消息M，因此能产，因此能产生该消息的杂凑值生该消息的杂凑
28、值H(M)。9/9/202429但由于敌手不知道用于加密杂凑值的密钥，但由于敌手不知道用于加密杂凑值的密钥，他就不可能既伪造一个消息他就不可能既伪造一个消息M，又伪造这，又伪造这个消息的杂凑值加密后的密文个消息的杂凑值加密后的密文EKH(M)。然而，如果第然而，如果第5个条件不成立，敌手在截个条件不成立，敌手在截获明文消息及其加密的杂凑值后，就可按获明文消息及其加密的杂凑值后，就可按以下方式伪造消息：首先求出截获的消息以下方式伪造消息：首先求出截获的消息的杂凑值，然后产生一个具有相同杂凑值的杂凑值，然后产生一个具有相同杂凑值的伪造消息，最后再将伪造的消息和截获的伪造消息，最后再将伪造的消息和截
29、获的加密的杂凑值发往通信的接收方。的加密的杂凑值发往通信的接收方。第第6个条件用于抵抗生日攻击。个条件用于抵抗生日攻击。9/9/2024306.2.3 生日攻击生日攻击1. 相关问题相关问题已知一杂凑函数已知一杂凑函数H有有n个可能的输出，个可能的输出，H(x)是一个特定的输出，如果对是一个特定的输出，如果对H随机取随机取k个输个输入，则至少有一个输入入，则至少有一个输入y使得使得H(y)=H(x)的概的概率为率为0.5时，时，k有多大？有多大？以后为叙述方便，称对杂凑函数以后为叙述方便，称对杂凑函数H寻找上述寻找上述y的攻击为的攻击为第第类生日攻击类生日攻击。9/9/202431因为因为H有
30、有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，则不可能
31、使得任意两个数据都不相同，则不可能使得任意两个数据都不相同，则不可能使得任意两个数据都不相同，则不可能使得任意两个数据都不相同，因此假定因此假定因此假定因此假定k365k365。k k个数据项中任意两个都不相同个数据项中任意两个都不相同个数据项中任意两个都不相同个数据项中任意两个都不相同的所有取值方式数为的所有取值方式数为的所有取值方式数为的所有取值方式数为9/9/202433 即第即第即第即第1 1个数据项可从个数据项可从个数据项可从个数据项可从365365个中任取一个，第个中任取一个，第个中任取一个，第个中任取一个，第2 2个数据个数据个数据个数据项可在剩余的项可在剩余的项可在剩余的项可在
32、剩余的364364个中任取一个，依次类推，最后个中任取一个，依次类推，最后个中任取一个，依次类推，最后个中任取一个，依次类推，最后一个数据项可从一个数据项可从一个数据项可从一个数据项可从365-k+1365-k+1个值中任取一个。个值中任取一个。个值中任取一个。个值中任取一个。如果去掉任意两个都不相同这一限制条件，可得如果去掉任意两个都不相同这一限制条件，可得如果去掉任意两个都不相同这一限制条件，可得如果去掉任意两个都不相同这一限制条件，可得k k个数据项中所有取值方式数为个数据项中所有取值方式数为个数据项中所有取值方式数为个数据项中所有取值方式数为365365k k。所以可得所以可得所以可得
33、所以可得9/9/2024349/9/202435当当k=23时，时，P(365,23)=0.5073，即上述问，即上述问题只需题只需23人。人。若若k取取100，则，则P(365,100)=0.9999997，即，即获得如此大的概率。获得如此大的概率。之所以称这一问题是悖论是因为当人数之所以称这一问题是悖论是因为当人数k给定时，得到的至少有两个人的生日相同给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。这是因为在的概率比想象的要大得多。这是因为在k个人中考虑的是任意两个人的生日是否相个人中考虑的是任意两个人的生日是否相同，在同，在23个人中可能的情况数为个人中可能的情况数为C223
34、=253。9/9/202436将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在1 1到到到到n n之间之间之间之间均匀分布的整数型随机变量，若该变量的均匀分布的整数型随机变量，若该变量的均匀分布的整数型随机变量，若该变量的均匀分布的整数型随机变量，若该变量的k k个取值个取值个取值个取值中至少有两个取值相同的概率大于中至少有两个取值相同的概率大于中至少有两个取值相同的概率大于中至少有两个取值相同的概率大于0.50.5，则，则，则，则k k至少多至少多至少多至少多大？大？大？大？与上类似，与上类似，与
35、上类似，与上类似， ，令，令，令，令P(n, k)0.5P(n, k)0.5，可得，可得，可得，可得 。若取若取若取若取n=365n=365，则，则，则，则 。9/9/2024373. 3. 生日攻击生日攻击生日攻击生日攻击生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数HH有有有有2 2mm个可能的输出（即输出长个可能的输出（即输出长个可能的输出（即输出长个可能的输出（即输出长mm比特），如果比特），如果比特），如果比特），如果HH的的的的k k个随机输入中至少有两个产生相同输出的概率大个随机输入中至少有
36、两个产生相同输出的概率大个随机输入中至少有两个产生相同输出的概率大个随机输入中至少有两个产生相同输出的概率大于于于于0.50.5，则，则，则，则 。称寻找函数称寻找函数称寻找函数称寻找函数HH的具有相同输出的两个任意输的具有相同输出的两个任意输的具有相同输出的两个任意输的具有相同输出的两个任意输入的攻击方式为入的攻击方式为入的攻击方式为入的攻击方式为第第第第类生日攻击类生日攻击类生日攻击类生日攻击。9/9/202438第第类生日攻击可按以下方式进行：类生日攻击可按以下方式进行： 设用户将用图设用户将用图6.3(c)所示的方式发送消息，即所示的方式发送消息，即A用自己的秘密钥对消息的杂凑值加密，
37、加密结用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往果作为对消息的签字，连同明文消息一起发往接收者。接收者。 敌手对敌手对A发送的消息发送的消息M产生出产生出2m/2个变形的消个变形的消息，每个变形的消息本质上的含义与原消息相息，每个变形的消息本质上的含义与原消息相同，同时敌手还准备一个假冒的消息同，同时敌手还准备一个假冒的消息M，并对，并对假冒的消息产生出假冒的消息产生出2m/2个变形的消息。个变形的消息。敌手在产生的两个消息集合中，找出杂凑值相敌手在产生的两个消息集合中，找出杂凑值相同的一对消息同的一对消息, ，由上述讨论可知敌手，由上述讨论可知敌手成功的
38、概率大于成功的概率大于0.5。如果不成功，则重新产生。如果不成功，则重新产生一个假冒的消息，并产生一个假冒的消息，并产生2m/2个变形，直到找个变形，直到找到杂凑值相同的一对消息为止。到杂凑值相同的一对消息为止。9/9/202439敌手将敌手将 提交给提交给A请求签字，由于请求签字，由于 与与 的杂凑值相同，所以可将的杂凑值相同，所以可将A对对 的签字当作的签字当作对对 的签字，将此签字连同的签字，将此签字连同 一起发给意一起发给意欲的接收者。欲的接收者。上述攻击中如果杂凑值的长为上述攻击中如果杂凑值的长为64比特，则敌比特，则敌手攻击成功所需的时间复杂度为手攻击成功所需的时间复杂度为O(23
39、2)。将一个消息变形为具有相同含义的另一消息将一个消息变形为具有相同含义的另一消息的方法有很多，例如对文件，敌手可在文件的方法有很多，例如对文件，敌手可在文件的单词之间插入很多的单词之间插入很多“space-space-backspace”字符对，然后将其中的某些字符字符对，然后将其中的某些字符对替换为对替换为“space-backspace-space ”就得到就得到一个变形的消息。一个变形的消息。9/9/2024406.2.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构目前使用的大多数杂凑函数如目前使用的大多数杂凑函数如MD5、SHA，其结构都是迭代型的，其中函数的输入，其结构都是迭
40、代型的，其中函数的输入M被分为被分为L个分组个分组Y0,Y1,YL-1，每一个分，每一个分组的长度为组的长度为b比特，最后一个分组的长度不比特，最后一个分组的长度不够的话，需对其做填充。够的话，需对其做填充。最后一个分组中还包括整个函数输入的长最后一个分组中还包括整个函数输入的长度值，这样一来，将使得敌手的攻击更为度值，这样一来，将使得敌手的攻击更为困难，即敌手若想成功地产生假冒的消息，困难，即敌手若想成功地产生假冒的消息，就必须保证假冒消息的杂凑值与原消息的就必须保证假冒消息的杂凑值与原消息的杂凑值相同，而且假冒消息的长度也要与杂凑值相同，而且假冒消息的长度也要与原消息的长度相等。原消息的长
41、度相等。9/9/202441图图图图6.4 6.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构9/9/202442算法中重复使用一压缩函数算法中重复使用一压缩函数f，f 的输入有两项：的输入有两项：一项是上一轮（第一项是上一轮（第i-1轮）输出的轮）输出的n比特值比特值CVi-1，称为，称为链接变量链接变量另一项是算法在本轮（第另一项是算法在本轮（第i轮）的轮）的b比特输入分组比特输入分组Yi。f 的输出为的输出为n比特值比特值CVi，CVi又作为下一轮的输入。又作为下一轮的输入。算法开始时还需对链接变量指定一个初值算法开始时还需对链接变量
42、指定一个初值IV，最，最后一轮输出的链接变量后一轮输出的链接变量CVL即为最终产生的杂凑即为最终产生的杂凑值。通常有值。通常有bn，因此称函数，因此称函数f为压缩函数。算法为压缩函数。算法可表达如下：可表达如下：CV0=IV=n比特长的初值；比特长的初值；CVi=f(CVi-1,Yi-1)；1iL；H(M)=CVL9/9/202443算法的核心技术是设计无碰撞的压缩函数算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是，而敌手对算法的攻击重点是f 的内部结的内部结构，由于构，由于f 和分组密码一样是由若干轮处和分组密码一样是由若干轮处理过程组成，所以对理过程组成，所以对f 的攻击
43、需通过对各的攻击需通过对各轮之间的位模式的分析来进行，分析过程轮之间的位模式的分析来进行，分析过程常常需要先找出常常需要先找出f 的碰撞。的碰撞。由于由于f 是压缩函数，其碰撞是不可避免的，是压缩函数，其碰撞是不可避免的，因此在设计因此在设计f 时就应保证找出其碰撞在计时就应保证找出其碰撞在计算上是不可行的。算上是不可行的。下面介绍几个重要的迭代型杂凑函数。下面介绍几个重要的迭代型杂凑函数。9/9/2024446.3 MD5杂凑算法杂凑算法MD4是是MD5杂凑算法的前身，由杂凑算法的前身，由Ron Rivest于于1990年年10月作为月作为RFC提出，提出，1992年年4月公布的月公布的MD
44、4的改进（的改进（RFC 1320，1321）称为）称为MD5。9/9/2024456.3.1 算法描述算法描述MD5算法采用迭代型杂凑函数的一般结构算法采用迭代型杂凑函数的一般结构算法的输入为任意长的消息（图中为算法的输入为任意长的消息（图中为K比特）比特），分为，分为512比特长的分组，输出为比特长的分组，输出为128比特的比特的消息摘要。消息摘要。9/9/202446图图图图6.5 MD56.5 MD5的算法框图的算法框图的算法框图的算法框图9/9/202447处理过程有以下几步：处理过程有以下几步： 对消息填充，对消息填充，使得其比特长在模使得其比特长在模512下为下为448，即填充后
45、消息的长度为，即填充后消息的长度为512的某一倍数的某一倍数减减64，留出的，留出的64比特备第比特备第2步使用。步使用。步骤步骤是必需的，即使消息长度已满足要求，是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为仍需填充。例如，消息长为448比特，则需填充比特，则需填充512比特，使其长度变为比特，使其长度变为960，因此填充的比特，因此填充的比特数大于等于数大于等于1而小于等于而小于等于512。填充方式是固定的，即第填充方式是固定的，即第1位为位为1，其后各位皆，其后各位皆为为0。9/9/202448 附加消息的长度附加消息的长度 用步骤用步骤留出的留出的64比特以比特以littl
46、e-endian方式来表示消息被填充前的长度。方式来表示消息被填充前的长度。如果消息长度大于如果消息长度大于264，则以，则以264为模数取模。为模数取模。little-endian方式是指按数据的最低有效字节方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，）（或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字即将最低有效字节（或最低有效位）存于低地址字节（或位）。相反的存储方式称为节（或位）。相反的存储方式称为big-endian方式。方式。前两步执行完后，消息的长度为前两步执行完后，消息的长度为512的倍数的倍数（设为（设为L倍），则
47、可将消息表示为分组长为倍），则可将消息表示为分组长为512的一系列分组的一系列分组Y0，Y1，YL-1，而每一，而每一分组又可表示为分组又可表示为16个个32比特长的字，这样消比特长的字，这样消息中的总字数为息中的总字数为N=L16，因此消息又可按字，因此消息又可按字表示为表示为M0,N-1。9/9/202449 对对MD缓冲区初始化缓冲区初始化 算法使用算法使用128比特长的缓比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表冲区以存储中间结果和最终杂凑值，缓冲区可表示为示为4个个32比特长的寄存器（比特长的寄存器（A，B，C，D），），每个寄存器都以每个寄存器都以littleendian
48、方式存储数据，其方式存储数据，其初值取为（以存储方式）初值取为（以存储方式）A=01234567，B=89ABCDEF， C=FEDCBA98，D=76543210，实际上为，实际上为67452301，EFCDAB89，98BADCFE，10325476。 以分组为单位对消息进行处理以分组为单位对消息进行处理 每一分组每一分组Yq(q=0,L-1)都经一压缩函数都经一压缩函数HMD5处理。处理。HMD5是算法的核心，其中又有是算法的核心，其中又有4轮处理过程。轮处理过程。 输出输出 消息的消息的L个分组都被处理完后，最后一个个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要。的输出即
49、为产生的消息摘要。9/9/2024509/9/2024519/9/202452HMD5的的4轮处理过程结构一样，但所用的逻辑轮处理过程结构一样，但所用的逻辑函数不同，分别表示为函数不同，分别表示为F、G、H、I。每轮的。每轮的输入为当前处理的消息分组输入为当前处理的消息分组Yq和缓冲区的当前和缓冲区的当前值值A、B、C、D，输出仍放在缓冲区中以产生，输出仍放在缓冲区中以产生新的新的A、B、C、D。每轮处理过程还需加上常数表每轮处理过程还需加上常数表T中四分之一个中四分之一个元素，分别为元素，分别为T116, T1732, T3348, T4964。表。表T有有64个元素，第个元素，第i个元素个
50、元素Ti为为232abs(sin(i)的整数部分，其中的整数部分，其中sin为正弦函为正弦函数，数，i以弧度为单位。由于以弧度为单位。由于abs(sin(i)大于大于0小于小于1，所以，所以Ti可由可由32比特的字表示。比特的字表示。第第4轮的输出再与第轮的输出再与第1轮的输入轮的输入CVq相加，相加相加，相加时将时将CVq看作看作4个个32比特的字，每个字与第比特的字，每个字与第4轮轮输出的对应的字按模输出的对应的字按模232相加，相加的结果即为相加，相加的结果即为压缩函数压缩函数HMD5的输出。的输出。9/9/202453步骤步骤到步骤到步骤的处理过程可总结如下：的处理过程可总结如下：CV
51、0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL 其中其中IV是步骤是步骤所取的缓冲区所取的缓冲区ABCD的初值，的初值，Yq是消息的第是消息的第q个个512比特长的分组，比特长的分组，L是消息经是消息经过步骤过步骤和步骤和步骤处理后的分组数，处理后的分组数，CVq为处理为处理消息的第消息的第q个分组时输入的链接变量（即前一个个分组时输入的链接变量（即前一个压缩函数的输出），压缩函数的输出），RFx为使用基本逻辑函数为使用基本逻辑函数x的轮函数，的轮函数，+为对应字的模为对应字的模232加法，加法，MD为最终为最终的杂凑值。的杂凑值。9/9/20
52、24546.3.2 MD5的压缩函数的压缩函数压缩函数压缩函数HMD5中有中有4轮处理过程，每轮又对轮处理过程，每轮又对缓冲区缓冲区ABCD进行进行16步迭代运算，每一步步迭代运算，每一步的运算形式为的运算形式为ab+CLSs(a+g(b,c,d)+Xk+Ti) 其中其中a、b、c、d为缓冲区的为缓冲区的4个字，运算完个字，运算完成后再右循环一个字，即得这一步迭代的成后再右循环一个字，即得这一步迭代的输出。输出。g是基本逻辑函数是基本逻辑函数F、G 、H、I之一。之一。CLSs是左循环移是左循环移s位位9/9/202455图图图图6.7 6.7 压缩函数中的一步迭代示意图压缩函数中的一步迭代示
53、意图压缩函数中的一步迭代示意图压缩函数中的一步迭代示意图9/9/2024569/9/202457Ti为表为表T中的第中的第i个字，个字，+为模为模232加法。加法。Xk=Mq16+k，即消息第，即消息第q个分组中个分组中的第的第k个字（个字（k=1,16）。）。4轮处理过程中，每轮以不同的次序使用轮处理过程中，每轮以不同的次序使用16个字，其中在第个字，其中在第1轮以字的初始次序使轮以字的初始次序使用。第用。第2轮到第轮到第4轮分别对字的次序轮分别对字的次序i做置做置换后得到一个新次序，然后以新次序使换后得到一个新次序，然后以新次序使用用16个字。个字。3个置换分别为个置换分别为2(i)=(1
54、+5i) mod 163(i)=(5+3i) mod 164(i)=7i mod 169/9/2024584轮处理过程分别使用不同的基本逻辑函数轮处理过程分别使用不同的基本逻辑函数F、G、H、I，每个逻辑函数的输入为，每个逻辑函数的输入为3个个32比特的字，输出是一个比特的字，输出是一个32比特的字，其比特的字，其中的运算为逐比特的逻辑运算，即输出的中的运算为逐比特的逻辑运算，即输出的第第n个比特是个比特是3个输入的第个输入的第n个比特的函数，个比特的函数，其中其中，-，分别是逻辑与、逻辑或、分别是逻辑与、逻辑或、逻辑非和异或运算逻辑非和异或运算9/9/2024599/9/2024609/9/
55、2024616.3.3 MD5的安全性的安全性9/9/2024626.4 安全杂凑算法安全杂凑算法安全杂凑算法安全杂凑算法SHA(Secure Hash Algorithm)由美国由美国NIST设计，于设计，于1993年作年作为联邦信息处理标准（为联邦信息处理标准（FIPS PUB 180）公）公布。布。SHA-0是是SHA的早期版本，的早期版本，SHA-0被公布被公布后，后，NIST很快就发现了它的缺陷，修改后很快就发现了它的缺陷，修改后的版本称为的版本称为SHA-1，简称为，简称为SHA。SHA是基于是基于MD4算法，其结构与算法，其结构与MD4非常非常类似。类似。9/9/2024636.
56、4.1 算法描述算法描述算法的输入为小于算法的输入为小于264比特长的任意消息，比特长的任意消息，分为分为512比特长的分组，输出为比特长的分组，输出为160比特长比特长的消息摘要。的消息摘要。9/9/202464算法的处理过程有以下几步：算法的处理过程有以下几步： 对消息填充对消息填充 与与MD5的步骤的步骤完全相同。完全相同。 附加消息的长度附加消息的长度 与与MD5的步骤的步骤类似，不同类似，不同之处在于以之处在于以big-endian方式表示填充前消息的长方式表示填充前消息的长度。即步骤度。即步骤留出的留出的64比特当作比特当作64比特长的无符比特长的无符号整数。号整数。 对对MD缓冲
57、区初始化缓冲区初始化 算法使用算法使用160比特长的缓比特长的缓冲区存储中间结果和最终杂凑值，缓冲区可表示冲区存储中间结果和最终杂凑值，缓冲区可表示为为5个个32比特长的寄存器比特长的寄存器(A, B, C, D, E)，每个寄，每个寄存器都以存器都以big-endian方式存储数据，其初始值分方式存储数据，其初始值分别为别为A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。9/9/202465 以分组为单位对消息进行处理以分组为单位对消息进行处理 每一分组每一分组Yq都经一压缩函数处理，都经一压缩函数处理，压缩函数由压缩函数由4轮处
58、理过轮处理过程程构成，构成，每一轮又由每一轮又由20步迭代组成步迭代组成。4轮处理轮处理过程结构一样，但所用的基本逻辑函数不同，过程结构一样，但所用的基本逻辑函数不同，分别表示为分别表示为f1,f2,f3,f4每轮的输入为当前处理的每轮的输入为当前处理的消息分组消息分组Yq和缓冲区的当前值和缓冲区的当前值A,B,C,D,E，输，输出仍放在缓冲区以替代出仍放在缓冲区以替代A,B,C,D,E的旧值，每的旧值，每轮处理过程还需加上一个加法常量轮处理过程还需加上一个加法常量Kt，其中，其中0t79表示迭代的步数。表示迭代的步数。80个常量中实际上只个常量中实际上只有有4个不同取值，其中个不同取值，其中
59、 为为x的整数部分。的整数部分。 第第4轮的输出再与第轮的输出再与第1轮的输入轮的输入CVq相加，以产相加，以产生生CVq+1，其中加法是缓冲区，其中加法是缓冲区5个字中的每一个个字中的每一个字与字与CVq中相应的字模中相应的字模232相加。相加。9/9/202466 输出输出 消息的消息的L个分组都被处理完后，最后一个分组都被处理完后，最后一个分组的输出即为个分组的输出即为160比特的消息摘要。比特的消息摘要。步骤步骤到步骤到步骤的处理过程可总结如下：的处理过程可总结如下：CV0=IV;CVq+1=SUM32(CVq,ABCDEq);MD=CVL 其中其中IV是步骤是步骤定义的缓冲区定义的缓
60、冲区ABCDE的初值，的初值，ABCDEq是第是第q个消息分组经最后一轮处理过程个消息分组经最后一轮处理过程处理后的输出，处理后的输出，L是消息（包括填充位和长度是消息（包括填充位和长度字段）的分组数，字段）的分组数，SUM32是对应字的模是对应字的模232加法，加法，MD为最终的摘要值。为最终的摘要值。9/9/2024679/9/2024689/9/2024696.4.2 SHA的压缩函数的压缩函数SHA的压缩函数由的压缩函数由4轮处理过程组成，每轮处理过程组成，每轮处理过程又由对缓冲区轮处理过程又由对缓冲区ABCDE的的20步步迭代运算组成，每一步迭代运算的形式为迭代运算组成，每一步迭代运
61、算的形式为 其中其中A，B，C，D，E为缓冲区的为缓冲区的5个字，个字，t是迭代的步数（是迭代的步数（0t79），），ft(B,C,D)是第是第t步迭代使用的基本逻辑函数，步迭代使用的基本逻辑函数，CLSs为左循为左循环移环移s位，位，Wt是由当前是由当前512比特长的分组导比特长的分组导出的一个出的一个32比特长的字，比特长的字，Kt是加法常量，是加法常量，+是模是模232加法。加法。9/9/202470图图图图6.9 SHA6.9 SHA的压缩函数中一步迭代示意图的压缩函数中一步迭代示意图的压缩函数中一步迭代示意图的压缩函数中一步迭代示意图9/9/202471基本逻辑函数的输入为基本逻辑函
62、数的输入为3个个32比特的字，比特的字，输出是一个输出是一个32比特的字，其中的运算为逐比特的字，其中的运算为逐比特逻辑运算，即输出的第比特逻辑运算，即输出的第n个比特是个比特是3个输入的相应比特的函数。表中个输入的相应比特的函数。表中, ,分别是与、或、非、异或分别是与、或、非、异或4个逻辑运算个逻辑运算9/9/2024729/9/202473下面说明如何由当前的输入分组（下面说明如何由当前的输入分组（下面说明如何由当前的输入分组（下面说明如何由当前的输入分组（512512比特长）比特长）比特长）比特长）导出导出导出导出WWt t（3232比特长）。前比特长）。前比特长）。前比特长）。前16
63、16个值（即个值（即个值（即个值（即WW0 0,W,W1 1,W,W1515）直接取为输入分组的直接取为输入分组的直接取为输入分组的直接取为输入分组的1616个相应的个相应的个相应的个相应的字，其余值（即字，其余值（即字，其余值（即字，其余值（即WW1616,W,W1717,W,W7979）取为取为取为取为与与与与MD5MD5比较，比较，比较，比较，MD5MD5直接用一个消息分组的直接用一个消息分组的直接用一个消息分组的直接用一个消息分组的1616个个个个字作为每步迭代的输入，而字作为每步迭代的输入，而字作为每步迭代的输入，而字作为每步迭代的输入，而SHASHA则将输入分组则将输入分组则将输入
64、分组则将输入分组的的的的1616个字扩展成个字扩展成个字扩展成个字扩展成8080个字以供压缩函数使用，从而个字以供压缩函数使用，从而个字以供压缩函数使用，从而个字以供压缩函数使用，从而使得寻找具有相同压缩值的不同的消息分组更为使得寻找具有相同压缩值的不同的消息分组更为使得寻找具有相同压缩值的不同的消息分组更为使得寻找具有相同压缩值的不同的消息分组更为困难。困难。困难。困难。9/9/202474图图图图6.10 SHA6.10 SHA分组处理所需的分组处理所需的分组处理所需的分组处理所需的8080个字的产生过程个字的产生过程个字的产生过程个字的产生过程9/9/2024756.4.3 SHA与与M
65、D5的比较的比较由于由于SHA与与MD5都是由都是由MD4演化而来，所演化而来，所以两个算法极为相似。以两个算法极为相似。1. 抗穷搜索攻击的强度抗穷搜索攻击的强度由于由于SHA和和MD5的消息摘要长度分别为的消息摘要长度分别为160和和128，所以用穷搜索攻击寻找具有给，所以用穷搜索攻击寻找具有给定消息摘要的消息分别需做定消息摘要的消息分别需做O(2160)和和O(2128)次运算，而用穷搜索攻击找出具有相次运算，而用穷搜索攻击找出具有相同消息摘要的两个不同消息分别需做同消息摘要的两个不同消息分别需做O(280)和和O(264)次运算。因此次运算。因此SHA抗击穷搜抗击穷搜索攻击的强度高于索
66、攻击的强度高于MD5抗击穷搜索攻击的抗击穷搜索攻击的强度。强度。9/9/2024762. 抗击密码分析攻击的强度抗击密码分析攻击的强度由于由于SHA的设计准则未被公开，所以它的设计准则未被公开，所以它抗击密码分析攻击的强度较难判断，似乎抗击密码分析攻击的强度较难判断，似乎高于高于MD5的强度。的强度。3. 速度速度由于两个算法的主要运算都是模由于两个算法的主要运算都是模232加法，加法，因此都易于在因此都易于在32位结构上实现。但比较起位结构上实现。但比较起来来,SHA的迭代步数的迭代步数(80步步)多于多于MD5的迭的迭代步数（代步数（64步），所用的缓冲区（步），所用的缓冲区（160比比特
67、）大于特）大于MD5使用的缓冲区（使用的缓冲区（128比特），比特），因此在相同硬件上实现时，因此在相同硬件上实现时，SHA的速度的速度要比要比MD5的速度慢。的速度慢。9/9/2024774. 简洁与紧致性简洁与紧致性两个算法描述起来都较为简单，实现起两个算法描述起来都较为简单，实现起来也较为简单，都不需要大的程序和代来也较为简单，都不需要大的程序和代换表。换表。5. 数据的存储方式数据的存储方式MD5使用使用little-endian方式，方式，SHA使用使用big-endian方式。两种方式相比看不出哪方式。两种方式相比看不出哪个更具优势，之所以使用两种不同的存个更具优势，之所以使用两种
68、不同的存储方式是因为设计者最初实现各自的算储方式是因为设计者最初实现各自的算法时，使用的机器的存储方式不同。法时，使用的机器的存储方式不同。9/9/2024789/9/2024796.5 HMAC一节中曾介绍过一个一节中曾介绍过一个MAC的例子的例子数数据认证算法，该算法反映了传统上构造据认证算法，该算法反映了传统上构造MAC最为普遍使用的方法，即基于分组最为普遍使用的方法，即基于分组密码的构造方法。但近年来研究构造密码的构造方法。但近年来研究构造MAC的兴趣已转移到基于密码杂凑函数的兴趣已转移到基于密码杂凑函数的构造方法，这是因为：的构造方法，这是因为：密码杂凑函数密码杂凑函数(如如MD5、
69、SHA)的软件实现快的软件实现快于分组密码于分组密码(如如DES)的软件实现；的软件实现； 密码杂凑函数的库代码来源广泛；密码杂凑函数的库代码来源广泛； 密码杂凑函数没有出口限制，而分组密码即密码杂凑函数没有出口限制，而分组密码即使用于使用于MAC也有出口限制。也有出口限制。9/9/202480杂凑函数并不是为用于杂凑函数并不是为用于MAC而设计的，由而设计的，由于杂凑函数不使用密钥，因此不能直接用于杂凑函数不使用密钥，因此不能直接用于于MAC。目前已提出了很多将杂凑函数用于构造目前已提出了很多将杂凑函数用于构造MAC的方法，其中的方法，其中HMAC就是其中之一，就是其中之一，已作为已作为RF
70、C2104被公布，并在被公布，并在IPSec和其和其他网络协议他网络协议(如如SSL)中得以应用。中得以应用。9/9/2024816.5.1 HMAC的设计目标的设计目标RFC2104列举了列举了HMAC的以下设计目标：的以下设计目标： 可不经修改而使用现有的杂凑函数，特别是那可不经修改而使用现有的杂凑函数，特别是那些易于软件实现的、源代码可方便获取且免费些易于软件实现的、源代码可方便获取且免费使用的杂凑函数。使用的杂凑函数。 其中镶嵌的杂凑函数可易于替换为更快或更安其中镶嵌的杂凑函数可易于替换为更快或更安全的杂凑函数。全的杂凑函数。 保持镶嵌的杂凑函数的最初性能，不因用于保持镶嵌的杂凑函数的
71、最初性能，不因用于HMAC而使其性能降低。而使其性能降低。 以简单方式使用和处理密钥。以简单方式使用和处理密钥。 在对镶嵌的杂凑函数合理假设的基础上，易于在对镶嵌的杂凑函数合理假设的基础上，易于分析分析HMAC用于认证时的密码强度。用于认证时的密码强度。9/9/202482其中前两个目标是其中前两个目标是HMAC被公众普遍接受的主要被公众普遍接受的主要原因，这两个目标是将杂凑函数当作一个黑盒使原因，这两个目标是将杂凑函数当作一个黑盒使用，这种方式有两个优点用，这种方式有两个优点: 第一，杂凑函数的实现可作为实现第一，杂凑函数的实现可作为实现HMAC的一个模块，的一个模块，这样一来，这样一来，H
72、MAC代码中很大一块就可事先准备好，代码中很大一块就可事先准备好，无需修改就可使用；无需修改就可使用；第二，如果第二，如果HMAC要求使用更快或更安全的杂凑函数，要求使用更快或更安全的杂凑函数，则只需用新模块代替旧模块，例如用实现则只需用新模块代替旧模块，例如用实现SHA的模块的模块代替代替MD5的模块。的模块。最后一条设计目标则是最后一条设计目标则是HMAC优于其他基于杂凑优于其他基于杂凑函数的函数的MAC的一个主要方面，的一个主要方面，HMAC在其镶嵌在其镶嵌的杂凑函数具有合理密码强度的假设下，可证明的杂凑函数具有合理密码强度的假设下，可证明是安全的。是安全的。9/9/2024836.5.
73、2 算法描述算法描述图图6.11是是HMAC算法的运行框图，其中算法的运行框图，其中H为嵌为嵌入的杂凑函数入的杂凑函数(如如MD5、SHA)，M为为HMAC的的输入消息输入消息(包括杂凑函数所要求的填充位包括杂凑函数所要求的填充位)，Yi(0iL-1)是是M的第的第i个分组，个分组，L是是M的分组数，的分组数，b是一个分组中的比特数，是一个分组中的比特数，n为由嵌入的杂凑函为由嵌入的杂凑函数所产生的杂凑值的长度，数所产生的杂凑值的长度，K为密钥，如果密为密钥，如果密钥长度大于钥长度大于b，则将密钥输入到杂凑函数中产，则将密钥输入到杂凑函数中产生一个生一个n比特长的密钥，比特长的密钥，K+是左边
74、经填充是左边经填充0后后的的K，K+的长度为的长度为b比特，比特，ipad为为b/8个个00110110，opad为为b/8个个01011010。9/9/2024849/9/202485算法的输出可如下表示算法的输出可如下表示:算法的运行过程可描述如下：算法的运行过程可描述如下： K的左边填充的左边填充0以产生一个以产生一个b比特长的比特长的K+ （例（例如如K的长为的长为160比特，比特，b=512，则需填充，则需填充44个零个零字节字节0x00）。）。 K+与与ipad 逐比特异或以产生逐比特异或以产生b比特的分组比特的分组Si。 将将M链接到链接到Si后。后。 将将H作用于步骤作用于步骤
75、产生的数据流。产生的数据流。 K+与与opad逐比特异或逐比特异或,以产生以产生b比特长的分组比特长的分组S0。9/9/202486 将步骤将步骤得到的杂凑值链接在得到的杂凑值链接在S0后。后。 将将H作用于步骤作用于步骤产生的数据流并输出最终结产生的数据流并输出最终结果。果。注意，注意，K+与与ipad逐比特异或以及逐比特异或以及K+与与opad逐比逐比特异或的结果是将特异或的结果是将K中的一半比特取反，但两中的一半比特取反，但两次取反的比特的位置不同。而次取反的比特的位置不同。而Si和和S0通过杂凑通过杂凑函数中压缩函数的处理，则相当于以伪随机方函数中压缩函数的处理，则相当于以伪随机方式从
76、式从K产生两个密钥。产生两个密钥。9/9/202487在实现在实现在实现在实现HMACHMAC时，可预先求出下面两个量时，可预先求出下面两个量时，可预先求出下面两个量时，可预先求出下面两个量其中其中其中其中f(cvf(cv，block)block)是杂凑函数中的压缩函数，其输是杂凑函数中的压缩函数，其输是杂凑函数中的压缩函数，其输是杂凑函数中的压缩函数，其输入是入是入是入是n n比特的链接变量和比特的链接变量和比特的链接变量和比特的链接变量和b b比特的分组，输出是比特的分组，输出是比特的分组，输出是比特的分组，输出是n n比比比比特的链接变量。这两个量的预先计算只在每次更改特的链接变量。这两
77、个量的预先计算只在每次更改特的链接变量。这两个量的预先计算只在每次更改特的链接变量。这两个量的预先计算只在每次更改密钥时才需进行。事实上这两个预先计算的量用于密钥时才需进行。事实上这两个预先计算的量用于密钥时才需进行。事实上这两个预先计算的量用于密钥时才需进行。事实上这两个预先计算的量用于作为杂凑函数的初值作为杂凑函数的初值作为杂凑函数的初值作为杂凑函数的初值IVIV。9/9/202488图图图图6.12 HMAC6.12 HMAC的有效实现的有效实现的有效实现的有效实现9/9/2024896.5.3 HMAC的安全性的安全性基于密码杂凑函数构造的基于密码杂凑函数构造的MAC的安全性取的安全性
78、取决于镶嵌的杂凑函数的安全性，而决于镶嵌的杂凑函数的安全性，而HMAC最吸引人的地方是它的设计者已经证明了最吸引人的地方是它的设计者已经证明了算法的强度和嵌入的杂凑函数的强度之间算法的强度和嵌入的杂凑函数的强度之间的确切关系，证明了对的确切关系，证明了对HMAC的攻击等价的攻击等价于对内嵌杂凑函数的下述两种攻击之一：于对内嵌杂凑函数的下述两种攻击之一：攻击者能够计算压缩函数的一个输出，即使攻击者能够计算压缩函数的一个输出，即使IV是随机的和秘密的。是随机的和秘密的。攻击者能够找出杂凑函数的碰撞，即使攻击者能够找出杂凑函数的碰撞，即使IV是随是随机的和秘密的。机的和秘密的。9/9/202490在
79、第一种攻击中，可将压缩函数视为与杂在第一种攻击中，可将压缩函数视为与杂凑函数等价，而杂凑函数的凑函数等价，而杂凑函数的n比特长比特长IV可可视为视为HMAC的密钥。对这一杂凑函数的攻的密钥。对这一杂凑函数的攻击可通过对密钥的穷搜索来进行，也可通击可通过对密钥的穷搜索来进行，也可通过第过第类生日攻击来实施，通过对密钥的类生日攻击来实施，通过对密钥的穷搜索攻击的复杂度为穷搜索攻击的复杂度为O（2n），通过第），通过第类生日攻击又可归结为上述第二种攻击。类生日攻击又可归结为上述第二种攻击。9/9/202491第二种攻击指攻击者寻找具有相同杂凑值的两第二种攻击指攻击者寻找具有相同杂凑值的两个消息，因此
80、就是第个消息，因此就是第类生日攻击。对杂凑值类生日攻击。对杂凑值长度为长度为n的杂凑函数来说，攻击的复杂度为的杂凑函数来说，攻击的复杂度为O(2n/2)。因此第二种攻击对。因此第二种攻击对MD5的攻击复杂度的攻击复杂度为为O(264)，就现在的技术来说，这种攻击是可，就现在的技术来说，这种攻击是可行的。行的。但这是否意味着但这是否意味着MD5不适合用于不适合用于HMAC？回？回答是否定的，原因如下：攻击者在攻击答是否定的，原因如下：攻击者在攻击MD5时，可选择任何消息集合后脱线寻找碰撞。时，可选择任何消息集合后脱线寻找碰撞。由于攻击者知道杂凑算法和默认的由于攻击者知道杂凑算法和默认的IV，因此
81、，因此能为自己产生的每个消息求出杂凑值。然而，能为自己产生的每个消息求出杂凑值。然而，在攻击在攻击HMAC时，由于攻击者不知道密钥时，由于攻击者不知道密钥K，从而不能脱线产生消息和认证码对。从而不能脱线产生消息和认证码对。9/9/202492所以攻击者必须得到所以攻击者必须得到HMAC在同一密钥在同一密钥下产生的一系列消息，并对得到的消息下产生的一系列消息，并对得到的消息序列进行攻击。对长序列进行攻击。对长128比特的杂凑值来比特的杂凑值来说，需要得到用同一密钥产生的说，需要得到用同一密钥产生的264个分个分组（组（273比特）。在比特）。在1Gbit/s的链路上，需的链路上，需250000年，因此年，因此MD5完全适合于完全适合于HMAC，而且就速度而言，而且就速度而言，MD5要快于要快于SHA作作为内嵌杂凑函数的为内嵌杂凑函数的HMAC。9/9/202493
