Xiaoen Lin
Department of Computer Science and Technology, Tsinghua University, Beijing, China

Le He
School of Cyber Engineering, Xidian University, Xi'an, China

Hongbo Yu
Department of Computer Science and Technology, Tsinghua University; Zhongguancun Laboratory; State Key Laboratory of Cryptography and Digital Economy Security, Tsinghua University, Beijing, China

Keywords: Keccak, SHA-3, Preimage attack, Linear structure

Abstract

Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers' work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with the unsatisfied restrictions while bringing more degrees of freedom at the same time. Besides, we show that guessing values for different variables will result in different complexity of solving time. With these techniques, the guessing times can be decreased to 2⁵², and the solving time for each guess can be decreased to around 2^5.2 3-round Keccak calls. As a result, the complexity of finding a preimage for 3-round Keccak-256 can be decreased to around 2^57.2. For 4-round Keccak[r=640, c=160], an instance of the Crunchy Contest, we use some techniques to save degrees of freedom and make better linearization. Based on these techniques, we build an MILP model and obtain an attack with better complexity of around 2^60.9. The results of 3-round Keccak-256 and 4-round Keccak[r=640, c=160] are verified with real examples.