Scan chains, a design for testability (DFT) feature, are included in most modern-day ICs. But, it opens a side channel for attacking cryptographic chips. We propose a methodology by which we can recover internal states of any stream cipher using scan chains without knowledge of its design. We consider conven- tional scan-chain design which is normally not scram- bled or protected in any other way. In this scenario the challenge of the adversary is to obtain the corre- spondence of output of the scan chain and the internal state registers of the stream cipher. We present a math- ematical model of the attack and the correspondence between the scan chain-outputs and the internal state bits have been proved under this model. We propose an algorithm that through o-line and on-line simulation forms bijection between the above mentioned sets and thus nds the required correspondence. We also give an estimate of the number of o-line simulations necessary for nding the correspondence. The proposed strategy is successfully applied to eS- tream hardware based nalists MICKEY-128 2.0, Triv- ium and Grain-128. To the best of our knowledge, this is the rst scan based attack against full round Grain-128 and only the fourth reported cryptanalysis. This attack on Trivium is better than that of the published scan- attack on Trivium. This scan-based attack is also the rst reported scan based cryptanalysis against MICKEY- 128 2.0.

This paper presents differential fault analysis of the MICKEY family of stream ciphers, one of the winners of eStream project. The current attacks are of the best performance among all the attacks against MICKEY ciphers reported till date. The number of faults required with respect to state size is about 1.5 times the state size. We obtain linear equations to determine state bits. The fault model required is reasonable. The fault model is further relaxed without reproducing the faults and allowing multiple bit faults. In this scenario, more faults are required when reproduction is not allowed whereas, it has been shown that the number of faults remains same for multiple bit faults.

In this paper, we present fault attack on Grain family of stream ciphers, an eStream finalist. The earlier fault attacks on Grain work on LFSR whereas our target for fault induction is the NFSR. Our attack requires a small number of faults to be injected; 150 only for Grain v1 and only 312 and 384 for Grain-128 and Grain-128a, respectively. The number of faults are much lesser than the earlier reported fault attacks; 1587 for Grain-128 and 1831 for Grain-128a.

In this paper we mount the cube attack on the Keccak sponge function. The cube attack, formally introduced in 2008, is an algebraic technique applicable to cryptographic primitives whose output can be described as a low-degree polynomial in the input. Our results show that 5- and 6-round Keccak sponge function is vulnerable to this technique. All the presented attacks have practical complexities and were verified on a desktop PC.

Basing on the original Cube attack, this paper proposes an improved method of Cube attack on stream ciphers, which makes improvement on the pre-processing phase of the original attack. The new method can induce maxterms of higher-order from those of lower-order by the trade-off between time and space, thus recovering more key bits and reducing the search complexity on higher-dimension. In this paper, the improved attack is applied to Lili-128 algorithm and reduced variants of Trivium algorithm. We can recover 88 key bits of Lili-128 algorithm within time complexity of 2^14 and 48 key bits of Trivium algorithm can be recovered by cubes with dimension no larger than 8 when the initialization round is 576, the results are much better than those of the original attacks.

Sablier is an authenticated encryption cipher submitted to the CAESAR competition, which is composed of the encryption Sablier v1 and the authentication \textup{Au}. In this work we present a state recovery attack against the encryption Sablier v1 with time complexity about $2^{44}$ operations and data complexity about 24 of 16-bit keywords. Our attack is practical in the workstation. It is noticed that the update of the internal state of Sablier v1 is invertible, thus our attack can further deduce a key recovery attack and a forgery attack against the authenticated encryption Sablier. The result shows that Sablier v1 is far from the goal of its security design (80-bit level).

We evaluate the security of the recently proposed authenticated encryption scheme POET with regard to weak keys when its universal hash functions are instantiated with finite field multiplications. We give explicit constructions for weak key classes not covered by POET's weak key testing strategy, and demonstrate how to leverage them to obtain universal forgeries.

Achterbahn stream cipher is proposed as a candidate for ECRYPT eSTREAM project which deals with key of length 80-bit. The linear distinguishing attack,which aims at distinguishing the keystream from purely random keystream,is employed to Achterbahn stream cipher. A linear distinguishing attack is based on linear sequential circuit approximation technique which distinguishes statistical bias in the keystream. In order to build the distinguisher, linear approximations of both non-linear feedback shift register (NLFSR) and the non-linear Boolean combining function R:F_2^8→F_2 are used. The keystream sequence generated by this algorithm consist a distinguisher with its probability bias〖 2〗^(-1809). Thus, to distinguish the Achterbahn, we only need 1/ε^2 =〖〖(2〗^1809)〗^2=2^3618 keystream bits and the time complexity is about 10/ε^2 =2^3621.3 which is much higher than the exhaustive key search O(2^80).

We describe a security-preserving construction of a random permutation of domain size~$N$ from a random function, the construction tolerating adversaries asking all~$N$ plaintexts, yet employing just $\Theta(\lg N)$ calls, on average, to the one-bit-output random function. The approach is based on card shuffling. The basic idea is to use the \textit{sometimes-recurse} transformation: lightly shuffle the deck (with some other shuffle), cut the deck, and then recursively shuffle one of the two halves. Our work builds on a recent paper of Ristenpart and Yilek.

We study the problem of efficient (sub-linear) fuzzy search on encrypted outsourced data, in the symmetric-key setting. In particular, a user who stores encrypted data on a remote untrusted server forms queries that enable the server to efficiently locate the records containing the requested keywords, even though the user may misspell keywords or provide noisy data in the query. We define an appropriate primitive for a general \emph{closeness} function on the message space that we call \emph{efficiently fuzzy-searchable encryption} (\emph{EFSE}). Next we identify an optimal security notion for EFSE. We demonstrate that existing schemes do not meet our security definition and propose a new scheme that we prove secure under basic assumptions. Unfortunately, the scheme requires large ciphertext length, but we show that, in a sense, this space-inefficiency is unavoidable for a general, optimally-secure scheme. Seeking the right balance between efficiency and security, we then show how to construct schemes that are more efficient and satisfy a weaker security notion that we propose. To illustrate, we present and analyze a more space-efficient scheme for supporting fuzzy search on biometric data that achieves the weaker notion.

In this paper, we investigate the properties of iterative non-injective functions and the security of primitives where they are used. First, we introduce the Collision Probability Spectrum (CPS) parameter to quantify how far from a permutation a function is. In particular, we show that the output size decreases linearly with the number of iterations whereas the collision trees grow quadratically. Secondly, we investigate the T-sponge construction and show how certain CPS and rate values lead to an improved preimage attack on long messages. As an example, we find collisions for the GLUON-64 internal function, approximate its CPS, and show an attack that violates the security claims. For instance, if a message ends with a sequence of 1~Mb (respectively 1~Gb) of zeros, then our preimage search takes time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$.

Encryption and compression are frequently used together in both network and storage systems, for example in TLS. Despite often being used together, there has not been a formal framework for analyzing these combined systems; moreover, the systems are usually just a simple chaining of compression followed by encryption. In this work, we present the first formal framework for proving security in combined compression-encryption schemes and relate it to the traditional notion of semantic security. We call this entropy-restricted semantic security. Additionally, we present a new, efficient cipher, called the squeeze cipher, that combines compression and encryption into a single primitive and provably achieves our entropy-restricted security.

Nonlinearity and resiliency are well known as some of the most important cryptographic parameters of Boolean functions, it is actual the problem of the constructing of functions that have high nonlinearity and resiliency simultaneously. In 2000 three groups of au\-thors obtained independently the upper bound $2^{n-1}-2^{m+1}$ for the nonlinearity of an $m$-resilient function of $n$ variables. It was shown that if this bound is achieved then $(n-3)/2\le m\le n-2$. Simultaneously in 2000 Tarannikov constructed functions that achieve this bound for $(2n-7)/3\le m\le n-2$. In 2001 Tarannikov constructed such functions for $0.6n-1\le m$ introducing for this aim so called proper matrices; later in 2001 Fedorova and Tarannikov constructed by means of proper matrices the functions that achieve the bound $2^{n-1}-2^{m+1}$ for $m\ge cn(1+o(1))$ where $c=1/\log_2(\sqrt{5}+1)=0.5902...$ but proved simultaneously that by means of proper matrices it is impossible to improve this result. During the period since 2001 it was not any further progress in the problem on the achievability of the bound $2^{n-1}-2^{m+1}$ in spite of this problem was well known and actual except the constructing in 2006--2007 by three groups of authors by means of a computer search concrete functions for $n=9$, $m=3$. In this paper we find the new approach that uses the generalization of the concept of proper matrices. We formulate com\-bi\-na\-to\-ri\-al problems solutions of which allow to construct generalized proper matrices with parameters impossible for old proper matrices. As a result we obtain the constructions of $m$-resilient functions of $n$ variables with maximal nonlinearity for $m\ge cn(1+o(1))$ where $c=0.5789...$, and also we demonstrate how further advance in combinatorial problems follows an additional decrease of the constant $c$.

\paes~is an authenticated encryption scheme designed by Ye {\it et al.}, and submitted to the CAESAR competition. The designers claim that \paese, which is one of the designs of the \paes-family, provides 128-bit security in the nonce misuse model. In this note, we show our forgery attack against \paese. Our attack works in the nonce misuse model. The attack exploits the slow propagation of message differences. The attack is very close to the universal forgery attack. As long as the target message is not too short, {\it e.g.} more than 10 blocks (160 bytes), a tag is forged only with $2^{11}$ encryption oracle calls, $2^{11}$ computational cost, and negligible memory.

\panda~is an authenticated encryption scheme designed by Ye {\it et al.}, and submitted to the CAESAR competition. The designers claim that \pandas, which is one of the designs of the \panda-family, provides 128-bit security in the nonce misuse model. In this note, we describe our forgery attack against \pandas. Our attack works in the nonce misuse model. It exploits the fact that the message processing function and the finalization function are identical, and thus a variant of the length-extension attack can be applied. We can find a tag for a pre-specified formatted message with 2 encryption oracle calls, $2^{64}$ computational cost, and negligible memory.

In the context of authenticated encryption (AE), generic composition has referred to the construction of an AE scheme by gluing together a conventional (privacy-only) encryption scheme and a MAC. Since the work of Bellare and Namprempre (2000) and then Krawczyk (2001), the conventional wisdom has become that there are three forms of generic composition, with Encrypt-then-MAC the only one that generically works. However, many caveats to this understanding have surfaced over the years. Here we explore this issue further, showing how this understanding oversimplifies the situation because it ignores the results’ sensitivity to definitional choices. When encryption is formalized differently, making it either IV-based or nonce-based, rather than probabilistic, and when the AE goal is likewise changed to take in a nonce, qualitatively different results emerge. We explore these alternatives versions of the generic-composition story. We also evidence the overreaching understanding of prior generic-composition results by pointing out that the Encrypt-then-MAC mechanism of ISO 19772 is completely wrong.

Multiple encryption---the practice of composing a blockcipher several times with itself under independent keys---has received considerable attention of late from the standpoint of provable security. Despite these efforts proving definitive security bounds (i.e., with matching attacks) has remained elusive even for the special case of triple encryption. In this paper we close the gap by improving both the best known attacks and best known provable security, so that both bounds match. Our results apply for arbitrary number of rounds and show that the security of $\ell$-round multiple encryption is precisely $\exp(\kappa + \min\{\kappa (\ell'-2)/2), n (\ell'-2)/\ell'\})$ where $\exp(t) = 2^t$ and where $\ell' = 2\lceil \ell/2\rceil$ is the even integer closest to $\ell$ and greater than or equal to $\ell$, for all $\ell \geq 1$. Our technique is based on Patarin's H-coefficient method and reuses a combinatorial result of Chen and Steinberger originally required in the context of key-alternating ciphers.

In this short article, we describe a very practical and simple attack on the authentication part of POET authenticated encryption mode proposed at FSE 2014. POET is a provably secure scheme that was designed to resist various attacks where the adversary is allowed to repeat the nonce, or even when the message is output before verifying the validity of the tag when querying the decryption oracle. However, we demonstrate that using only a single encryption query and a negligible amount of computations, even without any special misuse from the attacker, it is possible to generate many valid ciphertext/tag pairs for POET. Our work shows that one should not use POET for any application where authentication property is required. Furthermore, we propose a possible patch to overcome this particular issue, yet without backing up this patch with a security proof.

The integral attack is one of the most powerful attack against block ciphers. In this paper, we propose two new techniques for the integral attack, the FFT technique and the key concealment technique. The FFT technique is useful for the integral attack with enormous chosen plaintexts. As the previous result using FFT, Collard et al. showed a new technique which reduces the complexity for the linear attack. In this paper, we review the result of Collard et al. to estimate the complexity in detail, and we show the complexity can be estimated from the number of times using the addition of integers. Moreover, we show that attacks using FFT can be applied to the integral attack. As applications, we show integral attacks against AES and CLEFIA. For AES, we show that 6-round AES can be attacked with about $2^{51.7} additions. For CLEFIA, we show that 12-round CLEFIA can be attacked with about $2^{86.9}$ additions.

This paper presents the design of a lightweight, yet software friendly, block cipher. Most of the lightweight block ciphers are nibble-oriented as the implementation of a 4-bit S-box is much more compact than an 8-bit S-box. This paper uses a novel implementation of multiplicative inverse for 8-bit S-boxes using LFSR requiring only 138 gate-equivalent. With this powerful scheme, we design a lightweight block cipher competitive with existing standards in terms of hardware gate equivalent first time using an 8-bit S-box.

ANSI X9.24-1:2009 specifies the key check value, which is used to verify the integrity of the blockcipher key. This value is defined as the most significant bits of the ciphertext of the zero block, and is assumed to be publicly known data for verification. ISO/IEC 9797-1:2011 illustrates a total of ten CBC MACs, where one of these MACs, the basic CBC MAC, is widely known to be insecure. In this paper, we consider the remaining nine CBC MACs and derive the quantitative security impact of using the key check value. We first show attacks against five MACs by taking advantage of the knowledge of the key check value. We then prove that the analysis is tight, in a concrete security paradigm. For the remaining four MACs, we prove that the standard birthday bound still holds even with the presence of the key check value. As a result, we obtain a complete characterization of the impact of using ANSI X9.24-1 key check value with the ISO/IEC 9797-1 MACs.

We study a method for key predistribution in a network of $n$ users where pairwise keys are computed by hashing users' IDs along with secret information that has been (pre)distributed to the network users by a trusted entity. A communication graph $G$ can be specified to indicate which pairs of users should be able to compute keys. We determine necessary and sufficient conditions for schemes of this type to be secure. We also consider the problem of minimizing the storage requirements of such a scheme; we are interested in the total storage as well as the maximum storage required by any user. Minimizing the total storage is NP-hard, whereas minimizing the maximum storage required by a user can be computed in polynomial time.

We define and analyze the security of a blockcipher mode of operation, CLOC, for provably secure authenticated encryption with associated data. The design of CLOC aims at optimizing previous schemes, CCM, EAX, and EAX-prime, in terms of the implementation overhead beyond the blockcipher, the precomputation complexity, and the memory requirement. With these features, CLOC is suitable for handling short input data, say 16 bytes, without needing precomputation nor large memory. This property is especially beneficial to small microprocessors, where the word size is typically 8 bits or 16 bits, and there are significant restrictions in the size and the number of registers. CLOC uses a variant of CFB mode in its encryption part and a variant of CBC MAC in the authentication part. We introduce various design techniques in order to achieve the above mentioned design goals. We prove CLOC secure, in a reduction-based provable security paradigm, under the assumption that the blockcipher is a pseudorandom permutation. We also present our preliminary implementation results.

We introduce {\em honey encryption} (HE), a simple, general approach to encrypting messages using low min-entropy keys such as passwords. HE is designed to produce a ciphertext which, when decrypted with any of a number of {\em incorrect} keys, yields plausible-looking but bogus plaintexts called {\em honey messages}. A key benefit of HE is that it provides security in cases where too little entropy is available to withstand brute-force attacks that try every key; in this sense, HE provides security beyond conventional brute-force bounds. HE can also provide a hedge against partial disclosure of high min-entropy keys. HE significantly improves security in a number of practical settings. To showcase this improvement, we build concrete HE schemes for password-based encryption of RSA secret keys and credit card numbers. The key challenges are development of appropriate instances of a new type of randomized message encoding scheme called a {\em distribution-transforming encoder} (DTE), and analyses of the expected maximum loading of bins in various kinds of balls-and-bins games.

We study the security of \emph{key-alternating Feistel} ciphers, a class of key-alternating ciphers with a Feistel structure. Alternatively, this may be viewed as the study of Feistel ciphers where the pseudorandom round functions are of the form $F_i(x\oplus k_i)$, where $k_i$ is the (secret) round key and $F_i$ is a \emph{public} random function that the adversary is allowed to query in a black-box way. Interestingly, our results can be seen as a generalization of traditional results \emph{à la} Luby-Rackoff in the sense that we can derive results for this model by simply letting the number of queries of the adversary to the public random functions $F_i$ be zero in our general bounds. We make an extensive use of the coupling technique. In particular (and as a result of independent interest), we improve the analysis of the coupling probability for balanced Feistel schemes previously carried out by Hoang and Rogaway (CRYPTO 2010).

We conduct an analysis of the RC4 algorithm as it is used in the IEEE WPA/TKIP wireless standard. In that standard, RC4 keys are computed on a per-frame basis, with specific key bytes being set to known values that depend on 2 bytes of the WPA frame counter (called the TSC). We observe very large, TSC-dependent biases in the RC4 keystream when the algorithm is keyed according to the WPA specification. These biases permit us to mount an effective statistical, plaintext-recovering attack in the situation where the same plaintext is encrypted in many different frames (the so-called ``broadcast attack'' setting). We assess the practical impact of these attacks on WPA/TKIP.

Differential fault analysis (DFA) poses a significant threat to Advanced Encryption Standard (AES). It has been demonstrated that DFA can use only a single faulty ciphertext to reveal the secret key of AES in an average of 230 computation. Traditionally, concurrent error detection (CED) is used to protect AES against DFA. However, we emphasize that conventional CED assumes a uniform distribution of faults, which is not a valid assumption in the context of DFA. In contrast, we show practical examples which highlight that an attacker can inject specific and exploitable faults, thus threatening existing CED. This paper brings to the surface a new CED approach for cryptography, aimed at providing provable security by detecting all possible DFA-exploitable faults, which is a small subset of the entire fault space. We analyze the fault coverage of conventional CED against DFA-exploitable faults, and we find that the fault coverage of most of these techniques are significantly lower than the one they claimed. We stress that for security, it is imperative that CED should provide 100% fault coverage for DFA-exploitable faults. We further propose an invariance-based CED which provides 100% provable security against all known DFA of AES.

It is well known that the classical three- and four-round Feistel constructions are provably secure under chosen-plaintext and chosen-ciphertext attacks, respectively. However, irrespective of the number of rounds, no Feistel construction can resist related-key attacks where the keys can be offset by a constant. In this paper we show that, under suitable reuse of round keys, security under related-key attacks can be provably attained. Our modification is substantially simpler and more efficient than alternatives obtained using generic transforms, namely the PRG transform of Bellare and Cash (CRYPTO 2010) and its random-oracle analogue outlined by Lucks (FSE 2004). Additionally we formalize Luck's transform and show that it does not always work if related keys are derived in an oracle-dependent way, and then prove it sound under appropriate restrictions.

Liskov, Rivest and Wagner formalized the tweakable blockcipher (TBC) primitive at CRYPTO'02. The typical recipe for instantiating a TBC is to start with a blockcipher, and then build up a construction that admits a tweak. Almost all such constructions enjoy provable security only to the birthday bound, and the one that does achieve security beyond the birthday bound (due to Minematsu) severely restricts the tweak size and requires per-invocation blockcipher rekeying. This paper gives the first TBC construction that simultaneously allows for arbitrarily “wide” tweaks, does not rekey, and delivers provable security beyond the birthday bound. Our construction is built from a blockcipher and an $\eAXU$ hash function. As an application of the TBC primitive, LRW suggest the TBC-MAC construction (similar to CBC-MAC but chaining through the tweak), but leave open the question of its security. We close this question, both for TBC-MAC as a PRF and a MAC. Along the way, we find a nonce-based variant of TBC-MAC that has a tight reduction to the security of the underlying TBC, and also displays graceful security degradation when nonces are misused. This result is interesting on its own, but it also serves as an application of our new TBC construction, ultimately giving a variable input-length PRF with beyond birthday-bound security.

In this note, we describe an error in the proof for CLRW2 given by Landecker et al. in their paper at CRYPTO 2012 on the beyond-birthday-bound security for tweakable block ciphers. We are able to resolve the issue, give a new bound for the security of CLRW2, and identify a potential limitation of this proof technique when looking to extend the scheme to provide asymptotic security.

In this paper, we introduce a new class of double-block-length hash functions. Using the ideal cipher model, we prove that these hash functions, dubbed \MJH, are asymptotically collision resistant up to $O(2^{n(1-\epsilon)})$ query complexity for any $\epsilon>0$ in the iteration, where $n$ is the block size of the underlying blockcipher. When based on $n$-bit key blockciphers, our construction, being of rate 1/2, provides better provable security than MDC-2, the only known construction of a rate-1/2 double-length hash function based on an $n$-bit key blockcipher with non-trivial provable security. Moreover, since key scheduling is performed only once per message block for MJH, our proposal significantly outperforms MDC-2 in efficiency. When based on a $2n$-bit key blockcipher, we can use the extra $n$ bits of key to increase the amount of payload accordingly. Thus we get a rate-1 hash function that is much faster than existing proposals, such as Tandem-DM with comparable provable security. The proceedings version of this paper appeared in CT-RSA 2011.

While standard message authentication codes (MACs) guarantee authenticity of messages, they do not, in general, guarantee the anonymity of the sender and recipient. For example it may be easy for an observer to determine whether or not two authenticated messages were sent by the same party even without any information about the secret key used. However preserving any uncertainty an attacker may have about the identities of honest parties engaged in authenticated communication is an important goal of many cryptographic applications. For example this is stated as an explicit goal of modern cellphone authentication protocols~\cite{3GPP} and RFID based authentication systems\cite{Vaudenay10}. In this work we introduce and construct a new fundamental cryptographic primitive called \emph{key indistinguishable} (KI) MACs. These can be used to realize many of the most important higher-level applications requiring some form of anonymity and authenticity~\cite{AHMPR14}. We show that much (though not all) of the modular MAC construction framework of~\cite{DodisKPW12} gives rise to several variants of KI MACs. On the one hand, we show that KI MACs can be built from hash proof systems and certain weak PRFs allowing us to base security on such assumption as DDH, CDH and LWE. Next we show that the two direct constructions from the LPN assumption of~\cite{DodisKPW12} are KI, resulting in particularly efficient constructions based on structured assumptions. On the other hand, we also give a very simple and efficient construction based on a PRF which allows us to base KI MACs on some ideal primitives such as an ideal compression function (using HMAC) or block-cipher (using say CBC-MAC). In particular, by using our PRF construction, many real-world implementations of MACs can be easily and cheaply modified to obtain a KI MAC. Finally we show that the transformations of~\cite{DodisKPW12} for increasing the domain size of a MAC as well as for strengthening the type of unforgeability it provides also preserve (or even strengthen) the type of KI enjoyed by the MAC. All together these results provide a wide range of assumptions and construction paths for building various flavors of this new primitive.

Let $d \geq 1$ be an integer and $R_1$ be a finite ring whose elements are called {\bf block}. A $d$-block universal hash over $R_1$ is a vector of $d$ multivariate polynomials in message and key block such that the maximum {\em differential probability} of the hash function is ``low''. Two such single block hashes are pseudo dot-product (\tx{PDP}) hash and Bernstein-Rabin-Winograd (\tx{BRW}) hash which require $\frac{n}{2}$ multiplications for $n$ message blocks. The Toeplitz construction and $d$ independent invocations of \tx{PDP} are $d$-block hash outputs which require $d \times \frac{n}{2}$ multiplications. However, here we show that {\em at least $(d-1) + \frac{n}{2}$ multiplications are necessary} to compute a universal hash over $n$ message blocks. We construct a {\em $d$-block universal hash, called \tx{EHC}, which requires the matching $(d -1) + \frac{n}{2}$ multiplications for $d \leq 4$}. Hence it is optimum and our lower bound is tight when $d \leq 4$. It has similar parllelizibility, key size like Toeplitz and so it can be used as a light-weight universal hash.

In this paper, we revisit the old problem asking the exact provable security of triple encryption in the ideal cipher model. For a blockcipher with key length k and block size n, triple encryption is known to be secure up to 2^{k+min{k/2,n/2}} queries, while the best attack requires 2^{k+min{k,n/2}} query complexity. So there is a gap between the upper and lower bounds for the security of triple encryption. We close this gap by proving the security up to 2^{k+min{k,n/2}} query complexity. With the DES parameters, triple encryption is secure up to 2^{82.5} queries, greater than the current bound of 2^{78.3} and comparable to 2^{83.5} for 2-XOR-cascade. We also analyze the security of two-key triple encryption, where the first and the third keys are identical. We prove that two-key triple encryption is secure up to 2^{k+min{k,n/2}} queries to the underlying blockcipher and 2^{min{k,n/2}} queries to the outer permutation. For the DES parameters, this result is interpreted as the security of two-key triple encryption up to 2^{32} plaintext-ciphertext pairs and 2^{81.7} blockcipher encryptions.

A $t$-round \emph{key-alternating cipher} (also called \emph{iterated Even-Mansour cipher}) can be viewed as an abstraction of AES. It defines a cipher $E$ from $t$ fixed public permutations $P_1, \ldots, P_t : \bits^n \ra \bits^n$ and a key $k = k_0\Vert \cdots \Vert k_t \in \bits^{n(t+1)}$ by setting $E_{k}(x) = k_t \oplus P_t(k_{t-1} \oplus P_{t-1}(\cdots k_1 \oplus P_1(k_0 \oplus x) \cdots))$. The indistinguishability of $E_k$ from a truly random permutation by an adversary who also has oracle access to the (public) random permutations $P_1, \ldots, P_t$ was investigated in 1997 by Even and Mansour for $t = 1$ and for higher values of $t$ in a series of recent papers. For $t = 1$, Even and Mansour proved indistinguishability security up to $2^{n/2}$ queries, which is tight. Much later Bogdanov et al$.$ (2011) conjectured that security should be $2^{\frac{t}{t+1}n}$ queries for general $t$, which matches an easy distinguishing attack (so security cannot be more) . A number of partial results have been obtained supporting this conjecture, besides Even and Mansour's original result for $t = 1$: Bogdanov et al$.$ proved security of $2^{\frac{2}{3}n}$ for $t \geq 2$, Steinberger (2012) proved security of $2^{\frac{3}{4}n}$ for $t \geq 3$, and Lampe, Patarin and Seurin (2012) proved security of $2^{\frac{t}{t+2}n}$ for all even values of $t$, thus "barely" falling short of the desired $2^{\frac{t}{t+1}n}$. Our contribution in this work is to prove the long-sought-for security bound of $2^{\frac{t}{t+1}n}$, up to a constant multiplicative factor depending on $t$. Our method is essentially an application of Patarin's H-coefficient technique. The proof contains some coupling-like and inclusion-exclusion ideas, but the main trick that pushes the computations through is to stick with the combinatorics and to refrain from rounding any quantities too early. For the reader's interest, we include a self-contained tutorial on the H-coefficient technique.

FIDES is a lightweight authenticated cipher, presented at CHES 2013. The cipher has two version, providing either 80-bit or 96-bit security. In this paper, we describe internal state-recovery attacks on both versions of FIDES, and show that once we recover the internal state, we can use it to immediately forge any message. Our attacks are based on a guess-and-determine algorithm, exploiting the slow diffusion of the internal linear transformation of FIDES. Our most basic attacks have time complexities of 2^{75} and 2^{90} for FIDES-80 and FIDES-96, respectively, use a very small amount of memory, and their most distinctive feature is their very low data complexity: the attacks require at most 24 bytes of an arbitrary plaintext and its corresponding ciphertext, in order to break the cipher with probability 1. In addition to the basic attacks, we describe optimized attacks which exploit additional data in order to reduce the time complexities to 2^{73} and 2^{88} for FIDES-80 and FIDES-96, respectively.

The paper is about methodology to detect and demonstrate impossible differentials in a block cipher. We were inspired by the shrinking technique proposed by Biham et al. in 1999 which recovered properties of scalable block cipher structures from numerical search on scaled down variants. Attempt to bind all concepts and techniques of impossible differentials together reveals a view of the search for impossible differentials that can benefit from the computational power of a computer. We demonstrate on generalized Feistel networks with internal permutations an additional clustering layer on top of shrinking which let us merge numerical data into relevant human-readable information to be used in an actual proof. After that, we show how initial analysis of scaled down TEA-like schemes leaks the relevant part of the design and the length and ends of the impossible differentials. We use that initial profiling to numerically discover 4 15-round impossible differentials (beating the current 13-round) and thousands of shorter ones.

We present a new approach to the compression technique of Lyubashevsky et al for lattice-based signatures based on learning with errors (LWE). Our ideas seem to be particularly suitable for signature schemes whose security, in the random oracle model, is based on standard worst-case computational assumptions. Our signatures are shorter than any previous proposal for provably-secure signatures based on standard lattice problems: at the 128-bit level we improve signature size from (more than) 16500 bits to around 9000 to 12000 bits.

In this paper, we first prove beyond-birthyday-bound security for the Misty structure. Specifically, we show that an $r$-round Misty structure is secure against CCA attacks up to $O(2^{\frac{rn}{r+7}})$ query complexity, where $n$ is the size of each round permutation. So for any $\epsilon>0$, a sufficient number of rounds would guarantee the security of the Misty structure up to $2^{n(1-\epsilon)}$ query complexity.

In January 2013, the Stribog hash function officially replaced GOST R 34.11-94 as the new Russian cryptographic hash standard GOST R 34.11-2012. Stribog is an AES-based primitive and is considered as an asymmetric reply to the new SHA-3 selected by NIST. In this paper we investigate the structural integral properties of reduced version of the Stribog compression function and its internal permutation. Specifically, we present a forward and backward higher order integrals that can be used to distinguish 4 and 3.5 rounds, respectively. Moreover, using the start from the middle approach, we combine the two proposed integrals to get 6.5-round and 7.5-round distinguishers for the internal permutation and 6-round and 7-round distinguishers for the compression function.

Universal hash functions are commonly used primitives for fast and secure message authentication in the form of Message Authentication Codes (MACs) or Authenticated Encryption with Associated Data (AEAD) schemes. These schemes are widely used and standardised, the most well known being McGrew and Viega's Galois/Counter Mode (GCM). In this paper we identify some properties of hash functions based on polynomial evaluation that arise from the underlying algebraic structure. As a result we are able to describe a general forgery attack, of which Saarinen's cycling attack from FSE 2012 is a special case. Our attack removes the requirement for long messages and applies regardless of the field in which the hash function is evaluated. Furthermore we provide a common description of all published attacks against GCM, by showing that the existing attacks are the result of these algebraic properties of the polynomial-based hash function. We also greatly expand the number of known weak GCM keys and show that almost every subset of the keyspace is a weak key class. Finally, we demonstrate that these algebraic properties and corresponding attacks are highly relevant to GCM/2+, a variant of GCM designed to increase the efficiency in software.

In this paper, we provide performance measures for software implementations of the NSA-designed Speck128 block cipher together with various existing authenticated encryption modes. We investigated Speck128 using GCM, CCM, EAX, OCB3, COPA, and PAEAD-1, and we briefly discuss performance advantages and disadvantages of each mode. Our results indicate that Speck128 is capable of performing extremely fast authenticated encryption, as fast as 3.4 cycles/byte on a modern x86-based 64-bit processor.

In this paper, we propose a new lightweight hash function supporting three different digest sizes: 80, 96 and 128 bits, providing preimage security from 64 to 120 bits, second preimage and collision security from 40 to 60 bits. LHash requires about 817 GE and 1028 GE with a serialized implementation. In faster implementations based on function $T$, LHash requires 989 GE and 1200 GE with 54 and 72 cycles per block, respectively. Furthermore, its energy consumption evaluated by energy per bit is also remarkable. LHash allows to make trade-offs among security, speed, energy consumption and implementation costs by adjusting parameters. The design of LHash employs a kind of Feistel-PG structure in the internal permutation, and this structure can utilize permutation layers on nibbles to improve the diffusion speed. The adaptability of LHash in different environments is good, since different versions of LHash share the same basic computing module. The low-area implementation comes from the hardware-friendly S-box and linear diffusion layer. We evaluate the resistance of LHash against known attacks and confirm that LHash provides a good security margin.

We develop new schemes for deterministically updating a stored cryptographic key that provide security against an internal adversary who can control the update computation and leak bounded amounts of information to the outside world. Our schemes are much more efficient than the previous schemes for this model, due to Dziembowski, Kazana and Wichs (CRYPTO 2011). Specifically, our update operation runs in time quasilinear in the key length, rather than quadratic, while offering a similar level of leakage resilience. In order to design our scheme, we strengthen the connections between the model of Dziembowski et al. and ``pebbling games'', showing that random-oracle-based key evolution schemes are secure as long as the graph of the update function's calls to the oracle has appropriate combinatorial properties. This builds on a connection between pebbling and the random oracle model first established by Dwork, Naor and Wee (CRYPTO 2005). Our scheme's efficiency relies on the existence (which we show) of families of ``local'' bipartite expander graphs of constant degree.

We propose a tool for automatic search for differential trails in ARX ciphers. By introducing the concept of a partial difference distribution table (pDDT) we extend Matsui's algorithm, originally proposed for DES-like ciphers, to the class of ARX ciphers. To the best of our knowledge this is the first application of Matsui's algorithm to ciphers that do not have S-boxes. The tool is applied to the block ciphers TEA, XTEA, SPECK and RAIDEN. For RAIDEN we find an iterative characteristic on all 32 rounds that can be used to break the full cipher using standard differential cryptanalysis. This is the first cryptanalysis of the cipher in a non-related key setting. Differential trails on 9, 10 and 13 rounds are found for SPECK32, SPECK48 and SPECK64 respectively. The 13 round trail covers half of the total number of rounds. These are the first public results on the security analysis of SPECK. For TEA multiple full (i.e. not truncated) differential trails are reported for the first time, while for XTEA we confirm the previous best known trail reported by Hong et al. We also show closed formulas for computing the exact additive differential probabilities of the left and right shift operations. The source code of the tool is publicly available as part of a larger toolkit for the analysis of ARX at the following address: https://github.com/vesselinux/yaarx .

On-Line Authenticated Encryption (OAE) combines privacy with data integrity and is on-line computable. Most block cipher-based schemes for Authenticated Encryption can be run on-line and are provably secure against nonce-respecting adversaries. But they fail badly for more general adversaries. This is not a theoretical observation only --~in practice, the reuse of nonces is a frequent issue. In recent years, cryptographers developed misuse resistant schemes for Authenticated Encryption. These guarantee excellent security even against general adversaries which are allowed to reuse nonces. Their disadvantage is that encryption can be performed in an off-line way, only. This paper introduces a new family of OAE schemes --called McOE -- dealing both with nonce-respecting and with general adversaries. Furthermore, we present two family members, i.e., McOE-X and McOE-G. They are based on a 'simple' block cipher. In contrast to every other OAE scheme known in literature, they provably guarantee reasonable security against general adversaries as well as standard security against nonce-respecting adversaries.

XCB is a tweakable enciphering scheme (TES) which was first proposed in 2004. The scheme was modified in 2007. We call these two versions of XCB as XCBv1 and XCBv2 respectively. XCBv2 was later proposed as a standard for encryption of sector oriented storage media in IEEE-std 1619.2 2010. There is no known proof of security for XCBv1 but the authors provided a concrete security bound for XCBv2 and a ``proof'' for justifying the bound. In this paper we show that XCBv2 is not secure as a TES by showing an easy distinguishing attack on it. For XCBv2 to be secure, the message space should contain only messages whose lengths are multiples of the block length of the block cipher. For such restricted message spaces also, the bound that the authors claim is not justified. We show this by pointing out some errors in the proof. For XCBv2 on full block messages, we provide a new security analysis. The resulting bound that can be proved is much worse than what has been claimed by the authors. Further, we provide the first concrete security bound for XCBv1, which holds for all message lengths. In terms of known security bounds, both XCBv1 and XCBv2 are worse compared to existing alternative TES.

We show how efficient and secure cryptographic mixing functions can be constructed from low-degree rotation-invariant $\phi$ functions rather than conventional S-Boxes. These novel functions have surprising properties; many exhibit inherent feeble (Boolean circuit) one-wayness and offer speed/area tradeoffs unobtainable with traditional constructs. Recent theoretical results indicate that even if the inverse is not explicitly computed in an implementation, its degree plays a fundamental role to the security of the iterated composition. To illustrate these properties, we present CBEAM, a Cryptographic Sponge Permutation based on a single $5 \times 1$-bit Boolean function. This simple nonlinear function is used to construct a 16-bit rotation-invariant$\phi$ function of Degree 4 (but with a very complex Degree 11 inverse), which in turn is expanded into an efficient 256-bit mixing function. In addition to flexible tradeoffs in hardware we show that efficient implementation strategies exist for software platforms ranging from low-end microcontrollers to the very latest x86-64 AVX2 instruction set. A rotational bit-sliced software implementation offers not only comparable speeds to AES but also increased security against cache side channel attacks. Our construction supports Sponge-based Authenticated Encryption, Hashing, and PRF/PRNG modes and is highly useful as a compact ``all-in-one'' primitive for pervasive security.

BLINKER is a light-weight cryptographic suite and record protocol built from a single permutation. Its design is based on the Sponge construction used by the SHA-3 algorithm KECCAK. We examine the SpongeWrap authenticated encryption mode and expand its padding mechanism to offer explicit domain separation and enhanced security for our specific requirements: shared secret half-duplex keying, encryption, and a MAC-and-continue mode. We motivate these enhancements by showing that unlike legacy protocols, the resulting record protocol is secure against a two-channel synchronization attack while also having a significantly smaller implementation footprint. The design facilitates security proofs directly from a single cryptographic primitive (a single security assumption) rather than via idealization of multitude of algorithms, paddings and modes of operation. The protocol is also uniquely suitable for an autonomous or semi-autonomous hardware implementation of protocols where the secrets never leave the module, making it attractive for smart card and HSM designs.

Cube attacks can be used to analyse and break cryptographic primitives that have an easy algebraic description. One example for such a primitive is the stream cipher /Trivium. In this article we give a new framework for cubes that are useful in the cryptanalytic context. In addition, we show how algebraic modelling of a cipher can greatly be improved when taking both cubes and linear equivalences between variables into account. When taking many instances of Trivium, we empirically show a saturation effect, i.e., the number of variables to model an attack will become constant for a given number of rounds. Moreover, we show how to systematically find cubes both for general primitives and also specifically for Trivium. For the latter, we have found all cubes up to round 446 and draw some conclusions on their evolution between rounds. All techniques in this article are general and can be applied to any cipher.

EAX is a mode of operation for blockciphers to implement an authenticated encryption. The original paper of EAX proved that EAX is unforgeable up to $O(2^{n/2})$ data with one verification query. However, this generally guarantees a rather weak bound for the unforgeability under multiple verification queries, i.e., only $(2^{n/3})$ data is acceptable. This paper provides an improvement over the previous security proof, by showing that EAX is unforgeable up to $O(2^{n/2})$ data with multiple verification queries. Our security proof is based on the techniques appeared in a paper of FSE 2013 by Minematsu et al. which studied the security of a variant of EAX called EAX-prime. We also provide some ideas to reduce the complexity of EAX while keeping our new security bound. In particular, EAX needs three blockcipher calls and keep them in memory as a pre-processing, and our proposals can effectively reduce three calls to one call. This would be useful when computational power and memory are constrained.

Online ciphers encrypt an arbitrary number of plaintext blocks and output ciphertext blocks which only depend on the preceding plaintext blocks. All online ciphers proposed so far are essentially serial, which significantly limits their performance on parallel architectures such as modern general-purpose CPUs or dedicated hardware. We propose the first parallelizable online cipher, COPE. It performs two calls to the underlying block cipher per plaintext block and is fully parallelizable in both encryption and decryption. COPE is proven secure against chosen-plaintext attacks assuming the underlying block cipher is a strong PRP. We then extend COPE to create COPA, the first parallelizable, online authenticated cipher with nonce-misuse resistance. COPA only requires two extra block cipher calls to provide integrity. The privacy and integrity of the scheme is proven secure assuming the underlying block cipher is a strong PRP. Our implementation with Intel AES-NI on a Sandy Bridge CPU architecture shows that both COPE and COPA are about \textit{5 times faster} than their closest competition: TC1, TC3, and McOE-G. This high factor of advantage emphasizes the paramount role of parallelizability on up-to-date computing platforms.

Rabbit stream cipher is one of the finalists of eSTREAM project which uses 128-bit secret keys. Prior to us, the attacks on Rabbit has been all focused on the bias analysis and the best result showed the distinguishing attack with complexity 2136. Our analysis in this paper, is based on chosen IV analysis on reduced N-S round of Rabbit though using multi cube tester. For this purpose we show for a mature cube we could easily identify weak subcubes which increase the probability of distinguishing for an unknown secret key. We also represent with 225 complexity, using one iteration of next state function the keystream is completely distinguishable from random.

This paper introduces Multi-Stage Fault Attacks, which allow Differential Fault Analysis of block ciphers having independent subkeys. Besides the specification of an algorithm implementing the technique, we show concrete applications to LED-128 and PRINCE and demonstrate that in both cases approximately 3 to 4 fault-injections are enough to reconstruct the full 128-bit key.

Zorro is an AES-like lightweight block cipher proposed in CHES 2013, which only uses 4 S-boxes per round. The designers showed the resistance of the cipher against various attacks and concluded the cipher has a large security margin. Recently, Guo et. al have given a key recovery attack on full-round Zorro by using the internal differential characteristics. However, the attack only works for $2^{64}$ out of $2^{128}$ keys. In this paper, the secret key selected randomly from the whole key space can be recovered with a time complexity of $2^{108}$ full-round Zorro encryptions and a data complexity of $2^{112.4}$ chosen plaintexts. We first observe that the fourth power of the MDS matrix used in Zorro equals to the identity matrix. Moveover, several iterated differential characteristics and iterated linear trails are found due to the interesting property. We select three characteristics with the largest probability to give a key recovery attack on Zorro and a linear trail with the largest correlation to show a a linear distinguishing attack with $2^{105.3}$ known plaintexts. The results show that the security of Zorro against linear and differential cryptanalysis evaluated by designers is insufficient and the block cipher Zorro is far from a random permutation.

We explain the origins of Boolean feedback functions of nonlinear feedback shift registers (NLFSRs) of fixed order n generating de Bruijn binary sequences. They all come into existence by cross joining operations starting from one maximum period feedback shift register, e.g., a linear one which always exists for any order n. The result obtained yields some constructions of NLFSRs generating maximum period $ 2^n-1 $ binary sequences.

The literature on side-channel analysis describes numerous masking schemes designed to protect block ciphers at the implementation level. Such masking schemes typically require the computation of masked tables prior to the execution of an encryption function. In this paper we revisit an attack which directly exploits this computation in such a way as to recover all or some of the masks used. We show that securely implementing masking schemes is only possible where one has access to a significant amount of random numbers.

Irregular clocking of feedback shift registers is a popular technique to improve parameters of keystream generators in stream ciphers. Another technique is to implement nonlinear functions. We join these techniques and propose Modified Alternating Step Generators built with linear and nonlinear feedback shift registers. Adequate nonlinear Boolean functions are used as feedbacks or as filtering functions of shift registers in order to increase complexity of sequences produced by individual registers and the whole generator. We investigate basic parameters of proposed keystream generators, such as period, linear complexity and randomness.

Constructing S-boxes with low differential uniformity and high nonlinearity is of cardinal significance in cryptography. In the present paper, we show that numerous differentially 4-uniform permutations over GF(2^{2k}) can be constructed by composing the inverse function and cycles over GF(2^{2k}). Two sufficient conditions are given, which ensure that the differential uniformity of the corresponding compositions equals 4. A lower bound on nonlinearity is also given for permutations constructed with the method in the present paper. Moreover, up to CCZ-equivalence, a new differentially 4-uniform permutation with the best known nonlinearity over GF(2^{2k}) with $k$ odd is constructed. For some special cycles, necessary and sufficient conditions are given such that the corresponding compositions are differentially 4-uniform.

At CHES 2013 was presented a new block cipher called Zorro. Although it uses only 4 S-boxes per round, the designers showed the resistance of the cipher against various attacks, and concluded the cipher has a large security margin. In this paper, we give a key recovery attack on the full cipher in the single-key model that works for $2^{64}$ out of $2^{128}$ keys. Our analysis is based precisely on the fact that the non-linear layer has only 4 S-boxes. We exploit this twice in a two-stage attack: first, we show that Zorro has an equivalent description that does not have constants in the rounds, and then, we launch an internal differential attack on the newly described cipher. With computer verifications we confirm the correctness of the analysis. Our attack is the first to use internal differentials for block ciphers, thus we adapt Daemen's attack on Even-Mansour construction to the case of internal differentials (instead of differentials), which allows us to recovery to full key. This work provides as well insights on alternative descriptions of general Zorro-type ciphers (incomplete non-linear layers), the importance of well chosen constants, and the advantages of Daemen's attack.

The design and analysis of lightweight block ciphers has been a very active research area over the last couple of years, with many innovative proposals trying to optimize different performance figures. However, since these block ciphers are dedicated to low-cost embedded devices, their implementation is also a typical target for side-channel adversaries. As preventing such attacks with countermeasures usually implies significant performance overheads, a natural open problem is to propose new algorithms for which physical security is considered as an optimization criteria, hence allowing better performances again. We tackle this problem by studying how much we can tweak standard block ciphers such as the AES Rijndael in order to allow efficient masking (that is one of the most frequently considered solutions to improve security against side-channel attacks). For this purpose, we first investigate alternative S-boxes and round structures. We show that both approaches can be used separately in order to limit the total number of non-linear operations in the block cipher, hence allowing more efficient masking. We then combine these ideas into a concrete instance of block cipher called Zorro. We further provide a detailed security analysis of this new cipher taking its design specificities into account, leading us to exploit innovative techniques borrowed from hash function cryptanalysis (that are sometimes of independent interest). Eventually, we conclude the paper by evaluating the efficiency of masked Zorro implementations in an 8-bit microcontroller, and exhibit their interesting performance figures.

This paper introduces a dedicated authenticated encryption algorithm AEGIS; AEGIS allows for the protection of associated data which makes it very suitable for protecting network packets. AEGIS-128L uses eight AES round functions to process a 32-byte message block (one step). AEGIS-128 uses five AES round functions to process a 16-byte message block (one step); AES-256 uses six AES round functions. The security analysis shows that these algorithms offer a high level of security. On the Intel Sandy Bridge Core i5 processor, the speed of AEGIS-128L, AEGIS-128 and AEGIS-256 is around 0.48, 0.66 and 0.7 clock cycles/byte (cpb) for 4096-byte messages, respectively. This is substantially faster than the AES CCM, GCM and OCB modes.

We examine the security of the 64-bit lightweight block cipher PRESENT-80 against related-key differential attacks. With a computer search we are able to prove that no related-key differential characteristic exists with probability higher than $2^{-64}$ for the full-round PRESENT-80. To overcome the exponential (in the state and key sizes) computational complexity we use truncated differences, however as the key schedule is not nibble oriented, we switch to actual differences and apply early abort techniques to prune the tree-based search. With a new method called extended split approach we are able to make the whole search feasible and we implement and run it in real time. Our approach targets the PRESENT-80 cipher however, with small modifications can be reused for other lightweight ciphers as well.

The MMB block cipher (Modular Multiplication-based Block cipher) is an iterative block cipher designed by Daemen, Govaerts, and Vandewalle in 1993 as an improvement of the PES and IPES ciphers. In this paper we present several new related-key differential characteristics of MMB. These characteristics can be used to form several related-key boomerangs to attack the full MMB. Using 2^{20} adaptive chosen plaintexts and ciphertexts we recover all key bits in 2^{35} time for the full MMB. Our attack was experimentally verified, and it takes less than 15 minutes on a standard Intel i5 machine to recover the full MMB key. After showing this practical attack on the full key of the full MMB, we present partial attacks on extended versions of MMB with up to 9 rounds (which is three more rounds than in the full MMB). We recover 62 out of the 128-bit key in time of 2^{29.2} for 7-round MMB, using 2^{20} adaptive chosen plaintexts and ciphertexts encrypted under 4 related-keys, and time of 2^{29} for 8-round MMB using 2^{20} adaptive chosen plaintexts and ciphertexts, encrypted under 6 related-keys. We show how an adversary can recover 31 out of the 128-bit key for the 9-round MMB in time of 2^{27.8} using 2^{19} adaptive chosen plaintexts and ciphertexts, encrypted under only 2 related-keys. We also show how the time complexity of all attacks can be reduced by partially precomputing the difference distribution table of MMB's components.

TCS\_SHA-3 is a family of four cryptographic hash functions that are covered by an US patent (US 2009/0262925). The digest sizes are 224, 256, 384 and 512 bits. The hash functions use bijective functions in place of the standard, compression functions. In this paper we describe first and second preimage attacks on the full hash functions. The second preimage attack requires negligible time and the first preimage attack requires $O(2^{36})$ time. In addition to these attacks, we also present a negligible-time second preimage attack on a strengthened variant of the TCS\_SHA-3. All the attacks have negligible memory requirements.

The authentication encryption (AE) scheme based on the duplex construction can no be paralellized at the algorithmic level. To be competitive with some block cipher based modes like OCB (Offset CodeBook) or GCM (Galois Counter Mode), a scheme should allow parallel processing. In this note we show how parallel AE can be realized within the framework provided by the duplex construction. The first variant, pointed by the duplex designers, is a tree-like structure. Then we simplify the scheme replacing the final node by the bitwise xor operation and show that such a scheme has the same security level.

Time memory tradeoff algorithms are tools for inverting one-way functions, and they are often used to recover passwords from unsalted password hashes. There are many publicly known tradeoff algorithms, and the rainbow tradeoff is widely believed to be the best algorithm. This work provides an accurate complexity analysis of the non-perfect table version of the fuzzy rainbow tradeoff algorithm, which has not yet received much attention. It is shown that, when the pre-computation cost and the online efficiency are both taken into consideration, the non-perfect fuzzy rainbow tradeoff is preferable to the original rainbow tradeoff in many situations.

This paper presents differential attacks of round-reduced versions of Simon with up to 18/32, 19/36, 25/44, 35/54, and 46/72 rounds for the 32-, 48-, 64-, 96-, and 128-bit versions, respectively. Furthermore, we consider in brief related-key rectangle, impossible-differential, and also linear attacks. While all our attacks are completely academic, they demonstrate the drawback of the aggressive optimizations in Simon.

Block ciphers use Substitution boxes (S-boxes) to create confusion into the cryptosystems. Functions used as S-boxes should have low differential uniformity, high nonlinearity and algebraic degree larger than 3 (preferably strictly larger). They should be fastly computable; from this viewpoint, it is better when they are in even number of variables. In addition, the functions should be bijections in a Substitution-Permutation Network. Almost perfect nonlinear (APN) functions have the lowest differential uniformity 2 and the existence of APN bijections over $\F_{2^n}$ for even $n\ge 8$ is a big open problem. In the present paper, we focus on constructing differentially 4-uniform bijections suitable for designing S-boxes for block ciphers. Based on the idea of permuting the inverse function, we design a construction providing a large number of differentially 4-uniform bijections with maximum algebraic degree and high nonlinearity. For every even $n\ge 12$, we mathematically prove that the functions in a subclass of the constructed class are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. This is the first mathematical proof that an infinite class of differentially 4-uniform bijections is CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. We also get a general lower bound on the nonlinearity of our functions, which can be very high in some cases, and obtain three improved lower bounds on the nonlinearity for three special subcases of functions which are extremely large.

In this paper, we describe new techniques in meet-in-the-middle attacks. Our basic technique is called a \emph{linear key sieve} since it exploits as filtering conditions linear dependencies between key bits that are guessed from both sides of the attack. This should be contrasted with related previous attacks, which only exploited a \emph{linear state sieve} (i.e., linear dependencies between state bits that are computed from both sides of the attack). We apply these techniques to the lightweight block cipher LED-64, and improve some of the best known attacks on step-reduced variants of this cipher in all attack models. As a first application of the linear key sieve, we describe a chosen plaintext attack on 2-step LED-64, which reduces the time complexity of the best previously published attack on this variant from $2^{56}$ to $2^{48}$. Then, we present the first attack on 2-step LED-64 in the \emph{known plaintext model}. In this attack, we show for the first time that the splice-and-cut technique (which inherently requires chosen messages) can also be applied in the known plaintext model, and we use the linear key sieve in order to obtain an attack with the same time complexity as our chosen plaintext attack. Finally, we describe a related-key attack on 3-step LED-64 which improves the best previously published attack (presented at Asiacrypt 2012) in all the complexity parameters of time/data/memory from $2^{60}$ to $2^{49}$. As our first two single-key attacks, the related-key attack is also based on the linear key sieve, but it uses additional techniques in differential meet-in-the-middle which are interesting in their own right.

The block cipher used in the Chinese Wireless LAN Standard (WAPI), SMS4, was recently renamed as SM4, and became the block cipher standard issued by the Chinese government. This paper improves the previous linear cryptanalysis of SMS4 by giving the first 19-round one-dimensional approximations. The 19-round approximations hold with bias 2^{−62.27}; we use one of them to leverage a linear attack on 23-round SMS4. Our attack improves the previous 23-round attacks by reducing the time complexity. Furthermore, the data complexity of our attack is further improved by the multidimensional linear approach.

We present a new general-purpose obfuscator for all polynomial-size circuits. The obfuscator uses graded encoding schemes, a generalization of multilinear maps. We prove that the obfuscator exposes no more information than the program's black-box functionality, and achieves {\em virtual black-box security}, in the generic graded encoded scheme model. This proof is under the Bounded Speedup Hypothesis (BSH, a plausible worst-case complexity-theoretic assumption related to the Exponential Time Hypothesis), in addition to standard cryptographic assumptions. We also show that the weaker notion of {\em indistinguishability obfuscation} can be achieved without BSH. Very recently, Garg et al.~(FOCS 2013) used graded encoding schemes to present a candidate obfuscator for indistinguishability obfuscation. They posed the problem of constructing a provably secure indistinguishability obfuscator in the generic graded encoding scheme model. Our obfuscator resolves this problem. Indeed, under BSH it achieves the stronger notion of virtual black box security, which is our focus in this work. Our construction is different from that of Garg et al., but is inspired by it, in particular by their use of permutation branching programs. We obtain our obfuscator by developing techniques used to obfuscate $d$-CNF formulas (ePrint 2013), and applying them to permutation branching programs. This yields an obfuscator for the complexity class $NC^1$. We then use homomorphic encryption to obtain an obfuscator for any polynomial-size circuit.

Three time memory tradeoff algorithms are compared in this paper. Specifically, the classical tradeoff algorithm by Hellman, the distinguished point tradeoff method, and the rainbow table method, in their non-perfect table versions, are treated. We show that, under parameters and assumptions that are typically considered in theoretic discussions of the tradeoff algorithms, Hellman and distinguished point tradeoffs perform very close to each other and that the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different. The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point truncations and index tables. Our comparison of algorithms takes the success probabilities and pre-computation efforts fully into account.

In this paper we introduce a model for studying meet-in-the-middle attacks on block ciphers, and a simple block cipher construction provably resistant to such attacks in this model. A side-result of this is a proper formalization for an unproven alternative to DESX proposed by Kilian and Rogaway; this construction can now be shown to be sound in our model. Meet-in-the-middle attacks exploit weaknesses in key schedule algorithms, and building constructions resistant to such attacks is an important issue for improving the security of block ciphers. Our construction is generic so that it can be used on top of any block cipher, and it does not require to increase the key-length. We use an exposure resilient function (or ERF) as a building block and we propose a concrete and efficient instantiation strategy based on compression functions.

In this article, we investigate the use of limited-birthday distinguishers to the context of hash functions. We first provide a proper understanding of the limited-birthday problem and demonstrate its soundness by using a new security notion Differential Target Collision Resistance (dTCR) that is related to the classical Target Collision Resistance (TCR) notion. We then solve an open problem and close the existing security gap by proving that the best known generic attack proposed at FSE 2010 for the limited-birthday problem is indeed the best possible method. Moreover, we show that almost all known collision attacks are in fact more than just a collision finding algorithm, since the difference mask for the message input is usually fixed. A direct and surprising corollary is that these collision attacks are interesting for cryptanalysis even when their complexity goes beyond the $2^{n/2}$ birthday bound and up to the $2^{n}$ preimage bound, and can be used to derive distinguishers using the limited-birthday problem. Interestingly, cryptanalysts can now search for collision attacks beyond the $2^{n/2}$ birthday bound. Finally, we describe a generic algorithm that turns a semi-free-start collision attack on a compression function (even if its complexity is beyond the birthday bound) into a distinguisher on the whole hash function when its internal state is not too wide. To the best of our knowledge, this is the first result that exploits classical semi-free-start collisions on the compression function to exhibit a weakness on the whole hash function. As an application of our findings, we provide distinguishers on reduced or full version of several hash functions, such as RIPEMD-128, SHA-256, Whirlpool, etc.

In this article we propose a new cryptanalysis method for double-branch hash functions that we apply on the standard RIPEMD-128, greatly improving over know results. Namely, we were able to build a very good differential path by placing one non-linear differential part in each computation branch of the RIPEMD-128 compression function, but not necessarily in the early steps. In order to handle the low differential probability induced by the non-linear part located in later steps, we propose a new method for using the freedom degrees, by attacking each branch separately and then merging them with free message blocks. Overall, we present the first collision attack on the full RIPEMD-128 compression function as well as the first distinguisher on the full RIPEMD-128 hash function. Experiments on reduced number of rounds were conducted, confirming our reasoning and complexity analysis. Our results show that 16 years old RIPEMD-128, one of the last unbroken primitives belonging to the MD-SHA family, might not be as secure as originally thought.

We propose a new type of meet-in-the-middle attack that splits the cryptographic primitive in parallel to the execution of the operations. The result of the division are two primitives that have smaller input sizes and thus require lower attack complexities. However, the division is not completely independent and the sub-primitives depend (output of one is the input for the other) mutually on a certain number of bits. When the number of such bits is relatively small, we show a technique based on three classical meet-in-the-middle attacks that can recover the secret key of the cipher faster than an exhaustive search. We apply our findings to the lightweight block cipher Klein and show attacks on 10/11/13 rounds of Klein-64/-80/-96. Our approach requires only one or two pairs of known plaintexts and always recovers the secret key.

In this article, we propose an improved cryptanalysis of the double-branch hash function standard RIPEMD-160. Using a carefully designed non-linear path search tool, we study the potential differential paths that can be constructed from a difference in a single message word and show that some of these message words can lead to very good differential path candidates. Leveraging the recent freedom degree utilization technique from Landelle and Peyrin to merge two branch instances, we eventually manage to obtain a semi-free-start collision attack for 42 steps of the RIPEMD-160 compression function, while the previously best know result reached 36 steps. In addition, we also describe a 36-step semi-free-start collision attack which starts from the first step.

We examine the widespread SimonsVoss digital locking system 3060 G2 that relies on an undisclosed, proprietary protocol to mutually authenticate transponders and locks. For assessing the security of the system, several tasks have to be performed: By decapsulating the used microcontrollers with acid and circumventing their read-out protection with UV-C light, the complete program code and data contained in door lock and transponder are extracted. As a second major step, the multi-pass challenge-response protocol and corresponding cryptographic primitives are recovered via low-level reverse-engineering. The primitives turn out to be based on DES in combination with a proprietary construction. Our analysis pinpoints various security vulnerabilities that enable practical key-recovery attacks. We present two different approaches for unauthorizedly gaining access to installations. Firstly, an attacker having physical access to a door lock can extract a master key, allowing to mimic transponders, in altogether 30 minutes. A second, purely logical attack exploits an implementation flaw in the protocol and works solely via the wireless interface. As the only prerequisite, a valid ID of a transponder needs to be known (or guessed). After executing a few (partial) protocol runs in the vicinity of a door lock, and some seconds of computation, an adversary obtains all of the transponder’s access rights.

In 2009 and 2011, Toorani and Falahati introduced two variants of the classical Hill Cipher, together with protocols for the exchange of encrypted messages. The designers claim that the new systems overcome the weaknesses of the original Hill Cipher, and are resistant to any ciphertext-only, known-plaintext, chosen-plaintext, or chosen-ciphertext attack. However, we describe a chosen-plaintext attack that easily breaks both Toorani-Falahati Hill Ciphers, and we present computational results that confirm the effectiveness of our attack.

Cryptanalytic time memory tradeoff is a tool for inverting one-way functions, and the rainbow table method, the best-known tradeoff algorithm, is widely used to recover passwords. Even though extensive research has been performed on the rainbow tradeoff, the algorithm actually used in practice differs from the well-studied original algorithm. This work provides a full analysis of the rainbow tradeoff algorithm that is used in practice. Unlike existing works on the rainbow tradeoff, the analysis is done in the external memory model, so that the practically important issue of table loading time is taken into account. As a result, we are able to provide tradeoff parameters that optimize the wall-clock time.

Related-key and chosen IV attacks are well known cryptanalytic tools in cryptanalysis of stream ciphers. Though the related-key model is considered to be much more unrealistic scenario than the chosen IV model we show that under certain circumstances the attack assumptions may become equivalent. We show that the key differentiation method induces a generic attack in a related-key model whose time complexity in the on-line phase is less than the exhaustive key search. The case of formal equivalency between the two scenarios arises when so-called {\em differentiable polynomials} with respect to some subset of key variables are a part of the state bit expressions (from which the output keystream bits are built). Then the differentiation over a key cube has the same effect as the differentiation over the corresponding IV cube, so that a generic nature of a related-key model is transferred into a more practical chosen IV model. The existence of such polynomials is confirmed for the reduced round stream cipher TRIVIUM up to some 710 rounds and an algorithm for their detection is proposed. The key differentiation method induces a time/related-key trade-off (TRKTO) attack which (assuming the existence of differentiable polynomials) can be run in a chosen IV model. The resulting trade-off curve of our TMDTO attack is given by $T^2M^2D^2=(KV)^2$ ($V$ denoting the IV space), which is a significant improvement over the currently best known trade-off $TM^2D^2=(KV)^2$ \cite{IVDunkel08}.

GOST R is the hash function standard of Russia. This paper presents some cryptanalytic results on GOST R. Using the rebound attack technique, we achieve collision attacks on the reduced round compression function. Result on up to 9.5 rounds is proposed, the time complexity is 2^{176} and the memory requirement is 2^{128} bytes. Based on the 9.5-round collision result, a limited birthday distinguisher is presented. More over, a method to construct k collisions on 512-bit version of GOST R is given which show the weakness of the structure used in GOST R. To the best of our knowledge, these are the first results on GOST R.

In FSE 2010, Nandi proved a sufficient condition of pseudo random function (PRF) for affine domain extensions (ADE), wide class of block cipher based domain extensions. This sufficient condition is satisfied by all known blockcipher based ADE constructions, however, it is not a characterization of PRF. In this paper we completely characterize the ADE and show that {\em message authentication code (MAC) and weakly collision resistant (WCR) are indeed equivalent to PRF}. Note that a PRF is trivially a MAC and WCR, however, the converse need not be true in general. So our result suggests that it would be sufficient to ensure resisting against weakly collision attack or the forging attack to construct a pseudo random function ADE. Unlike FSE 2010 paper, here we consider the {\em forced collisions of inputs of underlying blockciphers by incorporating the final outputs of a domain extension queried by an adaptive adversary}. This is the main reason why we are able to obtain a characterization of PRF. Our approach is a more general and hence might have other theoretical interest.

This paper studies key-recovery attacks on AES-192 and PRINCE under single-key model by methodology of meet-in-the-middle attack. A new technique named key-dependent sieve is proposed to further reduce the memory complexity of Demirci et al.'s attack at EUROCRYPT 2013, which helps us to achieve 9-round attack on AES-192 by using a 5-round distinguisher; the data, time and memory complexities are 2^{121} chosen plaintexts, 2^{185} encryptions and 2^{185} 128- bit memories, respectively. The new technique is also applied to attack block cipher PRINCE. Instead of 6-round results in the previous cryptanalysis, we rst present attacks on 8-round (out of 12) PRINCEcore and PRINCE with about 2^{53} and 2^{60} encryptions, respectively. Furthermore, we construct an interesting 7-round distinguisher and extend the attack to 9-round PRINCE; the attack needs about 2^{57} chosen plaintexts, 2^{64} encryptions and 2^{57.3} 64-bit memories.

The Even-Mansour (EM) encryption scheme received a lot of attention in the last couple of years due to its exceptional simplicity and tight security proofs. The original $1$-round construction was naturally generalized into $r$-round structures with one key, two alternating keys, and completely independent keys. In this paper we describe the first key recovery attack on the one-key 3-round version of EM which is asymptotically faster than exhaustive search (in the sense that its running time is $o(2^n)$ rather than $O(2^n)$ for an $n$-bit key). We then use the new cryptanalytic techniques in order to improve the best known attacks on several concrete EM-like schemes. In the case of LED-128, the best previously known attack could only be applied to 6 of its 12 steps. In this paper we develop a new attack which increases the number of attacked steps to 8, is slightly faster than the previous attack on 6 steps, and uses about a thousand times less data. Finally, we describe the first attack on the full $\mbox{AES}^{2}$ (which uses two complete AES-128 encryptions and three independent $128$-bit keys, and looks exceptionally strong) which is about 7 times faster than a standard meet-in-the-middle attack, thus violating its security claim.

RC4 has remained the most popular software stream cipher since the last two decades. In parallel to cryptanalytic attempts, researchers have come up with many variants of RC4, some targeted to more security, some towards more throughput. We observe that the design of RC4 has been changed a lot in most of the variants. Since the RC4 structure is quite secure if the cipher is used with proper precautions, an arbitrary change in the design may lead to potential vulnerabilities, such as the distinguishing attack (Tsunoo et al., 2007) on the word-oriented variant GGHN (Gong et al., 2005). Some variants keep the RC4 structure (Maitra et al., 2008), but is byte-oriented and hence is an overkill for modern wide-word processors. In this paper, we try to combine the best of both the worlds. We keep the basic RC4 structure which guarantees reasonable security (if properly used) and we combine 4 RC4 states tacitly to design a high throughput stream cipher called {\em Quad-RC4} that produces $32$-bit output at every round. The storage requirement for the internal state is only $1024$ bits. In terms of speed, this cipher performs much faster than normal RC4 and is comparable with HC-128, the fastest software stream cipher amongst the eSTREAM finalists. We also discuss the issue of generalizing the structure of Quad-RC4 to higher word-width variants.

In this paper we use differential cryptanalysis to attack the winner of the SHA-3 competition, namely Keccak hash function. Despite more than 6 years of intensive cryptanalysis there have been known only two preimage attacks which reach 3 (or slightly more) rounds. Our 3-round preimage attack improves the complexity of those two existing attacks and it is obtained with a different technique. We also show the partial preimage attack on the 4-round Keccak, exploiting two properties of the linear step of the Keccak-f permutation.

Combinatorial key predistribution schemes can provide a practical solution to the problem of distributing symmetric keys to the nodes of a wireless sensor network. Such schemes often inherently suit networks in which the number of nodes belongs to some restricted set of values (such as powers of primes). In a recent paper, Bose, Dey and Mukerjee have suggested that this might pose a problem, since discarding keyrings to suit a smaller network might adversely affect the properties of the scheme. In this paper we explore this issue, with specific reference to classes of key predistribution schemes based on transversal designs. We demonstrate through experiments that, for a wide range of parameters, randomly removing keyrings in fact has a negligible and largely predictable effect on the parameters of the scheme. In order to facilitate these computations, we provide a new, efficient, generally applicable approach to computing important properties of combinatorial key predistribution schemes. We also show that the structure of a resolvable transversal design can be exploited to give a deterministic method of removing keyrings to adjust the network size, in such a way that the properties of the resulting scheme are easy to analyse. We show that these schemes have the same asymptotic properties as the transversal design schemes on which they are based, and that for most parameter choices their behaviour is very similar.

We show how to securely obfuscate a new class of functions: {\em conjunctions of $NC0_d$ circuits}. These are functions of the form $C(x) = \bigwedge_{i=1}^m C_i(x)$, where each $C_i$ is a boolean $NC0_d$ circuit, whose output bit is only a function of $d = O(1)$ bits of the input $x$. For example, $d$-CNFs, where each clause is a disjunction of at most $d$ variables, are in this class. Given such a function, we produce an obfuscated program that preserves the input-output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron, Lepoint and Tibouchi (CRYPTO 2013). We prove that the construction is a secure obfuscation in a generic multilinear group model, under the black-box definition of Barak et al.\ (CRYPTO 2001). Security is based on a new {\em worst-case} hardness assumption about exponential hardness of the NP-complete problem 3-SAT, the {\em Bounded Speedup Hypothesis}. One of the new techniques we introduce is a method for enforcing input consistency, which we call {\em randomizing sub-assignments}. We hope that this technique can find further application in constructing secure obfuscators. The family of functions we obfuscate is considerably richer than previous works that consider black-box obfuscation. As one application, we show how to achieve {\em obfuscated functional point testing}: namely, to construct a circuit that checks whether $f(x)=y$, where $f$ is an arbitrary ``public'' polynomial-time computable function, but $y$ is a ``secret'' point that is hidden in the obfuscation.

This document describes the symmetric encryption algorithm called Puzzle. It is free and open. The objective of this paper is to get an opinion about its security from the cryptology community. It is separated in two parts, a technical description of the algorithm and its cryptanalysis. The algorithm has some interesting properties : The block size is variable and unknown from an attacker. The size of the key has no limit and is unknown from an attacker. The key size does not affect the algorithm speed (using a 256 bit key is the same as using a 1024 bit key). The algorithm is much faster than the average cryptographic function. Experimental test showed 600 Mo/s - 4 cycles/byte on an Intel Core 2 Duo P8600 2.40GHz and 1,2 Go/s - 2 cycles/byte on an Intel i5-3210M 2.50GHz. Both CPU had only 2 cores.

Recently, the U.S National Security Agency has published the specifications of two families of lightweight block ciphers, SIMON and SPECK, in ePrint report 2013/404. The ciphers are developed with optimization towards both hardware and software in mind. While the specification paper discusses design requirements and performance of the presented lightweight ciphers thoroughly, no security assessment is given. This paper is a move towards filling that cryptanalysis gap for the SIMON family of ciphers. We present a series of observations on the presented construction that, in some cases, yield attacks, while in other cases may provide basis of further analysis by the cryptographic community. Specifically, we obtain attacks using classical- as well as truncated differentials. In the former case, we show how the smallest version of SIMON, Simon32/64, exhibits a strong differential effect.

In this article, we propose a new improvement of the rebound techniques, used for cryptanalyzing AES-like permutations during the past years. Our improvement, that allows to reduce the complexity of the attacks, increases the probability of the outbound part by considering a new type of differential paths. Moreover, we propose a new type of distinguisher, the multiple limited-birthday problem, based on the limited-birthday one, but where differences on the input and on the output might have randomized positions. We also discuss the generic complexity for solving this problem and provide a lower bound of it as well as we propose an efficient and generic algorithm for solving it. Our advances lead to improved distinguishing or collision results for many AES-based functions such as AES, ECHO, Grøstl, LED, PHOTON and Whirlpool.

The incidence matrix between a set of monomials and a set of vectors in $\F_2$ has a great importance in the study of coding theory, cryptography, linear algebra, combinatorics. The rank of these matrices are very useful while computing algebraic immunity($\ai$) of Boolean functions in cryptography literature~\cite{MPC04,DGM04}. Moreover, these matrices are very sparse and well structured. Thus, for aesthetic reason finding the rank of these matrices is also very interesting in mathematics. In this paper, we have reviewed the existing algorithms with added techniques to speed up the algorithms and have proposed some new efficient algorithms for the computation of the rank of incidence matrix and solving the system of equations where the co-efficient matrix is an incidence matrix. Permuting the rows and columns of the incidence matrix with respect to an ordering, the incidence matrix can be converted to a lower block triangular matrix, which makes the computation in quadratic time complexity and linear space complexity. Same technique is used to check and computing low degree annihilators of an $n$-variable Boolean functions in faster time complexity than the usual algorithms. Moreover, same technique is also exploited on the Dalai-Maitra algorithm in~\cite{DM06} for faster computation. On the basis of experiments, we conjecture that the $\ai$ of $n$-variable inverse S-box is $\lfloor\sqrt{n}\rfloor + \lceil\frac{n}{\lfloor\sqrt{n}\rfloor}\rceil-2$. We have also shown the skepticism on the existing fastest algorithm in~\cite{ACGKMR06} to find $\ai$ and lowest degree annihilators of a Boolean function.

In this paper, we present a framework for biclique cryptanalysis of block ciphers with an extremely low data complexity. To that end, we enjoy a new representation of biclique attack. Then an algorithm for choosing two dierential characteristics is also presented to simultaneously minimize the data complexity and control the computational complexity. Then we characterize those block ciphers that are vulnerable to this technique and among them, we apply this attack on lightweight block ciphers Piccolo-80, Piccolo-128 and HIGHT. The data complexities of these attacks are considerably less than the existing results. For full-round Piccolo-80 and 128, the data complexity of the attacks are only 16 plaintext-ciphertext pairs and for full-round HIGHT our attack requires 256 pairs. In all attacks the computational complexity remains the same as the previous ones or even it is slightly improved.

We construct a searchable encryption scheme that enables keyword search over data encrypted with {\em different} keys. The scheme is practical and was designed to be included in a new system for protecting data confidentiality in client-server applications against attacks on the server.

After a series of works on RC4 cryptanalysis in last few years (published in flagship cryptology conferences and journals), the most significant (and also very recent) attack on the cipher has been the discovery of vulnerabilities in the SSL/TLS protocol, by AlFardan, Bernstein, Paterson, Poettering and Schuldt. They ran extensive computations to identify significant short-term single-byte keystream biases of RC4, and utilized that knowledge in the attack. The biases identified by AlFardan et al. consist of earlier known biases of RC4, as well as some newly discovered ones. In this paper, we attempt at proving the new, unproved or partially proved biases amongst the above-mentioned ones. The theoretical proofs of these biases not only assert a scientific justification, but also discover intricate patterns and operations of the cipher associated with these biases. For example, while attempting the proof of a bias of the first output byte towards 129, we observe that this bias occurs prominently only for certain lengths of the secret key of RC4. In addition, our findings reveal that this bias may be related to the old and unsolved problem of ``anomalies'' in the distribution of the state array after the Key Scheduling Algorithm. In this connection, we prove the anomaly in $S_0[128] = 127$, a problem open for more than a decade. Other than proving the new biases, we also complete the proof for the extended keylength dependent biases in RC4, a problem attempted and partially solved by Isobe, Ohigashi, Watanabe and Morii in FSE 2013. Our new proofs and observations in this paper, along with the connection to the older results, provide a comprehensive view on the state-of-the-art literature in RC4 cryptanalysis.

We show that the class of polynomial-size branching programs can be obfuscated according to a virtual black-box notion akin to that of Barak et al. [Crypto 01], in an idealized black-box group model over pseudo-free groups. This class is known to lie between $NC^1$ and $P$ and includes most interesting cryptographic algorithms. The construction is rather simple and is based on Kilian's randomization technique for Barrington's branching programs. The black-box group model over pseudo-free groups is a strong idealization. In particular, in a pseudo-free group, the group operation can be efficiently performed, while finding surprising relations between group elements is intractable. %inverses or linking between different representations of the same group element are infeasible. A black-box representation of the group provides an ideal interface which permits prescribed group operations, and nothing else. Still, the algebraic structure and security requirements appear natural and potentially realizable. They are also unrelated to the specific function to be obfuscated. Our modeling should be compared with the recent breakthrough obfuscation scheme of Garg et al. [FOCS 2013]: While the high level structure is similar, some important details differ. It should be stressed however that, unlike Garg et al., we do not provide a candidate concrete instantiation of our abstract structure.

The series of published works, related to Differential Fault Attack (DFA) against the Grain family, require (i) quite a large number (hundreds) of faults (around $n \ln n$, where $n = 80$ for Grain v1 and $n = 128$ for Grain-128, Grain-128a) and also (ii) several assumptions on location and timing of the fault injected. In this paper we present a significantly improved scenario from the adversarial point of view for DFA against the Grain family of stream ciphers. Our model is the most realistic one so far as it considers that the cipher to be re-keyed a very few times and fault can be injected at any random location and at any random point of time, i.e., no precise control is needed over the location and timing of fault injections. We construct equations based on the algebraic description of the cipher by introducing new variables so that the degrees of the equations do not increase. In line of algebraic cryptanalysis, we accumulate such equations based on the fault-free and faulty key-stream bits and solve them using the SAT Solver Cryptominisat-2.9.5 installed with SAGE 5.7. In a few minutes we can recover the state of Grain v1, Grain-128 and Grain-128a with as little as 10, 4 and 10 faults respectively (and may be improved further with more computational efforts).

Proving bounds on the expected differential probability (EDP) of a characteristic over all keys has been a popular technique of arguing security for both block ciphers and hash functions. In fact, to a large extent, it was the clear formulation and elegant deployment of this very principle that helped Rijndael win the AES competition. Moreover, most SHA-3 finalists have come with explicit upper bounds on the EDP of a characteristic as a major part of their design rationale. However, despite the pervasiveness of this design approach, there is no understanding of what such bounds actually mean for the security of a primitive once a key is fixed --- an essential security question in practice. In this paper, we aim to bridge this fundamental gap. Our main result is a quantitative connection between a bound on the EDP of differential characteristics and the highest number of input pairs that actually satisfy a characteristic for a fixed key. This is particularly important for the design of permutation-based hash functions such as sponge functions, where the EDP value itself is not informative for the absence of rekeying. We apply our theoretical result to revisit the security arguments of some prominent recent block ciphers and hash functions. For most of those, we have good news: a characteristic is followed by a small number of pairs only. For Keccak, though, currently much more rounds would be needed for our technique to guarantee any reasonable maximum number of pairs. Thus, our work --- for the first time --- sheds light on the fixed-key differential behaviour of block ciphers in general and substitution-permutation networks in particular which has been a long-standing fundamental problem in symmetric-key cryptography.