International Association
for Cryptologic Research

This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.

In ToSC 2023(3), Rasoolzadeh presented an algorithm for classifying (n−m)-resilient Boolean functions with n variables, up to extended variable-permutation equivalence, for a small given positive integer m and any positive integer n with n ≥ m. By applying this algorithm along with several speed-up techniques, he classified n-variable (n − 4)-resilient Boolean functions up to equivalence for any n ≥ 4. However, for m = 5, due to the large number of representative functions, he was unable to classify n-variable (n − 5)-resilient Boolean functions for n > 6.In this work, we apply this algorithm together with a technique to restrict the ANF degree to classify quadratic and cubic (n − 5)-resilient Boolean functions with n variables, up to the same equivalence. We show that there are only 131 quadratic representative functions for any n ≥ 8. Additionally, we show that there are 359 078 cubic representative functions for any n ≥ 14.

Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme, a new transciphering framework called the Real-to-Finite-Field (RtF) framework and a corresponding FHE-friendly symmetric-key primitive called HERA were proposed at ASIACRYPT 2021. Although HERA has a very similar structure to AES, it is considerably different in the following aspects: 1) the power map x → x3 is used as the S-box; 2) a randomized key schedule is used; 3) it is over a prime field Fp with p > 216. In this work, we perform the first third-party cryptanalysis of HERA, by showing how to mount new algebraic attacks with multiple collisions in the round keys. Specifically, according to the special way to randomize the round keys in HERA, we find it possible to peel off the last nonlinear layer by using collisions in the last-round key and a simple property of the power map. In this way, we could construct an overdefined system of equations of a much lower degree in the key, and efficiently solve the system via the linearization technique. As a esult, for HERA with 192 and 256 bits of security, respectively, we could break some parameters under the same assumption made by designers that the algebra constant ω for Gaussian elimination is ω = 2, i.e., Gaussian elimination on an n × n matrix takes O(nω) field operations. If using more conservative choices like ω ∈ {2.8, 3}, our attacks can also successfully reduce the security margins of some variants of HERA to only 1 round. However, the security of HERA with 80 and 128 bits of security is not affected by our attacks due to the high cost to find multiple collisions. In any case, our attacks reveal a weakness of HERA caused by the randomized key schedule and its small state size.

A secure n-bit tweakable block cipher (TBC) using t-bit tweaks can be modeled as a tweakable uniform random permutation, where each tweak defines an independent random n-bit permutation. When an input to this tweakable permutation is fixed, it can be viewed as a perfectly secure t-bit random function. On the other hand, when a tweak is fixed, it can be viewed as a perfectly secure n-bit random permutation, and it is well known that the sum of two random permutations is pseudorandom up to 2n queries.A natural question is whether one can construct a pseudorandom function (PRF) beyond the block and the tweak length bounds using a small number of calls to the underlying tweakable permutations. A straightforward way of constructing a PRF from tweakable permutations is to xor the outputs from two tweakable permutations with c bits of the input to each permutation fixed. Using the multi-user security of the sum of two permutations, one can prove that the (t + n − c)-to-n bit PRF is secure up to 2n+c queries.In this paper, we propose a family of PRF constructions based on tweakable permutations, dubbed XoTPc, achieving stronger security than the straightforward construction. XoTPc is parameterized by c, giving a (t + n − c)-to-n bit PRF. When t < 3n and c = t/3 , XoTPt/3 becomes an (n + 2t/3 )-to-n bit pseudorandom function, which is secure up to 2n+2t/3 queries. It provides security beyond the block and the tweak length bounds, making two calls to the underlying tweakable permutations. In order to prove the security of XoTPc, we extend Mirror theory to q ≫ 2n, where q is the number of equations. From a practical point of view, our construction can be used to construct TBC-based MAC finalization functions and CTR-type encryption modes with stronger provable security compared to existing schemes.

The main goal of this work is to construct authenticated encryption (AE) hat is both committing and leakage-resilient. As a first approach for this we consider generic composition as a well-known method for constructing AE schemes. While the leakage resilience of generic composition schemes has already been analyzed by Barwell et al. (Asiacrypt’17), for committing security this is not the case. We fill this gap by providing a separate analysis of the generic composition paradigms with respect to committing security, giving both positive and negative results: By means of a concrete attack, we show that Encrypt-then-MAC is not committing. Furthermore, we prove that Encrypt-and-MAC is committing, given that the underlying schemes satisfy security notions we introduce for this purpose. We later prove these new notions achievable by providing schemes that satisfy them. MAC-then-Encrypt turns out to be more difficult due to the fact that the tag is not outputted alongside the ciphertext as it is done for the other two composition methods. Nevertheless, we give a detailed heuristic analysis of MAC-then-Encrypt with respect to committing security, leaving a definite result as an open task for future work. Our results, in combination with the fact that only Encrypt-then-MAC yields leakage-resilient AE schemes, show that one cannot obtain AE schemes that are both committing and leakage-resilient via generic composition. As a second approach for constructing committing and leakage-resilient AE, we develop a generic transformation that turns an arbitrary AE scheme into one that fulfills both properties. The transformation relies on a keyed function that is both binding, i.e., it is hard to find key-input pairs that result in the same output, and leakage-resilient pseudorandom.

During recent years, research on authenticated encryption has been thriving through two highly active and practically motivated research directions: provable leakage resilience and key- or context-commitment security. However, the intersection of both fields had been overlooked until very recently. In ToSC 1/2024, Struck and Weishäupl studied generic compositions of encryption schemes and message authentication codes for building committing leakage-resilient schemes. They showed that, in general, Encrypt-then-MAC (EtM) and MAC-then-Encrypt (MtE) are not committing while Encrypt-and-MAC (EaM) is, under plausible and weak assumptions on the components. However, real-world schemes are rarely strict blackbox constructions. Instead, while various leakage-resilient schemes follow blueprints inspired by generic compositions, they often tweak them for security or efficiency.In this paper, we study two blueprints, the first one based on EtM for one of the strongest possible levels of leakage resilience. The second one is a single-pass framework based on leveled implementations. We show that, with a careful selection of the underlying primitives such as with identical encryption and authentication keys and a collision-resistant PRF as the MAC, these blueprints are committing. Our results do not contradict the results by Struck and Weishäupl since we pose more, but practically-motivated, requirements on the components. We demonstrate the practical relevance of our results by showing that our results on those blueprints allow us to easily derive proofs that several state-of-the-art leakage-resilient schemes are indeed committing, including TEDT and its descendants TEDT2 and Romulus-T, as well as the single-pass scheme Triplex.

BipBip is a low-latency tweakable block cipher proposed by Belkheyar et al. in 2023. It was designed for pointer encryption inside a new memory safety mechanism called Cryptographic Capability Computing (C3). BipBip encrypts blocks of 24 bits using a 40-bit tweak and a 256-bit master key and is composed of 11 rounds. n this article, we provide a Demirci-Selçuk Meet-in-the-Middle (DS-MITM) attack against the 11-round (full) variant that breaks the security claim of the designers.

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.

The linear layer of block ciphers plays an important role in their security In particular, ciphers designed following the wide-trail strategy use the branch number of the linear layer to derive bounds on the probability of linear and differential trails. At FSE 2014, the LS-design construction was introduced as a simple and regular structure to design bitsliced block ciphers. It considers the internal state as a bit matrix, and applies alternatively an identical S-Box on all the columns, and an identical L-Box on all the lines. Security bounds are derived from the branch number of the L-Box.In this paper, we focus on bitsliced linear layers inspired by the LS-design construction and the Spook AEAD algorithm. We study the construction of bitsliced linear transformations with efficient implementations using XORs and rotations (optimized for bitsliced ciphers implemented on 32-bit processors), and a high branch number. In order to increase the density of the activity patterns, the linear layer is designed on the whole state, rather than using multiple parallel copies of an L-Box. Our main result is a linear layer for 128-bit ciphers with branch number 21, improving upon the best 32-bit transformation with branch number 12, and the one of Spook with branch number 16.

ChaCha is a well-known stream cipher that has been used in many network protocols and software. In this paper, we study the security of reduced round ChaCha. First, by considering the differential-linear hull effect, we improve the correlation of a four-round differential-linear distinguisher proposed at FSE 2023 by providing other intermediate linear masks. Then, based on the four-round differential-linear distinguisher and the PNB method, by using the assignment 100 ··· 00 for consecutive PNBs, higher backward correlation is obtained and improved key recovery attacks of 7-round and 7.25-round ChaCha are obtained with time complexity 2189.7 and 2223.9, which improve the previously best-known attacks by 217.1 and 214.44, respectively. Finally, we consider the equivalence of the security between (R + 0.25)-round and (R + 0.5)⊕-round ChaCha, and show that (R + 0.25)-round and (R + 0.5)⊕-round ChaCha provide the same security against chosen(known) plaintext attacks. As a result, improved differential-linear cryptanalysis of 7.5⊕-round ChaCha can also be obtained similarly to that of 7.25-round ChaCha, which improves the previously best-known attack by 219.

In this paper, we revisit the division property based dynamic cube attack on the full Grain-128 presented by Hao et al. at FSE 2020 and demonstrate that their attack on the full Grain-128 is invalid, that is, no key information could be successfully recovered. The theoretical framework for the dynamic cube attack provided by Hao et al. is correct, but the technique for building the MILP model in the dynamic cube attack has flaws. Besides, strong evidence indicates that their bias estimation method is not applicable to Grain-128AEAD and Grain-128. Accordingly, we introduce the three-subset division property without unknown subset (3SDP/u) into dynamic cube attacks and present a correct MILP modeling technique. In addition, we propose a heuristic technique called Polynomial Approximation with regard to Bias (PAB) to evaluate the bias in superpolies in the dynamic cube attack, which can provide a more accurate bias evaluation for high-dimension cubes. As a result, we implemented the dynamic cube attack based on 3SDP/u on 190-round Grain-128AEAD, and we could recover 3 key bits with a complexity 2103.44 and the success probability was evaluated to be 99.68%. For Grain-128, some zero-sum distinguishers of cube size 80 are given for the first time.

This paper focuses on equivalences between Generalised Feistel Networks (GFN) of type-II. We introduce a new definition of equivalence which captures the concept that two GFNs are identical up to re-labelling of the inputs/outputs, and give a procedure to test this equivalence relation. Such two GFNs are therefore cryptographically equivalent for several classes of attacks. It induces a reduction o the space of possible GFNs: the set of the (k!)2 possible even-odd GFNs with 2k branches can be partitioned into k! different classes.This result can be very useful when looking for an optimal GFN regarding specific computationally intensive properties, such as the minimal number of active S-boxes in a differential trail. We also show that in several previous papers, many GFN candidates are redundant as they belong to only a few classes. Because of this reduction of candidates, we are also able to suggest better permutations than the one of WARP: they reach 64 active S-boxes in one round less and still have the same diffusion round that WARP. Finally, we also point out a new family of permutations with good diffusion properties.

Ultra-fast AES round-based software cryptographic authentication/encryption primitives have recently seen important developments, fuelled by the authenticated encryption competition CAESAR and the prospect of future high-profile applications such as post-5G telecommunication technology security standards. In particular, Universal Hash Functions (UHF) are crucial primitives used as core components in many popular modes of operation for various use-cases, such as Message Authentication Codes (MACs), authenticated encryption, wide block ciphers, etc. In this paper, we extend and improve upon existing design approaches and present a general framework for the construction of UHFs, relying only on the AES round function and 128-bit word-wide XORs. This framework, drawing inspiration from tweakable block ciphers design, allows both strong security arguments and extremely high throughput. The security with regards to differential cryptanalysis is guaranteed thanks to an optimized MILP modelling strategy, while performances are pushed to their limits with a deep study of the details of AES-NI software implementations. In particular, our framework not only takes into account the number of AES-round calls per message block, but also the very important role of XOR operations and the overall scheduling of the computations.We instantiate our findings with two concrete UHF candidates, both requiring only 2 AES rounds per 128-bit message block, and each used to construct two MACs. First, LeMac, a large-state primitive that is the fastest MAC as of today on modern Intel processors, reaching performances of 0.068 c/B on Intel Ice Lake (an improvement of 60% in throughput compared to the state-of-the-art). The second MAC construction, PetitMac, provides an interesting memory/throughput tradeoff, allowing good performances on many platforms.

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 on satisfiability for finding optimal complete ID attacks in strongly aligned ciphers. While this approach was extended to weakly-aligned designs like PRESENT at ToSC 2024, its application to ARX and AndRX ciphers remained as future work. Moreover, this method only exploited ID distinguishers with direct contradictions at the junction of two deterministic transitions. In contrast, some ID distinguishers, particularly for ARX and AndRX designs, may not be detectable by checking only the existence of direct contradictions.This paper fills these gaps by extending Hadipour et al.’s method to handle indirect contradictions and adapting it for ARX and AndRX designs. We also present a similar method for identifying zero-correlation (ZC) distinguishers. Moreover, we extend our new model for finding ID distinguishers to a unified optimization problem that includes both the distinguisher and the key recovery for AndRX designs. Our method improves ID attacks and introduces new distinguishers for several ciphers, such as SIMON, SPECK, Simeck, ChaCha, Chaskey, LEA, and SipHash. For example, we achieve a one-round improvement in ID attacks against SIMON-64-96, SIMON-64-128, SIMON-128-128, SIMON-128-256 and a two-round improvement against SIMON-128- 192. These results significantly contribute to our understanding of the effectiveness of automated tools in the cryptanalysis of different design paradigms.

Impossible differential cryptanalysis is very important in the field of symmetric ciphers. Currently, there are many automatic search approaches to find impossible differentials. However, these methods have two underlying assumptions: Markov cipher assumption and key independence assumption. Actually, these two assumptions are not true in ARX ciphers, especially lightweight ones. In this paper, we study the impossible differentials in ARX cipher under weak keys for the first time. Firstly, we propose several accurate difference propagation properties on consecutive two and three modular additions. Then, these properties are applied to four typical local constructions composed of two consecutive modular additions, two modular additions with a rotation operation, xoring secret key or constant in the middle, to find impossible differentials under weak keys or special constants. What’s more, we propose a more accurate difference propagation property on three consecutive modular additions. It can be used to find impossible differentials on more complex local constructions under weak keys or special constants. In practical ciphers, these impossible differentials on local constructions can be used to find contradictions. Lastly, combining our new findings with traditional automatic search methods for impossible differentials, we propose a framework to find impossible differentials in ARX ciphers under weak keys. As applications, we apply the framework to SPECK-32/64, LEA and CHAM-64/128. As a result, we find two 8-round impossible differentials for SPECK-32/64 under 260 weak keys, and one 11-round impossible differential for LEA under 2k−1 weak keys, where k is the key size. These impossible differentials can start from any round. Furthermore, we find two 22-round impossible differentials for CHAM-64/128 under 2127 weak keys starting from certain rounds. As far as we know, all these impossible differentials are longer than previous ones.

A transciphering framework, also known as hybrid homomorphic encryption, is a practical method of combining a homomorphic encryption (HE) scheme with a symmetric cipher in the client-server model to reduce computational and communication overload on the client side. As a server homomorphically evaluates a symmetric cipher in this framework, new design rationales are required for “HE-friendly” ciphers that take into account the specific properties of the HE schemes. In this paper, we propose a new TFHE-friendly cipher, dubbed FRAST, with a TFHE-friendly round function based on a random S-box to minimize the number of rounds. The round function of FRAST can be efficiently evaluated in TFHE by a new optimization technique, dubbed double blind rotation. Combined with our new WoP-PBS method, the double blind rotation allows computing multiple S-box calls in the round function of FRAST at the cost of a single S-box call. In this way, FRAST enjoys 2.768 (resp. 10.57) times higher throughput compared to Kreyvium (resp. Elisabeth) for TFHE keystream evaluation in the offline phase of the transciphering framework at the cost of slightly larger communication overload.

The impossible boomerang (IB) attack was first introduced by Lu in his doctoral thesis and subsequently published at DCC in 2011. The IB attack is a variant of the impossible differential (ID) attack by incorporating the idea of the boomerang attack. In this paper, we revisit the IB attack, and introduce the incompatibility of two characteristics in boomerang to the construction of an IB distinguisher. With our methodology, all the constructions of IB distinguisher are represented in a unified manner. Moreover, we show that the related-(twea)key IB distinguishers possess more freedom than the ones of ID so that it can cover more rounds.We also propose a new tool based on Mixed-Integer Quadratically-Constrained Programming (MIQCP) to search for IB attacks. To illustrate the power of the IB attack, we mount attacks against three tweakable block ciphers: Deoxys-BC, Joltik-BC and SKINNY. For Deoxys-BC, we propose a related-tweakey IB attack on 14-round Deoxys-BC-384, which improves the best previous related-tweakey ID attack by 2 rounds, and we improve the data complexity of the best previous related-tweakey ID attack on 10-round Deoxys-BC-256. For Joltik-BC, we propose the best attacks against 10-round Joltik-BC-128 and 14-round Joltik-BC-192 with related-tweakey B attack. For SKINNY-n-3n, we propose a 27-round related-tweakey IB attack, which improves both the time and the memory complexities of the best previous ID attack. We also propose the first related-tweakey IB attack on 28-round SKINNY-n-3n, which improves the previous best ID attack by one round.

The best-known distinguisher on 7-round Ascon-128 and Ascon-128a AEAD uses a 60-dimensional cube where the nonce bits are set to be equal in the third and fourth rows of the Ascon state during initialization (Rohit et al. ToSC 2021/1). It was not known how to use this distinguisher to mount key-recovery attacks. In this paper, we investigate this problem using a new strategy called break-fix for the conditional cube attack. The idea is to introduce slightly-modified cubes which increase the degrees of 7-round output bits to be more than 59 (break phase) and then find key conditions which can bring the degree back to 59 (fix phase). Using this idea, key-recovery attacks on 7-round Ascon-128, Ascon-128a and Ascon-80pq are proposed. The attacks have better time/memory complexities than the existing attacks, and in some cases improve the weak-key attacks as well.

The Nostradamus attack was originally proposed as a security vulnerability for a hash function by Kelsey and Kohno at EUROCRYPT 2006. It requires the attacker to commit to a hash value y of an iterated hash function H. Subsequently, upon being provided with a message prefix P, the adversary’s task is to identify a suffix S such that H(P∥S) equals y. Kelsey and Kohno demonstrated a herding attack requiring O(√n · 22n/3) evaluations of the compression function of H, where n represents the output and state size of the hash, placing this attack between preimage attacks and collision searches in terms of complexity. At ASIACRYPT 2022, Benedikt et al. transform Kelsey and Kohno’s attack into a quantum variant, decreasing the time complexity from O(√n · 22n/3) to O( 3√n · 23n/7). At ToSC 2023, Zhang et al. proposed the first dedicated Nostradamus attack on AES-like hashing in both classical and quantum settings. In this paper, we have made revisions to the multi-target technique incorporated into the meet-in-the-middle automatic search framework. This modification leads to a decrease in time complexity during the online linking phase, effectively reducing the overall attack time complexity in both classical and quantum scenarios. Specifically, we can achieve more rounds in the classical setting and reduce the time complexity for the same round in the quantum setting.

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum collision attacks on hash functions. Their proposal presented a quantum adaptation of the rebound attack and revealed that differential trails, which have too low probability for use in classical settings, might be exploitable in quantum settings. After their work, subsequent research has actively delved into analyzing the security of hash functions in the quantum setting.In this paper, we revisit the quantum rebound attacks on the double block hash function Hirose instantiated with 10-round AES-256 (HCF-AES-256) and 7-round ARIA-256 (HCF-ARIA-256) proposed by Chauhan et al. and Baek et al., respectively. Initially, we identify the flaws in their work and reevaluate the complexity of the attacks. We reveal that the flaws stem from not considering the issue that the S-box differential equation has one solution on average. Earlier research addressed this problem by adding auxiliary bits to the search space. If this method is used to correct the flaws, the resulting time complexities are 217.36 and 220.94 times higher than their proposals. Consequently, in some settings, their attacks become less efficient than generic attacks.Subsequently, we propose improved quantum rebound attacks using nested quantum amplitude amplification and quantum state preparation. Our improved attack efficiently pre-filters the search space, leading to a reduction in overall time complexity. We first classically reduce the search space and employ quantum state preparation to generate a superposition state over the pre-filtered search space. We then use nested quantum amplitude amplification to further reduce the search space quantumly. As a result, we achieve a reduction in the time complexity of the quantum rebound attacks on HCF-AES-256 and HCF-ARIA-256 by factors of 211.2 and 219.5, respectively, making the attacks more efficient than generic attacks again.

Integral, impossible-differential (ID), and zero-correlation (ZC) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most automatic tools regarding integral, ZC, and ID attacks have focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP) model based on satisfiability for finding ID, ZC, and integral distinguishers. This new model can be extended to a unified CP model for finding full key recovery attacks. However, it has limitations, including determining the contradiction location beforehand and a cell-wise model unsuitable for weakly aligned ciphers like Ascon and PRESENT. They also deferred developing a CP model for the partial-sum technique in key recovery as future work.In this paper, we enhance Hadipour et al.’s method in several ways. First, we remove the limitation of determining the contradiction location in advance. Second, we show how to extend the distinguisher model to a bit-wise model, considering the internal structure of S-boxes and keeping the model based on satisfiability. Third, we introduce a CP model for the partial-sum technique for the first time. To show the usefulness and versatility of our approach, we apply it to various designs, from strongly aligned ones like ForkSKINNY and QARMAv2 to weakly aligned ones such as Ascon and PRESENT, yielding significantly improved results. To mention a few of our results, we improve the integral distinguisher of QARMAv2-128 (resp. QARMAv2-64) by 7 (resp. 5) rounds, and the integral distinguisher of ForkSKINNY by 1 round, only thanks to our cell-wise distinguisher modelings. By using our new bit-wise modeling, our tool can find a group of 2155 5-round ID and ZC distinguishers for Ascon in only one run, taking a few minutes on a regular laptop. The new CP model for the partial-sum technique enhances integral attacks on all SKINNY variants, notably improving the best attack on SKINNY-n-n in the single-key setting by 1 round. We also enhance ID attacks on ForkSKINNY and provide the first analysis of this cipher in a limited reduced-round setting. Our methods are generic and applicable to other block ciphers.

Recently, there has been a surge of interest in the security of authenticated encryption with associated data (AEAD) within the context of key commitment frameworks. Security within this framework ensures that a ciphertext chosen by an adversary does not decrypt to two different sets of key, nonce, and associated data. Despite this increasing interest, the security of several widely deployed AEAD schemes has not been thoroughly examined within this framework. In this work, we assess the key committing security of several AEAD schemes. First, the AEGIS family, which emerged as a winner in the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR), and has been proposed to standardization at the IETF. A now outdated version of the draft standard suggested that AEGIS could qualify as a fully committing AEAD scheme; we prove that it is not the case by proposing a novel attack applicable to all variants, which has been experimentally verified. We also exhibit a key committing attack on Rocca-S. Our attacks are executed within the FROB game setting, which is known to be one of the most stringent key committing frameworks. This implies that they remain valid in other, more relaxed frameworks, such as CMT-1, CMT-4, and so forth. Finally, we show that applying the same attack techniques to Rocca and Tiaoxin-346 does not compromise their key-committing security. This observation provides valuable insights into the design of such secure round update functions for AES-based AEAD schemes.

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 study the quantum security of block ciphers based on Simon’s period-finding quantum algorithm. We explored the relations between periodic functions and truncated differentials. The basic observation is that truncated differentials with a probability of 1 can be used to construct periodic functions, and two such constructions are presented with the help of a new notion called difference-annihilation matrix. This technique releases us from the tedious manual work of verifying the period of functions. Based on these new constructions, we find an 8-round quantum distinguisher for LBlock and a 9/10/11/13/15-round quantum distinguisher for SIMON-32/48/64/96/128 which are the best results as far as we know. Besides, to explore the security bounds of block cipher structures against Simon’s algorithm based quantum attacks, the unified structure, which unifies the Feistel, Lai-Massey, and most generalized Feistel structures, is studied. We estimate the exact round number of probability 1 truncated differentials that one can construct. Based on these results, one can easily check the quantum security of specific block ciphers that are special cases of unified structures, when the details of the non-linear building blocks are not considered.

Hash functions are a crucial component in incrementally verifiable computation (IVC) protocols and applications. Among those, recursive SNARKs and folding schemes require hash functions to be both fast in native CPU computations and compact in algebraic descriptions (constraints). However, neither SHA-2/3 nor newer algebraic constructions, such as Poseidon, achieve both requirements. In this work we overcome this problem in several steps. First, for certain prime field domains we propose a new design strategy called Kintsugi, which explains how to construct nonlinear layers of high algebraic degree which allow fast native implementations and at the same time also an efficient circuit description for zeroknowledge applications. Then we suggest another layer, based on the Feistel Type-3 scheme, and prove wide trail bounds for its combination with an MDS matrix. We propose a new permutation design named Monolith to be used as a sponge or compression function. It is the first arithmetization-oriented function with a native performance comparable to SHA3-256. At the same time, it outperforms Poseidon in a circuit using the Merkle tree prover in the Plonky2 framework. Contrary to previously proposed designs, Monolith also allows for efficient constant-time native implementations which mitigates the risk of side-channel attacks.

Authenticated Encryption (AE) modes of operation based on Tweakable Block Ciphers (TBC) usually measure efficiency in the number of calls to the underlying primitive per message block. On the one hand, many existing solutions reach a primitive-rate of 1, meaning that each n-bit block of message asymptotically needs a single call to the TBC with output length n. On the other hand, while these modes look optimal in a blackbox setting, they become less attractive when leakage comes into play, since all these calls must then be equally well protected to maintain security. Leakage-resistant modes improve this situation, by generating ephemeral keys every constant number of calls. However, rekeying is inherently suboptimal in primitive-rate, since a TBC call can only be used either to refresh a key or to encrypt a block. Even worse, existing solutions achieving almost n bits of security for n-bit secret keys have at most a primitive-rate 2/3. Hence the question: Can we design a highly-secure TBC-based rekeying mode with “nearly optimal” primitive-rate? We answer this question positively with Multiplex, a new mode that has primitive-rate d/(d + 1) given a TBC with a dn-bit tweak. Multiplex achieves n − log2(dn) bits of security for both (i) misuse-resilience CCA confidentiality security in the blackbox setting and (ii) Ciphertext Integrity with Misuse-resistant and unbounded Leakage in encryption and decryption (CIML2). It also provides (iii) confidentiality with leakage up to the birthday bound. Furthermore, Multiplex can run d + 1 calls in parallel in each iteration. The combination of these features gives a mode of operation that inherits most of the good implementation features and flexibility of a sponge construction – therefore paving the way towards sound comparisons between TBC-based and permutation-based AE.

The impossible boomerang attack, introduced in 2008 by Jiqiang Lu, is an extension of the impossible differential attack that relies on a boomerang distinguisher of probability 0 for discarding incorrect key guesses. In Lu’s work, the considered impossible boomerang distinguishers were built from 4 (different) probability-1 differentials that lead to 4 differences that do not sum to 0 in the middle, in a miss-in-the-middle way.In this article, we study the possibility of extending this notion by looking at finerlevel contradictions that derive from boomerang switch constraints. We start by discussing the case of quadratic Feistel ciphers and in particular of the Simon ciphers. We exploit their very specific boomerang constraints to enforce a contradiction that creates a new type of impossible boomerang distinguisher that we search with an SMT solver. We next switch to word-oriented ciphers and study how to leverage the Boomerang Connectivity Table contradictions. We apply this idea to SKINNYee, a recent tweakable block cipher proposed at Crypto 2022 and obtain a 21-round distinguisher.After detailing the process and the complexities of an impossible boomerang attack in the single (twea)key and related (twea)key model, we extend our distinguishers into attacks and present a 23-round impossible boomerang attack on Simon-32/64 (out of 32 rounds) and a 29-round impossible boomerang attack on SKINNYee (out of 56 rounds). To the best of our knowledge our analysis covers two more rounds than the (so far, only) other third-party analysis of SKINNYee that has been published to date.

Modular addition is often the most complex component of typical Addition- Rotation-XOR (ARX) ciphers, and the division property is the most effective tool for detecting integral distinguishers. Thus, having a precise division property model for modular addition is crucial in the search for integral distinguishers in ARX ciphers. Current division property models for modular addition either (a) express the operation as a Boolean circuit and apply standard propagation rules for basic operations (COPY, XOR, AND), or (b) treat it as a sequence of smaller functions with carry bits, modeling each function individually. Both approaches were originally proposed for the twosubset bit-based division property (2BDP), which is theoretically imprecise and may overlook some balanced bits.Recently, more precise versions of the division property, such as parity sets, threesubset bit-based division property without unknown subsets (3BDPwoU) or monomial prediction (MP), and algebraic transition matrices have been proposed. However, little attention has been given to modular addition within these precise models.The propagation rule for the precise division property of a vectorial Boolean function f requires that u can propagate to v if and only if the monomial πu(x) appears in πv(f). Braeken and Semaev (FSE 2005) studied the algebraic structure of modular addition and showed that for x ⊞ y = z, the monomial πu(x)πv(y) appears in πw(z) if and only if u + v = w. Their theorem directly leads to a precise division property model for modular addition. Surprisingly, this model has not been applied in division property searches, to the best of our knowledge.In this paper, we apply Braeken and Semaev’s theorem to search for integral distinguishers in ARX ciphers, leading to several new results. First, we improve the state-of-the-art integral distinguishers for all variants of the Speck family, significantly enhancing search efficiency for Speck-32/48/64/96 and detecting new integral distinguishers for Speck-48/64/96/128. Second, we determine the exact degrees of output bits for 7-round Speck-32 and all/16/2 output bits for 2/3/4-round Alzette for the first time. Third, we revisit the choice of rotation parameters in Speck instances, providing a criterion that enhances resistance against integral distinguishers. Additionally, we offer a simpler proof for Braeken and Semaev’s theorem using monomial prediction, demonstrating the potential of division property methods in the study of Boolean functions.We hope that the proposed methods will be valuable in the future design of ARX ciphers.

It is known that the sponge construction is tightly indifferentiable from a random oracle up to around 2c/2 queries, where c is the capacity. In particular, it cannot provide generic security better than half of the underlying permutation size. In this paper, we aim to achieve hash function security beating this barrier. We present a hashing mode based on two b-bit permutations named the double sponge. The double sponge can be seen as the sponge embedded within the double block length hashing paradigm, making two permutation calls in parallel interleaved with an efficient mixing function. Similarly to the sponge, the permutation size is split as b = r+c, and the underlying compression function absorbs r bits at a time. We prove that the double sponge is indifferentiable from a random oracle up to around 22c/3 queries. This means that the double sponge achieves security beyond the birthday bound in the capacity. In addition, if c > 3b/4, the double sponge beats the birthday bound in the primitive size, to our knowledge being the first hashing mode based on a permutation that accomplices this feature.

Reconstructing an S-box from a cryptographic table such as difference distribution table (DDT), linear approximation table (LAT), differential-linear connectivity table (DLCT) or boomerang connectivity table (BCT) is one of the fundamental problems in symmetric-key cryptography. Till now, there are only very few known methods which can reconstruct an S-box from a given table: guess-and-determine algorithms of Boura et al. (DCC 2019) and Tian et al. (DCC 2020), sign determination algorithm of Dunkelman et al. (ToSC 2019) and STP based approach of Lu et al. (DCC 2022). In this paper we consider the reconstruction problem in an even more challenging setup where one needs to reconstruct S-boxes from a partial cryptographic table. We are able to reconstruct S-boxes when only a few number of rows of a cryptographic table is given. This problem has never been studied in the literature. We apply mixed integer linear programming (MILP) as the key tool for solving this problem. Needless to say that we can solve the reconstruction problem when the full table is given and this is the first ever application of MILP tool in solving such fundamental problems. As a further application of our method, we provide the generic MILP models which can search for S-boxes with a given cryptographic property such as differential uniformity, linearity, differential-linear uniformity or boomerang uniformity. Additionally, our method can recover a Boolean function from a given Walsh spectrum or a Boolean function with a given nonlinearity. We also introduce a new heuristic called Optimistic MILP objective that guides the model towards obtaining multiple S-boxes or Boolean functions with the same cryptographic property. We give detailed experimental results for up to 6-bit S-boxes showing the effectiveness of our technique.

Quantum attacks using superposition queries are known to break many classically secure modes of operation. While these attacks do not necessarily threaten the security of the modes themselves, since they rely on a strong adversary model, they help us to draw limits on their provable security.Typically these attacks use the structure of the mode (stream cipher, MAC or authenticated encryption scheme) to embed a period-finding problem, which can be solved with a dedicated quantum algorithm. The hidden period can be recovered with a few superposition queries (e.g., O(n) for Simon’s algorithm), leading to state or key-recovery attacks. However, this strategy breaks down if the period changes at each query, e.g., if it depends on a nonce.In this paper, we focus on this case and give dedicated state-recovery attacks on the authenticated encryption schemes Rocca, Rocca-S, Tiaoxin-346 and AEGIS- 128L. These attacks rely on a procedure to find a Boolean hidden shift with a single superposition query, which overcomes the change of nonce at each query. This approach has the drawback of a lower success probability, meaning multiple independent (and parallelizable) runs are needed.We stress that these attacks do not break any security claim of the authors, and do not threaten the schemes if the adversary only makes classical queries.

DCT is a beyond-birthday-bound (BBB) deterministic authenticated encryption (DAE) mode proposed by Forler et al. in ACISP 2016, ensuring integrity by redundancy. The instantiation of DCT employs the BRW polynomial, which is more efficient than the usual polynomial in GCM by reducing half of the multiplication operations. However, we show that DCT suffers from a small stretch problem similar to GCM. When the stretch length τ is small, choosing a special m-block message, we can reduce the number of queries required by a successful forgery to O(2τ/m). We emphasize that this attack efficiently balances space and time complexity but does not contradict the security bounds of DCT. Finally, we propose an improved scheme named Robust DCT (RDCT) with a minor change to DCT, which improves the security when τ is small and makes it resist the above attack.

For Arithmetization-Oriented ciphers and hash functions Gröbner basis attacks are generally considered as the most competitive attack vector. Unfortunately, the complexity of Gröbner basis algorithms is only understood for special cases, and it is needless to say that these cases do not apply to most cryptographic polynomial systems. Therefore, cryptographers have to resort to experiments, extrapolations and hypotheses to assess the security of their designs. One established measure to quantify the complexity of linear algebra-based Gröbner basis algorithms is the so-called solving degree. Caminata & Gorla revealed that under a certain genericity condition on a polynomial system the solving degree is always upper bounded by the Castelnuovo-Mumford regularity and henceforth by the Macaulay bound, which only takes the degrees and number of variables of the input polynomials into account. In this paper we extend their framework to iterated polynomial systems, the standard polynomial model for symmetric ciphers and hash functions. In particular, we prove solving degree bounds for various attacks on MiMC, Feistel-MiMC, Feistel-MiMC-Hash, Hades and GMiMC. Our bounds fall in line with the hypothesized complexity of Gröbner basis attacks on these designs, and to the best of our knowledge this is the first time that a mathematical proof for these complexities is provided. Moreover, by studying polynomials with degree falls we can prove lower bounds on the Castelnuovo-Mumford regularity for attacks on MiMC, Feistel-MiMC and Feistel-MiMCHash provided that only a few solutions of the corresponding iterated polynomial system originate from the base field. Hence, regularity-based solving degree estimations can never surpass a certain threshold, a desirable property for cryptographic polynomial systems.

In this paper, we perform linear cryptanalysis of the stream cipher SNOW 5G, which is recommended by the international standardization group (SAGE) as one standard algorithm for 5G confidentiality and integrity protection over the wireless channel. SNOW 5G can be regarded as one member of the SNOW-V family, as it is modified from SNOW-Vi by SAGE with a slight improvement. As an overall contribution, we provide a comprehensive and elaborate theoretical analysis of linear approximations of SNOW 5G and provide the best public cryptanalysis result by far. Specifically, we first theoretically analyze the formats of linear masks of SNOW5G that can introduce high correlations, and then search for high-quality linear masks using a divide-and-conquer method based on the different cases of a critical intermediate linear mask. We find a linear approximation of SNOW 5G with correlation −2−67.67 and further launch a correlation attack against it with complexity 2279.8, improving the existing best correlation attack by a factor of 232.4. Our results are mainly from theoretical analysis, which involve little computation overhead and help to better understand the security of SNOW 5G.

Lightweight cryptographic constructions are often optimized on multiple aspects that put the security bounds to the limit. In this respect, it is important to obtain security bounds that are tight and give an accurate and exact indication of the generic security. However, whereas for black-box security bounds it has become common practice to argue tightness of security bounds, for leakage resilience security bounds this is not the case. This is unfortunate, as for leakage resilience results, tightness is even more important as there is already a lossiness incurred in capturing the actual leakage by a theoretical model in the first place.In this work, we consider the SuKS (Suffix Keyed Sponge) PRF construction and investigate tightness of the leakage resilience bound of Dobraunig and Mennink (ToSC 2019). We observe that, although their black-box security result is tight, their leakage resilience bound is not tight in their bounded leakage term λ. We observe that this is caused by the fact that parts of the security bound contain a term covering multicollisions and a term covering leakage, but an adversary is unable to combine both. We next consider improved security of the SuKS for two types of leakage: fixed position leakage, where the adversary directly learns the value of λ bits of a secret state, and Hamming weight leakage, where the Hamming weight of a fixed part of the state is leaked. For fixed position leakage, a very generous form of bounded leakage, we improve the original bound by making wise use of the multicollision limit function of Daemen et al. (ASIACRYPT 2017). For the more realistic setting of Hamming weight leakage, we structurally revisit the multicollision limit function analysis by including Hamming weight in the computation, a problem that is difficult on its own due to the non-uniform character of this type of leakage. In both cases, we improve and tighten the leakage resilience bound of Dobraunig and Mennink. The improved bound for the SuKS has immediate consequences for the leakage resilience of the NIST lightweight cryptography competition finalist ISAP v2, an authenticated encryption scheme that uses the SuKS internally.

A deterministic random bit generator (DRBG) generates pseudorandom bits from an unpredictable seed, i.e., a seed drawn from any random source with sufficient entropy. The current paper formalizes a security notion for a DRBG, in which an attacker may make any legal sequence of requests to the DRBG and sometimes compromise the DRBG state, but should still not be able to distingush DRBG outputs from ideal random bits. The paper proposes XDRBG, a new DRBG based on any eXtendable Output Function (XOF) and proves the security of the XDRBG in the ideal-XOF model. The proven bounds are tight, as demonstrated by matching attacks. The paper also discusses the security of XDRBG against quantum attackers. Finally, the paper proposes concrete instantiations of XDRBG, employing either the SHAKE128 or the SHAKE256 XDRBG. Alternative instantiations suitable for lightweight applications can be based on ASCON.