Roughly speaking, an encryption scheme is said to be non-malleable, if no adversary can modify a ciphertext so that the resulting message is meaningfully related to the original message. We compare this notion of security to secrecy and authenticity, and provide a complete characterization of their relative strengths. In particular, we show that information-theoretic perfect non-malleability is equivalent to perfect secrecy of two different messages. This implies that for $n$-bit messages a shared secret key of length roughly $2n$ is necessary to achieve non-malleability, which meets the previously known upper bound. We define approximate non-malleability by relaxing the security conditions and only requiring non-malleability to hold with high probability (over the choice of secret key), and show that any authentication scheme implies approximate non-malleability. Since authentication is possible with a shared secret key of length roughly $\log n$, the same applies to approximate non-malleability.

This paper shows preimage attacks against reduced SHA-1 up to 57 steps. The best previous attack has been presented at CRYPTO 2009 and was for 48 steps finding a two-block preimage with incorrect padding at the cost of 2159.3 evaluations of the compression function. For the same variant our attacks find a one-block preimage at 2150.6 and a correctly padded two-block preimage at 2151.1 evaluations of the compression function. The improved results come out of a differential view on the meet-in-the-middle technique originally developed by Aoki and Sasaki. The new framework closely relates meet-in-the-middle attacks to differential cryptanalysis which turns out to be particularly useful for hash functions with linear message expansion and weak diffusion properties.

In this paper, we study the security proofs of GCM (Galois/Counter Mode of Operation). We first point out that a lemma, which is related to the upper bound on the probability of a counter collision, is invalid. Both the original privacy and authenticity proofs by the designers are based on the lemma. We further show that the observation can be translated into a distinguishing attack that invalidates the main part of the privacy proof. It turns out that the original security proofs of GCM contain a flaw, and hence the claimed security bounds are not justified. A very natural question is then whether the proofs can be repaired. We give an affirmative answer to the question by presenting new security bounds, both for privacy and authenticity. As a result, although the security bounds are larger than what were previously claimed, GCM maintains its provable security. We also show that, when the nonce length is restricted to 96 bits, GCM has better security bounds than a general case of variable length nonces.

TWINE is a lightweight block cipher proposed at ECRYPT Workshop on Lightweight Cryptography 2011, Belgium. The cipher consists of 36 rounds and has two versions TWINE-80 and TWINE-128 supporting key lengths of 80 and 128 bits, respectively. The block length of the two versions is 64-bit. In this paper, we present the first single-key attacks on the both versions of the cipher. In these attacks, we use the recently developed biclique technique. The complexities of the attacks on TWINE-80 and TWINE-128 are $2^{79.10}$ and $2^{126.82}$ respectively and the data requirement for the two attacks is $2^{60}$.

In 2007, the U.S. National Institute of Standards and Technology (NIST) announced a public contest aiming at the selection of a new standard for a cryptographic hash function. In this paper, the security margin of five SHA-3 finalists is evaluated with an assumption that attacks launched on finalists should be practically verified. A method of attacks applied is called logical cryptanalysis where the original task is expressed as a SATisfiability problem instance. A new toolkit is used to simplify the most arduous stages of this type of cryptanalysis and helps to mount the attacks in a uniform way. In the context of SAT-based attacks, it has been shown that all the finalists have substantially bigger security margin than the current standards SHA-256 and SHA-1. Two other metrics, software performance and hardware efficiency are combined with security results to provide a more comprehensive picture of the SHA-3 finalists.

We present a framework that unifies several standard differential techniques. This unified view allows us to consider many, potentially all, output differences for a given input difference and to combine the information derived from them in an optimal way. We then propose a new attack that implicitly mounts several standard, truncated, impossible, improbable and possible future variants of differential attacks in parallel and hence allows to significantly improve upon known differential attacks using the same input difference. To demonstrate the viability of our techniques, we apply them to KATAN-32. In particular, our attack allows us to break 115 rounds of KATAN-32, which is 37 rounds more than previous work. For this, our attack exploits the non-uniformity of the difference distribution after 91 rounds which is 20 rounds more than the previously best known differential characteristic. Since our results still cover less than 1/2 of the cipher, they further strengthen our confidence in KATAN-32's resistance against differential attacks.

Piccolo is a 64-bit block cipher suitable for the constrained environments such as wireless sensor network environments. In this paper, we propose differential fault analysis on Piccolo. Based on a random byte fault model, our attack can recover the secret key of Piccolo-80 by using an exhaustive search of 2^{24} and six random byte fault injections on average. It can be simulated on a general PC within a few seconds. In the case of Piccolo-128, we require an exhaustive search of 2^{40} and eight random byte fault injections on average. This attack can be simulated on a general PC within one day. These results are the first known side-channel attack results on them.

In this paper, by modifying a subclass of bent functions in $\mathcal P S_{ap}$, we construct another subclass of bent functions in $\mathcal P S^+$ with maximum algebraic degree. We demonstrate that the algebraic immunity of the constructed functions is maximum. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1), pp. 1-14, 2011) which has been proved recently by Cohen and Flori (http://eprint.iacr.org/ 2011/400.pdf). Finally, we identify a class of $\cD_0$ type bent functions constructed by modifying Dillon functions whose lower bound on second-order nonlinearity is very high.

Differential Fault Analysis (DFA) finds the key of a block cipher using differential information between correct and faulty ciphertexts obtained by inducing faults during the computation of ciphertexts. Among many ciphers AES has been the main target of DFA due to its popularity. DFA of AES has also been diversied into several directions: reducing the required number of faults, applying it to multi-byte fault models, extending to AES-192 and AES-256, or exploiting faults induced at an earlier round. This paper deals with the first three directions together, especially giving weight to reducing the required number of faults. Many previous works show that the required numbers of faults are different although the same fault model is used. This comes from lack of a general method of constructing and solving differential fault equations. Therefore we first present how to generate differential fault equations systematically and reduce the number of candidates of the key with them, which leads us to find the minimum number of faults. Then we extend to multi-byte fault models and AES-192/256.

In the recent years, several hash constructions have been introduced that aim at achieving enhanced security margins by strengthening the Merkle-Damgård mode. However, their security analysis have been conducted independently and using a variety of proof methodologies. This paper unifies these results by proposing a unique indifferentiability proof that considers a broadened form of the general compression function introduced by Stam at FSE09. This general definition enables us to capture in a realistic model most of the features of the mode of operation ({\em e.g.}, message encoding, blank rounds, message insertion,...) within the pre-processing and post-processing functions. Furthermore, it relies on an inner primitive which can be instantiated either by an ideal block cipher, or by an ideal permutation. Then, most existing hash functions can be seen as the Chop-MD construction applied to some compression function which fits the broadened Stam model. Our result then gives the tightest known indifferentiability bounds for several general modes of operations, including Chop-MD, Haifa or sponges. Moreover, we show that it applies in a quite automatic way, by providing the security bounds for 7 out of the 14 second round SHA-3 candidates, which are in some cases improved over previously known ones.

In this paper, we consider the spectra of Boolean functions with respect to the action of unitary transforms obtained by taking tensor products of the Hadamard, denoted by $H$, and the nega--Hadamard, denoted by $N$, kernels. The set of all such transforms is denoted by $\{H, N\}^n$. A Boolean function is said to be bent$_4$ if its spectrum with respect to at least one unitary transform in $\{H, N\}^n$ is flat. We prove that the maximum possible algebraic degree of a bent$_4$ function on $n$ variables is $\lceil \frac{n}{2} \rceil$, and hence solve an open problem posed by Riera and Parker [cf. IEEE-IT: 52(2)(2006) 4142--4159]. We obtain a relationship between bent and bent$_4$ functions which is a generalization of the relationship between bent and negabent Boolean functions proved by Parker and Pott [cf. LNCS: 4893(2007) 9--23].

Certain block cipher confidentiality modes are susceptible to an adaptive chosen-ciphertext attack against the underlying format of the plaintext. When the application decrypts altered ciphertext and attempts to process the manipulated plaintext, it may disclose information about intermediate values resulting in an oracle. In this paper we describe how to recognize and exploit such an oracle to decrypt ciphertext and control the decryption to result in arbitrary plaintext. We also discuss ways to mitigate and remedy the issue.

``Lapin'' is a new RFID authentication protocol proposed at FSE 2012. ``Ring-LPN'' (Ring-Learning-Parity-with-Noise) is a new computational problem proposed in the same paper; there is a proof relating the security of Lapin to the difficulty of Ring-LPN. This paper presents an attack against Ring-LPN-512 and Lapin-512.The attack is not practical but nevertheless violates specific security claims in the FSE 2012 paper.

Order-preserving encryption (OPE) preserves the order of data in their ciphertexts and, hence, allows range search on the encrypted data without needing to decrypt them. Security analysis of OPE schemes is very important because OPE is not a perfect encryption algorithm (the ciphertexts leak the ordering information of the plaintexts). Most of the existing security analysis for the OPE schemes are informal: they are either based on author-defined attacks or experiments. The authors in \cite{Bol09} initiate the cryptographic study of the OPE scheme. They define the security notion POPF-CCA to qualify the security of OPE. In POPF-CCA, the ``ideal" OPE object is defined where the encryption function is uniformly randomly selected from all order-preserving functions (generally the ``ideal" OPE object is not computationally feasible), and a (constructed) ``real" OPE scheme is secure under POPF-CCA if it is computationally indistinguishable from the ideal object. In other words, although the ``ideal" OPE object is not computationally feasible, it is used as the security goal, and a (constructed) ``real" OPE scheme is secure if it is as secure as the ``ideal" OPE object. Such approach conceives the assumption (but not clearly stated and proved) that the ``ideal" OPE object is the most secure OPE. But the correctness of the assumption is an easily ignored problem. In this paper, we investigate the security of the OPE in more depth. We first give example to show that the ``ideal" OPE object may not always be the most secure OPE. It indicates that we need to use the ``ideal" encryption object more cautiously in the security analysis of OPE. Additionally we extend the concept of OPE to generalized OPE (GOPE). Unlike OPE, the ciphertexts of GOPE may not be numbers, but GOPE still enables the comparisons on the encrypted data without needing to decrypt them. We present two GOPEs in polynomial-sized and superpolynomial-sized domains that satisfy stronger notions of security than that of the ideal OPE object, respectively.

This paper proposes a new fault attack technique on the LED block cipher using a single fault injection by combining algebraic side-channel attack (ASCA) and differential fault attack (DFA). We name it as algebraic differential fault attack (ADFA). Firstly, a boolean equation set is constructed for LED using algebraic techniques. Then, the fault differences of the S-Box inputs in the last round of LED are deduced by DFA and represented using algebraic equations by the multiple deductions-based ASCA (MDASCA) technique proposed in COSADE 2012. Finally, the key is recovered by solving the equation set with the CryptoMiniSat solver. We show that, as to ADFA on LED under the single nibble-based fault model, the 64-bit key can be recovered within one minute on a common PC with a success rate of 79\%, which is more efficient than previous work. We modify the CryptoMiniSat solver to count and output multiple solutions for the key, and conduct ADFA to calculate the reduced key search space for DFA. The key search space of LED is reduced to $2^6 \sim 2^{17}$, which is different from previous work. We also successfully extend ADFA on LED to other fault models using a single fault injection, such as byte based fault model and nibble based diagonal fault model, where traditional DFAs are difficult to work. The results show that ADFA is an efficient and generic fault analysis technique which significantly improves DFA.

This paper reevaluates the security of GF-NLFSR, a new kind of generalized unbalanced Feistel network structure that was proposed at ACISP 2009. We show that GF-NLFSR itself reveals a very slow diffusion rate, which could lead to several distinguishing attacks. For GF-NLFSR containing $n$ sub-blocks, we find an $n^2$-round integral distinguisher by algebraic methods and further use this integral to construct an $(n^2+n-2)$-round impossible differential distinguisher. Compared with the original $(3n-1)$-round integral and $(2n-1)$-round impossible differential, ours are significantly better. Another contribution of this paper is to introduce a kind of non-surjective attack by analyzing a variant structure of GF-NLFSR, whose provable security against differential and linear cryptanalysis can also be provided. The advantage of the proposed non-surjective attack is that traditional non-surjective attack is only applicable to Feistel ciphers with non-surjective (non-uniform) round functions, while ours could be applied to block ciphers with bijective ones. Moreover, its data complexity is $\mathcal{O}(l)$ with $l$ the block length.

The nonlinear feedback shift registers (NLFSR) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of the linear feedback shift registers (LFSR). In general, it is not known how to construct NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. We used the implementation of NLFSRs in Field Programmable Gate Arrays (FPGA) to perform a corresponding search. We also investigated local statistical properties of the binary sequences ganerated by NLFSRs of order 25 and 27.

Despite the fact that we evidently have very good block ciphers at hand today, some fundamental questions on their security are still unsolved. One such fundamental problem is to precisely assess the security of a given block cipher with respect to linear cryptanalysis. In by far most of the cases we have to make (clearly wrong) assumptions, e.g., assume independent round-keys. Besides being unsatisfactory from a scientific perspective, the lack of fundamental understanding might have an impact on the performance of the ciphers we use. As we do not understand the security sufficiently enough, we often tend to embed a security margin -- from an efficiency perspective nothing else than wasted performance. The aim of this paper is to stimulate research on these foundations of block ciphers. We do this by presenting three examples of ciphers that behave differently to what is normally assumed. Thus, on the one hand these examples serve as counter examples to common beliefs and on the other hand serve as a guideline for future work.

Stream cipher ZUC plays a crucial role in the next generation of mobile communication as it has already been included by the 3GPP LTE-Advanced, which is a candidate standard for the 4G network. Through a long-time evaluation program, ZUC algorithm is thought to be robust enough to resist many existing cryptanalyses, but not for DPA, one of the most powerful threat of SCAs(Side Channel Analysis).Up to the present, almost all the work on DPA is for block ciphers, such as DES and AES, a very few work has been done on stream ciphers, such as ZUC algorithm, for particular reasons that would be illustrated in the later section. In this paper, we generally study the security of unprotected ZUC hardware implementation against DPA. Our theoretical analysis and experimental results show that ZUC algorithm is potentially vulnerable to this kind of attack. Furthermore, kinds of common countermeasures are discussed when we try to apply them to ZUC hardware implementations, both the security and tradeoffs are considered. The experiments are given in the last section to verify our conclusions, which would undoubtedly provide some guidance to the corresponding designers.

This paper is a short summary of a real world AES key extraction performed on a military grade FPGA marketed as 'virtually unbreakable' and 'highly secure'. We demonstrated that it is possible to extract the AES key from the Actel/Microsemi ProASIC3 chip in a time of 0.01 seconds using a new side-channel analysis technique called Pipeline Emission Analysis (PEA). This new technique does not introduce a new form of side-channel attacks (SCA), it introduces a substantially improved method of waveform analysis over conventional attack technology. It could be used to improve upon the speed at which all SCA can be performed, on any device and especially against devices previously thought to be unfeasible to break because of the time and equipment cost. Possessing the AES key for the ProASIC3 would allow an attacker to decrypt the bitstream or authenticate himself as a legitimate user and extract the bitstream from the device where no read back facility exists. This means the device is wide open to intellectual property theft, fraud and reverse engineering of the design to allow the introduction of a backdoor or Trojan. We show that with a very low cost hardware setup made with parts obtained from a local electronics distributor you can improve upon existing SCA up to a factor of x1,000,000 in time and at a fraction of the cost of existing SCA equipment.

We consider the family of 2n-to-n-bit compression functions that are solely based on at most three permutation executions and on XOR-operators, and analyze its collision and preimage security. Despite their elegance and simplicity, these designs are not covered by the results of Rogaway and Steinberger (CRYPTO 2008). By defining a carefully chosen equivalence relation on this family of compression functions, we obtain the following results. In the setting where the three permutations pi_1, pi_2, pi_3 are selected independently and uniformly at random, there exist at most four equivalence classes that achieve optimal 2^{n/2} collision resistance. Under a certain extremal graph theory based conjecture, these classes are proven optimally collision secure. Additionally, three of these classes allow for finding preimages in 2^{n/2} queries, and only one achieves optimal 2^{2n/3} preimage resistance (with respect to the bounds of Rogaway and Steinberger, EUROCRYPT 2008). Consequently, a compression function is optimally collision and preimage secure if and only if it is equivalent to F(x_1,x_2) = x_1 xor pi_1(x_1) xor pi_2(x_2) xor pi_3(x_1 xor x_2 xor pi_1(x_1)). If the compression function makes three calls to the same random permutation, there does not exist any compression function attaining 2^{n/2} collision resistance: for any scheme, collisions can be found with 2^{2n/5} queries. This result casts some doubt over the existence of any (larger) secure permutation-based compression function built only on XOR-operators and (multiple invocations of) a single permutation.

In their seminal work on authentication, Wegman and Carter propose that to authenticate multiple messages, it is sufficient to reuse the same hash function as long as each tag is encrypted with a one-time pad. They argue that because the one-time pad is perfectly hiding, the hash function used remains completely unknown to the adversary. Since their proof is not composable, we revisit it using a universally composable framework. It turns out that the above argument is insufficient: information about the hash function is in fact leaked in every round to the adversary, and after a bounded finite amount of rounds it is completely known. We show however that this leak is very small, and Wegman and Carter's protocol is still $\epsilon$-secure, if $\epsilon$-almost strongly universal hash functions are used. This implies that the secret key corresponding to the choice of hash function can be recycled for any task without any additional error than this $\epsilon$. We illustrate this by applying it to quantum key distribution (QKD): if the same hash function is recycled to authenticate the classical communication in every round of a QKD protocol, and used $\ell$ times per round, the total error after $r$ rounds is upper bounded by $r(\ell\epsilon+\epsilon')$, where $\epsilon'$ is the error of one round of QKD given an authentic channel.

In this paper we propose a new differential fault analysis (DFA) on CLEFIA of 128-bit key. The proposed attack requires to induce byte faults at the fourteenth round of CLEFIA encryption. The attack uses only two pairs of fault-free and faulty ciphertexts and uniquely determines the 128-bit secret key. The attacker does not need to know the plaintext. The most efficient reported fault attack on CLEFIA, needs fault induction at the fifteenth round of encryption and can be performed with two pairs of fault-free and faulty ciphertexts and brute-force search of around 20 bits. Therefore, the proposed attack can evade the countermeasures against the existing DFAs which only protect the last four rounds of encryption. Extensive simulation results have been presented to validate the proposed attack. The simulation results show that the attack can retrieve the 128-bit secret key in around one minute of execution time. To the best of authors’ knowledge the proposed attack is the most efficient attack in terms of both the input requirements as well as the complexity.

In this paper, we generalize some existing results on Boolean functions to the $q$-ary functions defined over $\BBZ_q$, where $q\geq 2$ is an integer, and obtain some new characterization of $q$-ary functions based on spectral analysis. We provide a relationship between Walsh-Hadamard spectra of two $p$-ary functions $f$ and $g$ (for $p$ a prime) and their derivative $D_{f, g}$. We provide a relationship between the Walsh-Hadamard spectra and the decompositions of any two $p$-ary functions. Further, we investigate a relationship between the Walsh-Hadamard spectra and the autocorrelation of any two $q$-ary functions.

Recently proposed algebraic attack has been shown to be very effective on several stream ciphers. In this paper, we have investigated the resistance of PingPong family of stream ciphers against algebraic attacks. This stream cipher was proposed in 2008 to enhance the security of the improved summation generator against the algebraic attack. In particular, we focus on the PingPong-128 stream cipher’s resistance against algebraic attack in this paper. In our analysis, it is found that an algebraic attack on PingPong family of stream ciphers require much more operations compare to the exhaustive key search on the internal state of the LFSRs. It will be shown that due to the irregular and mutual clock controlling in PingPong stream cipher the degree of the generated equation tends to grow up with each successive clock which in turn increases the overall complexity of an algebraic attack. Along with the PingPong 128 stream cipher the other instances of PingPong family stream ciphers are also investigated against the algebraic attack. Our analysis shows that, PingPong family stream ciphers are highly resistant against the algebraic attack due to their mutual and irregular clocking function.

The Square attack as a means of attacking reduced round variants of AES was described in the initial description of the Rijndael block cipher. This attack can be applied to AES, with a relatively small number of chosen plaintext-ciphertext pairs, reduced to less than six rounds in the case of AES-128 and seven rounds otherwise and several extensions to this attack have been described in the literature. In this paper we describe new variants of these attacks that have a smaller time complexity than those present in the literature. Specifically, we demonstrate that the quantity of chosen plaintext-ciphertext pairs can be halved producing the same reduction in the time complexity. We also demonstrate that the time complexity can be halved again for attacks applied to AES-128 and reduced by a smaller factor for attacks applied to AES-192. This is achieved by eliminating hypotheses on-the-fly when bytes in consecutive subkeys are related because of the key schedule.

WG-7 is a stream cipher based on WG Stream Cipher and has been designed by Y. Luo, Q. Chai, G. Gong, and X. Lai in 2010. This cipher is designed for low cost and lightweight applications (RFID tags and mobile phones, for instance). This paper addresses cryptographic weaknesses of WG-7 Stream Cipher. We show that the key stream generated by WG-7 can be distinguished from a random sequence after knowing $ 2^{13.5}$ keystream bits and with a negligible error probability. Also, we investigate the security of WG-7 against algebraic attacks. An algebraic key recovery attack on this cipher is proposed. The attack allows to recover both the internal state and the secret key with the time complexity about $2^{27}$.

The shrinking generator is a well-known key stream generator composed of two LFSR’s, LFSRx and LFSRc, where LFSRx is clock-controlled according to the regularly clocked LFSRc. In this paper we investigate the minimum required length of the output sequence for successful reconstruction of the LFSRx initial state in an optimal probabilistic divide and conquer correlation attack. We extract an exact expression for the joint probability of the prefix of length m of the output sequence of LFSRx and prefix of length n of the output sequence of the generator. Then we use computer simulation to compare our probability measure and two other probability measures, previousely proposed in [5] and [3], in the sense of minimum required output length. Our simulation results show that our measure reduces the required output length.

In this paper we investigate the invariant property of PRINTcipher first discovered by Leander et al. in their CRYPTO 2011 paper. We provide a thorough study and show that there exist 64 families of weak keys for PRINTcipher--48 and many more for PRINTcipher--96. Moreover, we show that searching the weak key space may be substantially sped up by splitting the search into two consecutive steps. We show that for many classes of weak keys key recovery can be done in a matter of minutes in the chosen/known plaintext scenario. In fact, at least $2^{45}$ weak keys can be recovered in less than 20 minutes per key on a single PC using only a few chosen and one known plaintext(s). We provide detailed treatment of the methods and put them in a more general context that opens new interesting directions of research for PRESENT-like ciphers.

In this article, we study the security of the IDEA block cipher when it is used in various simple-length or double-length hashing modes. Even though this cipher is still considered as secure, we show that one should avoid its use as internal primitive for block cipher based hashing. In particular, we are able to generate instantaneously free-start collisions for most modes, and even semi-free-start collisions, pseudo-preimages or hash collisions in practical complexity. This work shows a practical example of the gap that exists between secret-key and known or chosen-key security for block ciphers. Moreover, we also settle the 20-year-old standing open question concerning the security of the Abreast-DM and Tandem-DM double-length compression functions, originally invented to be instantiated with IDEA. Our attacks have been verified experimentally and work even for strengthened versions of IDEA with any number of rounds.

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on $n$ bits, an algorithm of complexity $2^{n-1}$ is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.

In this paper, we point out a new weakness of the AES key schedule by revisiting an old observation exploited by many known attacks. We also discover a major cause for this weakness is that the column-by-column word-wise property in the key schedule matches nicely with the MixColumns operation in the cipher's diffusion layer. Then we propose a new key schedule by minor modification to increase the security level for AES. First, it reduces the number of rounds that some attacks are effective, such as SQUARE attacks and meet-in-the-middle attacks; Second, it is interesting that our new key schedule also protects AES from the most devastating related-key differential type attacks, which work against AES-192 and AES-256 with the full number of rounds. Compared with the original key schedule, ours just does a transposition on the output matrix of the subkeys. Compared with other proposed modifications of AES key schedule, our modification adds no non-linear operations, no need to complicate the diffusion method, or complicate the iteration process of generating subkeys. Finally, our results suggest that the route of diffusion propagation should get more attention in the design of key schedules.

The hash function Skein is one of the five finalists of the NIST SHA-3 competition;it is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with complexities 2^{104.5} and 2^{454} respectively. Examples of the distinguishers on 28-round and 31-round are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2^{181}, 2^{305} and 2^{424}. Because Laurent et al. [14] pointed out that the previous boomerang distinguishers for Threefish-512 are in fact not compatible, our attacks are the first valid boomerang attacks for the final round Skein-512.

One of the hardest problems in computer science is the problem of gate-eficient implementation. Such optimizations are particularly important in industrial hardware implementations of standard cryptographic algorithms. In this paper we focus on optimizing some small circuits such as S-boxes in cryptographic algorithms. We consider the notion of Multiplicative Complexity studied in 2008 by Boyar and Peralta and applied to find interesting optimizations for the S-box of the AES cipher. We applied this methodology to produce a compact implementation of several ciphers. In this short paper we report our results on PRESENT and GOST, two block ciphers known for their exceptionally low hardware cost. This kind of representation seems to be very promising in implementations aiming at preventing side channel attacks on cryptographic chips such as DPA. More importantly, we postulate that this kind of minimality is also an important and interesting tool in cryptanalysis.

In the last few years, the need to design new cryptographic hash functions has led to the intense study of when desired hash multi-properties are preserved or assured under compositions and domain extensions. In this area, it is important to identify the exact notions and provide often complex proofs of the resulting properties. Getting this analysis right (as part of provable security studies) is, in fact, analogous to cryptanalysis. We note that it is important and quite subtle to get indeed the ``right'' notions and properties, and ``right'' proofs in this relatively young area. Specifically, the security notion we deal with is ``adaptive preimage resistance'' (apr) which was introduced by Lee and Park as an extension of ``preimage resistance'' (pr). In Eurocrypt 2010, in turn, Lee and Steinberger already used the apr security notion to prove ``preimage awareness'' and ``indifferentiable security'' of their new double-piped mode of operation. They claimed that if $H^P$ is collision-resistant (cr) and apr, then $F(M)=\mathcal{R}(H^P(M))$ is indifferentiable from a variable output length (VIL) random oracle $\mathcal{F}$, where $H^P$ is a function based on an ideal primitive $P$ and $\mathcal{R}$ is a fixed input length (FIL) random oracle. However, there are some limitations in their claim, because they considered only indifferentiability security notion in the information-theoretic adversarial model, not in the computation-theoretic adversarial model. As we show in the current work, the above statement is \textit{not} correct in the computation-theoretic adversarial model. First in our studies, we give a counterexample to the above. Secondly, we describe \textit{a new requirement} on $H^P$ (called ``admissibility'') so that the above statement is correct even in the computation-theoretic adversarial model. Thirdly, we show that apr is, in fact, not a strengthened notion of preimage resistance. Fourthly, we explain the relation between preimage awareness and cr+apr+(our new requirement) in the computation-theoretic adversarial model. Finally, we show that a polynomial-based mode of operation \cite{LeSt10} satisfies our new requirement; namely, the polynomial-based mode of operation with fixed-input-length random oracles is indifferentiable from a variable-input-length random oracle in the computation-theoretic adversarial model.

There are four somewhat classical double length block cipher based compression functions known: MDC-2, MDC-4, Abreast-DM, and Tandem-DM. They all have been developed over 20 years ago. In recent years, cryptographic research has put a focus on block cipher based hashing and found collision security results for three of them (MDC-2, Abreast-DM, Tandem-DM). In this paper, we add MDC-4, which is part of the IBM CLiC cryptographic module (FIPS 140-2 Security Policy for IBM CrytoLite in C, October 2003), to that list by showing that - 'instantiated' using an ideal block cipher with 128 bit key/plaintext/ciphertext size - no adversary asking less than $2^{74.76}$ queries can find a collision with probability greater than $1/2$. This is the first result on the collision security of the hash function MDC-4. The compression function MDC-4 is created by interconnecting two MDC-2 compression functions but only hashing one message block with them instead of two. The developers aim for MDC-4 was to offer a higher security margin, when compared to MEDC-2, but still being fast enough for practical purposes. The MDC-2 collision security proof of Steinberger (EUROCRYPT 2007) cannot be directly applied to MDC-4 due to the structural differences. Although sharing many commonalities, our proof for MDC-4 is much shorter and we claim that our presentation is also easier to grasp.

We analyze the internal permutations of Keccak, one of the NIST SHA-3 competition finalists, in regard to differential properties. By carefully studying the elements composing those permutations, we are able to derive most of the best known differential paths for up to 5 rounds. We use these differential paths in a rebound attack setting and adapt this powerful freedom degrees utilization in order to derive distinguishers for up to 8 rounds of the internal permutations of the submitted version of Keccak. The complexity of the 8 round distinguisher is $2^{491.47}$. Our results have been implemented and verified experimentally on a small version of Keccak. This is currently the best known differential attack against the internal permutations of Keccak.

TEA, XTEA and HIGHT are lightweight block ciphers with 64-bit block sizes and 128-bit keys. The round functions of the three ciphers are based on the simple operations XOR, modular addition and shift/rotation. TEA and XTEA are Feistel ciphers with 64 rounds designed by Needham and Wheeler, where XTEA is a successor of TEA, which was proposed by the same authors as an enhanced version of TEA. Whilst HIGHT, which is designed by Hong et al., is a generalized Feistel cipher with 32 rounds and eight 8-bit words in each round. On the one hand, all these ciphers are simple and easy to implement; on the other hand, the diffusion is slow, which allow us to find some impossible properties. This paper proposes a method to identify the impossible differentials for TEA and XTEA by using the diffusion property of these block ciphers, where the impossible differential comes from one bit contradiction. By means of the method, 14-round impossible differential of XTEA and 13-round impossible differential of TEA are derived, which results in improved impossible differential attacks on 23-round XTEA and 17-round TEA, respectively. These attacks significantly improve the previous 11-round impossible differential attack on TEA and 14-round impossible differential attack on XTEA given by Moon et al. from FSE 2002. For HIGHT, we improve the 26-round impossible differential attack proposed by Özen et al.; an impossible differential attack on 27-round HIGHT that is slightly faster that the exhaustive search is also given. The attacks on TEA, XTEA and HIGHT are also the best attacks in terms of time complexity.

The homomorphic encryption problem has been an open one for three decades. Recently, Gentry has proposed a full solution. Subsequent works have made improvements on it. However, the time complexities of these algorithms are still too high for practical use. For example, Gentry’s homomorphic encryption scheme takes more than 900 seconds to add two 32 bit numbers, and more than 67000 seconds to multiply them. In this paper, we develop a non-circuit based symmetric-key homomorphic encryption scheme. It is proven that the security of our encryption scheme is equivalent to the large integer factorization problem, and it can withstand an attack with up to m ln⁡poly⁡(λ) chosen plaintexts for any predetermined m, where λ is the security parameter. Multiplication, encryption, and decryption are almost linear in mλ, and addition is linear in mλ. Performance analyses show that our algorithm runs multiplication in 108 milliseconds and addition in a tenth of a millisecond for λ=1024 and m=16. We further consider practical multiple-user data-centric applications. Existing homomorphic encryption schemes only consider one master key. To allow multiple users to retrieve data from a server, all users need to have the same key. In this paper, we propose to transform the master encryption key into different user keys and develop a protocol to support correct and secure communication between the users and the server using different user keys. In order to prevent collusion between some user and the server to derive the master key, one or more key agents can be added to mediate the interaction.

Prefix-preserving encryption (PPE) is an important type of encryption scheme, having a wide range of applications, such as IP addresses anonymization, prefix-matching search, and rang search. There are two issues in PPE schemes, security proof and single key requirement. Existing security proofs for PPE only reduce the security of a real PPE scheme to that of the ideal PPE object by showing their computational indistinguishability \cite{Ama07,Xu02}. Such security proof is incomplete since the security of the ideal encryption object is unknown. Also, existing prefix-preserving encryption schemes only consider a single encryption key, which is infeasible for a practical system with multiple users (Implying that all users should have the single encryption key in order to encrypt or decrypt confidential data). In this paper we develop a novel mechanism to analyze the security of the ideal PPE object. We follow the modern cryptographic approach and create a new security notion IND-PCPA. Then, we show that such weakened security notion is necessary and the ideal PPE object is secure under IND-PCPA. We also design a new, security-enhanced PPE protocol to support its use in multi-user systems, where no single entity in the system knows the PPE key. The protocol secret shares and distributes the PPE key to a group of key agents and let them ``distributedly encrypt'' critical data. We develop a novel distributed PPE algorithm and the corresponding request and response protocols. Experimental results show that the protocol is feasible in practical systems.

Distance-bounding protocols address man-in-the-middle (MITM) in authentication protocols: by measuring response times, verifiers ensure that the responses are not purely relayed. Durholz et al. [13] formalize the following attacks against distance-bounding protocols: (1) mafia fraud, where adversaries must authenticate to the verifier in the presence of honest provers; (2) terrorist fraud, where malicious provers help the adversary (in offline phases) to authenticate (however, the adversary shouldn't authenticate on its own); (3) distance fraud, where a malicious prover must convince the verifier that it is closer to it than in reality; (4) impersonation security, where the prover must authenticate to the verifier in the rounds where response times are not measured. A scenario where distance-bounding can be successfully deployed is RFID authentication, where the provers and RFID tags, and the verifiers are RFID readers. Security models and most distance-bounding schemes designed so far are static, i.e. the used secret key is never updated. The scenario considered by [13] features a single reader and a single tag. However, a crucial topic in RFID authentication is privacy, as formalized by Vaudenay [32]. Adversaries against privacy can corrupt tags and learn the secret keys; in this scenario, key updates ensure better privacy. In this paper we extend distance-bounding security to include key updates, and show a compiler that preserves mafia, distance, and impersonation security, and turns a narrow-weak private distance-bounding protocol into a narrow-destructive private distance-bounding protocol as in [32]. We discuss why it is much harder to attain terrorist fraud resistance, for both stateless and stateful scenarios. We optimize our compiler for cases where (i) the underlying distance-bounding protocol does not have reader authentication; (ii) impersonation security is achieved (by using a pseudorandom function) before the distance-bounding phase; or (iii) the prover ends by sending a MAC of the transcript. We also use our compiler on the enhanced construction in [13].

We prove that Tandem-DM, one of the two ``classical'' schemes for turning a blockcipher of $2n$-bit key into a double block length hash function, has birthday-type collision resistance in the ideal cipher model. A collision resistance analysis for Tandem-DM achieving a similar birthday-type bound was already proposed by Fleischmann, Gorski and Lucks at FSE 2009. As we detail, however, the latter analysis is wrong, thus leaving the collision resistance of Tandem-DM as an open problem until now.

For a class of generalized Feistel block ciphers, an explicit recurrent formula for the minimum numbers of linearly active $S$-boxes of any round $r$ is presented.

We consider the question of efficiently extending the key length of block ciphers. To date, the approach providing highest security is triple encryption (used e.g. in Triple-DES), which was proved to have roughly k + min{n/2, k/2} bits of security when instantiated with ideal block ciphers with key length k and block length n, at the cost of three block-cipher calls per message block. This paper presents a new practical key-length extension scheme exhibiting k + n/2 bits of security – hence improving upon the security of triple encryption – solely at the cost of two block cipher calls and a key of length k + n. We also provide matching generic attacks showing the optimality of the security level achieved by our approach with respect to a general class of two-query constructions.

Finding the key of symmetric cipher takes computing common zero of polynomials, which define ideal and corresponding variety, usually considered over algebraically closed field. The solution is the point of the variety over prime field; it is defined by a sum of the polynomial ideal and the field ideal that defines prime field. Some authors use partitioning of this sum and reducing syzygies of polynomial ideal modulo field ideal. We generalize this method and consider polynomial ideal as a sum of two ideals, one of them is given by short polynomials, and add this ideal to the field ideal. Syzygies are reduced modulo this sum of ideals. Accuracy of definition of the substitution ideal by short polynomials can be increased using affine equivalence of ideals. This method decreases degree and length of syzygies and reduces complexity of Groebner basis computation.

In 2007, the US National Institute for Standards and Technology (NIST) announced a call for the design of a new cryptographic hash algorithm in response to vulnerabilities like differential attacks identified in existing hash functions, such as MD5 and SHA-1. NIST received many submissions, 51 of which got accepted to the first round. 14 candidates were left in the second round, out of which 5 candidates have been recently chosen for the final round. An important criterion in the selection process is the SHA-3 hash function security. We identify two important classes of security arguments for the new designs: (1) the possible reductions of the hash function security to the security of its underlying building blocks, and (2) arguments against differential attack on building blocks. In this paper, we compare the state of the art provable security reductions for the second round candidates, and review arguments and bounds against classes of differential attacks. We discuss all the SHA-3 candidates at a high functional level, analyze and summarize the security reduction results and bounds against differential attacks. Additionally, we generalize the well-known proof of collision resistance preservation, such that all SHA-3 candidates with a suffix-free padding are covered.

In this paper, we investigate the relation between the autocorrelation of a cubic Boolean function $f\in \cB_n$ at $a \in \BBF_{2^n}$ and the kernel of the bilinear form associated with $D_{a}f$, the derivative of $f$ at $a$. Further, we apply this technique to obtain the tight upper bounds of absolute indicator and sum-of-squares indicator for avalanche characteristics of various classes of highly nonlinear non-bent cubic Boolean functions.

A profiling adversary is an adversary which aims to classify messages into pre-defined profiles and thus gain useful information regarding the sender or receiver of such messages. Usual chosen-plaintext secure encryption schemes are capable of securing information from profilers, but these schemes provide more security than required for this purpose. In this paper we study the requirements for an encryption algorithm to be secure only against profilers and finally give a precise notion of security for such schemes. We also present a full protocol for secure (against profiling adversaries) communication, which neither requires a key exchange nor a public key infrastructure. Our protocol guarantees security against non-human profilers and is constructed using CAPTCHAs and secret sharing schemes.

Linear Feedback Shift Registers (LFSRs) are the main building block of many classical stream ciphers; however due to their inherent linearity, most of the LFSR-based designs do not offer the desired security levels. In the last decade, using Nonlinear Feedback Shift Registers(NFSRs) in stream ciphers became very popular. However, the theory of NFSRs is not well-understood, and there is no efficient method that constructs a cryptographically strong feedback function with maximum period and also, given a feedback function it is hard to predict the period. In this paper, we study the maximum-length NFSRs, focusing on the nonlinearity of their feedback functions. First, we provide some upper bounds on the nonlinearity of the maximum-length feedback functions, and then we study the feedback functions having nonlinearity 2 in detail. We also show some techniques to improve the nonlinearity of a given feedback function using cross-joining.

In this paper, we describe versatile and powerful algorithms for searching guess-and-determine and meet-in-the-middle attacks on some byte-oriented symmetric primitives. To demonstrate the strengh of these tools, we show that they allow to automatically discover new attacks on round-reduced AES with very low data complexity, and to find improved attacks on the AES-based MACs Alpha-MAC and Pelican-MAC, and also on the AES-based stream cipher LEX. Finally, the tools can be used in the context of fault attacks. These algorithms exploit the algebraically simple byte-oriented structure of the AES. When the attacks found by the tool are practical, they have been implemented and validated experimentally.

The MISTY1 block cipher has a 64-bit block length, a 128-bit user key and a recommended number of 8 rounds. It is a Japanese CRYPTREC-recommended e-government cipher, an European NESSIE selected cipher, and an ISO international standard. Despite of considerable cryptanalytic efforts during the past fifteen years, there has been no published cryptanalytic attack on the full MISTY1 cipher algorithm. In this paper, we present related-key differential and related-key amplified boomerang attacks on the full MISTY1 under certain weak key assumptions: We describe $2^{103.57}$ weak keys and a related-key differential attack on the full MISTY1 with a data complexity of $2^{61}$ chosen ciphertexts and a time complexity of $2^{87.94}$ encryptions; and we also describe $2^{92}$ weak keys and a related-key amplified boomerang attack on the full MISTY1 with a data complexity of $2^{60.5}$ chosen plaintexts and a time complexity of $2^{80.18}$ encryptions. For the very first time, our results exhibit a cryptographic weakness in the full MISTY1 cipher (when used with the recommended 8 rounds), and show that the MISTY1 cipher is distinguishable from a random function and thus cannot be regarded to be an ideal cipher.

This paper is a modified version of own paper “Latin Dances Revisited: New Analytic Results of Salsa20 and ChaCha” presented in ICICS2011. In the original paper, there are incorrect data because of software bug in the experimental program. Therefore, we conducted with a correct program. Additionally, we modified the algorithm with a view to improvement of analysis precision.

Sponge functions were introduced by Bertoni et al. as an alternative to the classical Merkle-Damgaard design. Many hash function submissions to the SHA-3 competition launched by NIST in 2007, such as CubeHash, Fugue, Hamsi, JH, Keccak and Luffa, derive from the original sponge design, and security guarantees from some of these constructions are typically based on indifferentiability results. Although indifferentiability proofs for these designs often bear significant similarities, these have so far been obtained independently for each construction. In this work, we introduce the parazoa family of hash functions as a generalization of ``sponge-like'' functions. Similarly to the sponge design, the parazoa family consists of compression and extraction phases. The parazoa hash functions, however, extend the sponge construction by enabling the use of a wider class of compression and extraction functions that need to satisfy certain properties. More importantly, we prove that the parazoa functions satisfy the indifferentiability notion of Maurer et al. under the assumption that the underlying permutation is ideal. Not surprisingly, our indifferentiability result confirms the bound on the original sponge function, but it also carries over to a wider spectrum of hash functions and eliminates the need for a separate indifferentiability analysis.

We present the new concept of biclique as a tool for preimage attacks, which employs many powerful techniques from differential cryptanalysis of block ciphers and hash functions. The new tool has proved to be widely applicable by inspiring many authors to publish new results of the full versions of AES, KASUMI, IDEA, Square, and others. In this paper, we demonstrate how our concept results in the first cryptanalysis of the Skein hash function, and describe an attack on the SHA-2 hash function with more rounds than before.

This paper presents differential-based distinguishers against ISO standard hash functions RIPEMD-128 and RIPEMD-160. The compression functions of RIPEMD-128/-160 adopt the double-branch structure, which updates a chaining variable by computing two functions and merging their outputs. Due to the double size of the internal state and difficulties of controlling two functions simultaneously, only few results were published before. In this paper, second-order differential paths are constructed on reduced RIPEMD-128 and -160. This leads to a practical 4-sum attack on 47 steps (out of 64 steps) of RIPEMD-128 and 40 steps (out of 80 steps) of RIPEMD-160. We then extend the distinguished property from the 4-sum to other properties, which we call \emph{a 2-dimension sum} and \emph{a partial 2-dimension sum}. As a result, the practical partial 2-dimension sum is generated on 48 steps of RIPEMD-128 and 42 steps of RIPEMD-160, with a complexity of $2^{35}$ and $2^{36}$, respectively. Theoretically, $2$-dimension sums are generated faster than the exhaustive search up to 52 steps of RIPEMD-128 and 51 steps of RIPEMD-160, with a complexity of $2^{101}$ and $2^{158}$, respectively. The practical attacks are implemented, and examples of generated (partial) 2-dimension sums are presented.

In this paper, we construct generalized bent Boolean functions in $n+ 2$ variables from $4$ generalized Boolean functions in $n$ variables. We also show that the direct sum of two generalized bent Boolean functions is generalized bent. Finally, we identify a set of affine functions in which every function is generalized bent.

In this paper, we investigate security of the KATAN family of block ciphers against differential fault attacks. KATAN consists of three variants with 32, 48 and 64-bit block sizes, called KATAN32, KATAN48 and KATAN64, respectively. All three variants have the same key length of 80 bits. We assume a single-bit fault injection model where the adversary is supposed to be able to corrupt a single random bit of the internal state of the cipher and this fault induction process can be repeated (by resetting the cipher); i.e., the faults are transient rather than permanent. First, we show how to identify the exact position of faulty bits within the internal state by precomputing difference characteristics for each bit position at a given round and comparing these characteristics with ciphertext differences (XOR of faulty and non-faulty ciphertexts) during the online phase of the attack. Then, we determine suitable rounds for effective fault inductions by analyzing distributions of low-degree (mainly, linear and quadratic) polynomial equations obtainable using the cube and extended cube attack techniques. The complexity of our attack on KATAN32 is $2^{59}$ computations and about 115 fault injections. For KATAN48 and KATAN64, the attack requires $2^{55}$ computations (for both variants), while the required number of fault injections is 211 and 278, respectively.

The algebraic immunity of cryptographic Boolean functions is studied in this paper. Proper modifications of functions achieving maximum algebraic immunity are proved, in order to yield new functions of also maximum algebraic immunity. It is shown that the derived results apply to known classes of functions. Moreover, two new efficient algorithms to produce functions of guaranteed maximum algebraic immunity are developed, which further extend and generalize known constructions of functions with maximum algebraic immunity.

This paper considers---for the first time---the concept of key-alternating ciphers in a provable security setting. Key-alternating ciphers can be seen as a generalization of a construction proposed by Even and Mansour in 1991. This construction builds a block cipher $PX$ from an $n$-bit permutation $P$ and two $n$-bit keys $k_0$ and $k_1$, setting $PX_{k_0,k_1}(x)=k_1\oplus P(x\oplus k_0)$. Here we consider a (natural) extension of the Even-Mansour construction with $t$ permutations $P_1,\ldots,P_t$ and $t+1$ keys, $k_0,\ldots, k_t$. We demonstrate in a formal model that such a cipher is secure in the sense that an attacker needs to make at least $2^{2n/3}$ queries to the underlying permutations to be able to distinguish the construction from random. We argue further that the bound is tight for $t=2$ but there is a gap in the bounds for $t>2$, which is left as an open and interesting problem. Additionally, in terms of statistical attacks, we show that the distribution of Fourier coefficients for the cipher over all keys is close to ideal. Lastly, we define a practical instance of the construction with $t=2$ using AES referred to as AES$^2$. Any attack on AES$^2$ with complexity below $2^{85}$ will have to make use of AES with a fixed known key in a non-black box manner. However, we conjecture its security is $2^{128}$.

This paper deals with the security of MISTY structure with SPN round function. We study the lower bound of the number of active s-boxes for differential and linear characteristics of such block cipher construction. Previous result shows that the differential bound is consistent with the case of Feistel structure with SPN round function, yet the situation changes when considering the linear bound. We carefully revisit such issue, and prove that the same bound in fact could be obtained for linear characteristic. This result combined with the previous one thus demonstrates a similar practical secure level for both Feistel and MISTY structures. Besides, we also discuss the resistance of MISTY structure with SPN round function against other kinds of cryptanalytic approaches including the integral cryptanalysis and impossible differential cryptanalysis. We confirm the existence of 6-round integral distinguishers when the linear transformation of the round function employs a binary matrix (i.e., the element in the matrix is either 0 or 1), and briefly describe how to characterize 5/6/7-round impossible differentials through the matrix-based method.

A binary de Bruijn sequence of order $n$ is a cyclic sequence of period $2^n$, in which each $n$-bit pattern appears exactly once. These sequences are commonly used in random number generation and symmetric key cryptography particularly in stream cipher design, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as a special type of traveling salesman tours (TSP) and tries to find optimal solutions. We present some experimental results for $n\leq 14$.

The block cipher Rijndael has undergone more than ten years of extensive cryptanalysis since its submission as a candidate for the Advanced Encryption Standard (AES) in April 1998. To date, most of the publicly-known cryptanalytic results are based on reduced-round variants of the AES (respectively Rijndael) algorithm. Among the few exceptions that target the full AES are the Related-Key Cryptanalysis (RKC) introduced at ASIACRYPT 2009 and attacks exploiting Time-Memory-Key (TMK) trade-offs such as demonstrated at SAC 2005. However, all these attacks are generally considered infeasible in practice due to their high complexity (i.e. $2^{99.5}$ AES operations for RKC, $2^{80}$ for TMK). In this paper, we evaluate the cost of cryptanalytic attacks on the full AES when using special-purpose hardware in the form of multi-core AES processors that are designed in a similar way as modern Graphics Processing Units (GPUs) such as the NVIDIA GT200b. Using today's VLSI technology would allow for the implementation of a GPU-like processor reaching a throughput of up to $10^{12}$ AES operations per second. An organization able to spend one trillion US\$ for designing and building a supercomputer based on such processors could theoretically break the full AES in a time frame of as little as one year when using RKC, or in merely one month when performing a TMK attack. We also analyze different time-cost trade-offs and assess the implications of progress in VLSI technology under the assumption that Moore's law will continue to hold for the next ten years. These assessments raise some concerns about the long-term security of the AES.

SecureMemory (SM), CryptoMemory (CM) and CryptoRF (CR) are the Atmel chip families with wide applications in practice. They implement a proprietary stream cipher, which we call the Atmel cipher, to provide authenticity, confidentiality and integrity. At CCS'2010, it was shown that given $1$ keystream frame, the secret key in SM protected by the simple version of the cipher can be recovered in $2^{39.4}$ cipher ticks and if $2640$ keystream frames are available, the secret key in CM guarded by the more complex version of the cipher can be restored in $2^{58}$ cipher ticks. In this paper, we show much more efficient and practical attacks on both versions of the Atmel cipher. The idea is to dynamically reconstruct the internal state of the underlying register by exploiting the different diffusion speeds of the different cells. For SM, we can recover the secret key in $2^{29.8}$ cipher ticks given $1$ keystream frame; for CM, we can recover the secret key in $2^{50}$ cipher ticks with around $24$ frames. Practical implementation of the full attack confirms our results.

While generic attacks on classical Feistel schemes and unbalanced Feistel schemes have been studied a lot, generic attacks on several generalized Feistel schemes like type-1, type-2 and type-3 and Alternating Feistel schemes, as defined in~\cite{HR}, have not been systematically investigated. This is the aim of this paper. We give our best Known Plaintext Attacks and non-adaptive Chosen Plaintext Attacks on these schemes and we determine the maximum number of rounds that we can attack. It is interesting to have generic attacks since there are well known block cipher networks that use generalized Feistel schemes: CAST-256 (type-1), RC-6 (type-2), MARS (type-3) and BEAR/LION (alternating). Also, Type-1 and Type-2 Feistel schemes are respectively used in the construction of the hash functions $Lesamnta$ and $SHAvite-3_{512}$.

Camellia is one of the most worldwide used block ciphers, which has been selected as a standard by ISO/IEC. In this paper, we propose several new 7-round impossible differentials of Camellia with 2 $FL/FL^{-1}$ layers, which turn out to be the first 7-round impossible differentials with 2 $FL/FL^{-1}$ layers. Combined with some basic techniques including the early abort approach and the key schedule consideration, we achieve the impossible differential attacks on 11-round Camellia-128, 11-round Camellia-192, 12-round Camellia-192, and 14-round Camellia-256, and the time complexity are $2^{123.6}$, $2^{121.7}$, $2^{171.4}$ and $2^{238.2}$ respectively. As far as we know, these are the best results against the reduced-round variants of Camellia. Especially, we give the first attack on 11-round Camellia-128 reduced version with $FL/FL^{-1}$ layers.

$H^2$-MAC was proposed to increase efficiency over HMAC by omitting its outer key, and keep the advantage and security of HMAC at the same time. However, as pointed out by the designer, the security of $H^2$-MAC also depends on the secrecy of the intermediate value (the equivalent key) of the inner hashing. In this paper, we propose an efficient method to break $H^2$-MAC, by using a generalized birthday attack to recover the equivalent key, under the assumption that the underlying hash function is secure (weak collision resistance). We can successfully recover the equivalent key of $H^2$-MAC in about $2^{n/2}$ on-line MAC queries and $2^{n/2}$ off-line MAC computations with great probability. Moreover, we can improve the attack efficiency by reducing the on-line MAC queries, which can't be done concurrently. This attack shows that the security of $H^2$-MAC is totally dependent on the (weak) collision resistance of the underlying hash function, instead of the PRF-AX of the underlying compression function in the origin security proof of $H^2$-MAC.

In this paper, by means of the idea proposed in \cite{carlet4uniformpermu}, differentially 4-uniform permutations with the best known nonlinearity over $\mbf_{2^{2m}}$ can be constructed by using quadratic APN permutations over $\mbf_{2^{2m+1}}$. Special emphasis is given for the Gold functions. The algebraic degree of the constructions and their compositional inverse is also investigated. One of the constructions and its compositional inverse have both algebraic degree $m+1$ over $\mbf_2^{2m}$.

In modern cryptography, stream ciphers are most useful in applications where information needs to be encrypted/decrypted at high speed (e.g. high resolution streaming video data) or when low footprint (gates/memory) encryption is required. In the literature, there exist plenty of stream ciphers whose internal states are based on arrays and that they use modular additions to generate output streams. The abundance of array-based stream ciphers with modular additions can be attributed to the fact that, when implemented in software skillfully, they are able to produce outputs at a very high speed. The main contribution of this thesis is a unified analysis of stream ciphers based on arrays and modular addition. During the process, we detect cryptographic weaknesses in the designs of 9 widely known stream ciphers or pseudorandom bit generators (PRBGs). At first, we show some theoretical results on solving an important class of equations known as \emph{differential equations of addition} (DEA) that combine modular additions over two different algebraic groups such as GF(2) and GF($2^{32}$). The results include, \bite \item proof of the fact that the satisfiability of an arbitrary set of DEA is in the complexity class \pP,\item deriving all the solutions of an arbitrary set of DEA. \eite Next, we apply these results to attack a practical stream cipher named Helix (designed by Ferguson \emph{et al.}) with both chosen plaintexts and adaptive chosen plaintexts. In the second phase, the thesis closely scrutinizes a number of array-based stream ciphers (or PRBGs) in order to estimate their resistance against distinguishing attacks. We eventually discover, counter-intuitively, that the correlations between the array-indices and their associated array-elements, which apparently seem to be useful from the point of view of implementation purposes, can be exploited to mount distinguishing attacks on such type of ciphers if adequate precautions are not taken. In support of our theoretical findings, we point out distinguishing attacks on 8 practical array-based stream ciphers (or PRBGs), namely RC4 (designed by Rivest), RC4A (designed by Paul and Preneel), Py, Py6 (designed by Biham and Seberry), IA, ISAAC (designed by Jenkins Jr.), GGHN, NGG (by Gong \emph{et al.}); our attacks are based on the dependence of array-elements on array-indices. In all the cases we work under the assumption that the key-setup algorithms of the ciphers produce uniformly distributed internal states. We detect flaws in the mixing of bits in the keystream generation algorithms. Our analysis can be explained as the extension, development, adaptation and deeper characterization of the \ti{fortuitous states attacks} on the RC4 cipher by Fluhrer and McGrew in 2000.

The Keccak hash function is one of the five finalists in NIST's SHA-3 competition, and so far it showed remarkable resistance against practical collision finding attacks: After several years of cryptanalysis and a lot of effort, the largest number of Keccak rounds for which actual collisions were found was only 2. In this paper we develop improved collision finding techniques which enable us to double this number. More precisely, we can now find within a few minutes on a single PC actual collisions in standard Keccak-224 and Keccak-256, where the only modification is to reduce their number of rounds to 4. When we apply our techniques to 5-round Keccak, we can get in a few days excellent near collisions, where the Hamming distance is 5 in the case of Keccak-224 and 10 in the case of Keccak-256. Our new attack combines differential and algebraic techniques, and uses the fact that each round of Keccak is only a quadratic mapping in order to efficiently find pairs of messages which follow a high probability differential characteristic.

We analyze the security of the SHA-3 finalist BLAKE. The BLAKE hash function follows the HAIFA design methodology, and as such it achieves optimal preimage, second preimage and collision resistance, and is indifferentiable from a random oracle up to approximately 2^{n/2} assuming the underlying compression function is ideal. In our work we show, however, that the compression function employed by BLAKE exhibits a non-random behavior and is in fact differentiable in only 2^{n/4} queries. Our attack on the indifferentiability of the BLAKE compression function seriously undermines the security strength of BLAKE not only with respect to its overall indifferentiability, but also its collision and (second) preimage security in the ideal model. Our next contribution is the restoration of the security results for BLAKE in the ideal model by refining the level of modularity and assuming that BLAKE's underlying block cipher is an ideal cipher. We prove that BLAKE is optimally collision, second preimage, and preimage secure (up to a constant). We go on to show that BLAKE is still indifferentiable from a random oracle up to the old bound of 2^{n/2} queries, albeit under a weaker assumption: the ideality of its block cipher.

We show that the knowledge of any one of the two internal state arrays of HC-128 along with the knowledge of 2048 keystream words is sufficient to construct the other state array completely in $2^{42}$ time complexity. Though our analysis does not lead to any attack on HC-128, it reveals a structural insight into the cipher. In the process, we theoretically establish certain combinatorial properties of HC-128 keystream generation algorithm. We also suggest a modification to HC-128 that takes care of the recently known cryptanalytic results with little reduction in speed.

IDEA is a 64-bit block cipher with 128-bit keys which is widely used due to its inclusion in several cryptographic packages such as PGP. After its introduction by Lai and Massey in 1991, it was subjected to an extensive cryptanalytic effort, but so far the largest variant on which there are any published attacks contains only 6 of its 8.5-rounds. The first 6-round attack, described in the conference version of this paper in 2007, was extremely marginal: It required essentially the entire codebook, and saved only a factor of 2 compared to the time complexity of exhaustive search. In 2009, Sun and Lai reduced the data complexity of the 6-round attack from 2^{64} to 2^{49} chosen plaintexts and simultaneously reduced the time complexity from 2^{127} to 2^{112.1} encryptions. In this revised version of our paper, we combine a highly optimized meet-in-the-middle attack with a keyless version of the Biryukov-Demirci relation to obtain new key recovery attacks on reduced-round IDEA, which dramatically reduce their data complexities and increase the number of rounds to which they are applicable. In the case of 6-round IDEA, we need only two known plaintexts (the minimal number of 64-bit messages required to determine a 128-bit key) to perform full key recovery in 2^{123.4} time. By increasing the number of known plaintexts to sixteen, we can reduce the time complexity to 2^{111.9}, which is slightly faster than the Sun and Lai data-intensive attack. By increasing the number of plaintexts to about one thousand, we can now attack 6.5 rounds of IDEA, which could not be attacked by any previously published technique. By pushing our techniques to extremes, we can attack 7.5 rounds using 2^{63} plaintexts and 2^{114} time, and by using an optimized version of a distributive attack, we can reduce the time complexity of exhaustive search on the full 8.5-round IDEA to 2^{126.8} encryptions using only 16 plaintexts.

In this paper, the RC4 Key Scheduling Algorithm (KSA) is theoretically studied to reveal non-uniformity in the expected number of times each value of the permutation is touched by the indices $i, j$. Based on our analysis and the results available in literature regarding the existing weaknesses of RC4, few additional layers over the RC4 KSA and RC4 Pseudo-Random Generation Algorithm (PRGA) are proposed. Analysis of the modified cipher (we call it RC4$^+$) shows that this new strategy avoids existing weaknesses of RC4.

\texttt{LEX} is a stream cipher proposed by Alex Biryukov. It was selected to phase $3$ of the eSTREAM competition. \texttt{LEX} is based on the Advanced Encryption Standard {\texttt{AES}) block cipher and uses a methodology called {\em Leak Extraction}, proposed by Biryukov himself. However Dunkelman and Keller show that a key recovery attack exists against \texttt{LEX}. Their attack requires $2^{36.3}$ bytes of keystream produced by the same key and works with a time complexity of $2^{112}$ operations. In this work we explored \texttt{LEX} further and have shown that under the assumption of a related key model we can obtain $24$ secret state bytes with a time complexity of $2^{96}$ and a data complexity of $2^{54.3}$. Subsequently, we introduce a tweaked version of \texttt{LEX}, called \texttt{TweLEX}, which is shown to resist all known attacks against \texttt{LEX}. Though the throughput of \texttt{TweLEX} is half of \texttt{LEX}, it is still $1.25$ times faster than \texttt{AES}, the underlying block cipher. This work attempts to revive the principle of {\em leak extraction} as a simple and elegant method to design stream ciphers.

KASUMI is a block cipher used in the confidentiality and integrity algorithms of the 3GPP (3rd Generation Partnership Project) mobile communications. In 2010, a related-key attack on full KASUMI was reported. The attack was very powerful and worked in practical complexity. However the attack was not a direct threat to full KASUMI because of the impractical assumptions related to the attack. Therefore, this paper concentrates on single-key attacks considered to be practical attacks. This paper proposes a single-key attack on 6-round KASUMI. The attack, which applies a technique of higher order differential attacks, requires 2^{60.8} data and 2^{65.4} encryption time. To the best of our knowledge, the attack reported in this paper is the most powerful single-key attack against reduced-round KASUMI in terms of time complexity.

FOX is a family of symmetric block ciphers from MediaCrypt AG that helps to secure digital media, communications, and storage. The high-level structure of FOX is the so-called (extended) Lai-Massey scheme. This paper presents a detailed fault analysis of the block cipher FOX64, the 64-bit version of FOX, based on a differential property of tworound Lai-Massey scheme in a fault model. Previous fault attack on FOX64 shows that each round-key (resp. whole round-keys) could be recovered through 11.45 (resp. 183.20) faults on average. Our proposed fault attack, however, can deduce any round-key (except the first one) through 4.25 faults on average (4 in the best case), and retrieve the whole round-keys through 43.31 faults on average (38 in the best case). This implies that the number of needed faults in the fault attack on FOX64 can be significantly reduced. Furthermore, the technique introduced in this paper can be extended to other series of the block cipher family FOX.

KISS (`Keep it Simple Stupid') is an efficient pseudo-random number generator specified by G. Marsaglia and A. Zaman in 1993. G. Marsaglia in 1998 posted a C version to various USENET newsgroups, including \texttt{sci.crypt}. Marsaglia himself has never claimed cryptographic security for the KISS generator, but many others have made the intellectual leap and claimed that it is of cryptographic quality. In this paper we show a number of reasons why the generator does not meet the KISS authors' claims, why it is not suitable for use as a stream cipher, and that it is not cryptographically secure. Our best attack requires about 70 words of generated output and a few hours of computation to recover the initial state.

GOST is a well known block cipher which was developed in the Soviet Union during the 1970's as an alternative to the US-developed DES. In spite of considerable cryptanalytic effort, until very recently there were no published single key attacks against its full 32-round version which were faster than the $2^{256}$ time complexity of exhaustive search. In February 2011, Isobe used in a novel way the previously discovered reflection property in order to develop the first such attack, which requires $2^{32}$ data, $2^{64}$ memory and $2^{224}$ time. Shortly afterwards, Courtois and Misztal used a different technique to attack the full GOST using $2^{64}$ data, $2^{64}$ memory and $2^{226}$ time. In this paper we introduce a new fixed point property and a better way to attack 8-round GOST in order to find improved attacks on full GOST: Given $2^{32}$ data we can reduce the memory complexity from an impractical $2^{64}$ to a practical $2^{36}$ without changing the $2^{224}$ time complexity, and given $2^{64}$ data we can simultaneously reduce the time complexity to $2^{192}$ and the memory complexity to $2^{36}$.

MQ_DRBG is a pseudorandom number bit generator proposed for international standardization by the French national organization for Standardization (AFNOR). It makes use of a specific instantiation of a one-way function $S:\ftwo^n\rightarrow \ftwo^{n+r}$ based on quadratic multivariate polynomials. We describe two methods for constructing function $S$, satisfying requirements of the proposed draft, but having less security level.

In response to needs of disk encryption standardization bodies, we provide the first tweakable ciphers that are proven to securely encipher their own keys. We provide both a narrowblock design StE and a wideblock design EtE. Our proofs assume only standard PRP-CCA security of the underlying tweakable ciphers.

The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for constructing lightweight RFID authentication protocols. The cryptographic power of adding biased noise can be characterized by the hardness of the intensively studied Learning Parity with Noise (LPN) Problem. In analogy to this, we identify a corresponding learning problem called RandomSelect for random selection and study its complexity. Given L secret linear functions f_1,...,f_L : {0,1}^n -> {0,1}^a, RandomSelect(L,n,a) denotes the problem of learning f_1,...,f_L from values (u,f_l(u)), where the secret indices l \in {1,...,L} and the inputs u \in {0,1}^n are randomly chosen by an oracle. We take an algebraic attack approach to design a nontrivial learning algorithm for this problem, where the running time is dominated by the time needed to solve full-rank systems of linear equations over O(n^L) unknowns. In addition to the mathematical findings relating correctness and average running time of the suggested algorithm, we also provide an experimental assessment of our results.

Much recent work in cryptography attempts to build secure schemes in the presence of \emph{side-channel leakage} or leakage caused by malicious software, like computer viruses. In this setting, the adversary may obtain some additional information (beyond the control of the scheme designer) about the internal secret state of a cryptographic scheme. Here, we consider key-evolution schemes that allow a user to evolve a secret-key $K_1$ via a \emph{deterministic} function $f$, to get updated keys $K_2 = f(K_1), K_3 = f(K_2), \ldots$. Such a scheme is \emph{leakage-resilient} if an adversary that can leak on the first $i$ steps of the evolution process does not get any useful information about any future keys. For such schemes, one must assume some restriction on the \emph{complexity} of the leakage to prevent \emph{pre-computation attacks}, where the leakage on a key $K_i$ simply pre-computes a future key $K_{i+ t}$ and leaks even a single bit on it. We notice that much of the prior work on this problem, and the restrictions made therein, can be divided into two types. Theoretical work offers rigor and provable security, but at the cost of having to make strong restrictions on the type of leakage and designing complicated schemes to make standard reduction-based proof techniques go through (an example of such an assumption is that only the data actually used in computation can leak to the adversary). On the other hand, practical work focuses on simple and efficient schemes, often at the cost of only achieving an intuitive notion of security without formal well-specified guarantees. In this paper, we complement the two tracks via a middle-of-the-road approach. On one hand, we rely on the random-oracle model, acknowledging the usefulness of this methodology in practice despite its theoretical shortcomings. On the other hand, we show that even in the random-oracle model, designing secure leakage-resilient schemes with clear and meaningful guarantees requires great care and is susceptible to pitfalls. For example, just assuming that leakage ``cannot evaluate the random oracle'' can be misleading. Instead, we define a new model in which we assume that the ``leakage'' can be any arbitrary \emph{space bounded} computation that can make random oracle calls itself. We connect the space-complexity of a computation in the random-oracle modeling to the \emph{pebbling complexity} on graphs. Using this connection, we derive meaningful guarantees for relatively simple key-evolution constructions. Our security proofs do not rely on the assumption that only data used in the computation can leak. Our scheme is secure also against a large and natural class of active attacks. This is especially important if the key evolution is performed on a PC that can be attacked by a virus. So far, all results that provided solutions against such attacks were secure under the assumption that the virus can download the data from the machine, but he cannot modify any information stored on it (that was called the {\em bounded retrieval model (BRM)}). This paper provides the first scheme were the adversary in the BRM can also modify the data stored on the machine.

The hardware-attractive block cipher family KTANTAN was studied by Bogdanov and Rechberger who identified flaws in the key schedule and gave a meet-in-the-middle attack. We revisit their result before investigating how to exploit the weakest key bits. We then develop several related-key attacks, e.g., one on KTANTAN32 which finds 28 key bits in time equivalent to $2^{3.0}$ calls to the full KTANTAN32 encryption. The main result is a related-key attack requiring $2^{28.44}$ time (half a minute on a current CPU) to recover the full 80-bit key. For KTANTAN48, we find three key bits in the time of one encryption, and give several other attacks, including full key recovery. For KTANTAN64, the attacks are only slightly more expensive, requiring $2^{10.71}$ time to find 38 key bits, and $2^{32.28}$ for the entire key. For all attacks, the requirements on related-key material are modest as in the forward and backward directions, we only need to flip a single key bit. All attacks succeed with probability one. Our attacks directly contradict the designers' claims. We discuss why this is, and what can be learnt from this.

PRINTcipher is a recent lightweight block cipher designed by Knudsen et al. Some noteworthy characteristics are a burnt-in key, a key-dependent permutation layer and identical round keys. Independent work on PRINTcipher has identified weak key classes that allow for a key recovery --- the obvious countermeasure is to avoid these weak keys at the cost of a small loss of key entropy. This paper identifies several larger classes of weak keys. We show how to distinguish classes of keys and give a $28$-round linear attack applicable to half the keys. We show that there are several similar attacks, each focusing on a specific class of keys. We also observe how some specific properties of PRINTcipher allow us to collect several samples from each plaintext--ciphertext pair. We use this property to construct an attack on $29$-round PRINTcipher applicable to a fraction $2^{-5}$ of the keys.

In this paper we describe the first single-key attack which can break the full version of Grain-128 for arbitrary keys by an algorithm which is considerably faster than exhaustive search (by a factor of about $2^{38}$). It uses a new version of a cube tester, which uses an improved choice of dynamic variables to eliminate all the previously made assumptions on the key, to speed up the attack, and to simplify the final key recovery. Since it is extremely difficult to mathematically analyze the expected behavior of such attacks, we implemented it on RIVYERA, which is a new massively parallel reconfigurable hardware, and tested its main components for dozens of random keys. These tests experimentally verified the correctness and expected complexity of the attack. This is the first time a complex analytical attack is successfully realized against a full-size cipher with a special-purpose machine. Moreover, it is also the first attack that truly exploits the configurable nature of an FPGA-based cryptanalytical hardware.

We present a study on the algebraic degree of iterated permutations seen as multivari- ate polynomials. Our main result shows that this degree depends on the algebraic degree of the inverse of the permutation which is iterated. This result is also extended to non-injective balanced vectorial functions where the relevant quantity is the minimal degree of the inverse of a permutation expanding the function. This property has consequences in symmetric cryptography since several attacks or distinguishers exploit a low algebraic degree, like higher-order differential attacks, cube attacks and cube testers, or algebraic attacks. Here, we present some applications of this improved bound to a higher-degree variant of the block cipher KN , to the block cipher Rijndael-256 and to the inner permutations of the hash functions ECHO and JH.

SQUARE, an 8-round substitution-permutation block cipher, is considered as the predecessor of the AES. In this paper, inspired from the recent biclique attack on the AES by Bogdanov et al., we present the first single-key attack on full SQUARE. First, we introduce a biclique for 3 rounds of SQUARE using the independent related-key differentials. Then, we present an attack on the full round of this cipher with a data complexity of about 2^48 chosen plaintexts and a time complexity of about 2^126 encryptions.

In this paper, we present new general techniques for practical security evaluation against differential and linear cryptanalysis for an extensive class of block ciphers similar to the cipher GOST. We obtain upper bounds of the average differential and linear characteristic probabilities for an arbitrary GOST-like cipher. The obtained bounds have similar form to the upper bounds of the average differential and linear characteristic probabilities known for some Markov Feistel ciphers. But, the expressions of our bounds contain new parameters (different from the classical differential and linear probabilities) of the cipher's $s$-boxes. These parameters are very natural for GOST-like ciphers, since they inherit the type of operation (key addition modulo $2^m$) used in these ciphers. The methods our proofs are based on are of independent interest and can be used for investigation both of a wider class of block ciphers and of a wider class of attacks. Application of our results to GOST shows that maximum values of the average differential and linear characteristic probabilities of this cipher (with 32 rounds and some $s$-boxes) are bounded by $2^{-59.57}$ and $2^{-42}$, respectively. The last two estimates of practical security of GOST against the differential and linear cryptanalysis are not quite impressive. But, as far as we know, they are the best of such estimates obtained by an accurate mathematical proof.

The cryptographic algorithm called INCrypt32 is a MAC algorithm to authenticate participants, RFID cards and readers, in HID Global's iCLASS systems. HID's iCLASS cards are widely used contactless smart cards for physical access control. Although INCrypt32 is a heart of the security of HID's iCLASS systems, its security has not been evaluated yet since the specication has not been open to public. In this paper, we reveal the specication of INCrypt32 by reverse engineering an iCLASS card and investigate the security of INCrypt32. As a result, we show that the secret key of size 64 bits can be recovered using only $2^{18}$ MAC queries if the attacker can request MAC for chosen messages of arbitrary length. If the length of messages is limited to predetermined values by the authentication protocol, the required number of MAC queries grows to $2^{42}$ to recover the secret key.

Since Rijndael was chosen as the Advanced Encryption Standard, improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 192/256-bit key variants has been one of the most difficult challenges in the cryptanalysis of block ciphers for more than a decade. In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results: 1) The first key recovery attack on the full AES-128 with computational complexity 2126.1. 2) The first key recovery attack on the full AES-192 with computational complexity 2^189.7. 3) The first key recovery attack on the full AES-256 with computational complexity 2^254.4. 4) Attacks with lower complexity on the reduced-round versions of AES not considered before, including an attack on 8-round AES-128 with complexity 2^124.9. 5) Preimage attacks on compression functions based on the full AES versions. In contrast to most shortcut attacks on AES variants, we do not need to assume any related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

In 2007, the US National Institute for Standards and Technology announced a call for the design of a new cryptographic hash algorithm in response to vulnerabilities identified in existing hash functions, such as MD5 and SHA-1. NIST received many submissions, 51 of which got accepted to the first round. At present, 14 candidates are left in the second round. An important criterion in the selection process is the SHA-3 hash function security and more concretely, the possible security reductions of the hash function to the security of its underlying building blocks. While some of the candidates are supported with firm security reductions, for most of the schemes these results are still incomplete. In this paper, we compare the state of the art provable security reductions of the second round candidates. We discuss all SHA-3 candidates at a high functional level, and analyze and summarize the security reduction results. Surprisingly, we derive some security bounds from the literature, which the hash function designers seem to be unaware of. Additionally, we generalize the well-known proof of collision resistance preservation, such that all SHA-3 candidates with a suffix-free padding are covered.

We suggest a new framework for block ciphers named Advanced Block Cipher, or shortly ABC. ABC has additional non-secret parameters that ensure that each call to the underlying block cipher uses a different pseudo-random permutation. It therefore ensures that attacks that require more than one block encrypted under the same secret permutation cannot apply. In particular, this framework protects against dictionary attacks, and differential and linear attacks, and eliminates weaknesses of ECB and CBC modes. This new framework shares a common structure with HAIFA, and can share the same logic with HAIFA compression functions. We analyze the security of several modes of operation for ABCs block ciphers, and suggest a few instances of ABCs.

ECHO-256 is a second-round candidate of the SHA-3 competition. It is an AES-based hash function that has attracted a lot of interest and analysis. Up to now, the best known attacks were a distinguisher on the full internal permutation and a collision on four rounds of its compression function. The latter was the best known analysis on the compression function as well as the one on the largest number of rounds so far. In this paper, we extend the compression function results to get a distinguisher on 7 out of 8 rounds using rebound techniques. We also present the first 5-round collision attack on the ECHO-256 hash function.

We present cryptanalytic results of an exhaustive search of all $16!$ bijective 4-bit S-Boxes. Previously affine equivalence classes have been exhaustively analyzed in 2007 work by Leander and Poschmann. We extend on this work by giving further properties of the optimal S-Box linear equivalence classes. In our main analysis we consider two S-Boxes to be cryptanalytically equivalent if they are isomorphic up to the permutation of input and output bits and a XOR of a constant in the input and output. We have enumerated all such equivalence classes with respect to their differential and linear properties. These equivalence classes are equivalent not only in their differential and linear bounds but also have equivalent algebraic properties, branch number and circuit complexity. We describe a ``golden'' set of S-boxes that have ideal cryptographic properties. We also present a comparison table of S-Boxes from a dozen published cryptographic algorithms.

In this paper, we present a new combinatorial conjecture about binary strings. Based on the new conjecture, two classes of Boolean functions of $2k$ variables with optimal algebraic immunity are proposed, where $k\ge 2$. The first class contains unbalanced functions having high algebraic degree and nonlinearity. The functions in the second one are balanced and have maximal algebraic degree and high nonlinearity. It is checked that, at least for small numbers of variables, both classes of functions have a good behavior against fast algebraic attacks. Compared with the known Boolean functions resisting algebraic attacks and fast algebraic attacks, the two classes of functions possess the highest lower bounds on nonlinearity. These bounds are however not enough for ensuring a sufficient nonlinearity for allowing resistance to the fast correlation attack. Nevertheless, as for previously found functions with the same features, there is a gap between the bound that we can prove and the actual values computed for small numbers of variables. Moreover, these values are very good and much better than for the previously found functions having all the necessary features for being used in the filter model of pseudo-random generators.

In this paper we find a lower bound of the second-order nonlinearities of Boolean bent functions of the form $f(x) = Tr_{1}^{n}(\alpha_{1}x^{d_{1}} + \alpha_{2}x^{d_{2}})$,where $d_1$ and $d_2$ are Niho exponents. A lower bound of the second-order nonlinearities of these Boolean functions can also be obtained by using a result proved by Li, Hu and Gao (eprint.iacr.org/2010 /009.pdf). It is demonstrated that for large values of $n$ the lower bound obtained in this paper are better than the lower bound obtained by Li, Hu and Gao.

GOST 28147-89 is a well-known block cipher and the official encryption standard of the Russian Federation. A 256-bit block cipher considered as an alternative for AES-256 and triple DES, having an amazingly low implementation cost and thus increasingly popular and used. Until 2010 researchers unanimously agreed that: "despite considerable cryptanalytic efforts spent in the past 20 years, GOST is still not broken" and in 2010 it was submitted to ISO 18033 to become a worldwide industrial encryption standard. In 2011 it was suddenly discovered that GOST is insecure on more than one account. There is an amazing variety of recent attacks on GOST. We have reflection attacks, attacks with double reflection, and various attacks which does not use reflections. All these methods follow a certain general framework called "Algebraic Complexity Reduction", a new general "umbrella" paradigm. The final key recovery step is in most cases a software algebraic attack and sometimes a Meet-In-The-Middle attack. In this paper we show that GOST is NOT SECURE even against (advanced forms of) differential cryptanalysis (DC). Previously Russian researchers postulated that GOST will be secure against DC for as few as 7 rounds out of 32 and Japanese researchers were already able to break about 13 rounds. In this paper we show a first advanced differential attack faster than brute force on full 32-round GOST. This paper is just a sketch and a proof of concept. More results of this kind will be published soon.

Faults occurred during the operations in a hardware device cause many problems such as performance deterioration, unreliable output, etc. If a fault occurs in a cryptographic hardware device, the effect can be even serious because an adversary may exploit it to find the secret information stored in the device. More precisely, the adversary can find the key of a block cipher using differential information between correct and faulty ciphertexts obtained by inducing faults during the computation of ciphertexts. This kind of attack is called \emph{Differential Fault Analysis} (DFA). Among many ciphers \emph{Advanced Encryption Standard} (AES) has been the main target of DFA due to its popularity. AES is widely used in different platforms and systems including Intel and AMD microprocessors. Normally DFA on AES exploits faults induced at the last few rounds. Hence, a general countermeasure is to recompute the last few rounds of AES and compare it with the original output. As redundancy is a costly countermeasure, one should ascertain exactly which rounds need to be protected. In 2006, Phan and Yen introduced a new type of DFA, so called Square-DFA, that works even when faults are induced into some middle rounds. However, it is impractical as it requires several hundreds of faulty ciphertexts as well as a bit fault model. In this article, we propose new attacks that need only dozens of faulty ciphertexts in a byte fault model. Normally it is believed that randomly corrupting a byte is easier than corrupting a specific bit. In addition, we extend the attacks to the AES-192 and AES-256, which is the first result in the literature.

In this paper, we propose a new lightweight block cipher called LBlock. Similar to many other lightweight block ciphers, the block size of LBlock is 64-bit and the key size is 80-bit. Our security evaluation shows that LBlock can achieve enough security margin against known attacks, such as differential cryptanalysis, linear cryptanalysis, impossible differential cryptanalysis and related-key attacks etc. Furthermore, LBlock can be implemented efficiently not only in hardware environments but also in software platforms such as 8-bit microcontroller. Our hardware implementation of LBlock requires about 1320 GE on 0.18 $\mu m$ technology with a throughput of 200 Kbps at 100 KHz. The software implementation of LBlock on 8-bit microcontroller requires about 3955 clock cycles to encrypt a plaintext block.

The visual cryptography scheme (VCS) is a scheme which encodes a secret image into several shares, and only qualified sets of shares can recover the secret image visually, other sets of shares cannot get any information about the content of the secret image. From the point of view of encrypting (carrying) the secret information, the traditional VCS is not an efficient method. The amount of the information that a VCS encrypts depends on the amount of secret pixels. And because of the restrictions of the human eyes and the pixel expansion and the alignment problem of the VCS, a VCS perhaps can only be used to encrypt a small secret image. VCS requires a random number generator to guide the generation of the shares. As we will show in this paper, the random input of VCS can ba seen as a subchannel which helps carrying more secret information. We propose a general method to increase the amount of secret information that a threshold VCS can encrypt by treating the pseudo-random inputs of the VCS as a subchannel, i.e. the Encrypting More Information Visual Cryptography Scheme (EMIVCS). We also study the bandwidth of the proposed EMIVCS. The disadvantage of the proposed scheme is that, the decoding process is computer aided. However, compared with other computer aided VCS, the proposed scheme is more efficient.