In this work, we analyze the resistance of SIMON-like ciphers against differential attacks without using computer-aided methods. In this context, we first define the notion of a SIMON-like cipher as a generalization of the SIMON design. For certain instances, we present a method for proving the resistance against differential attacks by upper bounding the probability of a differential characteristic by $2^{-2T+2}$ where $T$ denotes the number of rounds. Interestingly, if $2n$ denotes the block length, our result is sufficient in order to bound the probability by $2^{-2n}$ for all full-round variants of SIMON and Simeck. Thus, it guarantees security in a sense that, even having encryptions of the full codebook, one cannot expect a differential characteristic to hold. The important difference between previous works is that our proof can be verified by hand and thus contributes towards a better understanding of the design. However, it is to mention that we do not analyze the probability of multi-round differentials. Although there are much better bounds known, especially for a high number of rounds, they are based on experimental search like using SAT/SMT solvers. While those results have already shown that SIMON can be considered resistant against differential cryptanalysis, our argument gives more insights into the design itself. As far as we know, this work presents the first non-experimental security argument for full-round versions of several SIMON-like instances.

Rotational cryptanalysis is a statistical method for attacking ARX constructions. It was previously shown that ARX-C, i.e., ARX with the injection of constants can be used to implement any function. In this paper we investigate how rotational cryptanalysis is affected when constants are injected into the state. We introduce the notion of an RX-difference, generalizing the idea of a rotational difference. We show how RX-differences behave around modular addition, and give a formula to calculate their transition probability. We experimentally verify the for- mula using Speck32/64, and present a 7-round distinguisher based on RX-differences. We then discuss two types of constants: round constants, and constants which are the result of using a fixed key, and provide recommendations to designers for optimal choice of parameters.

The hash function Kupyna was recently published as the Ukrainian standard DSTU 7564:2014. It is structurally very similar to the SHA-3 finalist Grøstl, but differs in details of the round transformations. Most notably, some of the round constants are added with a modular addition, rather than bitwise xor. This change prevents a straightforward application of some recent attacks, in particular of the rebound attacks on the compression function of similar AES-like hash constructions. However, we show that it is actually possible to mount rebound attacks, despite the presence of modular constant additions. More specifically, we describe collision attacks on the compression function for 6 (out of 10) rounds of Kupyna-256 with an attack complexity of 2^{70}, and for 7 rounds with complexity 2^{125.8}. In addition, we have been able to use the rebound attack for creating collisions for the round-reduced hash function itself. This is possible for 4 rounds of Kupyna-256 with complexity 2^{67} and for 5 rounds with complexity 2^{120}.

We propose the TWEAKEY framework with goal to unify the design of tweakable block ciphers and of block ciphers resistant to related-key attacks. Our framework is simple, extends the key-alternating construction, and allows to build a primitive with arbitrary tweak and key sizes, given the public round permutation (for instance, the AES round). Increasing the sizes renders the security analysis very difficult and thus we identify a subclass of TWEAKEY, that we name STK, which solves the size issue by the use of finite field multiplications on low hamming weight constants. We give very efficient instances of STK, in particular, a 128-bit tweak/key/state block cipher Deoxys-BC that is the first AES-based ad-hoc tweakable block cipher. At the same time, Deoxys-BC could be seen as a secure alternative to AES-256, which is known to be insecure in the related-key model. As another member of the TWEAKEY framework, we describe Kiasu-BC, which is a very simple and even more efficient tweakable variation of AES-128 when the tweak size is limited to 64 bits. In addition to being efficient, our proposals, compared to the previous schemes that use AES as a black box, offer security beyond the birthday bound. Deoxys-BC and Kiasu-BC represent interesting pluggable primitives for authenticated encryption schemes, for instance, OCB instantiated with Kiasu-BC runs at about 0.75 c/B on Intel Haswell. Our work can also be seen as advances on the topic of secure key schedule design for AES-like ciphers, describing several proposals in this direction.

In this paper we explore the intriguing factors involved in the non one-one nature of the RC4, and explore new techniques and present interesting findings regarding the same. The first part of this paper studies near colliding keys of the RC4, and discusses how these keys are localized into clusters in the key-space. The second part of this paper proposes a new collision search algorithm specifically for 16-byte keys. It is generally the practice to choose the byte that differs between two keys to be near the end of the key. However, this is not necessary for 16-byte keys, and the second part of this paper discusses how this may be used to grant us an additional degree of control.

A few work has ever been performed in cryptanalysis of block ciphers using cube attacks. This paper presents a new framework for an efficient key recovery attack on block ciphers based on cube technique. In this method, a cube tester is positioned at the middle of the cipher which is extended in two directions over the maximum possible upper and lower rounds, given that some subkey bits are guessed. It is shown that an automated algorithm for this dynamic cube attack on block ciphers can be realized. Furthermore, we show its effectiveness on two lightweight block ciphers KATAN and SIMON. Our results shows that this method can break 117 and 152 out of 254 rounds of KATAN-32 in non-full-codebook and full-codebook attack scenarios, respectively. In the case of SIMON32/64, we succeed to cryptanalyse 16 and 18 out of 32 rounds, by the same scenarios. Both results show that although this method does not outperform all the existing attacks on these two ciphers, it can absolutely compete with the well-established and mature methods of cryptanalysis of block ciphers, such as linear, differential and meet in the middle attack families.

This paper reconsiders the design of the stream cipher RC4, and proposes an improved variant, which we call ``Spritz'' (since the output comes in fine drops rather than big blocks.) Our work leverages the considerable cryptanalytic work done on the original RC4 and its proposed variants. It also uses simulations extensively to search for biases and to guide the selection of intermediate expressions. We estimate that Spritz can produce output with about 24 cycles/byte of computation. Furthermore, our statistical tests suggest that about $2^{81}$ bytes of output are needed before one can reasonably distinguish Spritz output from random output; this is a marked improvement over RC4. [Footnote: However, see Appendix F for references to more recent work that suggest that our estimates of the work required to break Spritz may be optimistic.] In addition, we formulate Spritz as a ``sponge (or sponge-like) function,'' (see Bertoni et al.), which can ``Absorb'' new data at any time, and from which one can ``Squeeze'' pseudorandom output sequences of arbitrary length. Spritz can thus be easily adapted for use as a cryptographic hash function, an encryption algorithm, or a message-authentication code generator. (However, in hash-function mode, Spritz is rather slow.)

At CCS 2015, Gueron and Lindell proposed GCM-SIV, a provably secure authenticated encryption scheme that remains secure even if the nonce is repeated. While this is an advantage over the original GCM, we first point out that GCM-SIV allows a trivial distinguishing attack with about $2^{48}$ queries, where each query has one plaintext block. This shows the tightness of the security claim and does not contradict the provable security result. However, the original GCM resists the attack, and this poses a question of designing a variant of GCM-SIV that is secure against the attack. We present a minor variant of GCM-SIV, which we call GCM-SIV1, and discuss that GCM-SIV1 resists the attack, and it offers a security trade-off compared to GCM-SIV. As the main contribution of the paper, we explore a scheme with a stronger security bound. We present GCM-SIV2 which is obtained by running two instances of GCM-SIV1 in parallel and mixing them in a simple way. We show that it is secure up to $2^{85.3}$ query complexity, where the query complexity is measured in terms of the total number of blocks of the queries. Finally, we generalize this to show GCM-SIV$r$ by running $r$ instances of GCM-SIV1 in parallel, where $r\ge 3$, and show that the scheme is secure up to $2^{128r/(r+1)}$ query complexity. The provable security results are obtained under the standard assumption that the blockcipher is a pseudorandom permutation.

The security of order-revealing encryption (ORE) has been unclear since its invention. Dataset characteristics for which ORE is especially insecure have been identified, such as small message spaces and low-entropy distributions. On the other hand, properties like one-wayness on uniformly-distributed datasets have been proved for ORE constructions. This work shows that more plaintext information can be extracted from ORE ciphertexts than was previously thought. We identify two issues: First, we show that when multiple columns of correlated data are encrypted with ORE, attacks can use the encrypted columns together to reveal more information than prior attacks could extract from the columns individually. Second, we apply known attacks, and develop new attacks, to show that the \emph{leakage} of concrete ORE schemes on non-uniform data leads to more accurate plaintext recovery than is suggested by the security theorems which only dealt with uniform inputs.

{\sc Simon} is a family of lightweight block ciphers published by the U.S. National Security Agency (NSA) in 2013. Due to its novel and bit-based design, integral cryptanalysis on {\sc Simon} seems a tough job. At EUROCRYPT 2015 Todo proposed division property which is a generalized integral property, and he applied this technique to searching integral distinguishers of {\sc Simon} block ciphers by considering the left and right halves of {\sc Simon} independently. As a result, he found 11-round integral distinguishers for both {\sc Simon}48 and {\sc Simon}64. Recently, at FSE 2016 Todo \emph{et al.} proposed bit-based division property that considered each bit independently. This technique can find more accurate distinguishers, however, as pointed out by Todo \emph{et al.} the time and memory complexity is bounded by $ 2^n $ for an $ n$-bit block cipher. Thus, bit-based division property is only applicable to {\sc Simon}32. In this paper we propose a new technique that achieves a trade-off between considering each bit independently and considering left and right halves as a whole, which is actually a trade-off between time-memory and the accuracy of the distinguishers. We proceed by splitting the state of {\sc Simon} into small pieces and study the division property propagations of circular shift and bitwise AND operations under the state partition. Moreover, we propose two different state partitions and study the influences of different partitions on the propagation of division property. We find that different partitions greatly impact the division property propagation of circular shift which will finally result in a big difference on the length of integral distinguishers. By using a tailored search algorithm for {\sc Simon}, we find 12-round integral distinguishers for {\sc Simon}48 and {\sc Simon}64 respectively, which improve Todo's results by one round for both variants.

Free cloud-based services are powerful candidates for deploying ubiquitous encryption for messaging. In the case of email and increasingly chat, users expect the ability to store and search their messages persistently. Using data from one of the top three mail providers, we confirm that for a searchable encryption scheme to scale to millions of users, it should be highly IO-efficient (locality), and handle a very dynamic message corpi. We observe that existing solutions fail to achieve both properties simultaneously. We then design, build, and evaluate a provably secure Dynamic Searchable Symmetric Encryption (DSSE) scheme with significant reduction in IO cost compared to preceding works when used for email or other highly dynamic message corpi.

We introduce a new technique for doing the key recovery part of an integral or higher order differential attack. This technique speeds up the key recovery phase significantly and can be applied to any block cipher with S-boxes. We show several properties of this technique, then apply it to PRINCE and report on the improvements in complexity from earlier integral and higher order differential attacks on this cipher. Our attacks on 4 and 6 rounds were the fastest and the winner of PRINCE Challenge's last round in the category of chosen plaintext attack.

This paper presents a security bound in the standard security model for the Magma cipher CTR encryption mode and the «CryptoPro Key Meshing» (CPKM) re-keying method that was previously used with the GOST 28147-89 cipher. We enumerate the main requirements that should be followed during the development of re-keying methods, then we propose a modified method and justify its advantages over CPKM. We also obtain certain results about the operational features of the Kuznyechik cipher CTR encryption mode with several re-keying methods.

LowMC is a family of block ciphers developed particularly for use in multi-party computations and fully homomorphic encryption schemes, where the main performance penalty comes from non-linear operations. Thus, LowMC has been designed to minimize the total quantity of logical "and" operations, as well as the "and" depth. To achieve this, the LowMC designers opted for an incomplete S-box layer that does not cover the complete state, and compensate for it with a very dense, randomly chosen linear layer. In this work, we exploit this design strategy in a cube-like key-recovery attack. We are able to recover the secret key of a round-reduced variant of LowMC with 80-bit security, where the number of rounds is reduced from 11 to 9. Our attacks are independent of the actual instances of the used linear layers and therefore, do not exploit possible weak choices of them. From our results, we conclude that the resulting security margin of 2 rounds is smaller than expected.

In this paper we focus on the PRINCE block cipher reduced to 6 rounds, with two known plaintext/ciphertext pairs. We develop two attacks on 6-round PRINCE based on accelerated exhaustive search, one with negligible memory usage and one having moderate memory requirements. The time complexities for the two attacks are $2^{96.78}$ and $2^{88.85}$, respectively. The memory consumption of the second attack is less than 200MB and so is not a restricting factor in a real-world setting.

We investigate two attacks on the PRINCE block cipher in the most realistic scenario, when the attacker only has a minimal amount of known plaintext available. The first attack is called Accelerated Exhaustive Search, and is able to recover the key for up to the full 12-round PRINCE with a complexity slightly lower than the security claim given by the designers. The second attack is a meet-in-the-middle attack, where we show how to successfully attack 8- and 10-round PRINCE with only two known plaintext/ciphertext pairs. Both attacks take advantage of the fact that the two middle rounds in PRINCE are unkeyed, so guessing the state before the first middle round gives the state after the second round practically for free. These attacks are the fastest until now in the known plaintext scenario for the 8 and 10 reduced-round versions and the full 12-round of PRINCE.

In this paper we attack a $2n$-bit double length hash function proposed by Lee et al. This proposal is a blockcipher-based hash function with hash rate $2/3$. The designers claimed that it could achieve ideal collision resistance and gave a security proof. However, we find a collision attack with complexity of $\Omega(2^{3n/4})$ and a preimage attack with complexity of $\Omega(2^{n})$. Our result shows this construction is much worse than an ideal $2n$-bit hash function.

Digital signatures are one of the most important cryptographic primitives. In this work we construct an information-theoretically secure signature scheme which, unlike prior schemes, enjoys a number of advantageous properties such as short signature length and high generation efficiency, to name two. In particular, we extend symmetric-key message authentication codes (MACs) based on universal hashing to make them transferable, a property absent from traditional MAC schemes. Our main results are summarised as follows. - We construct an unconditionally secure signature scheme which, unlike prior schemes, does not rely on a trusted third party or anonymous channels. In our scheme, a sender shares with each of the remaining protocol participants (or recipients) a set of keys (or hash functions) from a family of universal hash functions. Also, the recipients share with each other a random portion of the keys that they share with the sender. A signature for a message is a vector of tags generated by applying the hash functions to the message. As such, our scheme can be viewed as an extension of MAC schemes, and therefore, the practical implementation of our scheme is straightforward. - We prove information-theoretic security of our scheme against forging, repudiation, and non-transferability. - We compare our schemes with existing both "classical" (not employing quantum mechanics) and quantum unconditionally secure signature schemes. The comparison shows that our new scheme has a number of unparalleled advantages over the previous schemes. - Finally, although our scheme does not rely on trusted third parties, we discuss this, showing that having a trusted third party makes our scheme even more attractive.

Authenticated encryption (AE) schemes are symmetric-key encryption schemes ensuring strong notions of confidentiality and integrity. Although various AE schemes are known, there remains significant interest in developing schemes that are more efficient, meet even stronger security notions (e.g., misuse-resistance), or satisfy certain non-cryptographic properties (e.g., being patent-free). We present an automated approach for analyzing and synthesizing blockcipher-based AE schemes, significantly extending prior work by Malozemoff et al. (CSF 2014) who synthesize encryption schemes satisfying confidentiality only. Our main insight is to restrict attention to a certain class of schemes that is expressive enough to capture several known constructions yet also admits automated reasoning about security. We use our approach to generate thousands of AE schemes with provable security guarantees, both known (e.g., variants of OCB and CCM) and new. Implementing two of these new schemes, we find their performance competitive with state-of-the-art AE schemes.

In this paper, we analyzed an extreme case of lightweight block cipher design in terms of security and efficiency. To do this, we proposed ELiF block cipher family which has one of the smallest hardware area in a fully serial design. We also defined ELiF to be flexible and scalable so that it can be implemented for real life applications with different scenarios such as fixed key implementations. We also gave hardware implementation results for different implementation settings to show its efficiency and flexibility. Because of its flexible implementation properties, ELiF family of ciphers are suitable for systems with asymmetric computation powers such as RFID reader and tags. We made theoretical and experimental analysis for various block sizes. Using the results for small block lengths, we estimated minimum number of rounds that the cipher becomes secure depending on the block size.

In this paper, we propose a generic method to construct involutory binary matrices from a three round Feistel scheme with a linear round function. We prove bounds on the maximum achievable branch number (BN) and the number of fixed points of our construction. We also define two families of efficiently implementable round functions to be used in our method. The usage of these families in the proposed method produces matrices achieving the proven bounds on branch numbers and fixed points. Moreover, we show that BN of the transpose matrix is the same with the original matrix for the function families we defined. Some of the generated matrices are \emph{Maximum Distance Binary Linear} (MDBL), i.e. matrices with the highest achievable BN. The number of fixed points of the generated matrices are close to the expected value for a random involution. Generated matrices are especially suitable for utilising in bitslice block ciphers and hash functions. They can be implemented efficiently in many platforms, from low cost CPUs to dedicated hardware.

We discuss the design of symmetric primitives, in particular Pseudo-Random Functions (PRFs) which are suitable for use in a secret-sharing based MPC system. We consider three different PRFs: the Naor-Reingold PRF, a PRF based on the Legendre symbol, and a specialized block cipher design called MiMC. We present protocols for implementing these PRFs within a secret-sharing based MPC system, and discuss possible applications. We then compare the performance of our protocols. Depending on the application, different PRFs may offer different optimizations and advantages over the classic AES benchmark. Thus, we cannot conclude that there is one optimal PRF to be used in all situations.

The cube attack is an algebraic attack that allows an adversary to extract low degree polynomial equations from the targeted cryptographic primitive. This work applies the cube attack to a reduced round version of ACORN, a candidate cipher design in the CAESAR cryptographic competition. The cube attack on 477 initialization rounds of ACORN can recover the 128 bit key with a total attack complexity of about $2^{35}$. We have also shown that linear equations relating the initial state of the full version of ACORN can be be easily generated which can lead to state recovery attack with an attack complexity of about $2^{72.8}$.

A robust combiner for hash functions takes two candidate implementations and constructs a hash function which is secure as long as at least one of the candidates is secure. So far, hash function combiners only aim at preserving a single property such as collision-resistance or pseudorandomness. However, when hash functions are used in protocols like TLS they are often required to provide several properties simultaneously. We therefore put forward the notion of robust multi-property combiners and elaborate on different definitions for such combiners. We then propose a combiner that provably preserves (target) collision-resistance, pseudorandomness, and being a secure message authentication code. This combiner satisfies the strongest notion we propose, which requires that the combined function satisfies every security property which is satisfied by at least one of the underlying hash function. If the underlying hash functions have output length n, the combiner has output length 2n. This basically matches a known lower bound for black-box combiners for collision-resistance only, thus the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the property of being indifferentiable from a random oracle, slightly increasing the output length to 2n + \omega(log n). Moreover, we show how to augment our constructions in order to make them also robust for the one-wayness property, but in this case require an a priory upper bound on the input length.

A common countermeasure against side-channel attacks consists in using the masking scheme originally introduced by Ishai, Sahai and Wagner (ISW) at Crypto 2003, and further generalized by Rivain and Prouff at CHES 2010. The countermeasure is provably secure in the probing model, and it was showed by Duc, Dziembowski and Faust at Eurocrypt 2014 that the proof can be extended to the more realistic noisy leakage model. However the extension only applies if the leakage noise $\sigma$ increases at least linearly with the masking order $n$, which is not necessarily possible in practice. In this paper we investigate the security of an implementation when the previous condition is not satisfied, for example when the masking order $n$ increases for a constant noise $\sigma$. We exhibit two (template) horizontal side-channel attacks against the Rivain-Prouff's secure multiplication scheme and we analyze their efficiency thanks to several simulations and experiments. We also describe a variant of Rivain-Prouff's multiplication that is still provably secure in the original ISW model, and also heuristically secure against our new attacks. Finally, we describe a new mask refreshing algorithm with complexity ${\cal O}(n \log n)$, instead of ${\cal O}(n^2)$ for the classical algorithm.

Kalyna is an SPN-based block cipher that was selected during Ukrainian National Public Cryptographic Competition (2007-2010) and its slight modification was approved as the new encryption standard of Ukraine. In this paper, we focus on the key-recovery attacks on reduced-round Kalyna-128/256 and Kalyna-256/512 with meet-in-the-middle method. The differential enumeration technique and key-dependent sieve technique which are popular to analyze AES are used to attack them. Using the key-dependent sieve technique to improve the complexity is not an easy task, we should build some tables to achieve this. Since the encryption procedure of Kalyna employs a pre- and post-whitening operations using addition modulo $2^{64}$ applied on the state columns independently, we carefully study the propagation of this operation and propose an addition plaintext structure to solve this. For Kalyna-128/256, we propose a 6-round distinguisher, and achieve a 9-round (out of total 14-round) attack. For Kalyna-256/512, we propose a 7-round distinguisher, then achieve an 11-round (out of total 18-round) attack. As far as we know, these are currently the best results on Kalyna-128/256 and Kalyna-256/512.

Standard form of authenticated encryption (AE) requires the ciphertext to be expanded by the nonce and the authentication tag. These expansions can be problematic when messages are relatively short and communication cost is high. To overcome the problem we propose a new form of AE scheme, MiniAE, which expands the ciphertext only by the single variable integrating nonce and tag. An important feature of MiniAE is that it requires the receiver to be stateful not only for detecting replays but also for detecting forgery of any type. McGrew and Foley already proposed a scheme having this feature, called AERO, however, there is no formal security guarantee based on the provable security framework. We provide a provable security analysis for MiniAE, and show several provably-secure schemes using standard symmetric crypto primitives. This covers a generalization of AERO, hence our results imply a provable security of AERO. Moreover, one of our schemes has a similar structure as OCB mode of operation and enables rate-1 operation, i.e. only one blockcipher call to process one input block. This implies that the computation cost of MiniAE can be as small as encryption-only schemes.

We prove the related-key security of the Iterated Even-Mansour cipher under broad classes of related key derivation (RKD) functions. Our result extends the classes of RKD functions considered by Farshim and Procter (FSE, 15). Moreover, we present a far simpler proof which uses techniques similar to those used by Cogliati and Seurin (EUROCRYPT, 15) in their proof that the four-round Even-Mansour cipher is secure against XOR related-key attacks---a special case of our result and the result of Farshim and Proctor. Finally, we give a concrete example of a class of RKD functions covered by our result which does not satisfy the requirements given by Farshim and Procter and prove that the three-round Even-Mansour cipher is secure against this class of RKD functions.

``Mirror Theory'' is the theory that evaluates the number of solutions of affine systems of equalities (=) and non equalities ($\neq$) in finite groups. It is deeply related to the security and attacks of many generic cryptographic secret key schemes, for example random Feistel schemes (balanced or unbalanced), Misty schemes, Xor of two pseudo-random bijections to generate a pseudo-random function etc. In this paper we will assume that the groups are abelian. Most of time in cryptography the group is $((\mathbb{Z}/2\mathbb{Z})^n, \oplus)$ and we will concentrate this paper on these cases. We will present here general definitions, some theorems, and many examples and computer simulations.

HANUMAN is a mode of operation of a keyless cryptographic permutation for nonce-based authenticated encryption with associated data, included among the modes bundled in the PRIMATEs candidate in the currently ongoing CAESAR competition. HANUMAN is a sponge-like mode whose design and security argument are inspired by the SpongeWrap construction. We identify a flaw in the domain separation of HANUMAN, and show how to exploit it to efficiently produce ciphertext forgeries.

Designing an efficient cipher was always a delicate balance between linear and non-linear operations. This goes back to the design of DES, and in fact all the way back to the seminal work of Shannon. Here we focus, for the first time, on an extreme corner of the design space and initiate a study of symmetric-key primitives that minimize the multiplicative size and depth of their descriptions. This is motivated by recent progress in practical instantiations of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where linear computations are, compared to non-linear operations, essentially ``free''. We focus on the case of a block cipher, and propose the family of block ciphers ``LowMC'', beating all existing proposals with respect to these metrics. As examples, we give concrete instatiations for 80-bit, 128-bit, and 256-bit security. We sketch several applications for such ciphers and give implementation comparisons suggesting that when encrypting larger amounts of data the new design strategy translates into improvements in computation and communication complexity by up to a factor of 5 compared to AES-128, which incidentally is one of the most competitive classical designs. Furthermore, we identify cases where ``free XORs'' can no longer be regarded as such but represent a bottleneck, hence refuting this commonly held belief with a practical example.

White-box cryptography aims at providing security against an adversary that has access to the encryption process. Numerous white-box encryption schemes were proposed since the introduction of white-box cryptography by Chow et al. in 2002. However, most of them are slow, and thus, can be used in practice only to protect very small amounts of information, such as encryption keys. In this paper we present a new threat model for white-box cryptography which corresponds to the practical abilities of the adversary in a wide range of applications. Furthermore, we study design criteria for white-box primitives that are important from the industry point of view. Finally, we propose a class of new primitives that combine a white-box algorithm with a standard block cipher to obtain white-box protection for encrypting long messages, with high security and reasonable performance.

We analyze the security of Android KeyStore, a system service whose purpose is to shield users credentials and cryptographic keys. The KeyStore protects the integrity and the confidentiality of keys by using a particular encryption scheme. Our main results are twofold. First, we formally prove that the used encryption scheme does not provide integrity, which means that an attacker is able to undetectably modify the stored keys. Second, we exploit this flaw to define a forgery attack breaching the security guaranteed by the KeyStore. In particular, our attack allows a malicious application to make mobile apps to unwittingly perform secure protocols using weak keys. The threat is concrete: the attacker goes undetected while compromising the security of users. Our findings highlight an important fact: intuition often goes wrong when security is concerned. Unfortunately, system designers still tend to choose cryptographic schemes not for their proved security but for their apparent simplicity. We show, once again, that this is not a good choice, since it usually results in severe consequences for the whole underlying system.

Gentry’s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In previous work I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the plaintext. I also proposed fully homomorphic encryptions with composite number modulus which avoid the weak point by adopting the plaintext including the random numbers in it. In this paper I propose another fully homomorphic encryption with zero norm cipher text where zero norm medium text is generated and enciphered by using composite number modulus. In the proposed scheme it is proved that if there exists the PPT algorithm that generates the cipher text of the plaintext -p from the cipher text of any plaintext p, there exists the PPT algorithm that factors the given composite number modulus. That is, we include the random parameter in the plaintext so that if the random parameter and the plaintext are separated, then the composite number to be the modulus is factored. Since the scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on.

Block-cipher-based authenticated encryption has obtained considerable attention from the ongoing CAESAR competition. While the focus of CAESAR resides primarily on nonce-based authenticated encryption, Deterministic Authenticated Encryption (DAE) is used in domains such as key wrap, where the available message entropy motivates to omit the overhead for nonces. Since the highest possible security is desirable when protecting keys, beyond-birthday-bound (BBB) security is a valuable goal for DAE. In the past, significant efforts had to be invested into designing BBB-secure AE schemes from conventional block ciphers, with the consequences of losing efficiency and sophisticating security proofs. This work proposes Deterministic Counter in Tweak (DCT), a BBB-secure DAE scheme inspired by the Counter-in-Tweak encryption scheme by Peyrin and Seurin. Our design combines a fast $\epsilon$-almost-XOR-universal family of hash functions, for $\epsilon$ close to $2^{-2n}$, with a single call to a $2n$-bit SPRP, and a BBB-secure encryption scheme. First, we describe our construction generically with three independent keys, one for each component. Next, we present an efficient instantiation which (1) requires only a single key, (2) provides software efficiency by encrypting at less than two cycles per byte on current x64 processors, and (3) produces only the minimal $\tau$-bit stretch for $\tau$ bit authenticity. We leave open two minor aspects for future work: our current generic construction is defined for messages of at least $2n-\tau$ bits, and the verification algorithm requires the inverse of the used $2n$-bit SPRP and the encryption scheme.

The algorithm presented in this paper computes a maximum probability differential characteristic in a Substitution-Permutation Network (or SPN). Such characteristics can be used to prove that a cipher is practically secure against differential cryptanalysis or on the contrary to build the most effective possible attack. Running in just a few second on 64 or 128-bit SPN, our algorithm is an important tool for both cryptanalists and designers of SPN.

We discuss a tweak for the domain extension called Merkle-Damgård with Permutation (MDP), which was presented at ASIACRYPT 2007. We first show that MDP may produce multiple independent pseudorandom functions (PRFs) using a single secret key and multiple permutations if the underlying compression function is a PRF against related-key attacks with respect to the permutations. Using this result, we then construct a hash-function-based MAC function, which we call FMAC, using a compression function as its underlying primitive. We also present a scheme to extend FMAC so as to take as input a vector of strings.

SIMON is a lightweight block cipher designed by NSA in 2013. NSA presented the specification and the implementation efficiency, but they did not provide detailed security analysis nor the design rationale. The original SIMON has rotation constants of $(1,8,2)$, and Kölbl {\it et al}.~regarded the constants as a parameter $(a,b,c)$, and analyzed the security of SIMON block cipher variants against differential and linear attacks for all the choices of $(a,b,c)$. This paper complements the result of Kölbl {\it et al}.~by considering integral and impossible differential attacks. First, we search the number of rounds of integral distinguishers by using a supercomputer. Our search algorithm follows the previous approach by Wang {\it et al}., however, we introduce a new choice of the set of plaintexts satisfying the integral property. We show that the new choice indeed extends the number of rounds for several parameters. We also search the number of rounds of impossible differential characteristics based on the miss-in-the-middle approach. Finally, we make a comparison of all parameters from our results and the observations by Kölbl {\it et al}. Interesting observations are obtained, for instance we find that the optimal parameters with respect to the resistance against differential attacks are not stronger than the original parameter with respect to integral and impossible differential attacks. We also obtain a parameter that is better than the original parameter with respect to security against these four attacks.

Kiasu-BC is a tweakable block cipher presented within the TWEAKEY framework at AsiaCrypt 2014. Kiasu-BC is almost identical to AES-128, the only difference to AES-128 is the tweak addition, where the 64-bit tweak is xored to the first two rows of every round-key. The security analysis of the designers focuses primarily on related-key related-tweak differential characteristics and meet-in-the-middle attacks. For other attacks, they conclude that the security level of Kiasu-BC is similar to AES-128. In this work, we provide the first third-party analysis of Kiasu-BC. We show that we can mount Square attacks on up to 7-round Kiasu-BC with a complexity of about $2^{48.5}$ encryptions, which improves upon the best published 7-round attacks for AES-128. Furthermore, we show that such attacks are applicable to the round-reduced OCB3-like mode of the CAESAR candidate Kiasu. To be specific, we show a key-recovery attack on 7-round Kiasu$\neq$ with a complexity of about $2^{82}$ encryptions.

We describe a new technique for improving the efficiency of the masking countermeasure against side-channel attacks. Our technique is based on using common shares between secret variables, in order to reduce the number of finite field multiplications. Our algorithms are proven secure in the ISW probing model with $n \geq t+1$ shares against $t$ probes. For AES, we get an equivalent of $2.8$ non-linear multiplications for every SBox evaluation, instead of $4$ in the Rivain-Prouff countermeasure. We obtain similar improvements for other block-ciphers. Our technique is easy to implement and performs relatively well in practice, with roughly a 20% speed-up compared to existing algorithms.

A new distinguishing property against block ciphers, called the division property, was introduced by Todo at Eurocrypt 2015. Our work gives a new approach to it by the introduction of the notion of parity sets. First of all, this new notion permits us to formulate and characterize in a simple way the division property of any order. At a second step, we are interested in the way of building distinguishers on a block cipher by considering some further properties of parity sets, generalising the division property. We detail in particular this approach for substitution-permutation networks. To illustrate our method, we provide low-data distinguishers against reduced-round Present. These distinguishers reach a much higher number of rounds than generic distinguishers based on the division property and demonstrate, amongst others, how the distinguishers can be improved when the properties of the linear and the Sbox layer are taken into account. At last, this work provides an analysis of the resistance of Sboxes against this type of attacks, demonstrates links with the algebraic normal form of an Sbox as well as its inverse Sbox and exhibit design criteria for Sboxes to resist such attacks.

This paper focuses on a surprising class of cryptanalysis results for symmetric-key primitives: when the number of rounds of the primitive is increased, the complexity of the cryptanalysis result decreases. Our primary target will be primitives that consist of identical round functions, such as PBKDF1, the Unix password hashing algorithm, and the Chaskey MAC function. However, some of our results also apply to constructions with non-identical rounds, such as the PRIDE block cipher. First, we construct distinguishers for which the data complexity decreases when the number of rounds is increased. They are based on two well-known observations: iterating a random permutation increases the expected number of fixed points, and iterating a random function decreases the expected number of image points. We explain that these effects also apply to components of cryptographic primitives, such as a round of a block cipher. Second, we introduce a class of key-recovery and preimage-finding techniques that correspond to exhaustive search, however on a smaller part (e.g. one round) of the primitive. As the time complexity of a cryptanalysis result is usually measured by the number of full-round evaluations of the primitive, increasing the number of rounds will lower the time complexity. None of the observations in this paper result in more than a small speed-up over exhaustive search. Therefore, for lightweight applications, implementation advantages may outweigh the presence of these observations.

It has been proved in Eurocrypt 2016 that if the details of the S-boxes are not exploited, an impossible differential and a zero-correlation hull can extend over at most 4 rounds of the AES. This paper concentrates on distinguishing attacks on AES-like SPN ciphers by investigating the details of both the S-boxes and the MDS matrices and illustrates some new insights on the security of these schemes. Firstly, we construct several types of $5$-round zero-correlation linear hulls for AES-like ciphers that adopt identical S-boxes to construct the round function and that have two identical elements in a column of the inverse of their MDS matrices. We then use these linear hulls to construct 5-round integrals provided that the difference of two sub-key bytes is known. Furthermore, we prove that we can always distinguish 5 rounds of such ciphers from random permutations even when the difference of the sub-keys is unknown. Secondly, the constraints for the S-boxes and special property of the MDS matrices can be removed if the cipher is used as a building block of the Miyaguchi-Preneel hash function. As an example, we construct two types of 5-round distinguishers for the hash function Whirlpool. Finally, we show that, in the chosen-ciphertext mode, there exist some nontrivial distinguishers for 5-round AES. To the best of our knowledge, this is the longest distinguishing attack for the round-reduced AES in the secret-key setting. Since the 5-round distinguisher for the AES can only be constructed in the chosen-ciphertext mode, the security margin for the round-reduced AES under the chosen-plaintext attack may be different from that under the chosen-ciphertext attack.

One of the submissions to the CAESAR competition for the design of a new authenticated encryption scheme is Offset Merkle-Damgård (OMD). At FSE 2015, Reyhanitabar et al. introduced p-OMD, an improvement of OMD that processes the associated data almost for free. As an extra benefit, p-OMD was claimed to offer integrity against nonce-misusing adversaries, a property that OMD does not have. In this work we show how a nonce-misusing adversary can forge a message for the original p-OMD using only 3 queries (including the forgery). As a second contribution, we generalize and simplify p-OMD. This is done via the introduction of the authenticated encryption scheme Spoed. The most important difference is the usage of a generalized padding function GPAD, which neatly eliminates the need for a case distinction in the design specification and therewith allows for a significantly shorter description of the scheme and a better security bound. Finally, we introduce the authenticated encryption scheme Spoednic, a variant of Spoed providing authenticity against a nonce-misusing adversary at a modest price.

We present XPX, a tweakable blockcipher based on a single permutation P. On input of a tweak (t_{11},t_{12},t_{21},t_{22}) in T and a message m, it outputs ciphertext c=P(m xor Delta_1) xor Delta_2, where Delta_1=t_{11}k xor t_{12}P(k) and Delta_2=t_{21}k xor t_{22}P(k). Here, the tweak space T is required to satisfy a certain set of trivial conditions (such as (0,0,0,0) not in T). We prove that XPX with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of XPX under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that XPX achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of T. For instance, if t_{12},t_{22} neq 0 and (t_{21},t_{22}) neq (0,1) for all tweaks, XPX is XOR-related-key secure. XPX generalizes Even-Mansour (EM), but also Rogaway's XEX based on EM, and various other tweakable blockciphers. As such, XPX finds a wide range of applications. We show how our results on XPX directly imply related-key security of the authenticated encryption schemes Prøst-COPA and Minalpher, and how a straightforward adjustment to the MAC function Chaskey and to keyed Sponges makes them provably related-key secure.

The CAESAR competition aims to provide a portfolio of authenticated encryption algorithms. SAT solvers represent powerful tools to verify automatically and efficiently (among others) the confidentiality and the authenticity of information claimed by cryptographic primitives. In this work, we study the security of the CAESAR candidate ACORN against a SAT-based cryptanalysis. We provide the first practical and efficient attacks on the first and the last versions of ACORN. More precisely, we achieve state recovery, key recovery, state collision as well as forgery attacks. All our results demonstrate the usefulness of SAT solvers to cryptanalyse all the candidates of the CAESAR competition, thereby accelerating the "test of time".

Statistical analysis of attacks on block ciphers have mostly used normal approximations. A few recent works have proposed doing away with normal approximations and instead use Chernoff and Hoeffding bounds to obtain rigorous bounds on data complexities of several attacks. This opens up the question of whether even better general bounds can be obtained using the statistical theory of large deviations. In this note we examine this question. Our conclusion is that while in theory this is indeed possible, in general obtaining meaningful expressions for data complexity presents several difficulties. This leaves open the question of whether this can be done for specific attacks.

In this paper, we propose a guess and determine attack against some variants of the π-Cipher family of authenticated ciphers. This family of ciphers is a second-round candidate of the CAESAR competition. More precisely, we show a key recovery attack with time complexity little higher than 24^ω, and low data complexity, against variants of the cipher with ω-bit words, when the internal permutation is reduced to 2.5 rounds. In particular, this gives an attack with time complexity 2^72 against the variant π16-Cipher096 (using 16-bit words) reduced to 2.5 rounds, while the authors claim 96 bits of security with 3 rounds in their second-round submission. Therefore, the security margin for this variant of π-Cipher is very limited. The attack can also be applied to lightweight variants that are not included in the CAESAR proposal, and use only two rounds. The lightweight variants π16-Cipher096 and π16-Cipher128 claim 96 bits and 128 bits of security respectively, but our attack can break the full 2 rounds with complexity 2^72. Finally, the attack can be applied to reduced versions of two more variants of π-Cipher that were proposed in the first-round submission with 4 rounds: π16-Cipher128 (using 16-bit words) and π32-Cipher256 (using 32-bit words). The attack on 2.5 rounds has complexity 2^72 and 2^137 respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.

Key schedules in block ciphers are often highly simplified, which causes weakness that can be exploited in many attacks. At ASIACRYPT 2011, Dunkelman et al. proposed a technique using the weakness in the key schedule of AES, called key-bridging technique, to improve the overall complexity. The advantage of key-bridging technique is that it allows the adversary to deduce some sub-key bits from some other sub-key bits, even though they are separated by many key mixing steps. Although the relations of successive rounds may be easy to see, the relations of two rounds separated by some mixing steps are very hard to find. In this paper, we describe a versatile and powerful algorithm for searching key-bridging technique on word-oriented and bit-oriented block ciphers. To demonstrate the usefulness of our approach, we apply our tool to the impossible differential and multidimensional zero correlation linear attacks on 23-round LBlock, 23-round TWINE-80 and 25-round TWINE-128. To the best of our knowledge, these results are the currently best results on LBlock and TWINE in the single-key setting.

Ascon is an authenticated encryption algorithm which is recently qualified for the second-round of the Competition for Authenticated Encryption: Security, Applicability, and Robustness. So far, successful differential, differential-linear, and cube-like attacks on the reduced-round Ascon are provided. In this work, we provide the inverse of Ascon's linear layer in terms of rotations which can be used for constructing impossible differentials. We show that Ascon's S-box contains 35 undisturbed bits and we use them to construct 4 and 5-round truncated, impossible, and improbable differential distinguishers. Our results include practical 4-round truncated, impossible, and improbable differential attacks on Ascon. Our best attacks using these techniques break 5 out of 12 rounds. These are the first successful truncated, impossible, and improbable differential attacks on the reduced-round Ascon.

In recent work, Bellare, Hoang, and Keelveedhi (CRYPTO 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed how they can replace random oracles (ROs) across a wide range of cryptosystems. We formulate a new framework, called Interactive Computational Extractors (ICEs), that extends UCEs by viewing them as models of ROs under unpredictable (aka. high-entropy) queries. We overcome a number of limitations of UCEs in the new framework, and in particular prove the adaptive RKA and semi-adaptive KDM securities of a highly efficient symmetric encryption scheme using ICEs under key offsets. We show both negative and positive feasibility results for ICEs. On the negative side, we demonstrate ICE attacks on the HMAC and NMAC constructions. On the positive side we show that: 1) ROs are indeed ICE secure, thereby confirming the structural soundness of our definition and enabling a finer layered approach to protocol design in the RO model; and 2) a modified version of Liskov's Zipper Hash is ICE secure with respect to an underlying fixed- input-length RO, for appropriately restricted classes of adversaries. This brings the first result closer to practice by moving away from variable-input- length ROs. Our security proofs employ techniques from indifferentiability in multi-stage settings.

In previous work I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the enciphering function. In this paper I propose the fully homomorphic encryption scheme with non-zero isotropic octonions. I improve the previous scheme by adopting the non-zero isotropic octonions so that the “m and -m attack” is not useful because in proposed scheme many ciphertexts exist where the plaintext m is not zero and the norm is zero. The improved scheme is based on multivariate algebraic equations with high degree or too many variables while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. The improved scheme is against the Gröbner basis attack.

Linear mappings are crucial components of symmetric ciphers. A special type of linear mappings are (0,1)-matrices which have been used in symmetric ciphers such as ARIA, E2 and Camellia as diffusion layers with efficient implementation. Bitwise linear maps are also used in symmetric ciphers such as SHA family of hash functions and HC family of stream ciphers. In this article, we investigate a special kind of linear mappings: based upon this study, we propose several linear mappings with only XOR and rotation operations. The corresponding matrices of these mappings can be used in either the former case as (0,1)-matrices of maximal branch number or in the latter case as linear mappings with good cryptographic properties. The proposed mappings and their corresponding matrices can be efficiently implemented both in software and hardware.

An authenticated encryption scheme is deemed secure (AE) if ciphertexts both look like random bitstrings and are unforgeable. AE is a much stronger notion than the traditional IND--CCA. One shortcoming of AE as commonly understood is its idealized, all-or-nothing decryption: if decryption fails, it will always provide the \emph{same single} error message \emph{and nothing more}. Reality often turns out differently: encode-then-encipher schemes often output decrypted ciphertext before verification has taken place whereas pad-then-MAC-then-encrypt schemes are prone to distinguishable verification failures due to the subtle interaction between padding and the MAC-then-encrypt concept. Three recent papers provided what appeared independent and radically different definitions to model this type of decryption leakage. We reconcile these three works by providing a reference model of security for authenticated encryption in the face of decryption leakage from invalid queries. Having tracked the development of AE security games, we provide a single expressive framework allowing us to compare and contrast the previous notions. We find that at their core, the notions are essentially equivalent, with their key differences stemming from definitional choices independent of the desire to capture real world behaviour.

Walsh-Hadamard transform is used in a wide variety of scientific and engineering applications, including bent functions and cryptanalytic optimization techniques in cryptography. In linear cryptanalysis, it is a key question to find a good linear approximation, which holds with probability $(1+d)/2$ and the bias $d$ is large in absolute value. Lu and Desmedt (2011) take a step toward answering this key question in a more generalized setting and initiate the work on the generalized bias problem with linearly-dependent inputs. In this paper, we give fully extended results. Deep insights on assumptions behind the problem are given. We take an information-theoretic approach to show that our bias problem assumes the setting of the maximum input entropy subject to the input constraint. By means of Walsh transform, the bias can be expressed in a simple form. It incorporates Piling-up lemma as a special case. Secondly, as application, we answer a long-standing open problem in correlation attacks on combiners with memory. We give a closed-form exact solution for the correlation involving the multiple polynomial of any weight \emph{for the first time}. We also give Walsh analysis for numerical approximation. An interesting bias phenomenon is uncovered, i.e., for even and odd weight of the polynomial, the correlation behaves differently. Thirdly, we introduce the notion of weakly biased distribution, and study bias approximation for a more general case by Walsh analysis. We show that for weakly biased distribution, Piling-up lemma is still valid. Our work shows that Walsh analysis is useful and effective to a broad class of cryptanalysis problems.

In the present paper, we investigate the problem of constructing MDS matrices with as few bit XOR operations as possible. The key contribution of the present paper is constructing MDS matrices with entries in the set of $m\times m$ non-singular matrices over $\mathbb{F}_2$ directly, and the linear transformations we used to construct MDS matrices are not assumed pairwise commutative. With this method, it is shown that circulant involutory MDS matrices, which have been proved do not exist over the finite field $\mathbb{F}_{2^m}$, can be constructed by using non-commutative entries. Some constructions of $4\times4$ and $5\times5$ circulant involutory MDS matrices are given when $m=4,8$. To the best of our knowledge, it is the first time that circulant involutory MDS matrices have been constructed. Furthermore, some lower bounds on XORs that required to evaluate one row of circulant and Hadamard MDS matrices of order 4 are given when $m=4,8$. Some constructions achieving the bound are also given, which have fewer XORs than previous constructions.

In this note, we describe attacks on the recently proposed Haraka hash functions. First, for the two hash functions Haraka-256/256 and Haraka-512/256 in the family, we show how two colliding messages can be constructed in about $2^{16}$ function evaluations. Second, we invalidate the preimage security claim for Haraka-512/256 with an attack finding one preimage in about $2^{192}$ function evaluations. These attacks are possible thanks to symmetries in the internal state that are preserved over several rounds.

We reconsider the formalization of known-key attacks against ideal primitive-based block ciphers. This was previously tackled by Andreeva, Bogdanov, and Mennink (FSE 2013), who introduced the notion of known-key indifferentiability. Our starting point is the observation, previously made by Cogliati and Seurin (EUROCRYPT 2015), that this notion, which considers only a single known key available to the attacker, is too weak in some settings to fully capture what one might expect from a block cipher informally deemed resistant to known-key attacks. Hence, we introduce a stronger variant of known-key indifferentiability, where the adversary is given multiple known keys to ``play'' with, the informal goal being that the block cipher construction must behave as an independent random permutation for each of these known keys. Our main result is that the 9-round iterated Even-Mansour construction (with the trivial key-schedule, i.e., the same round key xored between permutations) achieves our new ``multiple'' known-keys indifferentiability notion, which contrasts with the previous result of Andreeva et al. that one single round is sufficient when only a single known key is considered. We also show that the 3-round iterated Even-Mansour construction achieves the weaker notion of multiple known-keys sequential indifferentiability, which implies in particular that it is correlation intractable with respect to relations involving any (polynomial) number of known keys.

Filter generators are vulnerable to several attacks which have led to well-known design criteria on the Boolean filtering function. However, Rønjom and Cid have observed that a change of the primitive root defining the LFSR leads to several equivalent generators. They usually offer different security levels since they involve filtering functions of the form F(x^k) where k is coprime to (2^n-1) and n denotes the LFSR length. It is proved here that this monomial equivalence does not affect the resistance of the generator against algebraic attacks, while it usually impacts the resistance to correlation attacks. Most importantly, a more efficient attack can often be mounted by considering non-bijective monomial mappings. In this setting, a divide-and-conquer strategy applies based on a search within a multiplicative subgroup of F_{2^n}^*. Moreover, if the LFSR length n is not a prime, a fast correlation involving a shorter LFSR can be performed.

While \textsf{Salsa} and \textsf{ChaCha} are well known software oriented stream ciphers, since the work of Aumasson et al in FSE 2008 there aren't many significant results against them. The basic model of their attack was to introduce differences in the IV bits, obtain biases after a few forward rounds, as well as to look at the Probabilistic Neutral Bits (PNBs) while reverting back. In this paper we first consider the biases in the forward rounds, and estimate an upper bound on the number of rounds till such biases can be observed. For this, we propose a hybrid model (under certain assumptions), where initially the nonlinear rounds as proposed by the designer are considered, and then we employ their linearized counterpart. The effect of reverting the rounds with the idea of PNBs is also considered. Based on the assumptions and analysis, we conclude that 12 rounds of \textsf{Salsa} and \textsf{ChaCha} should be considered sufficient for 256-bit keys under the current best known attack models.

ICEPOLE is a family of authenticated encryptions schemes submitted to the ongoing CAESAR competition and in addition presented at CHES 2014. To justify the use of ICEPOLE, or to point out potential weaknesses, third-party cryptanalysis is needed. In this work, we evaluate the resistance of ICEPOLE-128 against forgery attacks. By using differential cryptanalysis, we are able to create forgeries from a known ciphertext-tag pair with a probability of $2^{-60.3}$ for a round-reduced version of ICEPOLE-128, where the last permutation is reduced to 4 (out of 6) rounds. This is a noticeable advantage compared to simply guessing the right tag, which works with a probability of $2^{-128}$. As far as we know, this is the first published attack in a nonce-respecting setting on round-reduced versions of ICEPOLE-128.

While impossible differential cryptanalysis is a well-known and popular cryptanalytic method, errors in the analysis are often discovered and many papers in the literature present flaws. Wishing to solve that, Boura \textit{et al.} presented at ASIACRYPT'14 a generic vision of impossible differential attacks with the aim of simplifying and helping the construction and verification of this type of cryptanalysis. In particular, they gave generic complexity analysis formulas for mounting such attacks and develop new ideas for optimizing them. In this paper we carefully study this generic formula and show impossible differential attacks for which the real time complexity is much higher than estimated by it. In particular, we show that the impossible differential attack against 25-round TWINE-128, presented at FSE'15 by Biryukov \textit{et al.}, actually has a complexity higher than the natural bound of exhaustive search.

NXP Semiconductors and its academic partners challenged the cryptographic community with finding practical attacks on the block cipher they designed, PRINCE. Instead of trying to attack as many rounds as possible using attacks which are usually impractical despite being faster than brute-force, the challenge invites cryptographers to find practical attacks and encourages them to actually implement them. In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the 4, 6 and 8-round categories --- the highest for which winners were identified. Our first attacks rely on a meet-in-the-middle approach and break up to 10 rounds of the cipher. We also describe heuristic methods we used to find practical SAT-based and differential attacks. Finally, we also present an analysis of the cycle structure of the internal rounds of PRINCE leading both to a low complexity distinguisher for 4-round PRINCE-core and an alternative representation of the cipher valid in particular contexts and which highlights, in this cases, a poor diffusion.

Telegram is a popular messaging app which supports end-to-end encrypted communication. In Spring 2015 we performed an audit of Telegram's source code. This short paper summarizes our findings. Our main discovery is that the symmetric encryption scheme used in Telegram -- known as MTProto -- is not IND-CCA secure, since it is possible to turn any ciphertext into a different ciphertext that decrypts to the same message. We stress that this is a theoretical attack on the definition of security and we do not see any way of turning the attack into a full plaintext-recovery attack. At the same time, we see no reason why one should use a less secure encryption scheme when more secure (and at least as efficient) solutions exist. The take-home message (once again) is that well-studied, provably secure encryption schemes that achieve strong definitions of security (e.g., authenticated-encryption) are to be preferred to home-brewed encryption schemes.

We provide an improved complexity analysis of backtracking-based state recovery attacks on RC4 and Spritz. Comparing new estimates with known results on Spritz, our analysis shows a significantly lower complexity estimate for simple state recovery attack as well as special state recovery attack. We validated the estimates by performing experiments for selected feasible parameters. We also propose a prefix check optimization for simple state recovery attack on Spritz. We believe that the simple state recovery attack with this optimization and so-called ``change order'' optimization inspired by Knudsen et al. attack on RC4 constitutes currently the best state recovery attack on Spritz (when no special state is observed).

The cryptographic algorithms AES and Twofish guarantee a high diffusion by the use of fixed 4x4 MDS matrices. In this article variations to the algorithms AES and Twofish are made. They allow that the process of cipher - decipher come true with MDS matrices selected randomly from the set of all MDS matrices with the use of proposed algorithm. A new key schedule with a high diffusion is designed for the algorithm AES. Besides proposed algorithm generate new S - box that depends of the key.

We study two open problems proposed by Wagner in his seminal work on the generalized birthday problem. First, with the use of multicollisions, we improve Wagner's $3$-tree algorithm. The new 3-tree only slightly outperforms Wagner's 3-tree, however, in some applications this suffices, and as a proof of concept, we apply the new algorithm to slightly reduce the security of two CAESAR proposals. Next, with the use of multiple collisions based on Hellman's table, we give improvements to the best known time-memory tradeoffs for the k-tree. As a result, we obtain the a new tradeoff curve T^2 \cdot M^{\lg k -1} = k \cdot N. For instance, when k=4, the tradeoff has the form T^2 M = 4 \cdot N.

Several improvements of fast correlation attacks have been proposed during the past two decades, with a regrettable lack of a better generalization and adaptation to the concrete involved primitives, especially to those modern stream ciphers based on word-based LFSRs. In this paper, we develop some necessary cryptanalytic tools to bridge this gap. First, a formal framework for fast correlation attacks over extension fields is constructed, under which the theoretical predictions of the computational complexities for both the offline and online/decoding phase can be reliably derived. Our decoding algorithm makes use of Fast Walsh Transform (FWT) to get a better performance. Second, an efficient algorithm to compute the large-unit distribution of a broad class of functions is proposed, which allows to find better linear approximations than the bitwise ones with low complexity in symmetric-key primitives. Last, we apply our methods to SNOW 2.0, an ISO/IEC 18033-4 standard stream cipher, which results in the significantly reduced complexities all below 2^164.15. This attack is more than 2^49 times better than the best published result at Asiacrypt 2008. Our results have been verified by experiments on a small-scale version of SNOW 2.0.

We show several constructions based on the AES round function that can be used as building blocks for MACs and authenticated encryption schemes. They are found by a search of the space of all secure constructions based on an efficient design strategy that has been shown to be one of the most optimal among all the considered. We implement the constructions on the latest Intel's processors. Our benchmarks show that on Intel Skylake the smallest construction runs at 0.188 c/B, while the fastest at only 0.125 c/B, i.e. five times faster than AES-128.

In May 2012, a highly advanced malware for espionage dubbed Flame was found targeting the Middle-East. As it turned out, it used a forged signature to infect Windows machines by MITM-ing Windows Update. Using counter-cryptanalysis, Stevens found that the forged signature was made possible by a chosen-prefix attack on MD5 \cite{DBLP:conf/crypto/Stevens13}. He uncovered some details that prove that this attack differs from collision attacks in the public literature, yet many questions about techniques and complexity remained unanswered. In this paper, we demonstrate that significantly more information can be deduced from the example collision. Namely, that these details are actually sufficient to reconstruct the collision attack to a great extent using some weak logical assumptions. In particular, we contribute an analysis of the differential path family for each of the four near-collision blocks, the chaining value differences elimination procedure and a complexity analysis of the near-collision block attacks and the associated birthday search for various parameter choices. Furthermore, we were able to prove a lower-bound for the attack's complexity. This reverse-engineering of a non-academic cryptanalytic attack exploited in the real world seems to be without precedent. As it allegedly was developed by some nation-state(s), we discuss potential insights to their cryptanalytic knowledge and capabilities.

Hash functions have been among the most scrutinized cryptographic primitives in the previous decade, mainly due to the cryptanalysis breakthroughs on MD-SHA family and the NIST SHA3 competition that followed. GRINDAHL is a hash function proposed at FSE 2007 that inspired several SHA3 candidates. One of its particularities is that it follows the RIJNDAEL design strategy, with an efficiency comparable to SHA2. This paper provides the first cryptanalytic work on this scheme and we show that the 256-bit version of GRINDAHL is not collision resistant. Our attack uses byte-level truncated differentials and leverages a counterintuitive method (reaching an internal state where all bytes are active) in order to ease the construction of good differential paths. Then, by a careful utilization of the freedom degrees inserted every round, and with a work effort of approximatively $2^{112}$ hash computations, an attacker can generate a collision for the full 256-bit version of GRINDAHL.

We provide new bounds for the pseudo-random function security of keyed sponge constructions. For the case $c\leq b/2$ ($c$ the capacity and $b$ the permutation size), our result improves over all previously-known bounds. A remarkable aspect of our bound is that dependence between capacity and message length is removed, partially solving the open problem posed by Gaži~et~al. at CRYPTO~2015. Our bound is essentially tight, matching the two types of attacks pointed out by Gaži~et~al. For the case $c>b/2$, Gaži~et~al.'s bound remains the best for the case of single-block output, but for keyed sponges with extendable outputs, our result partly (when query complexity is relatively large) provides better security than Mennink~et~al.'s bound presented at ASIACRYPT~2015.

Ciphers that do not use S-boxes have been discussed for the demand on lightweight cryptosystems, and their round functions consist of and, rotation, and xor. Especially, the Simon family is one of the most famous ciphers, and there are many cryptanalyses again the Simon family. However, it is very difficult to guarantee the security because we cannot use useful techniques for S-box-based ciphers. Very recently, the division property, which is a new technique to find integral characteristics, was shown in Eurocrypt 2015. The technique is powerful for S-box-based ciphers, and it was used to break, for the first time, the full MISTY1 in CRYPTO 2015. However, it has not been applied to non-S-box-based ciphers like the Simon family effectively, and only the existence of the 10-round integral characteristic on Simon32 was proven. On the other hand, the experimental characteristic, which possibly does not work for all keys, covers 15 rounds, and there is a 5-round gap. To fill the gap, we introduce a bit-based division property, and we apply it to show that the experimental 15-round integral characteristic always works for all keys. Though the bit-based division property finds more accurate integral characteristics, it requires much time and memory complexity. As a result, we cannot apply it to symmetric-key ciphers whose block length is over 32. Therefore, we alternatively propose a method for designers. The method works for ciphers with large block length, and it shows ``provable security'' against integral cryptanalyses using the division property. We apply this technique to the Simon family and show that Simon48, 64, 96, and 128 probably do not have 17-, 20-, 25-, and 29-round integral characteristics, respectively.

A constrained pseudorandom function (CPRF) $F \colon {\cal K} \times {\cal X} \to {\cal Y}$ for a family ${\cal T}$ of subsets of $\cal X$ is a function where for any key $k \in {\cal K}$ and set $S \in {\cal T}$ one can efficiently compute a short constrained key $k_S$, which allows to evaluate $F(k,\cdot)$ on all inputs $x \in S$, while the outputs on all inputs $x \notin S$ look random even given $k_S$. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets $S$ are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine $M$ as a short signature on $M$. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.

Multiplicative complexity is a complexity measure defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT). Implementations of ciphers with a small number of AND gates are preferred in protocols for fully homomorphic encryption, multi-party computation and zero-knowledge proofs. In 2002, Fischer and Peralta showed that the number of $n$-variable Boolean functions with multiplicative complexity one equals $2\binom{2^n}{3}$. In this paper, we study Boolean functions with multiplicative complexity 2. By characterizing the structure of these functions in terms of affine equivalence relations, we provide a closed form formula for the number of Boolean functions with multiplicative complexity 2.

At Eurocrypt 2016, Méaux et al. proposed FLIP, a new family of stream ciphers intended for use in Fully Homomorphic Encryption systems. Unlike its competitors which either have a low initial noise that grows at each successive encryption, or a high constant noise, the FLIP family of ciphers achieves a low constant noise thanks to a new construction called filter permutator. In this paper, we present an attack on the early version of FLIP that exploits the structure of the filter function and the constant internal state of the cipher. Applying this attack to the two instantiations proposed by Méaux et al. allows for a key recovery in $2^{54}$ basic operations (resp. $2^{68}$), compared to the claimed security of $2^{80}$ (resp. $2^{128}$).

We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form l(x)p(x), where l(x) is a polynomial of small degree and p(x) is a primitive polynomial. It is shown that, their adjacency graphs are closely related to the association graph of l(x) and the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of this method, we explicitly calculate the adjacency graphs of LFSRs with characteristic polynomials of the form (1+x+x^3+x^4)p(x), and construct a large class of De Bruijn sequences from them.

The meet-in-the-middle (MITM) attack has prove to be efficient in analyzing the AES block cipher. Its efficiency has been increasing with the introduction of various techniques such as differential enumeration, key-dependent sieve, super-box etc. The recent MITM attack given by Li and Jin has successfully mounted to 10-round AES-256. Crypton is an AES-like block cipher. In this paper, we apply the MITM method to the cryptanalysis of Crypton-256. Following Li and Jin's idea, we give the first 6-round distinguisher for Crypton. Based on the distinguisher as well as the properties of Crypton's simple key schedule, we successfully launch MITM attacks on Crypton-256 reduced to 9 and 10 rounds. For 9-round Crypton-256, our MITM attack can recover the 256-bit key with a time complexity $2^{173.05}$, a memory complexity $2^{241.17}$. For the 10-round version, we give two MITM attacks. The basic attack requires a time complexity $2^{240.01}$ and memory complexity $2^{241.59}$. The time/memory complexity of the advanced MITM attack on 10-round Crypton is $2^{245.05}/2^{209.59}$. Our MITM attacks share the same data complexity $2^{113}$ and their error rates are negligible.

We are at the dawn of a hyper connectivity age otherwise known as the Internet of Things (IoT). It is widely accepted that to be able to reap all benefits from the IoT promise, device security will be of paramount importance. A key requirement for most security solutions is the ability to provide secure cryptographic key storage in a way that will easily scale in the IoT age. In this paper, we focus on providing such a solution based on Physical Unclonable Functions (PUFs). To this end, we focus on microelectromechanical systems (MEMS)-based gyroscopes and show via wafer-level measurements and simulations, that it is feasible to use the physical and electrical properties of these sensors for cryptographic key generation. After identifying the most promising features, we propose a novel quantization scheme to extract bit strings from the MEMS analog measurements. We provide upper and lower bounds for the minimum entropy of the bit strings derived from the measurements and fully analyze the intra- and inter-class distributions across the operation range of the MEMS device. We complement these measurements via Monte-Carlo simulations based on the distributions of the parameters measured on actual devices. We also propose and evaluate a key derivation procedure based on fuzzy extractors for Hamming distance, using the min-entropy estimates obtained to derive a full entropy 128-bit key, requiring 1219-bits of helper data with an (authentication) failure probability of 4x10^-7. Thereby, we present a complete cryptographic key generation chain. In addition, we propose a dedicated MEMS-PUF design, which is superior to our measured sensor, in terms of chip area, quality and quantity of key seed features.

In this short note we report on invariant subspaces in Simpira in the case of four registers. In particular, we show that the whole input space (respectively output space) can be partitioned into invariant cosets of dimension $56$ over $\F_{2^8}^{64}$. These invariant subspaces are found by exploiting the \emph{non-invariant} subspace properties of AES together with the particular choice of Feistel configuration. Though we give the invariant subspaces for $b=4$ in this paper, we remark that there are invariant subspaces in several of the Simpira instances; these can be determined with only minor adjustments to the analysis in this paper.

At Crypto 2015, Blondeau et al. showed a known-key analysis on the full PRESENT lightweight block cipher. Based on some of the best differential distinguishers, they introduced a meet in the middle (MitM) layer to pre-add the differential distinguisher, which extends the number of attacked rounds on PRESENT from 26 rounds to full rounds without reducing differential probability. In this paper, we generalize their method and present a distinguisher on a kind of permutations called PRESENT-like permutations. This generic distinguisher is divided into two phases. The first phase is a truncated differential distinguisher with strong bias, which describes the unbalancedness of the output collision on some fixed bits, given the fixed input in some bits, and we take advantage of the strong relation between truncated differential probability and capacity of multidimensional linear approximation to derive the best differential distinguishers. The second phase is the meet-in-the-middle layer, which is pre-added to the truncated differential to propagate the differential properties as far as possible. Different with Blondeau et al.'s work, we extend the MitM layers on a 64-bit internal state to states with any size, and we also give a concrete bound to estimate the attacked rounds of the MitM layer. As an illustration, we apply our technique to all versions of SPONGENT permutations. In the truncated differential phase, as a result we reach one, two or three rounds more than the results shown by the designers. In the meet-in-the-middle phase, we get up to 11 rounds to pre-add to the differential distinguishers. Totally, we improve the previous distinguishers on all versions of SPONGENT permutations by up to 13 rounds.

The fresh re-keying scheme is a countermeasure designed to protect low-cost devices against side-channel attacks. In this paper, we present a new birthday-type attack based on a refined reduction to Ring-LPN with a reducible polynomial. Compared with the previous research, our algorithm significantly reduces the time complexity in the 128-bit leakage model—with an SNR equal to 8 and at most $2^{20}$ traces, for instance, the key can be recovered using $2^{41.99}$ bit-operations.

AMAC is a simple and fast candidate construction of a PRF from an MD-style hash function which applies the keyed hash function and then a cheap, un-keyed output transform such as truncation. Spurred by its use in the widely-deployed Ed25519 signature scheme, this paper investigates the provable PRF security of AMAC to deliver the following three-fold message: (1) First, we prove PRF security of AMAC (2) Second, we show that AMAC has a quite unique and attractive feature, namely that its multi-user security is essentially as good as its single-user security and in particular superior in some settings to that of competitors. (3) Third, it is technically interesting, its security and analysis intrinsically linked to security of the compression function in the presence of leakage.

In this work we provide low rank estimations for coordinate sequences of linear recurrent sequences (LRS) of maximal period (MP) over Galois ring $R=GR(p^n,r)$, $p\ge 5$, $r\ge2$, with numbers $s$ such that $s=kr+2$, $k\in \mathbb{N}_0$.

Pseudorandom functions (PRFs) play a central role in symmetric cryptography. While in principle they can be built from any one-way functions by going through the generic HILL (SICOMP 1999) and GGM (JACM 1986) transforms, some of these steps are inherently sequential and far from practical. Naor, Reingold (FOCS 1997) and Rosen (SICOMP 2002) gave parallelizable constructions of PRFs in NC\(^2\) and TC\(^0\) based on concrete number-theoretic assumptions such as DDH, RSA, and factoring. Banerjee, Peikert, and Rosen (Eurocrypt 2012) constructed relatively more efficient PRFs in NC\(^1\) and TC\(^0\) based on ``learning with errors'' (LWE) for certain range of parameters. It remains an open problem whether parallelizable PRFs can be based on the ``learning parity with noise'' (LPN) problem for both theoretical interests and efficiency reasons (as the many modular multiplications and additions in LWE would then be simplified to AND and XOR operations under LPN). In this paper, we give more efficient and parallelizable constructions of randomized PRFs from LPN under noise rate \(n^{-c}\) (for any constant 0<c<1) and they can be implemented with a family of polynomial-size circuits with unbounded fan-in AND, OR and XOR gates of depth \(\omega(1)\), where \(\omega(1)\) can be any small super-constant (e.g., \(\log\log\log{n}\) or even less). Our work complements the lower bound results by Razborov and Rudich (STOC 1994) that PRFs of beyond quasi-polynomial security are not contained in AC\(^0\)(MOD\(_2\)), i.e., the class of polynomial-size, constant-depth circuit families with unbounded fan-in AND, OR, and XOR gates. Furthermore, our constructions are security-lifting by exploiting the redundancy of low-noise LPN. We show that in addition to parallelizability (in almost constant depth) the PRF enjoys either of (or any tradeoff between) the following: (1) A PRF on a weak key of sublinear entropy (or equivalently, a uniform key that leaks any \((1 - o(1))\)-fraction) has comparable security to the underlying LPN on a linear size secret. (2) A PRF with key length \(\lambda\) can have security up to \(2^{O(\lambda/\log\lambda)}\), which goes much beyond the security level of the underlying low-noise LPN. where adversary makes up to certain super-polynomial amount of queries.

We examine the IND-qCPA security of the wide-spread block cipher modes of operation CBC, CFB, OFB, CTR, and XTS (i.e., security against quantum adversaries doing queries in superposition). We show that OFB and CTR are secure assuming that the underlying block cipher is a standard secure PRF (a pseudorandom function secure under classical queries). We give counterexamples that show that CBC, CFB, and XTS are not secure under the same assumption. And we give proofs that CBC and CFB mode are secure if we assume a quantum secure PRF (secure under queries in superposition).

Lightweight cryptography strives to protect communication in constrained environments without sacrificing security. However, security often conflicts with efficiency, shown by the fact that many new lightweight block cipher designs have block sizes as low as 64 or 32 bits. Due to the birthday bound, such low block sizes lead to impractical limits on how much data a mode of operation can process per key. MAC (message authentication code) modes of operation frequently have bounds which degrade with both the number of messages queried and the message length. We present a MAC mode of operation, LightMAC, where the message length has no effect on the security bound, allowing an order of magnitude more data to be processed per key. Furthermore, LightMAC is incredibly simple, has almost no overhead over the block cipher, and is parallelizable. As a result, LightMAC not only offers compact authentication for resource-constrained platforms, but also allows high-performance parallel implementations. We highlight this in a comprehensive implementation study, instantiating LightMAC with PRESENT and the AES. Moreover, LightMAC allows flexible trade-offs between rate and maximum message length. Unlike PMAC and its many derivatives, LightMAC is not covered by patents. Altogether, this makes it a promising authentication primitive for a wide range of platforms and use cases.

In 2015, Todo introduced a property of multisets of a finite field called the division property. It is then used by Todo in an attack against the S7 S-box of the MISTY1 cipher. This paper provides a complete mathematical analysis of the division property. The tool we use is the discrete Fourier transform. We relate the division property to the natural concept of the degree of a subset of a finite field. This indeed provides a characterization of multisets satisfying the division property. In 2015, Sun et al. gave some properties related to the division property. In this paper we give a complete characterization and reprove many of their results. We show that the division property is actually the dual of the degree of $t$-products of the inverse S-box and show these two characteristics are affine invariants. We then propose a very efficient way to check vulnerability of a given S-box against attacks of this type. We also reprove some recent interesting results using the method based on the discrete Fourier transform. We finally check whether the S-boxes of the candidate ciphers in the CAESAR competition are vulnerable against attacks based on the division property.

Juels and Ristenpart introduced honey encryption (HE) and showed how to achieve message recovery security even in the face of attacks that can exhaustively try all likely keys. This is important in contexts like password-based encryption where keys are very low entropy, and HE schemes based on the JR construction were subsequently proposed for use in password management systems and even long-term protection of genetic data. But message recovery security is in this setting, like previous ones, a relatively weak property, and in particular does not prohibit an attacker from learning partial information about plaintexts or from usefully mauling ciphertexts. We show that one can build HE schemes that can hide partial information about plaintexts and that prevent mauling even in the face of exhaustive brute force attacks. To do so, we introduce target-distribution semantic-security and target-distribution non-malleability security notions and proofs that a slight variant of the JR HE construction can meet them. The proofs require new balls-and-bins type analyses significantly different from those used in prior work. Finally, we provide a formal proof of the folklore result that an unbounded adversary which obtains a limited number of encryptions of known plaintexts can always succeed at message recovery.

In this work we study the security of Chaskey, a recent lightweight MAC designed by Mouha et al., currently being considered for standardisation by ISO/IEC and ITU-T. Chaskey uses an ARX structure very similar to SipHash. We present the first cryptanalysis of Chaskey in the single user setting, with a differential-linear attack against 6 and 7 rounds, hinting that the full version of Chaskey with 8 rounds has a rather small security margin. In response to these attacks, a 12-round version has been proposed by the designers. To improve the complexity of the differential-linear cryptanalysis, we refine a partitioning technique recently proposed by Biham and Carmeli to improve the linear cryptanalysis of addition operations. We also propose an analogue improvement of differential cryptanalysis of addition operations. Roughly speaking, these techniques reduce the data complexity of linear and differential attacks, at the cost of more processing time per data. It can be seen as the analogue for ARX ciphers of partial key guess and partial decryption for SBox-based ciphers. When applied to the differential-linear attack against Chaskey, this partitioning technique greatly reduces the data complexity, and this also results in a reduced time complexity. While a basic differential-linear attack on 7 round takes 2^78 data and time (respectively 2^35 for 6 rounds), the improved attack requires only 2^48 data and 2^67 time (respectively 2^25 data and 2^29 time for 6 rounds). We also show an application of the partitioning technique to FEAL-8X, and we hope that this technique will lead to a better understanding of the security of ARX designs.

Integral attacks form a powerful class of cryptanalytic techniques that have been widely used in the security analysis of block ciphers. The integral distinguishers are based on balanced properties holding with probability one. To obtain a distinguisher covering more rounds, an attacker will normally increase the data complexity by iterating through more plaintexts with a given structure under the strict limitation of the full codebook. On the other hand, an integral property can only be deterministically verified if the plaintexts cover all possible values of a bit selection. These circumstances have somehow restrained the applications of integral cryptanalysis. In this paper, we aim to address these limitations and propose a novel \emph{statistical integral distinguisher} where only a part of value sets for these input bit selections are taken into consideration instead of all possible values. This enables us to achieve significantly lower data complexities for our statistical integral distinguisher as compared to those of traditional integral distinguisher. As an illustration, we successfully attack the full-round Skipjack-BABABABA for the first time, which is the variant of NSA's Skipjack block cipher.

Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. In~\cite{P08a}, it is proved that we have security against CPA-2 attacks when $m \ll O(2^n)$, where $m$ is the number of queries and $n$ is the number of bits of the inputs and outputs of the bijections. In this paper, we will obtain similar (but slightly different) results by using the ``standard H technique'' instead of the ``$H_{\sigma}$ technique''. It will be interesting to compare the two techniques, their similarities and the differences between the proofs and the results.

We explore the use of the Mantin biases (Mantin, Eurocrypt 2005) to recover plaintexts from RC4-encrypted traffic. We provide a more fine-grained analysis of these biases than in Mantin's original work. We show that, in fact, the original analysis was incorrect in certain cases: the Mantin biases are sometimes non-existent, and sometimes stronger than originally predicted. We then show how to use these biases in a plaintext recovery attack. Our attack targets two unknown bytes of plaintext that are located close to sequences of known plaintext bytes, a situation that arises in practice when RC4 is used in, for example, TLS. We provide a statistical framework that enables us to make predictions about the performance of this attack and its variants. We then extend the attack using standard dynamic programming techniques to tackle the problem of recovering longer plaintexts, a setting of practical interest in recovering HTTP session cookies and user passwords that are protected by RC4 in TLS. We perform experiments showing that we can successfully recover 16-byte plaintexts with 80% success rate using $2^{31}$ ciphertexts, an improvement over previous attacks.

Standard differential cryptanalysis uses statistical dependencies between the difference of two plaintexts and the difference of the respective two ciphertexts to attack a cipher. Here we introduce polytopic cryptanalysis which considers interdependencies between larger sets of texts as they traverse through the cipher. We prove that the methodology of standard differential cryptanalysis can unambiguously be extended and transferred to the polytopic case including impossible differentials. We show that impossible polytopic transitions have generic advantages over impossible differentials. To demonstrate the practical relevance of the generalization, we present new low-data attacks on round-reduced DES and AES using impossible polytopic transitions that are able to compete with existing attacks, partially outperforming these.

We present TWORAM, the first efficient round-optimal oblivious RAM (ORAM) scheme. TWORAM provides oblivious access of a memory index $y$ in exactly two rounds: The client prepares an encrypted query encapsulating $y$ and sends it to the server. The server accesses memory obliviously and returns encrypted information containing the desired value $\mathsf{M}[y]$. The cost of TWORAM is only a multiplicative factor of security parameter higher than the tree-based ORAM schemes such as the path ORAM of Stefanov et al. (CCS, 2013). TWORAM gives rise to interesting applications, and in particular to the first fully-secure searchable symmetric encryption scheme where search is sublinear and search pattern is not leaked---access pattern can also be concealed if we assume the documents are stored in the obliviously accessed memory $\mathsf{M}$.

CLEFIA is a block cipher developed by Sony Corporation in 2007. It is a recommended cipher of CRYPTREC, and has been adopted as ISO/IEC international standard in lightweight cryptography. In this paper, some new 9-round zero-correlation linear distinguishers of CLEFIA are constructed with the input masks and output masks being independent, which allow multiple zero-correlation linear attacks on 14/15-rounds CLEAIA-192/256 with the partial sum technique. Furthermore, the relations between integral distinguishers and zero-correlation linear approximations are improved, and some new integral distinguishers over 9-round are deduced from zero-correlation linear approximations. By using these integral distinguishers and the partial sum technique, the previous integral results on CLEFIA are improved. The two results have either one more rounds or lower time complexity than previous attack results by means of integral and zero-correlation linear cryptanalysis.

s2n is an implementation of the TLS protocol that was released in late June 2015 by Amazon. It is implemented in around 6,000 lines of C99 code. By comparison, OpenSSL needs around 70,000 lines of code to implement the protocol. At the time of its release, Amazon announced that s2n had undergone three external security evaluations and penetration tests. We show that, despite this, s2n - as initially released - was vulnerable to a timing attack in the case of CBC-mode ciphersuites, which could be extended to complete plaintext recovery in some settings. Our attack has two components. The first part is a novel variant of the Lucky 13 attack that works even though protections against Lucky 13 were implemented in s2n. The second part deals with the randomised delays that were put in place in s2n as an additional countermeasure to Lucky 13. Our work highlights the challenges of protecting implementations against sophisticated timing attacks. It also illustrates that standard code audits are insufficient to uncover all cryptographic attack vectors.

Recent observations on polynomial structures of AES-like round functions are analysed in this note. We present computational evidence that input/output bits of AES-like 2-round transform up to $40$-bit, constructed with $8$-bit AES S-boxes, do not satisfy any relations of degree $3$. So it is very unlikely that actual AES 2-round transform admits any relations of degree $\leq 3$.

There are many kinds of attacks that can be mounted on block ciphers: differential attacks, impossible differential attacks, truncated differential attacks, boomerang attacks. We consider generic differential attacks used as distinguishers for various types of Feistel ciphers: they allow to distinguish a random permutation from a permutation generated by the cipher. These attacks are based on differences between the expectations of random variables defined by relations on the inputs and outputs of the ciphers. Sometimes, one has to use the value of the variance as well. In this paper, we will provide a tool that computes the exact values of these expectations and variances. We first explain thoroughly how these computations can be carried out by counting the number of solutions of a linear systems with equalities and non-equalities. Then we provide the first applications of this tool. For example, it enabled to discover a new geometry in 4-point attacks. It gave an explanation to some phenomena that can appear in simulations when the inputs and outputs have a small number of bits.

We first prove the truthfulness of a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper ``Cryptographic properties of monotone Boolean functions", by D. Joyner, P. Stanica, D. Tang and the author, to appear in the Journal of Mathematical Cryptology. We prove then an upper bound on such nonlinearity, which is asymptotically much stronger than the conjectured upper bound and than the upper bound proved for odd dimension in this same paper. This bound shows a deep weakness of monotone Boolean functions; they are too closely approximated by affine functions for being usable as nonlinear components in cryptographic applications. We deduce a necessary criterion to be satisfied by a Boolean (resp. vectorial) function for being nonlinear.