杂凑函数BLAKE的攻击方法研究

论文摘要

杂凑函数是确保数据完整性和不可否认性的重要工具,在信息安全领域有着非常广泛的应用。近几年,对杂凑函数安全性的研究取得了重要进展,我国密码学家王小云教授成功破解了MD4、MD5等一系列杂凑函数,随着研究的深入和计算能力的提高,SHA-1等杂凑函数的安全性也面临挑战。因此,美国国家标准及技术研究所于2007年开始征集新一代标准杂凑函数SHA-3,经过严格评估,BLAKE等14个算法于2009年被选为第二轮候选算法,入围最后一轮评估的候选算法也已于2010年12月公布。BLAKE算法作为最终入围的5个算法之一,其安全性有待进一步研究。本文通过分析BLAKE的算法特点,运用下列三种分析方法对算法的安全性进行了深入分析,取得了以下成果:1.详细分析了消息置换特征,发现了某些置换在减少运算轮数情况下存在设计缺陷,并根据压缩运算的特点,采用分段-连接技术,对BLAKE算法进行了三轮的自由起始原像攻击,降低了其抗原像攻击的计算复杂度。2.利用消息置换特征,提出了改进的自由起始碰撞攻击,进一步降低了算法在2轮运算下抗碰撞攻击的计算复杂度。利用链路状态变量输入输出差分特征和中途相遇思想,对六轮的BLAKE-32进行了中途相遇碰撞攻击,分析了该算法多轮运算情况下的安全性。3.通过对模加运算进行线性化,分析了初始差分值在各轮运算过程中的扩散特征,在此基础上,对线性化差分攻击在BLAKE算法安全性分析中的有效性进行了研究。研究表明,线性化差分攻击是当前攻击BLAKE算法最有效的方法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景与现状
• 1.2 研究内容及意义
• 1.3 本文的章节安排
• 第二章 杂凑函数及BLAKE 算法分析
• 2.1 杂凑函数概述
• 2.1.1 杂凑函数的定义
• 2.1.2 迭代型杂凑函数
• 2.1.3 杂凑函数的设计原则
• 2.2 BLAKE 算法的实现原理
• 2.2.1 算法总体结构
• 2.2.2 消息填充规则
• 2.2.3 算法实现过程
• 2.3 BLAKE 算法的特征分析
• 2.3.1 消息置换特征
• 2.3.2 链路变量差分
• 2.3.3 算法结构特征
• 2.4 BLAKE 的攻击方法比较
• 2.4.1 攻击方法研究
• 2.4.2 攻击方法比较
• 第三章 BLAKE 的自由起始原像攻击方法研究
• 3.1 BLAKE 的自由起始原像攻击方案
• 3.1.1 自由起始原像攻击总体思想
• 3.1.2 减少轮数BLAKE 的攻击方法
• 3.2 减少轮数BLAKE-32 的攻击步骤
• 3.2.1 2 轮BLAKE-32 的攻击步骤
• 3.2.2 3 轮BLAKE-32 的攻击步骤
• 3.3 BLAKE 的自由起始原像攻击效果
• 3.3.1 原像攻击的计算复杂度
• 3.3.2 原像攻击的局限性
• 第四章 减少轮数BLAKE 的碰撞攻击方法研究
• 4.1 减少轮数BLAKE 的碰撞攻击方案
• 4.1.1 自由起始碰撞攻击方案
• 4.1.2 中途相遇碰撞攻击方案
• 4.2 减少轮数BLAKE 的碰撞攻击步骤
• 4.2.1 改进的自由起始碰撞攻击
• 4.2.2 BLAKE-32 的中途相遇攻击
• 4.3 BLAKE 的碰撞攻击效果分析
• 4.3.1 改进方案的计算复杂度
• 4.3.2 两种攻击方案对比分析
• 第五章 BLAKE 的线性化差分攻击方法研究
• 5.1 BLAKE 的线性化差分攻击方案
• 5.1.1 G 函数的线性化方法
• 5.1.2 差分模式与线性化概率
• 5.2 BLAKE-32 的线性化差分扩散特征
• 5.2.1 1-bit 差分扩散特征
• 5.2.2 2-bit 差分扩散特征
• 5.3 BLAKE 线性化差分攻击的应用分析
• 5.3.1 近似碰撞实例分析
• 5.3.2 差分攻击的有效性
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 致谢
• 参考文献
• 研究生在读期间研究成果