对约减轮数Skein-1024的Boomerang区分攻击

The Boomerang Attacks on Round-Reduced Skein-1024

Skein算法是美国国家标准与技术研究所(NIST)开启的SHA-3竞赛中的五个候选算法之一,虽然Skein没有成为最终的SHA-3标准,但其在实现效率及安全性方面也十分优秀,尤其是软件实现方面,要高于SHA-3获胜算法Keccak,所以在一些领域也会有潜在应用价值,对其的分析依然有着重要意义.目前已经有很多学者对该算法进行了安全性分析.Boomerang攻击方法是一种自适应选择明密文攻击,由Wagner在1999年提出.它起初是一种分组密码分析方法,在近几年相继被应用于BLACK、SHA-256等杂凑算法分析中并取得了不错的结果,目前这种方法已经成为杂凑算法的一种重要分析方法.本文以Boomerang攻击为主要攻击手段,首次对Skein-1024算法进行了Boomerang区分攻击.根据文中给出的差分路线,我们对Skein-1024算法进行了33轮、34轮和36轮的Boomerang区分攻击,攻击的复杂度分别为2^(258.34)、2^(345.52)和2^(890).同时,本文找到28轮的Boomerang四元组验证了攻击的正确性.最后,基于Boomerang区分器,本文也给出了39轮Threefish-1024的相关密钥恢复攻击,可以恢复1024比特的主密钥,攻击的时间、数据和存储复杂度分别为2^(593.3),2^(414)和2^(45).这是目前对Skein-1024算法最好的Boomrang区分攻击结果.

The hash function Skein is one of the finalists of the NIST SHA-3 competition. At present, many scholars have analyzed the security of this algorithm. Although Skein did not become the final SHA-3 standard, the implementation efficiency and the security of Skein family are nevertheless very good, especially on the aspect of software implementation which is more efficient than the SHA-3 winner Keccak. So there will be some potential application value in some areas for Skein and it is still important to analyze the security of Skein. In this paper, we study the resistance of Skein-1024 against Boomerang attacks. We can attack 33-round, 34-round and 36-round Skein-1024, with a complexity of 2258.34, 2345.52 and 2890 , respectively. The correctness of our attack is verified by a practical 28-round Boomerang quartet. Based on the Boomerang distinguisher, we also propose a related-key key-recovery attack on 39-round simplified (or 32-round normal) Threesh-1024. This attack can recover the 1024 master keys with time, data and memory complexities of 2593.30, 2411 and 245respectively. This is the best Boomerang attack forSkein-1024 known so far.