杂凑函数结构研究现状及新的结构设计

密码杂凑函数是一类基础密码算法,在现代通信、金融、安全计算等许多领域有着极为广泛的应用。它可以用来提供数据完整性检测如篡改检测码MDC,消息认证码MAC,不可否认性如数字签名等安全性质,成为保障电子签名、身份认证等多种密码系统安全的关键技术。 杂凑函数设计方式通常有两种,一种是使用成熟的分组密码来构造杂凑函数。如,串联和并联的Davies-Meyer结构,以及MDC-2和MDC-4等。这类杂凑函数都是基于成熟的分组算法,它们的运行效率很低,在遇到海量数据时,这种杂凑函数便不能满足应用需求。这类杂凑函数的安全性分析主要侧重于对结构的分析。另一类是专用的安全高效的杂凑函数。1989年,Merkle[19]和Damgard [7]分别给出了利用输入长度固定的压缩函数构造杂凑函数的方法,其目的是使杂凑函数的抗碰撞性等价于压缩函数的抗碰撞性,这样杂凑函数的设计就集中于固定长度的压缩函数的设计,这种结构称为MD结构。最具代表性的是MDx系列杂凑函数,这一系列杂凑函数主要包括MD4, MD5, HAVAL, SHA-0, SHA-1, SHA-2, RIPEMD-160等[26,27,22,23,24,37]。这些杂凑函数都是在MD4设计思想的基础上,加入了新的设计理念,用以提高算法的安全性,统称为MDx系列杂凑函数。直到2004年,MD5与SHA-1一直是计算机网络世界普遍使用的两大杂凑函数标准。 对专用的杂凑函数的安全性分析,开始于1992年。在Eurocrypt1993上,Boer和Bosselaers首次给出了MD5的一条伪碰撞路线[2]。在Eurocrypt 1996上,Dobbertin给出了在非标准的初始值下MD5的碰撞攻击实例[9]。同年,在FSE 1996上,Dobbertin首次给出了MD4碰撞的有效攻击[10],这是MD系列的第一个理论攻击,也是有效的实际攻击。 1997年王小云教授首次使用“比特追踪法”来分析SHA-0,理论上破解了SHA-0[30]。第二年,她使用“消息修改”技术极大的改进了这一结果[31]。同年,在Crypto 1998上,Chabaud和Joux使用差分分析技术给出了SHA-0的理论分析结果[5]。在Crypto 2004上,王小云教授公布了MD4、MD5、HAVAL和RIPEMD的碰撞实例[32,34],具体攻击方法——比特追踪法和及攻击细节[33]等首次在Eurocrypt 2005上发表,这也是破解包括MN5、SHA-1在内的多数MDx系列杂凑函数的理论基础。在Crypto 2005上,王小云教授还公布了SHA-1全算法的碰撞攻击[35]。这些都说明当前使用的MDx系列杂凑函数是不安全的。 本文回顾了各种杂凑函数的结构和对结构的攻击方法,尤其是针对MD结构的攻击方法。同时研究了近几年新出现的HAIFA[1], sponge结构[3],宽管道结构[18]等,并概要的总结了这些新的结构设计特点。在此基础上提出双管道结构的加强版本—双管道加强。 早期的MD结构由于其迭代的性质而容易受到长度扩展攻击,二次碰撞攻击等,Merkle对MD进行了改进,对消息进行填充时,加入了消息的长度信息,提出了加强的MD结构。但即使MD迭代结构使用的压缩函数是抗碰撞的,这类杂凑函数仍然容易受到攻击。自2004年以来,密码学界对MD迭代结构的分析取得了突破性的研究进展。Joux在Crypto 2004上,使用生日攻击,给出了对MD结构的杂凑函数的多碰撞攻击[14],产生2t-碰撞的复杂度为t·2n／2,优于搜索攻击。在Eurocrypt 2005上,Kelsey和Schneier提出了构造可扩展的消息,对长消息进行第二原像攻击的方法[16],并分别使用Dean的固定点方法[8]和借鉴Joux的方法[14]构造了可扩展的消息,对长消息的第二原像进行了攻击。在Eurocrypt 2006上,Kelsey和Kohno提出了对一个相关的短消息进行原像攻击的方法[15],即选择目标固定前缀的原像攻击,在这个攻击中,攻击者通过预计算,成功构造了一个钻石结构,并给出目标杂凑值。然后对挑战者给出的前缀,寻找联接消息,将前缀与钻石结构联接起来,从而得到目标杂凑值的原像。这种攻击可以用来做预言攻击。 最初的杂凑函数设计并不要求其满足抗长度扩展攻击,但是如果杂凑函数不能抵抗长度扩展攻击,那么使用这种杂凑函数构造的消息认证码就面临受到伪造的风险。因此NIST在SHA-3标准算法的征集中增加了抗长度扩展攻击的安全属性。 国际密码领域又出现了许多新的杂凑函数结构,这些新的结构都力图避免遭受针对MD结构的攻击。Asiacrypt 2005上,Lucks提出的宽轨道设计方法[18],通过加长压缩函数的链接变量,进行迭代,最后在输出摘要时,将长的链接变量进行截断或是采用压缩函数压缩到需要的输出长度。这种使用长的链接变量进行迭代,使得找到内部的多碰撞和进行长消息的第二原像攻击的复杂度超过攻击理想的杂凑函数的复杂度而导致攻击的失败。2005年,Rivest提出了在压缩消息时,加入“无平方因子”的数字标签的方法[28],这样可以破坏引起第二原像攻击的迭代结构,但当数字标签出现重复时,就不能防止Kelsey等的构造可扩展的消息的方法,因而不能抵抗长消息的第二原像攻击。2007年,Biham等提出了HAIFA结构[1],在迭代过程中,增加了数字标签和随机数。增加数字标签,就不能再容易的使用Dean的固定点方法。增加随机数,使得离线预计算不再可行,从而可以防止对选择目标的固定前缀攻击等离线攻击方法,同时,使用HAIFA的杂凑函数构建的数字签名方案中,签名者可以选择随机数,攻击者必须要考虑随机数的因素才能进行攻击,从而增强了数字签名方案的安全性。2007年,Bertoni等人提出了一种可证明安全的Sponge结构[3],当迭代的基本算法是随机置换时,Sponge是可证明安全的[4],但多数基于Sponge结构的杂凑算法,利用简化的分组密码算法和简单的置换作为基本算法,因而不能达到理想的安全强度。 最后,通过分析最近几年新出现的这些杂凑函数结构的特点,借鉴宽管道结构中,通过加长内部状态,用来阻止敌手寻找内部碰撞的这种特点,本文提出对双管道的改进版本—双管道加强(Enstrengthed Double Pipe),并证明了在随机喻言模型下,这种新的结构同双管道结构一样,可以抵抗多碰撞攻击,长消息的第二原像攻击等攻击方法。这种新结构的效率与双管道相同。