You are looking at a specific version 20160914:033459 of this paper. See the latest version.

Paper 2016/878

Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak

Jian Guo and Meicheng Liu and Ling Song

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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2016
Keywords
CryptanalysisSHA-3KeccakPreimage attacksZero-sum distinguishers
Contact author(s)
meicheng liu @ gmail com
History
2016-09-14: received
Short URL
https://ia.cr/2016/878
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.