International Association
for Cryptologic Research

Yoroi is a family of space-hard block cipher proposed at TCHES 2021. This cipher contains two parts, a core part and an AES layer to prevent the blackbox adversary. At FSE 2023, Todo and Isobe proposed a code-lifting attack to recover the secret T-box in Yoroi, breaking the security claims of Yoroi. Their work shows that the AES layer is vulnerable in the whitebox model and has no contribution to the security in a hybrid of blackbox and whitebox model. Besides, their attack employs a strong hack model to modify and extract the table entries of the T-box. This hack model is suitable for the environment used by Yoroi while it is difficult to achieve in the practical application.In this paper, we present an attack on Yoroi within a more practical scenario. Compared with the previous attack, our attack is a chosen-plaintext-ciphertext attack in the blackbox phase and assumes that the whitebox attacker has reduced capabilities, as one only needs to extract the AES key without modifying or extracting the table entries. Furthermore, we introduce a family of equivalent representations of Yoroi, using this we can recover an equivalent cipher without any leaked information of table entries. As a result, the complexities of our attack remain almost the same as that of the previous attack.

In this paper, we present a new efficient stand-alone MAC construct named SMAC, based on processing using the Finite State Machine (FSM) part of the stream cipher family SNOW, which in turn uses the AES round function. It offers a combination of very high speed in software and hardware with a truncatable tag. Three concrete base versions of SMAC are proposed, each offering a different security level. SMAC can also be directly integrated with an external ciphering engine in an AEAD mode. Every design decision is thoroughly justified and supported by the results of our cryptanalysis and simulations. Additionally, we introduce an aggregated mode version, SMAC-1xn, in which software performance reaches up to 925 Gbps (around 0.038 cycles per byte) for long messages in a single thread. To the best of our knowledge, SMAC achieves a record-breaking software performance compared to all known MAC engines.

Differential cryptanalysis is one of the main methods of cryptanalysis and has been applied to a wide range of ciphers. While it is very successful, it also relies on certain assumptions that do not necessarily hold in practice. One of these is the hypothesis of stochastic equivalence, which states that the probability of a differential characteristic behaves similarly for all keys. Several works have demonstrated examples where this hypothesis is violated, impacting the attack complexity and sometimes even invalidating the investigated prior attacks. Nevertheless, the hypothesis is still typically taken for granted. In this work, we propose AutoDiVer, an automatic tool that allows to thoroughly verify differential characteristics. First, the tool supports calculating the expected probability of differential characteristics while considering the key schedule of the cipher. Second, the tool supports estimating the size of the space of keys for which the characteristic permits valid pairs, and deducing conditions for these keys. AutoDiVer implements a custom SAT modeling approach and takes advantage of a combination of features of advanced SAT solvers, including approximate model counting and clause learning. To show applicability to many different kinds of block ciphers like strongly aligned, weakly aligned, and ARX ciphers, we apply AutoDiVer to GIFT, PRESENT, RECTANGLE, SKINNY, Midori, WARP, SPECK, and SPEEDY.

We propose a new wide encryption (WE) mode of operation that satisfies robust authenticated encryption (RAE) and committing security with minimum ciphertext expansion. In response to the recent call for proposal by NIST, WE and its tweakable variant, TWE, are attracting much attention in the last few years. Combined with the encode-then-encipher (EtE) construction, TWE offers an RAE that provides robustness against wide range of misuses. The list of desired properties for WE-based authenticated encryption in the NIST standardization includes committing security that considers an attacker who generates ciphertexts that can be decrypted with different decryption contexts, but TWE-based EtE does not provide good committing security, and there is a recent constant-time CMT-4 attack (Chen et al., ToSC 2023(4)). Improving CMT-4 security requires considerable ciphertext expansion, and the state-of-the-art scheme expands the ciphertext by srae + 2scmt bits from an original message to achieve srae-bit RAE and scmt-bit CMT-4 security. Our new WE mode, FFF, addresses the issue by achieving srae-bit RAE and scmt-bit CMT-4 security only with max{scmt, srae} bits of ciphertext expansion. Our design is based on the committing concealer proposed by Bellare et al., and its extension to WE (cf. tag-based AE) while satisfying RAE security is the main technical innovation.

In ToSC 2024(2), Bariant et al. proposed a new framework for designing efficient AES-based Universal Hash Functions (UHFs) and Message Authentification Codes (MACs). They proposed two MAC instances aiming for 128-bit security, PetitMac and LeMac, based on two different UHF candidates. The security of the UHF candidates was evaluated with Mixed Integer Linear Programing (MILP) modeling, to find the minimum number of active S-boxes in differential trails from a non-zero message difference to a zero state difference. The designers claimed at least 26 active S-boxes for the UHF of LeMac.In this corrigendum, we point out that there was a mistake when writing the LeMac specification from the MILP model. The UHF candidate of LeMac presented in the paper does not correspond to the construction analysed with the MILP solver. In particular, the erroneous candidate only guarantees 25 active S-boxes rather than 26. Therefore, we propose to rename the candidate from the original paper to LeMac-0, and propose a fixed version of LeMac, with the correct underlying UHF candidate. The change of specification of LeMac is motivated by the fact that the new specification possesses better security guarantees than LeMac-0 for similar performances.

The Pointer Authentication Code (PAC) feature in the Arm architecture is used to enforce the Code Flow Integrity (CFI) of running programs. It does so by generating a short MAC — called the PAC — of the return address and some additional context information upon function entry, and checking it upon exit. An attacker that wants to overwrite the stack with manipulated addresses now faces an additional hurdle, as they now have to guess, forge, or reuse PAC values. PAC is deployed on billions of devices as a first line of defense to harden system software and complex programs against software exploitation.The original version of the feature uses a 12-round version the QARMA-64 block cipher. The output is then truncated to between 3 and 32 bits, in order to be inserted into unused bits of 64-bit pointers. A later revision of the specification allows the use of an 8-round version of QARMA-64. This reduction may introduce vulnerabilities such as high-probability distinguishers, potentially enabling key recovery attacks. The present paper explores this avenue.A cryptanalysis of the PAC computation function entails restricting the inputs to valid virtual addresses, meaning that certain most significant bits are fixed to zero, and considering only the truncated output. Within these constraints, we present practical attacks on various PAC configurations. These attacks, while not presenting immediate threat to the PAC mechanism, show that some versions of the feature do miss the security targets made for the original function. This offers new insights into the practical security of constructing MAC from truncated block ciphers, expanding on the mostly theoretical understanding of creating PRFs from truncated PRPs.We note that the results do not affect the security of QARMA-64 when used with the recommended number of rounds for general purpose applications.

This work presents an exact and compact formula for the probability of rotation-xor differentials (RX-differentials) through modular addition, for arbitrary rotation amounts, which has been a long-standing open problem. The formula comes with a rigorous proof and is also verified by extensive experiments.Our formula uncovers error in a recent work from 2022 proposing a formula for rotation amounts bigger than 1. Surprisingly, it also affects correctness of the more studied and used formula for the rotation amount equal to 1 (from TOSC 2016). Specifically, it uncovers rare cases where the assumptions of this formula do not hold. Correct formula for arbitrary rotations now opens up a larger search space where one can often find better trails.For applications, we propose automated mixed integer linear programming (MILP) modeling techniques for searching optimal RX-trails based on our exact formula. They are consequently applied to several ARX designs, including Salsa, Alzette and a small-key variant of Speck, and yield many new RX-differential distinguishers, some of them based on provably optimal trails. In order to showcase the relevance of the RX-differential analysis, we also design Malzette, a 12-round Alzette-based permutation with maliciously chosen constants, which has a practical RX-differential distinguisher, while standard differential/linear security arguments suggest sufficient security.

Beyne and Rijmen proposed in 2022 a systematic and generic framework to study the fixed-key probability of differential characteristics. One of the main challenges for implementing this framework is the ability to efficiently handle very large quasidifferential transition matrices (QDTMs) for big (e.g. 8-bit) S-boxes. Our first contribution is a new MILP model capable of efficiently representing such matrices, by exploiting the inherent block structure of these objects. We then propose two extensions to the original framework. First, we demonstrate how to adapt the framework to the related-key setting. Next, we present a novel approach to compute the average expected probability of a differential characteristic that takes the key schedule into account. This method, applicable to both linear and non-linear key schedules, works in both the single-key and related-key settings. Furthermore, it provides a faster way to verify the validity of characteristics compared to computing the fixed-key probability. Using these extensions and our MILP model, we analyze various (related-key) differential characteristics from the literature. First, we prove the validity of several optimal related-key differential characteristics of AES. Next, we show that this approach permits to obtain more precise results than methods relying on key constraints for SKINNY. Finally, we examine the validity of a differential distinguisher used in two differential meet-in-the-middle attacks on SKINNY-128, demonstrating that its probability is significantly higher than initially estimated.

Key lengths in symmetric cryptography are determined with respect to the brute force attacks with current technology. While nowadays at least 128-bit keys are recommended, there are many standards and real-world applications that use shorter keys. In order to estimate the actual threat imposed by using those short keys, precise estimates for attacks are crucial.In this work we provide optimized implementations of several widely used algorithms on GPUs, leading to interesting insights on the cost of brute force attacks on several real-word applications.In particular, we optimize KASUMI (used in GPRS/GSM), SPECK (used in RFID communication), and TEA3 (used in TETRA). Our best optimizations allow us to try 235.72, 236.72, and 234.71 keys per second on a single RTX 4090 GPU. Those results improve upon previous results significantly, e.g. our KASUMI implementation is more than 15 times faster than the optimizations given in the CRYPTO’24 paper [ACC+24] improving the main results of that paper by the same factor.With these optimizations, in order to break GPRS/GSM, RFID, and TETRA communications in a year, one needs around 11, 22 billion, and 1.36 million RTX 4090 GPUs, respectively.For KASUMI, the time-memory trade-off attacks of [ACC+24] can be performed with 142 RTX 4090 GPUs instead of 2400 RTX 3090 GPUs or, when the same amount of GPUs are used, their table creation time can be reduced to 20.6 days from 348 days, crucial improvements for real world cryptanalytic tasks.

Ciminion and Hydra are two recently introduced symmetric key Pseudo- Random Functions for Multi-Party Computation applications. For efficiency, both primitives utilize quadratic permutations at round level. Therefore, polynomial system solving-based attacks pose a serious threat to these primitives. For Ciminion, we construct a quadratic degree reverse lexicographic (DRL) Gröbner basis for the iterated polynomial model via linear transformations. With the Gröbner basis we can simplify cryptanalysis, as we no longer need to impose genericity assumptions to derive complexity estimates. For Hydra, with the help of a computer algebra program like SageMath we construct a DRL Gröbner basis for the iterated model via linear transformations and a linear change of coordinates. In the Hydra proposal it was claimed that rH = 31 rounds are sufficient to provide 128 bits of security against Gröbner basis attacks for an ideal adversary with ω = 2. However, via our Hydra Gröbner basis standard term order conversion to a lexicographic (LEX) Gröbner basis requires just 126 bits with ω = 2. Moreover, using a dedicated polynomial system solving technique up to rH = 33 rounds can be attacked below 128 bits for an ideal adversary.

S-boxes are the most popular nonlinear building blocks used in symmetrickey primitives. Both cryptographic properties and implementation cost of an S-box are crucial for a good cipher design, especially for lightweight ones. This paper aims to determine the exact minimum area of optimal 4-bit S-boxes (whose differential uniform and linearity are both 4) under certain standard cell library. Firstly, we evaluate the upper and lower bounds upon the minimum area of S-boxes, by proposing a Prim-like greedy algorithm and utilizing properties of balanced Boolean functions to construct bijective S-boxes. Secondly, an SAT-aided automatic search tool is proposed that can simultaneously consider multiple cryptographic properties such as the uniform, linearity, algebraic degree, and the implementation costs such as area, and gate depth complexity. Thirdly, thanks to our tool, we manage to find the exact minimum area for different types of 4-bit S-boxes.The measurement in this paper uses the gate equivalent (GE) as standard unit under UMC 180 nm library, all 2/3/4-input logic gates are taken into consideration. Our results show that the minimum area of optimal 4-bit S-box is 11 GE and the depth is 3. If we do not use the 4-input gates, this minimum area increases to 12 GE and the depth in this case is 4, which is the same if we only use 2-input gates. If we further require that the S-boxes should not have fixed points, the minimum area continue increasing a bit to 12.33 GE while keeping the depth. Interestingly, the same results are also obtained for non-optimal 4-bit bijective S-boxes as long as their differential uniform U(S) < 16 and linearity L(S) < 8 (i.e., there is no non-trivial linear structures) if only 2-input and 3-input gates are used. But the minimum area reduce to 9 GE if 4-input gates are involved. More strictly, if we require the algebraic degree of all coordinate functions of optimal S-boxes be 3, the minimum area is 14 GE with fixed point and 14.33 GE without fixed point, and the depth increases sharply to 8.Besides determining the exact minimum area, our tool is also useful to search for a better implementation of existing S-boxes. As a result, we find out an implementation of Keccak’s 5-bit S-box with 17 GE. As a contrast, the designer’s original circuit has an area of 23.33 GE, while the optimized result by Lu et al. achieves an area of 17.66 GE. Also, we find out the first optimized implementation of SKINNY’s 8-bit S-box with 26.67 GE.

Boomerang and rectangle cryptanalysis are powerful cryptanalytic techniques for security evaluation of block ciphers. Automated search for boomerang distinguishers is an important area of research. In FSE 2023, Hadipour et al. proposed a MILP model of searching boomerang distinguishers for Feistel structure, and applied their model to obtain the best known boomerang distinguishers to date for many generalized Feistel ciphers including WARP. In this paper, we focus on improving Hadipour et al.’s model for generalized Feistel structure and boomerang distinguishers on WARP. We show that a boomerang distinguisher with more active S-boxes may have a higher probability. It is caused by the semi-active S-boxes active only in one of the upper and lower differential trails, which are not considered in Hadipour et al.’s model. We classify the active S-boxes in the middle part Em in more detail, according to the associated tables of DDT, DDT2, FBCT and its variants in the computation formula of boomerang probability for Em. Then, we propose an improved MILP model to search boomerang distinguishers for generalized Feistel structure. Applying our model to WARP, we find better boomerang distinguishers for all rounds than those found by Hadipour et al.’s model. For 15-round boomerang distinguisher on WARP, the probability is improved by a factor of 25.78. For the longest 23-round boomerang distinguisher, the probability is improved by a factor of 24.23, resulting in the best result presented on WARP so far. Exploiting the properties of two local structures and the probabilistic extension technique, we improve the 26-round rectangle attack and give the first 27-round rectangle attack on WARP, which extends the best previous rectangle attack by one round. Note that our findings do not threaten the security of WARP which iterates 41 rounds.

A classical way to turn a cryptographic hash function into a MAC (message authentication code) function is by concatenating key and message and interpreting the result as a tag. For the Merkle-Damgård hash function construction, the approach to prepend the key to the message is known to be insecure, as it is vulnerable to the length extension attack. This observation eventually resulted in the introduction of the HMAC construction. The alternative approach to append the key to the message, even though it already dates back to a work of Tsudik from 1992, has never been investigated in detail. In this work, we perform an in-depth treatment on the possibilities to design a MAC function from the Merkle-Damgård hash function construction by processing the key at the suffix. We formalize two constructions: the suffix keyed Merkle-Damgård construction that simply appends key to message, and the suffix blinded Merkle-Damgård construction that blinds the state before compressing the last message, much like the suffix keyed sponge construction (SuKS). We subsequently prove that both constructions are secure in the standard model under reasonable assumptions on the underlying compression function. We finally investigate the security of these constructions in the leaky setting, and demonstrate that the suffix keyed Merkle-Damgård construction is not leakage resilient, but the suffix blinded Merkle-Damgård construction is leakage resilient as long as an appropriate padding rule is adopted and as long as the underlying building blocks are processing secret data in a leakage resilient manner.

We present a number of observations on TEA-3, a stream cipher used in TETRA radio networks that was kept secret until recently. While the same also holds for the six other TETRA encryption algorithms, we pick TEA-3 to start with, as (i) it is not obviously weakened as TEA-{1,4,7} but (ii) in contrast to TEA-2 it is approved for extra-European emergency service, and (iii) as already noted by [MBW23] the TEA-3 design surprisingly contains a non-bijective S-box. Most importantly, we show that the 80-bit non-linear feedback shift register operating on the key decomposes into a cascade of two 40-bit registers. Although this hints at an intentional weakness at first glance, we are not able to lift our results to a practical attack. Other than that, we show how the balanced non-linear feedback functions used in the state register of TEA-3 can be constructed.

Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers’ work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with the unsatisfied restrictions while bringing more degrees of freedom at the same time. Besides, we show that guessing values for different variables will result in different complexity of solving time. With these techniques, the guessing times can be decreased to 252, and the solving time for each guess can be decreased to around 25.2 3-round Keccak calls. As a result, the complexity of finding a preimage for 3-round Keccak-256 can be decreased to around 257.2. For 4-round Keccak[r=640, c=160], an instance of the Crunchy Contest, we use some techniques to save degrees of freedom and make better linearization. Based on these techniques, we build an MILP model and obtain an attack with better complexity of around 260.9. The results of 3-round Keccak-256 and 4-round Keccak[r=640, c=160] are verified with real examples.

Pseudo-Random Injections (PRIs) have been used in several applications in symmetric-key cryptography, such as in the idealization of Authenticated Encryption with Associated Data (AEAD) schemes, building robust AEAD, and, recently, in converting a committing AEAD scheme into a succinctly committing AEAD scheme. In Crypto 2024, Bellare and Hoang showed that if an AEAD scheme is already committing, it can be transformed into a succinctly committing scheme by encrypting part of the plaintext using a PRI. In this paper, we revisit the applications of PRIs in building Message Authentication Codes (MACs) and AEAD schemes. First, we look at some of the properties and definitions of PRIs, such as collision resistance and unforgeability when used as a MAC with a small plaintext space, under different leakage models. Next, we show how they can be combined with collision-resistant hash functions to build a MAC for long plaintexts, offering flexible security depending on how the PRI and equality check are implemented. If both the PRI and equality check are leak-free, the MAC provides almost optimal security, but the security only degrades a little if the equality check is only leakage-resilient (rather than leak-free). If the equality check has unbounded leakage, the security drops to a baseline security rather than being completely insecure. Next, we show how to use PRIs to build a succinctly committing online AEAD scheme from scratch, dubbed as scoAE. It achieves succinct CMT4 security, privacy, and Ciphertext Integrity with Misuse and Leakage (CIML2) security. Last but not least, we show how to build a succinctly committing nonce Misuse-Resistant (MRAE) AEAD scheme, dubbed as scMRAE. The construction combines the SIV paradigm with PRI-based encryption (e.g., the Encode-then-Encipher (EtE) framework).

Over the past decade and a half, cryptanalytic techniques for Salsa20 have been increasingly refined, largely following the overarching concept of Probabilistically Neutral Bits (PNBs) by Aumasson et al. (FSE 2008). In this paper, we present a novel criterion for choosing key-IV pairs using certain 2-round criteria and connect that with clever tweaks of existing techniques related to Probabilistically Independent IV bits (earlier used for ARX ciphers, but not for Salsa20) and well-studied PNBs. Through a detailed examination of the matrix after initial rounds of Salsa20, we introduce the first-ever cryptanalysis of Salsa20 exceeding 8 rounds. Specifically, Salsa20/8.5, consisting of 256 secret key bits, can be cryptanalyzed with a time complexity of 2245.84 and data amounting to 299.47. Further, the sharpness of our attack can be highlighted by showing that Salsa20/8 can be broken with time 2186.01 and data 299.73, which is a significant improvement over the best-known result of Coutinho et al. (Journal of Cryptology, 2023, time 2217.14 and data 2113.14). Here, the refinements related to backward biases for PNBs are also instrumental in achieving the improvements. We also provide certain instances of how these ideas improve the cryptanalysis on 128-bit versions. In the process, a few critical points are raised on some existing state-of-the-art works in this direction, and in those cases, their estimates of time and data are revisited to note the correct complexities, revising the incorrect numbers.

The Ascon authenticated encryption scheme and hash function of Dobraunig et al. (Journal of Cryptology 2021) were recently selected as winner of the NIST lightweight cryptography competition. The mode underlying Ascon authenticated encryption (Ascon-AE) resembles ideas of SpongeWrap, but not quite, and various works have investigated the generic security of Ascon-AE, all covering different attack scenarios and with different bounds. This work systematizes knowledge on the mode security of Ascon-AE, and fills gaps where needed. We consider six mainstream security models, all in the multi-user setting: (i) nonce-respecting security, reflecting on the existing bounds of Chakraborty et al. (ASIACRYPT 2023, ACISP 2024) and Lefevre and Mennink (SAC 2024), (ii) nonce-misuse resistance, observing a non-fixable flaw in the proof of Chakraborty et al. (ACISP 2024), (iii) nonce-misuse resilience, delivering missing security analysis, (iv) leakage resilience, delivering a new security analysis that supersedes the informal proof sketch (though in a different model) of Guo et al. (ToSC 2020), (v) state-recovery security, expanding on the analysis of Lefevre and Mennink, and (vi) release of unverified plaintext, also delivering missing security analysis. We also match all bounds with tight attacks (up to constant and up to reasonable assumptions). As a bonus, we systematize the knowledge on Ascon-Hash and Ascon-PRF.

The sponge is a popular construction for hashing and keyed hashing, and the duplex for authenticated encryption. They are proven to achieve approximately 2c/2 security, where c is the so-called capacity. This approach generalizes to arithmetizationoriented constructions, that operate on elements from a finite field of size p: in this case, security is guaranteed up to pc/2. However, to hash securely, the sponge needs to injectively pad the message, and likewise, authenticated encryption schemes often flip bits in the inner part to ensure domain separation. While these bit manipulations have little (but non-zero) influence on the efficiency and security in case of a field of size 2, they become more profound for larger fields. For example, Reinforced Concrete operates on a field with p ≈ 2256, absorbs 2 elements per permutation evaluation, and has a capacity c = 1. Consequently, injective padding results in superfluous permutation evaluations half of the time, and domain separation in the inner part would reduce the capacity to 0 and thus void security. In this work, we investigate an alternative approach to padding and domain separation for the sponge through the use of non-cryptographic permutations (NCPs) to transform the inner state. The idea dates back to the Merkle-Damgård with permutation construction (ASIACRYPT 2007) but we use it in a much more generalized form in the sponge and in the duplex. We demonstrate that this approach allows for NCP-based padding and NCP-based domain separation at a constant loss, regardless of the size of the field. We apply our findings to arithmetization-oriented element-wise sponging (akin to the recently introduced SAFE) and authenticated encryption.