International Association
for Cryptologic Research

Since the seminal works by Aoki and Sasaki, meet-in-the-middle (MITM) attacks are known to be effective for preimage and collision attacks of hash functions. At Eurocrypt'21, Bao et al. initiated the automation of such preimage and collision MITM attacks for AES-like hash functions, which brought up models that could capture larger search spaces than what could be studied manually before. Follow-up works then integrated several techniques such as guess-and-determine, bidirectional propagation, and states in superposition. However, this research direction has been far from complete. In previous models, initial states were limited to single independent states and were not allowed to have bytes in superposition. Moreover, S-box inputs in superposition could not be propagated unless the full byte was guessed. Besides more advanced techniques, the general question of how the state-of-the-art results could be improved remained of high interest. In this work, we lift some of these limitations with novel techniques: We introduce the S-box linearization technique for automated MITM preimage attacks so that a superposition of bytes active in both the for- and the backward neutral chunk can pass through an S-box. We propose what we call distributed initial structures that allow more general definitions of initial states from multiple states to enlarge the search space. Beyond those, we exploit the similarity between encryption function and key schedule in constructions such as Whirlpool, and Streebog in our models to reduce the consumed degrees of freedom. To better integrate the proposed techniques, we present a refined and lightweight MILP-based search model. We illustrate the effectiveness of our enhanced MITM framework with improved preimage attacks on hash-function modes of standardized AES-like designs. We obtain the first preimage attacks on 10-round AES-192, 10-round Rijndael-192/256, and 7.75-round Whirlpool. Moreover, we can reduce time or memory complexities for attacks on 5- and 6-round Whirlpool, and 7.5- and 8.5-round Streebog. We show that our model is not limited to preimage attacks with improved collision attacks on 6- and 6.5-round Whirlpool.

The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers \emph{except} for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In this paper, we develop a full-fledged automatic framework integrating all known techniques (differential enumeration, key-dependent-sieve, and key bridging, etc) for the DS-MITM attack that can produce key-recovery attacks directly rather than only search for distinguishers. Moreover, we develop a new technique that is able to exploit partial key additions to generate more linear relations beneficial to the attacks. We apply the framework to the SKINNY family of block ciphers and significantly improved results are obtained. In particular, all known DS-MITM attacks on the respective versions of SKINNY are improved by at least 2 rounds, and the data, memory, or time complexities of some attacks are reduced even compared to previous best attacks penetrating less rounds.

The Meet-in-the-Middle approach is one of the most powerful cryptanalysis techniques, demonstrated by its applications in preimage attacks on the full MD4, MD5, Tiger, HAVAL, and Haraka-512 v2 hash functions, and key recovery of the full block cipher KTANTAN. The success relies on the separation of a primitive into two independent chunks, where each active cell of the state is used to represent only one chunk or is otherwise considered unusable once mixed. We observe that some of such cells are linearly mixed and can be as useful as the independent ones. This leads to the introduction of superposition states and a whole suite of accompanied techniques, which we incorporate into the MILP-based search framework proposed by Bao et al. at EUROCRYPT 2021 and Dong et al. at CRYPTO 2021, and find applications on a wide range of AES-like hash functions and block ciphers.

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance vary from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we investigate the rectangle key recovery in depth and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Notably, it not only covers the four previous rectangle key recovery algorithms, but also unveils five types of new attacks which were missed previously. Along with the new key recovery algorithm, we propose a framework for automatically finding the best attacking parameters, with which the time complexity of the rectangle attack will be minimized using the new algorithm. To demonstrate the efficiency of the new key recovery algorithm, we apply it to Serpent, CRAFT, SKINNY and Deoxys-BC-256 based on existing distinguishers and obtain a series of improved rectangle attacks.

The double boomerang connectivity table (DBCT) is a new table proposed recently to capture the behavior of two consecutive S-boxes in boomerang attacks. In this paper, we observe an interesting property of DBCT of S-box that the ladder switch and the S-box switch happen in most cases for two continuous S-boxes, and for some S-boxes only S-box switch and ladder switch are possible. This property implies an additional criterion for S-boxes to resist the boomerang attacks and provides as well a new evaluation direction for an S-box. Using an extension of the DBCT, we verify that some boomerang distinguishers of TweAES and Deoxys are flawed. On the other hand, inspired by the property, we put forward a formula for estimating boomerang cluster probabilities. Furthermore, we introduce the first model to search for boomerang distinguishers with good cluster probabilities. Applying the model to CRAFT, we obtain 9-round and 10-round boomerang distinguishers with a higher probability than that of previous works.

The Meet-in-the-Middle (MITM) preimage attack is highly effective in breaking the preimage resistance of many hash functions, including but not limited to the full MD5, HAVAL, and Tiger, and reduced SHA-0/1/2. It was also shown to be a threat to hash functions built on block ciphers like AES by Sasaki in 2011. Recently, such attacks on AES hashing modes evolved from merely using the freedom of choosing the internal state to also exploiting the freedom of choosing the message state. However, detecting such attacks especially those evolved variants is difficult. In previous works, the search space of the configurations of such attacks is limited, such that manual analysis is practical, which results in sub-optimal solutions. In this paper, we remove artificial limitations in previous works, formulate the essential ideas of the construction of the attack in well-defined ways, and translate the problem of searching for the best attacks into optimization problems under constraints in Mixed-Integer-Linear-Programming (MILP) models. The MILP models capture a large solution space of valid attacks; and the objectives of the MILP models are attack configurations with the minimized computational complexity. With such MILP models and using the off-the-shelf solver, it is efficient to search for the best attacks exhaustively. As a result, we obtain the first attacks against the full (5-round) and an extended (5.5-round) version of Haraka-512 v2, and 8-round AES-128 hashing modes, as well as improved attacks covering more rounds of Haraka-256 v2 and other members of AES and Rijndael hashing modes.

As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with lightweight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if At is MDS, then one can implement A instead of At to achieve the MDS property at the expense of an increased latency with t clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a 4 × 4 block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest 4 × 4 iterative MDS block matrix (whose entries or blocks are 4 × 4 binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.

CRAFT is a lightweight tweakable block cipher proposed at FSE 2019, which allows countermeasures against Differential Fault Attacks to be integrated into the cipher at the algorithmic level with ease. CRAFT employs a lightweight and involutory S-box and linear layer, such that the encryption function can be turned into decryption at a low cost. Besides, the tweakey schedule algorithm of CRAFT is extremely simple, where four 64-bit round tweakeys are generated and repeatedly used. Due to a combination of these features which makes CRAFT exceedingly lightweight, we find that some input difference at a particular position can be preserved through any number of rounds if the input pair follows certain truncated differential trails. Interestingly, in contrast to traditional differential analysis, the validity of this invariant property is affected by the positions where the constant additions take place. We use this property to construct “weak-tweakey” truncated differential distinguishers of CRAFT in the single-key model. Subsequently, we show how the tweak additions allow us to convert these weak-tweakey distinguishers into ordinary secret-key distinguishers based on which key-recovery attacks can be performed. Moreover, we show how to construct MILP models to search for truncated differential distinguishers exploiting this invariant property. As a result, we find a 15-round truncated differential distinguisher of CRAFT and extend it to a 19-round key-recovery attack with 260.99 data, 268 memory, 294.59 time complexity, and success probability 80.66%. Also, we find a 14-round distinguisher with probability 2−43 (experimentally verified), a 16-round distinguisher with probability 2−55, and a 20-round weak-key distinguisher (2118 weak keys) with probability 2−63. Experiments on round-reduced versions of the distinguishers show that the experimental probabilities are sometimes higher than predicted. Finally, we note that our result is far from threatening the security of the full CRAFT.

This paper presents the first third-party security analysis of TinyJAMBU, which is one of 32 second-round candidates in NIST’s lightweight cryptography standardization process. TinyJAMBU adopts an NLFSR based keyed-permutation that computes only a single NAND gate as a non-linear component per round. The designers evaluated the minimum number of active AND gates, however such a counting method neglects the dependency between multiple AND gates. There also exist previous works considering such dependencies with stricter models, however those are known to be too slow. In this paper, we present a new model that provides a good balance of efficiency and accuracy by only taking into account the first-order correlation of AND gates that frequently occurs in TinyJAMBU. With the refined model, we show a 338-round differential with probability 2−62.68 that leads to a forgery attack breaking 64-bit security. This implies that the security margin of TinyJAMBU with respect to the number of unattacked rounds is approximately 12%. We also show a differential on full 384 rounds with probability 2−70.64, thus the security margin of full rounds with respect to the data complexity, namely the gap between the claimed security bits and the attack complexity, is less than 8 bits. Our attacks also point out structural weaknesses of the mode that essentially come from the minimal state size to be lightweight.

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum attack on hash functions -- a quantum version of the rebound attack exploiting differentials whose probabilities are too low to be useful in the classical setting. This work opens up a new perspective toward the security of hash functions against quantum attacks. In particular, it tells us that the search for differentials should not stop at the classical birthday bound. Despite these interesting and promising implications, the concrete attacks described by Hosoyamada and Sasaki make use of large quantum random access memories (qRAMs), a resource whose availability in the foreseeable future is controversial even in the quantum computation community. Without large qRAMs, these attacks incur significant increases in time complexities. In this work, we reduce or even avoid the use of qRAMs by performing a quantum rebound attack based on differentials with non-full-active super S-boxes. Along the way, an MILP-based method is proposed to systematically explore the search space of useful truncated differentials with respect to rebound attacks. As a result, we obtain improved attacks on \aes-\texttt{MMO}, \aes-\texttt{MP}, and the first classical collision attacks on 4- and 5-round \grostl-\texttt{512}. Interestingly, the use of non-full-active super S-box differentials in the analysis of \aes-\texttt{MMO} gives rise to new difficulties in collecting enough starting points. To overcome this issue, we consider attacks involving two message blocks to gain more degrees of freedom, and we successfully compress the qRAM demand of the collision attacks on \texttt{AES}-\texttt{MMO} and \texttt{AES}-\texttt{MP} (EUROCRYPT 2020) from $2^{48}$ to a range from $2^{16}$ to $0$, while still maintaining a comparable time complexity. To the best of our knowledge, these are the first dedicated quantum attacks on hash functions that slightly outperform Chailloux, Naya-Plasencia, and Schrottenloher's generic quantum collision attack (ASIACRYPT 2017) in a model where large qRAMs are not available. This work demonstrates again how a clever combination of classical cryptanalytic technique and quantum computation leads to improved attacks, and shows that the direction pointed out by Hosoyamada and Sasaki deserves further investigation.

We show that the correlation of any quadratic Boolean function can be read out from its so-called disjoint quadratic form. We further propose a polynomial-time algorithm that can transform an arbitrary quadratic Boolean function into its disjoint quadratic form. With this algorithm, the exact correlation of quadratic Boolean functions can be computed efficiently.We apply this method to analyze the linear trails of $$\mathsf {MORUS}$$ (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of $$\mathsf {MORUS}$$-like key-stream generators. In our model, any tool for finding linear trails of block ciphers can be used to search for trails of $$\mathsf {MORUS}$$-like key-stream generators. As a result, a set of trails with correlation $$2^{-38}$$ is identified for all versions of full $$\mathsf {MORUS}$$, while the correlations of previously published best trails for $$\mathsf {MORUS}$$-640 and $$\mathsf {MORUS}$$-1280 are $$2^{-73}$$ and $$2^{-76}$$ respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on $$\mathsf {MORUS}$$-1280-256 from $$2^{152}$$ to $$2^{76}$$. These new trails also lead to the first distinguishing and message-recovery attacks on $$\mathsf {MORUS}$$-640-128 and $$\mathsf {MORUS}$$-1280-128 with surprisingly low complexities around $$2^{76}$$.Moreover, we observe that the condition for exploiting these trails in an attack can be more relaxed than previously thought, which shows that the new trails are superior to previously published ones in terms of both correlation and the number of ciphertext blocks involved.

Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selçuk meet-in-the-middle ($$\mathcal {DS}$$-$$\mathsf {MITM}$$) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque’s work on $$\mathcal {DS}$$-$$\mathsf {MITM}$$ analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack based on general constraint programming, which allows the cryptanalysts to state the problem at a high level without having to say how it should be solved. Our method is not only able to enumerate distinguishers but can also partly automate the key-recovery process. This approach makes the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ cryptanalysis more straightforward and easier to follow, since the resolution of the problem is delegated to off-the-shelf constraint solvers and therefore decoupled from its formulation. We apply the method to SKINNY, TWINE, and LBlock, and we get the currently known best $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attacks on these ciphers. Moreover, to demonstrate the usefulness of our tool for the block cipher designers, we exhaustively evaluate the security of $$8! = 40320$$ versions of LBlock instantiated with different words permutations in the F functions. It turns out that the permutation used in the original LBlock is one of the 64 permutations showing the strongest resistance against the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack. The whole process is accomplished on a PC in less than 2 h. The same process is applied to TWINE, and similar results are obtained.

In this paper, we propose a new MILP modeling to find better or even optimal choices of conditional cubes, under the general framework of conditional cube attacks. These choices generally find new or improved attacks against the keyed constructions based on Keccak permutation and its variants, including Keccak-MAC, KMAC, Keyak, and Ketje, in terms of attack complexities or the number of attacked rounds. Interestingly, conditional cube attacks were applied to round-reduced Keccak-MAC, but not to KMAC despite the great similarity between Keccak-MAC and KMAC, and the fact that KMAC is the NIST standard way of constructing MAC from SHA-3. As examples to demonstrate the effectiveness of our new modeling, we report key recovery attacks against KMAC128 and KMAC256 reduced to 7 and 9 rounds, respectively; the best attack against Lake Keyak with 128-bit key is improved from 6 to 8 rounds in the nonce-respected setting and 9 rounds of Lake Keyak can be attacked if the key size is of 256 bits; attack complexity improvements are found generally on other constructions. Our new model is also applied to Keccak-based full-state keyed sponge and gives a positive answer to the open question proposed by Bertoni et al. whether cube attacks can be extended to more rounds by exploiting full-state absorbing. To verify the correctness of our attacks, reduced-variants of the attacks are implemented and verified on a PC practically. It is remarked that this work does not threaten the security of any full version of the instances analyzed in this paper.