The impossible differential (ID) attack is one of the most important cryptanalytic techniques for block ciphers. There are two phases to finding an ID attack: searching for the distinguisher and building a key recovery upon it. Previous works only focused on automated distinguisher discovery, leaving key recovery as a manual post-processing task, which may lead to a suboptimal final complexity. At EUROCRYPT~2023, Hadipour et al. introduced a unified constraint programming (CP) approach based...

The tweakable Even-Mansour construction yields a tweakable block cipher from a public random permutation. We prove post-quantum security of tweakable Even-Mansour when attackers have quantum access to the random permutation but only classical access to the secretly-keyed construction, the relevant setting for most real-world applications. We then use our results to prove post-quantum security—in the same model—of the symmetric-key schemes Chaskey (an ISO-standardized MAC), Elephant (an AEAD...

In CRYPTO 2019, Gohr first introduced the deep learning method to cryptanalysis for Speck32/64. A differential-neural distinguisher was obtained using ResNet neural network. Zhang et al. used multiple parallel convolutional layers with different kernel sizes to capture information from multiple dimensions, thus improving the accuracy or obtaining a more round of distinguisher for Speck32/64 and Simon32/64. Inspired by Zhang’s work, we apply the network structure to other ciphers. We not only...

Firstly, we improve the evaluation theory of differential propagation for modular additions and XORs, respectively. By introducing the concept of $additive$ $sums$ and using signed differences, we can add more information of value propagation to XOR differential propagation to calculate the probabilities of differential characteristics more precisely. Based on our theory, we propose the first modeling method to describe the general ARX differential propagation, which is not based on the...

In this paper, we formulate a new framework of cryptanalysis called rotational-linear attack on ARX ciphers. We firstly build an efficient distinguisher for the cipher $ E$ consisted of the rotational attack and the linear attack together with some intermediate variables. Then a key recovery technique is introduced with which we can recover some bits of the last whitening key in the related-key scenario. To decrease data complexity of our attack, we also apply a new method, called bit...

Differential-linear attacks are a cryptanalysis family that has recently benefited from various technical improvements, mainly in the context of ARX constructions. In this paper we push further this refinement, proposing several new improvements. In particular, we develop a better understanding of the related correlations, improve upon the statistics by using the LLR, and finally use ideas from conditional differentials for finding many right pairs. We illustrate the usefulness of these...

Machine learning aided cryptanalysis is an interesting but challenging research topic. At CRYPTO'19, Gohr proposed a Neural Distinguisher (ND) based on a plaintext difference. The ND takes a ciphertext pair as input and outputs its class (a real or random ciphertext pair). At EUROCRYPTO'20, Benamira et al proposed a deeper analysis of how two specific NDs against Speck32/64 work. However, there are still three research gaps that researchers are eager to fill in. (1) what features related to...

We present the first complete implementation of the offline Simon's algorithm, and estimate its cost to attack the MAC Chaskey, the block cipher PRINCE and the NIST lightweight candidate AEAD scheme Elephant. These attacks require a reasonable amount of qubits, comparable to the number of qubits required to break RSA-2048. They are faster than other collision algorithms, and the attacks against PRINCE and Chaskey are the most efficient known to date. As Elephant has a key smaller than its...

We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

At CRYPTO 2019, Gohr first introduces the deep learning based cryptanalysis on round-reduced SPECK. Using a deep residual network, Gohr trains several neural network based distinguishers on 8-round SPECK-32/64. The analysis follows an `all-in-one' differential cryptanalysis approach, which considers all the output differences effect under the same input difference. Usually, the all-in-one differential cryptanalysis is more effective compared to the one using only one single differential...

In this paper we analyse the algorithm Chaskey - a lightweight MAC algorithm for 32-bit micro controllers - with respect to rotational cryptanalysis. We perform a related-key attack over Chaskey and find a distinguisher by using rotational probabilities. Having a message $m$ we can forge and present a valid tag for some message under a related key with probability $2^{-57}$ for 8 rounds and $2^{-86}$ for all 12 rounds of the permutation for keys in a defined weak-key class. This attack can...

Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a new...

Differential cryptanalysis and linear cryptanalysis are the two best-known techniques for cryptanalysis of block ciphers. In 1994, Langford and Hellman introduced the differential-linear (DL) attack based on dividing the attacked cipher $E$ into two subciphers $E_0$ and $E_1$ and combining a differential characteristic for $E_0$ with a linear approximation for $E_1$ into an attack on the entire cipher $E$. The DL technique was used to mount the best known attacks against numerous ciphers,...

The division property method is a technique to determine integral distinguishers on block ciphers. While the complexity of finding these distinguishers is higher, it has recently been shown that MILP and SAT solvers can efficiently find such distinguishers. In this paper, we provide a framework to automatically find those distinguishers which solely requires a description of the cryptographic primitive. We demonstrate that by finding integral distinguishers for 30 primitives with different...

In this paper, quantum attacks against symmetric-key schemes are presented in which adversaries only make classical queries but use quantum computers for offline computations. Our attacks are not as efficient as polynomial-time attacks making quantum superposition queries, while our attacks use the realistic model and overwhelmingly improve the classical attacks. Our attacks convert a type of classical meet-in-the-middle attacks into quantum ones. The attack cost depends on the number of...

We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a long standing open problem in the area of ARX design. The wide trail design strategy (WTS), that is at the basis of many S-box based ciphers, including the AES, is not suitable for ARX designs due to the lack of S-boxes in the latter. In this paper we address the mentioned limitation by...

The Chaskey MAC algorithm was presented by Mouha et al. at SAC 2014. It is designed for real-world applications where 128-bit keys are required, but standard cryptographic algorithms cannot be implemented because of stringent requirements on speed, energy consumption, or code size. Shortly after its publication, Chaskey was considered for standardization by ISO/IEC JTC 1/SC 27/WG 2. At the October 2015 meeting, the ISO/IEC committee decided to terminate the study period on Chaskey, and to...

In this work we study the security of Chaskey, a recent lightweight MAC designed by Mouha et al., currently being considered for standardisation by ISO/IEC and ITU-T. Chaskey uses an ARX structure very similar to SipHash. We present the first cryptanalysis of Chaskey in the single user setting, with a differential-linear attack against 6 and 7 rounds, hinting that the full version of Chaskey with 8 rounds has a rather small security margin. In response to these attacks, a 12-round...

Chaskey is a Message Authentication Code (MAC) for 32-bit microcontrollers proposed by Mouha et. al at SAC 2014. Its underlying blockcipher uses an Even-Mansour construction with a permutation based on the ARX methodology. In this paper, we present key-recovery attacks against Chaskey in the single and multi-user setting. These attacks are based on recent work by Fouque, Joux and Mavromati presented at Asiacrypt 2014 on Even-Mansour based constructions. We first show a simple attack on the...

This paper focuses on a surprising class of cryptanalysis results for symmetric-key primitives: when the number of rounds of the primitive is increased, the complexity of the cryptanalysis result decreases. Our primary target will be primitives that consist of identical round functions, such as PBKDF1, the Unix password hashing algorithm, and the Chaskey MAC function. However, some of our results also apply to constructions with non-identical rounds, such as the PRIDE block cipher. First, we...

We present XPX, a tweakable blockcipher based on a single permutation P. On input of a tweak (t_{11},t_{12},t_{21},t_{22}) in T and a message m, it outputs ciphertext c=P(m xor Delta_1) xor Delta_2, where Delta_1=t_{11}k xor t_{12}P(k) and Delta_2=t_{21}k xor t_{22}P(k). Here, the tweak space T is required to satisfy a certain set of trivial conditions (such as (0,0,0,0) not in T). We prove that XPX with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider...

For constrained devices, standard cryptographic algorithms can be too big, too slow or too energy-consuming. The area of lightweight cryptography studies new algorithms to overcome these problems. In this paper, we will focus on symmetric-key encryption, authentication and hashing. Instead of providing a full overview of this area of research, we will highlight three interesting topics. Firstly, we will explore the generic security of lightweight constructions. In particular, we will discuss...

In this paper we introduce a framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate the execution time, RAM footprint, as well as binary code size, and allows one to define a custom "figure of merit" according to which all evaluated candidates can be ranked. We used the framework to benchmark implementations of 19 lightweight ciphers, namely AES, Chaskey, Fantomas, HIGHT, LBlock, LEA, LED, Piccolo, PRESENT, PRIDE,...

We propose Chaskey: a very efficient Message Authentication Code (MAC) algorithm for 32-bit microcontrollers. It is intended for applications that require 128-bit security, yet cannot implement standard MAC algorithms because of stringent requirements on speed, energy consumption, or code size. Chaskey is a permutation-based MAC algorithm that uses the Addition-Rotation-XOR (ARX) design methodology. We formally prove that Chaskey is secure in the standard model, based on the security of an...