This page lists all the third-party cryptanalysis results that we know of on Keccak, including FIPS 202 and SP 800-185 instances, KangarooTwelve, the authenticated encryption schemes Ketje and Keyak, and Kravatte. We may have forgotten some results, so if you think your result is relevant and should be on this page, please do not hesitate to contact us.
The results are divided into the following categories:
In each category, the most recent results come first.
First, the Crunchy Crypto Collision and Pre-image Contest contains third-party cryptanalysis results with practical complexities.
In this paper, Sahiba Suryawanshi, Dhiman Saha and Satyam Sachan use a linearization technique proposed by Jian Guo, Meicheng Liu and Ling Song to improve the SymSum distinguisher introduced by Dhiman Saha, Sukhendu Kuila and Dipanwita Roy Chowdhury. This allowed them to build distinguishers for the different SHA-3 variants up to 9 rounds, and in particular for SHAKE128 reduced to 9 rounds with a complexity of 264.
In this paper, Fukang Liu, Takanori Isobe, Willi Meier and Zhonghao Yang improve preimage attacks on Keccak[r=832, c=768] reduced to 2, 3 and 4 rounds and on Keccak[r=576, c=1024] reduced to 2 and 3 rounds. They also construct a practical zero-sum distinguisher for the Xoodoo permutation with 12 rounds.
In this paper, Jian Guo, Guohong Liao, Guozhen Liu, Meicheng Liu, Kexin Qiao and Ling Song recap on the state-of-the art collision attacks against Keccak with practical complexity.
In this paper, Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang and Jingyuan Zhao present a distinguisher on Keccak[r=1152, c=448] reduced to 8 rounds. The attack complexity is 2122 in time and 2122 data and negligible memory. A cube tester is used to construct the distinguisher and an MILP model is used to search for cube variables.
In this paper, Mahesh Sreekumar Rajasree presents new preimage attacks on Keccak by defining non-linear structures. The author focuses on instances with the number of rounds reduced to 2, 3 or 4, and with a capacity of c=768 or 1024 bits.
In this paper, Ting Li and Yao Sun present a new technique for performing a preimage attack on Keccak. They aim for 2 blocks, allowing the constraints to be spread and thus solved more easily. For 3 rounds, the preimage attacks with a practical complexity of 238-241 when the capacity is 448 bits and of 281-286 for c=512. For 4 rounds, the complexities are theoretical and above 2200, yet improving upon the previous results.
In this paper, Rajendra Kumar, Nikhil Mittal and Shashank Singh improve upon the existing preimage attacks on Keccak. Specifically, they present a preimage attack on Keccak[r=832, c=768] reduced to 2 rounds with a time complexity of 289.
In this paper, Yu-Ao Chen and Xiao-Shan Gao present a new algorithm for solving Boolean equations using a quantum computer. The apply their algorithm to mount a preimage attack. It is however unclear what is the complexity of this attack.
In this paper, Ting Li, Yao Sun, Maodong Liao and Dingkang Wang construct a novel kind of structures of polynomials inside the Keccak-f permutation, called cross-linear structures. Based on this, they present new preimage attacks on Keccak[r=240, c=160] and on Keccak[r=1088, c=512] (SHA3-256, SHAKE256), both reduced to 3 rounds. For the former, they solved the 3-round collision challenge in the Crunchy Contest after a computational effort of about 245 operations.
In this paper, Ling Song, Guohong Liao and Jian Guo improve upon their previous work by developing new techniques to save degrees of freedom in their attack. As a result, they propose a practical collision attack on Keccak[r=1152, c=448] reduced to 5 rounds, and they describe how they solved the 6-round collision challenge in the Crunchy Contest, which took 250 operations.
In this paper, Kexin Qiao, Ling Song, Meicheng Liu and Jian Guo develop a hybrid method combining algebraic and differential techniques to mount collision attacks on Keccak. They can find collisions on various instances of Keccak with the permutation Keccak-f or Keccak-f reduced to 5 rounds. This includes the 5-round collision challenges in the Crunchy Contest.
In this paper, Dhiman Saha, Sukhendu Kuila and Dipanwita Roy Chowdhury combine the analysis of symmetries and of the algebraic degree of the Keccak-f permutation to propose a distinguisher on the Keccak sponge function. It can reach up to 9 rounds with a complexity of 2511.
In this paper, Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent and John Schanck investigate the cost of Grover's quantum search algorithm when used to find preimage attacks on SHA3-256 (i.e., Keccak[r=1088, c=512] with 256 bits of output), as well as on SHA-2. They compare the cost of a classical generic attack (2256 operations) with that on a quantum computer with a carefully motivated cost metric (2166 logical-qubit-cycles).
In this paper, Jian Guo, Meicheng Liu and Ling Song develop the technique of linear structures and show how to linearize 3 rounds of Keccak-f. They then apply it in preimage attacks on up to 4 rounds. For instance, a preimage on SHAKE128 reduced to 4 rounds with 128 bits of output can be found in complexity 2106. The same technique has been used to solve the 3-round pre-image challenge in the Crunchy Contest. They also used the linear structures to improve the complexity of zero-sum distinguishers on Keccak-f.
In this paper, Sourav Das and Willi Meier investigate the bias of difference bits after the propagation of low-weight differential trails after two rounds of Keccak-f. They apply this technique to find distinguishers on Keccak when the permutation is reduced to 6 rounds, with a complexity of 252.
In this paper, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus present a preimage attack on Keccak[r=576, c=1024] reduced to 3 rounds and 512 bits of output with complexity 2503. They also present a partial preimage attack, where 256 bits of a 640-bit input message are unknown. This attack works on 4 rounds with a complexity of 2251.
In this paper, Stefan Kölbl, Florian Mendel, Tomislav Nad and Martin Schläffer analyze the differential properties of Keccak-f and Keccak-f. They present collision attacks with practical complexity on Keccak when the permutation is reduced to 4 rounds. The instances covered include c≤352 when using Keccak-f and c≤640 when using Keccak-f.
In this paper, Itai Dinur, Orr Dunkelman and Adi Shamir present collision attacks on Keccak with practical complexity up to 3 rounds of Keccak-f and with complexity 2115 for 5 rounds.
In this paper, Paweł Morawiecki, Josef Pierpzyk and Marian Srebrny apply rotational cryptanalysis to Keccak. They use it to construct a 5-round distinguisher for Keccak-f and to do preimage generation for 4 rounds of Keccak[r=1024,c=576] truncated to 512 bits with complexity 2506 calls to Keccak-f.
In this paper, Paweł Morawiecki and Marian Srebrny report on experiments for generating preimages using SAT solvers. They attack Keccak versions calling Keccak-f with width 50, 200 and 1600 and with a reduced number of rounds. They compare the SAT solver approach with plain exhaustive search and it turns out to be faster for up to 3 rounds.
The authors of this paper present practical-time collisions on Keccak[r=1088,c=512] (and lower capacity) with 4 rounds. They combine a low-weight trail over 3 rounds with algebraic techniques. They also find near-collisions when the number of rounds is reduced to 5.
In this paper, the authors propose several practical-time attacks on the Keccak hash function with 2 to 4 rounds. First, they give a differential distinguisher exploiting a low-weight differential trail. Its complexity is 225 for 4 rounds. Then, they show how to produce a collision (resp. near-collision) on 2 (resp. 3) rounds of Keccak[r=1088,c=512] (and lower capacity) with complexity 233 (resp. 225). Finally, they present an algorithm to find (second) preimages in time 231 and memory 229.
The attack exploits the low degree of Keccak-f's round function and turns it into a (second) preimage attack at the sponge function level. The downside of the attack is that this workload reduction comes at the cost of memory. For 6 rounds, 2176 bits of memory give a workload reduction by a factor 50 (~6 bits); for 7 rounds, 2320 bits of memory give a workload reduction by a factor 37 (~5 bits); and for 8 rounds, 2508 bits of memory give a workload reduction by a factor 1.4 (half a bit). The author was awarded the fourth prize for the best cryptanalysis.
In this paper, Tingting Cui and Lorenzo Grassi analyze Xoofff and highlight a non-ideal interaction between the expanding rolling function and the Xoodoo permutation. By combining a meet-in-the-middle algebraic attack and the linearization technique, they can recover the key of Xoofff where the expansion permutation is reduced to 4 rounds (instead of 6) in time 2106 and memory 270. Also, by exploiting high-order differentials and interpolation, they can recover the key of Xoofff where the middle and expansion permutations have a total of 9 rounds (instead of 12) in time 2106, memory 270 and data 2100.
In this paper, Haibo Zhou, Rui Zong, Xiaoyang Dong, Keting Jia and Willi Meier apply a type of algebraic cryptanalysis, called interpolation attacks, to the deck function Kravatte 6644, reduced-round versions of the deck functions Kravatte and Xoofff and the NIST lightweight proposal Elephant-Delirium that uses Keccak-f. They are able to cover 8 rounds of the underlying permutation with data complexities ranging from 270 blocks (Delirium) to 278 blocks (Kravatte) and computational complexities ranging from 290 to 2112 operations.
In this paper, Haibo Zhou, Zheng Li, Xiaoyang Dong, Keting Jia and Willi Meier further investigate conditional cube attacks on Ketje Jr, on an authenticated encryption mode based on Xoodoo, and on Xoodyak. When Ketje Jr is reduced to 5 rounds, they can recover the key with time complexity 227. For Xoodyak reduced to 6 rounds, this is 244.
In this paper, Fukang Liu, Zhenfu Cao and Gaoli Wang look at conditional cube attacks and introduce new techniques to find cube variables. They propose key recovery attacks that can break a MAC based on Keccak[r=576, c=1024] reduced to 6 rounds in time 240. For Keccak[r, c] with c=256, 512 or 768 reduced to 7 rounds, the time complexity is 271.
In this paper, Zheng Li, Xiaoyang Dong, Wenquan Bi, Keting Jia, Xiaoyun Wang and Willi Meier propose improved conditional cube attacks to reduce the complexity of the known key recovery attacks on Keccak, KMAC and Ketje Sr. In particular, for KMAC256 reduced to 9 rounds, the time complexity is now 2139, for a MAC based on Keccak[r=576, c=1024] reduced to 7 rounds, the time complexity is 272 and for Ketje Sr reduced to 7 rounds, the complexity is 277.
In this paper, Wenquan Bi, Xiaoyang Dong, Zheng Li, Rui Zong and Xiaoyun Wang improve upon the cube attacks of Dinur et al. [Eurocrypt 2015] by optimizing the choice of public variables in the cube using mixed-integer linear programming (MILP). Their method works best and outperforms other methods when the number of degrees of freedom is small (e.g., small rate or small permutation width). They apply the method to a MAC function on top of Keccak[r=1344, c=256] and Keccak[r=576, c=1024] reduced to 6 (time 242-259) or 7 rounds (280-2112). They also apply it to Lake Keyak reduced to 7 (242) or 8 rounds (279) and to Ketje Minor and Major reduced to 7 rounds (294-2113).
In this paper, Ling Song and Jian Guo further develop cube-attack-like techniques involving mixed integer linear programming (MILP) to attack reduced-round Keccak, Ketje and Xoodoo. More specifically, they attack a MAC based on Keccak[r=576, c=1024] reduced to 7 rounds with a time complexity of 2111. For Ketje Jr, they attack 5 and 6 rounds with time complexities of 235 and 259 respectively. They also consider a Ketje-style authenticated encryption mode on top of Xoodoo reduced to 6 rounds with a complexity of 289.
In this paper, Thomas Fuhr, María Naya-Plasencia and Yann Rotella describe key recovery attacks on Ketje Jr, targeting the encryption phase. The attacks work with a rate extended to 32 or 40 bits (instead of the nominal 16 bits). They compare the resistance of their attacks between Ketje Jr v1 and v2, and show that the latter has a thicker safety margin.
In this paper, Colin Chaigneau, Thomas Fuhr, Henri Gilbert, Jian Guo, Jérémy Jean, Jean-René Reinhard and Ling Song analyze the Kravatte pseudo-random function. They show that Kravatte 6644 is vulnerable to key recovery attacks using high-order differential attacks or using algebraic attacks on the expansion phase. They also show that the attacks work even if the number of rounds is raised to 6 for all permutations. However, their attacks do not extend to the final version of Kravatte, namely, Kravatte Achouffe. The authors were so generous to communicate their results to us during the review process of our Farfalle paper submission to ToSC, allowing us to tweak Kravatte accordingly.
In this paper, Chen-Dong Ye and Tian Tian investigate a variant of cube attacks called divide-and-conquer attacks, and apply it to a MAC function on top of Keccak[r=1024, c=576] reduced to 6 or 7 rounds. They improve upon the attacks of Dinur et al. [Eurocrypt 2015], but not on the attacks of Huang et al. [Eurocrypt 2017].
In this paper, Ling Song, Jian Guo, Danping Shi and San Ling improve cube attacks on Keccak-based functions by finding more optimal sets of conditional cubes. Their findings apply to many instances: to KMAC128 reduced to 7 rounds (time 276), KMAC256 reduced to 9 rounds (2147), Lake Keyak reduced to 9 rounds (2137), River and Lake Keyak reduced to 8 rounds (271-277), Ketje Minor and Major reduced to 7 rounds (271-273) and Ketje Sr reduced to 7 rounds (292). They also present a general attack on the full-state keyed duplex with Keccak-p[1600, nr=9] of complexity 290.
In this paper, Zheng Li, Wenquan Bi, Xiaoyang Dong and Xiaoyun Wang improve the cube attacks on Keccak and Ketje. First, they present key recovery attacks on Keccak used in a MAC mode, reduced to 6 rounds (time 258) and 7 rounds (time 275), gaining one round comapred to by Huang et al. Second, they reduce the time complexity of the key recovery attacks by Dong et al. on reduced-round Ketje Minor and Major, from 296 down to 281 and 283, respectively.
In this paper, Xiaoyang Dong, Zheng Li, Xiaoyun Wang and Ling Qin mount cube attacks on the Ketje family of authenticated encryption schemes, with a focus on the primary recommendation Ketje Sr. They can successfully recover the key when the number of rounds of the initialization step is reduced from 12 down to 6, with various complexities (e.g., from 296 for Ketje Minor or Major to 2113 for Ketje Sr).
In this paper, Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang and Jingyuan Zhao generalize cube attacks into conditional cube testers. They present different attacks in different settings. With a MAC mode on top of Keccak with a reduced-round Keccak-f, they can recover the secret key up to 7 rounds with a time and data complexity of 272. On Lake Keyak, their attack extends to 8 rounds with a time and data complexity of 274. Finally, they also propose (unkeyed) distinguishers on Keccak reduced to 7 rounds.
In this paper, Christoph Dobraunig, Maria Eichlseder and Florian Mendel present a heuristic tool for finding linear trails in permutations over a small number of rounds with low weight. The permutations they target are the ones of Ascon, ICEPOLE, Lake Keyak, Minalpher and Prøst. With this tool they re-discover the best known linear trails for 3 and 4 rounds of Keccak-f, that we reported on in KeccakTools. Additionally, they also looked for linear trails over 3 and 4 rounds where the output masks is only in the outer part, when being used in Lake Keyak, and found the best such trails known to date.
In their paper, Itai Dinur, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus present attacks that combine cube attacks and structural properties of Keccak. They target different keyed modes of Keccak as well as Keyak v1. They achieve forgery attacks up to 7 rounds (complexity: 265), key recovery attacks up to 7 rounds (complexity: 276) and keystream predictions up to 9 rounds (complexity: 2256). These are the attacks that reach the largest number of rounds of Keccak and Keyak v1.
In their paper, Itai Dinur, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus present some cube attacks on stream cipher and MAC modes of Keccak. The attacks allow to recover the key with a small complexity of 236 when the permutation is reduced to 6 rounds or less.
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.
In this paper, Jérémy Jean and Ivica Nikolić introduce the technique of internal differential boomerang distinguishers. They analyze the symmetry inside the permutation and propose distinguishers up to 8 rounds of Keccak-f with practical complexities.
In this paper, Sukhendu Kuila, Dhiman Saha, Madhumangal Pal and Dipanwita Roy Chowdhury consider distinguishers on Keccak-f where the state is self-symmetric, i.e., it has a period less than 64 along the z-axis. They show distinguishers up to 6 rounds with a complexity of 211.
This paper analyzes two aspects of differential cryptanalysis on Keccak: efficient trails and rebound attacks. In the former, the authors propose a heuristic to build differential trails with a low restriction weight. For Keccak-f, they obtained trails of weight 32, 142 and 709 for 3, 4 and 5 rounds, respectively. In the latter, the paper presents distinguishers making use of the rebound attack for up to 8 rounds of Keccak-f with a complexity of 2491.
The authors of this paper noted a property of the inverse of the non-linear function χ: while χ-1 has algebraic degree 3, the product of any two output bits also has degree 3. This allows to estimate the degree of the Keccak-f rounds more tightly and to extend the zero-sum distinguisher on Keccak-f to size 21575 for 24 rounds.
In this work, the authors present a new upper bounds for the algebraic degree of iterated permutations. While for a small number of rounds the algebraic degree increases exponentially with the number of rounds, for a large number of rounds the algebraic degree only converges exponentially to the maximum value (permutation width minus 1). This improves upon existing zero-sum distinguishers for several SHA-3 candidates. For Keccak-f, it allows extending the zero-sum distinguishers to the full 24-round version, although the size of the zero-sums is 21590 and the distinguisher does not extend to any other type of attack against Keccak.
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. The authors won the third prize for the best cryptanalysis.
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.
In this paper, Jean-Philippe Aumasson and Dmitry Khovratovich look at two possible distinguishers on reduced-round Keccak-f. First, cube testers are applied to detect non-ideal behavior 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).