Order-revealing encryption (ORE) is a popular primitive for outsourcing encrypted databases, as it allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.

The division property method is a technique to determine integral distinguishers on block ciphers. While the complexity of finding these distinguishers is higher, it has recently been shown that MILP and SAT solvers can efficiently find such distinguishers. In this paper, we provide a framework to automatically find those distinguishers which solely requires a description of the cryptographic primitive. We demonstrate that by finding integral distinguishers for 30 primitives with different design strategies. We provide several new or improved bit-based division property distinguishers for ChaCha, Chaskey, DES, GIFT, LBlock, Mantis, Qarma, RoadRunner, Salsa and SM4. Furthermore, we present an algorithm to find distinguishers with lower data complexity more efficiently.

Resistance against differential cryptanalysis is an important design criteria for any modern block cipher and most designs rely on finding some upper bound on probability of single differential characteristics. However, already at EUROCRYPT'91, Lai et al. comprehended that differential cryptanalysis rather uses differentials instead of single characteristics. In this paper, we consider exactly the gap between these two approaches and investigate this gap in the context of recent lightweight cryptographic primitives. This shows that for many recent designs like Midori, Skinny or Sparx one has to be careful as bounds from counting the number of active S-boxes only give an inaccurate evaluation of the best differential distinguishers. For several designs we found new differential distinguishers and show how this gap evolves. We found an 8-round differential distinguisher for Skinny-64 with a probability of $2^{-56.93}$, while the best single characteristic only suggests a probability of $2^{-72}$. Our approach is integrated into publicly available tools and can easily be used when developing new cryptographic primitives. Moreover, as differential cryptanalysis is critically dependent on the distribution over the keys for the probability of differentials, we provide experiments for some of these new differentials found, in order to confirm that our estimates for the probability are correct. While for Skinny-64 the distribution over the keys follows a Poisson distribution, as one would expect, we noticed that Speck-64 follows a bimodal distribution, and the distribution of Midori-64 suggests a large class of weak keys.

After the concept of a Fuzzy Extractor (FE) was rst introduced by Dodis et al. , it has been regarded as one of the candidate solutions for key management utilizing biometric data. With a noisy input such as biometrics, FE generates a public helper value and a random secret key which is reproducible given another input similar to the original input. However, "helper values" may cause some leakage of information when generated repeatedly by correlated inputs, thus reusability should be considered as an important property. Recently, Canetti et al. (Eurocrypt 2016) proposed a FE satisfying both reusability and robustness with inputs from low-entropy distributions. Their strategy, the so-called Sample-then-Lock method, is to sample many partial strings from a noisy input string and to lock one secret key with each partial string independently. In this paper, modifying this reusable FE, we propose a new FE with size-reduced helper data hiring a threshold scheme. Our new FE also satises both reusability and robustness, and requires much less storage memory than the original. To show the advantages of this scheme, we analyze and compare our scheme with the original in concrete parameters of the biometric, IrisCode. As a result, on 1024-bit inputs, with false rejection rate 0.5 and error tolerance 0.25, while the original requires about 1TB for each helper value, our scheme requires only 300MB with an additional 1.35GB of common data which can be used for all helper values.

Optimizing performance of Fully Homomorphic Encryption (FHE) is nowadays an active trend of research in cryptography. One way of improvement is to use a hybrid construction with a classical symmetric encryption scheme to transfer encrypted data to the Cloud. This allows to reduce the bandwidth since the expansion factor of symmetric schemes (the ratio between the ciphertext and the plaintext length) is close to one, whereas for FHE schemes it is in the order of 1,000 to 1,000,000. However, such a construction requires the decryption circuit of the symmetric scheme to be easy to evaluate homomorphically. Several works have studied the cost of homomorphically evaluating classical block ciphers, and some recent works have suggested new homomorphic oriented constructions of block ciphers or stream ciphers. Since the multiplication gate of FHE schemes significantly increases the noise of the ciphertext, we cannot afford too many multiplication stages in the decryption circuit. Consequently, FHE-friendly symmetric encryption schemes have a decryption circuit with small multiplication depth. We aim at minimizing the cost of the homomorphic evaluation of the decryption of symmetric encryption schemes. To do so, we focus on schemes based on learning problems: Learning With Errors (LWE), Learning Parity with Noise (LPN) and Learning With Rounding (LWR). We show that they have lower multiplicative depth than usual block ciphers, and hence allow more FHE operations before a heavy bootstrapping becomes necessary. Moreover, some of them come with a security proof. Finally, we implement our schemes in HElib. Experimental evidence shows that they achieve lower amortized and total running time than previous performance from the literature: our schemes are from 10 to 10,000 more efficient for the time per bit and the total running time is also reduced by a factor between 20 to 10,000. Of independent interest, the security of our LWR-based scheme is related to LWE and we provide an efficient security proof that allows to take smaller parameters.

At Indocrypt 2016, Ashur et al. showed that linear hulls are sometimes formed in a single round of a cipher (exemplifying on Simon ciphers) and showed that the success rate of an attack may be influenced by the quality of the estimation of one-round correlations. This paper improves the understanding regarding one-round linear hulls and trails, being dedicated to the study of one-round linear hulls of the DES cipher, more exactly of its $f$-function. It shows that, in the case of DES, the existence of one-round hulls is related to the number of active Sboxes and its correlation depends on a fixed set of key bits. All the ideas presented in this paper are followed by examples and are verified experimentally.

The Advanced Encryption Standard (AES) is one of the most studied symmetric encryption schemes. During the last years, several attacks have been discovered in different adversary models. In this paper, we focus on related-key differential attacks, where the adversary may introduce differences in plaintext pairs and also in keys. We show that Constraint Programming (CP) can be used to model these attacks, and that it allows us to efficiently find all optimal related-key differential characteristics for AES-128, AES-192 and AES-256. In particular, we improve the best related-key differential for the whole AES-256 and give the best related-key differential on 10 rounds of AES-192, which is the differential trail with the longest path. Those results allow us to improve existing related-key distinguishers, basic related-key attacks and $q$-multicollisions on AES-256.

Recently, the Boomerang Connection Table was introduced by Cid et al. as a tool to better evaluate the probability of a boomerang distinguisher. To compute the BCT of an $n$-bit to $n$-bit S-box, the inventors of the BCT proposed an algorithm that takes $O(2^{3n})$ time. We show that one can construct the same table in only $O(2^{2n})$ time.

The ARM TrustZone is a security extension which is used in recent Samsung flagship smartphones to create a Trusted Execution Environment (TEE) called a Secure World, which runs secure processes (Trustlets). The Samsung TEE includes cryptographic key storage and functions inside the Keymaster trustlet. The secret key used by the Keymaster trustlet is derived by a hardware device and is inaccessible to the Android OS. However, the ARM32 AES implementation used by the Keymaster is vulnerable to side channel cache-attacks. The Keymaster trustlet uses AES-256 in GCM mode, which makes mounting a cache attack against this target much harder. In this paper we show that it is possible to perform a successful cache attack against this AES implementation, in AES-256/GCM mode, using widely available hardware. Using a laptop's GPU to parallelize the analysis, we are able to extract a raw AES-256 key with 7 minutes of measurements and under a minute of analysis time and an AES-256/GCM key with 40 minutes of measurements and 30 minutes of analysis.

Substitution Boxes (S-Boxes) are crucial components in the design of many symmetric ciphers. The security of these ciphers against linear, differential, algebraic cryptanalyses and side-channel attacks is then strongly dependent on the choice of the S-Boxes. To construct S-Boxes having good resistive properties both towards classical cryptanalysis as well side-channel attacks is not a trivial task. In this article we propose new methods for generating S-Boxes with strong cryptographic properties and therefore study the resilience of such S-Boxes against side-channel attacks in terms of its theoretical metrics and masking possibility.

In this work, we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of DDT-equivalence which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion to what we call the $\gamma$-equivalence, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions, demonstrate that the number of DDT- or $\gamma$-equivalent functions is invariant under EA- and CCZ-equivalence and provide an algorithm for computing the DDT-equivalence and the $\gamma$-equivalence classes of a given function. We study the sizes of these classes for some families of Sboxes. Finally, we prove a result that shows that the rows of the DDT of an APN permutation are pairwise distinct.

In this paper we proposed an ultra-lightweight cipher GRANULE. It is based on Feistel network which encrypts 64 bits of data with 80/128 bits of key. GRANULE needs very less memory space as compared to existing lightweight ciphers .GRANULE needs 1288 GEs for 80 bit and 1577 GEs for 128 bit key size. It also shows good resistance against linear and differential cryptanalysis. GRANULE needs very small footprint area and provides robust secure design which thwart attacks like biclique attack, zero correlation attack, meet in the middle attack ,key schedule attack and key collision attack. GRANULE is having a strong S-box which is the key designing aspect in any cipher design. In this paper GRANULE is proposed with 32 rounds which are enough to provide resistance against all possible types of attacks. GRANULE consumes very less power as compared to other modern lightweight ciphers. We believe GRANULE cipher is the best suited cipher for providing robust security in applications like IoT.

In a functional encryption scheme, secret keys are associated with functions and ciphertexts are associated with messages. Given a secret key for a function f, and a ciphertext for a message x, a decryptor learns f(x) and nothing else about x. Inner product encryption is a special case of functional encryption where both secret keys and ciphertext are associated with vectors. The combination of a secret key for a vector x and a ciphertext for a vector y reveal <x, y> and nothing more about y. An inner product encryption scheme is function- hiding if the keys and ciphertexts reveal no additional information about both x and y beyond their inner product. In the last few years, there has been a flurry of works on the construction of function-hiding inner product encryption, starting with the work of Bishop, Jain, and Kowalczyk (Asiacrypt 2015) to the more recent work of Tomida, Abe, and Okamoto (ISC 2016). In this work, we focus on the practical applications of this primitive. First, we show that the parameter sizes and the run-time complexity of the state-of-the-art construction can be further reduced by another factor of 2, though we compromise by proving security in the generic group model. We then show that function privacy enables a number of applications in biometric authentication, nearest-neighbor search on encrypted data, and single-key two-input functional encryption for functions over small message spaces. Finally, we evaluate the practicality of our encryption scheme by implementing our function-hiding inner product encryption scheme. Using our construction, encryption and decryption operations for vectors of length 50 complete in a tenth of a second in a standard desktop environment.

Rank estimation is an important tool for a side-channel evaluations laboratories. It allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over $d$ subkeys (usually key bytes). These estimations are particularly useful where the key is not reachable with exhaustive search. We propose a new method called PRank for rank estimation, that is conceptually simple, and more time and memory efficient than previous proposals. Our main idea is to bound each subkey distribution by a Pareto-like function: since these are analytical functions, we can then estimate the rank by a closed formula. We evaluated the performance of PRank through extensive simulations based on two real SCA data corpora, and compared it to the currently-best histogram-based algorithm. We show that PRank gives a good rank estimation with much improved time and memory efficiency, especially for large ranks: For ranks between $2^{80}-2^{100}$ PRank estimation is at most 10 bits above the histogram rank and for ranks beyond $2^{100}$ the PRank estimation is only 4 bits above the histogram rank---yet it runs faster, and uses negligible memory. PRank gives a new and interesting method to solve the rank estimation problem based on reduction to analytical functions and calculating one closed formula hence using negligible time and space.

In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to $2^{2n/3}$ queries, but there are no known attacks with less than $2^{n}$ queries. We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with $\mathcal{O}(2^{3n/4})$ queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above $2^n$, but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito. Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity $\tilde{\mathcal{O}}(2^{6n/7})$. As far as we know, this is the first attack with complexity below $2^n$ against a deterministic beyond-birthday-bound secure MAC. As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

In modern cryptography, block encryption is a fundamental cryptographic primitive. However, it is impossible for block encryption to achieve the same security as one-time pad. Quantum mechanics has changed the modern cryptography, and lots of researches have shown that quantum cryptography can outperform the limitation of traditional cryptography. This article proposes a new constructive mode for private quantum encryption, named $\mathcal{EHE}$, which is a very simple method to construct quantum encryption from classical primitive. Based on $\mathcal{EHE}$ mode, we construct a quantum block encryption (QBE) scheme from pseudorandom functions. If the pseudorandom functions are standard secure, our scheme is indistinguishable encryption under chosen plaintext attack. If the pseudorandom functions are permutation on the key space, our scheme can achieve perfect security. In our scheme, the key can be reused and the randomness cannot, so a $2n$-bit key can be used in exponential times of encryption, where the randomness will be refreshed in each time of encryption. Thus $2n$-bit key can perfectly encrypt $O(n2^n)$ qubits, and the perfect secrecy would not be broken if the $2n$-bit key is reused only exponential times. Comparing with quantum one-time pad (QOTP), our scheme can be the same secure as QOTP, and the secret key can be reused (no matter whether the eavesdropping exists or not). Thus, the limitation of perfectly secure encryption (Shannon's theory) is broken in the quantum setting. Moreover, our scheme can be viewed as a positive answer to an open problem in quantum cryptography ``how to unconditionally reuse or recycle the whole key of private-key quantum encryption". In order to physically implement the QBE scheme, we only need to implement two kinds of single-qubit gates (Pauli $X$ gate and Hadamard gate), so it is within reach of current quantum technology.

Post-quantum cryptography has drawn considerable attention from cryptologists on a global scale. At Asiacrypt 2017, Leander and May combined Grover's and Simon's quantum algorithms to break the FX-based block ciphers, which were introduced by Kilian and Rogaway to strengthen DES. In this study, we investigate the Feistel constructions using Grover's and Simon's algorithms to generate new quantum key-recovery attacks on different rounds of Feistel constructions. Our attacks require $2^{nr/4~-~3n/4}$ quantum queries to break an $r$-round Feistel construction. The time complexity of our attacks is less than that observed for quantum brute-force search by a factor of $2^{0.75n}$. When compared with the best classical attacks, i.e., Dinur \emph{et al.}'s attacks at CRYPTO 2015, the time complexity is reduced by a factor of $2^{0.5n}$ without incurring any memory cost.

At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition, with other operations, as a modular addition. The starting point of our paper is afollow up of these previous results: First, we have developped new algorithms that improve and generalize Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005,largely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction. We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes. We also propose a generic algorithm to solve the hidden shift problem in non-abelian groups. In order to verify the theoretical analysis we performed, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities. Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak, concluding that it does not seem to be efficient.

Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage-exploiting attacks, and will very likely to become a must-have property of all new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost’s scheme is constructed with a relatively inefficient public key cryptographic primitive, and has poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost’s scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost’s scheme. The experiment results show that both our schemes are highly efficient.

Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a $wn$-bit (tweakable) block cipher from $n$-bit public permutations. Many widely deployed block ciphers are part of this family and rely on very small public permutations. Surprisingly, this structure has seen little theoretical interest when compared with Feistel networks, another high-level structure for block ciphers. This paper extends the work initiated by Dodis et al. in three directions; first, we make SPNs tweakable by allowing keyed tweakable permutations in the permutation layer, and prove their security as tweakable block ciphers. Second, we prove beyond-the-birthday-bound security for $2$-round non-linear SPNs with independent S-boxes and independent round keys. Our bounds also tend towards optimal security $2^n$ (in terms of the number of threshold queries) as the number of rounds increases. Finally, all our constructions permit their security proofs in the multi-user setting. As an application of our results, SPNs can be used to build provably secure wide tweakable block ciphers from several public permutations, or from a block cipher. More specifically, our construction can turn two strong public $n$-bit permutations into a tweakable block cipher working on $wn$-bit blocks and using a $6n$-bit key and an $n$-bit tweak (for any $w\geq 2$); the tweakable block cipher provides security up to $2^{2n/3}$ adversarial queries in the random permutation model, while only requiring $w$ calls to each permutation and $3w$ field multiplications for each $wn$-bit block.

Like any other cryptanalytic attack, the success rate of a linear attack is expected to improve as more data becomes available. Bogdanov and Tischhauser (FSE 2013) made the rather surprising claim that the success rate of a linear attack may go down with increasing plaintext amount, after an optimal point. They supported this claim with experimental evidence by an attack on SmallPresent-20. Different explanations have been given to explain this surprising phenomenon. In this note, we give quantitative values regarding when this phenomenon can be observed. We conclude that it should not be an issue for attacks in practice except for those with a tiny bias.

This paper applies non-adaptive group testing to aggregate message authentication code (MAC) and introduces non-adaptive group-testing aggregate MAC. After formalization of its syntax and security requirements, simple and generic construction is presented, which can be applied to any aggregate MAC scheme formalized by Katz and Lindell in 2008. Then, two instantioations of the construction is presented. One is based on the aggregate MAC scheme by Katz and Lindell and uses addition for tag aggregate. The other uses cryptographic hashing for tag aggregate. Provable security of the generic construction and two instantiations are also discussed.

We present various differential fault attack schemes for the RECTANGLE-80 and demonstrate how initially we started from a 80-bit fault to a single word fault scheme. This was mainly due to a differential vulnerability in the S-box of RECTANGLE as a result of which the exhaustive search space for the key reduces from $2^{80}$ to $2^{32}$. We have also presented a key schedule attack that is a variant of the single fault scheme, exploiting the same vulnerability and reduces the search space to $2^{40}$. The paper concludes with the simulation results for the single word fault scheme followed by countermeasures.

Post-quantum cryptography has attracted much attention from worldwide cryptologists. In ISIT 2010, Kuwakado and Morii gave a quantum distinguisher with polynomial time against 3-round Feistel networks. However, generalized Feistel schemes (GFS) have not been systematically investigated against quantum attacks. In this paper, we study the quantum distinguishers about some generalized Feistel schemes. For $d$-branch Type-1 GFS (CAST256-like Feistel structure), we introduce ($2d-1$)-round quantum distinguishers with polynomial time. For $2d$-branch Type-2 GFS (RC6/CLEFIA-like Feistel structure), we give ($2d+1$)-round quantum distinguishers with polynomial time. Classically, Moriai and Vaudenay proved that a 7-round $4$-branch Type-1 GFS and 5-round $4$-branch Type-2 GFS are secure pseudo-random permutations. Obviously, they are no longer secure in quantum setting. Using the above quantum distinguishers, we introduce generic quantum key-recovery attacks by applying the combination of Simon's and Grover's algorithms recently proposed by Leander and May. We denote $n$ as the bit length of a branch. For $(d^2-d+2)$-round Type-1 GFS with $d$ branches, the time complexity is $2^{(\frac{1}{2}d^2-\frac{3}{2}d+2)\cdot \frac{n}{2}}$, which is better than the quantum brute force search (Grover search) by a factor $2^{(\frac{1}{4}d^2+\frac{1}{4}d)n}$. For $4d$-round Type-2 GFS with $2d$ branches, the time complexity is $2^{{\frac{d^2 n}{2}}}$, which is better than the quantum brute force search by a factor $2^{{\frac{3d^2 n}{2}}}$.

We provide a survey about generic attacks on cryptographic hash constructions including hash-based message authentication codes and hash combiners. We look into attacks involving iteratively evaluating identical mappings many times. The functional graph of a random mapping also involves iteratively evaluating the mapping. These attacks essentially exploit properties of the functional graph. We map the utilization space of those properties from numerous proposed known attacks, draw a comparison among classes of attacks about their advantages and limitations. We provide a systematic exposition of concepts of cycles, deep-iterate images, collisions and their roles in cryptanalysis of iterated hash constructions. We identify the inherent relationship between these concepts, such that case-by-case theories about them can be unified into one knowledge system, that is, theories on the functional graph of random mappings. We show that the properties of the cycle search algorithm, the chain evaluation algorithm and the collision search algorithm can be described based on statistic results on the functional graph. Thereby, we can provide different viewpoints to support previous beliefs on individual knowledge. In that, we invite more sophisticated analysis of the functional graph of random mappings and more future exploitations of its properties in cryptanalysis.

S-boxes are important parts of modern ciphers. To construct S-boxes having cryptographic parameters close to optimal is an unsolved problem at present time. In this paper some new methods for generating such S-boxes are introduced.

Offset Public Permutation Mode (OPP) by Granger et al. is a one-pass authenticated encryption scheme supporting associated data (AEAD scheme). Leveraging an error in analysis of the scheme, a chosen plaintext attack that creates a forgery was discovered. This attack makes no assumptions about the underlying tweakable blockcipher while having negligible complexity requirements and high probability of success. An implementation of the attack is also provided.

This paper presents MergeMAC, a MAC that is particularly suitable for environments with strict time requirements and extremely limited bandwidth. MergeMAC computes the MAC by splitting the message into two parts. We use a pseudorandom function (PRF) to map messages to random bit strings and then merge them with a very efficient keyless function. The advantage of this approach is that the outputs of the PRF can be cached for frequently needed message parts. We demonstrate the merits of MergeMAC for authenticating messages on the CAN bus where bandwidth is extremely limited and caching can be used to recover parts of the message counter instead of transmitting it. We recommend an instantiation of the merging function MERGE and analyze the security of our construction. Requirements for a merging function are formally defined and the resulting EUF-CMA security of MergeMAC is proven.

QARMA is a family of lightweight tweakable block ciphers, which is used to support a software protection feature in the ARMv8 architecture. In this paper, we study the security of QARMA family against the impossible differential attack. First, we generalize the concept of truncated difference. Then, based on the generalized truncated difference, we construct the first 6-round impossible differential dinstinguisher of QARMA. Using the 6-round distinguisher and the time-and-memory trade-off technique, we present 10-round impossible differential attack on QARMA. This attack requires $2^{119.3}$ (resp. $2^{237.3}$) encryption units, $2^{61}$ (resp. $2^{122}$) chosen plaintext and $2^{72}$ 72-bit (resp. $2^{144}$ 144-bit) space for QARMA-64 (resp. QARMA-128). Further, if allowed with higher memory complexity (about $2^{116}$ 120-bit and $2^{232}$ 240-bit space for QARMA-64 and QARMA-128, respectively), our attack can break up 11 rounds of QARMA. To the best of our knowledge, these results are currently the best results with respect to attacked rounds.

We define a new mode of operation for block ciphers which in addition to providing confidentiality also ensures message integrity. In contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (MAC). The new mode of operation, called Integrity Aware Parallelizable Mode (IAPM), requires a total of m+1 block cipher evaluations on a plain-text of length m blocks. For comparison, the well known CBC (cipher block chaining) encryption mode requires m block cipher evaluations, and the second pass of computing the CBC-MAC essentially requires additional m+1 block cipher evaluations. As the name suggests, the new mode is also highly parallelizable.

AEGIS is an authenticated cipher introduced at SAC 2013, which takes advantage of AES-NI instructions to reach outstanding speed in software. Like LEX, Fides, as well as many sponge-based designs, AEGIS leaks part of its inner state each round to form a keystream. In this paper, we investigate the existence of linear biases in this keystream. Our main result is a linear mask with bias $2^{-89}$ on the AEGIS-256 keystream. The resulting distinguisher can be exploited to recover bits of a partially known message encrypted $2^{188}$ times, regardless of the keys used. We also consider AEGIS-128, and find a surprising correlation between ciphertexts at rounds $i$ and $i+2$, although the biases would require $2^{140}$ data to be detected. Due to their data requirements, neither attack threatens the practical security of the cipher.

JAMBU is an AEAD mode of operation which entered the third round of CAESAR competition. However, it does not have a security proof like other modes of operation do, and there was a cryptanalysis result that has overthrown the security claim under nonce misuse case by the designers. In this paper, we complement the shortage of the scheme by giving security proofs of JAMBU both under nonce respecting case and nonce misuse case. We prove that JAMBU under nonce respecting case has a slightly lower security than the birthday bound of $n$ bits, and JAMBU under nonce misuse case has a tight security bound of $n/2$ bits.

BRW-polynomial function is suggested as a preferred alternative of polynomial function, owing to its high efficiency and seemingly non-existent weak keys. In this paper we investigate the weak-key issue of BRW-polynomial function as well as BRW-instantiated cryptographic schemes. Though, in BRW-polynomial evaluation, the relationship between coefficients and input blocks is indistinct, we give out a recursive algorithm to compute another $(2^{v+1}-1)$-block message, for any given $(2^{v+1}-1)$-block message, such that their output-differential through BRW-polynomial evaluation, equals any given $s$-degree polynomial, where $v\ge\lfloor\log_2(s+1)\rfloor$. With such algorithm, we illustrate that any non-empty key subset is a weak-key class in BRW-polynomial function. Moreover any key subset of BRW-polynomial function, consisting of at least $2$ keys, is a weak-key class in BRW-instantiated cryptographic schemes like the Wegman-Carter scheme, the UHF-then-PRF scheme, DCT, etc. Especially in the AE scheme DCT, its confidentiality, as well as its integrity, collapses totally, when using weak keys of BRW-polynomial function, which are ubiquitous.

MDS matrices are an important element for the design of block ciphers such as the AES. In recent years, there has been a lot of work on the construction of MDS matrices with a low implementation cost, in the context of lightweight cryptography. Most of the previous efforts focused on local optimization, constructing MDS matrices with coefficients that can be efficiently computed. In particular, this led to a matrix with a direct xor count of only 106, while a direct implementation of the MixColumn matrix of the AES requires 152 bitwise xors. More recently, techniques based on global optimization have been introduced, were the implementation can reuse some intermediate variables. In particular, Kranz \emph{et al.} used optimization tools to a find good implementation from the description of an MDS matrix. They have lowered the cost of implementing the MixColumn matrix to 97 bitwise xors, and proposed a new matrix with only 72 bitwise xors, the lowest cost known so far. In this work we propose a different approach to global optimization. Instead of looking for an optimized circuit of a given matrix, we run a search through a space of circuits, to find optimal circuits yielding MDS matrices. This results in MDS matrices with an even lower cost, with only 67 bitwise xors.

This paper investigates the security of the KTANTAN block cipher against differential fault analysis. This attack is considered to be first side channel analysis of KTANTAN in the literature. KTANTAN is a relative to the KATAN block cipher. Therefore, the previous fault analysis on KATAN family of block cipher is revisited. Similar to KATAN, KTANTAN has three variants namely KTANTAN32, KTANTAN48 and KTANTAN64. The inner structure of KTANTAN is similar to KATAN except the key schedule algorithms. KATAN has been practically broken by using fault analysis, employing a transient single-bit fault model, with the assumption is that the attacker is able to inject faults randomly into the internal state of the cipher. The attack is empowerd by extended cube method similarly as applied on KATAN. The complexity of this attack is $2^{74}$ for KTANTAN32 and $2^{76}$ for both KTANTAN48 and KTANTAN64. Furthermore, based on the obtained results, this paper concludes that KTANTAN is more robust against fault analysis compared to KATAN.

Masking schemes represent a well-researched and successful option to follow when considering side-channel countermeasures. Still, such measures increase the implementation cost in term of power consumption, clock cycles, and random numbers generation. In fact, the higher the order of protection against side-channel adversaries, the higher the implementation cost of countermeasures. S-boxes represent the most vulnerable part in an implementation when considering side-channel adversary. In this paper, we investigate how to generate S-boxes that have improved resilience against varying orders of side-channel attacks while minimising the implementation costs. We examine whether S-boxes generated against a certain order of attack also represent a good solution when considering different order of attacks. We demonstrate that we successfully generated S-boxes resilient against a certain physical attack order but the improvements are small. As a result, S-boxes that are resilient against first order attacks stay resilient against higher-order attacks, which saves computational power during the design of higher-order side-channel attacks resilient S-boxes.

Lightweight block ciphers rely on simple operations to allow compact implementation. Thanks to its efficiency, bit permutation has emerged as an optimal choice for state-wise diffusion. It can be implemented by simple wiring or shifts. However, as recently shown by Spectre and Meltdown attacks, efficiency and security often go against each other. In this work, we show how bit permutations introduce a side-channel vulnerability that can be exploited to extract the secret key from the cipher. Such vulnerabilities are specific to bit permutations and do not occur in other state-wise diffusion alternatives. We propose Side-Channel Assisted Differential-Plaintext Attack (SCADPA) which targets this vulnerability in bit permutation operation. SCADPA is experimentally demonstrated on PRESENT-80 on an 8-bit microcontroller, with the best case key recovery in 17 encryptions. The attack is then extended to latest bit-permutation based cipher GIFT, allowing full key recovery in 36 encryptions. We also propose and experimentally verify an automatic threshold method which can be easily applied to SCADPA, allowing automation of the attack. Moreover, SCADPA on bit permutations has other applications. Application for reverse engineering secret sboxes in PRESENT-like proprietary ciphers is shown. We also highlight a special case, where fixing one vulnerability opens another one. This is shown by applying SCADPA on some assembly level fault attack countermeasures, rendering it less secure than unprotected implementations. Lastly, we also provide several different attack scenarios, such as targeting different encryption modes.

A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in the original message, or in an unrelated message. We consider the simplest possible construction in the computational split-state model, which simply encodes a message $m$ as $k||E_k(m)$ for a uniformly random key $k$, where $E$ is a block cipher. This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS 2016), who eschewed this simple scheme in fear of related-key attacks on $E$. In this work, we prove this construction to be a strong non-malleable code as long as $E$ is: (i) a pseudorandom permutation under leakage and (ii) related-key secure with respect to an arbitrary but fixed key relation. Both properties are believed to hold for "good" block ciphers, such as AES-128, making this non-malleable code very efficient with short codewords of length $|m| + 2\tau$ (where $\tau$ is the security parameter, e.g., 128 bits), without significant security penalty.

Cellular Automata (CA) represent an interesting approach to design Substitution Boxes (S-boxes) having good cryptographic properties and low implementation costs. From the cryptographic perspective, up to now there have been only ad-hoc studies about specific kinds of CA, the best known example being the $\chi$ nonlinear transformation used in Keccak. In this paper, we undertake a systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on their nonlinearity and differential uniformity. Next, we extend some previous published results about the construction of CA-based S-boxes by means of a heuristic technique, namely Genetic Programming (GP). In particular, we propose a "reverse engineering" method based on De Bruijn graphs to determine whether a specific S-box is expressible through a single CA rule. Then, we use GP to assess if some CA-based S-box with optimal cryptographic properties can be described by a smaller CA. The results show that GP is able to find much smaller CA rules defining the same reference S-boxes up to size $7\times 7$, suggesting that our method could be used to find more efficient representations of CA-based S-boxes for hardware implementations. Finally, we classify up to affine equivalence all $3\times 3$ and $4\times 4$ CA-based S-boxes.

In this paper, we study experimental cube attacks against Trivium-like ciphers and we focus on improving nonlinear superpolies recovery. We first present a general framework in cube attacks to test nonlinear superpolies, by exploiting a kind of linearization technique. It worth noting that, in the new framework, the complexities of testing and recovering nonlinear superpolies are almost the same as those of testing and recovering linear superpolies. To demonstrate the effectiveness of our new attack framework, we do extensive experiments on Trivium, Kreyvium, and TriviA-SC-v2 respectively. We obtain several linear and quadratic superpolies for the 802-round Trivium, which is the best experimental results against Trivium regarding the number of initialization rounds. For Kreyvium, it is shown that the probability of finding a quadratic superpoly using the new framework is twice as large as finding a linear superpoly. Hopefully, this new framework would provide some new insights on cube attacks against NFSR-based ciphers, and in particular make nonlinear superpolies potentially useful in the future cube attacks.

The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks $\sigma$ satisfies $\sigma \ll 2^{n/2}$), and a matching attack that can distinguish plaintext/ciphertext pairs from random using about $2^{n/2}$ blocks of data. The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity $\tilde{\mathcal{O}}(2^{n/2})$. This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message. To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required. As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity $\tilde{\mathcal{O}}(2^{2n/3})$.

In this paper we focus on S-box constructions. We consider the uniformity property of an S-box which plays an important role in Threshold Implementations (TI). Most papers so far have studied TI sharings for given S-boxes. We proceed in the opposite way: starting from $n$-bit S-boxes with known sharings we construct new $(n+1)$-bit S-boxes from them with the desired sharings. In addition, we investigate the self-equivalency of S-boxes and show some interesting properties.

A boomerang attack is a cryptanalysis framework that regards a block cipher $E$ as the composition of two sub-ciphers $E_1\circ E_0$ and builds a particular characteristic for $E$ with probability $p^2q^2$ by combining differential characteristics for $E_0$ and $E_1$ with probability $p$ and $q$, respectively. Crucially the validity of this figure is under the assumption that the characteristics for $E_0$ and $E_1$ can be chosen independently. Indeed, Murphy has shown that independently chosen characteristics may turn out to be incompatible. On the other hand, several researchers observed that the probability can be improved to $p$ or $q$ around the boundary between $E_0$ and $E_1$ by considering a positive dependency of the two characteristics, e.g.~the ladder switch and S-box switch by Biryukov and Khovratovich. This phenomenon was later formalised by Dunkelman et al.~as a sandwich attack that regards $E$ as $E_1\circ E_m \circ E_0$, where $E_m$ satisfies some differential propagation among four texts with probability $r$, and the entire probability is $p^2q^2r$. In this paper, we revisit the issue of dependency of two characteristics in $E_m$, and propose a new tool called Boomerang Connectivity Table (BCT), which evaluates $r$ in a systematic and easy-to-understand way when $E_m$ is composed of a single S-box layer. With the BCT, previous observations on the S-box including the incompatibility, the ladder switch and the S-box switch are represented in a unified manner. Moreover, the BCT can detect a new switching effect, which shows that the probability around the boundary may be even higher than $p$ or $q$. To illustrate the power of the BCT-based analysis, we improve boomerang attacks against Deoxys-BC, and disclose the mechanism behind an unsolved probability amplification for generating a quartet in SKINNY. Lastly, we discuss the issue of searching for S-boxes having good BCT and extending the analysis to modular addition.

We study instantiating the random permutation of the block-cipher mode of operation IAPM (Integrity-Aware Parallelizable Mode) with the public random permutation of Keccak, on which the draft standard SHA-3 is built. IAPM and the related mode OCB are single-pass highly parallelizable authenticated-encryption modes, and while they were originally proven secure in the private random permutation model, Kurosawa has shown that they are also secure in the public random permutation model assuming the whitening keys are uniformly chosen with double the usual entropy. In this paper, we show a general composability result that shows that the whitening key can be obtained from the usual entropy source by a key-derivation function which is itself built on Keccak. We stress that this does not follow directly from the usual indifferentiability of key-derivation function constructions from Random Oracles. We also show that a simple and general construction, again employing Keccak, can also be used to make the IAPM scheme key-dependent-message secure. Finally, implementations on modern AMD-64 architecture supporting 128-bit SIMD instructions, and not supporting the native AES instructions, show that IAPM with Keccak runs three times faster than IAPM with AES.

We discuss the design rationale and analysis of the SIMON and SPECK lightweight block ciphers.

In this paper, we consider the indistinguishability of XTS in some security models for both full final block and partial final block cases. Firstly, some evaluations of the indistinguishability up-to-block are presented. Then, we present a new security model in which the adversary can not control sector number, based on an $\epsilon$-collision resistant function. In this model, we give a bound of the distinguishing advantage that the adversary can get when attacks on XTS. The received results is an extension of \cite{6}.

In this paper, we consider the implications of parallelizing time-memory tradeoff attacks using a large number of distributed processors. It is shown that Hellman’s original tradeoff method and the Biryukov-Shamir attack on stream ciphers, which incorporates data into the tradeoff, can be effectively distributed to reduce both time and memory, while other approaches are less advantaged in a distributed approach. Distributed tradeoff attacks are specifically discussed as applied to stream ciphers and the counter mode operation of block ciphers, where their feasibility is considered in relation to distributed exhaustive key search. In particular, for counter mode with an unpredictable initial count, we show that distributed tradeoff attacks are applicable, but can be made infeasible if the entropy of the initial count is at least as large as the key. In general, the analyses of this paper illustrate the effectiveness of a distributed tradeoff approach and show that, when enough processors are involved in the attack, it is possible some systems, such as lightweight cipher implementations, may be practically susceptible to attack.

In this paper we study the affine equivalence problem, where given two functions $\vec{F},\vec{G}: \{0,1\}^n \rightarrow \{0,1\}^n$, the goal is to determine whether there exist invertible affine transformations $A_1,A_2$ over $GF(2)^n$ such that $\vec{G} = A_2 \circ \vec{F} \circ A_1$. Algorithms for this problem have several well-known applications in the design and analysis of Sboxes, cryptanalysis of white-box ciphers and breaking a generalized Even-Mansour scheme. We describe a new algorithm for the affine equivalence problem and focus on the variant where $\vec{F},\vec{G}$ are permutations over $n$-bit words, as it has the widest applicability. The complexity of our algorithm is about $n^3 2^n$ bit operations with very high probability whenever $\vec{F}$ (or $\vec{G})$ is a random permutation. This improves upon the best known algorithms for this problem (published by Biryukov et al. at EUROCRYPT 2003), where the first algorithm has time complexity of $n^3 2^{2n}$ and the second has time complexity of about $n^3 2^{3n/2}$ and roughly the same memory complexity. Our algorithm is based on a new structure (called a \emph{rank table}) which is used to analyze particular algebraic properties of a function that remain invariant under invertible affine transformations. Besides its standard application in our new algorithm, the rank table is of independent interest and we discuss several of its additional potential applications.

We show how to build a binary matrix from the MRHS representation of a symmetric-key cipher. The matrix contains the cipher represented as an equation system and can be used to assess a cipher's resistance against algebraic attacks. We give an algorithm for solving the system and compute its complexity. The complexity is normally close to exhaustive search on the variables representing the user-selected key. Finally, we show that for some variants of LowMC, the joined MRHS matrix representation can be used to speed up regular encryption in addition to exhaustive key search.

This paper considers the security of the Offset Two-Round (OTR) authenticated encryption mode \cite{cryptoeprint:2013:628} with respect to forgery attacks. The current version of OTR gives a security proof for specific choices of the block size $(n)$ and the primitive polynomial used to construct the finite field $\mathbb{F}_{2^n}$. Although the OTR construction is generic, the security proof is not. For every choice of finite field the distinctness of masking coefficients must be verified to ensure security. In this paper, we show that some primitive polynomials result in collisions among the masking coefficients used in the current instantiation, from which forgeries can be constructed. We propose a new way to instantiate OTR so that the masking coefficients are distinct in every finite field $\mathbb{F}_{2^n}$, thus generalising OTR without reducing the security of OTR.

Keccak is the final winner of SHA-3 competition and it can be used as message authentic codes as well. The basic and balanced divide-and-conquer attacks on Keccak-MAC were proposed by Dinur et al. at Eurocrypt 2015. The idea of cube attacks is used in the two attacks to divide key bits into small portions. In this paper, by carefully analysing the mappings used in Keccak-MAC, it is found that some cube variables could divide key bits into smaller portions and so better divide-and-conquer attacks are obtained. Furthermore, in order to evaluate the resistance of Keccak-MAC against divide-and-conquer attacks based on cubes, we theoretically analyse the lower bounds of the complexities of divide-and-conquer attacks. It is shown that the lower bounds of the complexities are still not better than those of the conditional cube tester proposed by Senyang Huang et al.. This indicates that Keccak-MAC can resist the divide-and-conquer attack better than the conditional cube tester. We hope that these techniques still could provide some new insights on the future cryptanalysis of Keccak.

The purpose of the work is to estimate the resistance of lightweight block ciphers Speck, Simon, Simeck, HIGHT, LEA to a distinguishing attack. (This attack is a form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data.) Modern lightweight block ciphers must be designed to be immune to such an attack. It turned out that Speck, Simon, HIGHT and LEA showed a sufficient resistance to the distinguishing attack, but Simeck with 48-bit block size and 96-bit key size was not immune to this attack.

Masking is an effective countermeasure against side-channel attacks. In this paper, we improve the efficiency of the high-order masking of look-up tables countermeasure introduced at Eurocrypt 2014, based on a combination of three techniques, and still with a proof of security in the Ishai-Sahai-Wagner (ISW) probing model. The first technique consists in proving security under the stronger t-SNI definition, which enables to use n=t+1 shares instead of n=2t+1 against t-th order attacks. The second technique consists in progressively incrementing the number of shares within the countermeasure, from a single share to n, thereby reducing the complexity of the countermeasure. The third technique consists in adapting the common shares approach introduced by Coron et al. at CHES 2016, so that half of a randomized look-up table can be pre-computed for multiple SBoxes. When combined, our three techniques lead to a factor 10.7 improvement in efficiency, asymptotically for a large number of shares n. For a practical implementation with a reasonable number of shares, we get a 4.8 speed-up factor compared to the initial countermeasure for AES.

Lightweight cryptography has been one of the "hot topics" in symmetric cryptography in the recent years. A huge number of lightweight algorithms have been published, standardized and/or used in commercial products. In this paper, we discuss the different implementation constraints that a "lightweight" algorithm is usually designed to satisfy in both the software and the hardware case. We also present an extensive survey of all lightweight symmetric primitives we are aware of. It covers designs from the academic community, from government agencies and proprietary algorithms which were reverse-engineered or leaked. Relevant national (NIST...) and international (ISO/IEC...) standards are listed. We identified several trends in the design of lightweight algorithms, such as the designers' preference for ARX-based and bitsliced-S-Box-based designs or simpler key schedules. We also discuss more general trade-offs facing the authors of such algorithms and suggest a clearer distinction between two subsets of lightweight cryptography. The first, ultra-lightweight cryptography, deals with primitives fulfilling a unique purpose while satisfying specific and narrow constraints. The second is ubiquitous cryptography and it encompasses more versatile algorithms both in terms of functionality and in terms of implementation trade-offs.

In this paper, quantum attacks against symmetric-key schemes are presented in which adversaries only make classical queries but use quantum computers for offline computations. Our attacks are not as efficient as polynomial-time attacks making quantum superposition queries, while our attacks use the realistic model and overwhelmingly improve the classical attacks. Our attacks convert a type of classical meet-in-the-middle attacks into quantum ones. The attack cost depends on the number of available qubits and the way to realize the quantum hardware. The tradeoff between data complexity $D$ and time complexity $T$ against the problem of cardinality $N$ is $D^2 \cdot T^2 =N$ and $D \cdot T^6 = N^3$ in the best and worst case scenarios to the adversary respectively, while the classic attack requires $D\cdot T = N$. This improvement is meaningful from an engineering aspect because several existing schemes claim beyond-birthday-bound security for $T$ by limiting the maximum $D$ to be below $2^{n/2}$ according to the classical tradeoff $D\cdot T = N$. Those schemes are broken if quantum offline computations are performed by adversaries. The attack can be applied to many schemes such as a tweakable block-cipher construction TDR, a dedicated MAC scheme Chaskey, an on-line authenticated encryption scheme McOE-X, a hash function based MAC H$^2$-MAC and a permutation based MAC keyed-sponge. The idea is then applied to the FX-construction to discover new tradeoffs in the classical query model.

Algebraic analysis of block ciphers aims at finding the secret key by solving a collection of polynomial equations that describe the internal structure of a cipher for chosen observations of plaintext/ciphertext pairs. Although algebraic attacks are addressed for cryptanalysis of block and stream ciphers, there is a lack of understanding of the impact of algebraic representation of the cipher on efficiency of solving the resulting collection of equations. The work investigates different S-box representations and their effect on complexity of algebraic attacks. In particular, we observe that a S-box representation defined in the work as \textit{Forward-Backward} (FWBW) leads to a collection of equations that can be solved efficiently. We show that the $SR(10,2,1,4)$ cipher can be broken using standard algebra software \textsc{Singular} and FGb. This is the best result achieved so far. The effect of description of S-boxes for some light-weight block ciphers is investigated. A by-product of this result is that we have achieved some improvements on the algebraic cryptanalysis of LBlock, PRESENT and MIBS light-weight block ciphers. Our study and experiments confirms a counter-intuitive conclusion that algebraic attacks work best for the FWBW S-box representation. This contradicts a common belief that algebraic attacks are more efficient for quadratic S-box representation.

We will present here two new and simple theorems that show that when we compose permutation generators with independent keys, then the ``quality'' of CCA security increases. These theorems (Theorems 2 and 5 of this paper) are written in terms of H-coefficients (which are nothing else, up to some normalization factors, than transition probabilities). Then we will use these theorems on the classical analysis of Random Feistel Schemes (i.e. Luby-Rackoff constructions) and we will compare the results obtained with the bounds obtained with the coupling technique. Finally, we will show an interesting difference between 5 and 6 Random Feistel Schemes. With 5 rounds on $2n$ bits $\rightarrow 2n$ bits, when the number of $q$ queries satisfies $\sqrt{2^n} \ll q \ll 2^n$, we have some ``holes'' in the H-coefficient values, i.e. some H values are much smaller than the average value of H. This property for 5 rounds does not exist anymore on 6 rounds.

We study the security of symmetric encryption schemes in settings with multiple users and realistic adversaries who can adaptively corrupt encryption keys. To avoid confinement to any particular definitional paradigm, we propose a general framework for multi-key security definitions. By appropriate settings of the parameters of the framework, we obtain multi-key variants of many of the existing single-key security notions. This framework is instrumental in establishing our main results. We show that for all single-key secure encryption schemes satisfying a minimal key uniqueness assumption and almost any instantiation of our general multi-key security notion, any reasonable reduction from the multi-key game to a standard single-key game necessarily incurs a linear loss in the number of keys. We prove this result for all three classical single-key security notions capturing confidentiality, authenticity and the combined authenticated encryption notion.

The ultimate goal of designing a symmetric-key cryptographic primitive often can be formulated as an optimization problem. So far, these problems mainly have been solved with trivial algorithms such as brute force or random search. We show that a more advanced and equally versatile class of search algorithms, called metaheuristics, can help to tackle optimization problems related to design of symmetric-key primitives. We use two nature-inspired metaheuristics, simulated annealing and genetic algorithm, to optimize in terms of security the components of two recent cryptographic designs, SKINNY and AES-round based constructions. The positive outputs of the optimization suggest that metaheuristics are non-trivial tools, well suited for automatic design of primitives.

Nachef et al used differential cryptanalysis to study four types of Generalized Feistel Scheme (GFS). They gave the lower bound of maximum number of rounds that is indistinguishable from a random permutation. In this paper, we study the security of several types of GFS by exploiting the asymmetric property. We show that better lower bounds can be achieved for the Type-1 GFS, Type-3 GFS and Alternating Feistel Scheme. Furthermore, we give the first general results regarding to the lower bound of the Unbalanced Feistel Scheme.

This work studies the success probability of key recovery attacks based on using a single linear approximation. Previous works had analysed success probability under different hypotheses on the distributions of correlations for the right and wrong key choices. This work puts forward a unifying framework of general key randomisation hypotheses. All previously used key randomisation hypotheses as also zero correlation attacks can be seen to special cases of the general framework. Derivations of expressions for the success probability are carried out under both the settings of the plaintexts being sampled with and without replacements. Compared to previous analysis, we uncover several new cases which have not been considered in the literature. For most of the cases which have been considered earlier, we provide complete expressions for the respective success probabilities. Finally, the complete picture of the dependence of the success probability on the data complexity is revealed. Compared to the extant literature, our work provides a deeper and more thorough understanding of the success probability of single linear cryptanalysis.

The Competition for Authenticated Encryption: Security, Applicability and Robustness (CAESAR) has as its official goal to ``identify a portfolio of authenticated ciphers that offer advantages over AES-GCM and are suitable for widespread adoption.'' Each of the 15 candidate schemes competing in the currently ongoing 3rd round of CAESAR must clearly declare its security claims, i.a. whether or not it can tolerate nonce misuse, and what is the maximal data complexity for which security is guaranteed. These claims appear to be valid for all 15 candidates. Interpreting "Robustness" in CAESAR as the ability to mitigate damage even if security guarantees are void, we describe attacks with birthday complexity or beyond, and/or with nonce reuse for each of the 15 candidates. We then sort the candidates into classes depending on how powerful does an attacker need to be to mount (semi-)universal forgeries, decryption attacks, or key recoveries. Rather than invalidating the security claims of any of the candidates, our results provide an additional criterion for evaluating the security that candidates deliver, which can be useful for e.g. breaking ties in the final CAESAR discussions.

Time-memory-data tradeoff (TMD-TO) attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $n/2$, where $n$ denotes the inner state length of the underlying keystream generator. This implies that to withstand TMD tradeoff attacks, the state size should be at least double the key size. In 2015, Armknecht and Mikhalev introduced a new line of research, which pursues the goal of reducing the inner state size of lightweight stream ciphers below this boundary by deploying a key-dependent state update function in a Grain-like stream cipher. Although their design Sprout was broken soon after publication, it has raised interest in the design principle, and a number of related ciphers have been suggested since, including Plantlet, a follow-up of Sprout, and the cipher Fruit. In 2017, Hamann et al. showed that the initial hope of achieving full security against TMD-TO attacks by continuously using the secret key has failed. In particular, they demonstrated that there are generic distinguishing attacks against such ciphers with a complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, they came up with a new design idea for small-state stream ciphers, which is based on also continuously using the public IV as part of the state update. The authors conjectured that this design principle might allow to finally achieve full security against TMD-TO attacks. In this note, we take their idea one step further. While Hamann et al. aimed for improving the security of small-state stream ciphers that continuously use the secret key against distinguishing, we explain here that also other stream cipher constructions can benefit from continuously using the IV. In particular, our approach allows for thwarting the well-known TMD-TO inner state recovery attacks of Babbage and Biryukov and Shamir without using the secret key more than once.

Recently, a new template attack on the DES key scheduling was demonstrated that allows recovery of a sufficiently large portion of the DES key of a widely deployed certified smart card chip using a single EM (electromagnetic) trace during the Exploitation Phase. Firstly, in this paper we show how the results can be improved upon when combining them with the analysis of another leakage channel, the total Hamming distance. Remaining rest entropies as low as approx 13 bits have been found for some single-trace attacks, meaning that effectively 42 bits of a single-key DES were recovered in a single trace. The nature of single-trace attacks has it that conventional software countermeasures are rendered useless by this attack, and thus the only remaining remedy is a hardware redesign. Secondly, various brute-force search strategies are compared with each other and an extensive analysis of the statistics of the rest entropy is presented. The analysis is also extended to two-key TDES. Moreover, the amount of brute-force effort can be drastically reduced when having more than one trace available for the attack. Already as few as N=8 traces during the Exploitation Phase bring about a reduction of the average brute-force effort of the order of 10 bits for single DES, and 22 bits for two-key TDES. For N approx 100 we achieve an average brute-force effort of less than 50 bits for two-key TDES. Further analysis reveals that this attack is not equally strong for all DES keys, but that quite a number of weaker DES keys exist where the attack is much stronger. Naturally, any assessment of the severity of this attack will have to be made based on the weakest keys. [This last part constitutes an update to a previous version of this paper.]

In this paper, we introduce Farfalle, a new permutation-based construction for building a pseudorandom function (PRF). The PRF takes as input a key and a sequence of arbitrary-length data strings, and returns an arbitrary-length output. It has a compression layer and an expansion layer, each involving the parallel application of a permutation. The construction also makes use of LFSR-like rolling functions for generating input and output masks and for updating the inner state during expansion. On top of the inherent parallelism, Farfalle instances can be very efficient because the construction imposes less requirements on the underlying primitive than, e.g., the duplex construction or typical block cipher modes. Farfalle has an incremental property: compression of common prefixes of inputs can be factored out. Thanks to its input-output characteristics, Farfalle is really versatile. We specify simple modes on top of it for authentication, encryption and authenticated encryption, as well as a wide block cipher mode. As a showcase, we present Kravatte, a very efficient instance of Farfalle based on Keccak-p[1600] permutations and formulate concrete security claims against classical and quantum adversaries. The permutations in the compression and expansion layers of Kravatte have only 6 rounds apiece and the rolling functions are lightweight. We provide a rationale for our choices and report on software performance.

Bit permutations are a common choice for diffusion function in lightweight block ciphers, owing to their low implementation footprint. In this paper, we present a novel Side-Channel Assisted Differential-Plaintext Attack (SCADPA), exploiting specific vulnerabilities of bit permutations. SCADPA is a chosen-plaintext attack, knowledge of the ciphertext is not required. Unlike statistical methods, commonly used for distinguisher in standard power analysis, the proposed method is more differential in nature. The attack shows that diffusion layer can play a significant role in distinguishing the internal cipher state. We demonstrate how to practically exploit such vulnerability to extract the secret key. Results on microcontroller-based PRESENT-80 cipher lead to full key retrieval using as low as 17 encryptions. It is possible to automate the attack by using a thresholding method detailed in the paper. Several case studies are presented, using various attacker models and targeting different encryption modes (such as CTR and CBC). We provide a discussion on how to avoid such attack from the design point of view.

The inclusion of ChaCha20 and Poly1305 into the list of supported ciphers in TLS 1.3 necessitates a security evaluation of those ciphers with all the state-of-the-art tools and innovative cryptanalysis methodologies. Mixed Integer Linear Programming (MILP) has been successfully applied to find more accurate characteristics of several ciphers such as SIMON and SPECK. In our research, we use MILP-aided cryptanalysis to search for differential characteristics, linear approximations and integral properties of ChaCha. We are able to find differential trails up to 2 rounds and linear trails up to 1 round. However, no integral distinguisher has been found, even for 1 round.

We initiate the study of multi-user (mu) security of authenticated encryption (AE) schemes as a way to rigorously formulate, and answer, questions about the "randomized nonce" mechanism proposed for the use of the AE scheme GCM in TLS 1.3. We (1) Give definitions of mu ind (indistinguishability) and mu kr (key recovery) security for AE (2) Characterize the intent of nonce randomization as being improved mu security as a defense against mass surveillance (3) Cast the method as a (new) AE scheme RGCM (4) Analyze and compare the mu security of both GCM and RGCM in the model where the underlying block cipher is ideal, showing that the mu security of the latter is indeed superior in many practical contexts to that of the former, and (5) Propose an alternative AE scheme XGCM having the same efficiency as RGCM but better mu security and a more simple and modular design.

Authenticated ciphers rely on the uniqueness of the nonces to meet their security goals. In this work, we investigate the implications of reusing nonces for three third-round candidates of the ongoing CAESAR competition, namely Tiaoxin, AEGIS and MORUS. We show that an attacker that is able to force nonces to be reused can reduce the security of the ciphers with results ranging from full key-recovery to forgeries with practical complexity and a very low number of nonce-misuse queries.

We make a number of remarks about the AES-GCM-SIV nonce-misuse resistant authenticated encryption scheme currently considered for standardization by the Crypto Forum Research Group (CFRG). First, we point out that the security analysis proposed in the ePrint report 2017/168 is incorrect, leading to overly optimistic security claims. We correct the bound and re-assess the security guarantees offered by the scheme for various parameters. Second, we suggest a simple modification to the key derivation function which would improve the security of the scheme with virtually no efficiency penalty.

In SAC 2013, Berger et al. defined Extended Generalized Feistel Networks (EGFN) and analyzed their security. Later, they proposed a cipher based on this structure: LILLIPUT. Impossible differential attacks and integral attacks have been mounted on LILLIPUT. We propose a tool which has found some classical, impossible and improbable differential attacks by using the variance method. It has highlighted unusual differential conditions which lead to efficient attacks by the complexity. Moreover, it is the first time we apply the generic variance method to a concrete cipher.

We consider a recent security definition of Chenette, Lewi, Weis, and Wu for order-revealing encryption (ORE) and order-preserving encryption (OPE) (FSE 2016). Their definition says that the comparison of two ciphertexts should only leak the index of the most significant bit on which the differ. While their work could achieve ORE with short ciphertexts that expand the plaintext by a factor approximate 1.58, it could only find OPE with longer ciphertxts that expanded the plaintext by a security-parameter factor. We give evidence that this gap between ORE and OPE is inherent, by proving that any OPE meeting the information-theoretic version of their security definition (for instance, in the random oracle model) must have ciphertext length close to that of their constructions. We extend our result to identify an abstract security property of any OPE that will result in the same lower bound.

We propose a new attack framework based upon cube testers and d-monomial tests. The d-monomial test is a general framework for comparing the ANF of the symmetric cipher’s output with ANF of a random Boolean function. In the d-monomial test, the focus is on the frequency of the special monomial in the ANF of Boolean functions, but in the proposed framework, the focus is on the truth table. We attack ACORN-v3 and Grain-128a and demonstrate the efficiency of our framework. We show how it is possible to apply a distinguishing attack for up to 676 initialization rounds of ACORN-v3 and 171 initialization rounds of Grain-128a using our framework. The attack on ACORN-v3 is the best practical attack (and better results can be obtained by using more computing power). One can apply distinguishing attacks to black box symmetric ciphers by the proposed framework, and we suggest some guidelines to make it possible to improve the attack by analyzing the internal structure of ciphers. The framework is applicable to all symmetric ciphers and hash functions. We discuss how it can reveal weaknesses that are not possible to find by other statistical tests. The attacks were practically implemented and verified.

In this paper, using probability transition matrix, at first we revisit the work of Mantin on finding the probability distribution of RC4 permutation after the completion of KSA. After that, we extend the same idea to analyse the probabilities during any iteration of Pseudo Random Generation Algorithm. Next, we study the bias $Z_r=r$ (where $Z_r$ is the $r$-th output keystream bit), which is one of the significant biases observed in RC4 output keystream. This bias has played an important role in the plaintext recovery attack proposed by Isobe et al. in FSE 2013. However, the accurate theoretical explanation of the bias of $Z_r=r$ is still a mystery. Though several attempts have been made to prove this bias, none of those provides accurate justification. Here, using the results found with the help of probability transition matrix we justify this bias of $Z_r=r$ accurately and settle this issue. The bias obtained from our proof matches perfectly with the experimental observations.

In the paper, we study the security of 3-line generalized Feistel network, which is a considerate choice for some special needs, such as designing a 96-bit cipher based on a 32-bit round function. We show key recovery attacks on 3-line generic balanced Feistel-2 and Feistel-3 based on the meet-in-the-middle technique in the chosen ciphertext scenario. In our attacks, we consider the key size is as large as one-third of the block size. For the first network, we construct a 9-round distinguisher and launch a 10-round key-recovery attack. For the second network, we show a 13-round distinguisher and give a 17-round attack based on some common assumptions.

Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting. We show how to `rewrite' an existing algorithm for computing the rank of a key after a side channel attack, such that it results in an enumeration algorithm that produces batches of keys that can be tested using Grover's algorithm. This results in the first quantum key search that benefits from side channel information.

We describe an algorithm which can efficiently evaluate Bernstein-Rabin-Winograd (BRW) polynomials. The presently best known complexity of evaluating a BRW polynomial on $m\geq 3$ field elements is $\lfloor m/2\rfloor$ field multiplications. Typically, a field multiplication consists of a basic multiplication followed by a reduction. The new algorithm requires $\lfloor m/2\rfloor$ basic multiplications and $1+\lfloor m/4\rfloor$ reductions. Based on the new algorithm for evaluating BRW polynomials, we propose two new hash functions ${\sf BRW}128$ and ${\sf BRW}256$ with digest sizes $128$ bits and $256$ bits respectively. The practicability of these hash functions is demonstrated by implementing them using instructions available on modern Intel processors. Timing results obtained from the implementations suggest that ${\sf BRW}$ based hashing compares favourably to the highly optimised implementation by Gueron of Horner's rule based hash function.

In this paper we formulate a SAT/SMT model for Rotational-XOR (RX) cryptanalysis in ARX primitives for the first time. The model is successfully applied to the block cipher family Speck, and distinguishers covering more rounds than previously are found, as well as RX-characteristics requiring less data to detect. In particular, we present distinguishers for 10, 11 and 12 rounds for Speck32/64 which have better probabilities than the previously known 9-round differential characteristic, for a certain weak key class. For versions of Speck48, we present several distinguishers, among which the longest one covering 15 rounds, while the previously best differential characteristic only covered 11.

The rapid growth of the Internet of Things together with the increasing popularity of connected objects have created a need for secure, efficient and lightweight ciphers. Among the multitude of candidates, the block cipher PRIDE is, to this day, one of the most efficient solutions for 8-bit micro-controllers. In this paper, we provide new insights and a better understanding of differential attacks of PRIDE. First, we show that two previous attacks are incorrect, and describe (new and old) properties of the cipher that make such attacks intricate. Based on this understanding, we show how to properly mount a differential attack. Our proposal is the first single key differential attack that reaches 18 rounds out of 20. It requires $2^{61}$ chosen plaintexts and recovers the 128-bit key with a final time complexity of $2^{63.3}$ encryptions, while requiring a memory of about $2^{35}$ blocks of 64 bits.

The cube attack is a powerful cryptanalytic technique and is especially powerful against stream ciphers. Since we need to analyze the complicated structure of a stream cipher in the cube attack, the cube attack basically analyzes it by regarding it as a blackbox. Therefore, the cube attack is an experimental attack, and we cannot evaluate the security when the size of cube exceeds an experimental range, e.g., 40. In this paper, we propose cube attacks on non-blackbox polynomials. Our attacks are developed by using the division property, which is recently applied to various block ciphers. The clear advantage is that we can exploit large cube sizes because it never regards the cipher as a blackbox. We apply the new cube attack to Trivium, Grain128a, ACORN and Kreyvium. As a result, the secret keys of 832-round Trivium, 183-round Grain128a, 704-round ACORN and 872-round Kreyvium are recovered. These attacks are the current best key-recovery attack against these ciphers.

Multidimensional linear cryptanalysis of block ciphers is improved in this work by introducing a number of new ideas. Firstly, formulae is given to compute approximate multidimensional distributions of encryption internal bits. Conventional statistics like LLR(Logarithmic Likelihood Ratio) do not fit to work in Matsui's Algorithm 2 for large dimension data, as the observation depend on too many cipher key bits. So, secondly, a new statistic which reflects the structure of the cipher round is constructed instead. Thirdly, computing the statistic values which fall into a critical region is presented as an optimisation problem for which an efficient algorithm is suggested. The algorithm works much faster than brute forcing all relevant key bits to compute the statistic. An attack for 16-round DES was implemented. We got an improvement over Matsui's attack on DES in data and time complexity keeping success probability the same.

Functional encryption, which emerges in the community recently, is a generalized concept of traditional encryption (e.g. RSA and AES). In traditional encryption scheme, decrypting a ciphertext with a correct decryption key will output the original plaintext associated to the ciphertext. In contrast, in functional encryption scheme, decrypting a ciphertext with a correct decryption key will output a value that is derived from both the plaintext and the decryption key, and the decryption output would change when different correct decryption key is used to decrypt the same ciphertext. We propose a new functional encryption scheme for multidimensional range query. Given a ciphertext that is the encryption of some secret plaintext under a public attribute (a multidimensional point), and a decryption key corresponding to a query range and a function key. If the public attribute point is within the query range, a user is able to decrypt the ciphertext with the decryption key to obtain a value, which is the output of a pre-defined \emph{one-way} function with the secret plaintext and the function key as input. In comparison, in previous functional encryption for range query, a decryption will simply output the original secret plaintext when the attribute point is within the query range.

Many modern block ciphers are constructed based on the paradigm of substitution-permutation networks (SPNs). But, somewhat surprisingly---especially in comparison with Feistel networks, which have been analyzed by dozens of papers going back to the seminal work of Luby and Rackoff---there are essentially no provable-security results about SPNs. In this work, we initiate a comprehensive study of the security of SPNs as strong pseudorandom permutations when the underlying "$S$-box" is modeled as a public random permutation. We show that 3~rounds of S-boxes are necessary and sufficient for secure linear SPNs, but that even 1-round SPNs can be secure when non-linearity is allowed. Additionally, our results imply security in settings where an SPN structure is used for domain extension of a block cipher, even when the attacker has direct access to the small-domain block cipher.

In a novel analysis, we formally prove that arbitrarily many Arbiter PUFs can be combined into a stable XOR Arbiter PUF. To the best of our knowledge, this design cannot be modeled by any known oracle access attack in polynomial time. Using majority vote of arbiter chain responses, our analysis shows that with a polynomial number of votes, the XOR Arbiter PUF stability of almost all challenges can be boosted exponentially close to 1; that is, the stability gain through majority voting can exceed the stability loss introduced by large XORs for a feasible number of votes. Considering state-of-the-art modeling attacks by Becker and Rührmair et al., our proposal enables the designer to increase the attacker's effort exponentially while still maintaining polynomial design effort. This is the first result that relates PUF design to this traditional cryptographic design principle.

In this paper, we present a practical password scheme due to Spilman, which is perfectly secure in the bounded retrieval model, assuming ideal hash functions. The construction is based on a hash-like function com- puted by a third party “facilitator”. The facilitator is trusted, and security derives from the facilitator’s long random secret, although the adversary is assumed to be able to retrieve a large fraction of that secret. Unlike the traditional “salted and hashed password” approach, this scheme is secure against an adversary capable of performing brute force dictionary attacks offline. The key security property for the facilitator function is a form of uncloneability, that prevents the adversary from calculating function values offline.

Argon2i is a data-independent memory hard function that won the password hashing competition. The password hashing algorithm has already been incorporated into several open source crypto libraries such as libsodium. In this paper we analyze the cumulative memory cost of computing Argon2i. On the positive side we provide a lower bound for Argon2i. On the negative side we exhibit an improved attack against Argon2i which demonstrates that our lower bound is nearly tight. In particular, we show that (1) An Argon2i DAG is $\left(e,O\left(n^3/e^3\right)\right))$-reducible. (2) The cumulative pebbling cost for Argon2i is at most $O\left(n^{1.768}\right)$. This improves upon the previous best upper bound of $O\left(n^{1.8}\right)$ [Alwen and Blocki, EURO S&P 2017]. (3) Argon2i DAG is $\left(e,\tilde{\Omega}\left(n^3/e^3\right)\right))$-depth robust. By contrast, analysis of [Alwen et al., EUROCRYPT 2017] only established that Argon2i was $\left(e,\tilde{\Omega}\left(n^2/e^2\right)\right))$-depth robust. (4) The cumulative pebbling complexity of Argon2i is at least $\tilde{\Omega}\left( n^{1.75}\right)$. This improves on the previous best bound of $\Omega\left( n^{1.66}\right)$ [Alwen et al., EUROCRYPT 2017] and demonstrates that Argon2i has higher cumulative memory cost than competing proposals such as Catena or Balloon Hashing. We also show that Argon2i has high {\em fractional} depth-robustness which strongly suggests that data-dependent modes of Argon2 are resistant to space-time tradeoff attacks.

A constrained pseudorandom function (PRF) is a secure PRF for which one can generate constrained keys that can only be used to evaluate the PRF on a subset of the domain. Constrained PRFs are used widely, most notably in applications of indistinguishability obfuscation (iO). In this paper we show how to constrain an invertible PRF (IPF), which is significantly harder. An IPF is a secure injective PRF accompanied by an inversion algorithm. A constrained key for an IPF can only be used to evaluate the IPF on a subset S of the domain, and to invert the IPF on the image of S. We first define the notion of a constrained IPF and then give two main constructions: one for puncturing an IPF and the other for (single-key) circuit constraints. Both constructions rely on recent work on private constrained PRFs. We also show that constrained pseudorandom permutations for many classes of constraints are impossible under our definition.

In the preprint [Characterizations of the differential uniformity of vectorial functions by the Walsh transform, IACR ePrint Archive 2017/516], the author has, for each even positive $\delta$, characterized in several ways differentially $\delta$-uniform functions by equalities satisfied by their Walsh transforms. These characterizations generalize the well-known characterization of APN functions by the fourth moment of their Walsh transform. We study two notions which are related to such known and new characterizations: (1) one for $(n,n)$-functions, that we call componentwise APNess (CAPNess), which is a stronger version of APNness related to the characterization by the fourth moment, and has been already considered in [On almost perfect nonlinear functions; Berger, Canteaut, Charpin and Laigle-Chapuy, IEEE Transactions on Information Theory 2006]; it is defined as follows: the arithmetic mean of $W_F^4(u,v)$ when $u$ ranges over ${\Bbb F}_2^n$ and $v$ is fixed nonzero in ${\Bbb F}_2^n$ equals $2^{2n+1}$, and (2) one for $(n,m)$-function ($m=n$, resp. $m= n-1$) that we call componentwise Walsh uniformity (CWU), which is a stronger version of APNness (resp. of differential 4-uniformity) related to one of the new characterizations, and is defined as follows: the arithmetic mean of $W_F^2(u_1,v_1)W_F^2(u_2,v_2)W_F^2(u_1+u_2,v_1+v_2)$ when $u_1,u_2$ range independently over ${\Bbb F}_2^n$ and $v_1,v_2$ are fixed nonzero and distinct in ${\Bbb F}_2^m$, equals $2^{3n}$. Concerning the first notion, it is easily seen, and known, that any plateaued function is CAPN if and only if it is AB and that APN power permutations are CAPN. We prove that CAPN functions can exist only if $n$ is odd; this solves an open problem by Berger et al. Concerning the second notion, we show that any APN function whose component functions are partially-bent (in particular, every quadratic APN function) is CWU, but we observe also that other APN functions like Kasami functions and the inverse of one of the Gold APN permutations are CWU. To the aim of proving these two more difficult results, we first show that the CWUness of APN power permutations is equivalent to a property which is similar to the difference set with Singer parameters property of the complement of $\Delta_F=\{F(x)+F(x+1)+1; x\in {\Bbb F}_{2^n}\}$, proved in the case of Kasami APN functions by Dillon and Dobbertin in [New cyclic difference sets with Singer parameters, FFA 2004]. This new property, that we call cyclic-additive difference set property, involves both operations of addition and multiplication and is more complex. We prove it in the case of the inverse of Gold function. In the case of Kasami functions, it seems difficult to find a direct proof, even by adapting the sophisticated proof by Dillon and Dobbertin of the cyclic difference set property. But the properties of plateaued APN functions proved recently by the author in [Boolean and vectorial plateaued functions, and APN functions, IEEE Transactions on Information Theory 2015] give more insight, for APN power functions, on the relation between the cyclic-additive difference set property and the cyclic difference set property. The author is working at finalizing this way the proof for Kasami functions in odd dimension. A stronger property proved in this same paper for the particular case of plateaued functions with unbalanced components shows a relationship between the cyclic-additive difference set property and the value set of the function. This hopefully will allow completing the proof in the case of even dimension.

Leakage of information between two processes sharing the same processor cache has been exploited in many novel approaches targeting various cryptographic algorithms. The software implementation of AES is an especially attractive target since it makes extensive use of cache-resident table lookups. We consider two attack scenarios where either the plaintext or ciphertext is known. We employ a multi-threaded spy process and ensure that each time slice provided to the victim (running AES) is small enough so that it makes a very limited number of table accesses. We design and implement a suite of algorithms to deduce the 128-bit AES key using as input the set of (unordered) cache line numbers captured by the spy threads in an access-driven cache-based side channel attack. Our algorithms are expressed using simple relational algebraic operations and run in under a minute. Above all, our attack is highly efficient - we demonstrate recovery of the full AES key given only about 6-7 blocks of plaintext or ciphertext (theoretically even a single block would suffice). This is a substantial improvement over previous cache-based side channel attacks that require between 100 and a million encryptions. Moreover, our attack supports varying cache hit/miss observation granularities, does not need frequent interruptions of the victim and will work even if the victim makes up to 60 cache accesses before being interrupted. Finally, we develop analytic models to estimate the number of encryptions/decryptions required as a function of access granularity and compare model results with those obtained from our experiments

At CRYPTO 2015, Minaud and Seurin introduced and studied the iterated random permutation problem, which is to distinguish the $r$-th iterate of a random permutation from a random permutation. In this paper, we study the closely related iterated random function problem, and prove the first almost-tight bound in the adaptive setting. More specifically, we prove that the advantage to distinguish the $r$-th iterate of a random function from a random function using $q$ queries is bounded by $O(q^2r(\log r)^3/N)$, where $N$ is the size of the domain. In previous work, the best known bound was $O(q^2r^2/N)$, obtained as a direct result of interpreting the iterated random function problem as a special case of CBC-MAC based on a random function. For the iterated random function problem, the best known attack has an advantage of $\Omega(q^2r/N)$, showing that our security bound is tight up to a factor of $(\log r)^3$.

The GMR-2 cipher is a type of stream cipher currently being used in some Inmarsat satellite phones. It has been proven that such a cipher can be cracked using only one single-frame (15 bytes) known keystream but with a moderate executing times. In this paper, we present a new thorough security analysis of the GMR-2 cipher. We first study the inverse properties of the cipher's components to reveal a bad one-way character of the cipher. By then introducing a new concept called ``valid key chain" according to the cipher's key schedule, we propose an unprecedented real-time inversion attack using a single-frame keystream. This attack comprises three phases: (1) table generation; (2) dynamic table look-up, filtration and combination; and (3) verification. Our analysis shows that, using the proposed attack, the size of the exhaustive search space for the 64-bit encryption key can be reduced to approximately $2^{13}$ when a single-frame keystream is available. Compared with previous known attacks, this inversion attack is much more efficient. Finally, the proposed attack is carried out on a 3.3-GHz PC, and the experimental results thus obtained demonstrate that the 64-bit encryption-key could be recovered in approximately 0.02 s on average.

We introduce identity-based format-preserving encryption (IB-FPE) as a way to localize and limit the damage to format-preserving encryption (FPE) from key exposure. We give definitions, relations between them, generic attacks and two transforms of FPE schemes to IB-FPE schemes. As a special case, we introduce and cover identity-based tweakable blockciphers. We apply all this to analyze DFF, an FPE scheme proposed to NIST for standardization.

Authenticated encryption schemes in practice have to be robust against adversaries that have access to various types of leakage, for instance decryption leakage on invalid ciphertexts (protocol leakage), or leakage on the underlying primitives (side channel leakage). This work includes several novel contributions: we augment the notion of nonce-base authenticated encryption with the notion of continuous leakage and we prove composition results in the face of protocol and side channel leakage. Moreover, we show how to achieve authenticated encryption that is simultaneously both misuse resistant and leakage resilient, based on a sufficiently leakage resilient PRF, and finally we propose a concrete, pairing-based, instantiation of the latter.

In this paper, we propose a family of lightweight cryptographic permutations called sLiSCP, with the sole aim to provide a realistic minimal design}that suits a variety of lightweight device applications. More precisely, we argue that for such devices the chip area dedicated for security purposes should, not only be consumed by an encryption or hashing algorithm, but also provide as many cryptographic functionalities as possible. Our main contribution is the design of a lightweight permutation employing a 4-subblock Type-2 Generalized-like Structure (GFS) and round-reduced unkeyed Simeck with either 48 or 64-bit block length as the two round functions, thus resulting in two lightweight instances of the permutation, sLiSCP-192 and sLiSCP-256. We leverage the extensive security analysis on both Simeck (Simon-like functions) and Type-2 GFSs and present bounds against differential and linear cryptanalysis. In particular, we provide an estimation on the maximum differential probability of the round-reduced Simeck and use it for bounding the maximum expected differential/linear characteristic probability for our permutation. Due to the iterated nature of the Simeck round function and the simple XOR and cyclic shift mixing layer of the GFS that fosters the propagation of long trails, the long trail strategy}is adopted to provide tighter bounds on both characteristics. Moreover, we analyze sLiSCP against a wide range of distinguishing attacks, and accordingly, claim that there exists no structural distinguishers for sLiSCP with a complexity below $2^{b/2}$ where $b$ is the state size. We demonstrate how sLiSCP can be used as a unified round function in the duplex sponge construction to build (authenticated) encryption and hashing functionalities. The parallel hardware implementation area of the unified duplex mode of sLiSCP-192 (resp. sLiSCP-256) in CMOS $65\,nm$ ASIC is 2289 (resp. 3039) GEs with a throughput of 29.62 (resp. 44.44) kbps, and their areas in CMOS $130\, nm$ are 2498 (resp. 3319) GEs.

The main efficiency metrics for a cryptographic primitive are its speed, its code size and its memory complexity. For a variety of reasons, many algorithms have been proposed that, instead of optimizing, try to increase one of these hardness forms. We present for the first time a unified framework for describing the hardness of a primitive along any of these three axes: code-hardness, time-hardness and memory-hardness. This unified view allows us to present modular block cipher and sponge constructions which can have any of the three forms of hardness and can be used to build any higher level symmetric primitive: hash function, PRNG, etc. We also formalize a new concept: asymmetric hardness. It creates two classes of users: common users have to compute a function with a certain hardness while users knowing a secret can compute the same function in a far cheaper way. Functions with such an asymmetric hardness can be directly used in both our modular structures, thus constructing any symmetric primitive with an asymmetric hardness. We also propose the first asymmetrically memory-hard function, DIODON. As illustrations of our framework, we introduce WHALE and SKIPPER. WHALE is a code-hard hash function which could be used as a key derivation function and SKIPPER is the first asymmetrically time-hard block cipher.

OCB3 is the current version of the OCB authenticated encryption mode which is selected for the third round in CAESAR. So far the integrity analysis has limited to an adversary making a single forging attempt. A simple extension for the best known bound establishes integrity security as long as the total number of query blocks (including encryptions and forging attempts) does not exceed the birthday-bound. In this paper we show an improved bound for integrity of OCB3 in terms of the number of blocks in the forging attempt. In particular we show that when the number of encryption query blocks is not more than birthdaybound (an assumption without which the privacy guarantee of OCB3 disappears), even an adversary making forging attempts with the number of blocks in the order of 2n=L_MAX (n being the block-size and L_MAX being the length of the longest block) may fail to break the integrity of OCB3.

We present a length doubler, LDT, that turns an n-bit tweakable block cipher into an efficient and secure cipher that can encrypt any bit string of length [n..2n-1]. The LDT mode is simple, uses only two cryptographic primitive calls (while prior work needs at least four), and is a strong length-preserving pseudorandom permutation if the underlying tweakable block ciphers are strong tweakable pseudorandom permutations. We demonstrate that LDT can be used to neatly turn an authenticated encryption scheme for integral data into a mode for arbitrary-length data.

In this article, we provide the first independent security analysis of Deoxys, a third-round authenticated encryption candidate of the CAESAR competition, and its internal tweakable block ciphers Deoxys-BC-256 and Deoxys-BC-384. We show that the related-tweakey differential bounds provided by the designers can be greatly improved thanks to a MILP-based search tool. In particular, we develop a new method to incorporate linear incompatibility in the MILP model. We use this tool to generate valid differential paths for reduced-round versions of Deoxys-BC-256 and Deoxys-BC-384, later combining them into broader boomerang or rectangle attacks. Here, we also develop a new MILP model which optimises the two paths by taking into account the effect of the ladder switch technique. Interestingly, with the tweak in Deoxys-BC providing extra input as opposed to a classical block cipher, we can even consider beyond full-codebook attacks, and we analyse how our results can be improved in this setting. As these primitives are based on the TWEAKEY framework, we further study how the security of the cipher is impacted when playing with the tweak/key sizes. All in all, we are able to attack 10 rounds of Deoxys-BC-256 (out of 14) and 14 rounds of Deoxys-BC-384 (out of 16). The extra rounds specified in Deoxys-BC to balance the tweak input (when compared to AES) seem to provide about the same security margin as AES-128. Finally we analyse why the authenticated encryption modes of Deoxys mostly prevent our attacks on Deoxys-BC to apply to the authenticated encryption primitive.

The keyed duplex construction was introduced by Bertoni et al.(SAC 2011) and recently generalized to full-state absorption by Mennink et al.(ASIACRYPT 2015). We present a generalization of the full-state keyed duplex that natively supports multiple instances by design, and perform a security analysis that improves over that of Mennink et al. in terms of a more modular security analysis and a stronger and more adaptive security bound. Via the introduction of an additional parameter to the analysis, our bound demonstrates a significant security improvement in case of nonce-respecting adversaries. Furthermore, by supporting multiple instances by design, instead of adapting the security model to it, we manage to derive a security bound that is largely independent of the number of instances.

Block cipher modes of operation provide a way to securely encrypt using a block cipher. The main factors in analyzing modes of operation are the level of security achieved (chosen-plaintext security, authenticated encryption, nonce-misuse resistance, and so on) and performance. When measuring the security level of a mode of operation, it does not suffice to consider asymptotics, and a concrete analysis is necessary. This is especially the case today, when encryption rates can be very high, and so birthday bounds may be approached or even reached. In this paper, we show that key-derivation at every encryption significantly improves the security bounds in many cases. We present a new key-derivation method that utilizes a truncated block cipher, and show that this is far better than standard block-cipher based key derivation. We prove that by using our key derivation method, we obtain greatly improved bounds for many modes of operation, with a result that the lifetime of a key can be significantly extended. We demonstrate this for AES-CTR (CPA-security), AES-GCM (authenticated encryption) and AES-GCM-SIV (nonce-misuse resistance). Finally, we demonstrate that when using modern hardware with AES instructions (AES-NI), the performance penalty of deriving keys at each encryption is insignificant for most uses.