The linear layer, which is basically a binary non-singular matrix, is an integral part of cipher construction in a lot of private key ciphers. As a result, optimising the linear layer for device implementation has been an important research direction for about two decades. The Boyar-Peralta's algorithm (SEA'10) is one such common algorithm, which offers significant improvement compared to the straightforward implementation. This algorithm only returns implementation with XOR2 gates, and is deterministic. Over the last couple of years, some improvements over this algorithm has been proposed, so as to make support for XOR3 gates as well as make it randomised. In this work, we take an already existing improvement (Tan and Peyrin, TCHES'20) that allows randomised execution and extend it to support three input XOR gates. This complements the other work done in this direction (Banik et al., IWSEC'19) that also supports XOR3 gates with randomised execution. Further, noting from another work (Maximov, Eprint'19), we include one additional tie-breaker condition in the original Boyar-Peralta's algorithm. Our work thus collates and extends the state-of-the-art, at the same time offers a simpler interface. We show several results that improve from the lastly best-known results.

COMETv1, by Gueron, Jha and Nandi, is a mode of operation for nonce-based authenticated encryption with associated data functionality. It was one of the second round candidates in the ongoing NIST Lightweight Cryptography Standardization Process. In this paper, we study a generalized version of COMETv1, that we call gCOMET, from provable security perspective. First, we present a comprehensive and complete security proof for gCOMET in the ideal cipher model. Second, we view COMET, the underlying mode of operation in COMETv1, as an instantiation of gCOMET, and derive its concrete security bounds. Finally, we propose another instantiation of gCOMET, dubbed COMETv2, and show that this version achieves better security guarantees as well as memory-efficient implementations as compared to COMETv1.

Fast correlation attacks, pioneered by Meier and Staffelbach, is an important cryptanalysis tool for LFSR-based stream cipher, which exploits the correlation between the LFSR state and key stream and targets at recovering the initial state of LFSR via a decoding algorithm. In this paper, we develop a vectorial decoding algorithm for fast correlation attack, which is a natural generalization of original binary approach. Our approach benefits from the contributions of all correlations in a subspace. We propose two novel criterions to improve the iterative decoding algorithm. We also give some cryptographic properties of the new FCA which allows us to estimate the efficiency and complexity bounds. Furthermore, we apply this technique to well-analyzed stream cipher Grain-128a. Based on a hypothesis, an interesting result for its security bound is deduced from the perspective of iterative decoding. Our analysis reveals the potential vulnerability for LFSRs over generic linear group and also for nonlinear functions with high SEI multidimensional linear approximations such as Grain-128a.

Cryptanalysis of the LowMC block cipher when the attacker has access to a single known plaintext/ciphertext pair is a mathematically challenging problem. This is because the attacker is unable to employ most of the standard techniques in symmetric cryptography like linear and differential cryptanalysis. This scenario is particularly relevant while arguing the security of the \picnic digital signature scheme in which the plaintext/ciphertext pair generated by the LowMC block cipher serves as the public (verification) key and the corresponding LowMC encryption key also serves as the secret (signing) key of the signature scheme. In the paper by Banik et al. (IACR ToSC 2020:4), the authors used a linearization technique of the LowMC S-box to mount attacks on some instances of the block cipher. In this paper, we first make a more precise complexity analysis of the linearization attack. Then, we show how to perform a 2-stage MITM attack on LowMC. The first stage reduces the key candidates corresponding to a fraction of key bits of the master key. The second MITM stage between this reduced candidate set and the remaining fraction of key bits successfully recovers the master key. We show that the combined computational complexity of both these stages is significantly lower than those reported in the ToSC paper by Banik et al.

This paper proposes a lightweight authenticated encryption (AE) scheme, called Light-OCB, which can be viewed as a lighter variant of the CAESAR winner OCB as well as a faster variant of the high profi le NIST LWC competition submission LOCUS-AEAD. Light-OCB is structurally similar to LOCUS-AEAD and uses a nonce-based derived key that provides optimal security, and short-tweak tweakable blockcipher (tBC) for efficient domain separation. Light-OCB improves over LOCUS-AEAD by reducing the number of primitive calls, and thereby signi ficantly optimizing the throughput. To establish our claim, we provide FPGA hardware implementation details and benchmark for Light-OCB against LOCUS-AEAD and several other well-known AEs. The implementation results depict that, when instantiated with the tBC TweGIFT64, Light-OCB achieves an extremely low hardware footprint - consuming only around 1128 LUTs and 307 slices (signifi cantly lower than that for LOCUS-AEAD) while maintaining a throughput of 880 Mbps, which is almost twice as that of LOCUS-AEAD. To the best of our knowledge, this fi gure is signi ficantly better than all the known implementation results of other lightweight ciphers with parallel structures.

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-128AEAD, 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-128AEAD, and Kreyvium. As a result, the exact ANFs of the superpolies for 843-, 844- and 845-round Trivium, 191-round Grain-128AEAD and 894-round Kreyvium are recovered. Moreover, with help of the Möbius transform, we present a novel key-recovery technique based on superpolies involving all key bits by exploiting the sparse structures, which leads to the best key-recovery attacks on the targets considered.

Evaluating a block cipher’s strength against differential or linear cryptanalysis can be a difficult task. Several approaches for finding the best differential or linear trails in a cipher have been proposed, such as using mixed integer linear programming or SAT solvers. Recently a different approach was suggested, modelling the problem as a staged, acyclic graph and exploiting the large number of paths the graph contains. This paper follows up on the graph-based approach and models the prob- lem via compressed right-hand side equations. The graph we build contains paths which represent differential or linear trails in a cipher with few active S-boxes. Our method incorporates control over the memory usage, and the time complexity scales linearly with the number of rounds of the cipher being analysed. The proposed method is made available as a tool, and using it we are able to find differential trails for the Klein and Prince ciphers with higher probabilities than previously published.

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.

In a differential cryptanalysis attack, the attacker tries to observe a block cipher's behavior under an input difference: if the system's resulting output differences show any non-random behavior, a differential distinguisher is obtained. While differential cryptanlysis has been known for several decades, Gohr was the first to propose in 2019 the use of machine learning (ML) to build a distinguisher. In this paper, we present the first Partial Differential (PD) ML-distinguisher, and demonstrate its effectiveness on lightweight cipher SPECK32/64. As a PD-ML-distinguisher is based on a selection of bits rather than all bits in a block, we also study if different selections of bits have different impact in the accuracy of the distinguisher, and we find that to be the case. More importantly, we also establish that certain bits have reliably higher effectiveness than others, through a series of independent experiments on different datasets, and we propose an algorithm for assigning an effectiveness score to each bit in the block. By selecting the highest scoring bits, we are able to train a partial ML-distinguisher over 8-bits that is almost as accurate as an equivalent ML-distinguisher over the entire 32 bits (68.8% against 72%), for six rounds of SPECK32/64. The reduced input size implies a significant reduction in the complexity of achieving a distinguisher, and also leads to a reduction in the number of bits of possible subkeys to be guessed in a potential subsequent key recovery attack. These results may therefore open the way to the application of (partial) ML-based distinguishers to ciphers whose block size has so far been considered too large.

MDPH is a double-block-length hash function proposed by Naito at Latincrypt 2019.This is a combination of Hirose's compression function and the domain extender called Merkle-Damg\r{a}rd with permutation (MDP). When instantiated with an $n$-bit block cipher, Naito proved that this achieves the (nearly) optimal indifferentiable security bound of $O(n-\log n)$-bit security. In this paper, we first point out that the proof of the claim contains a gap, which is related to the definition of the simulator in simulating the decryption of the block cipher. We then show that the proof can be fixed. We introduce a new simulator that addresses the issue, showing that MDPH retains its (nearly) optimal indifferentiable security bound of $O(n-\log n)$-bit security.

Designing Boolean functions whose output can be computed with light means at high speed, and satisfying all the criteria necessary to resist all major attacks on the stream ciphers using them as nonlinear components, has been an open problem since the beginning of this century, when algebraic attacks were invented. Functions allowing good resistance are known since 2008, but their output is too complex to compute. Functions with fast and easy to compute output are known which have good algebraic immunity, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have the same cryptographic weakness: their too small nonlinearity. \\In the present paper, we introduce a generalization of the HWB functions into a construction of $n$-variable balanced functions $f$ from $(n-1)$-variable Boolean functions $g$ having some property held by a large number of functions. Function $f$ is defined by its support, equal to the image set of a vectorial function depending on $g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with $f$ when the initial function $g$ equals constant 1. Other well chosen functions $g$ provide functions $f$ having good cryptographic parameters. \\We analyze the constructed functions $f$, we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers.

The infamous Enigma machine was believed to be unbreakable before 1932 simply because of its variable settings and incredible complexity. However, people realised that there is a known pattern in the German messages, which then significantly reduced the number of possible settings and made the code breaker's job easier. Modern cryptanalysis techniques provide a lot more powerful way to break the Enigma cipher using letter frequencies and a concept called index of coincidence. In turn, this technique only works well for the English language(using the characters of the English alphabet), but what if we encountered an Enigma machine designed for the Hungarian language, where the alphabet consists of more than 26 characters? Experiments on the Enigma cipher with different languages have not been done to date, hence in this article we show the language's impact on both the machine and the cipher. Not only the Hungarian, but in fact, any language using more characters than the English language could have a significant effect on the Enigma machine and its complexity if there existed one. By a broad comparative analysis, it is proven that the size of the alphabet has a significant impact on the complexity and therefore the cryptanalysis.

Block cipher DEFAULT has been proposed as a differential fault analysis immune cipher at Asiacrypt 2021. In this paper, we consider the initial version of DEFAULT with no permutation involved in the last round and show that one can find the key in this version with complexity $2^{16}$ by injecting 112 faults. However, our idea does not work in the modified version of the cipher.

Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to use blockciphers with inherently longer keys or develop key-length extension techniques to amplify the security of a blockcipher to use longer keys. We consider the latter approach and revisit the FX and double encryption constructions. Classically, FX was proven to be a secure key-length extension technique, while double encryption fails to be more secure than single encryption due to a meet-in-the-middle attack. In this work we provide positive results, with concrete and tight bounds, for the security of both of these constructions against quantum attackers in ideal models. For FX, we consider a partially-quantum model, where the attacker has quantum access to the ideal primitive, but only classical access to FX. This is a natural model and also the strongest possible, since effective quantum attacks against FX exist in the fully-quantum model when quantum access is granted to both oracles. We provide two results for FX in this model. The first establishes the security of FX against non-adaptive attackers. The second establishes security against general adaptive attackers for a variant of FX using a random oracle in place of an ideal cipher. This result relies on the techniques of Zhandry (CRYPTO '19) for lazily sampling a quantum random oracle. An extension to perfectly lazily sampling a quantum random permutation, which would help resolve the adaptive security of standard FX, is an important but challenging open question. We introduce techniques for partially-quantum proofs without relying on analyzing the classical and quantum oracles separately, which is common in existing work. This may be of broader interest. For double encryption, we show that it amplifies strong pseudorandom permutation security in the fully-quantum model, strengthening a known result in the weaker sense of key-recovery security. This is done by adapting a technique of Tessaro and Thiruvengadam (TCC '18) to reduce the security to the difficulty of solving the list disjointness problem and then showing its hardness via a chain of reductions to the known quantum difficulty of the element distinctness problem.

Message Authentication Code or MAC, is a well-studied cryptographic primitive that is used in order to authenticate communication between two parties sharing a secret key. A Tokenized MAC or TMAC is a related cryptographic primitive, introduced by Ben-David & Sattath (QCrypt'17) which allows limited signing authority to be delegated to third parties via the use of single-use quantum signing tokens. These tokens can be issued using the secret key, such that each token can be used to sign at most one document. We provide an elementary construction for TMAC based on BB84 states. Our construction can tolerate up to 14% noise, making it the first noise-tolerant TMAC construction. The simplicity of the quantum states required for our construction combined with its noise tolerance, makes it practically more feasible than the previous TMAC construction. The TMAC is existentially unforgeable against adversaries with signing and verification oracles (i.e., analogous to EUF-CMA security for MAC), assuming post-quantum one-way functions exist.

LightMAC, by Luykx et al., is a block cipher based message authentication code (MAC). The simplicity of design and low overhead allows it to have very compact implementations. As a result, it has been recently chosen as an ISO/IEC standard MAC for lightweight applications. LightMAC has been shown to achieve query length independent security bound of $O(q^2/2^n)$ when instantiated with two independently keyed $n$-bit block ciphers, where $q$ denotes the number of MAC queries and the query-length is upper bounded by $(n-s)2^s$ bits for a fixed counter size $s$. In this paper, we aim to minimize the number of block cipher keys in LightMAC. First, we show that the original LightMAC instantiated with a single block cipher key, referred as 1k-LightMAC, achieves security bound of $O(q^2/2^n)$ while the query-length is at least $(n-s)$ bits and at most $(n-s)\min\{2^{n/4},2^s\}$ bits. Second, we show that a minor variant of 1k-LightMAC, dubbed as LightMAC-ds, achieves security bound of $O(q^2/2^n)$ while query-length is upper bounded by $(n-s)2^{s-1}$ bits. Of independent interest, our security proof of 1k-LightMAC employs a novel sampling approach, called the reset-sampling, as a subroutine within the H-coefficient proof setup.

In Crypto’19, Gohr proposed the first deep learning-based key recovery attack on 11-round Speck32/64, which opens the direction of neural aided cryptanalysis. Until now, neural aided cryptanalysis still faces two problems: (1) the attack complexity estimations rely purely on practical experiments. There is no theoretical framework for estimating theoretical complexity. (2) it does not work when there are not enough neutral bits that exist in the prepended differential. To the best of our knowledge, we are the first to solve these two problems. In this paper, we propose a Neural Aided Statistical Attack (NASA) that has the following advantages: (1) NASA supports estimating the theoretical complexity. (2) NASA does not rely on any special properties including neutral bits. (3) NASA is applicable to large-size ciphers. Moreover, we propose three methods for reducing the attack complexity of NASA. One of the methods is based on a newly proposed concept named Informative Bit that reveals an important phenomenon. Four attacks on 9-round or 10-round Speck32/64 are executed to verify the correctness of NASA. To further highlight the advantages of NASA, we have performed a series of experiments. At first, we apply NASA and Gohr’s attack to round reduced DES. Since NASA does not rely on neutral bits, NASA breaks 10-round DES while Gohr’s attack breaks 8-round DES. Then, we compare the time consumption of attacks on 11-round Speck32/64. When the newly proposed three methods are used, the time consumption of NASA is almost the same as that of Gohr’s attack. Besides, NASA is applied to 13-round Speck32/64. At last, we introduce how to analyze the resistance of large-size ciphers with respect to NASA, and apply NASA to 14-round Speck96/96. The code of this paper is available at https://github.com/AI-Lab-Y/NASA. Our work arguably raises a new direction for neural aided cryptanalysis.

In this paper, we investigate the use of machine learning classifiers to assess block cipher security from the perspective of differential cryptanalysis. These classifiers were trained using common block cipher features (number of rounds, permutation pattern, truncated input and output differences), making our approach generalizable to an entire class of ciphers. Each data sample represents a truncated differential path, for which the level of security is labelled as secure or insecure by the trained classifier based on the number of differentially active S-boxes. We trained six machine learning classifiers (linear and nonlinear) to perform the security prediction task using a dataset generated from a small-scale generalized Feistel structure (GFS) cipher as a proof-of-concept. Prediction accuracy was further refined by determining the best way to represent features in the dataset during training. We then studied how well these classifiers perform the prediction tasks on ciphers that they were trained on (seen) and those that they were not (unseen). When applied on seen ciphers, the classifiers achieved prediction accuracy results of up to 93% whereas for unseen cipher variants, accuracy results of up to 71% were obtained. Our findings indicate that nonlinear classifiers are better suited for the prediction task. Next, we applied the proposed approach to a full-scale lightweight GFS block cipher, TWINE. By training the best performing nonlinear classifiers (k-nearest neighbour and decision tree classifiers) using data from five other GFS ciphers, we obtained an accuracy of up to 74% when labelling data from TWINE. In addition, the trained classifiers could generalize to a larger number of rounds of TWINE despite being trained using data obtained from fewer rounds. These findings showcase the feasibility of using machine learning classifiers, notably nonlinear variants, as a tool to assess block cipher security.

We consider the related-tweak impossible differential cryptanalysis of \texttt{TweAES}. It is one of the underlying primitives of Authenticated Encryption with Associated Data (AEAD) scheme \texttt{ESTATE} which was accepted as one of second-round candidates in the NIST Lightweight Cryptography Standardization project. Firstly, we reveal several properties of \texttt{TweAES}, which show what kinds of distinguishers are more effective in recovering keys. With the help of automatic solver Simple Theorem Prover (STP), we achieve many 5.5-round related-tweak impossible differentials with fixed input differences and output differences that just have one active byte. Then, we implement 8-round key recovery attacks against \texttt{TweAES} based on one of these 5.5-round distinguishes. Moreover, another 5.5-round distinguisher that has four active bytes at the end is utilized to mount a 7-round key recovery attack against \texttt{TweAES}, which needs much lower attack complexities than the 6-round related-tweak impossible differential attack of \texttt{TweAES} in the design document. Our 8-round key recovery attack is the best one against \texttt{TweAES} in terms of the number of rounds and complexities so far.

We propose to adapt ”low-algebra” digital signature schemes SPHINCS+ and PICNIC, present in the NIST-PQC contest, to the limitations of resource-bounded low-end devices. For this, we replaced the cryptographic primitives (hash functions and symmetric ciphers) of these schemes with lightweight alternatives presented in the NIST-LWC contest. With these specifically conceived primitives, we improve the performance of the signature schemes and still preserve the NIST’s security levels. Regarding SPHINCS+, besides replacing the hash function, we also take into consideration relaxing some parameters and introduce a new notion: security as life expectancy. Furthermore, we also introduce an attack to the SPHINCS+ scheme that takes advantage of the usage of FORS on this scheme and the way its leaves are calculated. Also, we give some solutions on how to avoid this attack. Additionally, a modification of PICNIC is introduced as PICNIC+WOTS where PICNIC is used to generate the secret keys for several WOTS+ signatures significantly reducing the size and signature time of each signature.

Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. In particular, Galois NFSRs with terminal bits are used in the typical stream ciphers Grain and Trivium. One security criterion for the design of stream ciphers is to assure their used NFSRs are nonsingular. The nonsingularity is well solved for Fibonacci NFSRs, whereas it is not for Galois NFSRs. In addition, some types of Galois NFSRs equivalent to Fibonacci ones have been found. However, whether there exist new types of such Galois NFSRs remains unknown. The paper first considers the nonsingularity of Galois NFSRs. Some necessary/sufficient conditions are presented. The paper then concentrates on the equivalence between Galois NFSRs and Fibonacci ones. Some necessary conditions for Galois NFSRs equivalent to Fibonacci ones are provided. The Galois NFSRs with terminal bits equivalent to a given Fibonacci one are enumerated. Moreover, two classes of nonsingular Galois NFSRs with terminal bits are found to be the new types of Galois NFSRs equivalent to Fibonacci ones.

ASCON is one of the elegant designs of authenticated encryption with associated data (AEAD) that was selected as the first choice for lightweight ap- plications in the CAESAR competition, which also has been submitted to NIST lightweight cryptography standardization. ASCON has been in the literature for a while, however, there has been no successful AEAD which is secure at the same time lighter than ASCON. In this article, we have overcome the challenge of constructing a permutation that is lighter than the ASCON permutation while ensuring a similar performance, and based on which we achieve a more lightweight AEAD which we call Sycon. Extensive security analysis of Sycon confirms that it provides the same level of security as that of ASCON. Our hardware implementation result shows that the Sycon permutation has 5.35% reduced area, compared to the ASCON permutation. This leads to a remarkable area reduction for Sycon AEAD which is about 14.95% as compared to ASCON AEAD. We regard the Sycon as a new milestone as it is the lightest among all the AEADs belonging to the ASCON family.

Lightweight cryptography has recently gained importance as the number of Internet of things (IoT) devices connected to Internet grows. Its main goal is to provide cryptographic algorithms that can be run efficiently in resource-limited environments such as IoT. To meet the challenge, the National Institute of Standards and Technology (NIST) announced the Lightweight Cryptography (LWC) project. One of the finalists of the project is the TinyJAMBU cipher. This work evaluates the security of the cipher. The tool used for the evaluation is the cube attack. We present five distinguishing attacks DA1 - DA5 and two key recovery attacks KRA1 - KRA2. The first two distinguishing attacks (DA1 and DA2) are launched against the initialisation phase of the cipher. The best result achieved for the attacks is a distinguisher for a 18-bit cube, where the cipher variant consists of the full initialisation phase together with 438 rounds of the encryption phase. The key recovery attacks (KRA1 and KRA2) are also launched against the initialisation phase of the cipher. The best key recovery attack can be applied for a cipher variant that consists of the full initialisation phase together with 428 rounds of the encryption phase. The attacks DA3 - DA5 present a collection of distinguishers up to 437 encryption rounds, whose 32-bit cubes are chosen from the plaintext, nonce, or associated data bits. The results are confirmed experimentally. A conclusion from the work is that TinyJAMBU has a better security margin against cube attacks than claimed by the designers.

A large number of the symmetric-key mode of operations, such as classical CBC-MAC, have serial structures. While a serial mode gives an implementation advantage in terms of required memory or footprint compared to the parallel counterparts, it wastes the capability of parallel process even when it is available. The problem is becoming more relevant as lightweight cryptography is going to be deployed in the real world. In this article, we propose an alternative implementation strategy for serial MAC modes and serial authenticated encryption (AE) modes that allows 2-block parallel operation for verification/decryption. Our proposal maintains the original functionality and security. It is simple yet novel, and generally applicable to a wide range of existing modes including two NIST recommendations, CMAC and CCM. We demonstrate the effectiveness of our proposal by showing several case studies with software implementations.

ChaCha has been one of the prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack which exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3 rounds. At Crypto $2020$, Beierle et. al. introduced for the first time single bit distinguishers for $3.5$ rounds, which contributed significantly in regaining the flow of research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher of $3.5$-th round helped to produce a 7-round distinguisher of ChaCha and a further improvement in key recovery. In the first part of this paper, we provide the theoretical framework for the distinguisher given by Beierle et. al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at $3.5$ rounds. Also, Beierle et. al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next we revisit the work of Coutinho et. al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed distinguisher and key recovery with complexities $2^{218}$ and $2^{228.51}$ respectively. We show that the differential correlation for $3.5$ rounds is much smaller than the claim of Coutinho et. al. This makes the attack complexities much higher than their claim.

We propose a general technique to improve the key-guessing step of several attacks on block ciphers. This is achieved by defining and studying some new properties of the associated S-boxes and by representing them as a special type of decision trees that are crucial for finding fine-grained guessing strategies for various attack vectors. We have proposed and implemented the algorithm that efficiently finds such trees, and use it for providing several applications of this approach, which include the best known attacks on NOKEON, GIFT, and RECTANGLE.

In this paper, we present a new technique which can be used to find better linear approximations in ARX ciphers. Using this technique, we present the first explicitly derived linear approximations for 3 and 4 rounds of ChaCha and, as a consequence, it enables us to improve the recent attacks against ChaCha. Additionally, we present new differentials for 3 and 3.5 rounds of ChaCha that, when combined with the proposed technique, lead to further improvement in the complexity of the Differential-Linear attacks against ChaCha.

We prove classical and quantum indifferentiability of a rate-1/3 compression function introduced by Shrimpton and Stam (ICALP '08). This construction was one of the first constructions based on three random functions that achieved optimal collision-resistance. We also prove that our result is tight, we define a classical and a quantum attackers that match the indifferentiability security level. Our tight indifferentiability results provide a negative result on the optimality of security of the construction by Shrimpton and Stam, security level of the strong indifferentiability notion is below that of collision-resistance. To arrive at these results, we generalize the results of Czajkowski, Majenz, Schaffner, and Zur (arXiv '19). Our generalization allows to analyze quantum security of constructions based on multiple independent random functions, something not possible before.

Differential Fault Analysis (DFA) is a well known cryptanalytic technique that exploits faulty outputs of an encryption device. Despite its popularity and similarity with the classical Differential Analysis (DA), a thorough analysis explaining DFA from a designer's point of view is missing in the literature. To the best of our knowledge, no DFA immune cipher at an algorithmic level has been proposed so far. Furthermore, all known DFA countermeasures somehow depend on the device/protocol or on the implementation such as duplication/comparison. As all of these are outside the scope of the cipher designer, we focus on designing a primitive which can protect from DFA on its own. We present the first concept of cipher level DFA resistance which does not rely on any device/protocol related assumption, nor does it depend on any form of duplication. Our construction is simple, software/hardware friendly and DFA security scales up with the state size. It can be plugged before and/or after (almost) any symmetric key cipher and will ensure a non-trivial search complexity against DFA. One key component in our DFA protection layer is an SBox with linear structures. Such SBoxes have never been used in cipher design as they generally perform poorly against differential attacks. We argue that they in fact represent an interesting trade-off between good cryptographic properties and DFA resistance. As a proof of concept, we construct a DFA protecting layer, named DEFAULT-LAYER, as well as a full-fledged block cipher DEFAULT. Our solutions compare favourably to the state-of-the-art, offering advantages over the sophisticated duplication based solutions like impeccable circuits/CRAFT or infective countermeasures.

The security proofs of leakage-resilient MACs based on symmetric building blocks currently rely on idealized assumptions that hardly translate into interpretable guidelines for the cryptographic engineers implementing these schemes. In this paper, we first present a leakage-resilient MAC that is both efficient and secure under standard and easily interpretable black box and physical assumptions. It only requires a collision resistant hash function and a single call per message authentication to a Tweakable Block Cipher ($\mathsf{TBC}$) that is unpredictable with leakage. This construction leverages two design twists: large tweaks for the $\mathsf{TBC}$ and a verification process that checks the inverse $\mathsf{TBC}$ against a constant. It enjoys beyond birthday security bounds. We then discuss the cost of getting rid of these design twists. We show that security can be proven without them as well. Yet, a construction without large tweaks requires stronger (non idealized) assumptions and may incur performance overheads if specialized $\mathsf{TBC}$s with large tweaks can be exploited, and a construction without twisted verification requires even stronger assumptions (still non idealized) and leads to more involved bounds. The combination of these results makes a case for our first pragmatic construction and suggests the design of $\mathsf{TBC}$s with large tweaks and good properties for side-channel countermeasures as an interesting challenge.

A new interpretation of linear cryptanalysis is proposed. This 'geometric approach' unifies all common variants of linear cryptanalysis, reveals links between various properties, and suggests additional generalizations. For example, new insights into invariants corresponding to non-real eigenvalues of correlation matrices and a generalization of the link between zero-correlation and integral attacks are obtained. Geometric intuition leads to a fixed-key motivation for the piling-up principle, which is illustrated by explaining and generalizing previous results relating invariants and linear approximations. Rank-one approximations are proposed to analyze cell-oriented ciphers, and used to resolve an open problem posed by Beierle, Canteaut and Leander at FSE 2019. In particular, it is shown how such approximations can be analyzed automatically using Riemannian optimization.

Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes. In this paper, we introduce the \emph{quantum linearization attack}, a new way of using Simon's algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries. We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch's, Bernstein-Vazirani's, and Shor's. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks. Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.

A number of arithmetization-oriented ciphers emerge for use in advanced cryptographic protocols such as secure multi-party computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proofs (ZK) in recent years. The standard block ciphers like AES and the hash functions SHA2/SHA3 are proved to be efficient in software and hardware but not optimal to use in this field, for this reason, new kind of cryptographic primitives were proposed recently. However, unlike traditional ones, there is no standard approach to design and analyze such block ciphers and the hash functions, therefore their security analysis needs to be done carefully. In 2018, StarkWare launched a public STARK-Friendly Hash (SFH) Challenge to select an efficient and secure hash function to be used within ZK-STARKs, transparent and post-quantum secure proof systems. The block cipher JARVIS is one of the first ciphers designed for STARK applications but, shortly after its publication, the cipher has been shown vulnerable to Gröbner basis attack. This paper aims to describe a Gröbner basis attack on new block ciphers, MiMC, GMiMCerf (SFH candidates) and the variants of JARVIS. We present the complexity of Gröbner basis attack on JARVIS-like ciphers. Then we give results from our experiments for the attack on reduced-round MiMC and a structure we found in the Gröbner basis attack for GMiMCerf.

In this report we study efficient binary approximations of the FSM of ZUC-256 with high correlation around $2^{-21.1}$ between the keystream words and the LFSR. We then map these approximations into a binary distinguisher with complexity around $2^{234}$. Thereafter, we convert to an approximation in the LFSR's field $\mathbb{Z}_p$ with correlation around $2^{-33.6}$. We share a number of observations and state open problems for further research and considerations.

In this paper, we propose a new block cipher-based authenticated encryption scheme, dubbed the Synthetic Counter with Masking~(SCM) mode. SCM follows the NSIV paradigm proposed by Peyrin and Seurin~(CRYPTO 2016), where a keyed hash function accepts a nonce N with associated data and a message, yielding an authentication tag T, and then the message is encrypted by a counter-like mode using both T and N. Here we move one step further by encrypting nonces; in the encryption part, the inputs to the block cipher are determined by T, counters, and an encrypted nonce, and all its outputs are also masked by an (additional) encrypted nonce, yielding keystream blocks. As a result, we obtain, for the first time, a block cipher-based authenticated encryption scheme of rate 1/2 that provides n-bit security with respect to the query complexity (ignoring the influence of message length) in the nonce-respecting setting, and at the same time guarantees graceful security degradation in the faulty nonce model, when the underlying n-bit block cipher is modeled as a secure pseudorandom permutation. Seen as a slight variant of GCM-SIV, SCM is also parallelizable and inverse-free, and its performance is still comparable to GCM-SIV.

LightMAC is a lightweight MAC designed by Luykx et al. and recently standardized by ISO/IEC. In this paper, we refine LightMAC and suggest two simple variants called LedMAC1 and LedMAC2. Compared to LightMAC, our first scheme LedMAC1 avoids unnecessary padding without sacrificing the security. Our second scheme LedMAC2 further reduces the number of keys from two to one, and achieves the same level security as that of LightMAC.

We propose a tool for automated truncation of differential trails in ciphers using modular addition, bitwise rotation, and XOR (ARX). The tool takes as input a differential trail and produces as output a set of truncated differential trails. The set represents all possible truncations of the input trail according to certain predefined rules. A linear-time algorithm for the exact computation of the differential probability of a truncated trail that follows the truncation rules is proposed. We further describe a method to merge the set of truncated trails into a compact set of non-overlapping truncated trails with associated probability and we demonstrate the application of the tool on block cipher Speck64. We have also investigated the effect of clustering of differential trails around a fixed input trail. The best cluster that we have found for $15$ rounds has probability $2^{-55.03}$ (consisting of 389 unique output differences) which allows us to build a distinguisher using $128$ times less data than the one based on just the single best trail, which has probability $2^{-62}$. Moreover, we show examples for Speck64 where a cluster of trails around a suboptimal (in terms of probability) input trail results in higher overall probability compared to a cluster obtained around the best differential trail.

The cube attack is a powerful cryptanalysis technique against symmetric cryptosystems, especially for stream ciphers. One of the key step in a cube attack is recovering the superpoly. The division property has been introduced to cube attacks with the aim first to identify variables/monomials that are not involved in the superpoly. Recently,some improved versions of this technique allowing the recovery of the exact superpoly have been developed and applied on various stream ciphers [13,15]. In this paper, we propose a new model to recover the exact superpoly of a stream cipher given a cube. We model the polynomials involved in the stream cipher as a directed graph. It happens that this structure handles some of the monomial cancellations more easily than those based on division property, and this leads to better timing results. We propose two implementations of our model, one in MILP and one in CP, which are up to 10 times faster than the original division property-based model from Hao et al. [13], and consistently 30 to 60 times faster than the monomial prediction-based model from Hu et al. [15].

With the recent development of Internet of Things (IoT) devices, related security issues are also increasing. In particular, the possibility of accessing and hijacking cryptographic devices is also increasing due to the rapid increase in usage of these devices. Therefore, research on cryptographic technologies that can provide a safe environment even in resource-constrained environments has been actively conducted. Among them, there are increasing security issues of side-channel analysis for devices due to their physical accessibility. The lightweight block cipher PIPO was recently proposed in ICISC 2020 to address these issues. The PIPO has the characteristic of providing robust security strength while having less overhead when using the side-channel analysis countermeasures. A differential fault attack is a type of side-channel analysis that induces fault in cryptographic operations and utilizes difference information that occurs. Differential fault attacks on the PIPO have not yet been studied. This paper proposed a single-bit flip-based differential fault attack on the lightweight block cipher PIPO for the first time. We show that simulations enable the recovery of the correct secret key with about 98% probability through 64 fault ciphertexts. Therefore, the PIPO does not provide security against differential fault attacks. When using the PIPO cipher on IoT devices, designers must apply appropriate countermeasures against fault injection attacks.

Gimli is a family of cryptographic primitives (both a hash function and an AEAD scheme) that has been selected for the second round of the NIST competition for standardizing new lightweight designs. The candidate Gimli is based on the permutation Gimli, which was presented at CHES 2017. In this paper, we study the security of both the permutation and the constructions that are based on it. We exploit the slow diffusion in Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity $2^{64}$. We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented. Next, we give (full state) collision and semi-free-start collision attacks on Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in Gimli, and we find a linear distinguisher on the full permutation.

Homomorphic encryption (HE) is a promising cryptographic primitive that enables computation over encrypted data, with a variety of applications including medical, genomic, and financial tasks. In Asiacrypt 2017, Cheon et al. proposed the CKKS scheme to efficiently support approximate computation over encrypted data of real numbers. HE schemes including CKKS, nevertheless, still suffer from slow encryption speed and large ciphertext expansion compared to symmetric cryptography. In this paper, we propose a novel hybrid framework, dubbed RtF (Real-to-Finite-field) framework, that supports CKKS. The main idea behind this construction is to combine the CKKS and the FV homomorphic encryption schemes, and use a stream cipher using modular arithmetic in between. As a result, real numbers can be encrypted without significant ciphertext expansion or computational overload on the client side. As an instantiation of the stream cipher in our framework, we propose a new HE-friendly cipher, dubbed HERA, and extensively analyze its security and efficiency. The main feature of HERA is that it uses a simple randomized key schedule. Compared to recent HE-friendly ciphers such as FLIP and Rasta using randomized linear layers, HERA requires a smaller number of random bits. For this reason, HERA significantly outperforms existing HE-friendly ciphers on both the client and the server sides. With the RtF transciphering framework combined with HERA at the 128-bit security level, we achieve small ciphertext expansion ratio with a range of 1.23 to 1.54, which is at least 23 times smaller than using (symmetric) CKKS-only, assuming the same precision bits and the same level of ciphertexts at the end of the framework. We also achieve 1.6 $\mu$s and 21.7 MB/s for latency and throughput on the client side, which are 9085 times and 17.8 times faster than the CKKS-only environment, respectively.

Grover’s search algorithm allows a quantum adversary to find a k-bit secret key of a block cipher by making O(2k/2) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the T-depth of its circuit implementation (time) and the number of qubits used by the circuit (space). Since the AES S-box is the only component which requires T-gates in the quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low T-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose four methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular,one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its T-depth.

Software watermarking schemes allow a user to embed an identifier into a piece of code such that the resulting program is nearly functionally-equivalent to the original program, and yet, it is difficult to remove the identifier without destroying the functionality of the program. Such schemes are often considered for proving software ownership or for digital rights management. Existing constructions of watermarking have focused primarily on watermarking pseudorandom functions (PRFs). In this work, we revisit the definitional foundations of watermarking, and begin by highlighting a major flaw in existing security notions. Existing security notions for watermarking only require that the identifier be successfully extracted from programs that preserve the exact input/output behavior of the original program. In the context of PRFs, this means that an adversary that constructs a program which computes a quarter of the output bits of the PRF or that is able to distinguish the outputs of the PRF from random are considered to be outside the threat model. However, in any application (e.g., watermarking a decryption device or an authentication token) that relies on PRF security, an adversary that manages to predict a quarter of the bits or distinguishes the PRF outputs from random would be considered to have defeated the scheme. Thus, existing watermarking schemes provide very little security guarantee against realistic adversaries. None of the existing constructions of watermarkable PRFs would be able to extract the identifier from a program that only outputs a quarter of the bits of the PRF or one that perfectly distinguishes. To address the shortcomings in existing watermarkable PRF definitions, we introduce a new primitive called a traceable PRF. Our definitions are inspired by similar definitions from public-key traitor tracing, and aim to capture a very robust set of adversaries: namely, any adversary that produces a useful distinguisher (i.e., a program that can break PRF security), can be traced to a specific identifier. We provide a general framework for constructing traceable PRFs via an intermediate primitive called private linear constrained PRFs. Finally, we show how to construct traceable PRFs from a similar set of assumptions previously used to realize software watermarking. Namely, we obtain a single-key traceable PRF from standard lattice assumptions and a fully collusion-resistant traceable PRF from indistinguishability obfuscation (together with injective one-way functions).

One of the well-known superiorities of GIFT-64 over PRESENT lies in the correction of the strong linear hull effect. However, apart from the investigation of the 9-round linear hull effect in the design document, we find no linear attack result on GIFT-64. Although we do not doubt the security of GIFT-64 regarding the linear cryptanalysis, the actual resistance of the cipher to the linear attack should be evaluated since it promotes a comprehensive perception of the soundness of GIFT-64. Motivated by this observation, we implement an automatic search and find a 12-round linear distinguisher whose dominating trail is an optimal linear characteristic. Following that, the first 19-round linear attack is launched by utilising the newly identified distinguisher. On the other side, we notice that the previous differential attack of GIFT-64 covering 20 rounds claims the entire codebook. To reduce the data complexity of the 20-round attack, we apply the automatic method to exhaustively check 13-round differential trails with probabilities no less than $2^{-64}$ and identify multiple 13-round differentials facilitating 20-round attacks without using the full codebook. One of the candidate differentials with the maximum probability and the minimum number of guessed subkey bits is then employed to realise the first 20-round differential attack without relying on the complete codebook. Given the newly obtained results, we conjecture that the resistances of GIFT-64 against differential and linear attacks do not have a significant gap. Also, we note that the attack results in this paper are far from threatening the security of GIFT-64.

We propose a new construction for format-preserving encryption. Our design provides the flexibility for use in format-preserving encryption (FPE) and for static table-driven tokenization. Our algorithm is a substitution-permutation network based on random Sboxes. Using pseudorandom generators and pseudorandom functions, we prove a strong adaptive security based on the super-pseudorandom permutation assumption of our core design. We obtain empirical parameters to reach this assumption. We suggest parameters for quantum security. Our design accommodates very small domains, with a radix $a$ from 4 to the Unicode alphabet size and a block length $\ell$ starting 2. The number of Sbox evaluations per encryption is asymptotically $\ell^{\frac32}$, which is also the number of bytes we need to generate using AES in CTR mode for each tweak setup. For instance, we tokenize 10 decimal digits using 29 (parallel) AES computations to be done only once, when the tweak changes.

A multi-forkcipher (MFC) is a generalization of the forkcipher (FC) primitive introduced by Andreeva et al. at ASIACRYPT'19. An MFC is a tweakable cipher that computes $s$ output blocks for a single input block, with $s$ arbitrary but fixed. We define the MFC security in the ind-prtmfp notion as indistinguishability from $s$ tweaked permutations. Generalizing tweakable block ciphers (TBCs, $s = 1$), as well as forkciphers ($s=2$), MFC lends itself well to building simple-to-analyze modes of operation that support any number of cipher output blocks. Our main contribution is the generic CTR encryption mode GCTR that makes parallel calls to an MFC to encrypt a message $M$. We analyze the set of all 36 ``simple and natural'' GCTR variants under the nivE security notion by Peyrin and Seurin from CRYPTO'16. Our proof method makes use of an intermediate abstraction called tweakable CTR (TCTR) that captures the core security properties of GCTR common to all variants, making their analyses easier. Our results show that many of the schemes achieve from well beyond birthday bound (BBB) to full $n$-bit security under nonce respecting adversaries and some even BBB and close to full $n$-bit security in the face of realistic nonce misuse conditions. We finally present an efficiency comparison of GCTR using $\mathsf{ForkSkinny}$ (an MFC with $s=2$) with the traditional CTR and the more recent CTRT modes, both are instantiated with the $\mathsf{SKINNY}$ TBC. Our estimations show that any GCTR variant with $\mathsf{ForkSkinny}$ can achieve an efficiency advantage of over $20\%$ for moderately long messages, illustrating that the use of an efficient MFC with $s\geq 2$ brings a clear speed-up.

The HADES design strategy combines the classical SPN construction with the Partial SPN (PSPN) construction, in which at every encryption round, the non-linear layer is applied to only a part of the state. In a HADES design, a middle layer that consists of PSPN rounds is surrounded by outer layers of SPN rounds. The security arguments of HADES with respect to statistical attacks use only the SPN rounds, disregarding the PSPN rounds. This allows the designers to not pose any restriction on the MDS matrix used as the linear mixing operation. In this paper we show that the choice of the MDS matrix significantly affects the security level provided by HADES designs. If the MDS is chosen properly, then the security level of the scheme against differential and linear attacks is significantly higher than claimed by the designers. On the other hand, weaker choices of the MDS allow for extremely large invariant subspaces that pass the entire middle layer without activating any non-linear operation (a.k.a. S-box). We showcase our results on the Starkad and Poseidon instantiations of HADES. For Poseidon, we significantly improve the lower bounds on the number of active S-boxes with respect to both differential and linear cryptanalysis provided by the designers -- for example, from 28 to 60 active S-boxes for the t=6 variant. For Starkad, we show that the t=24 variant proposed by the designers admits an invariant subspace of a huge size of $2^{1134}$ that passes any number of PSPN rounds without activating any S-box. Furthermore, we show that the problem can be fixed easily by replacing t with any value that is not divisible by four.

Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. We point out that the designers of Rasta and Dasta neglected an important property of the $\chi$ operation. Combined with the special structure of Rasta and Dasta, this property directly leads to significantly improved algebraic cryptanalysis. Especially, it enables us to theoretically break 2 out of 3 instances of full Agrasta, which is the aggressive version of Rasta with the block size only slightly larger than the security level in bits. We further reveal that Dasta is more vulnerable to our attacks than Rasta for its usage of a linear layer composed of an ever-changing bit permutation and a deterministic linear transform. Based on our cryptanalysis, the security margins of Dasta and Rasta parameterized with $(n,\kappa,r)\in\{(327,80,4),(1877,128,4),(3545,256,5)\}$ are reduced to only 1 round, where $n$, $\kappa$ and $r$ denote the block size, the claimed security level and the number of rounds, respectively. These parameters are of particular interest as the corresponding ANDdepth is the lowest among those that can be implemented in reasonable time and target the same claimed security level.

Collision attacks on AES-like hashing (hash functions constructed by plugging AES-like ciphers or permutations into the famous PGV modes or their variants) can be reduced to the problem of finding a pair of inputs respecting a differential of the underlying AES-like primitive whose input and output differences are the same. The rebound attack due to Mendel et al. is a powerful tool for achieving this goal, whose quantum version was first considered by Hosoyamada and Sasaki at EUROCRYPT 2020. In this work, we automate the process of searching for the configurations of rebound attacks by taking related-key differentials of the underlying block cipher into account with the MILP-based approach. In the quantum setting, our model guide the search towards characteristics that minimize the resources (e.g., QRAM) and complexities of the resulting rebound attacks. We apply our method to Saturnin-hash, SKINNY, and Whirlpool and improved results are obtained.

The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs. This problem has become ubiquitous in cryptanalytic algorithms, including variants in which the XOR operation is replaced by a modular addition ($k$-SUM) or other non-commutative operations (e.g., the composition of permutations). The case where a single solution exists on average is of special importance. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of ``quantum merging algorithms'' for the k-XOR problem, obtained by combining quantum search. They represented these algorithms by a set of ``merging trees'' and obtained the best ones through linear optimization of their parameters. In this paper, we give a simplified representation of merging trees that makes their analysis easier. We give better quantum algorithms for the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time $\widetilde{\mathcal{O}}(2^{7n/24})$.

Abstract. in this paper, we improve the results of linear approximation of SNOW-V and SNOW-Vi.We optimized the automatic search program by replacing the S-box part with accurate characterizations of the Walsh spectral of S-boxes, which results in a series of trails with higher correlations. On the basis of existing results, we investigate the common features of linear approximation trails with high correlation, and search for more trails by exhausting free masks. By summing up the correlations of trails with the same input and output masks, we get closer to the real correlation. As a result, we get a linear approximation with a correlation -2^{-47.76},which results in a correlation attack on SNOW-V and SNOW-Vi with a time complexity 2^{246:53}, data complexity 2^{237.5} and memory complexity 2^{238.77}.

In this paper, we investigate the security of SNOW-V, demonstrating two guess-and-determine (GnD) attacks against the full version with complexities $2^{384}$ and $2^{378}$, respectively, and one distinguishing attack against a reduced variant with complexity $2^{303}$. Our GnD attacks use enumeration with recursion to explore valid guessing paths, and try to truncate as many invalid guessing paths as possible at early stages of the recursion by carefully designing the order of guessing. In our first GnD attack, we guess three 128-bit state variables, determine the remaining four according to four consecutive keystream words. We finally use the next three keystream words to verify the correct guess. The second GnD attack is similar but exploits one more keystream word as side information helping to truncate more guessing paths. Our distinguishing attack targets a reduced variant where 32-bit adders are replaced with exclusive-OR operations. The samples can be collected from short keystream sequences under different (key, IV) pairs. These attacks do not threaten SNOW-V, but provide more in-depth details for understanding its security and give new ideas for cryptanalysis of other ciphers.

Inserting backdoors in encryption algorithms has long seemed like a very interesting, yet difficult problem. Most attempts have been unsuccessful for symmetric-key primitives so far and it remains an open problem how to build such ciphers. In this work, we propose the MALICIOUS framework, a new method to build tweakable block ciphers that have backdoors hidden which allows to retrieve the secret key. Our backdoor is differential in nature: a specific related-tweak differential path with high probability is hidden during the design phase of the cipher. We explain how any entity knowing the backdoor can practically recover the secret key of a user and we also argue why even knowing the presence of the backdoor and the workings of the cipher will not permit to retrieve the backdoor for an external user. We analyze the security of our construction in the classical black-box model and we show that retrieving the backdoor (the hidden high-probability differential path) is very difficult. We instantiate our framework by proposing the LowMC-M construction, a new family of tweakable block ciphers based on instances of the LowMC cipher, which allow such backdoor embedding. Generating LowMC-M instances is trivial and the LowMC-M family has basically the same efficiency as the LowMC instances it is based on.

This work presents techniques for modeling Boolean functions by mixed-integer linear inequalities (MILP) on binary variables in-place (without auxiliary variables), reaching minimum possible number of inequalities for small functions and providing meaningful lower bounds on the number of inequalities when reaching the minimum is infeasible. While the minimum number of inequalities does not directly translate to best performance in MILP applications, it nonetheless provides a useful benchmark. We remark that our framework is heuristic and relies on SAT solvers and MILP optimization and so its feasibility is limited.

Mixed Integer Linear Programming (MILP) solvers have become one of the most powerful tools for searching cryptographic characteristics, including differentials, impossible differentials, and division trails. Generally, one MILP problem can be formulated by several different MILP models, and the models with fewer constraints and variables are usually easier to solve. How to model a subset of $Z_2^n$ with the least number of constraints is also an interesting mathematical problem. In this paper, we discuss this problem in a general form. Specifically, given a set $C \subset Z_2^n$, let $L$ be a set of inequalities, and we say $L$ describes $C$ if the inequalities in $L$ only involve $n$ variables and the solution set to $L$ is exactly $C$. Our goal is to find such a set $L$ with the least number of inequalities. We present a brand new approach, named as SuperBall approach, for resolving this problem completely. Our approach is able to generate all available inequalities. Once these inequalities are obtained, Sasaki and Todo's method is used to find out the smallest subset of inequalities that describes $C$. If Sasaki and Todo's method succeeds, the found subset will be proved as the smallest. As a result, we found the smallest subsets of inequalities that describe the Sboxes of Keccak and APN-6. The previous best results were 34 and 167, presented in FSE 2020, and we decreased these numbers to 26 and 145. Moreover, we can prove these numbers are the smallest if no dummy variables are used for generating inequalities.

Arbiter based Physical Unclonable Function (sometimes called Physically Unclonable Function, or in short PUF) is a hardware based pseudorandom bit generator. The pseudorandomness in the output bits depends on device specific parameters. For example, based on the delay parameters, an $n$-length Arbiter PUF can be considered as an n-variable Boolean function. We note that the random variation of the delay parameters cannot exhaust all the Boolean functions and the class is significantly smaller as well as restricted. While this is expected (as the autocorrelation property in certain cases is quite biased), we present a more disciplined and first theoretical combinatorial study in this domain. Our work shows how one can explore the functions achieved through an Arbiter based PUF construction with random delay parameters. Our technique mostly shows limitation of such functions from the angle of cryptographic evaluation as the subclass of the Boolean function can be identified with much better efficiency (much less complexity) than random. On the other hand, we note that under certain constrains on the weights of inputs, such a simple model of Arbiter PUFs provide good cryptographic parameters in terms of differential analysis. In this regard, we theoretically solve the problem of autocorrelation properties in a restricted space of input variables with a fixed weight. Experimental evidences complement our theoretical findings.

In this paper, we study the security of the Legendre PRF against quantum attackers, given classical queries only, and without quantum random-access memories. We give two algorithms that recover the key of a shifted Legendre symbol with unknown shift, with a complexity smaller than the exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one is an offline variant of Kuperberg's abelian hidden shift algorithm. We note that the latter, although asymptotically promising, is not currently the most efficient against practical parameters.

A point obfuscator is an obfuscated program that indicates if a user enters a previously stored password. A digital locker is stronger: outputting a key if a user enters a previously stored password. The real-or-random transform allows one to build a digital locker from a composable point obfuscator (Canetti and Dakdouk, Eurocrypt 2008). Ideally, both objects would be nonmalleable, detecting adversarial tampering. Appending a non-interactive zero knowledge proof of knowledge adds nonmalleability in the common random string (CRS) model. Komargodski and Yogev (Eurocrypt, 2018) built a nonmalleable point obfuscator without a CRS. We show a lemma in their proof is false, leaving security of their construction unclear. Bartusek, Ma, and Zhandry (Crypto, 2019) used similar techniques and introduced another nonmalleable point function; their obfuscator is not secure if the same point is obfuscated twice. Thus, there was no composable and nonmalleable point function to instantiate the real-or-random construction. Our primary contribution is a nonmalleable point obfuscator that can be composed any polynomial number of times with the same point (which must be known ahead of time). Security relies on the assumption used in Bartusek, Ma, and Zhandry. This construction enables a digital locker that is nonmalleable with respect to the input password. As a secondary contribution, we introduce a key encoding step to detect tampering on the key. This step combines nonmalleable codes and seed-dependent condensers. The seed for the condenser must be public and not tampered, so this can be achieved in the CRS model. The password distribution may depend on the condenser’s seed as long as it is efficiently sampleable. This construction is black box in the underlying point obfuscation. Nonmalleability for the password is ensured for functions that can be represented as low degree polynomials. Key nonmalleability is inherited from the class of functions prevented by the nonmalleable code.

Multiplicative complexity is a relevant complexity measure for many advanced cryptographic protocols such as multi-party computation, fully homomorphic encryption, and zero-knowledge proofs, where processing AND gates is more expensive than processing XOR gates. For Boolean functions, multiplicative complexity is defined as the minimum number of AND gates that are sufficient to implement a function with a circuit over the basis (AND, XOR, NOT). In this paper, we study the multiplicative complexity of cubic Boolean functions. We propose a method to implement a cubic Boolean function with a small number of AND gates and provide upper bounds on the multiplicative complexity that are better than the known generic bounds.

WARP is proposed by S. Banik et al. in SAC 2020. It is a 128-bit lightweight block cipher with 128-bit key. WARP is based on the 32-nibble type-2 Generalised Feistel Network (GFN) structure. It uses a permutation over nibbles which is designed to optimize the security and efficiency. The designers have provided a lower bound for the number of differentially active S-boxes but the detailed differential characteristics are not provided. In this paper, we discuss the MILP based search technique and present the differential characteristics for the 18-round and 19-round WARP with probability of 2^(-122) and 2^(-132) respectively. We also present a key recovery attack on the 21-round WARP with data complexity of 2^(113 )chosen plaintexts. To the best of our knowledge, these detailed differential characteristics are presented for the first time and this is the first key recovery attack on the 21-round WARP.

Block cipher resistance against differential cryptanalysis is commonly assessed by counting the number of active substitution boxes (S-boxes) using search algorithms or mathematical solvers that incur high computational costs. In this paper, we propose an alternative approach using deep neural networks to predict the number of active S-boxes, trading off exactness for real-time efficiency as the bulk of computational work is brought over to pre-processing (training). Active S-box prediction is framed as a regression task whereby neural networks are trained using features such as input and output differences, number of rounds, and permutation pattern. We first investigate the feasibility of the proposed approach by applying it on a reduced (4-branch) generalized Feistel structure (GFS) cipher. Apart from optimizing a neural network architecture for the task, we also explore the impact of each feature and its representation on prediction error. We then extend the idea to 64-bit GFS ciphers by first training neural networks using data from five different ciphers before using them to predict the number of active S-boxes for TWINE, a lightweight block cipher. The best performing model achieved the lowest root mean square error of 1.62 and R$^2$ of 0.87, depicting the feasibility of the proposed approach.

Block ciphers such as the Advanced Encryption Standard (Rijndael) are used extensively in practice, yet our understanding of their security continues to be highly incomplete. This paper promotes and continues a research program aimed at *proving* the security of block ciphers against important and well-studied classes of attacks. In particular, we initiate the study of (almost) $t$-wise independence of concrete block-cipher construction paradigms such as substitution-permutation networks and key-alternating ciphers. Sufficiently strong (almost) pairwise independence already suffices to resist (truncated) differential attacks and linear cryptanalysis, and hence this is a relevant and meaningful target. Our results are two-fold. Our first result concerns substitution-permutation networks (SPNs) that model ciphers such as AES. We prove the almost pairwise-independence of an SPN instantiated with concrete S-boxes together with an appropriate linear mixing layer, given sufficiently many rounds and independent sub-keys. Our proof relies on a *characterization* of S-box computation on input differences in terms of sampling output differences from certain subspaces, and a new randomness extraction lemma (which we prove with Fourier-analytic techniques) that establishes when such sampling yields uniformity. We use our techniques in particular to prove almost pairwise-independence for sufficiently many rounds of both the AES block cipher (which uses a variant of the patched inverse function $x \mapsto x^{-1}$ as the $S$-box) and the MiMC block cipher (which uses the cubing function $x \mapsto x^3$ as the $S$-box), assuming independent sub-keys. Secondly, we show that instantiating a key-alternating cipher (which can be thought of as a degenerate case of SPNs) with most permutations gives us (almost) $t$-wise independence in $t + o(t)$ rounds. In order to do this, we use the probabilistic method to develop two new lemmas, an *independence-amplification lemma* and a *distance amplification lemma*, that allow us to reason about the evolution of key-alternating ciphers.

Division properties, introduced by Todo at Eurocrypt 2015, are extremely useful in cryptanalysis, are an extension of square attack (also called saturation attack or integral cryptanalysis). Given their im- portance, a large number of works tried to offer automatic tools to find division properties, primarily based on MILP or SAT/SMT. This paper studies better modeling techniques for finding division properties using the Constraint Programming and SAT/SMT-based automatic tools. We use the fact that the Quine-McCluskey algorithm produces a concise CNF representation corresponding to the division trail table of an Sbox. As a result, we can offer significantly more compact models, which allow SAT and Constraint Programming tools to outperform previous results. To show the strength of our new approach, we look at the NIST lightweight candidate KNOT and Ascon. We show several new distinguishers with a lower data complexity for 17-round KNOT-256, KNOT-384 and 19- round KNOT-512. In addition, for the 5-round Ascon, we get a lower data distinguisher than the previous division-based results. Finally, we revisit the method to extend the integral distinguisher by composing linear layers at the input and output. We provide a formu- lation to find the optimal number of linear combinations that need to be considered. As a result of this new formulation, we prove that 18- round KNOT-256 and KNOT-384 have no integral distinguisher using conventional division property and we show this more efficiently than the previous methods.

We introduce SPEEDY, a family of ultra low-latency block ciphers. We mix engineering expertise into each step of the cipher’s design process in order to create a secure encryption primitive with an extremely low latency in CMOS hardware. The centerpiece of our constructions is a high-speed 6-bit substitution box whose coordinate functions are realized as two-level NAND trees. In contrast to other low-latency block ciphers such as PRINCE, PRINCEv2, MANTIS and QARMA, we neither constrain ourselves by demanding decryption at low overhead, nor by requiring a super low area or energy. This freedom together with our gate- and transistor-level considerations allows us to create an ultra low-latency cipher which outperforms all known solutions in single-cycle encryption speed. Our main result, SPEEDY-6-192, is a6-round 192-bit block and 192-bit key cipher which can be executed faster in hardware than any other known encryption primitive (including Gimli in Even-Mansour scheme and the Orthros pseudorandom function) and offers 128-bit security. One round more, i.e., SPEEDY-7-192, provides full 192-bit security. SPEEDY primarily targets hardware security solutions embedded in high-end CPUs, where area and energy restrictions are secondary while high performance is the number one priority.

A new approach to the security analysis of hardware-oriented masked ciphers against second-order side-channel attacks is developed. By relying on techniques from symmetric-key cryptanalysis, concrete security bounds are obtained in a variant of the probing model that allows the adversary to make only a bounded, but possibly very large, number of measurements. Specifically, it is formally shown how a bounded-query variant of robust probing security can be reduced to the linear cryptanalysis of masked ciphers. As a result, the compositional issues of higher-order threshold implementations can be overcome without relying on fresh randomness. From a practical point of view, the aforementioned approach makes it possible to transfer many of the desirable properties of first-order threshold implementations, such as their low randomness usage, to the second-order setting. For example, a straightforward application to the block cipher LED results in a masking using less than 700 random bits including the initial sharing. In addition, the cryptanalytic approach introduced in this paper provides additional insight into the design of masked ciphers and allows for a quantifiable trade-off between security and performance.

Recently, Bar-On et al. introduced at Eurocrypt’19 a new tool, called the differential-linear connectivity table (DLCT), which allows for taking into account the dependency between the two subciphers E_0 and E_1 involved in differential-linear attacks. This paper presents a theoretical characterization of the DLCT, which corresponds to an autocorrelation table (ACT) of a vectorial Boolean function. We further provide some new theoretical results on ACTs of vectorial Boolean functions.

The keys of modern cryptographic algorithms have an enormous size, so the testing of the algorithm performance for all key combinations, will take practically an infinite time. To avoid this, the sampling method is used, where a much smaller number of keys is tested and then the estimation of the algorithm performance for all the keys is calculated with a predetermined sampling error. For each sampling key, an output sample of the algorithm must be generated and tested. Therefore, in order to have sampling results as close as possible to the real performance of the algorithm, the key question is whether the selection of the keys should be random or it must follow some rules. If the selection of the keys is completely random, there is a high probability that the tests will not find some "weak" or "equivalent" keys, which give non-random or similar outputs and therefore reduce the total number of active keys. But if the sampling keys are selected with some specific criteria, there is a much greater probability of detecting any weak or equivalent key. In this study an optimal key selection methodology is proposed, which combines the random and the non-random key selection.

The bulk of Internet interactions is highly redundant and also security sensitive. To reduce communication bandwidth and provide a desired level of security, a data stream is first compressed to squeeze out redundant bits and then encrypted using authenticated encryption. This generic solution is very flexible and works well for any pair of (compression, encryption) algorithms. Its downside, however, is the fact that the two algorithms are designed independently. One would expect that designing a single algorithm that compresses and encrypts (called compcrypt) should produce benefits in terms of efficiency and security. The work investigates how to design a compcrypt algorithm using the ANS compression. First, we examine basic properties of ANS and show that a plain ANS with a hidden encoding table can be broken by statistical attacks. Next, we study ANS behaviour when its states are chosen at random. Our compcrypt algorithm is built using ANS with randomised state jumps and a sponge MonkeyDuplex encryption. Its security and efficiency are discussed. The design provides 128-bit security for both confidentiality and integrity/authentication. Our implementation experiments show that our compcrypt algorithm processes symbols with a rate up to 269 MB/s (with a slight loss of compression rate).

Fault attacks (FA) intentionally inject some fault into the encryption process for analyzing a secret key based on faulty intermediate values or faulty ciphertexts. One of the easy ways for software-based countermeasures is to use time redundancy. However, existing methods can be broken by skipping comparison operations or by using non-uniform distributions of faulty intermediate values. In this paper, we propose a secure software-based redundancy, aptly named table redundancy, applying different linear and nonlinear transformations to redundant computations of table-based block cipher structures. To reduce the table size and the number of lookups, some outer tables that are not subjected to FA are shared, while the inner tables are protected by table redundancy. The basic idea is that different transformations protecting redundant computations are correctly decoded if the redundant outcomes are combined without faulty values. In addition, this recombination provides infective computations because a faulty byte is likely to propagate its error to adjacent bytes due to the use of 32-bit linear transformations. Our method also presents a stateful feature in the connection with detected faults and subsequent plaintexts for preventing iterative fault injection. We demonstrate the protection of AES-128 against FA and show a negligible advantage of FA.

SNOW 3G is a stream cipher used as one of the standard algorithms for data confidentiality and integrity protection over the air interface in the 3G and 4G mobile communication systems. SNOW-V is a recent new version that was proposed as a candidate for inclusion in the 5G standard. In this paper, we propose a faster variant of SNOW-V, called SNOW-Vi, that can reach the targeted speeds for 5G in a software implementation on a larger variety of CPU architectures. SNOW-Vi differs in the way how the LFSR is updated and also introduces a new location of the tap $T2$ for stronger security, while everything else is kept the same as in SNOW-V. The throughput in a software environment is increased by around 50\% in average, up to 92 Gbps. This makes the applicability of the cipher much wider and more use cases are covered. The security analyses previously done for SNOW-V are not affected in most aspects, and SNOW-Vi provides the same 256-bit security level as SNOW-V.

In this paper, we study dedicated quantum collision attacks on SHA-256 and SHA-512 for the first time. The attacks reach 38 and 39 steps, respectively, which significantly improve the classical attacks for 31 and 27 steps. Both attacks adopt the framework of the previous work that converts many semi-free-start collisions into a 2-block collision, and are faster than the generic attack in the cost metric of time-space tradeoff. We observe that the number of required semi-free-start collisions can be reduced in the quantum setting, which allows us to convert the previous classical 38 and 39 step semi-free-start collisions into a collision. The idea behind our attacks is simple and will also be applicable to other cryptographic hash functions.

Many new ciphers target a concise algebraic description for efficient evaluation in a proof system or a multi-party computation. This new target for optimization introduces algebraic vulnerabilities, particularly involving Gröbner basis analysis. Unfortunately, the literature on Gröbner bases tends to be either purely mathematical, or focused on small fields. In this paper, we survey the most important algorithms and present them in an intuitive way. The discussion of their complexities enables researchers to assess the security of concrete arithmetization-oriented ciphers. Aside from streamlining the security analysis, this paper helps newcomers enter the field.

Designing a block cipher or cryptographic permutation can be approached in many different ways. One such approach, popularized by AES, consists in grouping the bits along the S-box boundaries, e.g., in bytes, and in consistently processing them in these groups. This aligned approach leads to hierarchical structures like superboxes that make it possible to reason about the differential and linear propagation properties using combinatorial arguments. In contrast, an unaligned approach avoids any such grouping in the design of transformations. However, without hierarchical structure, sophisticated computer programs are required to investigate the differential and linear propagation properties of the primitive. In this paper, we formalize this notion of alignment and study four primitives that are exponents of different design strategies. We propose a way to analyze the interactions between the linear and the nonlinear layers w.r.t. the differential and linear propagation, and we use it to systematically compare the four primitives using non-trivial computer experiments. We show that alignment naturally leads to different forms of clustering, e.g., of active bits in boxes, of two-round trails in activity patterns, and of trails in differentials and linear approximations.

We give an algorithm for key recovery of the Legendre pseudorandom function that supersedes the best known algorithms so far. The expected number of operations is $O(\sqrt{p\log{\log{p}}})$ on a $\Theta(\log{p})$-bit word machine, under reasonable heuristic assumptions, and requires only $\sqrt[4]{p~{\log^2{p}}\log{\log{p}}}$ oracle queries. If the number of queries $M$ is smaller, the expected number of operations is $\frac{{p}\log{p}\log\log{p}}{M^2}$. We further show that the algorithm works in many different generalisations -- using a different character instead of the Legendre symbol, using the Jacobi symbol, or using a degree $r$ polynomial in the Legendre symbol numerator. In the latter case we show how to use Möbius transforms to lower the complexity to $O(p^{\operatorname{max}\{r-3,r/2\}}r^2\log{p})$ Legendre symbol computations, and $O(p^{\operatorname{max}\{r-4,r/2\}}r^2\log{p})$ in the case of a reducible polynomial. We also give an $O(\sqrt[3]{p})$ quantum algorithm that does not require a quantum oracle, and comments on the action of the Möbius group in the linear PRF case. On the practical side we give implementational details of our algorithm. We give the solutions of the $64, 74$ and $84$-bit prime challenges for key recovery with $M=2^{20}$ queries posed by Ethereum, out of which only the $64$ and $74$-bit were solved earlier.

At EUROCRYPT 2021, Bao et al. proposed an automatic method for systematically exploring the configuration space of meet-in-the-middle (MITM) preimage attacks. We further extend it into a constraint-based framework for finding exploitable MITM characteristics in the context of key-recovery and collision attacks by taking the subtle peculiarities of both scenarios into account. Moreover, to perform attacks based on MITM characteristics with nonlinear constrained neutral words, which have not been seen before, we present a procedure for deriving the solution spaces of neutral words without solving the corresponding nonlinear equations or increasing the overall time complexities of the attack. We apply our method to concrete symmetric-key primitives, including SKINNY, ForkSkinny, Romulus, Saturnin, Grostl, Whirlpool, and hashing modes with AES-256. As a result, we identify the first 23-round key-recovery attack on SKINNY-$n$-$3n$ and the first 24-round key-recovery attack on ForkSkinny-$n$-$3n$ in the single-key model. Moreover, improved (pseudo) preimage or collision attacks on round-reduced Whirlpool, Grostl, and hashing modes with AES-256 are obtained. In particular, employing the new representation of the AES key schedule due to Leurent and Pernot (EUROCRYPT 2021), we identify the first preimage attack on 10-round AES-256 hashing.

Abstract Modern cryptographic algorithms have an enormous key diversity, so if we want to test their strength for all the keys, it will take practically an infinite time. To avoid this, we use the sampling method, in which we examine a much smaller number of keys n and then we make estimation for the total key population N with a predetermined sampling error. For the generation of the n cipher outputs (samples) with the n corresponding keys, the critical questions are how many samples we will test and how large must be the size of each sample. The general rule is that, the sampling error is reduced as we increase the number of the samples. But since the tests must be executed in an acceptable time, we must compromise the above rule with some additional factors, such as the type of the cryptographic cipher, the kind and the size of the plain information and of course the available computer power. In this study we examine the interrelations of all the above factors, and we propose applicable solutions. Keywords: Cryptography, Data encryption, Communication security, Computer security, Data security, Information security.

Pilsung is an AES-based North Korean cipher, which uses key-dependent S-Boxes and permutation. The use of pseudo-random ShiftRows permutations gives rise to a potential for weak keys. In this work we show how to build distinguishers to such weak keys and how to effectively search for them. We conclude that no such class of weak keys exist.

Differential-linear attacks are a cryptanalysis family that has recently benefited from various technical improvements, mainly in the context of ARX constructions. In this paper we push further this refinement, proposing several new improvements. In particular, we develop a better understanding of the related correlations, improve upon the statistics by using the LLR, and finally use ideas from conditional differentials for finding many right pairs. We illustrate the usefulness of these ideas by presenting the first 7.5-round attack on Chaskey. Finally, we present a new competitive attack on 12 rounds of Serpent, and as such the first cryptanalytic progress on Serpent in 10 years.

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time $2^{40}$ GEA-1 evaluations and using 44.5 GiB of memory. The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design. In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time $2^{45.1}$ GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

Improved attacks on generic small-domain Feistel ciphers with alternating round tweaks are obtained using linear cryptanalysis. This results in practical distinguishing and message-recovery attacks on the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. The data-complexity of the proposed attacks on FF3-1 and FEA-1 is $O(N^{r/2 - 1.5})$, where $N^2$ is the domain size and $r$ is the number of rounds. For example, FF3-1 with $N = 10^3$ can be distinguished from an ideal tweakable block cipher with advantage $\ge 1/10$ using $2^{23}$ encryption queries. Recovering the left half of a message with similar advantage requires $2^{24}$ data. The analysis of FF3-1 serves as an interesting real-world application of (generalized) linear cryptanalysis over the group $\mathbb{Z}/N\mathbb{Z}$.

HMAC and NMAC are the most basic and important constructions to convert Merkle-Damgård hash functions into message authentication codes (MACs) or pseudorandom functions (PRFs). In the quantum setting, at CRYPTO 2017, Song and Yun showed that HMAC and NMAC are quantum pseudorandom functions (qPRFs) under the standard assumption that the underlying compression function is a qPRF. Their proof guarantees security up to $O(2^{n/5})$ or $O(2^{n/8})$ quantum queries when the output length of HMAC and NMAC is $n$ bits. However, there is a gap between the provable security bound and a simple distinguishing attack that uses $O(2^{n/3})$ quantum queries. This paper settles the problem of closing the gap. We show that the tight bound of the number of quantum queries to distinguish HMAC or NMAC from a random function is $\Theta(2^{n/3})$ in the quantum random oracle model, where compression functions are modeled as quantum random oracles. To give the tight quantum bound, based on an alternative formalization of Zhandry's compressed oracle technique, we introduce a new proof technique focusing on the symmetry of quantum query records.

Properties of the Grain-128AEAD key re-introduction, as part of the cipher initialization, are analyzed and discussed. We consider and analyze several possible alternatives for key re-introduction and identify weaknesses, or potential weaknesses, in them. Our results show that it seems favorable to separate the state initialization, the key re-introduction, and the $A/R$ register initialization into three separate phases. Based on this, we propose a new cipher initialization and update the cipher version to Grain-128AEADv2. It can be noted that previously reported and published analysis of the cipher remains valid also for this new version.

GIFT-COFB is a finalist of NIST Lightweight cryptography project that aims at standardizing authenticated encryption schemes for constrained devices. It is a block cipher-based scheme and comes with a provable security result. This paper studies the tightness of the provable security bounds of GIFT-COFB, which roughly tells that, if instantiated by a secure $n$-bit block cipher, we need $2^{n/2}$ encrypted blocks or $2^{n/2}/n$ decryption queries to break the scheme. This paper shows that the former condition is indeed tight, by presenting forgery attacks that work with $2^{n/2}$ encrypted blocks with single decryption query. This fills the missing spot of previous attacks presented by Khairallah, and confirms the tightness of the security bounds with respect to encryption. We remark that our attacks work independent of the underlying block cipher.

In this paper, we present preimage attacks on 4-round Keccak-224/256 as well as 4-round Keccak[$r = 640,c = 160,l = 80$] in the preimage challenges. We revisit the Crossbred algorithm for solving the Boolean multivariate quadratic (MQ) system, propose a new view for the case $D = 2$ and elaborate the computational complexity. The result shows that the Crossbred algorithm outperforms brute force theoretically and practically with feasible memory costs. In our attacks, we construct Boolean MQ systems in order to make full use of variables. With the help of solving MQ systems, we successfully improve preimage attacks on Keccak-224/256 reduced to 4 rounds. Moreover, we implement the preimage attack on 4-round Keccak[$r = 640,c = 160,l = 80$], an instance in the Keccak preimage challenges, and find 78-bit matched \textit{near preimages}. Due to the fundamental rule of solving MQ systems, the complexity elaboration of Crossbred algorithm is of independent interest.

We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a Feistel Network contains very specific patterns depending on the degree of the Feistel functions, the number of rounds and whether the Feistel functions are 1-to-1 or not. We exploit these patterns to distinguish Feistel Networks, even if the Feistel Network is whitened using unknown affine layers. We also present a new type of structural attack exploiting monomials that cannot be present at round $r-1$ to recover the ANF of the last Feistel function of a $r$-round Feistel Network. Finally, we discuss the relations between our findings, integral attacks, cube attacks, Todo's division property and the congruence modulo 4 of the Linear Approximation Table.

The existence of Almost Perfect Non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 bits in 2009. In this paper, we apply methods intended to reverse-engineer S-Boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over $GF(2^3)$. More precisely, we show that it is a particular case of a permutation structure we introduce, the butterfly. Such butterflies are $2n$-bit mappings with two CCZ-equivalent representations: one is a quadratic non-bijective function and one is a degree $n+1$ permutation. We show that these structures always have differential uniformity at most 4 when $n$ is odd. A particular case of this structure is actually a 3-round Feistel Network with similar differential and linear properties. These functions also share an excellent non-linearity for $n=3,5,7$. Furthermore, we deduce a bitsliced implementation and significantly reduce the hardware cost of a 6-bit APN permutation using this decomposition, thus simplifying the use of such a permutation as building block for a cryptographic primitive.

We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a long standing open problem in the area of ARX design. The wide trail design strategy (WTS), that is at the basis of many S-box based ciphers, including the AES, is not suitable for ARX designs due to the lack of S-boxes in the latter. In this paper we address the mentioned limitation by proposing the long trail design strategy (LTS) -- a dual of the WTS that is applicable (but not limited) to ARX constructions. In contrast to the WTS, that prescribes the use of small and efficient S-boxes at the expense of heavy linear layers with strong mixing properties, the LTS advocates the use of large (ARX-based) S-Boxes together with sparse linear layers. With the help of the so-called Long Trail argument, a designer can bound the maximum differential and linear probabilities for any number of rounds of a cipher built according to the LTS. To illustrate the effectiveness of the new strategy, we propose SPARX -- a family of ARX-based block ciphers designed according to the LTS. SPARX has 32-bit ARX-based S-boxes and has provable bounds against differential and linear cryptanalysis. In addition, SPARX is very efficient on a number of embedded platforms. Its optimized software implementation ranks in the top 6 of the most software-efficient ciphers along with SIMON, SPECK, Chaskey, LEA and RECTANGLE. As a second contribution we propose another strategy for designing ARX ciphers with provable properties, that is completely independent of the LTS. It is motivated by a challenge proposed earlier by Wall{é}n and uses the differential properties of modular addition to minimize the maximum differential probability across multiple rounds of a cipher. A new primitive, called LAX, is designed following those principles. LAX partly solves the Wall{é}n challenge.

In this paper, we present a new concept named the basic function. By the study of the basic function, we find the $O(n)$-time algorithm to calculate the probability or correlation for some property of Modulo $2^n$, including the difference-linear connective correlation coefficients, the linear approximation correlation coefficients, the differential probability, difference-boomerange connective probability, boomerange connective probability, boomerange-difference connective probability, etc.

Machine learning aided cryptanalysis is an interesting but challenging research topic. At CRYPTO'19, Gohr proposed a Neural Distinguisher (ND) based on a plaintext difference. The ND takes a ciphertext pair as input and outputs its class (a real or random ciphertext pair). At EUROCRYPTO'20, Benamira et al proposed a deeper analysis of how two specific NDs against Speck32/64 work. However, there are still three research gaps that researchers are eager to fill in. (1) what features related to a ciphertext pair are learned by the ND? (2) how to explain various phenomena related to NDs? (3) what else can machine learning do in conventional cryptanalysis? In this paper, we filled in the three research gaps: (1) we first propose the Extended Differential-Linear Connectivity Table (EDLCT) which is a generic tool describing a cipher. Features corresponding to the EDLCT are designed to describe a ciphertext pair. Based on these features, various machine learning-based distinguishers including the ND are built. To explore various NDs from the EDLCT view, we propose a Feature Set Sensitivity Test (FSST) to identify which features may have a significant influence on NDs. Features identified by FSST share the same characteristic related to the cipher's round function. Surrogate models of NDs are also built based on identified features. Experiments on Speck32/64 and DES confirm that features corresponding to the EDLCT are learned by NDs. (2) We explain phenomena related to NDs via EDLCT. (3) We show how to use machine learning to search differential-linear propagations ∆ → λ with a high correlation, which is a tough task in the differential-linear attack. Applications in Chaskey and DES demonstrate the advantages of machine learning. Furthermore, we provide some optional inputs to improve ND

Statistical Ineffective Fault Attacks (SIFA) have been recently proposed as very powerful key-recovery strategies on symmetric cryptographic primitives' implementations. Specically, they have been shown to bypass many common countermeasures against faults such as redundancy or infection, and to remain applicable even when side-channel countermeasures are deployed. In this work, we investigate combined side-channel and fault attacks and show that a profiled, SIFA-like attack can be applied despite not having any direct ciphertext knowledge. The proposed attack exploits the ciphertext's side-channel and fault characteristics to mount successful key recoveries, even in the presence of masking and duplication countermeasures, at the cost of both side-channel and fault profiling. We analyze the attack using simulations, discuss its requirements, strengths and limitations, and compare different approaches to distinguish the correct key. Finally, we demonstrate its applicability on an ARM Cortex-M4 device, utilizing a combination of laser-based fault injection and microprobe-based EM side-channel analysis.

Designing cryptographic permutations and block ciphers using a substitution-permutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios. For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, our goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, we derive conditions that allow us to either set up or prevent attacks based on infinitely long truncated differentials with probability 1. Our analysis is rather broad compared to earlier independent work on this problem since we consider (1) both invariant and non-invariant/iterative trails, and (2) trails with and without active S-boxes. For these cases, we provide rigorous sufficient and necessary conditions for the matrix that defines the linear layer to prevent the analyzed attacks. On the practical side, we present a tool that can determine whether a given linear layer is vulnerable based on these results. Furthermore, we propose a sufficient condition for the linear layer that, if satisfied, ensures that no infinitely long truncated differential exists. This condition is related to the degree and the irreducibility of the minimal polynomial of the matrix that defines the linear layer. Besides P-SPN schemes, our observations may also have a crucial impact on the Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.

Automatic modelling to search distinguishers with high probability covering as many rounds as possible, such as MILP, SAT/SMT, CP models, has become a very popular cryptanalysis topic today. In those models, the optimizing objective is usually the probability or the number of rounds of the distinguishers. If we want to recover the secret key for a round-reduced block cipher, there are usually two phases, i.e., finding an efficient distinguisher and performing key-recovery attack by extending several rounds before and after the distinguisher. The total attacked number of rounds is not only related to the chosen distinguisher, but also to the extended rounds before and after the distinguisher. In this paper, we try to combine the two phases in a uniform automatic model. Concretely, we apply this idea to automate the related-key rectangle attacks on SKINNY and ForkSkinny. We propose some new distinguishers with advantage to perform key-recovery attacks. Our key-recovery attacks on a few versions of round-reduced SKINNY and ForkSkinny cover 1 to 2 more rounds than the best previous attacks.

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure $n$-bit to $n$-bit PRF constructions, i.e., \textsf{SoEM22} and \textsf{SoKAC21}, which are built on public permutations, where $n$ is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based $n$-bit to $n$-bit beyond the birthday bound secure PRF, which they refer to as \textsf{PDMMAC}. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based $n$-bit to $n$-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose $\textsf{pEDM}$, a single permutation based $n$-bit to $n$-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to $2^{2n/3}$ construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

In this work we investigate how the choice of the key-expansion algorithm and its interaction with the round function affect the resistance of Simon-like ciphers against rotational-XOR (RX) cryptanalysis. We observe that among the key-expansion algorithms we consider, Simon is most resistant, while Simeck is much less so. Implications on lightweight ciphers design are discussed and open questions are proposed.

In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions. We exhibit three properties on the component functions such that satisfying one of them is sufficient to ensure that the algebraic immunity of their direct sum exceeds the maximum of their algebraic immunities. These properties can be checked while computing the algebraic immunity and they allow to determine better the security provided by functions central in different cryptographic constructions such as stream ciphers, pseudorandom generators, and weak pseudorandom functions. We provide examples for each property and determine the exact algebraic immunity of candidate constructions.

This paper considers the linear cryptanalyses of Authenticated Encryptions with Associated Data (AEADs) GIFT-COFB, SUNDAE-GIFT, and HyENA. All of these proposals take GIFT-128 as underlying primitives. The automatic search with the Boolean satisfiability problem (SAT) method is implemented to search for linear approximations that match the attack settings concerning these primitives. With the newly identified approximations, we launch key-recovery attacks on GIFT-COFB, SUNDAE-GIFT, and HyENA when the underlying primitives are replaced with 16-round, 17-round, and 16-round versions of GIFT-128. The resistance of GIFT-128 against linear cryptanalysis is also evaluated. We present a 24-round key-recovery attack on GIFT-128 with a newly obtained 19-round linear approximation. We note that the attack results in this paper are far from threatening the security of GIFT-COFB, SUNDAE-GIFT, HyENA, and GIFT-128.

AEGIS-128 and Tiaoxin-346 (Tiaoxin for short) are two AES-based primitives submitted to the CAESAR competition. Among them, AEGIS-128 has been selected in the final portfolio for high-performance applications, while Tiaoxin is a third-round candidate. Although both primitives adopt a stream cipher based design, they are quite different from the well-known bit-oriented stream ciphers like Trivium and the Grain family. Their common feature consists in the round update function, where the state is divided into several 128-bit words and each word has the option to pass through an AES round or not. During the 6-year CAESAR competition, it is surprising that for both primitives there is no third-party cryptanalysis of the initialization phase. Due to the similarities in both primitives, we are motivated to investigate whether there is a common way to evaluate the security of their initialization phases. Our technical contribution is to write the expressions of the internal states in terms of the nonce and the key by treating a 128-bit word as a unit and then carefully study how to simplify these expressions by adding proper conditions. As a result, we found that there are several groups of weak keys with $2^{96}$ keys each in 5-round AEGIS-128 and 8-round Tiaoxin, which allows us to construct integral distinguishers with time complexity $2^{32}$ and data complexity $2^{32}$. Based on the distinguisher, the time complexity to recover the weak key is $2^{72}$ for 5-round AEGIS-128. However, the weak key recovery attack on 8-round Tiaoxin will require the usage of a weak constant occurring with probability $2^{-32}$. All the attacks reach half of the total number of initialization rounds. We expect that this work can advance the understanding of the designs similar to AEGIS and Tiaoxin.

We show the applicability of Simon's period finding quantum algorithm to the cryptanalysis of several tweakable enciphering schemes (TESs), namely, CMC, EME, XCB, TET and FAST. For all of the five TESs, we show distinguishing attacks, while for XCB, TET and FAST, the attacks reveal portions of the secret keys.

Graphics processing units (GPUs) are specially designed for parallel applications and perform parallel operations much faster than central processing units (CPUs). In this work, we focus on the performance of the Advanced Encryption Standard (AES) on GPUs. We present optimizations which remove bank conflicts in shared memory accesses and provide 878.6 Gbps throughput for AES-128 encryption on an RTX 2070 Super, which is equivalent to 4.1 Gbps per Watt. Our optimizations provide more than 2.56x speed-up against the best GPU results in the literature. Our optimized AES implementations on GPUs even outperform any CPU using the hardware level AES New Instructions (AES-NI) and legacy FPGA-based cluster architectures like COPACOBANA and RIVYERA. Even on a low-end GPU like MX 250, we obtained 60.0 Gbps throughput for AES-256 which is generally faster than the read/write speeds of solid disks. Thus, transition from AES-128 to AES-256 when using GPUs would provide military grade security with no visible performance loss. With these breakthrough performances, GPUs can be used as a cryptographic co-processor for file or full disk encryption to remove performance loss coming from CPU encryption. With a single GPU as a co-processor, busy SSL servers can be free from the burden of encryption and use their whole CPU power for other operations. Moreover, these optimizations can help GPUs to practically verify theoretically obtained cryptanalysis results or their reduced versions in reasonable time.

In this article, we analyze and investigate two authenticated encryption algorithms: GIFT-COFB and HyENA. The two modes differ in some low levels details in both the design and security proofs. However, they share a lot of similarities. We take a look at the best-known attacks and security proofs of these designs. We show that the best-known attack is not a matching attack to the security bounds provided by the designers in the security proof. Second, we give a new attack that we characterize as an {\it "almost matching"} attack. It is significantly closer to the provable security bounds. The new attack requires $O(2^{n/4})$ encryptions and $O(2^{n/2})$ decryptions, as opposed to $O(2^{n/2})$ encryptions and $O(2^{n/2})$ decryptions shown previously. However, there is still a substantial logarithmic gap between this attack and the corresponding security bound. Next, we analyze why this gap still exists and why it is unlikely to find matching attacks. We give two arguments. The first argument is by analyzing the security proof and showing how it masks a term with non-negligible encryption complexity. The second argument looks at the attacker's point of view. A successful attack requires satisfying a non-trivial linear equation over secret random variables. Satisfying such an equation requires more decryption queries than what is bounded by the security proof. It is worth emphasizing that the analysis and attacks presented in this paper {\it do not} threaten the security claims made by the designers or the security of these designs within the parameters required by the NIST lightweight cryptography project. The results increase confidence in the security claims of GIFT-COFB and HyENA while showing their limitations by relying mostly on bounding the number of unsuccessful forgeries.