With the advancement of Cloud computing, people now store their data on remote Cloud servers for larger computation and storage resources. However, users’ data may contain sensitive information of users and should not be disclosed to the Cloud servers. If users encrypt their data and store the encrypted data in the servers, the search capability supported by the servers will be significantly reduced because the server has no access to the data content. In this paper, we propose a Fine-grained Multi-keyword Ranked Search (FMRS) scheme over encrypted Cloud data. Specifically, we leverage novel techniques to realize multikeyword ranked search, which supports both mixed “AND”, “OR” and “NO” operations of keywords and ranking according to the preference factor and relevance score. Through security analysis, we can prove that the data confidentiality, privacy protection of index and trapdoor, and the unlinkability of trapdoor can be achieved in our FMRS. Besides, Extensive experiments show that the FMRS possesses better performance than existing schemes in terms of functionality and efficiency.

Recently one new key recovery method for a filter generator was proposed. It is based on so-called planar approximations of such a generator. This paper contains the numerical part of the research of the Boolean functions properties which allow to protect the generator against this method. The main theoretical part of this research is presented at the CTCrypt 2019 conference.

Glitches entail a great issue when securing a cryptographic implementation in hardware. Several masking schemes have been proposed in the literature that provide security even in the presence of glitches. The key property that allows this protection was introduced in threshold implementations as non-completeness. We address crucial points to ensure the right compliance of this property especially for low-latency implementations. Specifically, we first discuss the existence of a flaw in DSD 2017 implementation of Keccak by Gross et al. in violation of the non-completeness property and propose a solution. We perform a side-channel evaluation on the first-order and second-order implementations of the proposed design where no leakage is detected with up to 55 million traces. Then, we present a method to ensure a non-complete scheme of an unrolled implementation applicable to any order of security or algebraic degree of the shared function. By using this method we design a two-rounds unrolled first-order Keccak-f [200] implementation that completes an encryption in 20.61ns, the fastest implementation in the literature to this date.

Withthiswork, weintendondemonstratingtheneedfor improvements to the currently standardized AES family of cryptosystems, and provide a solution that meets the requirements of long-term security in the rapidly evolving threat landscape. The solution proposed is flexible, dramatically increases the potential security of the cipher, and strongly mitigates many of the most serious attacks on the AES family of cryptosystems. Further, our solution can be easily integrated into existing AES cryptosystem deployments, with only a few small changes required, thus preserving the large investments in this cipher both in hardware and software.

A chosen-prefix collision attack is a stronger variant of a collision attack, where an arbitrary pair of challenge prefixes are turned into a collision. Chosen-prefix collisions are usually significantly harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is much larger. While many cryptographic constructions rely on collision-resistance for their security proofs, collision attacks are hard to turn into a break of concrete protocols, because the adversary has limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to break certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IPsec). In this article, we propose new techniques to turn collision attacks into chosen-prefix collision attacks. Our strategy is composed of two phases: first, a birthday search that aims at taking the random chaining variable difference (due to the chosen-prefix model) to a set of pre-defined target differences. Then, using a multi-block approach, carefully analysing the clustering effect, we map this new chaining variable difference to a colliding pair of states using techniques developed for collision attacks. We apply those techniques to MD5 and SHA1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA1 with complexity between $2^{66.9}$ and $2^{69.4}$ (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity $2^{77.1}$. This is within a small factor of the complexity of the classical collision attack on SHA1 (estimated as $2^{64.7}$). This represents yet another warning that industries and users have to move away from using SHA1 as soon as possible.

I am making this work from August 1998 available for historical reasons. It has been cited as an ``unpublished manuscript'' more than two dozen times over the years -- even though it has not been publicly available anywhere for almost 20 years. The short memo describes a simple non-intrusive reverse engineering technique against Russian GOST chips. The technique is based on a slide attack. This may be historically interesting since slide attacks had not been ``invented yet'', at least in formal sense. The brief original abstract: We show that a simple ``black box'' chosen-key attack against GOST can recover secret S-boxes with approximately $2^{32}$ encryptions.

Enigma 2000 (E2K) is a cipher that updates the World War II-era Enigma Machine for the twenty-first century. Like the original Enigma, E2K is intended to be computed by an offline device; this prevents side channel attacks and eavesdropping by malware. Unlike the original Enigma, E2K uses modern cryptographic algorithms; this provides secure encryption. E2K is intended for encrypted communication between humans only, and therefore it encrypts and decrypts plaintexts and ciphertexts consisting only of the English letters A through Z plus a few other characters. E2K uses a nonce in addition to the secret key, and requires that different messages use unique nonces. E2K performs authenticated encryption, and optional header data can be included in the authentication. This paper defines the E2K encryption and decryption algorithms, analyzes E2K’s security, and describes an encryption appliance based on the Raspberry Pi computer for doing E2K encryptions and decryptions offline.

Using modular addition as a source of nonlinearity is frequently used in many symmetric-key structures such as ARX and Lai--Massey schemes. At FSE'16, Fu \etal proposed a Mixed Integer Linear Programming (MILP)-based method to handle the propagation of differential trails through modular additions assuming that the two inputs to the modular addition and the consecutive rounds are independent. However, this assumption does not necessarily hold. In this paper, we study the propagation of the XOR difference through the modular addition at the bit level and show the effect of the carry bit. Then, we propose a more accurate MILP model to describe the differential propagation through the modular addition taking into account the dependency between the consecutive modular additions. The proposed MILP model is utilized to launch a differential attack against Bel-T-256, which is a member of the Bel-T block cipher family that has been adopted recently as a national standard of the Republic of Belarus. In particular, we employ the concept of partial Differential Distribution Table to model the 8-bit S-Box of Bel-T using a MILP approach in order to automate finding a differential characteristic of the cipher. Then, we present a $4\frac{1}{7}$-round (out of 8) differential attack which utilizes a $3$-round differential characteristic that holds with probability $2^{-111}$. The data, time and memory complexities of the attack are $2^{114}$ chosen plaintexts, $ 2^{237.14} $ $4\frac{1}{7}$-round encryptions, and $2^{224}$ 128-bit blocks, respectively.

mixFeed [CN19] is a round 1 candidate for the NIST Lightweight Cryptography Standardization Project. It is a single-pass, nonce-based, AES-based authenticated encryption algorithms. The authors claim that while there are no guarantees for security in terms of confidentiality in case of nonce-misuse (repetition), the integrity security still holds up to 2^32 data complexity. In this report, this claim is not true in case the plaintext length is non-zero (≥ 16 bytes to be exact). We show a forgery attack that requires only two encryption queries with the same nonce and 34 bytes of data.

Conditional cube attack was proposed by Huang et al. at EUROCRYPT 2017 to attack Keccak keyed mode. Inspired by dynamic cube attack, they reduce the degree by appending key bit conditions on the initial value (IV). Recently, Li et al. proposed new conditional cube attacks on Keccak keyed mode with extremely small degrees of freedom. In this paper, we find a new property on Li et al.'s method, and modify the new conditional cube attack for lightweight encryption algorithms using a 8-2-2 pattern, and apply it on 5-round Ketje Jr, 6-round Xoodoo-AE and Xoodyak, where Ketje Jr is among the 3rd round CAESAR competition candidates and Xoodyak is a Round 1 submission of the ongoing NIST lightweight cryptography project. Then we give the updated conditional cube attack analysis. All our results are of practical time complexity with negligible memory cost and our test codes are given in this paper. Notably, it is the first third-party cryptanalysis result for Xoodyak.

This paper presents CONCRETE (Commit-Encrypt-Send-the-Key) a new Authenticated Encryption mode that offers CIML2 security, that is, ciphertext integrity in the presence of nonce misuse and side-channel leakages in both encryption and decryption. CONCRETE improves on a recent line of works aiming at leveled implementations, which mix a strongly protected and energy demanding implementation of a single component, and other weakly protected and much cheaper components. Here, these components all implement a tweakable block cipher TBC. CONCRETE requires the use of the strongly protected TBC only once while supporting the leakage of the full state of the weakly protected components -- it achieves CIML2 security in the so-called unbounded leakage model. All previous works need to use the strongly protected implementation at least twice. As a result, for short messages whose encryption and decryption energy costs are dominated by the strongly protected component, we halve the cost of a leakage-resilient implementation. CONCRETE additionally provides security when unverified plaintexts are released, and confidentiality in the presence of simulatable leakages in encryption and decryption.

SFN is a lightweight block cipher designed to be compact in hardware environment and also efficient in software platforms. Compared to the conventional block ciphers that are either Feistel or Substitution-Permutation (SP) network based, SFN has a different encryption method which uses both SP network structure and Feistel network structure to encrypt. SFN supports key lengths of 96 bits and its block length is 64 bits. In this paper, we propose an attack on full SFN by using the related key distinguisher. With this attack, we are able to recover the keys with a time complexity of $2^{60.58}$ encryptions. The data and memory complexity of the attacks are negligible. In addition, in the single key mode, we present a meet in the middle attack against the full rounds block cipher for which the time complexity is $2^{80}$ SFN calculations and the memory complexity is $2^{87}$ bytes. The date complexity of this attack is only a single known plaintext and its corresponding ciphertext.

SKINNY is a family of lightweight tweakable block ciphers designed to have the smallest hardware footprint. In this paper, we present zero-correlation linear approximations and related-tweake impossible differential characteristics for different versions of SKINNY. We utilize meet-in-the-middle approach to construct 9-round and 10-round zero-correlation linear distinguisher. We also obtain 12-round related-tweakey impossible differential characteristics for both SKINNY-64 and 128 in TK1 model and TK2 model. To the best of our knowledge, the presented zero-correlation characteristics in this paper is the first investigation of the security of SKINNY against this attack.

Message authentication code, MAC for short, is a symmetric-key cryptographic function for authenticity. A standard MAC verification only tells whether the message is valid or invalid, and thus we can not identify which part is corrupted in case of invalid message. In this paper we study a class of MAC functions that enables to identify the part of corruption, which we call group testing MAC (GTM). This can be seen as an application of a classical (non-adaptive) combinatorial group testing to MAC. Although the basic concept of GTM (or its keyless variant) has been proposed in various application areas, such as data forensics and computer virus testing, they rather treat the underlying MAC function as a black box, and exact computation cost for GTM seems to be overlooked. In this paper, we study the computational aspect of GTM, and show that a simple yet non-trivial extension of parallelizable MAC (PMAC) enables $O(m+t)$ computation for $m$ data items and $t$ tests, irrespective of the underlying test matrix we use, under a natural security model. This greatly improves efficiency from naively applying a black-box MAC for each test, which requires $O(mt)$ time. Based on existing group testing methods, we also present experimental results of our proposal and observe that ours runs as fast as taking single MAC tag, with speed-up from the conventional method by factor around 8 to 15 for $m=10^4$ to $10^5$ items.

This document includes a collision/forgery attack against SNEIKEN128/192/256, where every message with more than 128 bytes of associated data can be converted into another message with different associated data and the same ciphertext/tag. The attack is a direct application of the probability 1 differential of the SNEIK permutation found by Léo Perrin in [Per19]. We verify the attack using the reference implementation of SNEIKEN128 provided by the designers, providing an example of such collisions.

Forkciphers are a new kind of primitive proposed recently by Andreeva et al. for efficient encryption and authentication of small messages. They fork the middle state of a cipher and encrypt it twice under two smaller independent permutations. Thus, forkciphers produce two output blocks in one primitive call. Andreeva et al. proposed ForkAES, a tweakable AES-based forkcipher that splits the state after five out of ten rounds. While their authenticated encrypted schemes were accompanied by proofs, the security discussion for ForkAES was not provided, and founded on existing results on the AES and KIASU-BC. Forkciphers provide a unique interface called reconstruction queries that use one ciphertext block as input and compute the respective other ciphertext block. Thus, they deserve a careful security analysis. This work fosters the understanding of the security of ForkAES with three contributions: (1) We observe that security in reconstruction queries differs strongly from the existing results on the AES. This allows to attack nine out of ten rounds with differential, impossible-differential and yoyo attacks. (2) We observe that some forkcipher modes may lack the interface of reconstruction queries, so that attackers must use encryption queries. We show that nine rounds can still be attacked with rectangle and impossible-differential attacks. (3) We present forgery attacks on the AE modes proposed by Andreeva et al. with nine-round ForkAES.

Recently, the NIST launched a competition for lightweight cryptography and a large number of ciphers are expected to be studied and analyzed under this competition. Apart from the classical security, the candidates are desired to be analyzed against physical attacks. Differential Fault Analysis (DFA) is an invasive physical attack method for recovering key information from cipher implementations. Up to date, almost all the block ciphers have been shown to be vulnerable against DFA, while following similar attack patterns. However, so far researchers mostly focused on particular ciphers rather than cipher families, resulting in works that reuse the same idea for different ciphers. In this article, we aim at bridging this gap, by providing a generic DFA attack method targeting Substitution-Permutation Network (SPN) based families of symmetric block ciphers. We provide an overview of the state-of-the-art of the fault attacks on SPNs, followed by generalized conditions that hold on all the ciphers of this design family. We show that for any SPN, as long as the fault mask injected before a non-linear layer in the last round follows a non-uniform distribution, the key search space can always be reduced. This shows that it is not possible to design an SPN-based cipher that is completely secure against DFA, without randomization. Furthermore, we propose a novel approach to find good fault masks that can leak the key with a small number of instances. We then developed a tool, called Joint Difference Distribution Table (JDDT) for pre-computing the solutions for the fault equations, which allows us to recover the last round key with a very small number of pairs of faulty and non-faulty ciphertexts. We evaluate our methodology on various block ciphers, including PRESENT-80, PRESENT-128, GIFT-64, GIFT-128, AES-128, LED-64, LED-128, Skinny-64-64, Skinny-128-128, PRIDE and PRINCE. The developed technique would allow automated DFA analysis of several candidates in the NIST competition.

SNEIK is a permutation at the core of a submission to the NIST lightweight cryptography project. In this note, we exhibit an iterated probability 1 differential in this permutation. However, it is still unclear if this differential can be used to construct attacks against the permutation in a mode, e.g., against the hash function SNEIKHA. We also suggest a simple fix: adding a 32-bit rotation in one tap prevents this issue.

Considering AES sub-steps that can be attacked with a small guess space, the most practicable is to target SubBytes of extremal rounds. For its contrast between candidates (non-linearity) and that the search space is reduced to 28 -sized blocks. But when such point of interests are not available, MixColumns may be considered but involve search spaces of 2^32 -sized blocks. This number of attacks to run being often considered as unrealistic to reach, published papers propose to attack using chosen inputs in order to reduce back search space to 2^8 -sized blocks. Several sets of chosen inputs acquisition will then be required to succeed an attack. Our contribution consists in an optimization of usage of gained information that allows to drastically reduce the number of set needed to realize such an attack, even to only one set in some configurations.

Concerning the side-channel attacks on Advanced Encryp- tion Standard, it seems that majority of studies focus on the lowest size: AES-128. Even when adaptable to higher sizes (AES-192 and AES-256), lots of state-of-the-art attacks see their complexity substantially raised. Indeed, it often requires to perform two consecutive dependent attacks. The first is similar to the one applied on AES-128, but a part of the key remains unknown and must be retrieved through a second attack directly dependent on the success of the first. This configuration may substantially raise the complexity for the at- tacker, especially if new signal acquisitions with specific input, built using the first key part recovered, must be performed. Any error/uncertainty in the first attack raise the key recovery complexity. Our contribution is to show that this complexity can be lowered to two independent attacks by the mean of attacking separately first and last round keys. We show that the information is enough to recover the main key (or a very small list of candidates) in a negligible exploratory effort.

White-box cryptography was originally introduced in the setting of digital rights management with the goal of preventing a user from illegally re-distributing their software decryption program. In recent years, mobile payment has become a popular new application for white-box cryptography. Here, white-box cryptography is used to increase the robustness against external adversaries (i.e., not the user) who aim to misuse/attack the cryptographic functionalities of the payment application. A necessary requirement for secure white-box cryptography is that an adversary cannot extract the embedded secret key from the implementation. However, a white-box implementation needs to fulfill further security properties in order to provide useful protection of an application. In this paper we focus on the popular property incompressibility that is a mitigation technique against code-lifting attacks. We provide an incompressible white-box encryption scheme based on the standard-assumption of one-way permutations whereas previous works used either public-key type assumptions or non-standard symmetric-type assumptions.

A generalized Feistel cipher is one of the methods to construct block ciphers, and it has several variants. Dong, Li, and Wang showed quantum distinguishing attacks against the $(2d-1)$-round Type-1 generalized Feistel cipher with quantum chosen-plaintext attacks, where $d\ge 3$, and they also showed key recovery attacks [Dong, Li, Wang. Sci China Inf Sci, 2019, 62(2): 022501]. In this paper, we show a polynomial time quantum distinguishing attack against the $(3d-3)$-round version, i.e., we improve the number of rounds by $(d-2)$. We also show a quantum distinguishing attack against the $(d^2-d+1)$-round version in the quantum chosen-ciphertext setting. We apply these quantum distinguishing attacks to obtain key recovery attacks against Type-1 generalized Feistel ciphers.

Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty. In this paper, we give more improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give new quantum polynomial-time distinguishers on $(3d-3)$-round Type-1 GFS with branches $d\geq3$, which gain $d-2$ more rounds than the previous distinguishers. Hence, we could get better key-recovery attacks, whose time complexities gain a factor of $2^{\frac{(d-2)n}{2}}$. In qCCA setting, we get $(3d-3)$-round quantum distinguishers on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers. In addition, we give some quantum attacks on CAST-256 block cipher. We find 12-round and 13-round polynomial-time quantum distinguishers in qCPA and qCCA settings, respectively, while the best previous one is only 7 rounds. Hence, we could derive quantum key-recovery attack on 19-round CAST-256. While the best previous quantum key-recovery attack is on 16 rounds. When comparing our quantum attacks with classical attacks, our result also reaches 16 rounds on CAST-256 with 128-bit key under a competitive complexity.

T-310 is an important Cold War cipher. It was the principal encryption algorithm used to protect various state communication lines in Eastern Germany throughout the 1980s. The cipher seems to be quite robust, and until now, no cryptography researcher has proposed an attack on T-310. In this paper we provide a detailed analysis of T-310 in the context of modern cryptography research and other important or similar ciphers developed in the same period. We introduce new notations which show the peculiar internal structure of this cipher in a new light. We point out a number of significant strong and weak properties of this cipher. Finally we propose several new attacks on T-310.

Inoue and Minematsu [Cryptology ePrint Archive: Report 2018/1040] presented efficient forgery attacks against OCB2, and Poettering [Cryptology ePrint Archive: Report 2018/1087] presented a distinguishing attack. In this short note, based on these results, we show a plaintext recovery attack against OCB2 in the chosen plaintext and ciphertext setting. We also show that the decryption oracle of the underlying block cipher can be simulated. This complements the simulation of the encryption oracle of the block cipher by Poettering in [Cryptology ePrint Archive: Report 2018/1087].

OCB2 is a widely standardized mode of operation of a blockcipher that aims at providing authenticated encryption. A recent report by Inoue and Minematsu (IACR EPRINT report 2018/1040) indicates that OCB2 does not meet this goal. Concretely, by describing simple forging attacks the authors evidence that the (sub)goal of authenticity is not reached. The report does not question the confidentiality offered by OCB2. In this note we show how the attacks of Inoue and Minematsu can be extended to also break the confidentiality of OCB2. We do this by constructing both IND-CCA and plaintext recovering adversaries, all of which require minimal resources and achieve overwhelming success rates.

Modern block ciphers are facing the threat of side-channel attacks by power leakage whose main target are the non-linear components known as S-boxes. A theoretical measure for the resistance of an S-box against this type of attacks is the confusion coefficient variance property. A higher value of this property represents a better theoretical resistance. In this work we use the leaders and followers meta-heuristic in order to achieve good confusion coefficient variance’s valued S-boxes.

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

Cube attack is an important cryptanalytic technique against symmetric cryptosystems, especially for stream ciphers. The key step in cube attack is recovering superpoly. However, when cube size is large, the large time complexity of recovering the exact algebraic normal form (ANF) of superpoly confines cube attack. At CRYPTO 2017, Todo et al. applied conventional bit-based division property (CBDP) into cube attack which could exploit large cube sizes. However, CBDP based cube attacks cannot ensure that the superpoly of a cube is non-constant. Hence the key recovery attack may be just a distinguisher. Moreover, CBDP based cube attacks can only recover partial ANF coefficients of superpoly. The time complexity of recovering the reminding ANF coefficients is very large, because it has to query the encryption oracle and sum over the cube set. To overcome these limits, in this paper, we propose a practical method to recover the ANF coefficients of superpoly. This new method is developed based on bit-based division property using three subsets (BDPT) proposed by Todo at FSE 2016. We apply this new method to reduced-round Trivium. To be specific, the time complexity of recovering the superpoly of 832-round Trivium at CRYPTO 2017 is reduced from $2^{77}$ to practical, and the time complexity of recovering the superpoly of 839-round Trivium at CRYPTO 2018 is reduced from $2^{79}$ to practical. Then, we propose a theoretical attack which can recover the superpoly of Trivium up to 842 round. As far as we know, this is the first time that the superpoly can be recovered for Trivium up to 842 rounds.

Concrete security proofs give upper bounds on the attacker's advantage as a function of its time/query complexity. Cryptanalysis suggests however that other resource limitations - most notably, the attacker's memory - could make the achievable advantage smaller, and thus these proven bounds too pessimistic. Yet, handling memory limitations has eluded existing security proofs. This paper initiates the study of time-memory trade-offs for basic symmetric cryptography. We show that schemes like counter-mode encryption, which are affected by the Birthday Bound, become more secure (in terms of time complexity) as the attacker's memory is reduced. One key step of this work is a generalization of the Switching Lemma: For adversaries with $S$ bits of memory issuing $q$ distinct queries, we prove an $n$-to-$n$ bit random function indistinguishable from a permutation as long as $S \times q \ll 2^n$. This result assumes a combinatorial conjecture, which we discuss, and implies right away trade-offs for deterministic, stateful versions of CTR and OFB encryption. We also show an unconditional time-memory trade-off for the security of randomized CTR based on a secure PRF. Via the aforementioned conjecture, we extend the result to assuming a PRP instead, assuming only one-block messages are encrypted. Our results solely rely on standard PRF/PRP security of an underlying block cipher. We frame the core of our proofs within a general framework of indistinguishability for streaming algorithms which may be of independent interest.

Let $\sigma$ be some positive integer and $\mathcal{C} \subseteq \{(i,j): 1 \leq i < j \leq \sigma \}$. The theory behind finding a lower bound on the number of distinct blocks $P_1, \ldots, P_{\sigma} \in \{0,1\}^n$ satisfying a set of linear equations $\{ P_i \oplus P_j = c_{i,j} : (i,j) \in \mathcal{C} \}$ for some $c_{i,j} \in \{0,1\}^n$, is called {\em mirror theory}. Patarin introduced the mirror theory and provided a proof for this. However, the proof, even for a special class of equations, is complex and contains several non-trivial gaps. As an application of mirror theory, $XORP[w]$ (known as XOR construction) which returns $(w-1)$-block output, is a {\em pseudorandom function} (PRF) for some parameter $w$, called {\em width}. The XOR construction can be seen as a basic structure of some encryption algorithms, e.g., the CENC encryption and the CHM authenticated encryption, proposed by Iwata in 2006. Due to potential application of $XORP[w]$ and the nontrivial gaps in the proof of mirror theory, an alternative simpler analysis of the PRF-security of $XORP[w]$ would be much desired. Recently (in Crypto 2017), Dai {\em et al.} have introduced a tool, called the $\chi^2$ method, for analyzing PRF-security. Using this tool, the authors have provided a proof of the PRF-security of $XORP[2]$ without relying on the mirror theory. In this paper, we resolve the general case; we apply the $\chi^2$ method to obtain {\em a simpler security proof of $XORP[w]$ for any $w \geq 2$}. For $w =2$, we obtain {\em a tighter bound for a wider range of parameters} than that of Dai {\em et al.}. Moreover, we consider variable width construction $XORP[*]$ (in which the widths are chosen by the adversary adaptively), and also provide {\em variable output length pseudorandom function} (VOLPRF) security analysis for it. As an application of VOLPRF, we propose {\em an authenticated encryption which is a simple variant of CHM or AES-GCM and provides much higher security} than those at the cost of one extra blockcipher call for every message.

LowMC is a block cipher family designed in 2015 by Albrecht et al. It is optimized for practical instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. LowMC is used in the Picnic signature scheme, submitted to NIST's post-quantum standardization project and is a substantial building block in other novel post-quantum cryptosystems. Many LowMC instances use a relatively recent design strategy (initiated by Gérard et al. at CHES 2013) of applying the non-linear layer to only a part of the state in each round, where the shortage of non-linear operations is partially compensated by heavy linear algebra. Since the high linear algebra complexity has been a bottleneck in several applications, one of the open questions raised by the designers was to reduce it, without introducing additional non-linear operations (or compromising security). In this paper, we consider LowMC instances with block size $n$, partial non-linear layers of size $s \leq n$ and $r$ encryption rounds. We redesign LowMC's linear components in a way that preserves its specification, yet improves LowMC's performance in essentially every aspect. Most of our optimizations are applicable to all SP-networks with partial non-linear layers and shed new light on this relatively new design methodology. Our main result shows that when $s < n$, each LowMC instance belongs to a large class of equivalent instances that differ in their linear layers. We then select a representative instance from this class for which encryption (and decryption) can be implemented much more efficiently than for an arbitrary instance. This yields a new encryption algorithm that is equivalent to the standard one, but reduces the evaluation time and storage of the linear layers from $r \cdot n^2$ bits to about $r \cdot n^2 - (r-1)(n-s)^2$. Additionally, we reduce the size of LowMC's round keys and constants and optimize its key schedule and instance generation algorithms. All of these optimizations give substantial improvements for small $s$ and a reasonable choice of $r$. Finally, we formalize the notion of linear equivalence of block ciphers and prove the optimality of some of our results. Comprehensive benchmarking of our optimizations in various LowMC applications (such as Picnic) reveals improvements by factors that typically range between $2$x and $40$x in runtime and memory consumption.

The boomerang attack is a variant of differential cryptanalysis which regards a block cipher $E$ as the composition of two sub-ciphers, i.e., $E=E_1\circ E_0$, and which constructs distinguishers for $E$ with probability $p^2q^2$ by combining differential trails for $E_0$ and $E_1$ with probability $p$ and $q$ respectively. However, the validity of this attack relies on the dependency between the two differential trails. Murphy has shown cases where probabilities calculated by $p^2q^2$ turn out to be zero, while techniques such as boomerang switches proposed by Biryukov and Khovratovich give rise to probabilities greater than $p^2q^2$. To formalize such dependency to obtain a more accurate estimation of the probability of the distinguisher, Dunkelman et al. proposed the sandwich framework that regards $E$ as $\tilde{E_1}\circ E_m \circ \tilde{E_0}$, where the dependency between the two differential trails is handled by a careful analysis of the probability of the middle part $E_m$. Recently, Cid et al. proposed the Boomerang Connectivity Table (BCT) which unifies the previous switch techniques and incompatibility together and evaluates the probability of $E_m$ theoretically when $E_m$ is composed of a single S-box layer. In this paper, we revisit the BCT and propose a generalized framework which is able to identify the actual boundaries of $E_m$ which contains dependency of the two differential trails and systematically evaluate the probability of $E_m$ with any number of rounds. To demonstrate the power of this new framework, we apply it to two block ciphers SKNNY and AES. In the application to SKNNY, the probabilities of four boomerang distinguishers are re-evaluated. It turns out that $E_m$ involves 5 or 6 rounds and the probabilities of the full distinguishers are much higher than previously evaluated. In the application to AES, the new framework is used to exclude incompatibility and find high probability distinguishers of AES-128 under the related-subkey setting. As a result, a 6-round distinguisher with probability $2^{-109.42}$ is constructed. Lastly, we discuss the relation between the dependency of two differential trails in boomerang distinguishers and the properties of components of the cipher.

The KECCAK hash function is the winner of the SHA-3 competition (2008 -- 2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some KECCAK variants. Following the framework developed by Dinur et al. at FSE~2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3, namely 5-round SHAKE128, SHA3-224, and SHA3-256, and three instances of KECCAK contest, namely KECCAK[$1440,160,5,160$], KECCAK[$640,160,5,160$] and KECCAK[$1440,160,6,160$], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family.

We propose TEDT, a new Authenticated Encryption with Associated Data (AEAD) mode leveraging Tweakable Block Ciphers (TBCs). TEDT provides the following features: (i) It offers asymptotically optimal security in the multi-user setting. (ii) It offers nonce misuse-resilience, that is, the repetition of nonces does not impact the security of ciphertexts produced with fresh nonces. (iii) It offers KDM security in the multi-user setting, that is, its security is maintained even if key-dependent messages are encrypted. (iv) It offers full leakage-resilience, that is, it limits the exploitability of physical leakages via side-channel attacks, even if these leakages happen during every message encryption and decryption operation. (v) It can be implemented with a remarkably low energy cost when strong resistance to side-channel attacks is needed, supports online encryption and handles static & incremental associated data efficiently. Concretely, TEDT encourages leveled implementations, in which two TBCs are implemented: one needs strong and energy demanding protections against side-channel attacks but is used in a limited way, while the other only requires weak and energy efficient protections and performs the bulk of the computation. As a result, TEDT leads to considerably more energy efficient implementations compared to traditional AEAD schemes, whose side-channel security requires to uniformly protect every (T)BC execution.

Encrypt-then-MAC (EtM) is a popular mode for authenticated encryption (AE). Unfortunately, almost all designs following the EtM paradigm, including the AE suites for TLS, are vulnerable against nonce misuse. A single repetition of the nonce value reveals the hash key, leading to a universal forgery attack. There are only two authenticated encryption schemes following the EtM paradigm which can resist nonce misuse attacks, the GCM-RUP (CRYPTO-17) and the GCM/2+ (INSCRYPT-12). However, they are secure only up to the birthday bound in the nonce respecting setting, resulting in a restriction on the data limit for a single key. In this paper we show that nEHtM, a nonce-based variant of EHtM (FSE-10) constructed using a block cipher, has a beyond birthday bound (BBB) unforgeable security that gracefully degrades under nonce misuse. We combine nEHtM with the CENC (FSE-06) mode of encryption using the EtM paradigm to realize a nonce-based AE, CWC+. CWC+ is very close (requiring only a few more xor operations) to the CWC AE scheme (FSE-04) and it not only provides BBB security but also gracefully degrading security on nonce misuse.

In this paper we analyze the new AEAD mode called the Multilinear Galois Mode (MGM) originally proposed in CTCrypt 2017. This mode is currently considered in the Russian Standardization system as the main contender to be adopted as a standard AEAD mode. The analysis of the MGM mode was carried out in the paradigm of provable security, in other words, lower security bounds were obtained for the Privacy and Authenticity notions. These bounds show that the privacy and authenticity of this mode is provably guaranteed (under security of the used block cipher) up to the birthday paradox bound.

MDS matrices are important building blocks providing diffusion functionality for the design of many symmetric-key primitives. In recent years, continuous efforts are made on the construction of MDS matrices with small area footprints in the context of lightweight cryptography. Just recently, Duval and Leurent (ToSC 2018/FSE 2019) reported some $32 \times 32$ binary MDS matrices with branch number 5, which can be implemented with only 67 XOR gates, whereas the previously known lightest ones of the same size cost 72 XOR gates. In this article, we focus on the construction of lightweight involutory MDS matrices, which are even more desirable than ordinary MDS matrices, since the same circuit can be reused when the inverse is required. In particular, we identify some involutory MDS matrices which can be realized with only 78 XOR gates with depth 4, whereas the previously known lightest involutory MDS matrices cost 84 XOR gates with the same depth. Notably, the involutory MDS matrix we find is much smaller than the AES MixColumns operation, which requires 97 XOR gates with depth 8 when implemented as a block of combinatorial logic that can be computed in one clock cycle. However, with respect to latency, the AES MixColumns operation is superior to our 78-XOR involutory matrices, since the AES MixColumns can be implemented with depth 3 by using more XOR gates. We prove that the depth of a $32\times 32$ MDS matrix with branch number 5 (e.g., the AES MixColumns operation) is at least 3. Then, we enhance Boyar's SLP-heuristic algorithm with circuit depth awareness, such that the depth of its output circuit is limited. Along the way, we give a formula for computing the minimum achievable depth of a circuit implementing the summation of a set of signals with given depths, which is of independent interest. We apply the new SLP heuristic to a large set of lightweight involutory MDS matrices, and we identify a depth 3 involutory MDS matrix whose implementation costs 88 XOR gates, which is superior to the AES MixColumns operation with respect to both lightweightness and latency, and enjoys the extra involution property.

Differential attacks are one of the main ways to attack block ciphers. Hence, we need to evaluate the security of a given block cipher against these attacks. One way to do so is to determine the minimal number of active S-boxes, and use this number along with the maximal differential probability of the S-box to determine the minimal probability of any differential characteristic. Thus, if one wants to build a new block cipher, one should try to maximize the minimal number of active S-boxes. On the other hand, the related-key security model is now quite important, hence, we also need to study the security of block ciphers in this model. In this work, we search how one could design a key schedule to maximize the number of active S-boxes in the related-key model. However, we also want this key schedule to be efficient, and therefore choose to only consider permutations. Our target is AES, and along with a few generic results about the best reachable bounds, we found a permutation to replace the original key schedule that reaches a minimal number of active S-boxes of 20 over 6 rounds, while no differential characteristic with a probability larger than $2^{-128}$ exists. We also describe an algorithm which helped us to show that there is no permutation that can reach 18 or more active S-boxes in 5 rounds. Finally, we give several pairs $(P_s, P_k)$, replacing respectively the ShiftRows operation and the key schedule of the AES, reaching a minimum of 21 active S-boxes over 6 rounds, while again, there is no differential characteristic with a probability larger than $2^{-128}$.

Streebog and Kuznyechik are the latest symmetric cryptographic primitives standardized by the Russian GOST. They share the same S-Box, $\pi$, whose design process was not described by its authors. In previous works, Biryukov, Perrin and Udovenko recovered two completely different decompositions of this S-Box. We revisit their results and identify a third decomposition of $\pi$. It is an instance of a fairly small family of permutations operating on $2m$ bits which we call TKlog and which is closely related to finite field logarithms. Its simplicity and the small number of components it uses lead us to claim that it has to be the structure intentionally used by the designers of Streebog and Kuznyechik. The $2m$-bit permutations of this type have a very strong algebraic structure: they map multiplicative cosets of the subfield $\mathbb{F}_{2^{m}}^{*}$ to additive cosets of $\mathbb{F}_{2^{m}}^{*}$. Furthermore, the function relating each multiplicative coset to the corresponding additive coset is always essentially the same. To the best of our knowledge, we are the first to expose this very strong algebraic structure. We also investigate other properties of the TKlog and show in particular that it can always be decomposed in a fashion similar to the first decomposition of Biryukov et al., thus explaining the relation between the two previous decompositions. It also means that it is always possible to implement a TKlog efficiently in hardware and that it always exhibits a visual pattern in its LAT similar to the one present in $\pi$. While we could not find attacks based on these new results, we discuss the impact of our work on the security of Streebog and Kuznyechik. To this end, we provide a new simpler representation of the linear layer of Streebog as a matrix multiplication in the exact same field as the one used to define $\pi$. We deduce that this matrix interacts in a non-trivial way with the partitions preserved by $\pi$.

In this work we show that the sponge construction can be used to construct quantum-secure pseudorandom functions. As our main result we prove that random sponges are quantum indistinguishable from random functions. In this setting the adversary is given superposition access to the input-output behavior of the construction but not to the internal function. Our proofs hold under the assumption that the internal function is a random function or permutation. We then use this result to obtain a quantum-security version of a result by Andreeva, Daemen, Mennink, and Van Assche (FSE'15) which shows that a sponge that uses a secure PRP or PRF as internal function is a secure PRF. This result also proves that the recent attacks against CBC-MAC in the quantum-access model by Kaplan, Leurent, Leverrier, and Naya-Plasencia (Crypto'16) and Santoli, and Schaffner (QIC'16) can be prevented by introducing a state with a non-trivial inner part. The proof of our main result is derived by analyzing the joint distribution of any $q$ input-output pairs. Our method analyzes the statistical behavior of the considered construction in great detail. The used techniques might prove useful in future analysis of different cryptographic primitives considering quantum adversaries. Using Zhandry's PRF/PRP switching lemma we then obtain that quantum indistinguishability also holds if the internal block function is a random permutation.

The automatic search method based on Mix-integer Linear Programming (MILP) is one of the most common tools to search the distinguishers of block ciphers. For differential analysis, the byte-oriented MILP model is usually used to count the number of differential active s-boxes and the bit-oriented MILP model is used to search the optimal differential characteristic. In this paper, we present the influences between the construction and solution of MILP models solved by Gurobi : 1). the number of variables; 2). the number of constraints; 3). the order of the constraints; 4). the order of variables in constraints. We carefully construct the MILP models according to these influences in order to find the desired results in a reasonable time. As applications, we search the differential characteristic of PRESENT,GIFT-64 and GIFT-128 in the single-key setting. We do a dual processing for the constraints of the s-box. It only takes 298 seconds to finish the search of the 8-round optimal differential characteristic based on the new MILP model. We also obtain the optimal differential characteristic of the 9/10/11-round PRESENT. With a special initial constraint, it only takes 4 seconds to obtain a 9-round differential characteristic with probability $2^{-42}$. We also get a 12/13-round differential characteristic with probability $2^{-58}/2^{-62}$. For GIFT-128, we improve the probability of differential characteristic of $9 \sim 21$ rounds and give the first attack on 26-round GIFT-128 based on a 20-round differential characteristic with probability $2^{-121.415}$.

TOHA is Key Hardened Function designed in the general spirit of sequential memory- hard function which based on secure cryptographic hash function, the idea behind its design is to make it harder for an attacker to perform some generic attacks and to make it costly as well, TOHA can be used for deriving keys from a master password or generating keys with length of 256-bit to be used in other algorithm schemes, general approach is to use a password and a salt like a normal scheme plus other parameters, and you can think of the salt as an index into a large set of keys derived from the same password, and of course you don’t need to hide the salt to operate.

De Bruijn sequences are a class of nonlinear recurring sequences that have wide applications in cryptography and modern communication systems. One main method for constructing them is to join the cycles of a feedback shift register (FSR) into a full cycle, which is called the cycle joining method. Jansen et al. (IEEE Trans on Information Theory 1991) proposed an algorithm for joining cycles of an arbitrary FSR. This classical algorithm is further studied in this paper. Motivated by their work, we propose a new algorithm for joining cycles, which doubles the efficiency of the classical cycle joining algorithm. Since both algorithms need FSRs that only generate short cycles, we also propose efficient ways to construct short-cycle FSRs. These FSRs are nonlinear and are easy to obtain. As a result, a large number of de Bruijn sequences are constructed from them. We explicitly determine the size of these de Bruijn sequences. Besides, we show a property of the pure circulating register, which is important for searching for short-cycle FSRs.

We propose an authenticated encryption scheme for the VMPC-R stream cipher. VMPC-R is an RC4-like algorithm proposed in 2013. It was created in a challenge to find a bias-free cipher within the RC4 design scope and to the best of our knowledge no security weakness in it has been published to date. The contribution of this paper is an algorithm to compute Message Authentication Codes (MACs) along with VMPC-R encryption. We also propose a simple method of transforming the MAC computation algorithm into a hash function.

We present a new Cryptographically Secure Pseudo-Random Number Generator. It uses permutations as its internal state, similarly to the RC4 stream cipher. We describe a statistical test which revealed non-random patterns in a sample of $2^{16.6}$ outputs of a 3-bit RC4. Our new algorithm produced $2^{46.8}$ undistinguishable from random 3-bit outputs in the same test. We probed $2^{51}$ outputs of the algorithm in different statistical tests with different word sizes and found no way of distinguishing the keystream from a random source. The size of the algorithm's internal state is $2^{3424}$ (for an 8-bit implementation). The algorithm is cryptographically secure to the extent we were able to analyse it. Its design is simple and easy to implement. We present the generator along with a key scheduling algorithm processing both keys and initialization vectors.

In this paper, we propose a new general construction to reduce the public key size of McEliece cryptosystems constructed from automorphism-induced Goppa codes. In particular, we generalize the ideas of automorphism-induced Goppa codes by considering nontrivial subsets of automorphism groups to construct Goppa codes with a nice block structure. By considering additive and multiplicative automorphism subgroups, we provide explicit constructions to demonstrate our technique. We show that our technique can be applied to automorphism-induced Goppa codes based cryptosystems to further reduce their key sizes.

Message franking enables cryptographically verifiable reporting of abusive content in end-to-end encrypted messaging. Grubbs, Lu, and Ristenpart recently formalized the needed underlying primitive, what they call compactly committing authenticated encryption (AE), and analyzed the security of a number of approaches. But all known secure schemes are still slow compared to the fastest standard AE schemes. For this reason Facebook Messenger uses AES-GCM for franking of attachments such as images or videos. We show how to break Facebook’s attachment franking scheme: a malicious user can send an objectionable image to a recipient but that recipient cannot report it as abuse. The core problem stems from use of fast but non-committing AE, and so we build the fastest compactly committing AE schemes to date. To do so we introduce a new primitive, called encryptment, which captures the essential properties needed. We prove that, unfortunately, schemes with performance profile similar to AES-GCM won’t work. Instead, we show how to efficiently transform Merkle-Damgärd-style hash functions into secure encryptments, and how to efficiently build compactly committing AE from encryptment. Ultimately our main construction allows franking using just a single computation of SHA-256 or SHA-3. Encryptment proves useful for a variety of other applications, such as remotely keyed AE and concealments, and our results imply the first single-pass schemes in these settings as well.

Secure block cipher design is a complex discipline which combines mathematics, engineering, and computer science. In order to develop cryptographers who are grounded in all three disciplines, it is necessary to undertake synergistic research as early as possible in technical curricula, particularly at the undergraduate university level. In this work, students are presented with a new block cipher, which is designed to offer moderate security while providing engineering and analysis challenges suitable for the senior undergraduate level. The BIG (Block) (Instructional, Generic) cipher is analyzed for vulnerability to linear cryptanalysis. Further, the cipher is implemented using the Nios II microprocessor and two configurations of memory-mapped hardware accelerators, in the Cyclone V FPGA on the Terasic DE1 System-on-chip (SoC). Three distinct implementations are realized: 1) Purely software (optimized for latency), 2) Purely hardware (optimized for area), and 3) A hardware-software codesign (optimized for throughput-to-area ratio). All three implementations are evaluated in terms of latency (encryption and decryption), throughput (Mbps), area (ALMs), and throughput-to-area (TP/A) ratio (Mbps/ALM); all metrics account for a fully functional Nios II, 8 kilobytes of on-chip RAM, Avalon interconnect, benchmark timer, and any hardware accelerators. In terms of security, we demonstrate recovery of a relationship among 12 key bits using as few as 16,000 plaintext/ciphertext pairs in a 6-round reduced round attack and reveal a diffusion rate of only 43.3 percent after 12 rounds. The implementation results show that the hardware-software codesign achieves a 67x speed-up and 37x increase in TP/A ratio over the software implementation, and 5x speed-up and 5x increase in TP/A ratio compared to the hardware implementation.

The design of modern stream ciphers is strongly influenced by the fact that Time-Memory-Data tradeoff attacks (TMD-TO attacks) reduce their effective key length to $\mathit{SL}/2$, where $\mathit{SL}$ denotes the inner state length. The classical solution, employed, e.g., by eSTREAM portfolio members Trivium and Grain v1, is to design the cipher in accordance with the Large-State-Small-Key construction, which implies that $\mathit{SL}$ is at least twice as large as the session key length $\mathit{KL}$. In the last years, a new line of research looking for alternative stream cipher constructions guaranteeing a higher TMD-TO resistance with smaller inner state lengths has emerged. So far, this has led to three generic constructions: the LIZARD construction, having a provable TMD-TO resistance of $2\cdot \mathit{SL}/3$; the Continuous-Key-Use construction, underlying the stream cipher proposals Sprout, Plantlet, and Fruit; and the Continuous-IV-Use construction, very recently proposed by Hamann, Krause, and Meier. Meanwhile, it could be shown that the Continuous-Key-Use construction is vulnerable against certain nontrivial distinguishing attacks. In this paper, we present a formal framework for proving security lower bounds on the resistance of generic stream cipher constructions against TMD-TO attacks and analyze two of the constructions mentioned above. First, we derive a tight security lower bound of approximately $\min\{\mathit{KL},\mathit{SL}/2\}$ on the resistance of the Large-State-Small-Key construction. This shows that the feature $\mathit{KL}\le \mathit{SL}/2$ does not open the door for new nontrivial TMD-TO attacks against Trivium and Grain v1 which are more dangerous than the known ones. Second, we prove a maximal security bound on the TMD-TO resistance of the Continuous-IV-Use construction, which shows that designing concrete instantiations of ultra-lightweight Continuous-IV-Use stream ciphers is a hopeful direction of future research.

In this paper we extend the work presented by Ashur and Posteuca in BalkanCryptSec 2018, by designing 0-correlation key-dependent linear trails covering more than one round of DES. First, we design a 2-round 0-correlation key-dependent linear trail which we then connect to Matsui's original trail in order to obtain a linear approximation covering the full DES and 3DES. We show how this approximation can be used for a key recovery attack against both ciphers. To the best of our knowledge, this paper is the first to use this kind of property to attack a symmetric-key algorithm, and our linear attack against 3DES is the first statistical attack against this cipher.

Determining the security of AES is a central problem in cryptanalysis, but progress in this area had been slow and only a handful of cryptanalytic techniques led to significant advancements. At Eurocrypt 2017 Grassi et al. presented a novel type of distinguisher for AES-like structures, but so far all the published attacks which were based on this distinguisher were inferior to previously known attacks in their complexity. In this paper we combine the technique of Grassi et al. with several other techniques in a novel way to obtain the best known key recovery attack on 5-round AES in the single-key model, reducing its overall complexity from about $2^{32}$ to less than $2^{22}$. Extending our techniques to 7-round AES, we obtain the best known attacks on AES-192 which use practical amounts of data and memory, breaking the record for such attacks which was obtained in 2000 by the classical Square attack.

Seminal results by Luby and Rackoff show that the 3-round Feistel cipher is secure against chosen-plaintext attacks (CPAs), and the 4-round version is secure against chosen-ciphertext attacks (CCAs). However, the security significantly changes when we consider attacks in the quantum setting, where the adversary can make superposition queries. By using Simon's algorithm that detects a secret cycle-period in polynomial-time, Kuwakado and Morii showed that the 3-round version is insecure against quantum CPA by presenting a polynomial-time distinguisher. Since then, Simon's algorithm has been heavily used against various symmetric-key constructions. However, its applications are still not fully explored. In this paper, based on Simon's algorithm, we first formalize a sufficient condition of a quantum distinguisher against block ciphers so that it works even if there are multiple collisions other than the real period. This distinguisher is similar to the one proposed by Santoli and Schaffner, and it does not recover the period. Instead, we focus on the dimension of the space obtained from Simon's quantum circuit. This eliminates the need to evaluate the probability of collisions, which was needed in the work by Kaplan et al. at CRYPTO 2016. Based on this, we continue the investigation of the security of Feistel ciphers in the quantum setting. We show a quantum CCA distinguisher against the 4-round Feistel cipher. This extends the result of Kuwakado and Morii by one round, and follows the intuition of the result by Luby and Rackoff where the CCA setting can extend the number of rounds by one. We also consider more practical cases where the round functions are composed of a public function and XORing the subkeys. We show the results of both distinguishing and key recovery attacks against these constructions.

In this paper, we describe and analyze the security of the AES-GCM-SIV mode of operation, as defined in the CFRG specification \cite{CFRG}. This mode differs from the original GCM-SIV mode that was designed in \cite{GL2015} in two main aspects. First, the CTR encryption uses a 127-bit pseudo-random counter instead of a 95-bit pseudo-random value concatenated with a 32-bit counter. This construction leads to improved security bounds when encrypting short messages. In addition, a new key derivation function is used for deriving a fresh set of keys for each nonce. This addition allows for encrypting up to $2^{50}$ messages with the same key, compared to the significant limitation of only $2^{32}$ messages that were allowed with GCM-SIV (which inherited this same limit from AES-GCM). As a result, the new construction is well suited for real world applications that need a nonce-misuse resistant Authenticated Encryption scheme. We explain the limitations of GCM-SIV, which motivate the new construction, prove the security properties of AES-GCM-SIV, and show how these properties support real usages. Implementations are publicly available in \cite{ShayGit}. We remark that AES-GCM-SIV is already integrated into Google's BoringSSL library \cite{BoringSSL}, and its deployment for ticket encryption in QUIC \cite{QUIC} is underway.

The division property proposed at Eurocrypt'15 is a novel technique to find integral distinguishers, which has been applied to most kinds of symmetric ciphers such as block ciphers, stream ciphers, and authenticated encryption,~\textit{etc}. The original division property is word-oriented, and later the bit-based one was proposed at FSE'16 to get better integral property, which is composed of conventional bit-based division property (two-subset division property) and bit-based division property using three subsets (three-subset division property). Three-subset division property has more potential to achieve better integral distinguishers compared with the two-subset division property. The bit-based division property could not be to apply to ciphers with large block sizes due to its unpractical complexity. At Asiacrypt'16, the two-subset division property was modeled using Mixed Integral Linear Programming (MILP) technique, and the limits of block sizes were eliminated. However, there is still no efficient method searching for three-subset division property. The propagation rule of the \texttt{XOR} operation for $\mathbb{L}$ \footnote{The definition of $\mathbb{L}$ and $\mathbb{K}$ is introduced in Section 2.}, which is a set used in the three-set division property but not in two-set one, requires to remove some specific vectors, and new vectors generated from $\mathbb{L}$ should be appended to $\mathbb{K}$ when \texttt{Key-XOR} operation is applied, both of which are difficult for common automatic tools such as MILP, SMT or CP. In this paper, we overcome one of the two challenges, concretely, we address the problem to add new vectors into $\mathbb{K}$ from $\mathbb{L}$ in an automatic search model. Moreover, we present a new model automatically searching for a variant three-subset division property (VTDP) with STP solver. The variant is weaker than the original three-subset division property (OTDP) but it is still powerful in some ciphers. Most importantly, this model has no constraints on the block size of target ciphers, which can also be applied to ARX and S-box based ciphers. As illustrations, some improved integral distinguishers have been achieved for SIMON32, SIMON32/48/64(102), SPECK32 and KATAN/KTANTAN32/48/64 according to the number of rounds or number of even/odd-parity bits.

Two vectorial Boolean functions are ``CCZ-equivalent'' if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a CCZ-equivalence class into its Extended-Affine (EA) equivalence classes; EA-equivalence being a simple particular case of CCZ-equivalence. In this paper, we characterize CCZ-equivalence as a property of the zeroes in the Walsh spectrum of a function $F : \mathbb{F}_2^{n} \to \mathbb{F}_2^{m}$ or, equivalently, of the zeroes in its Difference Distribution Table. We use this framework to show how to efficiently upper bound the number of distinct EA-equivalence classes in a given CCZ-equivalence class. More importantly, we prove that it is possible to go from a specific member of any EA-equivalence class to a specific member of another EA-equivalence class in the same CCZ-equivalence class using an operation called \emph{twisting}; so that CCZ-equivalence can be reduced to the association of EA-equivalence and twisting. Twisting a function is a simple process and its possibility is equivalent to the existence of a particular decomposition of the function considered. Using this knowledge, we revisit several results from the literature on CCZ-equivalence and show how they can be interpreted in light of our new framework. Our results rely on a new concept, the ``thickness'' of a space (or linear permutation), which can be of independent interest.

It is widely known that double encryption does not substantially increase the security of a block cipher. Indeed, the classical meet-in-the middle attack recovers the $2k$-bit secret key at the cost of roughly $2^k$ off-line enciphering operations, in addition to very few known plaintext-ciphertext pairs. Thus, essentially as efficiently as for the underlying cipher with a $k$-bit key. This paper revisits double encryption under the lens of multi-user security. We prove that its security degrades only very mildly with an increasing number of users, as opposed to single encryption, where security drops linearly. More concretely, we give a tight bound for the multi-user security of double encryption as a pseudorandom permutation in the ideal-cipher model, and describe matching attacks. Our contribution is also conceptual: To prove our result, we enhance and generalize the generic technique recently proposed by Hoang and Tessaro for lifting single-user to multi-user security. We believe this technique to be broadly applicable.

We prove beyond-birthday-bound security for the well-known types of generalized Feistel networks, including: (1) unbalanced Feistel networks, where the $n$-bit to $m$-bit round functions may have $n\ne m$; (2) alternating Feistel networks, where the round functions alternate between contracting and expanding; (3) type-1, type-2, and type-3 Feistel networks, where $n$-bit to $n$-bit round functions are used to encipher $kn$-bit strings for some $k\ge2$; and (4) numeric variants of any of the above, where one enciphers numbers in some given range rather than strings of some given size. Using a unified analytic framework we show that, in any of these settings, for any $\varepsilon>0$, with enough rounds, the subject scheme can tolerate CCA attacks of up to $q\sim N^{1-\varepsilon}$ adversarial queries, where $N$ is the size of the round functions' domain (the size of the larger domain for alternating Feistel). This is asymptotically optimal. Prior analyses for generalized Feistel networks established security to only $q\sim N^{0.5}$ adversarial queries.

A definition of \textit{online authenticated-encryption} (OAE), call it OAE1, was given by Fleischmann, Forler, and Lucks (2012). It has become a popular definitional target because, despite allowing encryption to be online, security is supposed to be maintained even if nonces get reused. We argue that this expectation is effectively wrong. OAE1 security has also been claimed to capture best-possible security for any online-AE scheme. We claim that this understanding is wrong, too. So motivated, we redefine OAE-security, providing a radically different formulation, OAE2. The new notion effectively \textit{does} capture best-possible security for a user's choice of plaintext segmentation and ciphertext expansion. It is achievable by simple techniques from standard tools. Yet even for OAE2, nonce-reuse can still be devastating. The picture to emerge is that no OAE definition can meaningfully tolerate nonce-reuse, but, at the same time, OAE security ought neverhave been understood to turn on this question.

This paper introduces Freestyle, a randomized, and variable round version of the ChaCha cipher. Freestyle demonstrates the concept of hash based halting condition, where a decryption attempt with an incorrect key is likely to take longer time to halt. This makes it resistant to key-guessing attacks i.e. brute-force and dictionary based attacks. Freestyle uses a novel approach for ciphertext randomization by using random number of rounds for each block of message, where the exact number of rounds are unknown to the receiver in advance. Due to its inherent random behavior, Freestyle provides the possibility of generating up to $2^{256}$ different ciphertexts for a given key, nonce, and message; thus resisting key and nonce reuse attacks. This also makes cryptanalysis through known-plaintext, chosen-plaintext, and chosen-ciphertext attacks difficult in practice. Freestyle is highly customizable, which makes it suitable for both low-powered devices as well as security-critical applications. It is ideal for: (i) applications that favor ciphertext randomization and resistance to key-guessing and key reuse attacks; and (ii) situations where ciphertext is in full control of an adversary for carrying out an offline key-guessing attack.

To deal with message streams, which is required by many symmetric cryptographic functionalities (MAC, AE, HASH), we propose a lightweight round function called Thin Sponge. We give a framework to construct all these functionalities (MAC, AE, and HASH) using the same Thin Sponge round function. Besides the common security assumptions behind traditional symmetric algorithms, the security of our schemes depends on the hardness of problems to find collisions of some states. We give a class of constructions of Thin Sponge, which is improvement of the round function of Trivium and ACORN. We give simple criteria for determining parameters. According to these criteria, we give an example, which achieves all functionalities in a single round function and hence can be realized by the same hardware. Our algorithm is also efficient in software.

In this paper we study a problem which emerged during an attempt to apply a differential cryptanalysis method to the <<Magma>> algorithm. We obtained a general formula of distribution in the difference distribution table of addition modulo $2^n$ and provided an efficient method for computing the distribution in a row with given index. Moreover, an exact formula that may be used to solve the task of counting all the distributions was obtained, and an asymptotically accurate approximation of number of distinct distributions was proved. Finally, we designed an algorithm to generate all distributions in $2^{O(\sqrt{(n)})}$ operations (whereas the corresponding brute-force method takes $2^{\Omega(n)}$).

SIMON and SPECK families of block ciphers are well-known lightweight ciphers designed by NSA. In this note, based on the previous investigations on SIMON, a closed formula for the squared correlations and differential probabilities of the mapping $\phi(x) = x \odot S^1(x)$ on $\mathbb{F}_2^n$ is given. From the aspects of linear and differential cryptanalysis, this mapping is equivalent to the core quadratic mapping of SIMON via rearrangement of coordinates and EA-equivalence. Based upon the proposed explicit formula, a full description of DDT and LAT of $\phi$ is provided. In the case of SPECK, as the only nonlinear operation in this family of ciphers is, addition mod $2^n$, after reformulating the formula for linear and differential probabilities of addition mod $2^n$, straightforward algorithms for finding the output masks with maximum squared correlation, given the input masks as well as the output differences with maximum differential probability, given the input differences, are presented.

The ZK-STARK technology, published by Ben-Sasson et al. in ePrint 2018/046 is hailed by many as being a viable, efficient solution to the scaling problem of cryptocurrencies. In essence, a ZK-STARK proof uses a Merkle-tree to compress the data that needs to be verified, thus greatly reduces the communication overhead between the prover and the verifier. We propose MARVELlous a family of cryptographic algorithms specifically designed for STARK efficiency. The family currently includes the block cipher Jarvis and the hash function Friday. The design of Jarvis is inspired by the design of Rijndael, better known as the AES. By doing so we create a cipher with similar properties to those of Rijndael which allows us to reuse the wide-trail strategy to argue the resistance of the design against differential and linear cryptanalysis and focus our efforts on resistance against algebraic attacks. Friday is a Merkle-Damgard based hash function instantiated with Jarvis as its compression function thus it inherits its security properties up to the birthday bound. Jarvis and Friday have been suggested to be used in the Ethereum protocol by Ben-Sasson in Ethereum's Devcon IV. In this paper, we instantiate versions of Jarvis offering 128, 160, 192 and 256-bit security (both state- and key-size) which are used to implement Friday. We warmly invite the community to study and assess the security of the designs.

The keyed sponge is a well-accepted method for message authentication. It processes data at a certain rate by sequential evaluation of an underlying permutation. If the key size $k$ is smaller than the rate, currently known bounds are tight, but if it exceeds the rate, state of the art only dictates security up to $2^{k/2}$. We take closer inspection at the key prediction security of the sponge and close the remaining gap in the existing security analysis: we confirm key security up to close to $2^k$, regardless of the rate. The result impacts all applications of the keyed sponge and duplex that process at a rate smaller than the key size, including the STROBE protocol framework, as well as the related constructions such as HMAC-SHA-3 and the sandwich sponge.

We present practical attacks against OCB2, an ISO-standard authenticated encryption (AE) scheme. OCB2 is a highly-efficient blockcipher mode of operation. It has been extensively studied and widely believed to be secure thanks to the provable security proofs. Our attacks allow the adversary to create forgeries with single encryption query of almost-known plaintext. This attack can be further extended to powerful almost-universal and universal forgeries using more queries. The source of our attacks is the way OCB2 implements AE using a tweakable blockcipher, called XEX*. We have verified our attacks using a reference code of OCB2. Our attacks do not break the privacy of OCB2, and are not applicable to the others, including OCB1 and OCB3.

This paper presents the complete description of the best differentials and linear hulls in 2-round Kuznyechik. We proved that 2-round $\mathrm{MEDP}=2^{-86.66...}$, $\mathrm{MELP}=2^{-76.739...}$. A comparison is made with similar results for the AES cipher.

We develop new constructions of lattice-based PRFs using keyed pseudorandom synthesizers. We generalize all of the known `basic' parallel lattice-based PRFs--those of [BPR12], [BLMR13], and [BP14]--to build highly parallel lattice-based PRFs with smaller modulus (and thus better reductions from worst-case lattice problems) while still maintaining computational efficiency asymptotically equal to the fastest known lattice-based PRFs at only the cost of larger key sizes. In particular, we build several parallel (in $NC^{2}$) lattice-based PRFs with modulus independent of the number of PRF input bits based on both standard LWE and ring LWE. Our modulus for these PRFs is just $O \left(m^{ f \left(m \right)} \right)$ for lattice dimension $m$ and any function $f \left(m \right) \in \omega \left(1 \right)$. The only known parallel construction of a lattice-based PRF with such a small modulus is a construction from Banerjee's thesis, and some of our parallel PRFs with equivalently small modulus have smaller key sizes and are very slightly faster (when using FFT multiplication). These PRFs also asymptotically match the computational efficiency of the most efficient PRFs built from any LWE- or ring LWE-based assumptions known (potentially excluding some concurrent work), respectively, and concretely require less computation per output than any known parallel lattice-based PRFs (again when using FFT multiplication). We additionally use our techniques to build other efficient PRFs with very low circuit complexity (but higher modulus) which improve known results on highly parallel lattice PRFs. For instance, for input length $\lambda$, we show that there exists a ring LWE-based PRF in $NC^{1}$ with modulus proportional to $m^{\lambda^{c}}$ for any $c \in \left(0, 1 \right)$. Constructions from lattices with this circuit depth were only previously known from larger moduli.

At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon's algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with O(n) quantum time and queries. In this paper we propose many other types of quantum slide attacks. First, we are able to quantize classical advanced slide attacks on Feistel networks. With modular additions inside branch or key-addition operations, these attacks reach up to two round self-similarity. With only XOR operations, they reach up to four rounds self-similarity, with a cost at most quadratic in the block size. Moreover, some of these variants combined with whitening keys (FX construction) can be successfully attacked. We show how these results relate to general quantization principles of classical techniques including sliding with a twist, complementation slide and mirror slidex. Furthermore, we show that some quantum slide attacks can be composed with other quantum attacks to perform efficient key-recoveries even when the round founction is a strong function classically. Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, that were thought to enjoy an exponential speed up in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.

Little theoretical work has been done on $(n,m)$-functions when $\frac {n}{2}<m<n$, even though these functions can be used in Feistel ciphers, and actually play an important role in several block ciphers. Nyberg has shown that the differential uniformity of such functions is bounded below by $2^{n-m}+2$ if $n$ is odd or if $m>\frac {n}{2}$. In this paper, we first characterize the differential uniformity of those $(n,m)$-functions of the form $F(x,z)=\phi(z)I(x)$, where $I(x)$ is the $(m,m)$-Inverse function and $\phi(z)$ is an $(n-m,m)$-function. Using this characterization, we construct an infinite family of differentially $\Delta$-uniform $(2m-1,m)$-functions with $m\geq 3$ achieving Nyberg's bound with equality, which also have high nonlinearity and not too low algebraic degree. We then discuss an infinite family of differentially $4$-uniform $(m+1,m)$-functions in this form, which leads to many differentially $4$-uniform permutations. We also present a method to construct infinite families of $(m+k,m)$-functions with low differential uniformity and construct an infinite family of $(2m-2,m)$-functions with $\Delta\leq2^{m-1}-2^{m-6}+2$ for any $m\geq 8$. The constructed functions in this paper may provide more choices for the design of Feistel ciphers.

Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bit is the so-called Big APN Problem. It has been solved in the 6-bit case by Dillon et al. in 2009 but, since then, the general case has remained an open problem. In 2016, Perrin et al. discovered the butterfly structure which contains Dillon et al.'s permutation over $\mathbb{F}_{2^6}$. Later, Canteaut et al. generalised this structure and proved that no other butterflies with exponent $3$ can be APN. Recently, Yongqiang et al. further generalized the structure with Gold exponent and obtained more differentially 4-uniform permutations with the optimal nonlinearity. However, the existence of more APN permutations in their generalization was left as an open problem. In this paper, we adapt the proof technique of Canteaut et al. to handle all Gold exponents and prove that a generalised butterfly with Gold exponents over $\mathbb{F}_{2^{2n}}$ can never be APN when $n>3$. More precisely, we prove that such a generalised butterfly being APN implies that the branch size is strictly smaller than 5. Hence, the only APN butterflies operate on 3-bit branches, i.e. on 6 bits in total.

This note defines Kravatte-SANE and Kravatte-SANSE. Both are session authenticated encryption schemes and differ in their robustness with respect to nonce misuse. They are defined as instances of modes on top of the deck function Kravatte, where a deck function is a keyed function with variable-length input strings, an arbitrary-length output and certain incrementality properties.

In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) scheme (i.e., an encryption scheme that supports comparisons over encrypted values). However, Naveed et al. (CCS 2015) recently showed that OPE-encrypted databases are extremely vulnerable to "inference attacks." In this work, we consider a related primitive called order-revealing encryption (ORE), which is a generalization of OPE that allows for stronger security. We begin by constructing a new ORE scheme for small message spaces which achieves the "best-possible" notion of security for ORE. Next, we introduce a "domain-extension" technique and apply it to our small-message-space ORE. While our domain-extension technique does incur a loss in security, the resulting ORE scheme we obtain is more secure than all existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives. As part of our analysis, we also give a tight lower bound for OPE and show that no efficient OPE scheme can satisfy best-possible security if the message space contains just three messages. Thus, achieving strong notions of security for even small message spaces requires moving beyond OPE. Finally, we examine the properties of our new ORE scheme and show how to use it to construct an efficient range query protocol that is robust against the inference attacks of Naveed et al. We also give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes, it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.

At CRYPTO 2018, we proposed a method to reduce the Boolean polynomial of 855-round Trivium. By multiplying a polynomial reduction factor, the output Boolean polynomial is simplified. Based on this method, a 855-round key-recovery attack on Trivium is introduced. In addition, we also give a practical attack on 721-round Trivium to show some rationality and evidence. However, Yonglin Hao et al. find some errors in the 721-round attack recently. As a correction, we propose some new right 721-round example attacks based on our method proposed at CRYPTO 2018.

Authenticated Encryption ($\mathsf{AE}$) achieves confidentiality and authenticity, the two most fundamental goals of cryptography, in a single scheme. A common strategy to obtain $\mathsf{AE}$ is to combine a Message Authentication Code $(\mathsf{MAC})$ and an encryption scheme, either nonce-based or $\mathsf{iv}$-based. Out of the 180 possible combinations, Namprempre et al.~[25] proved that 12 were secure, 164 insecure and 4 were left unresolved: A10, A11 and A12 which use an $\iv$-based encryption scheme and N4 which uses a nonce-based one. The question of the security of these composition modes is particularly intriguing as N4, A11, and A12 are more efficient than the 12 composition modes that are known to be provably secure.\\ We prove that: $(i)$ N4 is not secure in general, $(ii)$ A10, A11 and A12 have equivalent security, $(iii)$ A10, A11, A12 and N4 are secure if the underlying encryption scheme is either misuse-resistant or ``message malleable'', a property that is satisfied by many classical encryption modes, $(iv)$ A10, A11 and A12 are insecure if the underlying encryption scheme is stateful or untidy.\\ All the results are quantitative.

Recently, another kind of dynamic cube attack is proposed by Fu et al. With some key guesses and a transformation in the output bit, they claim that, when the key guesses are correct, the degree of the transformed output bit can drop so significantly that the cubes of lower dimension can not exist, making the output bit vulnerable to the zero-sum cube tester using slightly higher dimensional cubes. They applied their method to 855-round TRIVIUM. In order to verify the correctness of their result, they even proposed a practical attack on 721-round TRIVIUM claiming that the transformed output bit after 721-rounds of initialization does not contain cubes of dimensions 31 and below. However, the degree evaluation algorithm used by Fu et al. is innovative and complicated, and its complexity is not given. Their algorithm can only be implemented on huge clusters and cannot be verified by existing theoretic tools. In this paper, we theoretically analyze the dynamic cube attack method given by Fu et al. using the division property and MILP modeling technique. Firstly, we draw links between the division property and Fu et al.'s dynamic cube attack so that their method can be described as a theoretically well founded and computationally economic MILP-aided division-property-based cube attack. With the MILP model drawn according to the division property, we analyzed the 721-round TRIVIUM in detail and find some interesting results: \begin&#8203;{enumerate} \item The degree evaluation using our MILP method is more accurate than that of Fu et al.'s. Fu et al. prove that the degree of pure z721z721 is 40 while our method gives 29. We practically proved the correctness of our method by trying thousands of random keys, random 30-dimensional cubes and random assignments to non-cube IVs finding that the summations are constantly 0. \item For the transformed output bit (1+s2901)&#8901;z721(1+s1290)&#8901;z721, we proved the same degree 31 as Fu et al. and we also find 32-dimensional cubes have zero-sum property for correct key guesses. But since the degree of pure z721z721 is only 29, the 721-round practical attack on TRIVIUM is violating the principle of Fu et al.'s work: after the transformation in the output bit, when the key guesses are correct, the degree of the transformed output bit has not dropped but risen. \item Now that the degree theoretic foundation of the 721-round attack has been violated, we also find out that the key-recovery attack cannot be carried out either. We theoretically proved and practically verified that no matter the key guesses are correct or incorrect, the summation over 32-dimensional cube are always 0. So, no key bit can be recovered at all. \end{enumerate} All these analysis on 721-round TRIVIUM can be verified practically and we open our C++ source code for implementation as well. Secondly, we revisit their 855-round result. Our MILP model reveal that the 855-round result suffers from the same problems with its 721-round counterpart. We provide theoretic evidence that, after their transformation, the degree of the output bit is more likely to rise rather than drop. Furthermore, since Fu \etal's degree evaluation is written in an unclear manner and no complexity analysis is given, we rewrite the algorithm according to their main ideas and supplement a detailed complexity analysis. Our analysis indicates that a precise evaluation to the degree requires complexities far beyond practical reach. We also demonstrate that further abbreviation to our rewritten algorithm can result in wrong evaluation. This might be the reason why Fu \etal give such a degree evaluation. This is also an additional argument against Fu \etal's dynamic cube attack method. Thirdly, the selection of Fu \etal's cube dimension is also questionable. According to our experiments and existing theoretic results, there is high risk that the correct key guesses and wrong ones share the same zero-sum property using Fu \etal's cube testers. As a remedy, we suggest that concrete cubes satisfying particular conditions should be identified rather than relying on the IV-degree drop hypothesis. To conclude, Fu \etal's dynamic cube attack on 855-round TRIVIUM is questionable. 855-round as well as 840-and-up-round TRIVIUM should still be open for further convincible cryptanalysis.

Strong Pseudo-random Permutations (SPRPs) are important for various applications. In general, it is desirable to base an SPRP on a single-keyed primitive for minimizing the implementation costs. For constructions built on classical block ciphers, Nandi showed at ASIACRYPT'15 that at least two calls to the primitive per processed message block are required for SPRP security, assuming that all further operations are linear. The ongoing trend of using tweakable block ciphers as primitive has already led to MACs or encryption modes with high security and efficiency properties. Thus, three interesting research questions are hovering in the domain of SPRPs: (1) if and to which extent the bound of two calls per block can be reduced with a tweakable block cipher, (2) how concrete constructions could be realized, and (3) whether full $n$-bit security is achievable from primitives with $n$-bit state size. The present work addresses all three questions. Inspired by Iwata et al.'s ZHash proposal at CRYPTO'17, we propose the ZCZ (ZHash-Counter-ZHash) construction, a single-key variable-input-length SPRP based on a single tweakable block cipher whose tweak length is at least its state size. ZCZ possesses close to optimal properties with regards to both performance and security: not only does it require only asymptotically $3\ell/2$ calls to the primitive for $\ell$-block messages, but we also show that this figure is close to the minimum by an PRP distinguishing attack on any construction with tweak size of $\tau = n$ bits and fewer than $(3\ell-1)/2$ calls to the same primitive. Moreover, it provides optimal $n$-bit security for a primitive with $n$-bit state and tweak size.

We present hash functions that are almost optimally one-way in the quantum setting. Our hash functions are based on the Merkle-Damgård construction iterating a Davies-Meyer compression function, which is built from a block cipher. The quantum setting that we use is a natural extention of the classical ideal cipher model. Recent work has revealed that symmetric-key schemes using a block cipher or a public permutation, such as CBC-MAC or the Even-Mansour cipher, can get completely broken with quantum superposition attacks, in polynomial time of the block size. Since many of the popular schemes are built from a block cipher or a permutation, the recent findings motivate us to study such schemes that are provably secure in the quantum setting. Unfortunately, no such schemes are known, unless one relies on certain algebraic assumptions. In this paper we present hash constructions that are provably one-way in the quantum setting without algebraic assumptions, solely based on the assumption that the underlying block cipher is ideal. To do this, we reduce one-wayness to a problem of finding a fixed point and then bound its success probability with a distinguishing advantage. We develop a generic tool that helps us prove indistinguishability of two quantum oracle distributions.

In this paper we use MILP technique for automatic search for differential characteristics of ARX ciphers LEA and HIGHT. We show that the MILP model of the differential property of modular addition with one constant input can be represented with a much less number of linear inequalities compared to the general case. Benefiting from this new developed model for HIGHT block cipher, we can achieve a reduction of 112r out of 480r in the total number of linear constraints for MILP model of r-round of HIGHT. This saving accelerates the searching process of HIGHT about twice as fast. We enjoy the MILP model to investigate the differential effect of these ciphers and provide a more accurate estimation for the differential probability, as well. Our observations show that despite HIGHT, LEA exhibits a strong differential effect. The details of differential effects are reflected in a more compact manner using the newly defined notion of probability polynomial. The results gained by this method improve or extend the previous results as follows. For LEA block cipher, we found more efficient 12 and 13-round differentials whose probabilities are better than the best previous 12 and 13-round differentials for a factor of about 2^6 and 2^7, respectively. In the case of HIGHT block cipher, we found two new 12 and 13-round differentials, though with the same best reported probabilities.

Linear cryptanalysis considers correlations between linear input and output combiners for block ciphers and stream ciphers. Daeman and Rijmen (2007) had obtained the distributions of the correlations between linear input and output combiners of uniform random functions and uniform random permutations. Our first contribution is to generalise these results to obtain the distributions of the correlations between arbitrary input and output combiners of uniform random functions and uniform random permutations. Recently, Todo et al. (2018) have proposed nonlinear invariant attacks which consider correlations between nonlinear input and output combiners for a key-alternating block cipher. In its basic form, a nonlinear invariant attack is a distinguishing attack. The second and the main contribution of this paper is to obtain precise expressions for the errors of nonlinear invariant attacks in distinguishing a key-alternating cipher from either a uniform random function or a uniform random permutation.

Robust authenticated encryption (RAE) is a primitive for symmetric encryption that allows to flexibly specify the ciphertext expansion, i.e., how much longer the ciphertext is compared to the plaintext. For every ciphertext expansion, RAE aims at providing the best-possible authenticity and confidentiality. To investigate whether this is actually achieved, we characterize exactly the guarantees symmetric cryptography can provide for any given ciphertext expansion. Our characterization reveals not only that RAE reaches the claimed goal, but also, contrary to prior belief, that one cannot achieve full confidentiality without ciphertext expansion. This provides new insights into the limits of symmetric cryptography. Moreover, we provide a rigorous treatment of two previously only informally stated additional features of RAE; namely, we show how redundancy in the message space can be exploited to improve the security and we analyze the exact security loss if multiple messages are encrypted with the same nonce.

Motivated by the wide adoption of authenticated encryption and TLS, we suggest a basic channel abstraction, an augmented secure channel (ASC), that allows a sender to send a receiver messages consisting of two parts, where one is privacy-protected and both are authenticity-protected. Working in the tradition of constructive cryptography, we formalize this idea and provide a construction of this kind of channel using the lower-level tool authenticated-encryption. We look at recent proposals on TLS 1.3 and suggest that the criterion by which their security can be judged is quite simple: do they construct an ASC? Due to this precisely defined goal, we are able to give a natural construction that comes with a rigorous security proof and directly leads to a proposal on TLS 1.3 that is provably secure.

This paper studies the security of Ring Oscillator Physically Unclonable Function (PUF) with Enhanced Challenge-Response Pairs as proposed by Delavar et al. We present an attack that can predict all PUF responses after querying the PUF with n+2 attacker-chosen queries. This result renders the proposed RO-PUF with Enhanced Challenge-Response Pairs inapt for most typical PUF use cases, including but not limited to all cases where an attacker has query access.

In the context of fault attacks on nonce-based authenticated encryption, an attacker faces two restrictions. The first is the uniqueness of the nonce for each new encryption that prevents the attacker from collecting pairs of correct and faulty outputs to perform, e.g., differential fault attacks. The second restriction concerns the verification/decryption, which releases only verified plaintext. While many recent works either exploit misuse scenarios (e.g. nonce-reuse, release of unverified plaintext), we turn the fact that the decryption/verification gives us information on the effect of a fault (whether a fault changed a value or not) against it. In particular, we extend the idea of statistical ineffective fault attacks (SIFA) to target the initialization performed in nonce-based authenticated encryption schemes. By targeting the initialization performed during decryption/verification, most nonce-based authenticated encryption schemes provide the attacker with an oracle whether a fault was ineffective or not. This information is all the attacker needs to mount statistical ineffective fault attacks. To demonstrate the practical threat of the attack, we target software implementations of the authenticated encryption schemes Keyak and Ketje. The presented fault attacks can be carried out without the need of sophisticated equipment. In our practical evaluation the inputs corresponding to 24 ineffective fault inductions were required to reveal large parts of the secret key in both scenarios.

Threshold cryptography provides a mechanism for protecting secret keys by sharing them among multiple parties, who then jointly perform cryptographic operations. An attacker who corrupts upto a threshold number of parties cannot recover the secrets or violate security. Prior works in this space have mostly focused on definitions and constructions for public-key cryptography and digital signatures, and thus do not capture the security concerns and efficiency challenges of symmetric-key based applications which commonly use long-term (unprotected) master keys to protect data at rest, authenticate clients on enterprise networks, and secure data and payments on IoT devices. We put forth the first formal treatment for distributed symmetric-key encryption, proposing new notions of correctness, privacy and authenticity in presence of malicious attackers. We provide strong and intuitive game-based definitions that are easy to understand and yield efficient constructions. We propose a generic construction of threshold authenticated encryption based on any distributed pseudorandom function (DPRF). When instantiated with the two different DPRF constructions proposed by Naor, Pinkas and Reingold (Eurocrypt 1999) and our enhanced versions, we obtain several efficient constructions meeting different security definitions. We implement these variants and provide extensive performance comparisons. Our most efficient instantiation uses only symmetric-key primitives and achieves a throughput of upto 1 million encryptions/decryptions per seconds, or alternatively a sub-millisecond latency with upto 18 participating parties.

The Cascaded LRW2 tweakable block cipher was introduced by Landecker et al. at CRYPTO 2012, and proven secure up to $2^{2n/3}$ queries. There has not been any attack on the construction faster than the generic attack in $2^n$ queries. In this work we initiate the quest towards a tight bound. We first present a distinguishing attack in $2n^{1/2}2^{3n/4}$ queries against a generalized version of the scheme. The attack is supported with an experimental verification and a formal success probability analysis. We subsequently discuss non-trivial bottlenecks in proving tight security, most importantly the distinguisher's freedom in choosing the tweak values. Finally, we prove that if every tweak value occurs at most $2^{n/4}$ times, Cascaded LRW2 is secure up to $2^{3n/4}$ queries.

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, information theory as well as mathematics. Building new APN families is a challenge which has not been successfully addressed for more than seven years now. The most general known equivalence relation preserving APN property in characteristic 2 is CCZ-equivalence. Extended to general characteristic, it also preserves planarity. In the case of quadratic planar functions, it is a particular case of isotopic equivalence. We apply the idea of isotopic equivalence to transform APN functions in characteristic 2 into other functions, some of which can be APN. We deduce new quadratic APN functions and a new quadratic APN family.

SUM-ECBC (Yasuda, CT-RSA 2010) is the first beyond birthday bound (BBB) secure block cipher based deterministic MAC. After this work, some more BBB secure deterministic MACs have been proposed, namely PMAC_Plus (Yasuda, CRYPTO 2011), 3kf9 (Zhang et al., ASIACRYPT 2012) and LightMAC_Plus (Naito, ASIACRYPT 2017). In this paper, we have abstracted out the inherent design principle of all these BBB secure MACs and present a generic design paradigm to construct a BBB secure pseudo random function, namely Double-block Hash-then-Sum or in short (DbHtS). A DbHtS construction, as the name implies, computes a double block hash on the message and then sum the encrypted output of the two hash blocks. Our result renders that if the underlying hash function meets certain security requirements (namely cover-free and block-wise universal advantage is low), DbHtS construction provides $2n/3$-bit security. We demonstrate the applicability of our result by instantiating all the existing beyond birthday secure deterministic MACs (e.g., SUM-ECBC, PMAC_Plus, 3kf9, LightMAC_Plus) as well as a simple two-keyed variant for each of them and some algebraic hash based constructions.

Implementation attacks like side-channel and fault attacks are a threat to deployed devices especially if an attacker has physical access. As a consequence, devices like smart cards and IoT devices usually provide countermeasures against implementation attacks, such as masking against side-channel attacks and detection-based countermeasures like temporal or spacial redundancy against fault attacks. In this paper, we show how to attack implementations protected with both masking and detection-based fault countermeasures by using statistical ineffective fault attacks using a single fault induction per execution. Our attacks are largely unaffected by the deployed protection order of masking and the level of redundancy of the detection-based countermeasure. These observations show that the combination of masking plus error detection alone may not provide sufficient protection against implementation attacks.

This work focuses on side-channel resilient design strategies for symmetric-key cryptographic primitives targeting lightweight applications. In light of NIST's lightweight cryptography project, design choices for block ciphers must consider not only security against traditional cryptanalysis, but also side-channel security, while adhering to low area and power requirements. In this paper, we explore design strategies for substitution-permutation network (SPN)-based block ciphers that make them amenable to low-cost threshold implementations (TI) - a provably secure strategy against side-channel attacks. The core building blocks for our strategy are cryptographically optimal 4x4 S-Boxes, implemented via repeated iterations of simple cellular automata~(CA) rules. We present highly optimized TI circuits for such S-Boxes, that consume nearly 40% less area and power as compared to popular lightweight S-Boxes such as PRESENT and GIFT. We validate our claims via implementation results on ASIC using 180nm technology. We also present a comparison of TI circuits for two popular lightweight linear diffusion layer choices - bit permutations and MixColumns using almost-maximum-distance-separable (almost-MDS) matrices. We finally illustrate design paradigms that combine the aforementioned TI circuits for S-Boxes and diffusion layers to obtain fully side-channel secure SPN block cipher implementations with low area and power requirements.

Key-Alternating Feistel (KAF) ciphers, a.k.a. Feistel-2 models, refer to Feistel networks with round functions of the form $F_i(k_i\oplus x_i)$, where $k_i$ is the (secret) round-key and $F_i$ is a public random function. This model roughly captures the structures of many famous Feistel ciphers, and the most prominent instance is DES. Existing provable security results on KAF assumed independent round-keys and round functions (ASIACRYPT 2004 & FSE 2014). In this paper, we investigate how to achieve security under simpler and more realistic assumptions: with round-keys derived from a short main-key, and hopefully with identical round functions. For birthday-type security, we consider 4-round KAF, investigate the minimal conditions on the way to derive the four round-keys, and prove that when such adequately derived keys and the same round function are used, the 4-round KAF is secure up to $2^{n/2}$ queries. For beyond-birthday security, we focus on 6-round KAF. We prove that when the adjacent round-keys are independent, and independent round-functions are used, the 6 round KAF is secure up to $2^{2n/3}$ queries. To our knowledge, this is the first beyond-birthday security result for KAF without assuming completely independent round-keys. Our results hold in the multi-user setting as well, constituting the first non-trivial multi-user provable security results on Feistel ciphers. We finally demonstrate applications of our results on designing key-schedules and instantiating keyed sponge constructions.

Cube-attack-like cryptanalysis on round-reduced Keccak was proposed by Dinur et al. at EUROCRYPT 2015. It recovers the key through two phases: the preprocessing phase for precomputing a look-up table and online phase for querying the output and getting the cube sum with which the right key can be retrieved by looking up the precomputed table. It was shown that such attacks are efficient specifically for Keccak-based constructions with small nonce or message block size. In this paper, we provide a mixed integer linear programming (MILP) model for cube-attack-like cryptanalysis on keyed Keccak, which does not impose any unnecessary constraint on cube variables and finds almost optimal cubes by balancing the two phases of cube-attack-like cryptanalysis. Our model is applied to Ketje Jr, Ketje Sr, a Xoodoo-based authenticated encryption and Keccak-MAC-512, all of which have a relatively small nonce or message block size. As a result, time complexities of 5-round attacks on Ketje Jr and 7-round attacks on Ketje Sr can be improved significantly. Meanwhile, 6-round attacks, one more round than the previous best attack, are possible if the key size of Ketje V1 (V2) is reduced to 72 (80) bits. For Xoodoo-based AE in Ketje style, the attack reaches 6 rounds. Additionally, a 7-round attack of Keccak-MAC-512 is achieved. To verify the correctness of our attacks, a 5-round attack on Ketje V1 is implemented and tested practically. It is noted that this work does not threaten the security of any Keccak-based construction.

In the present paper we introduce some sufficient conditions and a procedure for checking whether, for a given function, CCZ-equivalence is more general than EA-equivalence together with taking inverses of permutations. It is known from Budaghyan, Carlet and Pott (2006) and Budaghyan, Carlet and Leander (2009) that for quadratic APN functions (both monomial and polynomial cases) CCZ-equivalence is more general. We prove hereby that for non-quadratic APN functions CCZ-equivalence can be more general (by studying the only known APN function which is CCZ-inequivalent to both power functions and quadratics). On the contrary, we prove that for pawer no-Gold APN functions, CCZ equivalence coincides with EA-equivalence and inverse transformation for $n\le 8$. We conjecture that this is true for any $n$.

This article presents universal forgery and multiple forgeries against MergeMAC that has been recently proposed to fit scenarios where bandwidth is limited and where strict time constraints apply. MergeMAC divides an input message into two parts, $m\|\tilde{m}$, and its tag is computed by $\mathcal{F}( \mathcal{P}_1(m) \oplus \mathcal{P}_2(\tilde{m}) )$, where $\mathcal{P}_1$ and $\mathcal{P}_2$ are PRFs and $\mathcal{F}$ is a public function. The tag size is 64 bits. The designers claim $64$-bit security and imply a risk of accepting beyond-birthday-bound queries. This paper first shows that it is inevitable to limit the number of queries up to the birthday bound, because a generic universal forgery against CBC-like MAC can be adopted to MergeMAC. Afterwards another attack is presented that works with a very few number of queries, 3 queries and $2^{58.6}$ computations of $\mathcal{F}$, by applying a preimage attack against weak $\mathcal{F}$, which breaks the claimed security. The analysis is then generalized to a MergeMAC variant where $\mathcal{F}$ is replaced with a one-way function $\mathcal{H}$. Finally, multiple forgeries are discussed in which the attacker's goal is to improve the ratio of the number of queries to the number of forged tags. It is shown that the attacker obtains tags of $q^2$ messages only by making $2q-1$ queries in the sense of existential forgery, and this is tight when $q^2$ messages have a particular structure. For universal forgery, tags for $3q$ arbitrary chosen messages can be obtained by making $5q$ queries.

Length doublers are cryptographic functions that transform an n-bit cryptographic primitive into an efficient and secure cipher that length-preservingly encrypts strings of length in [n,2n-1]. All currently known constructions are only proven secure up to the birthday bound, and for all but one construction this bound is known to be tight. We consider the remaining candidate, LDT by Chen et al.(ToSC 2017(3)), and prove that it achieves beyond the birthday bound security for the domain [n,3n/2). We generalize the construction to multiple rounds and demonstrate that by adding one more encryption layer to LDT, beyond the birthday bound security can be achieved for all strings of length in [n,2n-1]: security up to around 2^{2n/3} for the encryption of strings close to n and security up to around 2^{n} for strings of length close to 2n. The security analysis of both schemes is performed in a modular manner through the introduction and analysis of a new concept called ``harmonic permutation primitives.''

Low Entropy Masking Scheme (LEMS) has attracted wide attention for its low-cost feature of small fixed mask sets in Side-Channel-Analysis (SCA). To achieve the expected side channel security, it is necessary to find a balanced mask set to reduce the correlations between key dependent variables and their corresponding leakages. However, the security proof of LEMS, based on an inadequate assumption, might lead to consequent mask sets proposed without balance property, which could cause vulnerable LEMS implementations. This paper focusing on correcting and improving this scheme, first gives the formal definitions of univariate balance property on mask sets and extends it to multivariate settings. From these definitions, we propose three fundamental properties to analyze the balance of mask sets in Rotating Sbox Masking (RSM), the most popular LEMS implementations. To demonstrate the definitions and properties, three state-of-the-art RSM mask sets were selected as research objects. The corresponding attacks when any properties violated distinctly indicate the necessity of evaluating the balance property of the mask set in advance (during the design phase). However, it is found impossible to get a mask set for the RSM with all three properties satisfied, which means the vulnerabilities of RSM scheme in its unbalanced mask set are unavoidable. Thus, this promising masking scheme may be broken for its unqualified mask set.

Reduced-round AES has been a popular underlying primitive to design new cryptographic schemes and thus its security including distinguishing properties deserves more attention. At Crypto'16, a key-dependent integral distinguisher on 5-round AES was put forward, which opened up a new direction to take more insights into the distinguishing properties of AES. After that, two key-dependent impossible differential (ID) distinguishers on 5-round AES were proposed at FSE'16 and CT-RSA'18, respectively. It is strange that the current key-dependent integral distinguisher requires significantly higher complexities than the key-dependent ID distinguishers, even though they are constructed with the same property of MixColumns ($2^{128} \gg 2^{98.2}$). Proposers of the 5-round key-dependent distinguishers claimed that the corresponding integral and ID distinguishers can only work under chosen-ciphertext and chosen-plaintext settings, respectively, which is very different from the situations of traditional key-independent distinguishers. In this paper, we first construct a novel key-dependent integral distinguisher on 5-round AES with $2^{96}$ chosen plaintexts, which is much better than the previous key-dependent integral distinguisher that requires the full codebook proposed at Crypto'16. Secondly, we show that both distinguishers are valid under either chosen-plaintext setting or chosen-ciphertext setting, which is different from the claims of previous cryptanalysis. However, under different settings, complexities of key-dependent integral distinguishers are very different while those of the key-dependent ID distinguishers are almost the same. We analyze the reasons for it.

Deoxys is a third-round candidate of the CAESAR competition. This paper presents the first impossible differential cryptanalysis of Deoxys-BC-256 which is used in Deoxys as an internal tweakable block cipher. First, we find a 4.5-round ID characteristic by utilizing a miss-in-the-middle-approach. We then present several cryptanalyses based upon the 4.5 rounds distinguisher against round-reduced Deoxys-BC-256 in both single-key and related-key settings. Our contributions include impossible differential attacks on up to 8-rounds Deoxys-BC-256 in the tweak-key model which is, to the best of our knowledge, the first independent investigation of the security of Deoxys-BC-256 in the single-key model. Our attack reaches 9 rounds in the related-key related-tweak model which has a slightly higher data complexity than the best previous results obtained by a rectangle attack presented at FSE 2018 but requires a lower memory complexity with an equal time complexity.

In an order-preserving encryption scheme, the encryption algorithm produces ciphertexts that preserve the order of their plaintexts. Order-preserving encryption schemes have been studied intensely in the last decade, and yet not much is known about the security of these schemes. Very recently, Boneh et al. (Eurocrypt 2015) introduced a generalization of order-preserving encryption, called order-revealing encryption, and presented a construction which achieves this notion with best-possible security. Because their construction relies on multilinear maps, it is too impractical for most applications and therefore remains a theoretical result. In this work, we build efficiently implementable order-revealing encryption from pseudorandom functions. We present the first efficient order-revealing encryption scheme which achieves a simulation-based security notion with respect to a leakage function that precisely quantifies what is leaked by the scheme. In fact, ciphertexts in our scheme are only about 1.6 times longer than their plaintexts. Moreover, we show how composing our construction with existing order-preserving encryption schemes results in order-revealing encryption that is strictly more secure than all preceding order-preserving encryption schemes.

In this article, we propose a new method to protect block cipher implementations against Differential Fault Attacks (DFA). Our strategy, so-called ``Tweak-in-Plaintext'', ensures that an uncontrolled value (`tweak-in') is inserted into some part of the block cipher plaintext, thus effectively rendering DFA much harder to perform. Our method is extremely simple yet presents many advantages when compared to previous solutions proposed at AFRICACRYPT 2010 or CARDIS 2015. Firstly, we do not need any Tweakable block cipher, nor any related-key security assumption (we do not perform any re-keying). Moreover, performance for lightweight applications is improved, and we do not need to send any extra data. Finally, our scheme can be directly used with standard block ciphers such as AES or PRESENT. Experimental results show that the throughput overheads, for incorporating our scheme into AES-128, range between $\approx$ 5\% to $\approx$ 26.9\% for software, and between $\approx$ 3.1\% to $\approx$ 25\% for hardware implementations; depending on the tweak-in size.