This paper defines the conditional constant function problem (CCFP), and for a special case of CCFP, presents a quantum algorithm for solving it efficiently. Such an algorithm enables us to make new evaluations of the quantum security of Feistel block cipher in the case where quantum attackers can only perform online classical queries. Specifically, the chosen-plaintext key recovery attacks on two Feistel block cipher variants, known as Feistel-KF and Feistel-FK, are significantly improved. For Feistel-KF, a 3-round distinguisher based on the special case of CCFP is constructed, and key recovery attacks forr> 3 rounds are proposed. For Feistel-FK, the CCFP based distinguisher covers 4 rounds and the key recovery attacks are applicable forr> 4 rounds. Based on the CCFP solving algorithm, the key recovery attacks can reduce the classical memory complexity from the previous exponentialO(2cn) toO(1), wherec’s are constants. The query complexity of key recovery attacks on Feistel-KF is also significantly reduced fromO(2cn) toO(1). Besides, the CCFP solving algorithm can be extended to reduce the query complexity exponentially in attacking the 2IEM and pEDM constructions. These results indicate that quantum algorithms solving CCFP could be more promising than those solving the period finding problem.

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.

As the practical applications of fully homomorphic encryption (FHE), secure multi‐party computation (MPC) and zero‐knowledge (ZK) proof continue to increase, so does the need to design and analyze new symmetric‐key primitives that can adapt to these privacy‐preserving protocols. These designs typically have low multiplicative complexity and depth with the parameter domain adapted to their application protocols, aiming to minimize the cost associated with the number of nonlinear operations or the multiplicative depth of their representation as circuits. In this paper, we propose two differential fault attacks against a one‐way function RAIN used for Rainier (CCS 2022), a signature scheme based on the MPC‐in‐the‐head approach and an FHE‐friendly cipher HERA used for the RtF framework (Eurocrypt 2022), respectively. We show that our attacks can recover the keys for both ciphers by only injecting a fault into the internal state and requiring only one normal and one faulty ciphertext blocks. Thus, we can use only the practical complexity of 2 26.6 /2 28.8 /2 30.4 bit operations to break the full‐round RAIN with 128/192/256‐bit keys. For full‐round HERA with 80/128‐bit key, our attack is practical with complexity the complexity of 2 20 encryptions with about 2 16 memory.

Abstract At ASIACRYPT 2019, Zhang proposed a near collision attack on A5/1 claiming to recover the 64‐bit A5/1 state with a time complexity around 2 32 cipher ticks with negligible memory requirements. Soon after its proposal, Zhang's near collision attack was severely challenged by Derbez et al. who claimed that Zhang's attack cannot have a time complexity lower than Golic's memoryless guess‐and‐determine attack dating back to EUROCRYPT 1997. In this article, both the guess‐and‐determine and the near collision attacks for recovering A5/1 states with negligible memory complexities are studied. Firstly, a new guessing technique called the move guessing technique that can construct linear equation filters in a more efficient manner is proposed. Such a technique can be applied to both guess‐and‐determine and collision attacks for efficiency improvements. Secondly, the filtering strength of the linear equation systems is taken into account for complexity analysis. Such filtering strength are evaluated with practical experiments making the complexities more convincing. Based on such new techniques, the authors are able to give 2 new guess‐and‐determine attacks on A5/1: the 1st attack recovers the internal state with time complexity 2 43.92 ; the 2nd one recovers a different state with complexity 2 43.25 . Golic's guess‐and‐determine attack and Zhang's near collision attacks are revisited. According to our detailed analysis, the complexity of Golic's recovery attack is no lower than 2 46.04 , higher than the previously believed 2 43 . On the other hand, Zhang's near collision attack recovers with the time complexity 2 53.19 : such a complexity can be further lowered to 2 50.78 with our move guessing technique.

Abstract The 5G mobile communication system is coming with a main objective, known also as IMT-2020, that intends to increase the current data rates up to several gigabits per second. To meet an accompanying demand of the super high-speed encryption, EIA and EEA algorithms face some challenges. The 3GPP standardization organization expects to increase the security level to 256-bit key length, and the international cryptographic field responds actively in cipher designs and standard applications. SNOW-V is such a proposal offered by the SNOW family design team, with a revision of the SNOW 3G architecture in terms of linear feedback shift register (LFSR) and finite state machine (FSM), where the LFSR part is new and operates eight times the speed of the FSM, consisting of two shift registers and each feeding into the other, and the FSM increases to three 128-bit registers and employs two instances of full AES encryption round function for update. It takes a 128-bit IV, employs 896-bit internal state and produces 128-bit keystream blocks. The result is competitive in pure software environment, making use of both AES-NI and AVX acceleration instructions. Thus, the security evaluation of SNOW-V is essential and urgent, since there is scarcely any definite security bound for it. In this paper, we propose a byte-based guess-and-determine attack on SNOW-V with complexity $2^{406}$ using only seven keystream blocks. We first improve the heuristic guessing-path auto-searching algorithm based on dynamic programming by adding initial guessing set, which is iteratively modified by sieving out the unnecessary guessing variables, in order to correct the guessing path according to the cipher structure and finally launch smaller guessing basis. For the specific design, we split all the computing units into bytes and rewrite all the internal operations correspondingly. We establish a backward-clock linear equation system according to the circular construction of the LFSR part. Then we further simplify the equations to adapt to the input requirements of the heuristic guessing-path auto-searching algorithm. Finally, the derived guessing path needs modification for the pre-simplification and post-reduction. This is the first complete guess-and-determine attack on SNOW-V as well as the first specific security evaluation to the full cipher.

TRIVIUM is a stream cipher of the finalists by eSTREAM project and has been accepted as ISO standard. Although the design has a simple structure, no attack on its full cipher has been found yet. In this study, based on Maximov and Biryukov's attack, the authors present an improved guess‐and‐determine attack on TRIVIUM. Analysis details are provided corresponding to TRIVIUM specifications for better comprehension, and errors that may lead to higher attack complexity in the original attack are pointed and corrected. They further bring in some techniques like backward‐clock equation collection, quadratic equations, linear transformation to improve the attack. In addition, they integrate with time‐memory‐data tradeoffs from the framework, based on the analysis of the coefficient matrices form of derived linear equation systems on the internal state. In this way, better use of the imposed quadratic conditions can be made, which leads to reduced attack complexity by filtering out the impossible keystreams before solving the equation systems. Their attack offers more parameter selections, and gives several borderline results compared with the key exhaustive search. The new attack behaves better in the original case. It also verifies the necessity of data requirement imposed on TRIVIUM, which is questioned in TRIVIUM specifications.

At CRYPTO 2017 and IEEE Transactions on Computers in 2018, Todo et al. proposed the division property based cube attack method making it possible to launch cube attacks with cubes of dimensions far beyond practical reach. However, assumptions are made to validate their attacks. In this paper, we further formulate the algebraic properties of the superpoly in one framework to facilitate cube attacks in more successful applications: we propose the “flag” technique to enhance the precision of MILP models, which enable us to identify proper non-cube IV assignments; a degree evaluation algorithm is presented to upper bound the degree of the superpoly s.t. the superpoly can be recovered without constructing its whole truth table and overall complexity of the attack can be largely reduced; we provide a divide-and-conquer strategy to Trivium-like stream ciphers namely Trivium, Kreyvium, TriviA-SC1/2 so that the large scale MILP models can be split into several small solvable ones enabling us to analyze Trivium-like primitives with more than 1000 initialization rounds; finally, we provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. We apply our techniques to attack the initialization of several ciphers namely 839-round Trivium, 891-round Kreyvium, 1009-round TriviA-SC1, 1004-round TriviA-SC2, 184-round Grain-128a and 750-round Acorn respectively.

The integral attack, exploits the balanced property of the output in the distinguisher. Usually, adversaries append some rounds after the distinguisher, guess the corresponding key bits and check whether the target bits are balanced. Few works add rounds before the distinguisher to make the key recovery attack. In the first full‐round attack on MISTY1, Todo adds one FL layer (key‐dependent linear function) before the distinguisher. In this study, the authors extend his method and give a general method, which they can use to extend some rounds (non‐linear) before the distinguisher to attack more rounds with data complexity smaller than the whole space and little extra time consumption. The basic idea is that for different subkeys guessed in the forward rounds, they set different constant values for the input of the distinguisher. Finally, the selected data space is not full. For substitution permutation network (SPN) (Feistel with SPN round function) structures with 4 bit S‐box and bit permutation, they estimate the data complexity when adding one round before the distinguishers for all 4 bit S‐boxes. Using the method, they improve the integral attacks on PRESENT, RECTANGLE, TWINE and LBlock, and their results could cover one more round.

Guess‐and‐determine attack is a cryptanalysis method that has been applied to various stream ciphers. In this study, the authors study the guess‐and‐determine attacks on two ISO standardised, P anama ‐like stream ciphers: MUGI and Enocoro. Utilising the word‐oriented structure of the two ciphers, they are able to launch heuristic guess‐and‐determine attacks in a more efficient manner. Their first target MUGI is both an ISO standard and a Japanese‐government‐selected CRYPTREC standard. By splitting its basic 64‐bit words into 16‐bit quarter‐words, they are able to conduct a guess‐and‐determine attack with complexity 2 388 , much lower than its 1216‐bit internal state size. Enocoro is a lightweight stream cipher family. It has two versions named according to key‐length as Enocoro‐80 and Enocoro‐128v2. They provide the specific guessing paths and they are able to launch guess‐and‐determine attacks on Enocoro‐80 and Enocoro‐128v2 with complexities 2 88 and 2 144 , respectively. In addition to specific attacking results, they also find some generic rules that may help to improve the efficiency of guess‐and‐determine attacks in the future.

The cube attack is a powerful cryptanalytic technique and is especially powerful against stream ciphers. Since we need to analyze the complicated structure of a stream cipher in the cube attack, the cube attack basically analyzes it by regarding it as a blackbox. Therefore, the cube attack is an experimental attack, and we cannot evaluate the security when the size of cube exceeds an experimental range, e.g., 40. In this paper, we propose cube attacks on non-blackbox polynomials. Our attacks are developed by using the division property, which is recently applied to various block ciphers. The clear advantage is that we can exploit large cube sizes because it never regards the cipher as a blackbox. We apply the new cube attack to Trivium, Grain128a, ACORN and Kreyvium. As a result, the secret keys of 832-round Trivium, 183-round Grain128a, 704-round ACORN and 872-round Kreyvium are recovered. These attacks are the current best key-recovery attack against these ciphers.

The cube tester is a powerful tool to detect non‐randomness of cryptographic primitives. The balance tester is a kind of powerful cube tester that has been applied to various cryptographic primitives. However, most existing results of the balance tester are acquired experimentally using small cubes of dimension no more than 50. To understand the mechanic of the balance tester, it is necessary to predict the number of higher‐dimensional cubes. In this paper, we firstly draw links between the number of cubes and the resistance against the balance tester. Secondly, we theoretically prove that there are lower and upper bounds for the number of each dimensional cubes using a probabilistic model. Based on our analysis, we propose our main algorithms that can draw the lower and upper bounds for the number of different dimensional cubes utilising some easily acquired statistics. We apply our main algorithms to some famous stream ciphers namely Trivium, Grain‐128, Grain‐128a and Grain‐v1. The results are in high accordance with our theories and expectations. Our work provides a better understanding of the balance tester. We expect that our main algorithms will equip the cryptologists with useful information when evaluating the secure margin of newly designed ciphers.

In this paper, we study the security of the LSH hash functions. We find that the wide-pipe MD-structural LSH hash functions apply the 17th PGV scheme which is backward attackable. This property equips us with trivial attacks including pseudo-preimage, free-start collision, and Type II boomerang. These attacks can never be available to previous MD-structural hash functions like Skein. We stress that such trivial attacks can only be regarded as distinguishers rather than real threat to the LSH in nowadays' practical applications. But we should still be cautious about the possible malicious use of LSH in specific situations in the future. We also launch 14-round boomerang attacks on LSH-512 and LSH-256 hash functions with complexities 2308 and 2242, respectively. We verify the correctness of our boomerang attacks by giving practical 11-round boomerang quartets. To the best of our knowledge, these are the first practically verifiable boomerang results on the LSH hash functions. These boomerang results indicate that the round functions of LSH are well designed. Copyright © 2016 John Wiley & Sons, Ltd.