SHA-3的安全性分析*

为分析Hash函数新标准SHA-3算法的安全性,从算法统计性能和轮函数Keccak-f的对称性两个方面对其进行测试。测试结果表明,SHA-3算法雪崩效应良好,平均变化比特数和平均变化概率都非常接近理想值且方差比较小,具有较高的稳定性和较低的碰撞程度; Keccak-f中添加常数的变换会严重扰乱轮函数的对称性,利用轮函数对称性对SHA-3进行内部差分攻击只适用于轮数较少的情况。     

LBlock算法的相关密钥不可能差分分析

LBlock算法是2011年提出的轻量级分组密码,适用于资源受限的环境.目前,关于LBlock最好的分析结果为基于14轮不可能差分路径和15轮的相关密钥不可能差分路径,攻击的最高轮数为22轮.为研究LBlock算法抵抗不可能差分性质,结合密钥扩展算法的特点和轮函数本身的结构,构造了新的4条15轮相关密钥不可能差分路径.将15轮差分路径向前扩展4轮、向后扩展3轮,分析了22轮LBlock算法.在已有的相关密钥不可能差分攻击的基础上,深入研究了轮函数中S盒的特点,使用2类相关密钥不可能差分路径.基于部分密钥分别猜测技术降低计算量,分析22轮LBlock所需数据量为261个明文,计算量为259.58次22轮加密.     

SHA-3轮函数中ρ、π及χ变换的逆变换

Keccak自2012年被宣布为新一代Hash函数标准SHA-3后受到密码学界的高度关注,成为当前Hash函数研究的热点。文中给出了SHA-3轮函数中ρ、π和χ三个变换的逆变换。ρ变换只在同一道内沿z轴正向循环移位,故依据其移位距离表沿z轴负方向移位同样距离即得到其逆变换ρ-1;π变换依赖于GF（5）上一个2阶变换矩阵,利用高斯消元法对此方阵求逆可得到其逆矩阵,也即得到了π变换的逆变换;χ变换是SHA-3轮函数中唯一的非线性变换,首先列出χ变换的真值表,然后通过真值表推导得出了其逆变换χ-1的布尔函数表达式。基于ρ^-1、π^-1和χ^-1,可利用中间相遇攻击的思想构造差分路径对SHA-3进行攻击,通过消息修改技术使差分路径以概率1通过χ-1,能够大大提高攻击成功的概率。     

Hash差分攻击算法研究

Hash函数广泛应用于商业.军事等领域,因此对Hash算法的攻击在理论上和实际应用上都有重要的意义.自王小云教授提出差分攻击算法并攻破SHA-1,MD5,RIPEMD,MD4以来,对该算法的研究日益受到关注.然而王教授没有给出如何寻找差分和差分路径的方法.国内外专家都猜测她是靠非凡的直觉手工完成的,如何寻找差分和差分路径的方法成为关注的热点.构造差分路径涉及到如何处理差分循环移位和选择高概率的充分条件.业已证明,一般情况下,差分位移后有4种情况,并给出了4种情况的概率,最后比较了4种情况的概率.     

SHA-1充分条件自动化求解算法

充分条件的求解是模差分攻击的重要步骤之一。将充分条件的求解转化为F₂上线性方程组的构造过程,利用线性方程组解的判定定理判断每步所求得充分条件的正确性,提出了针对SHA-1模差分攻击的充分条件自动化求解算法。文中算法做适当变形后,同样适用于MD5、SHA-0等与SHA-1结构相似的Hash函数充分条件的自动化求解。     

ESF算法的相关密钥不可能差分分析

ESF算法是一种具有广义Feistel结构的32轮迭代型轻量级分组密码。为研究ESF算法抵抗不可能差分攻击的能力,首次对ESF算法进行相关密钥不可能差分分析,结合密钥扩展算法的特点和轮函数本身的结构,构造了两条10轮相关密钥不可能差分路径。将一条10轮的相关密钥不可能差分路径向前向后分别扩展1轮和2轮,分析了13轮ESF算法,数据复杂度是260次选择明文对,计算量是223次13轮加密,可恢复18 bit密钥。将另一条10轮的相关密钥不可能差分路径向前向后都扩展2轮,分析了14轮ESF算法,数据复杂度是262选择明文对,计算复杂度是243.95次14轮加密,可恢复37 bit密钥。     

SIMON不可能差分及零相关路径自动化搜索算法

对于分组密码,不可能差分和零相关线性分析都是很重要的分析手段.通过研究非线性组件与（AND）的性质,首先得到用于刻画SIMON轮函数差分及线性传播特性的约束式,再基于布尔可满足约束问题（SAT）,提出一种普适性不可能差分和零相关路径自动化搜索算法,并利用该算法搜索得到SIMON更多的不可能差分及零相关路径.除用于自动化搜索外,该算法还可判断特定的差分对（掩码对）是否能构成一条有效不可能差分和零相关路径.此外,基于该算法,从抵抗不可能差分攻击的角度出发,给出SIMON轮函数设计中循环移位常数的选取依据.     

CRAFT算法基于比特可分性的积分区分器搜索

CRAFT算法是一种新型SPN结构的类AES型轻量级可调分组密码算法,可以有效地抵抗差分故障攻击.为了对CRAFT算法抵抗积分攻击的能力进行评估,采用基于混合整数线性规划(MILP)的方法自动化搜索比特可分性的工具,对CRAFT算法的积分区分器进行搜索,搜索到了最长为12轮的积分区分器,同时得到一条平衡比特数最多的9轮积分区分器.这是目前为止对该算法获得的最长区分器,同时利用这些积分区分器可以对算法进行更多轮的密钥恢复攻击.     

一个新的MD4消息差分

在对Hash函数MD4的已知碰撞攻击方法研究的基础上,提出了一个新的分析思路——在差分路径的第3轮中不再构造局部碰撞,并给出了一条全新的差分路径。结果表明：新的差分路径在第3轮中不存在充分条件需要满足,以此路径构造的MD4碰撞攻击效率与以往攻击结果相比最优,计算复杂度不超过1次MD4运算。     

QARMA算法的相关密钥不可能差分攻击

QARMA算法是一种代替置换网络结构的轻量级可调分组密码算法。研究QARMA算法抵抗相关密钥不可能差分攻击的能力,根据QARMA-64密钥编排的特点搜索到一个7轮相关密钥不可能差分区分器,在该差分区分器的前、后各添加3轮构成13轮相关密钥不可能差分攻击。分析结果表明,在猜测52 bit密钥时,与现有中间相遇攻击相比,该相关密钥不可能差分攻击具有攻击轮数较多、时间复杂度和空间复杂度较低的优点。     

改进Twister碰撞攻击技术

Twister是SHA-3候选算法中的一个典型的基于AES结构的分组密码算法。介绍Twister算法现有攻击技术,并对计算复杂度进行分析。运用反弹攻击,设计了一种可行的差分路径,对Twister算法圈的碰撞攻击进行分析,得到计算复杂度分别为2128和2184的圈碰撞。基于此对Twister压缩函数的碰撞攻击进行分析,可以降低其计算复杂度。     

对MD5的改进及其安全性分析

针对MD5的碰撞攻击,分析了差分分析的步骤和方法;针对消息预处理导致了分组块数增加这一缺陷,提出了修改步函数的方法,能阻止选择好的差分路径,限制消息修改技术的使用,增强了抗碰撞攻击的能力。实验结果表明改进后算法的效率比消息预处理方案的效率高。     

Improved Collision Attack on Hash Function MD5

In this paper, we present a fast attack algorithm to find two-block collision of hash function MD5. The algorithm is based on the two-block collision differential path of MD5 that was presented by Wang et al. in the Conference EUROCRYPT 2005. We found that the derived conditions for the desired collision differential path were not sufficient to guarantee the path to hold and that some conditions could be modified to enlarge the collision set. By using technique of small range searching and omitting the computing steps to check the characteristics in the attack algorithm, we can speed up the attack of MD5 efficiently. Compared with the Advanced Message Modification technique presented by Wang et al., the small range searching technique can correct 4 more conditions for the first iteration differential and 3 more conditions for the second iteration differential, thus improving the probability and the complexity to find collisions. The whole attack on the MD5 can be accomplished within 5 hours using a PC with Pentium4 1.70GHz CPU.     

Second order collision for the 42-step reduced DHA-256 hash function

At the Cryptographic Hash Workshop hosted by NIST in 2005, Lee et al. proposed the DHA-256 (Double Hash Algorithm-256) hash function. The design of DHA-256 builds upon the design of SHA-256, but introduces additional strengthening features such as optimizing the message expansion and step function against local collision attacks. Previously, DHA-256 was analyzed by J. Zhong and X. Lai, who presented a preimage attack on 35 steps of the compression function with complexity 2^239.6. In addition, the IAIK Krypto Group provided evidence that there exists a 9-step local collision for the DHA-256 compression function with probability higher than previously predicted. In this paper, we analyze DHA-256 in the context of higher order differential attacks. In particular, we provide a practical distinguisher for 42 out of 64 steps and give an example of a colliding quartet to validate our results.     

MD5碰撞攻击的差分路径构建

著名的杂凑算法MD5是MD4的增强版本,由Ronald L.Rivest在1991年设计.MD5广泛应用于口令变换、数据完整性、数字证书等领域.近年最具影响的MD5安全性的分析结果是王小云首次发现的MD5碰撞.之后,MD5碰撞攻击的改进主要集中在提高碰撞对搜索的性能.基于新的不同于王小云的明文差分构成的MD5碰撞,介绍差分路径的构建方法,并给出一条差分路径以及碰撞对数据.     

基于多启发式信息融合的攻击路径发现算法研究

攻击路径发现对于提高信息系统安全具有重要意义,传统攻击路径发现技术存在考虑因素有限以及可扩展性不高的问题,导致其在网络攻击复杂化和网络规模扩大化的趋势下应用价值有限。针对该问题,本文提出一种基于多启发式信息融合的攻击路径发现算法,该算法结合攻击路径发现背景知识,将漏洞威胁程度,漏洞成功率以及主机资产作为启发式函数计算依据引导攻击路径搜索,达到减少搜索范围、提高路径可用性的目的;并且基于SMHA^*（Share Multi-Heuristic A^*,SMHA^*）框架实现多种启发式信息融合,共同引导攻击路径搜索。通过与现有规划算法进行对比实验,验证了本算法能够更加灵活而全面地考虑攻击路径发现中的现实因素,且规划效率也能够满足实际需求,能够有效提高规划结果的可行性以及应用价值。     

基于明文相关的混沌映射与SHA-256算法数字图像的加密与监测

针对数字图像的传播安全性问题,以及数字图像加密脱离明文、过分依赖混沌系统的问题,提出了基于明文相关的混沌映射与SHA-256算法数字图像的加密与监测算法。算法通过使用SHA-256算法计算明文图像的哈希值,作为摘要来监测数字图像的传播;使用前向扩散、关联明文的置乱与后向扩散的方法对数字图像进行加密,Lorenz混沌映射产生相应的密码。结果表明该算法具有较好的抵抗各种攻击的能力,达到了图像传播的安全性与隐蔽性的目的。     

A new one-bit diFFerence collision attack on HAVAL-128

In this paper,we give a new fast attack on HAVAL-128.Our attack includes many present methods of constructing hash collisions.Moreover,we present a neighborhood modification.We propose a new difference path different from the previous ones.The conclusion is that,when the output of each step satisfies our condition,the message m can collide with m’= m + Δm,where Δm =(0,0,0,0,231,0,...,0).There is only one bit difference between m and m’.Two pairs of collision examples for HAVAL-128 are given.In order to improve the probability of collision,we use four tricks of message modification.The attack’s running time is less than 225.83 2-pass HAVAL computations,which is the best result for one-bit collision of HAVAL so far.