Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak
In this paper, we analyze the security of round-reduced versions of the Keccak hash function family. Based on the work pioneered by Aumasson and Meier, and Dinur et al., we formalize and develop a technique named linear structure, which allows linearizati
- PDF / 1,257,109 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 215 Views
3
Cryptanalysis Taskforce, Temasek Laboratories@NTU, Singapore, Singapore [email protected], [email protected], [email protected] 2 School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, People’s Republic of China
Abstract. In this paper, we analyze the security of round-reduced versions of the Keccak hash function family. Based on the work pioneered by Aumasson and Meier, and Dinur et al., we formalize and develop a technique named linear structure, which allows linearization of the underlying permutation of Keccak for up to 3 rounds with large number of variable spaces. As a direct application, it extends the best zero-sum distinguishers by 2 rounds without increasing the complexities. We also apply linear structures to preimage attacks against Keccak. By carefully studying the properties of the underlying Sbox, we show bilinear structures and find ways to convert the information on the output bits to linear functions on input bits. These findings, combined with linear structures, lead us to preimage attacks against up to 4-round Keccak with reduced complexities. An interesting feature of such preimage attacks is low complexities for small variants. As extreme examples, we can now find preimages of 3-round SHAKE128 with complexity 1, as well as the first practical solutions to two 3-round instances of Keccak challenge. Both zero-sum distinguishers and preimage attacks are verified by implementations. It is noted that the attacks here are still far from threatening the security of the full 24-round Keccak. Keywords: Cryptanalysis Zero-sum distinguishers
1
·
SHA-3
·
Keccak
·
Preimage attacks
·
Introduction
The Keccak sponge function family [6] was designed by Bertoni et al. as one of the 64 proposals submitted to the SHA-3 competition [24] in October 2008. It won in October 2012 after intense competition, and was subsequently standardized by the U.S. National Institute of Standards and Technology (NIST) as Secure Hash Algorithm-3 [25] (SHA-3) in August 2015. As such, Keccak has received intensive security analysis, since the design was made public in 2008, against the traditional security notions such as collision, preimage, and second-preimage c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 249–274, 2016. DOI: 10.1007/978-3-662-53887-6 9
250
J. Guo et al.
resistance, as well as distinguishers of the underlying permutations and securities under some message authentication code, stream cipher, and authenticated cipher modes. Up to date, the best collision attacks are reduced up to 4 out of 24 rounds of Keccak-224/256 with practical complexities [12,14], and up to 5 rounds of Keccak-256 with theoretical complexities [13], by differential attacks. Practical preimage attacks are up to 2 rounds, by the approaches of meet-in-the-middle [23] and SAT s
Data Loading...
