International Association
for Cryptologic Research

Arithmetization-Oriented hash functions are optimized for their verification to be efficiently implemented within various proof systems, but they are often too slow when evaluated on a regular machine. To solve this problem for some specific protocols, some recent proposals introduced a new type of operations: the Split- And-Lookup. The idea in this case is to “split” prime field elements into smaller integers, e.g. by simply considering their binary representations, and then applying a permutation on each such integer before rebuilding a field element from them. Such operations are fast to evaluate, and of a very high degree in the field, which hopefully implies a high resistance against algebraic attacks.In this paper, we investigate the security offered by such components using two distinct approaches. First, we provide a detailed analysis of the cryptographic properties of the Split-And-Lookup construction. In particular, we present technique to efficiently compute its Fourier coefficients and linear approximation probabilities, and use them to show linear approximations of the S-boxes of Skyscraper, Monolith, Tip5, and Reinforced Concrete with surprisingly high probabilities. We also present our own S-boxes that could be used as a drop-in replacement for those of Monolith and Tip5, and would provide enhanced security and performances in some contexts. Finally, we turn our attention to the primitives themselves, and present a freestart partial preimage attack on a version of Tip5 reduced to four out of five rounds, where the attacker is allowed to control only one word in the initialization vector. This can be turned into a collision attack against a four-round version of Tip5 with a capacity reduced to 320 bits out of 384, though it should still provide the same security level as the original hash function. Despite the high degree of the Split-And- Lookup construction, we use an algebraic attack that essentially goes “around” these components.While these results do not directly threaten the security of full-round primitives, they further the understanding of the cryptographic properties of these new operations, and of the actual impact they have on the security against various attacks.

In recent years, many hash functions have been introduced to satisfy the pressing need of some zero-knowledge protocols for such primitives allowing a low degree verification of their round function when arithmetized over a large field.While this can be achieved by restricting their sub-components to low-degree functions (and their inverse), the newest primitives in this category also leverage the intricacies of some proof systems to use “Split-and-Lookup” non-linear functions that essentially apply a small S-box in parallel over the binary representation of a field element.Such components excel at hindering attacks relying on polynomial system solving, but they offer poor security against statistical attacks. On the other hand, low degree monomials offer the opposite guarantees, being strong against statistical attacks. Several primitives have recently been proposed that combine such components in different ways in order to get the best from both.In this paper, we target such primitives by relying on the low degree components to allow a low-cost polynomial solving step. The weakness of Split-and-Lookups against linear attacks is used to simplify these systems, and their weakness against differential attacks is then used to propagate across many rounds the differential patterns obtained during polynomial solving. We instantiate this general approach by attacking round-reduced Monolith, and providing a distinguisher on full-round Skyscraper. These result then shed some light on how to best combine the different types of components to achieve the highest security.