A SAT-based preimage analysis of reduced Keccak hash functions
- a Kielce University of Commerce, ul. Peryferyjna 15, 25-562 Kielce, Poland
- b Institute of Computer Science, Polish Academy of Sciences, ul. Ordona 21, 01-237 Warsaw, Poland
- Received 22 December 2011, Revised 15 November 2012, Accepted 8 March 2013, Available online 20 March 2013
- Communicated by A. Tarlecki
Highlights
- •
We have carried out the SAT-based preimage attack on reduced Keccak hash function.
- •
We have found a preimage and partial preimages for reduced versions of Keccak hash function.
- •
The results suggest the strength of the Keccak function against the SAT-based attack.
Abstract
In this paper, we present a preimage attack on reduced versions of Keccak hash functions. We use our recently developed toolkit CryptLogVer for generating the conjunctive normal form, CNF, which is passed to the SAT solver PrecoSAT. We found preimages for some reduced versions of the function and showed that full Keccak function has a comfortable security margin against this kind of attack.
Keywords
- Cryptography;
- Hash functions;
- Keccak;
- Algebraic cryptanalysis;
- Logical cryptanalysis;
- SAT solvers
