International Association
for Cryptologic Research

<p> Mixed-Integer Linear Programming (MILP) modeling has become an important tool for both the analysis and the design of symmetric cryptographic primitives. The bit-wise modeling of their nonlinear components, especially the S-boxes, is of particular interest since it allows more informative analysis compared to word-oriented models focusing on counting active S-boxes. At the same time, the size of these models, especially in terms of the number of required inequalities, tends to significantly influence and ultimately limit the applicability of this method to real-world ciphers, especially for larger number of rounds.</p><p> It is therefore of great cryptographic significance to study optimal linear inequality descriptions for Boolean functions. The pioneering works of Abdelkhalek et al. (FSE 2017), Boura and Coggia (FSE 2020) and Li and Sun (FSE 2023) provided various heuristic techniques for this computationally hard problem, decomposing it into two algorithmic steps, coined Problem 1 and Problem 2, with the latter being identical to the well-known NP-hard set cover problem, for which there are many heuristic and exact algorithms in the literature.</p><p> In this paper, we introduce a novel and efficient branch-and-bound algorithm for generating all minimal, non-redundant candidate inequalities that satisfy a given Boolean function, therefore solving Problem 1 in an optimal manner without relying on heuristics. We furthermore prove that our algorithm correctly computes optimal solutions. Using a number of dedicated optimizations, it provides significantly improved runtimes compared to previous approaches and allows the optimal modeling of the difference distribution tables (DDT) and linear approximation tables (LAT) of many practically used S-boxes. The source code for our algorithm is publicly available as a tool for researchers and practitioners in symmetric cryptography. </p>

Extensions of linear cryptanalysis making use of multiple approximations, such as multiple and multidimensional linear cryptanalysis, are an important tool in symmetric-key cryptanalysis, among others being responsible for the best known attacks on ciphers such as Serpent and present. At CRYPTO 2015, Huang et al. provided a refined analysis of the key-dependent capacity leading to a refined key equivalence hypothesis, however at the cost of additional assumptions. Their analysis was extended by Blondeau and Nyberg to also cover an updated wrong key randomization hypothesis, using similar assumptions. However, a recent result by Nyberg shows the equivalence of linear dependence and statistical dependence of linear approximations, which essentially invalidates a crucial assumption on which all these multidimensional models are based. In this paper, we develop a model for linear cryptanalysis using multiple linearly independent approximations which takes key-dependence into account and complies with Nyberg’s result. Our model considers an arbitrary multivariate joint distribution of the correlations, and in particular avoids any assumptions regarding normality. The analysis of this distribution is then tailored to concrete ciphers in a practically feasible way by combining a signal/noise decomposition approach for the linear hulls with a profiling of the actual multivariate distribution of the signal correlations for a large number of keys, thereby entirely avoiding assumptions regarding the shape of this distribution. As an application of our model, we provide an attack on 26 rounds of present which is faster and requires less data than previous attacks, while using more realistic assumptions and far fewer approximations. We successfully extend the attack to present the first 27-round attack which takes key-dependence into account.

Lightweight cryptography was developed in response to the increasing need to secure devices for the Internet of Things. After significant research effort, many new block ciphers have been designed targeting lightweight settings, optimizing efficiency metrics which conventional block ciphers did not. However, block ciphers must be used in modes of operation to achieve more advanced security goals such as data confidentiality and authenticity, a research area given relatively little attention in the lightweight setting. We introduce a new authenticated encryption (AE) mode of operation, SUNDAE, specially targeted for constrained environments. SUNDAE is smaller than other known lightweight modes in implementation area, such as CLOC, JAMBU, and COFB, however unlike these modes, SUNDAE is designed as a deterministic authenticated encryption (DAE) scheme, meaning it provides maximal security in settings where proper randomness is hard to generate, or secure storage must be minimized due to expense. Unlike other DAE schemes, such as GCM-SIV, SUNDAE can be implemented efficiently on both constrained devices, as well as the servers communicating with those devices. We prove SUNDAE secure relative to its underlying block cipher, and provide an extensive implementation study, with results in both software and hardware, demonstrating that SUNDAE offers improved compactness and power consumption in hardware compared to other lightweight AE modes, while simultaneously offering comparable performance to GCM-SIV on parallel high-end platforms.