International Association
for Cryptologic Research

In some linear key recovery attacks, the function which determines the value of the linear approximation is replaced by a similar map in order to improve the time or memory complexity at the cost of a data complexity increase. We propose a general framework for key recovery map substitution, and introduce Walsh spectrum puncturing, which consists of removing carefully-chosen coefficients from the Walsh spectrum of this map. The capabilities of this technique are illustrated by describing improved attacks on reduced-round Serpent (including the first 12-round attack on the 192-bit key variant), GIFT-128 and NOEKEON, as well as the full DES.

QARMAv2 is a general-purpose and hardware-oriented family of lightweight tweakable block ciphers (TBCs) introduced in ToSC 2023. QARMAv2, as a redesign of QARMAv1 with a longer tweak and tighter security margins, is also designed to be suitable for cryptographic memory protection and control flow integrity. The designers of QARMAv2 provided a relatively comprehensive security analysis in the design specification, e.g., some bounds for the number of attacked rounds in differential and boomerang analysis, together with some concrete impossible differential, zerocorrelation, and integral distinguishers. As one of the first third-party cryptanalysis of QARMAv2, Hadipour et al., [HGSE24] significantly improved the integral distinguishers of QARMAv2, and provided the longest concrete distinguishers of QARMAv2 up to now. However, they provided no key recovery attack based on their distinguishers. This paper delves into the cryptanalysis of QARMAv2 to enhance our understanding of its security. Given that the integral distinguishers of QARMAv2 are the longest concrete distinguishers for this cipher so far, we focus on integral attack. To this end, we first further improve the automatic tool introduced by Hadipour et al. [HSE23,HGSE24] for finding integral distinguishers of TBCs following the TWEAKEY framework. This new tool exploits the MixColumns property of QARMAv2 to find integral distinguishers more suitable for key recovery attacks. Then, we combine several techniques for integral key recovery attacks, e.g., Meet-in-the-middle and partial-sum techniques to build a fine-grained integral key recovery attack on QARMAv2. Notably, we demonstrate how to leverage the low data complexity of the integral distinguishers of QARMAv2 to reduce the memory complexity of the meet-in-the-middle technique. As a result, we successfully present the first concrete key recovery attacks on reduced-round versions of QARMAv2. This includes attacking 13 rounds of QARMAv2-64-128 with a single tweak block (T = 1), 14 rounds of QARMAv2-64-128 with two independent tweak blocks (T = 2), and 16 rounds of QARMAv2-128-256 with two independent tweak blocks (T = 2), all in an unbalanced setting. Our attacks do not compromise the claimed security of QARMAv2, but they shed more light on the cryptanalysis of this cipher.

This paper examines the security of Rocca, an authenticated encryption algorithm designed for Beyond 5G/6G contexts. Rocca has been revised multiple times in the initialization and finalization for security reasons. In this paper, we study how the choice of the finalization affects the overall security of Rocca, covering key recovery, universal forgery, and committing attacks. We show a key-recovery attack faster than the exhaustive key search if a linear key mixing is used in the finalization. We also consider the ideally secure keyed finalization, which prevents key-recovery attacks. We show that, in the nonce-misuse setting, this does not prevent universal forgery with a practical data complexity, although the time complexity is high. Our result on committing attacks shows that none of the versions of Rocca considered in this paper is secure. We complete our analysis by presenting a concrete example of colliding inputs against the designers’ latest version of Rocca in the FROB setting, a strong notion of the committing security. Our analysis significantly improves the key committing attack against Rocca shown in ToSC 2024(1)/FSE 2024.

In this paper, we present the first third-party cryptanalysis of SCARF, a tweakable low-latency block cipher designed to thwart contention-based cache attacks through cache randomization. We focus on multiple-tweak differential attacks, exploiting biases across multiple tweaks. We establish a theoretical framework explaining biases for any number of rounds and verify this framework experimentally. Then, we use these properties to develop a key recovery attack on 7-round SCARF with a time complexity of 2^76, achieving a 98.9% success rate in recovering the 240-bit secret key. Additionally, we introduce a distinguishing attack on the full 8-round SCARF in a multi-key setting, with a complexity of c x 2^67.55, demonstrating that SCARF does not provide 80-bit security under these conditions. We also explore whether our approach could be extended to the single-key model and discuss the implications of different S-box choices on the attack success.

We introduce a new approach between classical security proofs of modes of operation and dedicated security analysis for known crypt- analysis families: General Practical Cryptanalysis. This allows us to ana- lyze generically the security of the sum of two keyed permutations against known attacks. In many cases (of course, not all), we show that the se- curity of the sum is strongly linked to that of the composition of the two permutations. This enables the construction of beyond-birthday bound secure low-latency PRFs by cutting a known-to-be-secure block cipher into two equal parts. As a side result, our general analysis shows an in- evitable difficulty for the key recovery based on differential-type attacks against the sum, which leads to a correction of previously published at- tacks on the dedicated design Orthros

<p>This paper presents a new side-channel attack (SCA) on unrolled implementations of stream ciphers, with a particular focus on Trivium. Most conventional SCAs predominantly concentrate on leakage of some first rounds prior to the sufficient diffusion of the secret key and initial vector (IV). However, recently, unrolled hardware implementation has become common and practical, which achieves higher throughput and energy efficiency compared to a round-based hardware. The applicability of conventional SCAs to such unrolled hardware is unclear because the leakage of the first rounds from unrolled hardware is hardly observed. In this paper, focusing on Trivium, we propose a novel SCA on unrolled stream cipher hardware, which can exploit leakage of rounds latter than 80, while existing SCAs exploited intermediate values earlier than 80 rounds. We first analyze the algebraic equations representing the intermediate values of these rounds and present the recursive restricted linear decomposition (RRLD) strategy. This approach uses correlation power analysis (CPA) to estimate the intermediate values of latter rounds. Furthermore, we present a chosen-IV strategy for a successful key recovery through linearization. We experimentally demonstrate that the proposed SCA achieves the key recovery of a 288-round unrolled Trivium hardware implementation using 360,000 traces. Finally, we evaluate the performance of unrolled Trivium hardware implementations to clarify the trade-off between performance and SCA (in)security. The proposed SCA requires 34.5 M traces for a key recovery of 384-round unrolled Trivium implementation and is not applicable to 576-round unrolled hardware. </p>

For an Authenticated Encryption with Associated Data (AEAD) scheme, the key committing security refers to the security notion of whether the adversary can produce a pair of distinct input tuples, including the key, that result in the same output. While the key committing security of various nonce-based AEAD schemes is known, the security analysis of Robust AE (RAE) is largely unexplored. In particular, we are interested in the key committing security of AEAD schemes built on the Encode-then-Encipher (EtE) approach from a wide block cipher. We first consider AEZ v5, the classical and the first dedicated RAE that employs the EtE approach. We focus our analysis on the core part of AEZ to show our best attacks depending on the length of the ciphertext expansion. In the general case where the Tweakable Block Cipher (TBC) is assumed to be ideal, we show a birthday attack and a matching provable security result. AEZ adopts a simpler key schedule and the prove-then-prune approach in the full specification, and we show a practical attack against it by exploiting the simplicity of the key schedule. The complexity is 227, and we experimentally verify the correctness with a concrete example. We also cover two AEAD schemes based on EtE. One is built on Adiantum, and the other one is built on HCTR2, which are two wide block ciphers that are used in real applications. We present key committing attacks against these schemes when used in EtE and matching proofs for particular cases.

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.

Rocca is an authenticated encryption with associated data scheme for beyond 5G/6G systems. It was proposed at FSE 2022/ToSC 2021(2), and the designers make a security claim of achieving 256-bit security against key-recovery and distinguishing attacks, and 128-bit security against forgery attacks (the security claim regarding distinguishing attacks was subsequently weakened in the full version in ePrint 2022/116). A notable aspect of the claim is the gap between the privacy and authenticity security. In particular, the security claim regarding key-recovery attacks allows an attacker to obtain multiple forgeries through the decryption oracle. In this paper, we first present a full key-recovery attack on Rocca. The data complexity of our attack is 2128 and the time complexity is about 2128, where the attack makes use of the encryption and decryption oracles, and the success probability is almost 1. The attack recovers the entire 256-bit key in a single-key and nonce-respecting setting, breaking the 256-bit security claim against key-recovery attacks. We then extend the attack to various security models and discuss several countermeasures to see the feasibility of the security claim. Finally, we consider a theoretical question of whether achieving the security claim of Rocca is possible in the provable security paradigm. We present both negative and positive results to the question.

There is a high demand for whitebox cryptography from the practical use of encryption in untrusted environments. It has been actively discussed for two decades since Chow et al. presented the whitebox implementation of DES and AES. The goal is to resist the key extraction from the encryption program and mitigate the code lifting of the program. At CCS2015, Bogdanov and Isobe proposed space-hard block ciphers as a dedicated design of whitebox block ciphers. It ensures that the key extraction is as difficult as the key recovery in the standard blackbox model. Moreover, to mitigate code lifting, they introduce space hardness, a kind of leakage-resilient security with the incompressibility of a huge program. For space-hard ciphers, code lifting (a partial leakage of the entire program) is useless to copy the functionality.In this paper, we consider a new attack model of space-hard block ciphers called hybrid code lifting. Space-hard block ciphers are intended to ensure security under a size-bounded leakage. However, they do not consider attackers (in the standard blackbox model) receiving the leakage by code lifting. If such attackers can recover the encryption program of a space-hard block cipher, such a cipher does not always satisfy the intention. We analyze Yoroi proposed in TCHES 2021. We introduce the canonical representation of Yoroi. Using the representation enables the recovery of the programs of Yoroi-16 and Yoroi-32 with 233 and 265.6 complexities, respectively, in spite of slight leakage. The canonical representation causes another attack against Yoroi. It breaks an authors’ security claim about the “longevity”. We additionally analyzed SPNbox proposed in Asiacrypt 2016. As a result, considering security on the hybrid code lifting, the original number of rounds is insufficient to achieve 128-bit security under quarter-size leakage.

Incompressibility is one of the most fundamental security goals in white-box cryptography. Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock, we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers. We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an incompressble block cipher. This motivates us to revisit and formalize incompressibility-based security definitions for AEAD schemes and for block ciphers, so that we become able to design modes and reduce their security to that of the underlying ciphers. Our new security notion for AEAD, which we name whPRI, is an extension of the pseudo-random injection security in the black-box setting. Similar security notions are also defined for other cryptosystems such as privacy-only encryption schemes. We emphasize that whPRI ensures quite strong authenticity against white-box adversaries: existential unforgeability beyond leakage. This contrasts sharply with previous notions which have ensured either no authenticity or only universal unforgeability. For the underlying ciphers we introduce a new notion of whPRP, which extends that of PRP in the black-box setting. Interestingly, our incompressibility reductions follow from a variant of public indifferentiability. In particular, we show that a practical whPRI-secure AEAD mode can be built from a whPRP-secure block cipher: We present a SIV-like composition of the sponge construction (utilizing a block cipher as its underlying primitive) with the counter mode and prove that such a construction is (in the variant sense) public indifferentiable from a random injection. To instantiate such an AEAD scheme, we propose a 256-bit variant of SPACE, based on our conjecture that SPACE should be a whPRP-secure cipher.

Integral attacks belong to the classical attack vectors against any given block ciphers. However, providing arguments that a given cipher is resistant against those attacks is notoriously difficult. In this paper, based solely on the assumption of independent round keys, we develop significantly stronger arguments than what was possible before: our main result is that we show how to argue that the sum of ciphertexts over any possible subset of plaintext is key-dependent, i.e., the non existence of integral distinguishers.

Determining the exact algebraic structure or some partial information of the superpoly for a given cube is a necessary step in the cube attack -- a generic cryptanalytic technique for symmetric-key primitives with some secret and public tweakable inputs. Currently, the division property based approach is the most powerful tool for exact superpoly recovery. However, as the algebraic normal form (ANF) of the targeted output bit gets increasingly complicated as the number of rounds grows, existing methods for superpoly recovery quickly hit their bottlenecks. For example, previous method stuck at round 842, 190, and 892 for \trivium, \grain, and \kreyvium, respectively. In this paper, we propose a new framework for recovering the exact ANFs of massive superpolies based on the monomial prediction technique (ASIACRYPT 2020, an alternative language for the division property). In this framework, the targeted output bit is first expressed as a polynomial of the bits of some intermediate states. For each term appearing in the polynomial, the monomial prediction technique is applied to determine its superpoly if the corresponding MILP model can be solved within a preset time limit. Terms unresolved within the time limit are further expanded as polynomials of the bits of some deeper intermediate states with symbolic computation, whose terms are again processed with monomial predictions. The above procedure is iterated until all terms are resolved. Finally, all the sub-superpolies are collected and assembled into the superpoly of the targeted bit. We apply the new framework to \trivium, \grain, and \kreyvium. As a result, the exact ANFs of the superpolies for 843-, 844- and 845-round \trivium, 191-round \grain and 894-round \kreyvium are recovered. Moreover, with help of the M\"{o}bius transform, we present a novel key-recovery technique based on superpolies involving \textit{all} key bits by exploiting the sparse structures, which leads to the best key-recovery attacks on the targets considered.

Energy efficiency is critical in battery-driven devices, and designing energyoptimal symmetric-key ciphers is one of the goals for the use of ciphers in such environments. In the paper by Banik et al. (IACR ToSC 2018), stream ciphers were identified as ideal candidates for low-energy solutions. One of the main conclusions of this paper was that Trivium, when implemented in an unrolled fashion, was by far the most energy-efficient way of encrypting larger quantity of data. In fact, it was shown that as soon as the number of databits to be encrypted exceeded 320 bits, Trivium consumed the least amount of energy on STM 90 nm ASIC circuits and outperformed the Midori family of block ciphers even in the least energy hungry ECB mode (Midori was designed specifically for energy efficiency).In this work, we devise the first heuristic energy model in the realm of stream ciphers that links the underlying algebraic topology of the state update function to the consumptive behaviour. The model is then used to derive a metric that exhibits a heavy negative correlation with the energy consumption of a broad range of stream cipher architectures, i.e., the families of Trivium-like, Grain-like and Subterranean-like constructions. We demonstrate that this correlation is especially pronounced for Trivium-like ciphers which leads us to establish a link between the energy consumption and the security guarantees that makes it possible to find several alternative energy-optimal versions of Trivium that meet the requirements but consume less energy. We present two such designs Trivium-LE(F) and Trivium-LE(S) that consume around 15% and 25% less energy respectively making them the to date most energy-efficient encryption primitives. They inherit the same security level as Trivium, i.e., 80-bit security. We further present Triad-LE as an energy-efficient variant satisfying a higher security level. The simplicity and wide applicability of our model has direct consequences for the conception of future hardware-targeted stream ciphers as for the first time it is possible to optimize for energy during the design phase. Moreover, we extend the reach of our model beyond plain encryption primitives and propose a novel energy-efficient message authentication code Trivium-LE-MAC.

A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium , we show a 842-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 842-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to a distinguishing attack. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. In the application to ACORN , we prove that the 772-round key-recovery attack at ISC2019 is in fact a constant-sum distinguisher. We then give new key-recovery attacks mounting to 773-, 774- and 775-round ACORN . We verify the current best key-recovery attack on 892-round Kreyvium and recover the exact superpoly. We further propose a new attack mounting to 893 rounds.

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.

Only the method to estimate the upper bound of the algebraic degree on block ciphers is known so far, but it is not useful for the designer to guarantee the security. In this paper we provide meaningful lower bounds on the algebraic degree of modern block ciphers.

A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the feature of the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application to Trivium, we show a 841-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 841-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to distinguishing attacks. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds.

A theoretically reliable key-recovery attack should evaluate not only the non-randomness for the correct key guess but also the randomness for the wrong ones as well. The former has always been the main focus but the absence of the latter can also cause self-contradicted results. In fact, the theoretic discussion of wrong key guesses is overlooked in quite some existing key-recovery attacks, especially the previous cube attack variants based on pure experiments. In this paper, we draw links between the division property and several variants of the cube attack. In addition to the zero-sum property, we further prove that the bias phenomenon, the non-randomness widely utilized in dynamic cube attacks and cube testers, can also be reflected by the division property. Based on such links, we are able to provide several results: Firstly, we give a dynamic cube key-recovery attack on full Grain-128. Compared with Dinur et al.’s original one, this attack is supported by a theoretical analysis of the bias based on a more elaborate assumption. Our attack can recover 3 key bits with a complexity 297.86 and evaluated success probability 99.83%. Thus, the overall complexity for recovering full 128 key bits is 2125. Secondly, now that the bias phenomenon can be efficiently and elaborately evaluated, we further derive new secure bounds for Grain-like primitives (namely Grain-128, Grain-128a, Grain-V1, Plantlet) against both the zero-sum and bias cube testers. Our secure bounds indicate that 256 initialization rounds are not able to guarantee Grain-128 to resist bias-based cube testers. This is an efficient tool for newly designed stream ciphers for determining the number of initialization rounds. Thirdly, we improve Wang et al.’s relaxed term enumeration technique proposed in CRYPTO 2018 and extend their results on Kreyvium and ACORN by 1 and 13 rounds (reaching 892 and 763 rounds) with complexities 2121.19 and 2125.54 respectively. To our knowledge, our results are the current best key-recovery attacks on these two primitives.

The security and performance of many integrity proof systems like SNARKs, STARKs and Bulletproofs highly depend on the underlying hash function. For this reason several new proposals have recently been developed. These primitives obviously require an in-depth security evaluation, especially since their implementation constraints have led to less standard design approaches. This work compares the security levels offered by two recent families of such primitives, namely GMiMC and HadesMiMC. We exhibit low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in recently launched public challenges for STARK-friendly hash functions. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we present a practical collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. To achieve those results, we adapt and generalize several cryptographic techniques to fields of odd characteristic.

The design and analysis of dedicated tweakable block ciphers is a quite recent and very active research field that provides an ongoing stream of new insights. For instance, results of Kranz, Leander, and Wiemer from FSE 2017 show that the addition of a tweak using a linear tweak schedule does not introduce new linear characteristics. In this paper, we consider – to the best of our knowledge – for the first time the effect of the tweak on zero-correlation linear cryptanalysis for ciphers that have a linear tweak schedule. It turns out that the tweak can often be used to get zero-correlation linear hulls covering more rounds compared to just searching zero-correlation linear hulls on the data-path of a cipher. Moreover, this also implies the existence of integral distinguishers on the same number of rounds. We have applied our technique on round reduced versions of Qarma, Mantis, and Skinny. As a result, we can present – to the best of our knowledge – the best attack (with respect to number of rounds) on a round-reduced variant of Qarma.

A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.

The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range, e.g., typically 40. These limits were first overcome by the division property based cube attacks proposed by Todo et al. at CRYPTO 2017. Based on MILP modelled division property, for a cube (index set) I, they identify the small (index) subset J of the secret key bits involved in the resultant superpoly. During the precomputation phase which dominates the complexity of the cube attacks, $$2^{|I|+|J|}$$2|I|+|J| encryptions are required to recover the superpoly. Therefore, their attacks can only be available when the restriction $$|I|+|J|<n$$|I|+|J|<n is met.In this paper, we introduced several techniques to improve the division property based cube attacks by exploiting various algebraic properties of the superpoly. 1.We propose the “flag” technique to enhance the preciseness of MILP models so that the proper non-cube IV assignments can be identified to obtain a non-constant superpoly.2.A degree evaluation algorithm is presented to upper bound the degree of the superpoly. With the knowledge of its degree, the superpoly can be recovered without constructing its whole truth table. This enables us to explore larger cubes I’s even if $$|I|+|J|\ge n$$|I|+|J|≥n.3.We provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. As an illustration, we apply our techniques to attack the initialization of several ciphers. To be specific, our key recovery attacks have mounted to 839-round Trivium, 891-round Kreyvium, 184-round Grain-128a and 750-round Acornrespectively.

Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selçuk meet-in-the-middle ($$\mathcal {DS}$$-$$\mathsf {MITM}$$) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque’s work on $$\mathcal {DS}$$-$$\mathsf {MITM}$$ analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack based on general constraint programming, which allows the cryptanalysts to state the problem at a high level without having to say how it should be solved. Our method is not only able to enumerate distinguishers but can also partly automate the key-recovery process. This approach makes the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ cryptanalysis more straightforward and easier to follow, since the resolution of the problem is delegated to off-the-shelf constraint solvers and therefore decoupled from its formulation. We apply the method to SKINNY, TWINE, and LBlock, and we get the currently known best $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attacks on these ciphers. Moreover, to demonstrate the usefulness of our tool for the block cipher designers, we exhaustively evaluate the security of $$8! = 40320$$ versions of LBlock instantiated with different words permutations in the F functions. It turns out that the permutation used in the original LBlock is one of the 64 permutations showing the strongest resistance against the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack. The whole process is accomplished on a PC in less than 2 h. The same process is applied to TWINE, and similar results are obtained.

A dedicated pseudorandom function (PRF) called AES-PRF was proposed by Mennink and Neves at FSE 2018 (ToSC 2017, Issue 3). AES-PRF is obtained from AES by using the output of the 5-th round as the feed-forward to the output state. This paper presents extensive security analysis of AES-PRF and its variants. Specifically, we consider unbalanced variants where the output of the s-th round is used as the feed-forward. We also analyze the security of “dual” constructions of the unbalanced variants, where the input state is used as the feed-forward to the output of the s-th round. We apply an impossible differential attack, zero-correlation linear attack, traditional differential attack, zero correlation linear distinguishing attack and a meet-in-the-middle attack on these PRFs and reduced round versions. We show that AES-PRF is broken whenever s ≤ 2 or s ≥ 6, or reduced to 7 rounds, and Dual-AES-PRF is broken whenever s ≤ 4 or s ≥ 8. Our results on AES-PRF improve the initial security evaluation by the designers in various ways, and our results on Dual-AES-PRF give the first insight to its security.

Search for different types of distinguishers are common tasks in symmetrickey cryptanalysis. In this work, we employ the constraint programming (CP) technique to tackle such problems. First, we show that a simple application of the CP approach proposed by Gerault et al. leads to the solution of the open problem of determining the exact lower bound of the number of active S-boxes for 6-round AES-128 in the related-key model. Subsequently, we show that the same approach can be applied in searching for integral distinguishers, impossible differentials, zero-correlation linear approximations, in both the single-key and related-(twea)key model. We implement the method using the open source constraint solver Choco and apply it to the block ciphers PRESENT, SKINNY, and HIGHT (ARX construction). As a result, we find 16 related-tweakey impossible differentials for 12-round SKINNY-64-128 based on which we construct an 18-round attack on SKINNY-64-128 (one target version for the crypto competition https://sites.google.com/site/skinnycipher announced at ASK 2016). Moreover, we show that in some cases, when equipped with proper strategies (ordering heuristic, restart and dynamic branching strategy), the CP approach can be very efficient. Therefore, we suggest that the constraint programming technique should become a convenient tool at hand of the symmetric-key cryptanalysts.

Current Mixed Integer Linear Programming (MILP)-based search against symmetric-key primitives with 8-bit S-boxes can only build word-wise model to search for truncated differential characteristics. In such a model, the properties of the Differential Distribution Table (DDT) are not considered. To take these properties into account, a bit-wise model is necessary, which can be generated by the H-representation of the convex hull or the logical condition modeling. However, the complexity of both approaches becomes impractical when the size of the S-box exceeds 5 bits. In this paper, we propose a new modeling for large (8-bit or more) S-boxes. In particular, we first propose an algorithm to generate a bit-wise model of the DDT for large S-boxes. We observe that the problem of generating constraints in logical condition modeling can be converted into the problem of minimizing the product-of-sum of Boolean functions, which is a well-studied problem. Hence, classical off-the-shelf solutions such as the Quine-McCluskey algorithm or the Espresso algorithm can be utilized, which makes building a bit-wise model, for 8-bit or larger S-boxes, practical. Then this model is further extended to search for the best differential characteristic by considering the probabilities of each propagation in the DDT, which is a much harder problem than searching for the lower bound on the number of active S-boxes. Our idea is to separate the DDT into multiple tables for each probability and add conditional constraints to control the behavior of these multiple tables. The proposed modeling is first applied to SKINNY-128 to find that there is no differential characteristic having probability higher than 2−128 for 14 rounds, while the designers originally expected that 15 rounds were required. We also applied the proposed modeling to two, arbitrarily selected, constructions of the seven AES round function based constructions proposed in FSE 2016 and managed to improve the lower bound on the number of the active S-boxes in one construction and the upper bound on the differential characteristic for the other.

This paper presents Gimli, a 384-bit permutation designed to achieve high security with high performance across a broad range of platforms, including 64-bit Intel/AMD server CPUs, 64-bit and 32-bit ARM smartphone CPUs, 32-bit ARM microcontrollers, 8-bit AVR microcontrollers, FPGAs, ASICs without side-channel protection, and ASICs with side-channel protection.

In this article, we revisit the design strategy of PRESENT, leveraging all the advances provided by the research community in construction and cryptanalysis since its publication, to push the design up to its limits. We obtain an improved version, named GIFT, that provides a much increased efficiency in all domains (smaller and faster), while correcting the well-known weakness of PRESENT with regards to linear hulls. GIFT is a very simple and clean design that outperforms even SIMON or SKINNY for round-based implementations, making it one of the most energy efficient ciphers as of today. It reaches a point where almost the entire implementation area is taken by the storage and the Sboxes, where any cheaper choice of Sbox would lead to a very weak proposal. In essence, GIFT is composed of only Sbox and bit-wiring, but its natural bitslice data flow ensures excellent performances in all scenarios, from area-optimised hardware implementations to very fast software implementation on high-end platforms.We conducted a thorough analysis of our design with regards to state-of-the-art cryptanalysis, and we provide strong bounds with regards to differential/linear attacks.