Abstract With the growing prevalence of compact and resource-constrained computing devices, demand for lightweight cryptographic schemes is burgeoning. , a lightweight hash function that entered the final round of the NIST Lightweight Cryptography (LWC), has received extensive attention owing to its security and high efficiency. Meet-in-the-Middle (MitM) attack serves as an effective method for the analysis of sponge-based hashing. Nevertheless, constrained by the large search space, the optimization of MitM attack remains to be further investigated. We introduce an improved approach, overall-weak-diffusion structure searching strategy, to identify a weak diffusion neutral set in the heuristic two-stage searching strategy, and apply it to 3-round . Ultimately, the time complexity of MitM collision attack against 3-round is reduced to $$2^{124.24}$$ 2 124.24 and the memory is $${2}^{123}$$ 2 123 . To our knowledge, this establishes the most efficient collision attack against 3-round , which lowers both the time and memory complexities by half compared to the current best results achieved at CRYPTO 2024. Furthermore, this paper also evaluates the resistance of 3-round -like hashing against MitM collision attack and provides recommendations for parameter selection.

Abstract With the increasingly widespread application scenarios of the Internet of Things, the demand for lightweight ciphers continues to grow. For some lightweight ciphers whose only nonlinear component is the AND gate, their resistance to linear cryptanalysis relies heavily on the properties of the AND operation, making the analysis of such AND gates crucial. In current linear cryptanalysis, two main methods exist: estimating the correlation of linear charactertics based on the number of active AND gates or constructing cipher-specific models that calculate the correlation among AND gates. The former method lacks precision, while the latter method lacks generality. Considering the correlation among AND gates allows for a more accurate assessment of a cipher’s resistance to linear cryptanalysis. However, there is currently no general model to systematically characterize the correlation between quadratic AND gates. This paper proposes a model to characterize the correlation between quadratic AND gates. We apply the model to TinyJAMBU and MiniMORUS. For the permutation $$P_l$$ P l of TinyJAMBU, we improve the absolute of correlation of the 512-round linear charactertics from $$2^{-46}$$ 2 - 46 to $$2^{-33}$$ 2 - 33 . For 760-round, we identify a valid linear charactertics with absolute of correlation of $$2^{-63}$$ 2 - 63 . For MiniMORUS-640 and MiniMORUS-1280, we find unique linear charactertics with absolute of correlations of $$2^{-8}$$ 2 - 8 each.

Abstract Boomerang attack serves as a potent cryptanalytic tool for assessing the security of block ciphers. Over the past few years, various automatic search models for boomerang distinguishers have been proposed for block ciphers with different structures. This paper presents improved Mixed-Integer Linear Programming (MILP)-based search models for both single-key and related-key boomerang distinguishers. In the single-key scenario, we propose a method for dynamic allocation of active S-boxes. Our search model for single-key boomerang distinguishers characterizes the distinguisher probability more accurately, addressing the suboptimality issue caused by non-fixed weight assignments in prior models. In the related-key scenario, a search model for related-key boomerang distinguisher is proposed for block ciphers with bit-level key schedule algorithms, where the probability of the boomerang switch is ensured to be 1. To validate the effectiveness of our models, we apply them to the lightweight block cipher LILLIPUT based on Extended Generalized Feistel Networks (EGFN), conducting a comprehensive security analysis against boomerang attacks. Using our models, we successfully derive single-key boomerang distinguishers for 8 to 13 rounds and a 15-round related-key boomerang distinguisher. Notably, the data complexity required for 13-round single-key distinguishing attack is reduced by $${2^{ 3.172}}$$ 2 3.172 , and the 15-round related-key boomerang distinguisher with a probability of $${2^{ - 58}}$$ 2 - 58 is currently the longest-round distinguisher among all known distinguishers for LILLIPUT. The application results fully demonstrate the capability of our models in evaluating the security of block ciphers. This research not only provides new insights and methods for the design and analysis of lightweight block ciphers, but also deepens the understanding of the security characteristics for LILLIPUT.

The impossible boomerang attack is a powerful cryptanalytic technique, but existing key recovery methods face several limitations that restrict its applicability. Specifically, the key pre-guessing is coarse-grained, S-box details are ignored in the differential propagation, the complexity estimation and the key guessing order determination remain rudimentary. To overcome these issues, we introduce three key improvement measures. First, we propose a flexible partial key and difference pre-guessing technique based on directed graphs, enabling selective identification of required keys and differences for generating partial pairs and quartets. Second, we propose a pre-sieving technique to early eliminate invalid quartets by exploiting cipher-specific details. Third, we introduce an automatic key-guessing strategy based on the same directed graphs to efficiently determine valid guessing orders. We integrate these techniques to develop a unified key recovery framework for impossible boomerang attacks, accompanied by a formal and precise characterization of the overall complexity. This is the first framework to support flexible key and difference pre-guessing while incorporating block cipher details during key recovery for impossible boomerang attacks. Crucially, it enables the automatic generation of detailed recovery steps, a capability missing in prior work. As applications, under the four related-key/tweakey setting, we apply the framework to ARADI, a low-latency cipher proposed by the National Security Agency (NSA), and SKINNYe v2, a threshold-implementation-friendly cipher proposed at EUROCRYPT 2020. For ARADI, we achieve the first full-round attack with 2130data, 2253.78time, and 2235.75memory complexity. For SKINNYe v2, we present the first 34-round impossible boomerang attack with 266data, 2253.75time, and 2239.75memory complexity. These results demonstrate the framework’s significance and its substantial improvement in advancing the impossible boomerang attack.

Fast correlation attack is one of the most powerful attack methods for LFSR-based stream ciphers, and the primary problem of the attack is to construct the linear approximations with great absolute correlations. For some stream ciphers with complex structures of linear approximations, the search for the maximum absolute correlation of linear approximations has always been a difficult problem because of the extremely high amount of masks that need to be searched. In this paper, an analysis method for searching maximum absolute correlation based on the linear mask structure is developed, including the filtering technology based on mask propagation trail, a structural characteristic of linear approximations of linear transformations with fewer active bytes, and linear approximation equivalence theorem of composite function composed of the parallel identical S-boxes and linear transformation. These methods efficiently reduce the exhaustive time complexity of the masks. As applications, this paper proves that the suprema of absolute correlations of all the linear approximations for the five XOR-versions of SNOW family stream ciphers (i.e., SNOW 2.0⊕, SNOW 3G⊕, SNOW-V⊕, SNOWVi⊕, SNOW 5G⊕) are 2−9/2−15:893/2−37:964/2−37:964/2−37:964. The exhaustive time complexity of the masks can be reduced fromO(232)/O(296)/O(2384)/O(2384)/O(2384) toO(224)/O(231.98)/O(239.98)/O(239.98)/O(239.98), respectively. Furthermore, we give the provable security evaluations of the five ciphers against fast correlation attacks under the success probability of 0:99 for the known fast correlation attack method. For SNOW-V⊕/SNOW-Vi⊕/SNOW 5G⊕, the time/data/memory complexity of the optimal fast correlation attacks are allO(2227.54)/O(2227.72)/O(2227.72). The results show that SNOWV⊕/SNOW-Vi⊕/SNOW 5G⊕cannot guarantee the claimed 256- bit key security for the known fast correlation attack methods if we ignore the design constraint that the maximum length of keystream for a single pair of key and IV is 264. For SNOW 2.0⊕and SNOW 3G⊕, the time/data/memory complexity of the optimal fast correlation attacks areO(2151.94)/O(2151.35)/O(2151.35) andO(2165.91)/O(2165.43)/O(2165.43), respectively. The results show that both SNOW 2.0⊕and SNOW 3G⊕can guarantee the claimed 128-bit key security for the known fast correlation attack methods. In addition, this paper also discusses that the existing fast correlation attacks based on multiple linear approximations are invalid for these five ciphers.

Differential‐linear (DL) cryptanalysis is an important cryptanalytic method in cryptography and has received extensive attention from the cryptography community since its proposal by Langford and Hellman in 1994. At CT‐RSA 2023, Bellini et al. introduced continuous difference propagations of XOR, rotation, and modulo‐addition operations and proposed a fully automatic method using Mixed‐Integer Linear Programing (MILP) and Mixed‐Integer Quadratic Constraint Programing (MIQCP) techniques to search for DL distinguishers of Addition‐Rotation‐XOR (ARX) ciphers. In this paper, we propose continuous difference propagation of AND operation and construct an MILP/MIQCP‐based fully automatic model of searching for DL distinguishers of SIMON‐like ciphers. We apply the fully automatic model to all versions of SIMON and SIMECK. As a result, for SIMON, we find 13 and 14‐round DL distinguishers of SIMON32, 15, 16, and 17‐round DL distinguishers of SIMON48, 20‐round DL distinguishers of SIMON64, 25 and 26‐round DL distinguishers of SIMON96, 31 and 32‐round DL distinguishers of SIMON128. For SIMECK, we find 14‐round DL distinguishers of SIMECK32, 17 and 18‐round DL distinguishers of SIMECK48, 22, 23, 24, and 25‐round DL distinguishers of SIMECK64. As far as we know, our results are currently the best.

With the rapid development of the Internet of Things (IoT), many new lightweight block ciphers are designed in recent years to meet the security demand in IoT devices. Shadow is a lightweight block cipher designed for IoT Nodes (IEEE Internet of Things Journal, 2021). In this article, an efficient attack on full-round Shadow is proposed based on the idea of a related-key differential attack. First, a differential transfer property for AND operation is illustrated. This property demonstrates a link between the difference and the input value. If the difference of the input is not zero, to lead to a zero difference, there are some constraints on the input value. Furthermore, two properties for Shadow family ciphers are identified. According to these properties, some related keys on Shadow will lead to an internal collision for the subkey generator, which will eventually lead to a full-round distinguisher. Finally, with the idea of related-key differential attack, an efficient attack is applied to Shadow. For Shadow-32, with 4 related keys, 8 master key bits can be derived in about 0.044 seconds on average. For Shadow-64, with 4 related keys, 24 master key bits can be derived in about 3.9 hours on average. All our theoretical results are verified by experiments.

A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form of$\mathcal {O}$, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by$2^{t}(t\gt 0)$, the depth decreases by a factor of$\sqrt {2^{t}}$. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, includingSUM-ECBCand its variants (2K-SUM-ECBC,2K-ECBC_Plus), andGCM-SIV2. In the typical case whereSUM-ECBCis based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.

How to evaluate the security of Substitution-Permutation Network (SPN) block ciphers against impossible differential (ID) cryptanalysis is a valuable problem. In this paper, a series of methods for bounding the length of IDs of SPN block ciphers are proposed. Firstly, we propose the definitions of minimal representative set and partition table. Therefore, an improved partition-first implementation strategy for bounding the length of IDs is given. Secondly, we introduce a new definition of ladder and propose the ladder-first implementation strategy for bounding the length of IDs. In order to be able to apply ladder-first implementation strategy in practice, the methods for determining ladders and integrating a ladder into searching models are given. Thirdly, a heuristic algorithm called dynamic-ladder-partition implementation strategy is proposed. According to our experimental results, dynamic-ladder-partition implementation strategy is more suitable for SPN ciphers whose number of elements in partition tables is little. Fourthly, rotation-equivalence ID sets of ciphers are explored to reduce the number of models that need to be considered. As applications, we show that 9-round PRESENT, 5-round AES, 6-round Rijndael-160, 7-round Rijndael-192, 7-round Rijndael-224 and 7-round Rijndael-256 do not have any ID under the sole assumption that the round keys are uniformly random. What’s more, we obtain that 8-round GIFT-64, 12-round GIFT-128 and 14-round SKINNY-128 do not have any ID under the assumptions that GIFT and SKINNY are Markov ciphers and the round keys are uniformly random. Our methods fill crucial gaps on bounding the length of IDs with the differential properties of S-boxes considered. They enhance our confidence in the security and are valuable, especially for designers.

In this paper, a security evaluation framework for AND-RX ciphers against impossible differential cryptanalysis is proposed. This framework is constructed based on three different methods towards finding the theoretical upper boundary, theoretical lower boundary, and practical boundary of impossible differential distinguishers (short for ID) respectively. The provable security boundary (upper boundary) can be calculated with two round-function-related matrices through a few matrix multiplications, this calculation is beyond actual input and output differences. For searching longer IDs (lower boundary), an automatic method is proposed. With this method, given the input and output difference, all the possible direct and indirect contradictions are detected. For the practical boundary, a method of approximating all the potential longest IDs with concrete differential trails is introduced. The three boundaries validate the correctness from each other. According to our result, on the one hand, the boundaries derived with well-designed ID-construction methods can already reach the practical boundary for some block ciphers and it is unlikely to be improved based on known construction methods or future unknown construction methods. On the other hand, for those ciphers whose current best result does not reach our boundary, longer IDs can be discovered with this framework. The correctness is validated by a series of applications. For the provable security boundary, four family ciphers-SIMON, Simeck, Friet-PC and SAND are investigated. For SIMON and Simeck, the lengths of current longest IDs have reached their provable security boundaries. For Friet-PC and SAND, there is a gap between the provable security boundary and current best results. With the automatic searching method, some longer IDs on Friet-PC and SAND are discovered. For Friet-PC, 128 11-round IDs are discovered, while the previous best differential distinguisher is 9-round. For SAND64, 256 11-round IDs are proposed. For SAND128, 456 14-round IDs are presented. Both results extend previous longest IDs by one round and all these newly proposed distinguishers reached corresponding provable security boundaries. For Simeck, the length of longest IDs has not been improved. However, more distinguishers of the same length are discovered. For Simeck64, the increased ratio for the quantity can reach 300%. Besides, the practical boundary of SIMON is investigated, the results indicate that for SIMON, the practical boundary is identical with the provable security boundary or the boundary derived with the automatic searching method.

In this paper, a security evaluation framework for AND-RX ciphers against rotational-XOR differential cryptanalysis is proposed. This framework first models the structure of all the possible rotational-XOR differential (abbreviated to “RXD”) trails and introduces a method to calculate this structure round by round. Based on this approach, an automatic method is proposed for searching RXD trails. In this method, four strategies are proposed to derive better result and improve the efficiency. Unlike previous automations, the time complexity for this framework can be pre-computed, which is bounded by${\mathcal{ O}}\left ({{c\cdot n\cdot R^{2}\cdot C_{n}^{n_{1}}} }\right)$(where$n$is the block size,$n_{1}$is the number of active bits for the starting point of automatic method,$R$is the length of the targeted rounds and$c$is a fixed constant). Under the given strategies and searching subspaces, the derived RXD trails are guaranteed to be optimal. To prove the correctness and efficiency, this framework is applied to all the ten variants for SIMON and three variants for Simeck. When compared with previous RXD trails, the best improvement is up to three rounds. To validate the correctness of the derived rotational-XOR differential trails, a concrete experiment on Simeck32 is conducted and the experimental result complies with the theoretical analysis. As far as we know, for all the variants of Simeck, current longest distinguishers over all the cryptanalytic methods are obtained in this paper.