资源描述
第第6章章 消息认证和杂凑算法消息认证和杂凑算法6.1 消息认证码消息认证码6.2 杂凑函数杂凑函数6.3 MD5杂凑算法杂凑算法6.4 安全杂凑算法安全杂凑算法SHA6.5 HMAC算法算法引言引言信息安全所面临的基本攻击类型信息安全所面临的基本攻击类型括被动攻击括被动攻击获取消息的内容获取消息的内容业务流分析业务流分析主动攻击主动攻击假冒假冒重放重放消息的篡改消息的篡改业务拒绝业务拒绝加密消息认证对认证的要求对认证的要求l伪装Masquerade，欺诈源向网络中插入一条消息l内容篡改Content modification，对消息内容的修改l顺序篡改Sequence modification，对消息顺序的修改l计时篡改Timing modification，对消息的延时和重放l信源抵赖Source repudiation,发送方否认发送过某消息l信宿抵赖Destination repudiation，接收方否认接收过某消息消息认证的概念消息认证的概念消息认证是一个过程，用以验证接收消息的消息认证是一个过程，用以验证接收消息的真实性真实性：消息确是由它所声称的实体发来的：消息确是由它所声称的实体发来的完整性完整性：消息未被篡改、插入、删除：消息未被篡改、插入、删除顺序性和时间性顺序性和时间性：未重排、重放、延迟：未重排、重放、延迟不可否认性不可否认性：防止通信双方中的某一方对所：防止通信双方中的某一方对所传输消息的否认。传输消息的否认。实现消息的不可否认性可通过数字签名，数字实现消息的不可否认性可通过数字签名，数字签名也是一种认证技术签名也是一种认证技术认证符认证符(认证码认证码)消息认证和数字签名都需认证码消息认证和数字签名都需认证码认证符是用于认证消息的数值，它的产生认证符是用于认证消息的数值，它的产生方法又分为两种：方法又分为两种：消息认证码消息认证码MAC（message authentication code）杂凑函数（杂凑函数（hash function）消息认证码：指消息消息认证码：指消息被一密钥控制的公开函数被一密钥控制的公开函数作用后产生的作用后产生的、用作认证符的用作认证符的、固定长度固定长度的数的数值，也称为密码校验和值，也称为密码校验和MAC函数与加密算法类似，不同之处为函数与加密算法类似，不同之处为MAC函函数不必是可逆的，因此与加密算法相比更不易数不必是可逆的，因此与加密算法相比更不易被攻破被攻破MAC不提供数字签名，因为双方共享密钥不提供数字签名，因为双方共享密钥6.1 消息认证码消息认证码 6.1.1 消息认证码的定义及使用方式消息认证码的定义及使用方式MAC认证需要通信双方认证需要通信双方A和和B共享一密钥共享一密钥K。设设A欲发送给欲发送给B的消息是的消息是M，A首先计算首先计算MAC=CK(M)，其中其中CK()是密钥控制的公开函是密钥控制的公开函数，然后向数，然后向B发送发送MMAC，B收到后做与收到后做与A相同相同的计算，求得一新的计算，求得一新MAC，并与收到的并与收到的MAC做比做比较。较。如果仅收发双方知道如果仅收发双方知道K，且且B计算得到的计算得到的MAC与接与接收到的收到的MAC一致，则这一系统就实现了以下功能：一致，则这一系统就实现了以下功能：接收方相信发送方发来的消息未被篡改接收方相信发送方发来的消息未被篡改 接收方相信发送方不是冒充的接收方相信发送方不是冒充的MAC的基本使用方式的基本使用方式6.1.2 MAC函数函数MAC函数一般都为多到一映射函数一般都为多到一映射如果产生如果产生n比特长的比特长的MAC，则函数的取值范围则函数的取值范围即为即为2n个可能的个可能的MACMAC函数输入的可能的消息个数函数输入的可能的消息个数N2n如果函数所用的密钥为如果函数所用的密钥为k比特，则可能的密钥比特，则可能的密钥个数为个数为2k如果系统不考虑保密性，即敌手能获取明文消如果系统不考虑保密性，即敌手能获取明文消息和相应的息和相应的MAC，敌手使用穷搜索攻击来获取敌手使用穷搜索攻击来获取MAC函数所使用的密钥的过程：函数所使用的密钥的过程：假定假定kn，且敌手已得到且敌手已得到M1和和MAC1，其中其中MAC1=CK1(M1)，敌手对所有可能的密钥值敌手对所有可能的密钥值Ki求求MACi=CKi(M1)，直到找到某个直到找到某个Ki使得使得MACi=MAC1由于不同的密钥个数为由于不同的密钥个数为2k，因此将产生因此将产生2k个个MAC，但但其中仅有其中仅有2n个不同，由于个不同，由于2k2n，所以有很多密钥（平所以有很多密钥（平均有均有2k/2n=2k-n个）都可产生出正确的个）都可产生出正确的MAC1，而敌手而敌手无法知道进行通信的两个用户用的是哪一个密钥，还无法知道进行通信的两个用户用的是哪一个密钥，还必须按以下方式重复上述攻击：必须按以下方式重复上述攻击：如果系统不考虑保密性，即敌手能获取明文消如果系统不考虑保密性，即敌手能获取明文消息和相应的息和相应的MAC，敌手使用穷搜索攻击来获取敌手使用穷搜索攻击来获取MAC函数所使用的密钥的过程：函数所使用的密钥的过程：第第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轮即可找出正确的密钥。轮即可找出正确的密钥。如果系统不考虑保密性，即敌手能获取明文消如果系统不考虑保密性，即敌手能获取明文消息和相应的息和相应的MAC，敌手使用穷搜索攻击来获取敌手使用穷搜索攻击来获取MAC函数所使用的密钥的过程：函数所使用的密钥的过程：如果密钥长度如果密钥长度k小于小于MAC的长度的长度n，则第，则第1轮就有可能轮就有可能找出正确的密钥，也有可能找出多个可能的密钥，如找出正确的密钥，也有可能找出多个可能的密钥，如果是后者，则仍需执行第果是后者，则仍需执行第2轮搜索轮搜索对消息认证码的穷搜索攻击比对使用相同长度密钥的对消息认证码的穷搜索攻击比对使用相同长度密钥的加密算法的穷搜索攻击的代价还要大加密算法的穷搜索攻击的代价还要大不寻找不寻找MAC密钥的认证攻击密钥的认证攻击设设M=X1X2Xm是由是由64比特长的分组比特长的分组Xi(i=1,m)链接得到的，其消息认证码由以下方式得到：链接得到的，其消息认证码由以下方式得到：加密算法是加密算法是ECB模式的模式的DES。敌手可用以下方式攻敌手可用以下方式攻击系统：击系统：将将X1到到Xm-1分别用自己选取的分别用自己选取的Y1到到Ym-1替替换，求出换，求出 Ym=Y1Y2Ym-1(M)并用并用Ym替换替换Xm，伪造一新消息，伪造一新消息 M=Y1Ym-1Ym则则M的的MAC与原消息与原消息M的的MAC相同相同MAC函数应满足的条件：函数应满足的条件：如果敌手得到如果敌手得到M和和CK(M)，则构造一满足则构造一满足CK(M)=CK(M)的新消息的新消息M在计算上是不可行的在计算上是不可行的 CK(M)在以下意义下是均匀分布的：随机选取两在以下意义下是均匀分布的：随机选取两个消息个消息M、M，PCK(M)=CK(M)=2-n，其中其中n为为MAC的长的长 若若M是是M的某个变换，即的某个变换，即M=f(M)，例如例如f为插为插入一个或多个比特，那么入一个或多个比特，那么PCK(M)=CK(M)=2-nData Authentication Alogrithm最为广泛使用的消息认证之一最为广泛使用的消息认证之一FIPS PUB 113标准标准ANSI X9.17标准标准算法基于算法基于CBC模式的模式的DES算法算法其初始向量其初始向量IV取为零向量取为零向量需被认证的数据被分为需被认证的数据被分为64比特长的分组比特长的分组 D1，D2，DN 其中最后一个分组不够其中最后一个分组不够64比特的话，可在其右比特的话，可在其右边填充一些边填充一些06.1.3 数据认证算法数据认证算法(DAA)MAC值或者取为值或者取为ON，或者取为，或者取为ON的最左的最左M个比特，个比特，其中其中16M64。6.1.3 数据认证算法数据认证算法(DAA)杂凑函数杂凑函数H是一公开函数，用于将任意长的消息是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值映射为较短的、固定长度的一个值H(M)，作为认作为认证符，称函数值证符，称函数值H(M)为为杂凑值杂凑值、杂凑码杂凑码或或消息摘消息摘要要。杂凑码是消息中所有比特的函数，因此提供了一种杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。比特都会使杂凑码发生改变。6.2 杂凑函数杂凑函数 6.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式6.2 杂凑函数杂凑函数 6.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式6.2 杂凑函数杂凑函数 6.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式6.2 杂凑函数杂凑函数 6.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式用杂凑函数提供消息认证的基本使用方式（用杂凑函数提供消息认证的基本使用方式（1）消息与杂凑码链接后用单钥加密算法加密。消息与杂凑码链接后用单钥加密算法加密。所用密钥仅为收发双方所用密钥仅为收发双方A、B共享，因此可保证共享，因此可保证消息的确来自消息的确来自A并且未被篡改，即提供并且未被篡改，即提供认证认证由于消息和杂凑码都被加密，这种方式还提供由于消息和杂凑码都被加密，这种方式还提供了了机密性机密性用杂凑函数提供消息认证的基本使用方式（用杂凑函数提供消息认证的基本使用方式（2）用单钥加密算法仅对杂凑码加密用单钥加密算法仅对杂凑码加密只提供只提供认证认证用于不要求保密性的情况下，可减少处理负担用于不要求保密性的情况下，可减少处理负担用杂凑函数提供消息认证的基本使用方式（用杂凑函数提供消息认证的基本使用方式（3）用公钥加密算法和发送方的秘密钥加密杂凑码用公钥加密算法和发送方的秘密钥加密杂凑码提供提供认证认证提供提供数字签名数字签名只有发送方能产生加密的杂凑码只有发送方能产生加密的杂凑码用杂凑函数提供消息认证的基本使用方式（用杂凑函数提供消息认证的基本使用方式（4）消息的杂凑值用公钥加密算法和发送方的秘密消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接后的结果用单钥加密后与消息链接，再对链接后的结果用单钥加密算法加密钥加密算法加密提供提供保密性、认证和数字签名保密性、认证和数字签名用杂凑函数提供消息认证的基本使用方式（用杂凑函数提供消息认证的基本使用方式（5）要求通信双方共享一个秘密值要求通信双方共享一个秘密值S，A计算消息计算消息M和秘密值和秘密值S链接在一起的杂凑值，并将此杂凑值链接在一起的杂凑值，并将此杂凑值附加到附加到M后发往后发往B。因因B也有也有S，所以可重新计所以可重新计算杂凑值以对消息进行认证。算杂凑值以对消息进行认证。秘密值秘密值S本身未被发送，敌手无法对截获的消息本身未被发送，敌手无法对截获的消息加以篡改，也无法产生假消息。加以篡改，也无法产生假消息。只提供只提供认证认证用杂凑函数提供消息认证的基本使用方式（用杂凑函数提供消息认证的基本使用方式（6）在方式在方式(5)的基础上，将消息与杂凑值链接以后的基础上，将消息与杂凑值链接以后再增加单钥加密运算再增加单钥加密运算即可提供即可提供认证认证，又可提供，又可提供机密性机密性用杂凑函数提供消息认证的基本使用方式：总结用杂凑函数提供消息认证的基本使用方式：总结由于加密运算的速度较慢，代价较高，而且很多加密由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要求保密性的情况下，算法还受到专利保护，因此在不要求保密性的情况下，方式方式(2)和和(3)将比其他方式更具优势。将比其他方式更具优势。1.公开，不需要密钥公开，不需要密钥2.可以应用于任意大小的数据块，产生固定长度的输可以应用于任意大小的数据块，产生固定长度的输出出3.对任意给定的明文对任意给定的明文x，计算，计算H(x)容易，可由硬件或容易，可由硬件或软件实现软件实现4.单向性单向性：对任意给定的散列码：对任意给定的散列码h，找到满足，找到满足H(x)=h的的x，在计算上不可行，又称，在计算上不可行，又称Peimage Resistance5.抗弱碰撞性抗弱碰撞性：对任何给定的分组：对任何给定的分组x，找到满足，找到满足yx且且H(x)=H(y)的的y，在计算上不可行，在计算上不可行6.抗强碰撞性抗强碰撞性：找到任何满足：找到任何满足H(x)=H(y)的偶的偶对(x,y)，在计算上不可行在计算上不可行6.2.2 杂凑函数应满足的条件杂凑函数应满足的条件以上以上6个条件中，前个条件中，前3个是杂凑函数能用于消息认证个是杂凑函数能用于消息认证的基本要求的基本要求第第4个条件（即单向性）则对使用秘密值的认证技个条件（即单向性）则对使用秘密值的认证技术术(见图见图6.3(e)极为重要。假如杂凑函数不具有单向极为重要。假如杂凑函数不具有单向性，则攻击者截获性，则攻击者截获M和和C=H(SM)后，求后，求C的逆的逆SM，就可求出秘密值就可求出秘密值S。第第5个条件使得敌手无法在已知某个消息时，找到个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。这一性质用与该消息具有相同杂凑值的另一消息。这一性质用于杂凑值被加密情况时于杂凑值被加密情况时(见图见图6.3(b)和图和图6.3(c)防止防止敌手的伪造敌手的伪造第第6个条件用于防范个条件用于防范“生日攻击生日攻击”6.2.2 杂凑函数应满足的条件杂凑函数应满足的条件若试图伪造明文若试图伪造明文M，即要找到，即要找到M M，但，但满足满足H(M)=H(M)，到底需要尝试多少明文才能找到这，到底需要尝试多少明文才能找到这个对应的个对应的M？Rabin的方法（第一类生日攻击）的方法（第一类生日攻击）若一个函数可能有若一个函数可能有n个函数值，且已知一个函数值个函数值，且已知一个函数值h(x)，任选，任选k个任意数作为函数输入值，问：个任意数作为函数输入值，问：k必必须多大才能保证至少找到一个输入值须多大才能保证至少找到一个输入值y，且，且h(x)=h(y)的概率大于的概率大于1/2？当当kn/2时，这个概率将超过时，这个概率将超过1/26.2.3 生日攻击生日攻击生日悖论（第二类生日攻击）生日悖论（第二类生日攻击）生日悖论是考虑这样一个问题：在生日悖论是考虑这样一个问题：在k个人中至少有个人中至少有两个人的生日相同的概率大于两个人的生日相同的概率大于0.5时，时，k至少多大？至少多大？当当k=23时，时，P(365,23)=0.5073，当当k=100时，时，P(365,100)=0.9999997将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在1到到n之间之间均匀分布的整数型随机变量，若该变量的均匀分布的整数型随机变量，若该变量的k个取值个取值中至少有两个取值相同的概率大于中至少有两个取值相同的概率大于0.5，则，则k至少多至少多大？大？与上类似，与上类似，令令P(n,k)0.5，可得可得 。若取若取n=365，则则 。基于生日悖论的第二类生日攻击基于生日悖论的第二类生日攻击生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数H有有2m个可个可能的输出（即输出长能的输出（即输出长m比特），如果比特），如果H的的k个随机输个随机输入中至少有两个产生相同输出的概率大于入中至少有两个产生相同输出的概率大于0.5，则，则 。第第类生日攻击可按以下方式进行：类生日攻击可按以下方式进行：设用户将用图设用户将用图6.3(c)所示的方式发送消息，即所示的方式发送消息，即A用自己的秘密钥对消息的杂凑值加密，加密结果作用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签名，连同明文消息一起发往接收者。为对消息的签名，连同明文消息一起发往接收者。敌手对敌手对A发送的消息发送的消息M产生出产生出2m/2个变形的消息，个变形的消息，每个变形的消息本质上的含义与原消息相同，同时每个变形的消息本质上的含义与原消息相同，同时敌手还准备一个假冒的消息敌手还准备一个假冒的消息M，并对假冒的消息并对假冒的消息产生出产生出2m/2个变形的消息。个变形的消息。敌手在产生的两个消息集合中，找出杂凑值相敌手在产生的两个消息集合中，找出杂凑值相同的一对消息同的一对消息,，由上述讨论可知敌手成功由上述讨论可知敌手成功的概率大于的概率大于0.5。如果不成功，则重新产生一个假冒。如果不成功，则重新产生一个假冒的消息，并产生的消息，并产生2m/2个变形，直到找到杂凑值相同个变形，直到找到杂凑值相同的一对消息为止。的一对消息为止。敌手将敌手将 提交给提交给A请求签名，由于请求签名，由于 与与 的杂的杂凑值相同，所以可将凑值相同，所以可将A对对 的签名当作对的签名当作对 的签的签名，将此签名连同名，将此签名连同 一起发给意欲的接收者。一起发给意欲的接收者。上述攻击中如果杂凑值的长为上述攻击中如果杂凑值的长为64比特，则敌手攻击比特，则敌手攻击成功所需的时间复杂度为成功所需的时间复杂度为O(232)。目前使用的大多数杂凑函数如目前使用的大多数杂凑函数如MD5、SHA，其结构其结构都是迭代型的都是迭代型的其中函数的输入其中函数的输入M被分为被分为L个分组个分组Y0,Y1,YL-1，每每一个分组的长度为一个分组的长度为b比特，最后一个分组的长度不比特，最后一个分组的长度不够的话，需对其做填充。够的话，需对其做填充。6.2.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构CV0=IV=n比特长的初值；比特长的初值；CVi=f(CVi-1,Yi-1)；1iL；H(M)=CVLMerkleDamgrd 常用的常用的HASH函数函数常用的常用的HASH函数函数由由Ron Rivest于于1990年年10月作为月作为RFC提出提出1992年年4月公布的月公布的MD4的改进（的改进（RFC 1320，1321）称为称为MD5。算法的输入为任意长的消息，分为算法的输入为任意长的消息，分为512比特长的比特长的分组，输出为分组，输出为128比特的消息摘要。比特的消息摘要。6.3 MD5杂凑算法杂凑算法6.3 MD5杂凑算法杂凑算法6.3.1 MD5算法描述算法描述MD5处理步骤处理步骤消息填充消息填充对消息填充对消息填充，使得其比特长在模对消息填充对消息填充，使得其比特长在模512下为下为448，即填充后消息的长度为，即填充后消息的长度为512的某一倍的某一倍数减数减64，留出的，留出的64比特备第比特备第2步使用。步使用。即使消息长度已满足要求，仍需填充。例如，即使消息长度已满足要求，仍需填充。例如，消息长为消息长为448比特，则需填充比特，则需填充512比特，使其长比特，使其长度变为度变为960，因此填充的比特数大于等于，因此填充的比特数大于等于1而小而小于等于于等于512。填充方式是固定的，即第填充方式是固定的，即第1位为位为1，其后各位皆，其后各位皆为为0。MD5处理步骤处理步骤附加消息长度附加消息长度用步骤用步骤留出的留出的64比特以比特以little-endian方式来表方式来表示消息被填充前的长度。如果消息长度大于示消息被填充前的长度。如果消息长度大于264，则以，则以264为模数取模。为模数取模。Little-endian方式是指按数据的最低有效字节方式是指按数据的最低有效字节（byte）（）（或最低有效位）优先的顺序存储数或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于据，即将最低有效字节（或最低有效位）存于低地址字节（或位）。相反的存储方式称为低地址字节（或位）。相反的存储方式称为big-endian方式。方式。前两步执行完后，消息的长度为前两步执行完后，消息的长度为512的倍数（设为的倍数（设为L倍），则可将消息表示为分组长为倍），则可将消息表示为分组长为512的一系列分的一系列分组组Y0，Y1，YL-1，而每一分组又可表示为而每一分组又可表示为16个个32比特长的字，这样消息中的总字数为比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为因此消息又可按字表示为M0,N-1。MD5处理步骤处理步骤对对MD缓冲区初始化缓冲区初始化算法使用算法使用128比特长的缓冲区以存储中间结果和比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为最终杂凑值，缓冲区可表示为4个个32比特长的寄比特长的寄存器（存器（A，B，C，D），），每个寄存器都以每个寄存器都以little endian方式存储数据，其初值取为（以存储方方式存储数据，其初值取为（以存储方式）式）A=01234567 A=01234567 B=89ABCDEF B=89ABCDEF C=FEDCBA98 C=FEDCBA98 D=76543210 D=76543210实际上为实际上为67452301，EFCDAB89，98BADCFE，10325476。MD5处理步骤处理步骤 对每一分组进行对每一分组进行HMD5处理处理以分组为单位对消息进行处理每一分组以分组为单位对消息进行处理每一分组Yq(q=0,L-1)都经一压缩函数都经一压缩函数HMD5处理。处理。HMD5是是算法的核心，包括算法的核心，包括4轮处理过程轮处理过程MD5处理步骤处理步骤产生消息摘要产生消息摘要输出消息的输出消息的L个分组都被处理完后，最后一个个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要。的输出即为产生的消息摘要。HMD5的的4轮处理过程结构一样，但所用的逻辑函轮处理过程结构一样，但所用的逻辑函数不同，分别表示为数不同，分别表示为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)的整数部分。的整数部分。第第4轮的输出再与第轮的输出再与第1轮的输入轮的输入CVq相加，相加时相加，相加时将将CVq看作看作4个个32比特的字，每个字与第比特的字，每个字与第4轮输出轮输出的对应的字按模的对应的字按模232相加，相加的结果即为压缩相加，相加的结果即为压缩函数函数HMD5的输出的输出步骤步骤到步骤到步骤的处理过程可总结如下：的处理过程可总结如下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL其中：其中：IV是步骤是步骤所取的缓冲区所取的缓冲区ABCD的初值的初值Yq是消息的第是消息的第q个个512比特长的分组比特长的分组L是消息经过步骤是消息经过步骤和步骤和步骤处理后的分组数处理后的分组数CVq为处理消息的第为处理消息的第q个分组时输入的链接变量（即个分组时输入的链接变量（即前一个压缩函数的输出）前一个压缩函数的输出）RFx为使用基本逻辑函数为使用基本逻辑函数x的轮函数的轮函数+为对应字的模为对应字的模232加法加法MD为最终的杂凑值。为最终的杂凑值。6.3.2 MD5的压缩函数的压缩函数HMD5压缩函数压缩函数HMD5中中有有4轮处理过程轮处理过程每轮又对缓冲区每轮又对缓冲区ABCD进行进行16步步迭代运算，每一迭代运算，每一步的运算形式为步的运算形式为ab+CLSs(a+g(b,c,d)+Xk+Ti)运算完成后再右循环一个字，即得这一步迭代的输出运算完成后再右循环一个字，即得这一步迭代的输出ab+CLSs(a+g(b,c,d)+Xk+Ti)a、b、c、d为缓冲区的为缓冲区的4个字个字g是基本逻辑函数是基本逻辑函数F、G、H、I之一之一CLSs是左循环移是左循环移s位，位，s的取值由表的取值由表6.2给出给出Ti为表为表T中的第中的第i个字个字+为模为模232加法加法Xk=Mq16+k，即消息第即消息第q个分组中的第个分组中的第k个字个字(k=1,16)。4轮处理过程中，每轮以不同的次序使用轮处理过程中，每轮以不同的次序使用16个字，其中在第个字，其中在第1轮以字的初始次序使用。第轮以字的初始次序使用。第2轮到第轮到第4轮轮分别对字的次序分别对字的次序i做置换后得到一个新次序，然后以新次序做置换后得到一个新次序，然后以新次序使用使用16个字。个字。3个置换分别为个置换分别为2(i)=(1+5i)mod 163(i)=(5+3i)mod 164(i)=7i mod 166.3.2 MD5的压缩函数的压缩函数4轮处理过程分别使用不同的基本逻辑函数轮处理过程分别使用不同的基本逻辑函数F、G、H、I，每个逻辑函数的输入为每个逻辑函数的输入为3个个32比特的字，输比特的字，输出是一个出是一个32比特的字，其中的运算为逐比特的逻辑比特的字，其中的运算为逐比特的逻辑运算，即输出的第运算，即输出的第n个比特是个比特是3个输入的第个输入的第n个比特个比特的函数的函数轮表 示定 义1F(x,y,z)(xy)(x-1z)2G(x,y,z)(xz)(yz-1)3H(x,y,z)xyz4I(x,y,z)y(xz-1)6.3.3 MD5的安全性的安全性MD5杂凑码中的每一个比特是所有输入比特的杂凑码中的每一个比特是所有输入比特的函数，因此获得了很好的混淆效果，从而使得函数，因此获得了很好的混淆效果，从而使得不可能随机选择两个具有相同杂凑值的消息。不可能随机选择两个具有相同杂凑值的消息。Rivest猜想作为猜想作为128比特长的杂凑值来说，比特长的杂凑值来说，MD5的强度达到了最大的强度达到了最大找出具有相同杂凑值的两个消息需执行找出具有相同杂凑值的两个消息需执行O(264)次运算次运算寻找具有给定杂凑值的一个消息需要执行寻找具有给定杂凑值的一个消息需要执行O(2128)次运算。次运算。6.3.3 MD5的安全性的安全性MD5易受第易受第类生日攻击的威胁类生日攻击的威胁安全杂凑算法安全杂凑算法(secure hash algorithm,SHA)由美国由美国NIST设计，于设计，于1993年作为联邦信息处理标准年作为联邦信息处理标准（FIPS PUB 180）公布。公布。SHA是基于是基于MD4的算法，的算法，其结构与其结构与MD4非常类似。非常类似。SHA的最新国际标准：的最新国际标准：FIPS PUB 180-46.4 安全杂凑算法安全杂凑算法SHA-1算法的输入为小于算法的输入为小于264比特长的任意消息，分比特长的任意消息，分为为512比特长的分组，输出为比特长的分组，输出为160比特长的消息摘要。比特长的消息摘要。算法的框图与算法的框图与MD5一样，但一样，但HASH值的长度和链接值的长度和链接变量的长度为变量的长度为160比特。比特。6.4.1 SHA-1算法描述算法描述SHA-1算法的处理过程有以下几步：算法的处理过程有以下几步：消息填充消息填充：与：与MD5的步骤的步骤完全相同。完全相同。附加消息长度附加消息长度：与：与MD5的步骤的步骤类似，不同之处类似，不同之处在于以在于以big-endian方式表示填充前消息的长度。即方式表示填充前消息的长度。即步骤步骤留出的留出的64比特当作比特当作64比特长的无符号整数。比特长的无符号整数。MD缓冲区初始化缓冲区初始化：使用：使用160比特长的缓冲区存储比特长的缓冲区存储中间结果和最终杂凑值，缓冲区可表示为中间结果和最终杂凑值，缓冲区可表示为5个个32比比特长的寄存器特长的寄存器(A,B,C,D,E)，每个寄存器都以每个寄存器都以big-endian方式存储数据，其初始值分别为方式存储数据，其初始值分别为 A=67452301 B=EFCDAB89A=67452301 B=EFCDAB89C=98BADCFB D=10325476C=98BADCFB D=10325476E=C3D2E1F0E=C3D2E1F0压缩函数压缩函数以分组为单位对消息进行处理每一分组以分组为单位对消息进行处理每一分组Yq都经都经一压缩函数处理一压缩函数处理压缩函数压缩函数压缩函数由压缩函数由4轮处理过程构成，每一轮又由轮处理过程构成，每一轮又由20步步迭代组成迭代组成压缩函数压缩函数4轮处理过程结构一样，但所用的基本逻辑函数轮处理过程结构一样，但所用的基本逻辑函数不同，分别表示为不同，分别表示为f1,f2,f3,f4压缩函数压缩函数每轮的输入为当前处理的消息分组每轮的输入为当前处理的消息分组Yq和缓冲区和缓冲区的当前值的当前值A,B,C,D,E，输出仍放在缓冲区以替代输出仍放在缓冲区以替代A,B,C,D,E的旧值的旧值压缩函数压缩函数每轮处理过程还需加上一个加法常量每轮处理过程还需加上一个加法常量Kt，其中其中0t79表示迭代的步数。表示迭代的步数。80个常量中实际上只个常量中实际上只有有4个不同取值个不同取值压缩函数压缩函数每轮处理过程还需加上一个加法常量每轮处理过程还需加上一个加法常量Kt，其中其中0t79表示迭代的步数。表示迭代的步数。80个常量中实际上只个常量中实际上只有有4个不同取值个不同取值第第4轮的输出（即第轮的输出（即第80步迭代的输出）再与第步迭代的输出）再与第1轮的输入轮的输入CVq相加，以产生相加，以产生CVq+1，其中加法是其中加法是缓冲区缓冲区5个字中的每一个字与个字中的每一个字与CVq中相应的字模中相应的字模232相加。相加。输出消息的输出消息的L个分组都被处理完后，最后一个分个分组都被处理完后，最后一个分组的输出即为组的输出即为160比特的消息摘要。比特的消息摘要。步骤步骤到步骤到步骤的处理过程可总结如下：的处理过程可总结如下：CV0=IV;CVq+1=SUM32(CVq,ABCDEq);MD=CVL其中其中IV是步骤是步骤定义的缓冲区定义的缓冲区ABCDE的初值的初值ABCDEq是第是第q个消息分组经最后一轮处理过程个消息分组经最后一轮处理过程处理后的输出处理后的输出L是消息（包括填充位和长度字段）的分组数是消息（包括填充位和长度字段）的分组数SUM32是对应字的模是对应字的模232加法加法MD为最终的摘要值。为最终的摘要值。SHA的压缩函数由的压缩函数由4轮处理过程组成，每轮处理过轮处理过程组成，每轮处理过程又由对缓冲区程又由对缓冲区ABCDE的的20步迭代运算组成，每步迭代运算组成，每一步迭代运算的形式为一步迭代运算的形式为6.4.2 SHA-1的压缩函数的压缩函数A,B,C,D,E为缓冲区的为缓冲区的5个字个字t是迭代的步数是迭代的步数(0t79)ft(B,C,D)是第是第t步迭代使用的步迭代使用的基本逻辑函数基本逻辑函数CLSs为左循环移为左循环移s位位Wt是由当前是由当前512比特长的分比特长的分组导出的一个组导出的一个32比特长的字比特长的字Kt是加法常量是加法常量+是模是模232加法。加法。6.4.2 SHA-1的压缩函数的压缩函数基本逻辑函数基本逻辑函数输入为输入为3个个32比特的字，输出是一个比特的字，输出是一个32比特的字，比特的字，其中的运算为逐比特逻辑运算，即输出的第其中的运算为逐比特逻辑运算，即输出的第n个比个比特是特是3个输入的相应比特的函数个输入的相应比特的函数计算计算Wt的方法的方法Wt由当前的输入分组（由当前的输入分组（512比特长）导出比特长）导出Wt为为32比特长比特长前前16个值（即个值（即W0,W1,W15）直接取为输入分直接取为输入分组的组的16个相应的字个相应的字其余值（即其余值（即W16,W17,W79）取为取为补充：补充：SHA-512的结构的结构SHA-2的三种模式比较的三种模式比较1.抗穷搜索攻击的强度抗穷搜索攻击的强度用穷搜索攻击寻找具有给定消息摘要的消息用穷搜索攻击寻找具有给定消息摘要的消息SHA-1：O(2160)MD5：O(2128)用穷搜索攻击找出具有相同消息摘要的两个不用穷搜索攻击找出具有相同消息摘要的两个不同消息同消息SHA-1：O(280)MD5：O(264)6.4.3 SHA-1与与MD5的比较的比较2.抗击密码分析攻击的强度抗击密码分析攻击的强度由于由于SHA的设计准则未被公开，所以它抗击密码分的设计准则未被公开，所以它抗击密码分析攻击的强度较难判断，似乎高于析攻击的强度较难判断，似乎高于MD5的强度。的强度。3.速度速度两个算法的主要运算都是模两个算法的主要运算都是模232加法，都易于在加法，都易于在32位位结构上实现。结构上实现。SHA-1的迭代步数的迭代步数(80步步)多于多于MD5的迭代步数（的迭代步数（64步），所用的缓冲区（步），所用的缓冲区（160比特）大于比特）大于MD5使用的使用的缓冲区（缓冲区（128比特），因此在相同硬件上实现时，比特），因此在相同硬件上实现时，SHA-1的速度要比的速度要比MD5的速度慢。的速度慢。4.简洁与紧致性简洁与紧致性两个算法描述起来都较为简单，实现起来也较为简两个算法描述起来都较为简单，实现起来也较为简单，都不需要大的程序和代换表。单，都不需要大的程序和代换表。5.数据的存储方式数据的存储方式MD5使用使用little-endian方式，方式，SHA使用使用big-endian方方式。两种方式相比看不出哪个更具优势，之所以使式。两种方式相比看不出哪个更具优势，之所以使用两种不同的存储方式是因为设计者最初实现各自用两种不同的存储方式是因为设计者最初实现各自的算法时，使用的机器的存储方式不同。的算法时，使用的机器的存储方式不同。世界震惊世界震惊:王小云破解全球两大密码算法王小云破解全球两大密码算法 王小云，毕业于山东大学数学系，师从于著名数学家潘承洞、王小云，毕业于山东大学数学系，师从于著名数学家潘承洞、于秀源教授，是一位外表普通却充满自信的中国女性。于秀源教授，是一位外表普通却充满自信的中国女性。2004年年8月，在美国加州圣芭芭拉召开的国际密码大会上，并没月，在美国加州圣芭芭拉召开的国际密码大会上，并没有被安排发言的王小云教授拿着自己的研究成果找到会议主有被安排发言的王小云教授拿着自己的研究成果找到会议主席，要求进行大会发言。就这样，王小云在国际会议上首次席，要求进行大会发言。就这样，王小云在国际会议上首次宣布了她及她的研究小组近年来的研究成果宣布了她及她的研究小组近年来的研究成果对对MD5、HAVAL-128、MD4和和RIPEMD等四个著名密码算法的破译等四个著名密码算法的破译结果。报告结束后，所有与会专家对她们的突出工作报以长结果。报告结束后，所有与会专家对她们的突出工作报以长时间的掌声。时间的掌声。王小云的研究成果作为密码学领域的重大发现宣告了固若金王小云的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准汤的世界通行密码标准MD5大厦轰然倒塌，引发了密码学大厦轰然倒塌，引发了密码学界的轩然大波。这次会议的总结报告这样写道：界的轩然大波。这次会议的总结报告这样写道：“我们该怎我们该怎么办？么办？MD5被重创了，它即将从应用中淘汰。被重创了，它即将从应用中淘汰。SHA-1仍然活仍然活着，但也见到了它的末日。现在就得开始更换着，但也见到了它的末日。现在就得开始更换SHA-1了。了。”世界震惊世界震惊:王小云破解全球两大密码算法王小云破解全球两大密码算法2005年年2月月7日，美国国家标准技术研究院发表声明，日，美国国家标准技术研究院发表声明，SHA-1没有被没有被攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在2010年前应该转向更为安全的年前应该转向更为安全的SHA-256和和SHA-512算法。而仅仅在一周算法。而仅仅在一周之后，王小云就宣布了破译之后，王小云就宣布了破译SHA-1的消息。因为的消息。因为SHA-1在美国等国在美国等国家有更加广泛的应用，密码被破的消息一出，在国际社会的反响可家有更加广泛的应用，密码被破的消息一出，在国际社会的反响可谓石破天惊。换句话说，王小云的研究成果表明了从理论上讲电子谓石破天惊。换句话说，王小云的研究成果表明了从理论上讲电子签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的密码标准，以保证电子商务的安全。密码标准，以保证电子商务的安全。世界震惊世界震惊:王小云破解全球两大密码算法王小云破解全球两大密码算法How to Break MD5 and other Hash FunctionsEurocrypt 2005“Best Paper Award”Finding Collisions in the Full SHA-1 Crypto 2005 Best Paper Award”最近国际密码学家最近国际密码学家Lenstra利用王小云提供的利用王小云提供的MD5碰撞，伪造了符碰撞，伪造了符合合X.509标准的数字证书，这就说明了标准的数字证书，这就说明了MD5的破译已经不仅仅是理的破译已经不仅仅是理论破译结果，而是可以导致实际的攻击，论破译结果，而是可以导致实际的攻击，MD5的撤出迫在眉睫。的撤出迫在眉睫。王小云说，目前王小云说，目前SHA1在理论上已经被破译，离实际应用也为期在理论上已经被破译，离实际应用也为期不远。不远。传统构造传统构造MAC的方法：基于分组密码的构造方的方法：基于分组密码的构造方法。近年来构造法。近年来构造MAC的兴趣已转移到基于密码的兴趣已转移到基于密码杂凑函数的构造方法，这是因为：杂凑函数的构造方法，这是因为：密码杂凑函数密码杂凑函数(如如MD5、SHA)的软件实现快于的软件实现快于分组密码分组密码(如如DES)的软件实现；的软件实现；密码杂凑函数的库代码来源广泛；密码杂凑函数的库代码来源广泛；密码杂凑函数没有出口限制，而分组密码即使密码杂凑函数没有出口限制，而分组密码即使用于用于MAC也有出口限制。也有出口限制。6.5 HMAC算法算法杂凑函数并不是为用于杂凑函数并不是为用于MAC而设计的，由于杂而设计的，由于杂凑函数不使用密钥，因此不能直接用于凑函数不使用密钥，因此不能直接用于MAC目前已提出了很多将杂凑函数用于构造目前已提出了很多将杂凑函数用于构造MAC的的方法，其中方法，其中HMAC就是其中之一就是其中之一HMAC已作为已作为RFC2104被公布，并在被公布，并在IPSec和其和其他网络协议他网络协议(如如SSL)中得以应用中得以应用6.5 HMAC算法算法RFC2104列举了列举了HMAC的以下设计目标：的以下设计目标：可不经修改而使用现有的杂凑函数，特别是那些可不经修改而使用现有的杂凑函数，特别是那些易于软件实现的、源代码可方便获取且免费使用的易于软件实现的、源代码可方便获取且免费使用的杂凑函数。杂凑函数。其中镶嵌的杂凑函数可易于替换为更快或更安全其中镶嵌的杂凑函数可易于替换为更快或更安全的杂凑函数。的杂凑函数。保持镶嵌的杂凑函数的最初性能，不因用于保持镶嵌的杂凑函数的最初性能，不因用于HMAC而使其性能降低。而使其性能降低。以简单方式使用和处理密钥。以简单方式使用和处理密钥。在对镶嵌的杂凑函数合理假设的基础上，易于分在对镶嵌的杂凑函数合理假设的基础上，易于分析析HMAC用于认证时的密码强度。用于认证时的密码强度。6.5.1 HMAC的设计目标的设计目标6.5.2 算法描述算法描述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个个01011010HMAC算法运行过程算法运行过程 K的左边填充的左边填充0以产生一个以产生一个b比特长的比特长的K+（例如例如K的长为的长为160比特，比特，b=512，则需填充则需填充44个零字节个零字节0 x00）K+与与ipad 逐比特异或以产生逐比特异或以产生b比特的分组比特的分组Si 将将M链接到链接到Si后后 将将H作用于步骤作用于步骤产生的数据流。产生的数据流。K+与与opad逐比特异或逐比特异或,以产生以产生b比特长的分组比特长的分组S0 将步骤将步骤得到的杂凑值链接在得到的杂凑值链接在S0后后 将将H作用于步骤作用于步骤产生的数据流并输出最终结果。产生的数据流并输出最终结果。HMAC算法的有效实现算法的有效实现在实现在实现HMAC时，可预时，可预先求出右面两个量：先求出右面两个量：f()是杂凑函数中的压缩是杂凑函数中的压缩函数，其输入是函数，其输入是n比特的比特的链接变量和链接变量和b比特的分组，比特的分组，输出是输出是n比特的链接变量比特的链接变量这两个量的预先计算只这两个量的预先计算只在每次更改密钥时才需在每次更改密钥时才需进行进行事实上这两个预先计算事实上这两个预先计算的量用于作为杂凑函数的量用于作为杂凑函数的初值的初值IV。基于密码杂凑函数构造的基于密码杂凑函数构造的MAC的安全性取决于镶的安全性取决于镶嵌的杂凑函数的安全性嵌的杂凑函数的安全性可以证明了对可以证明了对HMAC的攻击等价于对内嵌杂凑函数的攻击等价于对内嵌杂凑函数的下述两种攻击之一：的下述两种攻击之一：攻击者能够计算压缩函数的一个输出，即使攻击者能够计算压缩函数的一个输出，即使IV是随机的和秘密的。是随机的和秘密的。攻击者能够找出杂凑函数的碰撞，即使攻击者能够找出杂凑函数的碰撞，即使IV是随是随机的和秘密的。机的和秘密的。6.5.3 HMAC的安全性的安全性
展开阅读全文