论文部分内容阅读
Hash函数是现代密码学的重要组成部分,它能够将任意长度的消息压缩成固定长度的Hash值,被广泛应用于多种密码协议中,如数字签名,数据完整性保护和消息认证码等。作为一个安全的Hash函数,需要至少满足3个基本安全属性,分别是抗碰撞攻击、抗原像攻击和抗第二原像攻击。随着一系列国际Hash标准算法在碰撞攻击方面的突破,原像攻击也受到众多密码学家的重视。中间相遇攻击在2008年被引入到Hash函数的原像攻击中,成为原像攻击的基本方法之一。随后,又有很多技术被融入到中间相遇攻击中,如分段-链接技术、部分匹配技术、完全二分结构体技术和初始结构体技术等。但是基于中间相遇的原像攻击的复杂度一般都很高,接近于暴力搜索的复杂度。同时Hash函数通常都包含消息扩展过程,这使构造全部轮数的原像攻击的难度增加。基于上述原因,Hash函数的原像攻击主要有两个方向,一个是如何提高攻击的轮数,另一个是如何降低攻击的复杂度。本文分析了韩国Hash标准算法HAS-160、ISO/IEC 10118-3 Hash标准算法RIPEMD-160和我国Hash标准算法SM3密码杂凑算法的安全性。它们均采用Merkle-Damgard结构,消息分组长度512比特。Hash值长度分别为160比特、160比特和256比特。本文取得了三个重要成果:第一给出了HAS-160的71轮伪原像攻击和71轮原像攻击;第二给出了RIPEMD-160的31轮到35轮原像攻击;第三给出了SM3密码杂凑算法的29轮和30轮原像攻击。就攻击轮数而言,所有结果均为当前最好的原像攻击。·HAS-160的伪原像和原像攻击HAS-160于2000年被提出,结构与SHA-1相似,并在韩国得到了广泛应用。HAS-160的轮数最多的原像攻击是Hong等人给出的从第1轮开始的67轮原像攻击和从第13轮开始的68轮原像攻击。对HAS-160的分析主要考虑如何提高原像攻击的轮数。本文构造了HAS-160的6轮完全二分结构体,结合差分中间相遇攻击给出了从第1轮开始的复杂度为2158.12的71轮HAS-160的伪原像攻击,将从第1轮开始的伪原像攻击的轮数由67轮提高到71轮。但是该攻击使用了消息填充所需的比特,不能满足消息填充。通过调整压缩函数的划分形式以及线性空间的组合方式,改变完全二分结构体的位置,避开了消息填充对线性空间的影响,将伪原像攻击中线性空间所占的消息字由7个降低到4个,维数由3增加到5,提高了差分路线的概率,给出了从第7轮开始的71轮原像攻击,其复杂度为2158.97。该结果将从中间轮开始的原像攻击的轮数由68轮提高到71轮。这是目前HAS-160的轮数最多的原像攻击。·RIPEMD-160的原像攻击RIPEMD-160是RIPEMD的增强版本,该算法于1996年由Dobbertin,Bossselaers和Preneel提出,是ISO/IEC 10118-3 Hash标准算法之一。它的压缩函数采用双分支结构,增加了分段-链接的难度。目前,RIPEMD-160还没有从第1轮开始的原像攻击,从中间轮开始的轮数最多的原像攻击是Ohtahara等人给出的31轮结果。为了增加分析的轮数,将初始值作为完全二分结构体的内部变量,匹配选在右支的最后一轮的输出变量上。通过搜索线性空间的位置,使初始值的低比特尽量保持不变,构造了3.5轮的完全二分结构体。使用差分中间相遇攻击给出了从第1轮开始的31轮到34轮RIPEMD-160的原像攻击,复杂度分别为2157.97、2157.75、2158.80和2158.91。这是首个从第1轮开始的RIPEMD-160的原像攻击结果。将线性空间选在同一个消息字内部,给出了从第2轮开始的35轮RIPEMD-160的原像攻击,复杂度为2159.38,这是目前RIPEMD-160的轮数最多的原像攻击。该结果将从中间轮开始的原像攻击的轮数由31轮提高到35轮。·SM3密码杂凑算法的原像攻击SM3密码杂凑算法由王小云教授等人设计,整体结构和SHA-2相似,增加了双字介入等属性来提高其安全性。由于SM3密码杂凑算法的前16轮采用全异或的布尔函数,构造从第1轮开始的原像攻击相对比较困难。从第1轮开始的SM3密码杂凑算法的轮数最多的原像攻击是王高丽老师等人给出的29轮结果。本文首先使用间接部分匹配技术和比特进位猜测改进了王高丽老师等人的29轮原像攻击,将伪原像攻击的复杂度降低26,原像攻击复杂度降低23。使用差分中间相遇攻击给出了从第1轮开始的复杂度为2255.2的30轮原像攻击,将从第1轮开始的原像攻击的轮数提高1轮。这是目前从第1轮开始的SM3密码杂凑算法的轮数最多的原像攻击。