对杂凑函数和分组密码算法的分析

论文摘要

杂凑函数和分组密码在很多密码安全协议中起着非常重要的作用。杂凑函数最初是为了实现消息的完整性检测和起源认证检测等目的而提出的。当设计出有效且安全的杂凑函数算法之后，人们逐渐认识到若假设杂凑函数是“随机的”（输入和输出独立，各输出之间独立等），杂凑函数可用于其它很多地方，例如：保护口令，构造有效的数字签名方案，构造诸如认证协议，密钥分配协议，比特承诺等协议，构造加密算法等。分组算法主要用来保密消息，包括在广播消息和储存消息时的保密，其安全性主要依赖于算法能抵抗各种攻击。分组算法的分析主要考虑算法的安全性，密码学家用各种分析技巧分析算法，用以评估其安全性。每个分析技巧都使用不同的模型，试图发现算法某方面的设计漏洞。设计杂凑函数的方法有很多，1991年Rivest第一次用直接构造法设计出了杂凑函数MD4[8]，随后的十多年，按照MD4的设计思想，人们陆续设计了MD4系列杂凑函数，包括：MD5[13]，HAVAL[14]，SHA-0[16]，RIPEMD[15]，SHA-1[23]，RIPEMD-128[26]，RIPEMD-160[26]，SHA-2[36]等。其中MD5和SHA-1是应用最广泛的国际通用杂凑算法。RIPEMD算法是欧洲新计划RIPE[15]的一部分，1996年，H．Dobbertin，A．Bosselaers和B．Preneel公布了RIPEMD算法的替代算法RIPEMD-128。RIPEMD-128包含两个并行且独立的操作，记为操作1和操作2，每个操作包含四轮（64步），每轮使用不同的轮函数，并且每个操作中消息字的顺序也不一样。随着MD4系列杂凑函数的广泛应用，对其安全性的分析受到了越来越多的关注，其中最受关注的是对杂凑函数进行碰撞攻击，也就是，找到两个不同的消息，使得它们有相同的杂凑值。H．Dobbertin在1996年公布了MD4的碰撞[24]，该攻击的计算复杂度概率是222，1996年公布了任意初始值下MD5的碰撞[25]，1997年公布两轮RIPEMD算法的碰撞[28]，1998年证明了前两轮的MD4算法非单向函数[31]。B．den Boer[20]，A．Bosselaers[20]和F．Chabaud[32]，A．Joux[32，44]分别给出了对MD5和SHA-0的攻击结果。1997年，王小云提出了比特追踪法[29]，后来被称为模差分方法[51，52]。2004年美密会上，王小云公布了杂凑函数MD4，MD5，RIPEMD和HAVAL-128的碰撞实例[43]。模差分方法是王小云等破解MD4系列杂凑函数的理论基础，她们用模差分方法破解了大多数MD4系列杂凑函数：MD4[51]，MD5[52]，RIPEMD[51]，HAVAL-128[53，54]，SHA-0[48]和SHA-1[49]，找到MD4和RIPEMD算法的计算复杂度分别低于28和218。模差分方法还可以用来寻找杂凑算法的第二原根[50]，攻击HMAC和NMAC（伪造攻击和恢复密钥攻击）[55]。随着MD4系列杂凑函数的破解，对基于杂凑函数的分组密码的分析逐渐成为热点。SHACAL-1[35]是基于杂凑函数SHA-1的分组密码算法，其分组长度为160比特，它是NESSIET程第二阶段评估后胜出的算法之一。以前对SHACAL-1的分析结果参见[38，59，41，45，46，57]。[57]给出了对完整SHACAL-1算法的相关密钥矩形攻击，该攻击的数据复杂度是2159．8(或2153．8)个选择明文，计算复杂度是2420．0(或2501.2)。适用于该攻击的弱密钥数占总密钥数的1/214。SHACAL-2[39]是基于杂凑函数SHA-2的分组密码算法，其分组长度为256比特，它是NESSIE工程最终胜出的算法之一。以前对SHACAL-2的分析结果参见[40，42，58]。就轮数而言，目前对SHACAL-2最好的分析结果见[58]，它利用相关密钥矩形攻击分析了42-轮SHACAL-2，其数据复杂度是2243．38个选择明文，计算复杂度是2488．37。在分析SHACAL-1和SHACAL-2时，找到高概率的差分特征是至关重要的，而找到这些差分特征最关键的部分是分析并利用杂凑函数SHA-1和SHA-2的性质。本文的主要工作分为三部分：1．对前两轮RIPEMD-128算法的碰撞攻击在第4章，利用模差分方法，给出了杂凑函数算法RIPEMD-128前两轮的碰撞攻击，找到前两轮碰撞的计算复杂度是228。到目前为止，这是对RIPEMD-128算法分析的最好结果。攻击RIPEMD-128的难度是相当大的，从设计者公开该算法至今，还未发表过对完整算法的攻击文章，即使对缩减的前n（n<64）步算法，在本文的分析结果之前，也没有公开的分析结果。目前对RIPEMD-128算法唯一公开的分析结果参见[60]，其中给出了RIPEMD-128后三轮的碰撞攻击路线，理论上使其碰撞概率为2-55。利用模差分方法，结合杂凑函数RIPEMD-128算法的特点，通过寻找前两轮操作1和操作2的几乎碰撞差分特征，找到了前两轮（32步）算法的理论破解路线并给出了碰撞实例。寻找前两轮算法碰撞的过程包括以下四步：·记前两轮（32步）RIPEMD-128算法为H32，H32压缩消息M后的输出值记为H32（M）。因为RIPEMD-128算法的初始值不满足几乎碰撞差分特征中对初始值的要求，所以首先要寻找消息M0，使得H32（M0）满足要求，从而几乎碰撞包含两个消息分组（M0||M，M0||M′）。·通过分析RIPEMD-128圈函数的性质和消息在操作1和操作2中的位置，结合明文修改技术的操作特点，确定出构成碰撞路线的可能的消息差分ΔM=M′-M如下：ΔM=(0，…，0，224，0)，其中M=(m0，m1，…，m15)。分别寻找前两轮操作1和操作2的几乎碰撞差分特征，若M和M′满足前两轮操作1的几乎碰撞差分特征，也满足前两轮操作2的几乎碰撞差分特征，那么，前两轮操作1和操作2的压缩结果经过算法的组合后，使得M0||M和M0||M′构成H32的碰撞。前两轮操作1和操作2的几乎碰撞差分特征如表3和表4所示。H32的输出差分为：Δa=Δcc+Δddd=0，Δd=Δbb+Δccc=0,Δc=Δaa+Δbbb=0，Δb=Δdd+Δaaa=231+231(mod232)=0。·推导保证差分特征成立的充分条件。使得前两轮操作1的差分特征成立仅需21个充分条件(亦即，操作1成立的概率不小于2-21)，这对整个攻击能成功实施是非常重要的。在这个过程中，必须保证充分条件互相不矛盾，否则，差分特征就不成立。保证差分特征成立的充分条件见表5和表6。·利用明文修改技术，使得大部分充分条件得以满足。对任意随机消息M，利用基本明文修改技术（单步修改），使得第一轮的充分条件都得以满足。使用高级明文修改技术（多步修改），使得第二轮前几步的充分条件能够得以满足。其余处在第二轮后几步及其后面的充分条件很难通过明文修改使得它们成立。因此，在寻找路线时，应该让处在第二轮及其以后的充分条件尽量少。该攻击的难点之一是选择合适的消息差分：因为RIPEMD-128算法是由两部分平行且独立的操作构成，这两部分的圈函数和消息顺序都不一样，为了寻找合适的碰撞路线并让路线成立的概率尽可能的高，选择合适的消息差分是至关重要且困难的。该攻击的难点之二是明文修改：主要是因为两部分操作的消息顺序不一样，改变一个消息字，只能对操作1和操作2中的一个操作进行进行修改，很难对两部分操作同时进行修改，更坏的是对一个操作进行修改的时候另一个操作的差分路线还有可能被破坏。2．NSHACAL-1的分析在第5章，受到模差分方法中寻找局部碰撞路线的启发，我们发现以前所有对分组算法SHACAL-1的分析都存在错误和不足。[57]的分析不能对所有的密钥都成立，而只能针对满足一定条件的密钥（弱密钥）进行；[46]的分析使用的差分特征成立的概率是零，而不是如作者所说的非零（与随机的相比有一定的优势）；[57]在分析过程中存在漏洞，把许多错误的密钥误认为是正确的，因为用它们解密和用正确的密钥解密能得到同样多的期望中的“正确对／正确四元组”。利用相关密钥矩形攻击方法，我们改进了对完整SHACAL-1算法的攻击，适用于该攻击的弱密钥数占总密钥数的1/256(而以前最好的攻击中的弱密钥的比例是1/214)，该攻击的明文复杂度是2146个选择明文(或2144个选择明文)，计算复杂度是2465次SHACAL-1加密运算(或2494)，需要约2150．33个字节存储。该攻击利用表7和表8的66-轮相关密钥矩形差分特征。第一个差分特征（见表7）的输入差分是α=([8，1]，[3]，[3，-20]，[16，31]，213-210-26)，输出差分是β=(e10,0，e5，C30，0，0)，差分特征成立的概率是2-35。第二个差分特征（见表8）的输入差分是γ=(e1，e1，0，e30,31，e31)，输出差分是δ=（0，e3，0，0，e0），差分特征成立的概率是2-36。第二个差分特征用到了一组弱密钥，其个数占总密钥个数的2-8，对这些弱密钥，第二个差分特征成立的概率增加到2-28(=2-36·28)。通过固定9比特的明文值（见表5．5），第一个差分特征成立的概率可以提高29倍，提高之后第一个差分特征成立的概率是2-35。3．对SHACAL-2的分析在第6章，我们找到SHACAL-2的新的差分特征，结合算法的一些性质，改进了对43-轮SHACAL-2的相关密钥矩形攻击，该攻击的明文复杂度是2240．38个选择明文，计算复杂度是2480．4次43-轮SHACAL-2加密运算，需要约2245．38个字节存储。该攻击利用的差分特征基于[58]，我们的差分特征第0步的输入一输出差分是(0，eM，e31，0，e9,13,19，e18,29，e31，Δi,j)→(0，0，eM，e31，0，e9,13,19，e18,29，e31)其中g1(E0(?e9,13,19)-g1（E0）+Δi,j=0。如果固定如表6．2所示的一些明文比特值，则第0步成立的概率是1。因为D2=B0，H2=F0，根据加密算法以及条件B0，i=（?）F0,i（i=18，29），第2步成立的概率增加到2-10。从[58]我们知道从第2步到第24步成立的概率是2-37，故第一个差分特征成立的概率是2-46。由[58]知道，第二个差分特征成立的概率是2-63．38。故35-轮相关密钥矩形差分特征成立的概率是2-474．76。根据泊阿松分布，知X～Poi（λ=8），PrX[X>5]≈0．8，从而该攻击成功（亦即，对正确的密钥，过滤之后剩下的四元组的个数至少是6个）的概率约是0．8。

论文目录

• 中文部分
• 符号
• 中文摘要
• 英文摘要
• 第一章 介绍和主要内容
• 第二章 杂凑函数和分组密码
• §2.1 杂凑函数
• §2.1.1 杂凑函数的介绍
• §2.1.2 模差分方法
• §2.2 分组密码
• §2.2.1 分组密码介绍
• §2.2.2 分组密码的分析方法
• 第三章 RIPEMD-128和SHACAL-x的算法描述
• §3.1 杂凑函数RIPEMD-128的描述
• §3.2 分组算法SHACAL-1的描述
• §3.3 分组算法SHACAL-2的描述
• 第四章 对RIPEMD-128的分析
• §4.1 32-步RIPEMD-128的差分特征
• §4.2 推导满足操作1和操作2的充分条件
• §4.3 明文修改
• 第五章 对SHACAL-1的分析
• §5.1 以前对SHACAL-1攻击中存在的缺陷
• §5.1.1 使用概率是零的差分特征
• §5.1.2 密钥条件
• §5.1.3 通过基本攻击的错误密钥
• §5.2 一个对SHACAL-1的新分析
• §5.2.1 SHACAL-1的相关密钥差分特征
• §5.2.2 对密钥长为512比特SHACAL-1的恢复密钥攻击
• 第六章 对SHACAL-2的分析
• §6.1 以前对SHACAL-2的分析结果
• §6.2 对43-步SHACAL-2的相关密钥矩形攻击
• §6.2.1 SHACAL-2的相关密钥差分特征
• §6.2.2 对密钥长为512比特43-步SHACAL-2的恢复密钥攻击
• 参考文献
• 致谢
• 攻读博士学位期间完成论文情况
• 学位论文评阅及答辩情况表
• 英文部分
• Abstract
• 摘要
• Notations
• Chapter 1 Introduction and Main Results
• Chapter 2 Hash Function and Block Cipher
• §2.1 Hash Function
• §2.1.1 Introduction of Hash Function
• §2.1.2 The Modular Differential Method
• §2.2 Block Cipher
• §2.2.1 Introduction of Block Cipher
• §2.2.2 Techniques for Cryptanalysis of Block Cipher
• Chapter 3 RIPEMD-128 and SHACAL-x
• §3.1 Description of RIPEMD-128
• §3.2 Description of SHACAL-1
• §3.3 Description of SHACAL-2
• Chapter 4 Cryptanalysis of Reduced RIPEMD-128
• §4.1 Collision Differential Path for the Reduced RIPEMD-128
• §4.2 Deriving Conditions on Chaining Variables of Collision Path
• §4.3 Message Modification
• Chapter 5 Cryptanalysis of SHACAL-1
• §5.1 Flaws in Previously Published Attacks
• §5.1.1 The Use of Differentials with Probability Zero
• §5.1.2 Conditions on the Keys
• §5.1.3 Wrong Keys that Pass the Basic Attacks
• §5.2 A New Related-Key Rectangle Attack on the Full SHACAL-1
• §5.2.1 Related-Key Differential Characteristics for SHACAL-1
• §5.2.2 The Key Recovery Attack Procedure for the Full SHACAL-1 with 512-bit Keys
• Chapter 6 Cryptanalysis of SHACAL-2
• §6.1 Previous Attacks on SHACAL-2
• §6.2 Related-Key Rectangle Attack on 43-round SHACAL-2
• §6.2.1 Related-Key Differential Characteristics for SHACAL-2
• §6.2.2 The Key Recovery Attack Procedure for 43-round SHACAL-2 with 512-bit Keys
• Bibliography
• Acknowledgement
• Completed papers in the doctoral time
• 学位论文评阅及答辩情况表