We study the security of the concatenation combiner $H_1(M) \| H_2(M)$ for two independent iterated hash functions with $n$-bit outputs that are built using the Merkle-Damgård construction. In 2004 Joux showed that the concatenation combiner of hash functions with an $n$-bit internal state does not offer better collision and preimage resistance compared to a single strong $n$-bit hash function. On the other hand, the problem of devising second preimage attacks faster than $2^n$ against this combiner has remained open since 2005 when Kelsey and Schneier showed that a single Merkle-Damgård hash function does not offer optimal second preimage resistance for long messages. In this paper, we develop new algorithms for cryptanalysis of hash combiners and use them to devise the first second preimage attack on the concatenation combiner. The attack finds second preimages faster than $2^n$ for messages longer than $2^{2n/7}$ and has optimal complexity of $2^{3n/4}$. This shows that the concatenation of two Merkle-Damgård hash functions is not as strong a single ideal hash function. Our methods are also applicable to other well-studied combiners, and we use them to devise a new preimage attack with complexity of $2^{2n/3}$ on the XOR combiner $H_1(M) \oplus H_2(M)$ of two Merkle-Damgård hash functions. This improves upon the attack by Leurent and Wang (presented at Eurocrypt 2015) whose complexity is $2^{5n/6}$ (but unlike our attack is also applicable to HAIFA hash functions). Our algorithms exploit properties of random mappings generated by fixing the message block input to the compression functions of $H_1$ and $H_2$. Such random mappings have been widely used in cryptanalysis, but we exploit them in new ways to attack hash function combiners.

We study the weakness of key schedules from an observation: many existing attacks use the fact that the key schedules poorly distribute key bits in the diffusion path of round function. This reminds us of the importance of the diffusion's relation between key schedule and round function. We present new cryptanalysis results by exploring such diffusion relation and propose a new criterion for necessary key schedule diffusion. We discuss potential attacks and summarize the causes for key schedules without satisfying this criterion. One major cause is that overlapping between the diffusion of key schedule and round function leads to information leakage of key bits. Finally, a measure to estimate our criterion for recursive key schedules is presented. Today designing key schedule still lacks practical and necessary principles. For a practical key schedule with limited diffusion, our work adds more insight to its requirements and helps to maximize the security level.

Impossible differential and zero correlation linear cryptanalysis are two of the most important cryptanalytic vectors. To characterize the impossible differentials and zero correlation linear hulls which are independent of the choices of the non-linear components, Sun et al. proposed the structure deduced by a block cipher at CRYPTO 2015. Based on that, we concentrate in this paper on the security of the SPN structure and Feistel structure with SP-type round functions. Firstly, we prove that for an SPN structure, if \alpha_1\rightarrow\beta_1 and \alpha_2\rightarrow\beta_ are possible differentials, \alpha_1|\alpha_2\rightarrow\beta_1|\beta_2 is also a possible differential, i.e., the OR "|" operation preserves differentials. Secondly, we show that for an SPN structure, there exists an r-round impossible differential if and only if there exists an r-round impossible differential \alpha\not\rightarrow\beta where the Hamming weights of both \alpha and \beta are 1. Thus for an SPN structure operating on m bytes, the computation complexity for deciding whether there exists an impossible differential can be reduced from O(2^{2m}) to O(m^2). Thirdly, we associate a primitive index with the linear layers of SPN structures. Based on the matrices theory over integer rings, we prove that the length of impossible differentials of an SPN structure is upper bounded by the primitive index of the linear layers. As a result we show that, unless the details of the S-boxes are considered, there do not exist 5-round impossible differentials for the AES and ARIA. Lastly, based on the links between impossible differential and zero correlation linear hull, we projected these results on impossible differentials to zero correlation linear hulls. It is interesting to note some of our results also apply to the Feistel structures with SP-type round functions.

Handycipher is a low-tech, randomized, symmetric-key, stream cipher, simple enough to permit pen-and-paper encrypting and decrypting of messages, while providing a significantly high level of security. It combines a simple 31-character substitution cipher with a 3,045-token nondeterministic homophonic substitution cipher, and employs the insertion of randomly chosen decoy characters at random locations in the ciphertext. A deniable encryption scheme based on the cipher is described, as well as a way of extending the cipher by using randomly generated session keys.

Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on {\it a short-term bias} in the first two bytes of a keystream and {\it a long-term bias} in the first two bytes of every cycle of $N$ keystream bytes, where $N$ is the size of the internal permutation. Our attacks are able to distinguish a keystream of the {\it full} Spritz from a random sequence with samples of first two bytes produced by $2^{44.8}$ multiple key-IV pairs or $2^{60.8}$ keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the $2^{1400}$ step algorithm of Ankele et al. at Latincrypt 2015.

At Crypto 2015, Blondeau, Peyrin and Wang proposed a truncated-differential-based known-key attack on full PRESENT, a nibble oriented lightweight blockcipher with a SPN structure. The truncated difference they used is derived from the existing multidimensional linear characteristics. An innovative technique of their work is the design of a MITM layer added before the characteristic that covers extra rounds with a complexity lower than that of a generic construction. We notice that there are good linear hulls for bit-oriented block cipher Simon corresponding to highly qualified truncated differential characteristics. Based on these characteristics, we propose known-key distinguishers on round-reduced Simon block cipher family, which is bit oriented and has a Feistel structure. Similar to the MITM layer, we design a specific start-from-the-middle method for pre-adding extra rounds with complexities lower than generic bounds. With these techniques, we launch basic known-key attacks on round-reduced Simon. We also involve some key guessing technique and further extend the basic attacks to more rounds. Our known-key attacks can reach as many as 29/32/38/48/63-rounds of Simon32/48/64/96/128, which comes quite close to the full number of rounds. To the best of our knowledge, these are the first known-key results on the block cipher Simon.

RoadRunneR is a small and fast bitslice lightweight block cipher for low cost 8-bit processors proposed by Adnan Baysal and Sa ̈hap S ̧ahin in the LightSec 2015 conference. While most software efficient lightweight block ciphers lacking a security proof, RoadRunneR’s security is provable against differential and linear attacks. RoadRunneR is a Feistel structure block cipher with 64-bit block size. RoadRunneR-80 is a vision with 80-bit key and 10 rounds, and RoadRunneR-128 is a vision with 128-bit key and 12 rounds. In this paper, we obtain 5-round truncated differentials of RoadRunneR-80 and RoadRunneR-128 with probability 2^{−56}. Using the truncated differentials, we give a truncated differential attack on 7-round RoadRunneR-128 without whitening keys with data complexity of 2^{55} chosen plaintexts, time complexity of 2^{121} encryptions and memory complexity of 2^{68}. This is first known attack on RoadRunneR block cipher.

We show that a distinguishing attack in the related key model on an Even-Mansour block cipher can readily be converted into an extremely efficient key recovery attack. Concerned ciphers include in particular all iterated Even-Mansour schemes with independent keys. We apply this observation to the Caesar candidate Prøst-OTR and are able to recover the whole key with a number of requests linear in its size. This improves on recent forgery attacks in a similar setting.

In this paper security aspects of the existing symmetric key encryption schemes based on Hadamard matrices are examined. Hadamard matrices itself have symmetries like one circulant core or two circulant core. Here, we are exploiting the inherent symmetries of Hadamard matrices and are able to perform attacks on these encryption schemes. It is found that entire key can be obtained by observing the ciphertext.

Multidimensional linear attacks are one of the most powerful variants of linear cryptanalytic techniques now. However, there is no knowledge on the key-dependent capacity and data complexity so far. Their values were assumed to be close to the average value for a vast majority of keys. This assumption is not accurate. In this paper, under a reasonable condition, we explicitly formulate the capacity as a Gamma distribution and the data complexity as an Inverse Gamma distribution, in terms of the average linear potential and the dimension. The capacity distribution is experimentally verified on the 5-round PRESENT. Regarding complexity, we solve the problem of estimating the average data complexity, which was difficult to estimate because of the existence of zero correlations. We solve the problem of using the median complexity in multidimensional linear attacks, which is an open problem since proposed in Eurocrypt 2011. We also evaluate the difference among the median complexity, the average complexity and a lower bound of the average complexity -- the reciprocal of average capacity. In addition, we estimate more accurately the key equivalent hypothesis, and reveal the fact that the average complexity only provides an accurate estimate for less than half of the keys no matter how many linear approximations are involved. Finally, we revisit the so far best attack on PRESENT based on our theoretical result.

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 a fully homomorphic encryption with composite number modulus which avoids the weak point by adopting the plaintext including the random numbers in it. In this paper I propose another fully homomorphic encryption with composite number modulus where the complexity required for enciphering and deciphering is smaller than the same modulus RSA scheme. In the proposed scheme it is proved that if there exists the PPT algorithm that decrypts the plaintext from the any ciphertexts of the proposed scheme, there exists the PPT algorithm that factors the given composite number modulus. In addition it is said that the proposed fully homomorphic encryption scheme is immune from the “p and -p attack”. 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.

This paper investigates the degradation properties of Boolean functions from the aspects of the distributions of dierences and linear masks, and shows two characterizations of the degraded Boolean function. One is that there exists a linear space of the input dierences, where the dierentials with the zero output dierence have probability 1; Another one is that the input linear masks of the nonzero-correlation linear approximations are included in a linear space. Those two linear spaces are orthogonal spaces. Moreover, the degradation properties are showed about the exponentiation type S-box of the SAFER block ciphers, which are applied to reduce the compute complexity in the zero-correlation linear attacks on 5-round SAFER SK/128, 4(5)-round SAFER+/128(256) and 5(6)-round SAFER++/128(256). In the attacks, some of the linear properties of PHT employed as the linear layer by the SAFER block ciphers are investigated and some zero-correlation approximations for SAFER SK, SAFER+, and SAFER++ are identied, when only the least one or two signicant bits are considered. The results show that more rounds of some of the SAFER block ciphers can be attacked, by considering the degradation properties and the zero-correlation linear relations.

In this document we present an introductory overview of the algorithms and design components underlying the Keccac cryptographic primitive and the Keyak encryption scheme for authenticated (session-supporting) encryption. This document aims to familiarize readers with the basic principles of authenticated encryption, the Sponge and Duplex constructions (full-state, keyed as well as regular versions), the permutation functions underlying Keccak and Keyak as well as Keyak v2's Motorist mode of operation.

The reported power analysis attacks on hardware implementations of the MICKEY family of streams ciphers require a large number of power traces. The primary motivation of our work is to break an implementation of the cipher when only a limited number of power traces can be acquired by an adversary. In this paper, we propose a novel approach to mount a Template attack (TA) on MICKEY-128 2.0 stream cipher using Particle Swarm Optimization (PSO) generated initialization vectors (IVs). In addition, we report the results of power analysis against a MICKEY-128 2.0 implementation on a SASEBO-GII board to demonstrate our proposed attack strategy. The captured power traces were analyzed using Least Squares Support Vector Machine (LS-SVM) learning algorithm based binary classifiers to segregate the power traces into the respective Hamming distance (HD) classes. The outcomes of the experiments reveal that our proposed power analysis attack strategy requires a much lesser number of IVs compared to a standard Correlation Power Analysis (CPA) attack on MICKEY-128 2.0 during the key loading phase of the cipher.

In this note, using rather elementary technique and the derived formula that relates the coefficients of a polynomial over a finite field and its derivative, we deduce many interesting results related to derivatives of Boolean functions and derivatives of mappings over finite fields. For instance, we easily identify several infinite classes of polynomials which cannot possess linear structures. The same technique can be applied for deducing a nontrivial upper bound on the degree of so-called planar mappings.

Designing block ciphers and hash functions in a manner that resemble the AES in many aspects has been very popular since Rijndael was adopted as the Advanced Encryption Standard. However, in sharp contrast to the MixColumns operation, the security implications of the way the state is permuted by the operation resembling ShiftRows has never been studied in depth. Here, we provide the first structured study of the influence of ShiftRows-like operations, or more generally, word-wise permutations, in AES-like ciphers with respect to diffusion properties and resistance towards differential- and linear attacks. After formalizing the concept of guaranteed trail weights, we show a range of equivalence results for permutation layers in this context. We prove that the trail weight analysis when using arbitrary word-wise permutations, with rotations as a special case, reduces to a consideration of a specific normal form. Using a mixed-integer linear programming approach, we obtain optimal parameters for a wide range of AES-like ciphers, and show improvements on parameters for Rijndael-192, Rijndael-256, PRIMATEs-80 and Prøst-128. As a separate result, we show for specific cases of the state geometry that a seemingly optimal bound on the trail weight can be obtained using cyclic rotations only for the permutation layer, i.e. in a very implementation friendly way.

A simple cryptographic method, a type of columnar transposition cipher, is described which may be used in series with other methods to provide practical hybrid encryption. The method involves the use of a deterministic Cryptographic Pseudo Random Number Generator (CPRNG) to specify an unbiased random transposition of blocks of plain-text or intermediate text. The decryption process involves applying a reverse transposition at the appropriate stage. The method may be applied at a single stage or several stages. The unit of transposition may be a bit or a byte or larger block. The method, when added in series with existing encryption methods, can deter attacks which exploit known weaknesses. The method could be applied at several scales in order to obscure structures within the plain-text, e.g. at the bit level, to obscure the almost fixed transmission headers; at the computer word-level, to disguise application record structures. Two (incompatible) outline implementations are presented. One for use with a block cipher and one for use with a stream cipher The specification of necessary configuration parameters required to amend or construct a software or hardware implementation is avoided in this preliminary article

In this paper, we construct several tools for building and manipulating pools of statistical correlations in the analysis of RC4. We develop a theory to analyze these correlations in an optimized manner. We leverage this theory to mount several attacks on IEEE 802.11 wireless communication protocols WEP and WPA. Based on several partial temporary key recovery attacks, we recover the full 128-bit temporary key of WPA by using $2^{42}$ packets. It works with complexity $2^{96}$. Then, we describe a distinguisher for WPA with complexity $2^{42}$ and advantage 0.5 which uses $2^{42}$ packets. Moreover, we report extremely fast and optimized active and passive attacks against WEP. This was achieved through an extensive amount of theoretical and experimental analysis (capturing WiFi packets), refinement and optimization of all the former known attacks and methodologies against RC4. Our theory is supported and verified by a patch on top of Aircrack-ng. Our new attack improves its success probability drastically. Our active attack, based on ARP injection, requires 22500 packets to gain success probability of 50\% against a 104-bit WEP key, using Aircrack-ng in non-interactive mode. It runs in less than 5 seconds on an off-the-shelf PC. Using the same number of packets, Aicrack-ng yields around 3\% success rate. Furthermore, we describe very fast passive only attacks by eavesdropping TCP/IPv4 packets in a WiFi communication. Our passive attack requires 27500 packets. This is much less than the number of packets Aircrack-ng requires in active mode (around 37500), which is a significant improvement. We believe that our analysis brings on further insight to the security of RC4.

The Kalyna block cipher has recently been established as the Ukranian encryption standard in June, 2015. It was selected in a Ukrainian National Public Cryptographic Competition running from 2007 to 2010. Kalyna supports block sizes and key lengths of 128, 256 and 512 bits. Denoting the variants of Kalyna as Kalyna-$b/k$, where $b$ denotes the block size and $k$ denotes the keylength, the design specifies $k \in \{b, 2b\}$. In this work, we re-evaluate the security bound of some reduced round Kalyna variants, specifically Kalyna-$128/256$ and Kalyna-$256/512$ against key recovery attacks in the single key model. We first construct new 6-round distinguishers and then use these distinguishers to demonstrate 9-round attacks on these Kalyna variants. These attacks improve the previous best 7-round attacks on the same.\\ Our 9-round attack on Kalyna-128/256 has data, time and memory complexity of $2^{105}$, $2^{245.83}$ and $2^{226.86}$ respectively. For our 9-round attack on Kalyna-256/512, the data/time/memory complexities are $2^{217}$, $2^{477.83}$ and $2^{443.45}$ respectively. The time and data complexities for Kalyna-256/512 reported in this work improve upon the previous best 7-round attack complexities on the same. The attacks presented in this work are currently the best on Kalyna. We apply multiset attack - a variant of meet-in-the-middle attack to achieve these results.

Secret-key authentication protocols have recently received a considerable amount of attention, and a long line of research has been devoted to devising efficient protocols with security based on the hardness of the learning-parity with noise (LPN) problem, with the goal of achieving low communication and round complexities, as well as highest possible security guarantees. In this paper, we construct 2-round authentication protocols that are secure against sequential man-in-the-middle (MIM) attacks with tight reductions to LPN, Field-LPN, or other problems. The best prior protocols had either loose reductions and required 3 rounds (Lyubashevsky and Masny, CRYPTO'13) or had a much larger key (Kiltz et al., EUROCRYPT'11 and Dodis et al., EUROCRYPT'12). Our constructions follow from a new generic deterministic and round-preserving transformation enhancing actively-secure protocols of a special form to be sequentially MIM-secure while only adding a limited amount of key material and computation.

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. In this paper, we extend the formal model of PRNG with input defined by Dodis et al. at CCS 2013 to deal with partial leakage of sensitive information. The resulting security notion, termed leakage-resilient robust PRNG with input, encompasses all the previous notions, but also allows the adversary to continuously get some leakage on the manipulated data. Dodis et al. also proposed an efficient construction, based on simple operations in a finite field and a classical deterministic pseudo-random generator PRG. Here, we analyze this construction with respect to our new stronger security model, and prove that with a stronger PRG, it also resists leakage. We show that this stronger PRG can be obtained by tweaking some existing constructions based on AES. We also propose a new instantiation which may be better in specific cases. Eventually, we show that the resulting scheme remains quite efficient in spite of its new security properties. It can thus be recommended in contexts where side-channel resistance is required.

We prove that a (balanced) 10-round Feistel network is indifferentiable from a random permutation. In a previous seminal result, Holenstein et al. had established indifferentiability of Feistel at 14 rounds. Our simulator achieves security $O(q^8/2^n)$ and query complexity $O(q^4)$, where $n$ is half the block length, similarly to the 14-round simulator of Holenstein et al., so that our result is a strict (and also the first) improvement of that work. Our simulator is very similar to a 10-round simulator of Seurin that was subsequently found to be flawed. Indeed, the main change of our simulator is to switch to "FIFO" path completion from "LIFO" path completion. This relatively minor change results in an overall significant paradigm shift, including a conceptually simpler proof.

In this paper we study authenticated encryption algorithms inspired by the OCB mode (Offset Codebook). These algorithms use secret offsets (masks derived from a whitening key) to turn a block cipher into a tweakable block cipher, following the XE or XEX construction. OCB has a security proof up to 2^n/2 queries, and a matching forgery attack was described by Ferguson, where the main step of the attack recovers the whitening key. In this work we study recent authenticated encryption algorithms inspired by OCB, such as Marble, AEZ, and COPA. While Ferguson’s attack is not applicable to those algorithms, we show that it is still possible to recover the secret mask with birthday complexity. Recovering the secret mask easily leads to a forgery attack, but it also leads to more devastating attacks, with a key-recovery attack against Marble and AEZ v2 and v3 with birthday complexity. For Marble, this clearly violates the security claims of full n-bit security. For AEZ, this matches the security proof, but we believe it is nonetheless a quite undesirable property that collision attacks allow to recover the master key, and more robust designs would be desirable. Our attack against AEZ is generic and independent of the internal permutation (in particular, it still works with the full AES), but the key-recovery is specific to the key derivation used in AEZ v2 and v3. Against Marble, the forgery attack is generic, but the key-recovery exploits the structure of the E permutation (4 AES rounds). In particular, we introduce a novel cryptanalytic method to attack 3 AES rounds followed by 3 inverse AES rounds, which can be of independent interest.

With the growing popularity of remote storage, the ability to outsource a large private database yet be able to search on this encrypted data is critical. Searchable symmetric encryption (SSE) is a practical method of encrypting data so that natural operations such as searching can be performed on this data. It can be viewed as an efficient private-key alternative to powerful tools such as fully homomorphic encryption, oblivious RAM, or secure multiparty computation. The main drawbacks of existing SSE schemes are the limited types of search available to them and their leakage. In this paper, we present a construction of a private outsourced database in the two-server model (e.g. two cloud services) which can be thought of as an SSE scheme on a B-tree that allows for a wide variety of search features such as range queries, substring queries, and more. Our solution can hide all leakage due to access patterns (``metadata'') between queries and features a tunable parameter that provides a smooth tradeoff between privacy and efficiency. This allows us to implement a solution that supports databases which are terabytes in size and contain millions of records with only a 5x slowdown compared to MySQL when the query result size is around 10% of the database, though the fixed costs dominate smaller queries resulting in over 100x relative slowdown (under 1 second actual). In addition, our solution also provides a mechanism for allowing data owners to set filters that prevent prohibited queries from returning any results, without revealing the filtering terms. Finally, we also present the benchmarks of our prototype implementation. This is the full version of the extended abstract to appear at CT-RSA 2016.

In this paper, we present an invariant subspace attack against block cipher Midori64 which has recently been proposed by Banik et al. at Asiacrypt 2015 to achieve low energy consumption. We show that when each nibble of the key has the value 0 or 1 and each nibble of the plaintext has the value 8 or 9, each nibble of the ciphertext also has the value 8 or 9 with probability one regardless of the number of rounds applied. This fact indicates that Midori64 has a class of $2^{32}$ weak keys that can be distinguished with a single query. It also indicates that the number of keys generated uniformly at random for Midori64 must not exceed $2^{96}$, i.e., the pseudorandom-permutation security of Midori64 is only up to 96 bits instead of 128 bits. Interestingly, given the information that the key is from the $2^{32}$ weak key subspace, key recovery can be performed within time complexity $2^{16}$ and data complexity $2^1$. We have confirmed the correctness of the analysis by implementing the attack. At the current stage, our attacks do not apply to Midori128.

The Chaskey MAC algorithm was presented by Mouha et al. at SAC 2014. It is designed for real-world applications where 128-bit keys are required, but standard cryptographic algorithms cannot be implemented because of stringent requirements on speed, energy consumption, or code size. Shortly after its publication, Chaskey was considered for standardization by ISO/IEC JTC 1/SC 27/WG 2. At the October 2015 meeting, the ISO/IEC committee decided to terminate the study period on Chaskey, and to circulate a first working draft. Since Chaskey was introduced, many follow-up results were published, including improved cryptanalysis results, new security proofs and more efficient implementations. This paper gives a comprehensive overview of those results, and introduces a twelve-round variant of Chaskey: Chaskey-12. Although the original eight-round Chaskey remains unbroken, Chaskey-12 has a much more conservative design, while reducing the performance by only 15% to 30%, depending on the platform.

Low-cost resource-constrained devices can allocate very limited resources for implementing security. At the same time, they still require some level of protection. In this paper, we present a lightweight message authentication scheme based on Cyclic Redundancy Check (CRC). The presented CRC inherits the implementation simplicity of the conventional CRC checksum except that the LFSR implementing its encoding and decoding is made re-programmable. Similarly to previously proposed cryptographic CRCs, it detects both random and malicious errors without increasing bandwidth. The main difference from previous approaches is that we use arbitrary instead of irreducible generator polynomials. This eliminates the need for irreducibility tests. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The results show that the presented scheme is particularly suitable for the authentication of short messages.

Midori is a lightweight block cipher designed by Banik et al. at ASIACRYPT 2015. One version of Midori uses a 64-bit state, another uses a 128-bit state and we denote these versions Midori-64 and Midori-128. Each of these versions uses a 128-bit key. In this paper, we focus on the key-recovery attacks on reduced-round Midori-64 with meet-in-the-middle method. We use the differential enumeration technique and key-dependent sieve technique which are popular to analyze AES to attack Midori-64. We propose a 6-round distinguisher, and achieve a 10-round attack with time complexity of 2^{99.5} 10-round Midori-64 encryptions, data complexity of 2^{61.5} chosen-plaintexts and memory complexity of 2^{92.7} 64-bit blocks. After that, by adding one round at the end, we get an 11-round attack with time complexity of 2^{122} 11-round Midori-64 encryptions, data complexity of 2^{53} chosen-plaintexts and memory complexity of 2^{89.2} 64-bit blocks. Finally, with a 7-round distinguisher, we get an attack on 12-round Midori-64 with time complexity of 2^{125.5} 12-round Midori-64 encryptions, data complexity of 2^{55.5} chosen-plaintexts and memory complexity of 2^{106} 64-bit blocks. To the best of our knowledge, this is recently the best attack on Midori-64.

Khudra is a lightweight block cipher designed for Field Programmable Gate Array (FPGA) based platforms. The cipher has an 18-round generalized type-2 Feistel structure with 64-bit block size. The key schedule takes 80-bit master key and produces 32-bit round keys performing very simple operations. In this work, we analyze the security of Khudra. We first show that the effective round key length is 16-bit. By the help of this observation, we improve the 14-round MITM attack proposed by Youssef et al. by reducing the memory complexity from $2^{64.8}$ to $2^{32.8}$. Also, we propose a new guess-and-determine type attack on 14 rounds where only 2 known plaintext-ciphertext pairs are required to mount the attack in a time complexity of $2^{64}$ encryption operations. To the best of our knowledge, this is the best attack in the single key model in terms of time, memory and data complexities where the data complexity is equal to the minimum theoretical data requirement. Moreover, we present two observations on differential probabilities of the round function and the symmetric structure of the cipher. We introduce $2^{40}$ weak keys for the full cipher by exploiting the symmetric structure of the cipher.

This paper presents NORX8 and NORX16, the 8-bit and 16-bit versions of the authenticated cipher NORX, one of the CAESAR candidates. These new versions are better suited for low-end systems---such as ``internet of things'' devices---than the original 32-bit and 64-bit versions: whereas 32-bit NORX requires 64 bytes of RAM or cache memory, NORX8 and NORX16 require just 16 and 32 bytes, respectively. Both of the low-end variants were designed to retain the security properties of the initial NORX and be fast on small CPUs.

This paper presents an algebraic attack against Trivium that breaks 625 rounds using only $4096$ bits of output in an overall time complexity of $2^{42.2}$ Trivium computations. While other attacks can do better in terms of rounds ($799$), this is a practical attack with a very low data usage (down from $2^{40}$ output bits) and low computation time (down from $2^{62}$). From another angle, our attack can be seen as a proof of concept: how far can algebraic attacks can be pushed when several known techniques are combined into one implementation? All attacks have been fully implemented and tested; our figures are therefore not the result of any potentially error-prone extrapolation, but results of practical experiments.

In CRYPTO 2003, Halevi and Rogaway proposed CMC, a tweakable enciphering scheme (TES) based on a blockcipher. It requires two blockcipher keys and it is not inverse-free (i.e., the decryption algorithm uses the inverse (decryption) of the underlying blockcipher). We present here a new inverse-free, single-keyed TES. Our construction is a tweakable strong pseudorandom permutation (tsprp), i.e., it is secure against chosen-plaintext-ciphertext adversaries assuming that the underlying blockcipher is a pseudorandom permutation (prp), i.e., secure against chosen-plaintext adversaries. In comparison, sprp assumption of the blockcipher is required for the sprp security of CMC. Our scheme can be viewed as a mixture of type-1 and type-3 Feistel cipher and so we call it FMix or mixed-type Feistel cipher.

In the past few years, lightweight cryptography has become a popular research discipline with a number of ciphers and hash functions proposed. The designers' focus has been predominantly to minimize the hardware area, while other goals such as low latency have been addressed rather recently only. However, the optimization goal of low energy for block cipher design has not been explicitly addressed so far. At the same time, it is a crucial measure of goodness for an algorithm. Indeed, a cipher optimized with respect to energy has wide applications, especially in constrained environments running on a tight power/energy budget such as medical implants. This paper presents the block cipher Midori that is optimized with respect to the energy consumed by the circuit per bit in encryption or decryption operation. We deliberate on the design choices that lead to low energy consumption in an electrical circuit, and try to optimize each component of the circuit as well as its entire architecture for energy. An added motivation is to make both encryption and decryption functionalities available by small tweak in the circuit that would not incur significant area or energy overheads. We propose two energy-efficient block ciphers Midori128 and Midori64 with block sizes equal to 128 and 64 bits respectively. These ciphers have the added property that a circuit that provides both the functionalities of encryption and decryption can be designed with very little overhead in terms of area and energy. We compare our results with other ciphers with similar characteristics: it was found that the energy consumptions of Midori64 and Midori128 are by far better when compared ciphers like PRINCE and NOEKEON.

Hash functions are often constructed based on permutations or blockciphers, and security proofs are typically done in the ideal permutation or cipher model. However, once these random primitives are instantiated, vulnerabilities of these instantiations may nullify the security. At ASIACRYPT 2007, Knudsen and Rijmen introduced known-key security of blockciphers, which gave rise to many distinguishing attacks on existing blockcipher constructions. In this work, we analyze the impact of such attacks on primitive-based hash functions. We present and formalize the weak cipher model, which captures the case a blockcipher has a certain weakness but is perfectly random otherwise. A specific instance of this model, considering the existence of sets of B queries whose XOR equals 0 at bit-positions C, where C is an index set, covers a wide range of known-key attacks in literature. We apply this instance to the PGV compression functions, as well as to the Groestl (based on two permutations) and Shrimpton-Stam (based on three permutations) compression functions, and show that these designs do not seriously succumb to any differential known-key attack known to date.

This paper suggests a model and a definition for forward-secure authenticated key exchange (AKE) protocols, which can be satisfied without depending on the Diffie-Hellman assumption. The basic idea is to use key-evolving schemes (KES), where the long-term keys of the system get updated regularly and irreversibly. Protocols conforming to our model can be highly efficient, since they do not require the resource-intensive modular exponentiations of the Diffie-Hellman protocol. We also introduce a protocol, called FORSAKES, and prove rigorously that it is a forward-secure AKE protocol in our model. FORSAKES is a very efficient protocol, and can be implemented by merely using hash functions.

We prove (nearly) tight bounds on the concrete PRF-security of two constructions of message-authentication codes (MACs): (1) The truncated CBC-MAC construction, which operates as plain CBC-MAC (without prefix-free encoding of messages), but only returns a subset of the output bits. (2) The MAC derived from the sponge hash-function family by pre-pending a key to the message, which is the de-facto standard method for SHA-3-based message authentication. The tight analysis of keyed sponges is our main result and we see this as an important step in validating SHA-3-based authentication before its deployment. Still, our analysis crucially relies on the one for truncated CBC as an intermediate step of independent interest. Indeed, no previous security analysis of truncated CBC was known, whereas only significantly weaker bounds have been proved for keyed sponges following different approaches. Our bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) $\ell \le \min\{2^{n/4},2^r\}$ blocks, where $n$ is the state size and $r$ is the desired output length; and for $q \ge \ell$ queries. Our proofs rely on a novel application of Patarin's H-coefficient method to iterated MAC constructions.

HMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box. Generic security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question. In this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing. While our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions.

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a ``weak" random source $X$ with min-entropy $k$ and a uniformly random seed $Y$ of length $d$, and outputs a string of length close to $k$ that is close to uniform and independent of $Y$. Dodis and Wichs~\cite{DW09} introduced a generalization of randomness extractors called non-malleable extractors ($\nmExt$) where $\nmExt(X,Y)$ is close to uniform and independent of $Y$ and $\nmExt(X,f(Y))$ for any function $f$ with no fixed points. We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor ($\AmExt: \F^n \times \F^d \mapsto \F$) where $\AmExt(X,Y)$ is close to uniform and independent of $Y$ and has some limited dependence of $\AmExt(X,f(Y))$ - that conditioned on $Y$, $(\AmExt(X,Y), \AmExt(X,f(Y)))$ is close to $(U, A \cdot U + B)$ where $U$ is uniformly distributed in $\F$ and $A, B \in \F$ are random variables independent of $\F$. We show under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture) that the inner-product function $\IP{\cdot,\cdot}:\F^n \times \F^n \mapsto \F$ is an affine-malleable extractor. As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture. We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret $X$ of min-entropy $k$, and wish to agree on secret key $R$ of length $m$ over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and its many variants has been in constructing secure privacy amplification protocols. We show that affine-malleable extractors along with affine-evasive sets can also be used to construct efficient privacy amplification protocols. We show that our protocol, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.

In this paper, we investigate Keccak --- the cryptographic hash function adopted as the SHA-3 standard. We propose a malicious variant of the function, where new round constants are introduced. We show that for such the variant, collision and preimage attacks are possible. We also identify a class of weak keys for the malicious Keccak working in the MAC mode. Ideas presented in the paper were verified by implementing the attacks on the function with the 128-bit hash.

We consider the symmetric Feedback Shift Registers (FSRs), especially a special class of symmetric FSRs (we call them scattered symmetric FSRs), and construct a large class of De Bruijn sequences from them. It is shown that, at least O(2^((n-6)(logn)/2)) De Bruijn sequences of order n can be constructed from just one n-stage scattered symmetric FSR. To generate the next bit in the De Bruijn sequence from the current state, it requires no more than 2n comparisons and n+1 FSR shifts. By further analyse the cycle structure of the scattered symmetric FSRs, other methods for constructing De Bruijn sequences are suggested.

The adjacency graphs of feedback shift registers (FSRs) with characteristic function of the form g=(x_0+x_1)*f are considered in this paper. Some properties about these FSRs are given. It is proved that these FSRs contains only prime cycles and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. It is shown that, when f is a linear function and contains an odd number of terms, the adjacency graph of \mathrm{FSR}((x_0+x_1)*f) can be determined directly from the adjacency graph of \mathrm{FSR}(f). As an application of these results, we determine the adjacency graphs of \mathrm{FSR}((1+x)^4p(x)) and \mathrm{FSR}((1+x)^5p(x)), where p(x) is a primitive polynomial, and construct a large class of de Bruijn sequences from them.

Guess-and-determine attacks are based on guessing a subset of internal state bits and subsequently using these guesses together with the cipher's output function to determine the value of the remaining state. These attacks have been successfully employed to break NFSR-based stream ciphers. The complexity of a guess-and-determine attack is directly related to the number of state bits used in the output function. Consequently, an opportunity exits for efficient cryptanalysis of NFSR-based stream ciphers if NFSRs used can be transformed to derive an equivalent stream cipher with a simplified output function. In this paper, we present a new technique for transforming NFSRs. We show how we can use this technique to transform NFSRs to equivalent NFSRs with simplified output functions. We explain how such transformations can assist in cryptanalysis of NFSR-based ciphers and demonstrate the application of the technique to successfully cryptanalyse the lightweight cipher Sprout. Our attack on Sprout has a time complexity of 2^70.87, which is 2^3.64 times better than any published non-TMD attack, and requires only 164 bits of plaintext-ciphertext pairs.

RFID security is currently one of the major challenges cryptography has to face, often solved by protocols assuming that an on-tag hash function is available. In this article we present the PHOTON lightweight hash-function family, available in many different flavors and suitable for extremely constrained devices such as passive RFID tags. Our proposal uses a sponge-like construction as domain extension algorithm and an AES-like primitive as internal unkeyed permutation. This allows us to obtain the most compact hash function known so far (about 1120 GE for 64-bit collision resistance security), reaching areas very close to the theoretical optimum (derived from the minimal internal state memory size). Moreover, the speed achieved by PHOTON also compares quite favorably to its competitors. This is mostly due to the fact that unlike for previously proposed schemes, our proposal is very simple to analyze and one can derive tight AES-like bounds on the number of active Sboxes. This kind of AES-like primitive is usually not well suited for ultra constrained environments, but we describe in this paper a new method for generating the column mixing layer in a serial way, lowering drastically the area required. Finally, we slightly extend the sponge framework in order to offer interesting trade-offs between speed and preimage security for small messages, the classical use-case in hardware.

In this very short note we prove that the pseudo-random index j of RC4 is indeed not pseudo-random. This is a simple result that missed our attention for quite a long time. We show that in long term Pr(j = i+1) = 1/N - 1/N^2, instead of the random association 1/N and this happens for the non-existence of the condition S[i] = 1 and j = i+1 that is mandatory for the non-existence of the Finney cycle.

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. In this paper I propose the improved fully homomorphic encryption scheme on non-associative octonion ring over finite ring with composite number modulus where the plaintext p consists of three numbers u,v,w. The proposed fully homomorphic encryption scheme is immune from the “p and -p attack”. As 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. It is proved that if there exists the PPT algorithm that decrypts the plaintext from the ciphertexts of the proposed scheme, there exists the PPT algorithm that factors the given composite number modulus.

We investigate a well-known way to construct pseudo-random sequences by separation p-adic coordinate sequences of linear recurrences over Galois ring. Commonly it is necessary to know rank estimations of separated sequences. In this article we describe divisors of the minimal polynomial of the second p-adic coordinate sequence of the linear recurrent sequence of maximal period/MP-LRS over non-trivial Galois ring of odd characteristic in dependence of the initial vector of this LRS. Also we describe polynomials divisible by that minimal polynomial in dependence of the initial vector of this LRS. As a corollary we get non-trivial upper and lower estimations for the rank of the second coordinate sequence of such MP-LRS which provides us by possibility to use it in pseudo-random generation. We say that the Galois ring is non-trivial, if it differs from Galois field and from quotient ring too. These results were worked out with participation of V.L.Kurakin as a supervisor. Author is very grateful to V.L.Kurakin for his participation in this work

One of the crucial factors for enabling fast and secure computations in the Zettabyte era is the use of incremental cryptographic primitives. For files ranging from several megabytes up to hundreds of gigabytes, incremental cryptographic primitives offer speedup factors measured in multiple orders of magnitude. In this paper we define two incremental hash functions iSHAKE128 and iSHAKE256 based on the recent NIST proposal for SHA-3 Extendable-Output Functions SHAKE128 and SHAKE256. We give two practical implementation aspects of a newly introduced hash functions and compare them with already known tree based hash scheme. We show the trends of efficiency gains as the amount of data increases in comparisons between our proposed hash functions and the standard tree based incremental schemes. Our proposals have the security levels against collision attacks of 128 and 256 bits.

PAGES+ is a family of block ciphers based on block ciphers Speck [2] and PAGES [9]. The block length was increased vom 128 bit to 512 bit and additional rounds were introduced to make the cipher more resistent against attacks. The number of rounds are 64, 96, and 128. The key size are 1024 bit, 1536 bit, and 2048 bit, respectively. The size of variables, as with PAGES, is 128 bit. Thus the variables can be stored in registers of the microprocessors of two leading suppliers. As with Speck, PAGES+ utilizes instructions with a low latency, such as addition modulo 2 128 , subtraction modulo 2 128 , XOR, and circular shifts (rotation). All these instructions are usually carried out within a few cycles. Hence despite the number of rounds is considerable, PAGES+ has a high software throughput. For a processor with a frequency of 2.5 GHz, the software throughput with the optimized version of the reference implementation is 30 megabyte per second with a key length of 2048 bit and a number of rounds of 128. In hardware or the implementation on a FPGA a considerable performance is expected, yet with a limited expense. PAGES- is a family of block ciphers based on block ciphers Speck [2] and PAGES [9]. The block length was increased vom 128 bit to 256 bit and additional rounds were introduced to make the cipher more resistent against attacks. The number of rounds are 32, 48, 64, 96, and 128. The key size are 256 bit, 384 bit, 512 bit, 768 bit, and 1024 bit, respectively. The size of variables, as with Speck, is 64 bit. As with Speck, PAGES- utilizes instructions with a low latency, such as addition modulo 2 64 , subtraction modulo 2 64 , XOR, and circular shifts (rotation). All these instructions are usually carried out within one cycle. Hence despite the number of rounds is considerable, PAGES- has a high software throughput. For a processor with a frequency of 2.5 GHz, the software throughput with the optimized version of the reference implementation is 80 megabyte per second with a key length of 1024 bit and a number of rounds of 128. PAGES– is a family of block ciphers based on block ciphers Speck [2] and PAGES [9]. The block length was increased vom 128 bit to 512 bit and additional rounds were introduced to make the cipher more resistent against attacks. The number of rounds are 32, 48, 64, 96, and 128. The key size are 512 bit, 768 bit, 1024 bit, 1536 bit, and 2048 bit respectively. The size of variables, as with Speck, is 64 bit. For a processor with a frequency of 2.5 GHz, the software throughput with the optimized version of the reference implementation is 65 megabyte per second with a key length of 2048 bit and a number of rounds of 128.

We consider the generic design of a tweakable blockcipher from one or more evaluations of a classical blockcipher, in such a way that all input and output wires are of size n bits. As a first contribution, we show that any tweakable blockcipher with one primitive call and arbitrary linear pre- and postprocessing functions can be distinguished from an ideal one with an attack complexity of about 2^{n/2}. Next, we introduce the tweakable blockcipher tilde{F}[1]. It consists of one multiplication and one blockcipher call with tweak-dependent key, and achieves 2^{2n/3} security. Finally, we introduce tilde{F}[2], which makes two blockcipher calls, one of which with tweak-dependent key, and achieves optimal 2^n security. Both schemes are more efficient than all existing beyond birthday bound tweakable blockciphers known to date, as long as one blockcipher key renewal is cheaper than one blockcipher evaluation plus one universal hash evaluation.

In this paper, we describe a variant of the cube attack with much better-understood Preprocessing Phase, where complexity can be calculated without running the actual experiments and random-like search for the cubes. We apply our method to a few different cryptographic algorithms, showing that the method can be used against a wide range of cryptographic primitives, including hash functions and authenticated encryption schemes. We also show that our key-recovery approach could be a framework for side-channel attacks, where the attacker has to deal with random errors in measurements.

In this paper we analyse two variants of SIMON family of light-weight block ciphers against linear cryptanalysis and present the best linear cryptanalytic results on these variants of reduced-round SIMON to date. We propose a time-memory trade-off method that finds differential/linear trails for any permutation allowing low Hamming weight differential/linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32. The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box $F$ of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of $F$ are far from random and propose a design criteria, along with an algorithm which generates S-Boxes very similar to that of Skipjack. Then we consider more general S-box decomposition problems and propose new methods for decomposing S-Boxes built from arithmetic operations or as a Feistel Network of up to 5 rounds. Finally, we develop an S-box generating algorithm which can fix a large number of DDT entries to the values chosen by the designer. We demonstrate this algorithm by embedding images into the visual representation of S-box's DDT.

At SAC 2006, Liskov proposed the zipper hash, a technique for constructing secure (indifferentiable from random oracles) hash functions based on weak (invertible) compression functions. Zipper hash is a two pass scheme, which makes it unfit for practical consideration. But, from the theoretical point of view it seemed to be secure, as it had resisted standard attacks for long. Recently, Andreeva {\em et al.} gave a forced-suffix herding attack on the zipper hash, and Chen and Jin showed a second preimage attack provided $f_1$ is strong invertible. In this paper, we analyse the construction under the random oracle model as well as when the underlying compression functions have some weakness. We show (second) preimage, and herding attacks on an $n$-bit zipper hash and its relaxed variant with $f_1 = f_2$, all of which require less than $ 2^{n} $ online computations. Hoch and Shamir have shown that the concatenated hash offers only $\frac{n}{2}$-bits security when both the underlying compression functions are strong invertible. We show that the bound is tight even when only one of the underlying compression functions is strong invertible.

The Kupyna hash function was selected as the new Ukrainian standard DSTU 7564:2014 in 2015. It is designed to replace the old Independent States (CIS) standard GOST 34.311-95. The Kupyna hash function is an AES-based primitive, which uses Merkle-Damgård compression function based on Even-Mansour design. In this paper, we show the first cryptanalytic attacks on the round-reduced Kupyna hash function. Using the rebound attack, we present a collision attack on 5-round of the Kupyna-256 hash function. The complexity of this collision attack is ($2^{120},2^{64}$) (in time and memory). Furthermore, we use guess-and-determine MitM attack to construct pseudo-preimage attacks on 6-round Kupyna-256 and Kupyna-512 hash function, respectively. The complexity of these preimage attacks are ($2^{250.33},2^{250.33}$) and ($2^{498.33},2^{498.33}$) (in time and memory), respectively.

The core of the 3rd Generation Partnership Project (3GPP) encryption standard 128-EEA3 is a stream cipher called ZUC. It was designed by the Chinese Academy of Sciences and proposed for inclusion in the cellular wireless standards called “Long Term Evolution” or “4G”. The LFSR-based cipher uses a 128-bit key. In this paper, we first show timing attacks on ZUC that can recover, with about 71.43% success rate, (i) one bit of the secret key immediately, and (ii) information involving 6 other key bits. The time, memory and data requirements of the attacks are negligible. While we see potential improvements to the attacks, we also suggest countermeasures.

PAGES is a block cipher familiy basedon the design of Speck, see [1]. However, some intriguing design details of SPeck were not used in the design of PAGES. PAGES has a block size of 256 bit and comes in three versions:PAGES-512, PAGES-768 and PAGES-1024, where the number denotes the key length. The number of rounds is 64, 96, and 128, respectively. PAGES uses 128 bit variables, that is half of the block size.

Existing standards (ZigBee and Bluetooth Low Energy) for networked low-power wireless devices do not support secure association (or pairing) of new devices into a network: their association process is vulnerable to man-in-the-middle attacks. This paper addresses three essential aspects in attaining secure association for such devices. First, we define a user-interface primitive, oblivious comparison, that allows users to approve authentic associations and abort compromised ones. This distills and generalizes several existing approve/abort mechanisms, and moreover we experimentally show that OC can be implemented using very little hardware: one LED and one switch. Second, we provide a new Message Recognition Protocol (MRP) that allows devices associated using oblivious comparison to exchange authenticated messages without the use of public-key cryptography (which exceeds the capabilities of many IoT devices). This protocol improves upon previously proposed MRPs in several respects. Third, we propose a robust definition of security for MRPs that is based on universal composability, and show that our MRP satisfies this definition.

Side channel analysis and active fault analysis are now major threats to even mathematically robust cryptographic algorithms that are otherwise resistant to classical cryptanalysis. It is necessary to design suitable countermeasures to protect cryptographic primitives against such attacks. This paper focuses on designing encryption schemes that are innately secure against fault analysis. The paper formally proves that one such design strategy, namely the use of key-dependent SBoxes, is only partially secure against DFA. The paper then examines the fault tolerance of encryption schemes that use a key-independent secret tweak value for randomization. In particular, the paper focuses on a linear tweak based and a non-linear tweak based version of a recently proposed block cipher DRECON. The paper demonstrates that while both versions are secure against classical DFA, the non-linear tweak based version provides greater fault coverage against stronger fault models. This fact, together with the DPA resistance provided by the use of variable S-Boxes, makes DRECON a strong candidate for the design of secure cryptographic primitives. All claims have been validated by experimental results on a SASEBO GII platform.

In earlier eighties of XX century A.A.Nechaev has obtained the criterion of full period of a Galois polynomial over primary residue ring modulo power of 2. Also he has obtained necessary conditions of maximal period of the Galois polynomial over such ring in terms of coefficients of this polynomial. Further A.S.Kuzmin has obtained analogous results for the case of Galois polynomial over primary residue ring of odd characteristic . Later the first author of this article has carried the criterion of full period of the Galois polynomial over primary residue ring of odd characteristic obtained by A.S.Kuzmin to the case of Galois polynomial over nontrivial Galois ring of odd characteristic. Using this criterion as a basis we have obtained criterion calling attention to. This result is an example how to apply results of the previous work of V.N.Tsypyschev in order to construct polynomials of maximal period over nontrivial Galois ring of odd characteristic. During this it is assumed that period of polynomial modulo prime ideal is known and maximal .

We provide a security analysis for full-state keyed Sponge and full-state Duplex constructions. Our results can be used for making a large class of Sponge-based authenticated encryption schemes more efficient by concurrent absorption of associated data and message blocks. In particular, we introduce and analyze a new variant of SpongeWrap with almost free authentication of associated data. The idea of using full-state message absorption for higher efficiency was first made explicit in the Donkey Sponge MAC construction, but without any formal security proof. Recently, Gaži, Pietrzak and Tessaro (CRYPTO 2015) have provided a proof for the fixed-output-length variant of Donkey Sponge. Yasuda and Sasaki (CT-RSA 2015) have considered partially full-state Sponge-based authenticated encryption schemes for efficient incorporation of associated data. In this work, we unify, simplify, and generalize these results about the security and applicability of full-state keyed Sponge and Duplex constructions; in particular, for designing more efficient authenticated encryption schemes. Compared to the proof of Gaži et al., our analysis directly targets the original Donkey Sponge construction as an arbitrary-output-length function. Our treatment is also more general than that of Yasuda and Sasaki, while yielding a more efficient authenticated encryption mode for the case that associated data might be longer than messages.

This paper analyzes the authenticated encryption algorithm ACORN, a candidate in the CAESAR cryptographic competition. We identify weaknesses in the state update function of ACORN which result in collisions in the internal state of ACORN. This paper shows that for a given set of key and initialization vector values we can construct two distinct input messages which result in a collision in the ACORN internal state. Using a standard PC the collision can be found almost instantly when the secret key is known.

Statistical analysis of attacks on symmetric ciphers often require assuming the normal behaviour of a test statistic. Typically such an assumption is made in an asymptotic sense. In this work, we consider concrete versions of some important normal approximations that have been made in the literature. To do this, we use the Berry-Esséen theorem to derive explicit bounds on the approximation errors. Analysing these error bounds in the cryptanalytic context throws up several surprising results. One important implication is that this puts in doubt the applicability of the order statistics based approach for analysing key recovery attacks on block ciphers. This approach has been earlier used to obtain several results on the data complexities of (multiple) linear and differential cryptanalysis. The non-applicability of the order statistics based approach puts a question mark on the data complexities obtained using this approach. Fortunately, we are able to recover all of these results by utilising the hypothesis testing framework. Detailed consideration of the error in normal approximation also has implications for $\chi^2$ and the log-likelihood ratio (LLR) based test statistics. The normal approximation of the $\chi^2$ test statistics has some serious and counter-intuitive restrictions. One such restriction is that for multiple linear cryptanalysis as the number of linear approximations grows so does the requirement on the number of plaintext-ciphertext pairs for the approximation to be proper. The issue of satisfactorily addressing the problems with the application of the $\chi^2$ test statistics remains open. For the LLR test statistics, previous work used a normal approximation followed by another approximation to simplify the parameters of the normal approximation. We derive the error bound for the normal approximation which turns out to be difficult to interpret. We show that the approximation required for simplifying the parameters restricts the applicability of the result. Further, we argue that this approximation is actually not required. More generally, the message of our work is that all cryptanalytic attacks should properly derive and interpret the error bounds for any normal approximation that is made.

The application of the concept of linear cryptanalysis to the domain of key-less primitives is largely an open problem. In this paper we, for the first time, propose a model in which its application is meaningful for distinguishing block ciphers. Combining our model with ideas from message modification and rebound-like approaches, we initiate a study of cryptographic primitives with respect to this new attack vector and choose the lightweight block cipher PRESENT as an example target. This leads to known-key distinguishers over up to 27 rounds, whereas the best previous result is up to 18 rounds in the chosen-key model.

Designing block ciphers targeting resource constrained 8-bit CPUs is a challenging problem. There are many recent lightweight ciphers designed for better performance in hardware. On the other hand, most software efficient lightweight ciphers either lack a security proof or have a low security margin. To fill the gap, we present RoadRunneR which is an efficient block cipher in 8-bit software, and its security is provable against differential and linear attacks. RoadRunneR has lowest code size in Atmel’s ATtiny45, except NSA’s design SPECK, which has no security proof. Moreover, we propose a new metric for the fair comparison of block ciphers. This metric, called ST/A, is the first metric to use key length as a parameter to rank ciphers of different key length in a fair way. By using ST/A and other metrics in the literature, we show that RoadRunneR is competitive among existing ciphers on ATtiny45.

SIMECK is a family of 3 lightweight block ciphers designed by Yang et al. They follow the framework used by Beaulieu et al. from the United States National Security Agency (NSA) to design SIMON and SPECK. A cipher in this family with K-bit key and N-bit block is called SIMECKN=K.We show that the security of this block cipher against linear cryptanalysis is not as good as its predecessors SIMON. More precisely, while the best known linear attack for SIMON32/64, using algorithm 1 of Matsui, covers 13 rounds we present a linear attack in this senario which covers 14 rounds of SIMECK32/64. Similarly, using algorithm 1 of Matsui, we present attacks on 19 and 22 rounds of SIMECK48/96 and SIMECK64/128 respectively, compare them with known attacks on 16 and 19 rounds SIMON48/96 and SIMON64/128 respectively. In addition, we use algorithm 2 of Matsui to attack 18, 23 and 27 rounds of SIMECK32/64, SIMECK48/96 and SIMECK64/128 respectively, compare them with known attacks on 18, 19 and 21 rounds SIMON32/64, SIMON48/96 and SIMON64/128 respectively.

Conventional Cipher Feedback Mode (CFB) can allow the transmission unit to be shorter than the block-cipher length. Eventually, it causes no delay and even any message expansion unlike the ECB and CBC mode of operation where encryption cannot begin unless and until a complete block of full-length (say 64 bits) plain-text data is available. However, because of stalling during the block encryption, CFB cannot provide low latency, low jitter; these are two imperative properties in the sense of real-time cryptography. For that, it is important that the input stream should not wait for the key-stream to be generated; that means, key-streams are required to be arranged in advance, which cannot be expected in case of the conventional CFB mode. Besides, the conventional Cipher Feedback Mode is also incompetent for such real-time crypto systems, where the integrity of the message is also greatly desirable along with privacy. In this article, we propose a variant of Cipher Feedback Mode, called, Integrity-Aware, Parallelizable Cipher Feedback Mode (IAP-CFB), which can guarantee all the aforesaid requirements, such as, low latency, low jitter, privacy, and integrity assurance, etc.

Camellia is a widely used block cipher, which has been selected as an international standard by ISO/IEC. In this paper, we consider a new family of dierentials of round-reduced Camellia-128 depending on dierent key subsets. There are totally 224 key subsets corresponding to 224 types of 8-round dierentials, which cover a fraction of 1- 1=2^{15} of the keyspace. And each type of 8-round dierential consists of 2^{43} dierentials. Combining with the multiple dierential attack techniques, we give the key-dependent multiple dierential attack on 10-round Camellia-128 with data complexity 2^{91} and time complexity 2^{113}. Furthermore, we propose a 7-round property for Camellia-192 and an 8-round property for Camellia-256, and then mount the meet-in-the-middle attacks on 12-round Camellia-192 and 13-round Camellia-256, with complexity of 2^{180} encryptions and 2^{232.7} encryptions, respectively. All these attacks start from the rst round in a single keysetting.

Tweakable blockcipher (TBC) is an extension of standard blockcipher introduced by Liskov, Rivest and Wagner in 2002. TBC is a versatile building block for efficient symmetric-key cryptographic functions, such as authenticated encryption. In this paper we study the problem of extending tweak of a given TBC of fixed-length tweak, which is a variant of popular problem of converting a blockcipher into a TBC, i.e., blockcipher mode of operation. The problem is particularly important for known dedicated TBCs since they have relatively short tweak. We propose a simple and efficient solution, called XTX, for this problem. XTX converts a TBC of fixed-length tweak into another TBC of arbitrarily long tweak, by extending the scheme of Liskov, Rivest and Wagner that converts a blockcipher into a TBC. Given a TBC of $n$-bit block and $m$-bit tweak, XTX provides $(n+m)/2$-bit security while conventional methods provide $n/2$ or $m/2$-bit security. We also show that XTX is even useful when combined with some blockcipher modes for building TBC having security beyond the birthday bound.

Recent advances in block-cipher theory deliver security analyses in models where one or more underlying components (e.g., a function or a permutation) are {\em ideal} (i.e., randomly chosen). This paper addresses the question of finding {\em new} constructions achieving the highest possible security level under minimal assumptions in such ideal models. We present a new block-cipher construction, derived from the Swap-or-Not construction by Hoang et al. (CRYPTO '12). With $n$-bit block length, our construction is a secure pseudorandom permutation (PRP) against attackers making $2^{n - O(\log n)}$ block-cipher queries, and $2^{n - O(1)}$ queries to the underlying component (which has itself domain size roughly $n$). This security level is nearly optimal. So far, only key-alternating ciphers have been known to achieve comparable security levels using $O(n)$ independent random permutations. In contrast, here we only assume that a {\em single} {\em function} or {\em permutation} is available, while achieving similar efficiency. Our second contribution is a generic method to enhance a block cipher, initially only secure as a PRP, to achieve related-key security with comparable quantitative security.

The iterated Even-Mansour construction defines a block cipher from a tuple of public $n$-bit permutations $(P_1,\ldots,P_r)$ by alternatively xoring some $n$-bit round key $k_i$, $i=0,\ldots,r$, and applying permutation $P_i$ to the state. The \emph{tweakable} Even-Mansour construction generalizes the conventional Even-Mansour construction by replacing the $n$-bit round keys by $n$-bit strings derived from a master key \emph{and a tweak}, thereby defining a tweakable block cipher. Constructions of this type have been previously analyzed, but they were either secure only up to the birthday bound, or they used a nonlinear mixing function of the key and the tweak (typically, multiplication of the key and the tweak seen as elements of some finite field) which might be costly to implement. In this paper, we tackle the question of whether it is possible to achieve beyond-birthday-bound security for such a construction by using only linear operations for mixing the key and the tweak into the state. We answer positively, describing a 4-round construction with a $2n$-bit master key and an $n$-bit tweak which is provably secure in the Random Permutation Model up to roughly $2^{2n/3}$ adversarial queries.

A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4x4 S-boxes and use these iteratively (e.g., PRESENT and SPONGENT). In order to efficiently implement the primitive, efficient implementations of its internal components are needed. Multiplicative complexity of a function is the minimum number of AND gates required to implement it by a circuit over the basis (AND, XOR, NOT). It is known that multiplicative complexity is exponential in the number of input bits n. Thus it came as a surprise that circuits for all 65 536 functions on four bits were found which used at most three AND gates. In this paper, we verify this result and extend it to five-variable Boolean functions. We show that the multiplicative complexity of a Boolean function with five variables is at most four.

Khudra is a 18-round lightweight block cipher proposed by Souvik Kolay and Debdeep Mukhopadhyay in the SPACE 2014 conference which is applicable to Field Programmable Gate Arrays (FPGAs). In this paper, we obtain $2^{16}$ 14-round related-key impossible differentials of Khudra, and based on these related-key impossible differentials for 32 related keys, we launch an attack on the full Khudra with data complexity of $2^{63}$ related-key chosen-plaintexts, time complexity of about $2^{68.46}$ encryptions and memory complexity of $2^{64}$.

The last hash function and block cipher standardized by the Russian standardization body (GOST) both use the same S-Box. It is also used by an independent CAESAR candidate. This transformation is only specified as a look up table and the reason behind its choice is unknown. We managed to reverse-engineer this S-Box and describe its unpublished structure. Our decomposition allows a much more efficient hardware implementation but the choice of the components used is puzzling from a cryptographic perspective. This extended abstract does not explain \emph{how} we found this decomposition. We will describe our process in an extended version of this paper.

RC4 suffered from a range of plaintext-recovery attacks using statistical biases, which use substantial, albeit close-to-practical, amounts of known keystream in applications such as TLS or WEP/WPA. Spritz was recently proposed at the rump session of CRYPTO 2014 as a slower redesign of RC4 by Rivest and Schuldt, aiming at reducing the statistical biases that lead to these attacks on RC4. Even more devastating than those plaintext-recovery attacks from large amounts of keystream would be state- or key-recovery attacks from small amounts of known keystream. For RC4, there is unsubstantiated evidence that they may exist, the situation for Spritz is however not clear, as resistance against such attacks was not a design goal. In this paper, we provide the first cryptanalytic results on Spritz and introduce three different state recovery algorithms. Our first algorithm recovers an internal state, requiring only a short segment of keystream, with an approximated complexity of $2^{1400}$, which is much faster than exhaustive search through all possible states, but is still far away from a practical attack. Furthermore, we introduce a second algorithm that uses a pattern in the keystream to reduce the number of guessed values in our state recovery algorithm. Our third algorithm uses a probabilistic approach by considering the permutation table as probability distribution. All in all, rather than showing a weakness, our analysis supports the conjecture that compared to RC4, Spritz may also provide higher resistance against potentially devastating state-recovery attacks.

Motivated by revelations concerning population-wide surveillance of encrypted communications, we formalize and investigate the resistance of symmetric encryption schemes to mass surveillance. The focus is on algorithm-substitution attacks (ASAs), where a subverted encryption algorithm replaces the real one. We assume that the goal of ``big~brother'' is undetectable subversion, meaning that ciphertexts produced by the subverted encryption algorithm should reveal plaintexts to big~brother yet be indistinguishable to users from those produced by the real encryption scheme. We formalize security notions to capture this goal and then offer both attacks and defenses. In the first category we show that successful (from the point of view of big brother) ASAs may be mounted on a large class of common symmetric encryption schemes. In the second category we show how to design symmetric encryption schemes that avoid such attacks and meet our notion of security. The lesson that emerges is the danger of choice: randomized, stateless schemes are subject to attack while deterministic, stateful ones are not.

We present a general framework for developing and analyzing homomorphic cryptosystems whose security relies on the difficulty of solving systems of nonlinear equations over Z/nZ, n being an RSA modulus. In this framework, many homomorphic cryptosystems can be conceptualized. Based on symmetry considerations, we propose a general assumption that ensures the security of these schemes. To highlight this, we present an additive homomorphic private-key cryptosystem and we prove its security. Finally, we propose two motivating perspectives of this work. We first propose an FHE based on the previous scheme by defining a simple multiplicative operator. Secondly, we propose ways to remove the factoring assumption in order to get pure multivariate schemes.

A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than $2^{10}$ times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack shows that a more careful analysis should be done in order to instantiate the proposed design method.

In 'Turning Online Ciphers Off', a class of constructions was defined based on layers of secure online ciphers interleaved with simple mixing layers (like reversing and block-shifting). Here we show that an SPRP construction proposed in the work cited is insecure. Howevewr, the same construction is secure under the assumption that the underlying construction is online-but-last ciphers. We include a simpler proof for beyond-birthday security of other constructions proposed in the same work.

Chaskey is a Message Authentication Code (MAC) for 32-bit microcontrollers proposed by Mouha et. al at SAC 2014. Its underlying blockcipher uses an Even-Mansour construction with a permutation based on the ARX methodology. In this paper, we present key-recovery attacks against Chaskey in the single and multi-user setting. These attacks are based on recent work by Fouque, Joux and Mavromati presented at Asiacrypt 2014 on Even-Mansour based constructions. We first show a simple attack on the classical single-user setting which confirms the security properties of Chaskey. Then, we describe an attack in the multi-user setting and we recover all keys of 2^{43} users by doing 2^{43} queries per user. Finally, we show a variant of this attack where we are able to recover keys of two users in a smaller group of 2^{32} users.

Hill is a classical cipher which is generally believed to be resistant against ciphertext-only attack. In this paper, by using a divide-and-conquer technique, it is first shown that Hill with d*d key matrix over Z_26 can be broken with computational complexity of O(d26^d), for the English language. This is much less than the only publicly known attack, i.e., the brute-force with complexity of O(d^3(26)^(d^2)). Then by using the Chinese Remainder Theorem, it is shown that the computational complexity of the proposed attack can be reduced to O(d13^d). Using an information-theoretic approach, supported by extensive simulation results, it is shown that the minimum ciphertext length required for a successful attack increases by a factor of about 7 and 9.8, respectively for these two attacks in comparison with the brute-force attack. This is the only serious attack on Hill since its invention in 1929.

At CRYPTO 2014 Bellare, Paterson, and Rogaway (BPR) presented a formal treatment of symmetric encryption in the light of algorithm substitution attacks (ASAs), which may be employed by `big brother' entities for the scope of mass surveillance. Roughly speaking, in ASAs big brother may bias ciphertexts to establish a covert channel to leak vital cryptographic information. In this work, we identify a seemingly benign assumption implicit in BPR's treatment and argue that it artificially (and severely) limits big brother's capabilities. We then demonstrate the critical role that this assumption plays by showing that even a slight weakening of it renders the security notion completely unsatisfiable by any, possibly deterministic and/or stateful, symmetric encryption scheme. We propose a refined security model to address this shortcoming, and use it to restore the positive result of BPR, but caution that this defense does not stop most other forms of covert-channel attacks.

COFFE is a hash-based authenticated encryption scheme. In the original paper, it was claimed to have IND-CPA security and also ciphertext integrity even in nonce-misuse scenario. In this paper, we analyse the security of COFFE. Our attack shows that even under the assumption that the primitive hash function is ideal, a valid ciphertext can be forged with 2 enquiries with success probability close to 1. The motivation of the attack is to find a collision on the input of each of the hash calls in the COFFE instantiation. It can be done in two ways. The first way is by modifying nonce and last message block size. Chosen appropriately, we can ensure two COFFE instantiations with different nonce and different last message block size can have exactly the same intermediate state value. This hence leads to a valid ciphertext to be generated. Another way is by considering two different COFFE instantiations with different message block size despite same key. In this case, we will use the existence of consecutive zero in the binary representation the initial value to achieve identical intermediate state value on two different COFFE instantiations. Having the state collisions, the forgery attack is then conducted by choosing two different plaintexts with appropriate nonce and tag size to query. Having this fact, without knowing the secret key, we can then validly encrypt another plaintext with probability equal to 1.

Most stream ciphers used in practice are vulnerable against generic collision attacks, which allow to compute the secret initial state on the basis of O(2^{n/2}) keystream bits in time and space O(2^{n/2}), where n denotes the inner state length of the underlying keystream generator. This implies the well-known rule that for reaching n-bit security, the inner state length should be at least 2n. Corresponding to this, the inner state length of recent proposals for practically used stream ciphers is quite large (e.g., n=288 for Trivium and n=160 for Grain v1). In this paper, we suggest a simple stream cipher operation mode, respectively a simple way how to modify existing operation modes like that in the Bluetooth system, which provides provable security near 2^{2n/3} against generic collision attacks. Our suggestion refers to stream ciphers (like E0 in Bluetooth) which generate keystreams that are partitioned into packets and where the initial states for each packet are computed from a packet-IV and the secret session key using a resynchronization algorithm. Our security analysis is based on modeling the resynchronization algorithm in terms of the FP(1)-construction E(x,k)=F(P(x+k)+k), where k denotes an n-bit secret key (corresponding to the symmetric session key), F denotes a publicly known n-bit function (corresponding to the output function of the underlying keystream generator), P denotes a publicly known n-bit permutation (corresponding to the iterated state update function of the generator), and the input x is an n-bit public initial value. Our security bounds follow from the results presented in [Cryptology ePrint Archive: Report 2015/636], where a tight 2n/3 security bound for the FP(1)-construction in the random oracle model was proved.

Side-channel cryptanalysis is a very efficient class of attacks that recovers secret information by exploiting the physical leakage of a device executing a cryptographic computation. To adress this type of attack, many countermeasures have been proposed, and some papers adressed the question of constructing an efficient masking scheme for existing ciphers. In their work, G.~Piret, T.~Roche and C.~Carlet took the problem the other way around and specifically designed a cipher that would be easy to mask. Their careful analysis, that started with the design of an adapted Sbox, leads to the construction of a 12-round Feistel cipher named PICARO. In this paper, we present the first full-round cryptanalysis of this cipher and show how to recover the key in the related-key model. Our analysis takes advantage of the low diffusion of the key schedule together with the non-bijectivity of PICARO Sbox. Our best trade-off has a time complexity equivalent to $2^{107.4}$ encryptions, a data complexity of $2^{99}$ plaintexts and requires to store $2^{17}$ (plaintext, ciphertext) pairs.

This paper fills an important foundational gap with the first proofs, under standard assumptions and in the standard model, of the existence of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) resisting rich and relevant forms of related-key attacks (RKA). An RKA allows the adversary to query the function not only under the target key but under other keys derived from it in adversary-specified ways. Based on the Naor-Reingold PRF we obtain an RKA-PRF whose keyspace is a group and that is proven, under DDH, to resist attacks in which the key may be operated on by arbitrary adversary-specified group elements. Previous work was able only to provide schemes in idealized models (ideal cipher, random oracle), under new, non-standard assumptions, or for limited classes of attacks. The reason was technical difficulties that we resolve via a new approach and framework that, in addition to the above, yields other RKA-PRFs including a DLIN-based one derived from the Lewko-Waters PRF. Over the last 15 years cryptanalysts and blockcipher designers have routinely and consistently targeted RKA-security; it is visibly important for abuse-resistant cryptography; and it helps protect against fault-injection sidechannel attacks. Yet ours are the first significant proofs of existence of secure constructs. We warn that our constructs are proofs-of-concept in the foundational style and not practical.

In previous work(2015/474 in Cryptology ePrint Archive), I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the enciphering function. In this paper I propose the improved fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. I improve the previous scheme by (1) adopting the enciphering function such that it is difficult to express simply by using the matrices and (2) constructing the composition of the plaintext p with two sub-plaintexts u and v. The improved scheme is immune from the “p and -p attack”. 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. The key size of this scheme and complexity for enciphering /deciphering become to be small enough to handle.

Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions. When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called \textit{yoyo game} which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to $O(2^{2n})$ encryptions where $n$ is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively $O(2^{n2^{n-1}+2n})$ and $O(2^{n2^{n}+2n})$. However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity $O(2^{n2^{3n/4}})$. Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.

The aim of this work is to find large S-Boxes, typically operating on 8 bits, having both good cryptographic properties and a low implementation cost. Such S-Boxes are suitable building-blocks in many lightweight block ciphers since they may achieve a better security level than designs based directly on smaller S-Boxes. We focus on S-Boxes corresponding to three rounds of a balanced Feistel and of a balanced MISTY structure, and generalize the recent results by Li and Wang on the best differential uniformity and linearity offered by such a construction. Most notably, we prove that Feistel networks supersede MISTY networks for the construction of 8-bit permutations. Based on these results, we also provide a particular instantiation of an 8-bit permutation with better properties than the S-Boxes used in several ciphers, including Robin, Fantomas or CRYPTON.

Indifferentiability security of a hash mode of operation guarantees the mode's resistance against all (meaningful) generic attacks. It is also useful to establish the security of protocols that use hash functions as random functions. The JH hash function is one of the five finalists in the ongoing NIST SHA-3 hash function competition. Despite several years of analysis, the indifferentiability security of the JH mode (with n-bit digest and 2n-bit permutation) has remained remarkably low, only at n/3 bits (FSE 2010), while the other four finalist modes -- with comparable parameter values -- offer a security guarantee of n/2 bits. In this paper, we improve the indifferentiability security bound for the JH mode to n/2 bits (e.g. from 171 to 256 bits when n=512). To put this into perspective, our result guarantees the absence of attacks on both JH-256 and JH-512 hash functions with time less than approximately 2^{256} computations of the underlying 1024-bit permutation, under the assumption that the basic permutation is structurally strong. Our bounds are optimal for JH-256, and the best, so far, for JH-512. We obtain this improved bound by establishing an isomorphism of certain query-response graphs through a careful design of the simulators and the bad events. Our experimental data strongly supports the theoretically obtained results.

Recently, ChaCha20 (the stream cipher ChaCha with 20 rounds) is in the process of being a standard and thus it attracts serious interest in cryptanalysis. The most significant effort to analyse Salsa and ChaCha had been explained by Aumasson et al long back (FSE 2008) and further, only minor improvements could be achieved. In this paper, first we revisit the work of Aumasson et al to provide a clearer insight of the existing attack (2^{248} complexity for ChaCha7, i.e., 7 rounds) and showing certain improvements (complexity around 2^{243}) by exploiting additional Probabilistic Neutral Bits. More importantly, we describe a novel idea that explores proper choice of IVs corresponding to the keys, for which the complexity can be improved further (2^{239}). The choice of IVs corresponding to the keys is the prime observation of this work. We systematically show how a single difference propagates after one round and how the differences can be reduced with proper choices of IVs. For Salsa too (Salsa20/8, i.e., 8 rounds), we get improvement in complexity, reducing it to 2^{245.5} from 2^{247.2} reported by Aumasson et al.

Three-neighbourhood Cellular Automata (CA) are widely studied and accepted as suitable cryptographic primitive. Rule 30, a 3-neighbourhood CA rule, was proposed as an ideal candidate for cryptographic primitive by Wolfram. However, rule 30 was shown to be weak against Meier-Staffelbach attack. The cryptographic properties like diffusion and randomness increase with increase in neighbourhood radius and thus opens the avenue of exploring the cryptographic properties of 4-neighbourhood CA. This work explores whether four-neighbourhood CA can be a better cryptographic primitive. We construct a class of cryptographically suitable 4-neighbourhood nonlinear CA rules that resembles rule 30. One 4-neighbourhood nonlinear CA from this selected class is shown to be resistant against Meier-Staffelbach attack on rule 30, justifying the applicability of 4-neighbourhood CA as better cryptographic primitives.

The U.S. National Security Agency (NSA) developed the SIMON and SPECK families of lightweight block ciphers as an aid for securing applications in very constrained environments where AES may not be suitable. This paper summarizes the algorithms, their design rationale, along with current cryptanalysis and implementation results.

MISTY1 is a block cipher designed by Matsui in 1997. It was well evaluated and standardized by projects, such as CRYPTREC, ISO/IEC, and NESSIE. In this paper, we propose a key recovery attack on the full MISTY1, i.e., we show that 8-round MISTY1 with 5 FL layers does not have 128-bit security. Many attacks against MISTY1 have been proposed, but there is no attack against the full MISTY1. Therefore, our attack is the first cryptanalysis against the full MISTY1. We construct a new integral characteristic by using the propagation characteristic of the division property, which was proposed in 2015. We first improve the division property by optimizing a public S-box and then construct a 6-round integral characteristic on MISTY1. Finally, we recover the secret key of the full MISTY1 with $2^{63.58}$ chosen plaintexts and $2^{121}$ time complexity. Moreover, if we can use $2^{63.994}$ chosen plaintexts, the time complexity for our attack is reduced to $2^{107.9}$. Note that our cryptanalysis is a theoretical attack. Therefore, the practical use of MISTY1 will not be affected by our attack.

We present here optimized implementations of the MAKWA password hashing function on an AMD Radeon HD 7990 GPU, and compare its efficiency with an Intel i7 4770K CPU for systematic dictionary attacks. We find that the GPU seems to get more hashing done for a given budget, but not by a large amount (the GPU is less than twice as efficient as the CPU). Raising the MAKWA modulus size to 4096 bits, instead of the default 2048 bits, should restore the balance in favour of the CPU. We also find that power consumption, not hardware retail price, is likely to become the dominant factor for industrialized, long-term attacking efforts.

In this paper, we show structural cryptanalyses against two popular networks, i.e., the Feistel Network and the Substitute-Permutation Network (SPN). Our cryptanalyses are distinguishing attacks by an improved integral distinguisher. The integral distinguisher is one of the most powerful attacks against block ciphers, and it is usually constructed by evaluating the propagation characteristic of integral properties, e.g., the ALL or BALANCE property. However, the integral property does not derive useful distinguishers against block ciphers with non-bijective functions and bit-oriented structures. Moreover, since the integral property does not clearly exploit the algebraic degree of block ciphers, it tends not to construct useful distinguishers against block ciphers with low-degree functions. In this paper, we propose a new property called {\it the division property}, which is the generalization of the integral property. It can effectively construct the integral distinguisher even if the block cipher has non-bijective functions, bit-oriented structures, and low-degree functions. From viewpoints of the attackable number of rounds or chosen plaintexts, the division property can construct better distinguishers than previous methods. Although our attack is a generic attack, it can improve several integral distinguishers against specific cryptographic primitives. For instance, it can reduce the required number of chosen plaintexts for the 10-round distinguisher on Keccak-f from $2^{1025}$ to $2^{515}$. For the Feistel cipher, it theoretically proves that Simon 32, 48, 64, 96, and 128 have 9-, 11-, 11-, 13-, and 13-round integral distinguishers, respectively.

We demonstrate the first attacks on the SPN ciphers with 6, 7, 8, and 9 secret layers. In particular, we show a decomposition attack on the SASASASAS scheme when the S-box size M and the block length N satisfy the condition M^2 < N (for example, 8-bit S-box and 128-bit block).

The Kalyna block cipher was selected during Ukrainian National Public Cryptographic Competition (2007-2010) and its slight modification was approved as the new encryption standard of Ukraine in 2015. Main requirements for Kalyna were both high security level and high performance of software implementation on general-purpose 64-bit CPUs. The cipher has SPN-based (Rijndael-like) structure with increased MDS matrix size, a new set of four different S-boxes, pre- and postwhitening using modulo 2^{64} addition and a new construction of the key schedule. Kalyna supports block size and key length of 128, 256 and 512 bits (key length can be either equal or double of the block size). On the time of this paper publishing, no more effective cryptanalytic attacks than exhaustive search are known. In this paper we present the adapted English translated specification of Kalyna as it is given in the national standard of Ukraine.

Two lightweight block cipher families, SIMON and SPECK, have been proposed by researchers from the NSA recently. In this paper, we introduce Simeck, a new family of lightweight block ciphers that combines the good design components from both SIMON and SPECK, in order to devise even more compact and efficient block ciphers. For Simeck32/64, we can achieve 505 GEs (before the Place and Route phase) and 549 GEs (after the Place and Route phase), with the power consumption of 0.417 $\mu W$ in CMOS 130nm ASIC, and 454 GEs (before the Place and Route phase) and 488 GEs (after the Place and Route phase), with the power consumption of 1.292 $\mu W$ in CMOS 65nm ASIC. Furthermore, all of the instances of Simeck are smaller than the ones of hardware-optimized cipher SIMON in terms of area and power consumption in both CMOS 130nm and CMOS 65nm techniques. In addition, we also give the security evaluation of Simeck with respect to many traditional cryptanalysis methods, including differential attacks, linear attacks, impossible differential attacks, meet-in-the-middle attacks, and slide attacks. Overall, all of the instances of Simeck can satisfy the area, power, and throughput requirements in passive RFID tags.

For constrained devices, standard cryptographic algorithms can be too big, too slow or too energy-consuming. The area of lightweight cryptography studies new algorithms to overcome these problems. In this paper, we will focus on symmetric-key encryption, authentication and hashing. Instead of providing a full overview of this area of research, we will highlight three interesting topics. Firstly, we will explore the generic security of lightweight constructions. In particular, we will discuss considerations for key, block and tag sizes, and explore the topic of instantiating a pseudorandom permutation (PRP) with a non-ideal block cipher construction. This is inspired by the increasing prevalence of lightweight designs that are not secure against related-key attacks, such as PRINCE, PRIDE or Chaskey. Secondly, we explore the efficiency of cryptographic primitives. In particular, we investigate the impact on efficiency when the input size of a primitive doubles. Lastly, we provide some considerations for cryptographic design. We observe that applications do not always use cryptographic algorithms as they were intended, which negatively impacts the security and/or efficiency of the resulting implementations.

This memo collects references to published cryptanalytic results which are directly relevant to the security evaluation of CAESAR first round algorithm STRIBOB and its second round tweaked variant, WHIRLBOB. During the first year after initial publication of STRIBOB and WHIRLBOB, no cryptanalytic breaks or other serious issues have emerged. The main difference in the security between the two variants is that WHIRLBOB allows easier creation of constant-time software implementations resistant to cache timing attacks.