In this paper we study the S-box known as Chi or \chi initially proposed by Daemen in 1995 and very widely used ever since in Keccak, Ascon, and many other. This type of ciphers is typically analyzed [in recent research] in terms of subspace trail attacks [TeDi19] and vector space invariants. An interesting question is then, when different spaces are mapped to each other by translations with a constant. In this paper we relax this fundamental question and we consider arbitrary sets of...

In symmetric cryptography, vectorial Boolean functions over finite fields F2n derive strong S-boxes. To this end, the S-box should satisfy a list of tests to resist existing attacks, such as the differential, linear, boomerang, and variants. Several tables are employed to measure an S- box’s resistance, such as the difference distribution table (DDT) and the boomerang connectivity table (BCT). Following the boomerang attacks recently revisited in terms of the boomerang switch effect, with a...

At CRYPTO 2019, Gohr demonstrated that differential-neural distinguishers (DNDs) for Speck32/64 can learn more features than classical cryptanalysis's differential distribution tables (DDT). Furthermore, a non-classical key recovery procedure is devised by combining the Upper Confidence Bound (UCB) strategy and the BayesianKeySearch algorithm. Consequently, the time complexity of 11-round key recovery attacks on Speck32/64 is significantly reduced compared with the state-of-the-art results...

In 1994, Langford and Hellman introduced differential-linear (DL) cryptanalysis, with the idea of decomposing the block cipher E into two parts, EU and EL, such that EU exhibits a high-probability differential trail, while EL has a high-correlation linear trail.Combining these trails forms a distinguisher for E, assuming independence between EU and EL. The dependency between the two parts of DL distinguishers remained unaddressed until EUROCRYPT 2019, where Bar-On et al. introduced the DLCT...

In CRYPTO 2019, Gohr showed that well-trained neural networks could perform cryptanalytic distinguishing tasks superior to differential distribution table (DDT)-based distinguishers. This suggests that the differential-neural distinguisher (ND) may use additional information besides pure ciphertext differences. However, the explicit knowledge beyond differential distribution is still unclear. In this work, we provide explicit rules that can be used alongside DDTs to enhance the effectiveness...

The substitution box (S-box) is an important nonlinear component in most symmetric cryptosystems and thus should have good properties. Its difference distribution table (DDT) and linear approximation table (LAT) affect the security of the cipher against differential and linear cryptanalysis. In most previous work, differential uniformity and linearity of an S-box are two primary cryptographic properties to impact the resistance against differential and linear attacks. In some cases, the...

This paper presents ``SASQUATCH'', an open-source tool, that aids in finding an unknown substitution box (SBox) given its properties. The inspiration of our work can be directly attributed to the DCC 2022 paper by Lu, Mesnager, Cui, Fan and Wang. Taking their work as the foundation (i.e., converting the problem of SBox search to a satisfiability modulo theory instance and then invoking a solver), we extend in multiple directions (including -- but not limiting to -- coverage of more options,...

In the design of GIFT, half round key XOR is used. This leads to the undesired consequence that the security against the differential/linear attacks are overestimated. This comes from the observation that; in the usual DDT/LAT based analysis of the differential/linear attacks, the inherent assumption is the full round key is XORed at each round.

Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers. The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID. Unfortunately, due to the huge search space (approximately $2^{2n}$ for a cipher with a block size $n$ bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem. In this paper, we propose a systematic...

Mixed integer linear programming (MILP) based tools are used to estimate the strength of block ciphers against the cryptanalytic attacks. The existing tools use partial difference distribution table (p-DDT) approach to optimize the probability of differential characteristics for large (≥8-bit) S-box based ciphers. We propose to use the full difference distribution table (DDT) with the probability of each possible propagation for MILP modeling of large S-boxes. This requires more than 16...

This work presents techniques for modeling Boolean functions by mixed-integer linear inequalities (MILP) on binary variables in-place (without auxiliary variables), reaching minimum possible number of inequalities for small functions and providing meaningful lower bounds on the number of inequalities when reaching the minimum is infeasible. While the minimum number of inequalities does not directly translate to best performance in MILP applications, it nonetheless provides a useful...

At CRYPTO'19, Gohr proposed a new cryptanalysis strategy based on the utilisation of machine learning algorithms. Using deep neural networks, he managed to build a neural based distinguisher that surprisingly surpassed state-of-the-art cryptanalysis efforts on one of the versions of the well studied NSA block cipher speck (this distinguisher could in turn be placed in a larger key recovery attack). While this work opens new possibilities for machine learning-aided cryptanalysis, it remains...

Given the links between nonlinearity properties and the related tables such as LAT, DDT, BCT and ACT that have appeared in the literature, the boomerang connectivity table BCT seems to be an outlier as it cannot be derived from the others using Walsh-Hadamard transform. In this paper, a brief unified summary of the existing links for general vectorial Boolean functions is given first and then a link between the autocorrelation and boomerang connectivity tables is established.

Motivated by the algorithm of differential probability calculation of Lipmaa and Moriai, we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel construction of combinational DDT, which makes it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the...

We studied the applicability of differential cryptanalysis to cryptosystems based on operation of addition modulo $2^n$. We obtained an estimate (accurate up to an additive constant) of expected value of entropy $H_n$ in rows of DDT of corresponding mapping. Moreover, the $k$-th moments of $2^{H_n}$ are explored. In particular, asymptotic inequalities that describe the behavior of values $\mathbb{E}2^{H_n}$ and $\mathbb{D}2^{H_n}$ as $n \to \infty$ were obtained. A simple analytical formula...

Automatic search methods have been widely used for cryptanalysis of block ciphers, especially for the most classic cryptanalysis methods -- differential and linear cryptanalysis. However, the automatic search methods, no matter based on MILP, SMT/SAT or CP techniques, can be inefficient when the search space is too large. In this paper, we improve Matsui's branch-and-bound search algorithm which is known as the first generic algorithm for finding the best differential and linear trails by...

SIMON and SPECK families of block ciphers are well-known lightweight ciphers designed by NSA. In this note, based on the previous investigations on SIMON, a closed formula for the squared correlations and differential probabilities of the mapping $\phi(x) = x \odot S^1(x)$ on $\mathbb{F}_2^n$ is given. From the aspects of linear and differential cryptanalysis, this mapping is equivalent to the core quadratic mapping of SIMON via rearrangement of coordinates and EA-equivalence. Based upon...

In this paper we study the problem of recovering a secret S-box from its difference distribution table (DDT). While being an interesting theoretical problem on its own, the ability to recover the S-box from the DDT of a secret S-box can be used in cryptanalytic attacks where the adversary can obtain the DDT (e.g., in Bar-On et al.’s attack on GOST), in supporting theoretical analysis of the properties of difference distribution tables (e.g., in Boura et al.’s work), or as a tool for...

In this work, we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of DDT-equivalence which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion to what we call the $\gamma$-equivalence, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions, demonstrate that the number of DDT- or $\gamma$-equivalent...

In this paper, we analyzed an extreme case of lightweight block cipher design in terms of security and efficiency. To do this, we proposed ELiF block cipher family which has one of the smallest hardware area in a fully serial design. We also defined ELiF to be flexible and scalable so that it can be implemented for real life applications with different scenarios such as fixed key implementations. We also gave hardware implementation results for different implementation settings to show its...

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box $F$ of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of $F$ are far from random and propose a design criteria,...

The fundamental problem of differential cryptanalysis is to find the highest entries in the Difference Distribution Table (DDT) of a given mapping F over n-bit values, and in particular to find the highest diagonal entries which correspond to the best iterative characteristics of $F$. The standard bottom-up approach to this problem is to consider all the internal components of the mapping along some differential characteristic, and to multiply their transition probabilities. However, this...

Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability 1 for an S-Box. The existence of undisturbed bits was found in the S-Box of PRESENT and its inverse. A 13-round improbable differential attack on PRESENT was provided by Tezcan and without using the...