Pseudo-random functions are a fundamental building block in many cryptographic applications. In certain scenarios, a weaker notion (where security is restricted to uniformly random input), but more computationally efficient, called weak pseudo-random functions, is sufficient. In this work, we present new differential attacks on the main binary weak pseudo-random function constructions, namely the so-called Alternative Mod-2/Mod-3. For the Alternative Mod-2/Mod-3 wPRF, the best distinguisher proposed by Cheon et al. achieves O(20.21n) complexity, where n is the input length. We show that our attack asymptotically outperforms this and requires far fewer samples that can be applied in restricted oracle settings. By minimizing computational complexity, we can achieve O(20.166n) complexity. Additionally, in a small experiment, we indicate that their proposed fix of using keys with large Hamming weight is even more vulnerable to our attack.

Abstract At FSE 2008, Leurent introduced the preimage attack on MD4 by exploiting differential trails. In this paper, we apply the differential-aided preimage attack to Keccak with the message modification techniques. Instead of directly finding the preimage, we exploit differential characteristics to modify the messages, so that the differences of their hashing values and the changes of given target can be controlled. By adding some constraints, a trail can be used to change one bit at a time and reduce the time complexity by a factor of 2. When the number of rounds increases, we introduce two-stage modification techniques to satisfy part of constraints as well. In order to solve other constraints, we also combine the linear-structure technique and accordingly give a preimage attack on 5-round Keccak[$r=1440,c=160,l=80$].

ChaCha has been one of the most prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack that exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3rd round. At Crypto 2020, Beierle et al. introduced for the first time the single bit distinguishers for 3.5th round, which contributed significantly to regaining the flow of the research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher at 3.5th round helped to produce a 7th round distinguisher of ChaCha and a further improvement in the key recovery. In this paper, first, we provide the theoretical framework for the distinguisher given by Beierle et al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at 3.5th round. Also, Beierle et al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next, we revisit the work of Coutinhoet al.(Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218and$2^{228.51}$respectively. We show that the differential correlation for the 3.5th round is much smaller than the claim of Coutinho et al. This makes the attack complexities much higher than their claim.

Abstract We introduce an interpolation attack using the Moebius Transform. This can reduce the time complexity to get a linear system of equations for specified intermediate state bits, which is general to cryptanalysis of some ciphers with update function of low algebraic degree. Along this line, we perform an interpolation attack against Elephant-Delirium, a round 2 submission of the ongoing national institute of standards and technology (NIST) lightweight cryptography project. This is the first third-party cryptanalysis on this cipher. Moreover, we promote the interpolation attack by applying it to the Farfalle pseudo-random constructions Kravatte and Xoofff. Our attacks turn out to be the most efficient method for these ciphers thus far.

Abstract A new conditional cube attack was proposed by Li et al. at ToSC 2019 for cryptanalysis of Keccak keyed modes. In this paper, we find a new property of Li et al.’s method. The conditional cube attack is modified and applied to cryptanalysis of 5-round Ketje Jr, 6-round Xoodoo-AE and Xoodyak, where Ketje Jr is among the third round CAESAR competition candidates and Xoodyak is a Round 2 submission of the ongoing NIST lightweight cryptography project. For the updated conditional cube attack, all our results are shown to be of practical time complexity with negligible memory cost, and test codes are provided. Notably, our results on Xoodyak represent the first third-party cryptanalysis for Xoodyak.

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.

MORUS is an authenticated encryption algorithm and one of the candidates in the CAESAR competition. Currently, the security of MORUS received extensive attention. In this paper, a new existence terms detection method in superpoly recovery phase in cube attack is proposed. More precisely, the upper bounding degree of superpoly is first estimated by using the cube attack based on the division property with Mixed Integer Linear Programming tool. Moreover, the t-degree monomials that may be involved in the superpoly are divided into two groups, where the elements of the first group can be directly determined without using the solver via the embedded property. Compared with previous methods, the time consumption by the solvers of our new method is reduced significantly. In particular, the truth table from only the existent terms can be used to recover the superpoly in the offline phase of the cube attack. Therefore, the time complexity of cube attack can be further reduced. As illustrative example, the security of the reduced-step variants of MORUS-640-128 against cube attack is evaluated by using this new method. It is demonstrated that the key recovery attacks can be applied to 6/7-step MORUS-640-128. Furthermore, some integral distinguishers of 7-step MORUS-640-128/MORUS-1280-256 are achieved.

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.

Cryptographic hash functions are used to protect information integrity and authenticity in a wide range of applications. After the discovery of weaknesses in the current deployed standards, the U.S. Institute of Standards and Technology started a public competition to develop the future standard SHA-3, which will be implemented in a multitude of environments, after its selection in 2012. In this paper, we investigate high-speed and low-area hardware architectures of one of the 14 “second-round” candidates in this competition: BLAKE. VLSI performance results of the proposed high-speed designs indicate a throughput improvement between 16% and 36% compared to the current standard SHA-2. Additionally, we propose a compact implementation of BLAKE with memory optimization that fits in 0.127 mm2of a 0.18 μ m CMOS. Measurements reveal a minimal power dissipation of 9.59 μW/MHz at 0.65 V, which suggests that BLAKE is suitable for resource-limited systems.

A new stream cipher, Grain-128, is proposed. The design is very small in hardware and it targets environments with very limited resources in gate count, power consumption, and chip area. Grain-128 supports key size of 128 bits and IV size of 96 bits. The design is very simple and based on two shift registers, one linear and one nonlinear, and an output function