学位论文 > 优秀研究生学位论文题录展示

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

作　者: 王高丽
导　师: 王小云
学　校: 山东大学
专　业: 信息安全
关键词: 杂凑函数分组密码碰撞攻击模差分相关密钥矩形攻击
分类号: TN918
类　型: 博士论文
年　份: 2008年
下　载: 367次
引　用: 1次
阅　读: 论文下载

内容摘要

杂凑函数和分组密码在很多密码安全协议中起着非常重要的作用。杂凑函数最初是为了实现消息的完整性检测和起源认证检测等目的而提出的。当设计出有效且安全的杂凑函数算法之后，人们逐渐认识到若假设杂凑函数是“随机的”（输入和输出独立，各输出之间独立等），杂凑函数可用于其它很多地方，例如：保护口令，构造有效的数字签名方案，构造诸如认证协议，密钥分配协议，比特承诺等协议，构造加密算法等。分组算法主要用来保密消息，包括在广播消息和储存消息时的保密，其安全性主要依赖于算法能抵抗各种攻击。分组算法的分析主要考虑算法的安全性，密码学家用各种分析技巧分析算法，用以评估其安全性。每个分析技巧都使用不同的模型，试图发现算法某方面的设计漏洞。设计杂凑函数的方法有很多，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]，该攻击的计算复杂度概率是2²²，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算法的计算复杂度分别低于2⁸和2¹⁸。模差分方法还可以用来寻找杂凑算法的第二原根[50]，攻击HMAC和NMAC（伪造攻击和恢复密钥攻击）[55]。随着MD4系列杂凑函数的破解，对基于杂凑函数的分组密码的分析逐渐成为热点。SHACAL-1[35]是基于杂凑函数SHA-1的分组密码算法，其分组长度为160比特，它是NESSIET程第二阶段评估后胜出的算法之一。以前对SHACAL-1的分析结果参见[38，59，41，45，46，57]。[57]给出了对完整SHACAL-1算法的相关密钥矩形攻击，该攻击的数据复杂度是2^159．8(或2^153．8)个选择明文，计算复杂度是2^420．0(或2^501.2)。适用于该攻击的弱密钥数占总密钥数的1/2¹⁴。SHACAL-2[39]是基于杂凑函数SHA-2的分组密码算法，其分组长度为256比特，它是NESSIE工程最终胜出的算法之一。以前对SHACAL-2的分析结果参见[40，42，58]。就轮数而言，目前对SHACAL-2最好的分析结果见[58]，它利用相关密钥矩形攻击分析了42-轮SHACAL-2，其数据复杂度是2^243．38个选择明文，计算复杂度是2^488．37。在分析SHACAL-1和SHACAL-2时，找到高概率的差分特征是至关重要的，而找到这些差分特征最关键的部分是分析并利用杂凑函数SHA-1和SHA-2的性质。本文的主要工作分为三部分：1．对前两轮RIPEMD-128算法的碰撞攻击在第4章，利用模差分方法，给出了杂凑函数算法RIPEMD-128前两轮的碰撞攻击，找到前两轮碰撞的计算复杂度是2²⁸。到目前为止，这是对RIPEMD-128算法分析的最好结果。攻击RIPEMD-128的难度是相当大的，从设计者公开该算法至今，还未发表过对完整算法的攻击文章，即使对缩减的前n（n<64）步算法，在本文的分析结果之前，也没有公开的分析结果。目前对RIPEMD-128算法唯一公开的分析结果参见[60]，其中给出了RIPEMD-128后三轮的碰撞攻击路线，理论上使其碰撞概率为2^-55。利用模差分方法，结合杂凑函数RIPEMD-128算法的特点，通过寻找前两轮操作1和操作2的几乎碰撞差分特征，找到了前两轮（32步）算法的理论破解路线并给出了碰撞实例。寻找前两轮算法碰撞的过程包括以下四步：·记前两轮（32步）RIPEMD-128算法为H₃₂，H₃₂压缩消息M后的输出值记为H₃₂（M）。因为RIPEMD-128算法的初始值不满足几乎碰撞差分特征中对初始值的要求，所以首先要寻找消息M₀，使得H₃₂（M₀）满足要求，从而几乎碰撞包含两个消息分组（M₀||M，M₀||M′）。·通过分析RIPEMD-128圈函数的性质和消息在操作1和操作2中的位置，结合明文修改技术的操作特点，确定出构成碰撞路线的可能的消息差分ΔM=M′-M如下：ΔM=(0，…，0，2²⁴，0)，其中M=(m₀，m₁，…，m₁₅)。分别寻找前两轮操作1和操作2的几乎碰撞差分特征，若M和M′满足前两轮操作1的几乎碰撞差分特征，也满足前两轮操作2的几乎碰撞差分特征，那么，前两轮操作1和操作2的压缩结果经过算法的组合后，使得M₀||M和M₀||M′构成H₃₂的碰撞。前两轮操作1和操作2的几乎碰撞差分特征如表3和表4所示。H₃₂的输出差分为：Δa=Δcc+Δddd=0，Δd=Δbb+Δccc=0,Δc=Δaa+Δbbb=0，Δb=Δdd+Δaaa=2³¹+2³¹(mod2³²)=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/2¹⁴)，该攻击的明文复杂度是2¹⁴⁶个选择明文(或2¹⁴⁴个选择明文)，计算复杂度是2⁴⁶⁵次SHACAL-1加密运算(或2⁴⁹⁴)，需要约2^150．33个字节存储。该攻击利用表7和表8的66-轮相关密钥矩形差分特征。第一个差分特征（见表7）的输入差分是α=([8，1]，[3]，[3，-20]，[16，31]，2¹³-2¹⁰-2⁶)，输出差分是β=(e_10,0，e₅，C₃₀，0，0)，差分特征成立的概率是2^-35。第二个差分特征（见表8）的输入差分是γ=(e₁，e₁，0，e_30,31，e₃₁)，输出差分是δ=（0，e₃，0，0，e₀），差分特征成立的概率是2^-36。第二个差分特征用到了一组弱密钥，其个数占总密钥个数的2^-8，对这些弱密钥，第二个差分特征成立的概率增加到2^-28(=2^-36·2⁸)。通过固定9比特的明文值（见表5．5），第一个差分特征成立的概率可以提高2⁹倍，提高之后第一个差分特征成立的概率是2^-35。3．对SHACAL-2的分析在第6章，我们找到SHACAL-2的新的差分特征，结合算法的一些性质，改进了对43-轮SHACAL-2的相关密钥矩形攻击，该攻击的明文复杂度是2^240．38个选择明文，计算复杂度是2^480．4次43-轮SHACAL-2加密运算，需要约2^245．38个字节存储。该攻击利用的差分特征基于[58]，我们的差分特征第0步的输入一输出差分是(0，e_M，e₃₁，0，e_9,13,19，e_18,29，e₃₁，Δ_i,j)→(0，0，e_M，e₃₁，0，e_9,13,19，e_18,29，e₃₁)其中g₁(E⁰(?_e_9,13,19)-g1（E⁰）+Δ_i,j=0。如果固定如表6．2所示的一些明文比特值，则第0步成立的概率是1。因为D²=B⁰，H²=F⁰，根据加密算法以及条件B_0，i=（?）F_0,i（i=18，29），第2步成立的概率增加到2^-10。从[58]我们知道从第2步到第24步成立的概率是2^-37，故第一个差分特征成立的概率是2^-46。由[58]知道，第二个差分特征成立的概率是2^-63．38。故35-轮相关密钥矩形差分特征成立的概率是2^-474．76。根据泊阿松分布，知X～P_oi（λ=8），Pr_X[X>5]≈0．8，从而该攻击成功（亦即，对正确的密钥，过滤之后剩下的四元组的个数至少是6个）的概率约是0．8。

全文目录

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

相似论文

用于文档加密的Rijndael算法研究,TP309.7
分组密码抗差分攻击分析技术研究,TN918.2
MD5选择前缀碰撞关键技术研究,TN918.1
混沌网络文件密码系统研究,TN918.2
（X+K）mod2~n加密环节的性质及其在数据库加密中的应用研究,TP309.7
视频图像智能分析系统关键技术研究与实现,TP391.41
分组密码的关键组件检测及实际安全性研究,TN918.1
分组密码扩散结构的构造与分析,TN918.1
分组密码的差分故障分析,TN918.1
对缩减轮数的分组算法Serpent和ICEBERG的差分攻击,TN918.1
嵌套SPN结构的Feistel型分组密码的可证明安全性,TN918.1
密码函数的理论和分析,TN918.1
多媒体信息的混沌加密算法研究,TP309.7
基于APN函数的S盒研究,TN918.1
IDEA密码体制的安全性分析,TN918.1
基于分组密码的增量哈希函数的设计与分析,TN918.1
跳频电台加密算法研究与实现,TN914.41
椭圆曲线数字签名的FPGA设计,TN918.1
一种基于分组密码算法的设计和分析,TN918.1
分组密码CLEFIA的分析,TN918.1
基于XTS-AES的主机加密卡的FPGA的设计与实现,TP309.7