Practical Collision Attacks against Round-Reduced SHA-3
Practical Collision Attacks against Round-Reduced SHA-3
复制标题
针对轮数减少的 SHA-3 的实际碰撞攻击
DOI：
10.1007/s00145-019-09313-3
复制
发表时间：
2020-01-01
影响因子：
3
通讯作者：
Song, Ling
中科院分区：
文献类型：
--
作者：
Guo, Jian;Liao, Guohong;Song, Ling
Keccak Hash功能是SHA-3比赛（2008-2012）的获胜者，并于2015年成为NIST的SHA-3标准。在本文中，我们专注于对圆形SHA-3和一些Keccak的实际碰撞攻击变体。遵循Dinur等人开发的框架。在FSE 2012上，通过组合3轮差距和1轮连接器发现了4轮碰撞，我们将连接器扩展到最多三轮，从而实现最多6轮的碰撞攻击。由于广泛的内部国家的自由度，可能会扩展。通过线性化第一轮的S框，找到2轮连接器的解决方案的问题被转换为求解线性方程系统的解决方案。当将线性化应用于前两轮时，将可能进行3轮连接器。但是，由于线性化引起的自由度的迅速降低，只有当三轮差距满足某些其他条件时，连接器才能成功。我们制定了专门的策略来搜索差异步道，并发现确实存在这种特殊的差异步道。总而言之，我们在六个实例上获得了第一次真实的碰撞，包括三个圆形的SHA-3实例，即5轮Shake128，SHA3-224和SHA3-256，以及三个Keccak竞赛实例，即Keccak [1440，Keccak [1440，，， 160，5，160]，Keccak [640，160，5，160]和Keccak [1440，160， 6，160]，将实际攻击的数量提高了两个。据指出，这里的工作仍然没有威胁到整个24回合SHA-3家族的安全。
The Keccak hash function is the winner of the SHA-3 competition (2008-2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some Keccak variants. Following the framework developed by Dinur et al. at FSE 2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3, namely 5-round SHAKE128, SHA3-224 and SHA3-256, and three instances of Keccak contest, namely Keccak[1440, 160, 5, 160], Keccak[640, 160, 5, 160] and Keccak[1440, 160, 6, 160], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family.