Today's article comes from the journal of Cybersecurity. The authors are Gao et al., from Information Engineering University, in China. In this paper, they attempt to penetrate the defenses of Xoodyak with what's called a "Meet-in-the-Middle" collision attack.
DOI: 10.1186/s42400-025-00510-1
A few years ago, NIST (the National Institute of Standards and Technology) created the Lightweight Cryptography (LWC) Standardization project. It was a multi-year competition meant to narrow down and identify the best cryptographic algorithms for constrained devices: systems with limited silicon area, limited RAM, limited power, limited energy budget, or limited firmware space. Systems that, despite all those constraints, still need modern security properties like authenticated encryption, message authentication, and hashing. Submissions started coming-in in 2019. 56 were accepted into the first round, 32 to the second round, and 10 into the finals. Those finalists were ASCON, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU, and Xoodyak.
Eventually, ASCON would come out on top. But we've actually already talked about that algorithm before. On a recent episode ("Statistical fault analysis of Ascon: multiple distinguishers and impossible-state exploitation") we looked at how fault injection can be used to push that implementation into abnormal internal states and infer information about the computation underneath. So today we're looking at a different contender on that list. Xoodyak. Why? Because the winner of these kinds of competitions isn't the only algorithm that people will start using in the wild. Each of the top finalists is built for a slightly different use case, and makes slightly different tradeoffs. ASCON being selected as the standard only means that the NIST judges thought it was the best all-around candidate for the majority of contexts. That doesn't mean it's the only one that should be implemented, or that it's the best one for your specific needs.
Xoodyak was designed for the same general case as the others (LWC), but it also takes its own unique position on permutation-based design and primitive reuse. So it's very much worth exploring and analyzing in its own right. Our lens for that exploration today is this paper, in which the authors discuss the scheme and try to penetrate its defenses with what's called a "Meet-in-the-Middle" collision attack. On today's episode we're going to explore all of those moving pieces: what Xoodyak is, how it works, where it's potentially vulnerable, what a collision attack is, how a Meet-in-the-Middle attack works, and finally how successful this particular attack ended up being against it. Let's dive in.
In order to understand "Xoodyak-Hash" (the formal name for this function), we first need to wrap our heads around something called the "Xoodoo permutation". A permutation, in this context, is a fixed transformation from one internal state to another internal state of the same size. It is not yet a hash function, because it does not compress arbitrary-length input into a shorter digest. Instead, it is the low-level mixing engine that a larger hash construction repeatedly calls. Xoodoo takes a 384-bit state and maps it to another 384-bit state. Every possible input state maps to exactly one output state. The security does not come from the permutation throwing information away. The security comes from how the larger mode controls what parts of the state are exposed, what parts remain hidden, and how many rounds of mixing are applied before output is released.
The Xoodoo "state" (the content of the permutation), is organized as a three-dimensional array of bits rather than a simple string. That state has three coordinates:
That gives 4 x 3 x 32 bits, or 384 bits in total. And this organization is not cosmetic. The round function is defined in terms of movement and interaction across those coordinates. Some steps mix information across columns. Some steps shift rows or lanes. And some steps apply a nonlinear operation column by column. This gives the designer very fine control over diffusion: where each bit moves, which neighboring bits it interacts with, and how quickly a local change propagates across the rest of the state.
Each round of Xoodoo is built from a sequence of simple bitwise operations. The theta step mixes column information so that a bit in one location begins to depend on parity information from nearby columns. The rho-west step shifts parts of the state so that bits are moved into new relative positions before the nonlinear layer. The iota step injects a round constant, which prevents each round from being a perfectly symmetric copy of the last one. The chi step is the nonlinear layer. This is the point where the output bits stop being expressible only as simple XOR combinations of earlier bits, because each bit is updated using other bits in the same column. Then rho-east shifts the state again so that the output of the nonlinear layer is redistributed before the next round begins. None of these operations is especially complicated by itself. The security comes from repeating them enough times that input differences become widely distributed and algebraically entangled.
And that distinction between one round and many rounds is central here. A full Xoodoo permutation uses 12 rounds. But cryptanalysis often studies reduced-round versions first, because fewer rounds make it easier to see whether the design has weak diffusion, unexpected symmetry, or exploitable structure. If a bit difference spreads everywhere almost immediately (for example) then it becomes difficult to isolate one part of the computation from another. But if some selected bits can be changed while their effects stay locally contained for several steps, then an attacker may be able to split the computation into two partially independent paths. And that is the opening that this paper focuses on. The authors are not claiming that the full 12-round construction collapses or anything like that. They're just seeing if an attack can exploit the diffusion behavior of a 3-round reduced version.
But hold on. If that's Xoodoo, then what is Xoodyak-Hash? Well it's a sponge-based hash construction built on top of Xoodoo. A sponge construction maintains an internal state and divides that state conceptually into two parts: a visible working part called the "rate", and a hidden security part called the "capacity". Message blocks are absorbed into the rate portion, usually by XORing each block into that portion of the state, and then the internal permutation is applied to mix the absorbed data into the full state. Then, after all message blocks have been absorbed, it enters the squeezing phase, where digest bits are read out from the rate portion, with more permutation calls when more output is needed. In the particular setup discussed in the paper, the state is 384 bits, the rate is 128 bits, the capacity is 256 bits, and the digest size is also 256. And in this study, the authors were trying to see if a specific type of collision attack called a Meet-in-the-Middle could work against that particular setup.
So what's a collision attack then? A collision attack is when the adversary tries to find two different inputs that produce the same hash output. But note, this is different from a preimage attack, where the attacker starts with a specific digest and tries to find any message that maps to it. In a collision attack, the attacker usually gets to choose both messages, and this makes the task easier. For a 256-bit hash output, a generic collision attack (the "birthday attack") is expected to take about 2^128 work, because after that many sampled outputs, the probability of seeing a repeated digest becomes significant. So the cryptanalytic question is not whether collisions exist. They always exist. Infinitely many possible inputs are being mapped into a fixed-size output space, so there will be collisions, that's a certainty. The question is whether the internal structure of the hash lets an attacker find those collisions faster than the birthday strategy. If it does, then the effective collision resistance of the reduced construction is lower than intended.
The attack they're testing here ("Meet-in-the-Middle", not to be confused with "Man-in-the-Middle") is when the attacker splits a cryptographic computation into two parts and tries to make the two parts meet at an intermediate state. Instead of guessing an entire message and running the whole hash from beginning to end, the attacker identifies one set of variable bits whose effects can be computed forward and another set of variable bits whose effects can be computed through a different path, then searches for intermediate values that satisfy a matching condition. In this paper, those variable bit groups are called "neutral sets". The blue neutral set and the red neutral set are chosen so that, under certain fixed conditions, each side can be evaluated without immediately depending on the other. The attack then stores one side of the computation in a table, computes the other side, and checks whether the two sides agree at the matching points. The more independent degrees of freedom the attacker has, and the more matching bits can be checked, the more efficiently the search space can be filtered.
The hard part is finding neutral sets that stay independent long enough to be useful. Remember, Xoodoo is designed specifically to diffuse information, so arbitrary chosen bits will quickly interact with each other through the linear and nonlinear layers. And if the blue and red sets mix too early, the meet-in-the-middle split collapses, because neither side can be computed independently anymore. So here the authors use MILP (a mathematical optimization technique), to search for valid attack structures automatically. In this setting, the MILP model is not learning from data. It is encoding the propagation rules of the construction instead: which bits are constant, which bits depend on the blue neutral set, which bits depend on the red neutral set, which bits depend on both, and which relationships become nonlinear. And an optimizer is then used to search for a configuration where the blue and red paths remain sufficiently separated and still produce enough matching conditions to filter candidates efficiently.
So, what happened when the authors tried to execute this against Xoodyak-Hash? Well, something a bit surprising. They successfully improved on the best known collision attack on the 3-round hash. Earlier work used a two-stage heuristic: first pick one neutral set that appears to have weak diffusion, then fix that choice and ask the MILP model to complete the full attack structure. The authors argued that the earlier first-stage objective was too local. It tried to minimize one immediate diffusion measure, but that did not necessarily produce the best full-round characteristic. Their replacement was an overall-weak-diffusion structure searching strategy. Instead of only asking which initial choice looks weakest right away, it tries to select a neutral set whose diffusion remains more favorable across the whole collision path. That makes it more likely that the second-stage MILP search can find a matching with a higher degree and better usable degrees of freedom. And it works!
But what does this mean? Is this conclusive evidence that Xoodyak is broken? Does this make Xoodyak unusable for lightweight hashing? No, definitely not. Again, the attack is against the 3-round version, and the full Xoodoo permutation uses 12. Reduced-round attacks are a normal part of cryptographic evaluation. They help researchers estimate the security margin between the strongest known attacks and the full deployed design. But not necessarily more than that. These results do not mean that normal users can now generate practical collisions against full Xoodyak. Far from it. The takeaway here is more nuanced. That:
But we can't really extrapolate beyond that without overrunning our skis.
Want to dive deeper? Make sure you download the paper. The authors go much further into the MILP encoding, the representation of constant bits and neutral bits, the complexity accounting for each stage of the attack, and the comparison of Xoodyak-like variants under different linear-layer shift parameters.