Third-party cryptanalysis

This page lists all the third-party cryptanalysis results that we know of on Keccak and Xoodoo, including FIPS 202 and SP 800-185 instances, KangarooTwelve, Ketje, Keyak, Kravatte, Xoofff and Xoodyak. 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:

  • analysis of Keccak (covering also KangarooTwelve, FIPS 202 and SP 800-185 instances) and Xoodyak in the context of (unkeyed) hashing;
  • analysis that is more specifically targetting keyed modes of use of Keccak and Xoodoo-based schemes, including Ketje, Keyak, Kravatte, Xoofff and Xoodyak;
  • analysis on the (reduced-round) Keccak-f and Xoodoo permutations that does not extend to any of the aforementioned cryptographic functions.

In each category, the most recent results come first.

Analysis of unkeyed modes

First, the Crunchy Crypto Collision and Pre-image Contest contains third-party cryptanalysis results with practical complexities.

R. Wang, X. Li, J. Gao, H. Li and B. Wang, Allocating Rotational Cryptanalysis based Preimage Attack on 4-round Keccak-224 for Quantum Setting, IACR Cryptol. ePrint Arch., 2022

In this paper, Runsong Wang, Xuelian Li, Juntao Gao, Hui Li and Baocang Wang show preimage attacks obtained from rotational distinguishers and linearization techniques. They focus on Keccak[r=1152, c=448] reduced to 4 rounds, with an output length of 224 bits. They show attacks both in the classical and in the quantum setting. In the former, the complexity of their attack is 2218, while in the latter it is 2110, so faster than a Grover search.

S. Huang, O. A. Ben-Yehuda, O. Dunkelman and A. Maximov, Finding Collisions against 4-Round SHA-3-384 in Practical Time, IACR Trans. Symmetric Cryptol., 2022

In this paper, Senyang Huang, Orna Agmon Ben-Yehuda, Orr Dunkelman and Alexander Maxim present a collision attack on Keccak[r=832, c=768] (SHA3-384) reduced to 4 rounds. The complexity of the attack is practical, just above 259, and much lower than the previous result on the same instance (2147 by Dinur et al.).

L. He, X. Lin and H. Yu, Improved Preimage Attacks on Round-Reduced Keccak-384/512 via Restricted Linear Structures, IACR Cryptol. ePrint Arch., 2022

In this paper, Le He, Xiaoen Lin and Hongbo Yu improve the complexity of preimage attacks against round-reduced Keccak with a high capacity (c=768 or 1024). For instance, the complexity of a preimage attack on Keccak[r=832, c=768] reduced to 2 rounds is now 228 (instead of 289 previously). On other instances, the complexity remains theoretical, e.g., for Keccak[r=576, c=1024] reduced to 3 rounds the complexity is now 2426 (instead of 2475 previously).

R. Preston, Applying Grover's Algorithm to Hash Functions: A Software Perspective, CoRR, 2022

In this paper, Richard Preston looks at the cost of finding short (e.g., 16-bit) preimages on Keccak using a quantum computer. He improves the quantum implementation of Keccak to reduce the number of qubits required.

J. Guo, G. Liu, L. Song and Y. Tu, Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks against 6-Round SHA-3, IACR Cryptol. ePrint Arch., 2022

In this paper, Jian Guo, Guozhen Liu, Ling Song and Yi Tu show a collision attack on Keccak, and more precisely SHAKE128, reduced to 6 rounds. The collision takes time 2123.5 and is the first one reaching 6 rounds with standard parameters. Next to this, the authors present quantum collision attacks with complexities 261.4, 296.15 and 2102.65 for Keccak[r=1344, c=256] (SHAKE128), Keccak[r=1152, c=448] (SHA3-224) and Keccak[r=1088, c=512] (SHA3-256), respectively, again reduced to 6 rounds.

R. Wang, X. Li, J. Gao, H. Li and B. Wang, Quantum rotational cryptanalysis for preimage recovery of round-reduced Keccak, IACR Cryptol. ePrint Arch., 2022

In this paper, Runsong Wang, Xuelian Li, Juntao Gao, Hui Li and Baocang Wang propose a quantum algorithm exploiting rotational cryptanalysis to mount a preimage attack on Keccak reduced to 4 rounds. The complexity of the attack is slightly below that of the generic quantum attacks and is respectively given by 2112.57, 2128.57, 2191.49 and 2255.08 for output lengths 224, 256, 384 and 512 bits, respectively, and a capacity twice the output length.

C. Wei, C. Wu, X. Fu, X. Dong, K. He, J. Hong and X. Wang, Preimage attacks on 4-round Keccak by solving multivariate quadratic systems, IACR Cryptol. ePrint Arch., 2021

In this paper, Congming Wei, Chenhao Wu, Ximing Fu, Xiaoyang Dong, Kai He, Jue Hong and Xiaoyun Wang revisit the Crossbred algorithm for solving a Boolean multivariate quadratic system and apply it to finding preimages on reduced-round Keccak. The complexity for Keccak[r=1088, c=512] reduced to 4 rounds and output length 256 bits is 2214.

X. Lin, L. He and H. Yu, Improved Preimage Attacks on 3-Round Keccak-224/256, IACR Trans. Symmetric Cryptol., 2021

In this paper, Xiaoen Lin, Le He and Hongbo Yu improve upon the complexity of preimage attacks on Keccak[r=1152, c=448] and Keccak[r=1088, c=512] reduced to 3 rounds, with 224 and 256 bits of output, respectively. Compared to the previous methods, they generate the preimage in two blocks instead of one. The complexity of their attack is 232 and 265, respectively.

R. H. Boissier, C. Noûs and Y. Rotella, Algebraic Collision Attacks on Keccak, IACR Trans. Symmetric Cryptol., 2021

In this paper, Rachelle Heim Boissier and Yann Rotella explore collision attacks on lightweight instances of Keccak, namely, Keccak[r=40, c=160], Keccak[r=72, c=128] and Keccak[r=144, c=256] reduced to 2 rounds. They use algebraic and linearization techniques and obtain complexities of 273, 252.2 and 2101.5 for the different instances, respectively.

L. He, X. Lin and H. Yu, Improved Preimage Attacks on 4-Round Keccak-224/256, IACR Trans. Symmetric Cryptol., 2021

In this paper, Le He, Xiaoen Lin and Hongbo Yu provide a preimage attack on Keccak[r=1152, c=448] and Keccak[r=1088, c=512] reduced to 4 rounds, with 224 and 256 bits of output, respectively. They improve the current linearization techniques and decrease the complexity down to 2192 and 2218, respectively.

S. Suryawanshi, D. Saha and S. Sachan, New Results on the SymSum Distinguisher on Round-Reduced SHA3, Africacrypt, 2020

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.

F. Liu, T. Isobe, W. Meier and Z. Yang, Algebraic Attacks on Round-Reduced Keccak/Xoodoo, IACR Cryptol. ePrint Arch., 2020

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.

J. Guo, G. Liao, G. Liu, M. Liu, K. Qiao and L. Song, Practical Collision Attacks against Round-Reduced SHA-3, J. Cryptol., 2020

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.

S. Huang, X. Wang, G. Xu, M. Wang and J. Zhao, New Distinguisher on Reduced-Round Keccak Sponge Function, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2019

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.

M. S. Rajasree, Cryptanalysis of Round-Reduced Keccak using Non-Linear Structures, Indocrypt, 2019

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.

T. Li and Y. Sun, Preimage Attacks on Round-Reduced Keccak-224/256 via an Allocating Approach, Eurocrypt, 2019

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.

S. V. Goncharov, Using fuzzy bits and neural networks to partially invert few rounds of some cryptographic hash functions, CoRR, 2019

In this paper, Sergij V. Goncharov train neural networks using fuzzy bit values to mount a preimage attack. This works up to one round.

R. Kumar, N. Mittal and S. Singh, Cryptanalysis of 2 Round Keccak-384, Indocrypt, 2018

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.

Y. Chen and X. Gao, Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems, IACR Cryptology ePrint Archive, 2018

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.

R. Kumar, M. S. Rajasree and H. AlKhzaimi, Cryptanalysis of 1-Round Keccak, Africacrypt, 2018

In this paper, Rajendra Kumar, Mahesh Sreekumar Rajasree and Hoda AlKhzaimi present preimage and collision attacks on Keccak[r=576, c=1024] reduced to 1 round with a very small complexity.

T. Li, Y. Sun, M. Liao and D. Wang, Preimage Attacks on the Round-reduced Keccak with Cross-linear Structures, IACR Trans. Symmetric Cryptol., 2017

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.

L. Song, G. Liao and J. Guo, Non-Full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak, Crypto, 2017

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.

K. Qiao, L. Song, M. Liu and J. Guo, New Collision Attacks on Round-Reduced Keccak, Eurocrypt, 2017

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[1600] or Keccak-f[800] reduced to 5 rounds. This includes the 5-round collision challenges in the Crunchy Contest.

D. Saha, S. Kuila and D. R. Chowdhury, SymSum: Symmetric-Sum Distinguishers Against Round Reduced SHA3, IACR Trans. Symmetric Cryptol., 2017

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.

M. Amy, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent and J. M. Schanck, Estimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3, Selected Areas in Cryptography, 2016

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).

J. Guo, M. Liu and L. Song, Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak, Asiacrypt, 2016

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[1600].

P. Morawiecki, Malicious Keccak, IACR Cryptology ePrint Archive, 2015

In this article, Paweł Morawiecki investigates a variant of Keccak with different round constants. This is an interesting experiment providing third-party motivation for the choice of the Keccak-f round constants.

S. Das and W. Meier, Differential Biases in Reduced-Round Keccak, Africacrypt, 2014

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.

P. Morawiecki, J. Pieprzyk, M. Srebrny and M. Straus, Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis, IACR Cryptology ePrint Archive, 2013

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.

S. Kölbl, F. Mendel, T. Nad and M. Schläffer, Differential Cryptanalysis of Keccak Variants, IMA Int. Conf., 2013

In this paper, Stefan Kölbl, Florian Mendel, Tomislav Nad and Martin Schläffer analyze the differential properties of Keccak-f[800] and Keccak-f[1600]. 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[800] and c≤640 when using Keccak-f[1600].

I. Dinur, O. Dunkelman and A. Shamir, Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials, FSE, 2013

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[1600] and with complexity 2115 for 5 rounds.

P. Morawiecki, J. Pieprzyk and M. Srebrny, Rotational Cryptanalysis of Round-Reduced Keccak, FSE, 2013

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[1600] 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[1600].

P. Morawiecki and M. Srebrny, A SAT-based preimage analysis of reduced Keccak hash functions, Inf. Process. Lett., 2013

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.

I. Dinur, O. Dunkelman and A. Shamir, New Attacks on Keccak-224 and Keccak-256, FSE, 2012 (also published in Journal of Cryptology 27(2) (pp. 183-209), 2014)

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.

M. Naya-Plasencia, A. Röck and W. Meier, Practical Analysis of Reduced-Round Keccak, Indocrypt, 2011

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.

D. J. Bernstein, Second preimages for 6 (7? (8??)) rounds of Keccak?, NIST hash forum, 2010

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.

Analysis of keyed modes

O. Dunkelman and A. Weizman, Differential-Linear Cryptanalysis on Xoodyak, NIST LWC Workshop, 2022

In this paper, Orr Dunkelman and Ariel Weizman use differential-linear cryptanalysis techniques to mount a distinguisher on Xoodoo reduced to 4 and 5 rounds. They present a key recovery attack on Xoodyak reduced to 4 rounds, with a practical complexity of 223, as well as a related-key attack on Xoodyak reduced to 5 rounds (222).

T. Cui and L. Grassi, Algebraic Key-Recovery Attacks on Reduced-Round Xoofff, SAC, 2020

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.

H. Zhou, R. Zong, X. Dong, K. Jia and W. Meier, Interpolation Attacks on Round-Reduced Elephant, Kravatte and Xoofff, IACR Cryptol. ePrint Arch., 2020

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[200]. 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.

H. Zhou, Z. Li, X. Dong, K. Jia and W. Meier, Practical Key-recovery Attacks on Round-Reduced Ketje Jr, Xoodoo-AE and Xoodyak, Comput. J., 2020

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.

X. Bonnetain, A. Hosoyamada, M. Naya-Plasencia, Y. Sasaki and A. Schrottenloher, Quantum Attacks Without Superposition Queries: The Offline Simon's Algorithm, Asiacrypt, 2019

In this paper, Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki and André Schrottenloher apply a novel quantum attack that uses Simon's algorithm in a way that does not require queries in quantum superposition. Applied to Kravatte and Xoofff, their attack would cost 2533 data and time and 2128 data, respectively. They also discuss applications to sponge functions, but with a cost above 2c.

F. Liu, Z. Cao and G. Wang, Finding Ordinary Cube Variables for Keccak-MAC with Greedy Algorithm, IWSEC, 2019

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.

Z. Li, X. Dong, W. Bi, K. Jia, X. Wang and W. Meier, New Conditional Cube Attack on Keccak Keyed Modes, IACR Trans. Symmetric Cryptol., 2019

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.

W. Bi, X. Dong, Z. Li, R. Zong and X. Wang, MILP-aided Cube-attack-like Cryptanalysis on Keccak Keyed Modes, Des. Codes Cryptography, 2019

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).

L. Song and J. Guo, Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP, IACR Trans. Symmetric Cryptol., 2018

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.

T. Fuhr, M. Naya-Plasencia and Y. Rotella, State-Recovery Attacks on Modified Ketje Jr, IACR Trans. Symmetric Cryptol., 2018

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.

C. Chaigneau, T. Fuhr, H. Gilbert, J. Guo, J. Jean, J. Reinhard and L. Song, Key-Recovery Attacks on Full Kravatte, IACR Trans. Symmetric Cryptol., 2018

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.

C. Ye and T. Tian, New Insights into Divide-and-Conquer Attacks on the Round-Reduced Keccak-MAC, IACR Cryptology ePrint Archive, 2018

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].

L. Song, J. Guo, D. Shi and S. Ling, New MILP Modeling: Improved Conditional Cube Attacks on Keccak-Based Constructions, Asiacrypt, 2018

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.

Z. Li, W. Bi, X. Dong and X. Wang, Improved Conditional Cube Attacks on Keccak Keyed Modes with MILP Method, Asiacrypt, 2017

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.

X. Dong, Z. Li, X. Wang and L. Qin, Cube-like Attack on Round-Reduced Initialization of Ketje Sr, IACR Trans. Symmetric Cryptol., 2017

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).

S. Huang, X. Wang, G. Xu, M. Wang and J. Zhao, Conditional Cube Attack on Reduced-Round Keccak Sponge Function, Eurocrypt, 2017

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[1600], 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.

C. Dobraunig, M. Eichlseder and F. Mendel, Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates, Asiacrypt, 2015

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[1600], 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.

I. Dinur, P. Morawiecki, J. Pieprzyk, M. Srebrny and M. Straus, Cube Attacks and Cube-Attack-Like Cryptanalysis on the Round-Reduced Keccak Sponge Function, Eurocrypt, 2015

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.

I. Dinur, P. Morawiecki, J. Pieprzyk, M. Srebrny and M. Straus, Practical Complexity Cube Attacks on Round-Reduced Keccak Sponge Function, IACR Cryptology ePrint Archive, 2014

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.

J. Lathrop, Cube Attacks on Cryptographic Hash Functions, 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.

Analysis of the Keccak-f and Xoodoo permutations

K. Hu and T. Peyrin, Revisiting Higher-Order Differential(-Linear) Attacks from an Algebraic Perspective – Applications to Ascon, Grain v1, Xoodoo, and ChaCha, IACR Cryptol. ePrint Arch., 2022

In this paper, Kai Hu and Thomas Peyrin present a second-order differential-linear distinguisher for Xoodoo reduced to 4 rounds.

T. Omland and P. Stanica, Permutation rotation-symmetric Sboxes, liftings and affine equivalence, IACR Cryptol. ePrint Arch., 2022

In this paper, Tron Omland and Pantelimon Stanica investigate permutation shift-invariant vectorial Boolean functions that generalize Keccak's χ mapping.

E. Bellini and R. H. Makarim, Functional Cryptanalysis: Application to reduced-round Xoodoo, IACR Cryptol. ePrint Arch., 2022

In this paper, Emanuele Bellini and Rusydi H. Makarim introduce functional cryptanalysis as a generalization of other techniques such as differential and rotational cryptanalysis. They show a functional distinguisher on 3 rounds of Xoodoo, which works better than a differential distinguisher.

Y. Liu, S. Sun and C. Li, Rotational cryptanalysis from a differential-linear perspective: practical distinguishers for round-reduced FRIET, Xoodoo, and Alzette, Eurocrypt, 2021

In this paper, Yunwen Liu, Siwei Sun and Chiao Li revisit the rotational cryptanalysis from the perspective of differential-linear cryptanalysis. They apply this technique to find rotational differential-linear distinguishers with correlation 1 on Xoodoo reduced to 4 rounds.

H. Yan, X. Lai, L. Wang, Y. Yu and Y. Xing, New zero-sum distinguishers on full 24-round Keccak-f using the division property, IET Inf. Secur., 2019

In this paper, Hailun Yan, Xuejia Lai, Lei Wang, Yu Yu and Yiran Xing propose a new zero-sum distinguisher of full 24-round Keccak-f by using the division property, a generalized integral property that was initially used in the integral cryptanalysis of symmetric-key algorithms. Extending on work done by Todo at CRYPTO 2015, they prove a propagation rule of the division property under the assumption that the S-box specification is known to attackers. They apply this to S-boxes in Keccak-f and Ascon. For full-round Keccak-f, this brings the best distinguisher to a complexity of 21573.

G. Liu, W. Qiu and Y. Tu, New Techniques for Searching Differential Trails in Keccak, IACR Trans. Symmetric Cryptol., 2019

In this paper, Guozhen Liu, Weidong Qiu and Yi Tu introduce new algorithms to cover 3-round trail cores in Keccak-f with propagation weight up to 53.

M. Li and L. Cheng, Distinguishing Property for Full Round Keccak-f Permutation, CISIS, 2017

In this paper, Maolin Li and Lu Cheng apparently reduced the size of a zero-sum partition to 21573 elements.

J. Jean and I. Nikolić, Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation, Fast Software Encryption, 2015

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[1600] with practical complexities.

S. Kuila, D. Saha, M. Pal and D. R. Chowdhury, Practical Distinguishers against 6-Round Keccak-f Exploiting Self-Symmetry, Africacrypt, 2014

In this paper, Sukhendu Kuila, Dhiman Saha, Madhumangal Pal and Dipanwita Roy Chowdhury consider distinguishers on Keccak-f[1600] 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.

A. Duc, J. Guo, T. Peyrin and L. Wei, Unaligned Rebound Attack: Application to Keccak, Fast Software Encryption, 2012

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[1600], 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[1600] with a complexity of 2491.

M. Duan and X. Lai, Improved zero-sum distinguisher for full round Keccak-f permutation, IACR Cryptology ePrint Archive, 2011

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[1600] to size 21575 for 24 rounds.

C. Boura, A. Canteaut and C. De Cannière, Higher-Order Differential Properties of Keccak and Luffa, Fast Software Encryption, 2011

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.

C. Boura and A. Canteaut, Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256, Selected Areas in Cryptography, 2010

In this paper, Christina Boura and Anne Canteaut extend their zero-sum distinguishers to 20 rounds.

C. Boura and A. Canteaut, A zero-sum property for the Keccak-f permutation with 18 rounds, ISIT, 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. The authors won the third prize for the best cryptanalysis.

J. Aumasson and W. Meier, Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi, rump session of CHES, 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.

J. Aumasson and D. Khovratovich, First Analysis of Keccak, NIST hash forum, 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 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).