Third-party papers, studies and implementations
This page lists the third-party papers, studies and implementations related to Keccak in the scope of the SHA-3 contest or otherwise.
Cryptanalysis
J.-P. Aumasson and D. Khovratovich, First Analysis of Keccak, comment on the NIST Hash Competition, 2009
In this paper, Jean-Philippe Aumasson and Dmitry Khovratovich look at two possible distinguishers on reduced-round Keccak-f[1600]. First, cube testers are applied to detect non-ideal behaviors in the algebraic description of the permutation. Second, the authors try to solve the constrained-input constrained-output (CICO) problem using automated algebraic techniques.
The authors received 25 bottles of Belgian trappist beer as the paper was awarded the first prize for the best cryptanalysis. It was presented by Dmitry Khovratovich at the rump session of Eurocrypt 2009 (Beer-recovery analysis).
J. Lathrop, Cube Attacks on Cryptographic Hash Functions, Master's thesis, Rochester Institute of Technology, 2009
In his thesis, Joel Lathrop shows that cube attacks can not only be applied to keyed cryptosystems but also to hash functions by way of a partial preimage attack. Cube attacks are applied to reduced-round variants of ESSENCE and Keccak.
J.-P. Aumasson and W. Meier, Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi, note presented at the CHES 2009 rump session, 2009
In this note, Jean-Philippe Aumasson and Willi Meier investigate a new kind of distinguishers called zero-sum distinguishers. In particular, they compute high-order derivatives of the rounds and the inverse rounds of Keccak-f. Starting from the middle, they obtain a set of values whose sum is zero and whose sum of images through reduced-round Keccak-f is also zero. This distinguisher is successful up to 16 rounds. The authors did not find a way to use this distinguisher against the Keccak sponge function, though.
The authors won the second prize for the best cryptanalysis.
C. Boura and A. Canteaut, A zero-sum property for the Keccak-f permutation with 18 rounds, comment on the NIST Hash Competition, 2010
In this paper, Christina Boura and Anne Canteaut extend the zero-sum distinguisher of Aumasson and Meier to 18 rounds by analyzing the Walsh spectrum of the non-linear part and bounding the degree of the rounds more tightly.
We discuss the zero-sum distinguishers in the following note.
Note on zero-sum distinguishers of Keccak-f, comment on the NIST Hash Competition, 2010
Implementations
J. Strömbergson, Implementation of the Keccak Hash Function in FPGA Devices, 2009
Studies on all SHA-3 candidates
ECRYPT II Project, The SHA-3 Zoo
D. J. Bernstein and T. Lange (editors), eBACS: ECRYPT Benchmarking of cryptographyic systems (eBASH project)
The performance numbers of Keccak, as measured in eBASH, are summarized here.
N. Ferguson, Engineering comparison of SHA-3 candidates
Note that the performance figures are not up-to-date.
E. Fleischmann, C. Forler and M. Gorski, Classification of the SHA-3 Candidates, Cryptology ePrint Archive, Report 2008/511, 2008
The authors of the study do not mention that Keccak has indeed a 5×5 S-box. Note that the performance figures are not up-to-date.
MIT students (group 5), Homework on the SHA-3 Competition, March 2009
Professor Ronald L. Rivest gave his students a homework assignment to review some of the submissions to the SHA-3 hash function competition with respect to the arguments made by the submitters about the security of their proposals. Group 5 looked at Keccak, LUX, AURORA, and TIB3.
We were surprised that the students do not refer to the Keccak main document. They do refer to the specifications, but all design rationale and security analysis is in the main document. It seems that they based their analysis on the Keccak specifications and the sponge functions paper only. We have passed these remarks on to Prof. Rivest who confirmed that this work was not very well done.
K. Ideguchi, T. Owada and H. Yoshida, A Study on RAM Requirements of Various SHA-3 Candidates on Low-cost 8-bit CPUs, comment on the NIST Hash Competition, 2009
In this document, the authors assume that the message block is counted towards the memory usage of the application. It is a valid assumption in several cases. However, there are also applications for which the message is formatted on the fly or does not need to be kept after being hashed. There, constructions such as sponge functions or similar (e.g., CubeHash, LUX) can directly XOR the message block into the state, relieving the application from dedicating a memory area for it. This optimization also applies where the hashing API is composed of functions such as Init, Update and Final. In general a message queue must be allocated, which can be avoided for sponge functions or similar.
About Keccak specifically, the designer of an application on a memory-constrained device may also opt for a smaller state size by using an alternate set of parameters, such as Keccak[r=288,c=512], which uses 100 bytes of RAM. And if 256 bits of capacity are enough for such an application, Keccak[r=144,c=256] uses only 50 bytes.
S. Tillich, M. Feldhofer, M. Kirschbaum, T. Plos, J.-M. Schmidt and A. Szekely, High-Speed Hardware Implementations of BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein, Cryptology ePrint Archive, Report 2009/510, 2009. An interactive version of the graphs is also available.
In this document, the authors implemented all the second-round SHA-3 candidates in HDL and synthesized them on a 0.18µm standard-cell library. Keccak exhibits a very high throughput of 21Gbit/s and a reasonable silicon area requirement of 56K gate equivalents.