随着信息化时代的到来,信息成为社会发展的重要资源,是当今世界发展的潮流和核心。而信息安全在信息社会中扮演着非常重要的角色,直接关系到国家安全,金融、商业、公安、军事和政府等部门的正常运作,以及人们的日常生活。随着信息产业的快速发展,全球对信息安全方面的要求进一步提高,特别是电子商务的兴起,使得信息加密、认证技术以及安全传输协议等变得尤为重要。消息认证码(Message Authentication Code,简称MAC码)是保证消息完整性和进行数据源认证的基本算法,它将密钥和任意长度的消息作为输入,输出一个固定长度的标签,使验证者可以能够校验消息的发送者是谁,以及消息传输过程中是否被篡改。这在网络交互中是非常重要的,因此它被广泛应用于各种安全协议中,如IPSec, SSL/TLS、SSH、SNMP等。目前,消息认证码主要有三种构造方法——基于分组密码(Block Ci-pher)、杂凑函数(Hash Function)或者泛杂凑函数族。本文侧重于对基于杂凑函数的MAC码的安全性进行研究。杂凑函数(Hash Function)将任意比特长的输入消息压缩成固定长的输出。这个输出称为该消息的消息摘要(Message Digest),也称杂凑值(Hash Value)。对杂凑函数的攻击主要有：原像攻击、第二原像攻击、碰撞攻击及长度延展攻击等。现代抗碰撞杂凑函数可以提供数据完整性保护,是数字签名中的关键技术,并被用于构造伪随机数生成器及消息认证码等。一系列的杂凑函数已经被开发出来,如MD4, MD5, SHA-0, SHA-1以及SHA-2函数族(可产生224,256,384和512比特杂凑值),所有这些都遵循MD (Merkle-Damgard)结构。1993年,美国国家标准技术局(National Institute of Standards and Technology, NIST)开始对SHA函数进行标准化,在FIPS PUB 180 (Federal Information Processing Standards Publication)中给出了安全杂凑函数标准SHA-0的规范说明。后续版本FIPS 180-1将SHA-0替换为SHA-1, FIPS180-2添加了SHA-2函数族。近几年来,王小云等提出一系列Hash函数的碰撞攻击成果,发现了MD4, MD5, SHA-0, SHA-1的碰撞攻击。尽管SHA-2系列还没有实际的攻击出现,但是对SHA-2系列成功的碰撞攻击将对数字签名的安全性带来灾难性的后果。面对Hash函数的安全性现状,NIST于2007年在全球范围内开始新的杂凑函数标准的征集工作,预计在2012年评选出新的Hash函数标准算法,这个新算法将被称为"SHA-3"。杂凑函数的系列攻击结果,也影响到其相关应用的安全性,密码研究人员发现这些碰撞路线直接导致了一些MAC算法的有效差分攻击,基于杂凑函数的MAC码的安全性成为研究热点。对MAC码算法的攻击方法主要有以下几种：·区分攻击(区分MAC算法和随机函数的R型区分攻击/Distinguishing-R Attacks以及区分MAC算法基于的具体密码元件和基于随机函数的H型区分攻击/Distinguishing-H Attacks);·伪造攻击(攻击者可计算随机消息M的有效MAC值C的存在性伪造／(?)Existential Forgery,攻击者可选择消息M并计算有效MAC值C的选择性伪造／Selective Forgery,对任给的消息M,都可计算有效MAC值C的一般性伪造Universal Forgery);·密钥恢复攻击(恢复密钥k,从而可以任意进行伪造。如果不能恢复全部的密钥,则恢复部分密钥的攻击称为部分密钥恢复攻击。通过恢复部分密钥,猜测剩余的密钥比特,可以极大的降低攻击的复杂度)。在导师的悉心指导下,本论文对基于SHA系列杂凑函数的MAC码的安全性进行分析,并有如下结果：(1)基于63步(8-70)SHA-1的LPMAC的区分攻击在深入分析SHA-1碰撞路线中差分向量选取和碰撞概率的关系的基础上,结合王小云等在FSE 2009提出的新型区分器,适当选取碰撞路线起始点,将基于61步SHA-1的LPMAC的区分攻击扩展到63步(8-70),复杂度为2157次查询,成功率为0.70。MAC码又称带密钥的杂凑函数,根据密钥介入方式的不同,分为密钥前置(Secret Prefix Method).或者密钥后置(Secret Surfix Method),以及密钥封装(Envelope Method)等,秘密前置MAC码,即将密钥等秘密信息级联在明文消息之前,然后进行杂凑操作的MAC码,是早期广泛使用的一类MAC码,其最初的形式为：MACk(m)=H(k‖m),但是这种MAC码易受到长度扩展攻击,因为在Merkle-Damgard迭代结构中,我们有HIV(m1‖m2)=HH(m1)(m2),从而,如果敌手通过某种渠道获得了消息ml的MAC值,那么他可以在不知道秘密密钥k的情况下,伪造m1‖m2的MAC值。解决这一问题的一种方案是将消息的长度也放到秘密前置中,即：MACk(m)=H(K‖l‖padding‖m),其中“l”表示消息的长度,"padding"为消息填充,使得“k‖l‖padding”成为一个完整的消息块。这种MAC码的构造方式称为LPMAC (Length Prefix MAC)。王小云等的攻击方法利用一条截断的61步SHA-1碰撞路线,通过来识别第一轮的一个内部几乎碰撞,确切的说,是发生在第14步的几乎碰撞来进行区分攻击。我们知道,SHA-1的碰撞路线中,第一轮的情况最为复杂,条件数也最多,通过这种方法,可以忽略前14步的条件,而用一个碰撞来代替,从而降低问题的难度。我们发现对于截断的SHA-1算法,如果不从SHA-1的第一步开始,而是从第一轮的某一步开始的话,则有可能将该方法应用于基于更多轮数的截断的SHA-1的LPMAC。首先,我们对SHA-1的碰撞攻击进行研究。根据王小云等对安全杂凑函数(SHA-体制)的碰撞攻击,SHA-1的碰撞路线是由一些局部碰撞构成。局部碰撞可以分为两种情形：单一局部碰撞和复合局部碰撞。·单一局部碰撞是指对两个明文M,M′,虽然在以后的相邻6步操作内所对应的扩展明文块不同,但在计算H(M),H(M′)的第i步操作后,输出值相同。·复合局部碰撞是指多个单一局部碰撞复合而成的碰撞,在不同的轮函数内,其性质有所不同。第一圈的一个单一局部碰撞成立的概率为1／25,即需要5个条件来保证碰撞的发生。对于第二圈来说,所需条件数为2个,第三圈为4个,第四圈为2个。而复合碰撞攻击的情况稍微复杂,第一圈两个相邻的单一碰撞不可能构成复合局部碰撞,而第三圈的某些复合局部碰撞成立所需要的条件数低于相应几个单一碰撞所需条件数之和,第二和第四圈的复合局部碰撞成立所需的条件数则与相应单一碰撞所需条件数之和相等。然后,编程搜索适当的差分向量(Disturbance Vector),我们发现,差分向量应满足第一圈的条件数尽量少,同时避免不能构成复合碰撞的情况,并且总的条件数尽量少,则有可能将该方法用于基于更多轮数的SHA-1的LPMAC.通过设定不同的初始值,按照SHA-1的消息扩展获得一定长度的差分向量列表,然后对这些差分向量进行筛选。由于在王小云等的方法中,第14步之后的条件数不能超过40,因此这限制了可用的差分向量的筛选。我们通过比较最终确定了一段适合的差分向量,它与王小云等所采用的差分路线中使用的差分向量的初始值相同,但整条路线作了平移。这样使得整条路线可以达到63步,条件数为37个。确定了几乎碰撞路线,按照王小云等的区分器,成功进行区分攻击,其复杂度为2157次查询,成功的概率为0.70。(2)基于65步(12-76)SHA-1的LPMAC的区分攻击通过进一步分析SHA-1的差分路线的特点,发现可以单条路线取代两条路线构造新的区分器,使原本不能超过40个条件的制约扩展为不超过80个条件,从而将基于SHA-1的LPMAC的区分攻击由63步扩展到65步(12-76),复杂度由2157次查询降低为280.9次查询。王小云等的方法有效的避免了SHA-1中第一轮的复杂情况,但所利用的区分器需要两对消息同时满足差分路线,极大限制了碰撞路线需要的条件数,使得该攻击很难扩展到基于更多步数的截断SHA-1的LPMAC,因此我们尝试采用不同的方法对基于缩减轮数SHA-1的LPMAC进行区分攻击。首先要解决的问题是条件数的限制,我们的区分器只需一对消息满足差分路线,这样碰撞路线的条件数只需不超过80,就可保证攻击复杂度不超过2160次查询。但这样一来我们就无法使用内部几乎碰撞来代替第一轮的条件,而必须使用其他的方法来避免第一轮的复杂情况出现。我们通过寻找适合的碰撞路线来做到这一点。由于放宽了条件数的制约,在选择差分向量的时候有了很大的空间,根据需要我们选择了一条适合的差分向量,使其在SHA-1第一轮中的条件尽量少,并且能够构成复合碰撞,同时由于第三轮也产生较多的条件,通过构造某些特定复合局部碰撞,使第三轮的条件也尽量优化,以达到使碰撞路线尽可能长而总条件数相对较少的目的。我们选择了差分向量起始值为(0x00000002,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)的路线,并通过调整其位置来尽量达到上述要求,通过这种方法,我们选择的伪碰撞路线可以分析65步(12-76)SHA-1,条件数为78个。在此路线的基础上,构造区分器。对于包含两个分组的消息,根据生日悖论,我们首先保证第一次迭代之后发生碰撞,然后通过选择适当的第二个消息块来识别该碰撞,最终利用选定的65步SHA-1的几乎碰撞路线来进行区分攻击,将基于65步SHA-1的LPMAC与基于随机函数的LPMAC区分开来。区分器的构造思路如下：1.选取足够多的单分组消息x,对每个x级联相同的单分组消息y,询问所有x‖y的MAC值。2.使用生日攻击,搜索所有满足LPMAC(x||y)=LPMAC(x’||y)的碰撞对(x||y,x’||y).则碰撞可能发生在第一次迭代之后,也有可能发生在第二次迭代之后。对于前者,我们称为内部碰撞,而后者称为外部碰撞。3.过滤掉外部碰撞,对于内部碰撞,级联上278对满足选定碰撞路线的消息对(y1,y2),4.询问所有的(x||y1,x’||y2),看能否找到一对满足差分路线的碰撞。若能找到,则该MAC算法有很大概率是基于65步SHA-1的LPMAC,否则是基于随机函数的LPMAC.我们将该攻击应用于基于65步(12-76)的SHA-1的LPMAC,其复杂度为2809次查询,成功的概率为0.51。(3)SHA-0-MAC的部分密钥恢复攻击结合Contini等HMAC-MD5部分密钥恢复攻击及王小云等MD5-MAC部分密钥恢复攻击的思想,利用现有SHA-0(伪)碰撞路线,推断路线成立的充要条件,首次提出SHA-0-MAC的部分密钥恢复攻击,可恢复子密钥K0及160比特子密钥K1的128个比特,复杂度为2125.58次MAC查询。MDx-MAC是另一类将MD结构的杂凑函数转化为MAC码的构造方法,它可以基于MD5,RIPEMD,SHA系列等基于MD迭代结构的杂凑函数(MD4由于其安全强度的原因不宜采用)。这种方法首先在1995年美密会(Crypto’95)上由Preneel和Oorschot提出,它通过对密钥K进行变换,得到3个子密钥K0,K1,K2,其中K0,K2两个子密钥的用法类似于信封式,而子密钥K1分成4个32比特字,分别介入4轮中间变量的置换。我们把基于SHA-0的MDx-MAC称为SHA-0-MAC.在导师的建议和指导下,我们对SHA-0-MAC的安全性进行了分析,并给出了对SHA-0-MAC的部分密钥恢复攻击。该攻击首先要寻找所需的碰撞,伪碰撞是一类具有如下形式的碰撞：H(IV’,M’).其中M为消息,IV为初始值,IV≠IV′。经过我们的分析发现文献给出的1条伪碰撞差分路线具有好的概率优势,成立的概率为2-64。我们利用该路线推出了路线成立的充分条件,基于这条差分路线,采用与MD5-MAC的密钥恢复相似的方法进行部分密钥恢复攻击。首先利用生日攻击寻找碰撞,并从中识别出满足差分路线的碰撞。所采用的方法与(1)中的类似,然后利用其进行SHA-0-MAC的部分密钥恢复。SHA-0-MAC的密钥K0 K1 K2分别在IV,每一个迭代中,和末尾出现,由于中间密钥K1参与中间状态的迭代过程,因此我们可以通过验证中间状态和子密钥K1的相互关系来恢复中间密钥K1。利用上述碰撞,首先恢复给定碰撞的部分中间变量比特,由于要恢复的中间状态的部分比特由于SHA-0的明文扩展没有循环移位,,可直接使用位反转算法来恢复ai,对子密钥K1的4部分K1[0],K1[1],K1[2],K1[3]分别进行恢复。其复杂度主要取决于寻找符合特定差分路线的碰撞。最后,在SHA-0-MAC的计算过程中,由于子密钥K0作为IV我们已经恢复了K1,所以可选择另一条差分路线,直接利用文献中6.2节的方法恢复K0,复杂度是284次MAC询问和260次SHA-0压缩函数的计算。