基于不可能差分的SHA3-512约减轮区分攻击

Distinguish Attack on Round-reduced SHA3-512 Based on Impossible Differential

Keccak算法是一族具有海绵结构的杂凑函数,由Bertoni等人设计,是SHA3标准征集活动的最终获选算法,对该算法的分析主要分为三类,分别是对约减轮压缩函数的分析、对消息认证码和认证加密方案的分析以及对置换函数的区分攻击.本文研究了Keccak算法的不可能差分性质,给出了基于不可能差分特征的区分攻击方法.我们发现在轮函数运算过程中,位于同一列的两比特在经过线性层θ时异或值保持不变,基于此性质我们构造了4轮置换函数的不可能差分特征.考虑到不同版本中消息和摘要的长度各不相同,并且会影响输入输出差分的选择,我们筛选出了符合SHA3-512版本约束条件的不可能差分特征.最后,利用在非线性层χ的逆运算中,当输入值满足一定条件时,某些比特的输出差分与输入差分相等这一性质,我们给出了4轮SHA3-512不可能差分区分攻击.当数据量达到2^(8.21)个消息时,将SHA3-512与随机函数区分开的成功率达到99%,对应的时间复杂度为2^(8.21)次压缩.我们以SHA-512作为随机函数,实验验证了上述理论结果.同等轮数下,我们的攻击复杂度优于其他方法.

Keccak is a family of Hash functions with sponge construction, which was designed by Bertoni et al., and selected as the winner of the SHA3 competition. The security analysis of Keccak can be divided into three parts, which are the analyses of Keccak in the context of hashing,the analyses on Keccak-MAC and authenticated encryption schemes, and the distinguish attacks on Keccak-f permutations. This paper studies the impossible differential property of Keccak, and presents a distinguish attack based on it. It is found that the XOR of two bits in a column remains unchanged after the linear operation θ in the round function. Based on this property, a 4-round impossible differential characteristic of Keccak function can be constructed. Considering that the sizes of the message and the digest are different in each version and will affect the choice of the input and output differentials, an impossible differential characteristic is selected that conforms to SHA3-512. Then we develop a property of the non-linear operation x^(-1),which shows that when the input pairs satisfy some constraints, the output difference and the input difference should be equal. Finally, Based on the characteristic and the property, an impossible differential distinguish attack on 4-round SHA3-512 is performed. The success rate of this attack is 99%, where the data complexity is 2^(8.21) messages and the corresponding time complexity is 2^(8.21). We did some experiments to verify the above theoretical results by taking SHA-512 as the random function, and it shows that the complexity of our attack is better than other methods in the same number of rounds.