We describe Heraclitus as an example of a stream cipher that uses a 128 bit index string to specify the structure of each instance in real time: each instance of Heraclitus will be a stream cipher based on mutually clocked shift registers. Ciphers with key-dependent structures have been investigated and are generally based on Feistel networks. Heraclitus, however, is based on mutually clocked shift registers. Ciphers of this type have been extensively analysed, and published attacks on them will be infeasible against any instance of Heraclitus. The speed and security of Heraclitus makes it suitable as a session cipher, that is, an instance is generated at key exchange and used for one session.

We introduce the rebound attack as a variant of differential cryptanalysis on hash functions and apply it to the hash function Whirlpool, standardized by ISO/IEC. We give attacks on reduced variants of the Whirlpool hash function and the Whirlpool compression function. Next, we introduce the subspace problems as generalizations of near-collision resistance. Finally, we present distinguishers based on the rebound attack, that apply to the full compression function of Whirlpool and the underlying block cipher $W$.

The block cipher 1024 has a key schedule that somehow resembles that of IDEA. The user key is cyclicly shifted by a fiexed amount to form the round keys. In the key schedule of IDEA this has lead to weak keys. The primitive key schedule from 1024 may lead also to attacks with related keys. Although to the knowlegde of the author weak keys or attacks with related keys have not yet been published, there is a need to put things right. The new one-way key schedule of 1024XKS (eXtended Key Schedule) has pseudo-random round keys, which are obtained by using the cipher as randomizer.Apart from that, the user key has now to sizes, 2048 bit and 4096 bit. Also the order of the s-boxes have been changed to thwart attacks based on symmetry

An distinguisher was constructed by utilizing a 2-round collision differential path of ALPHA-MAC, with about $2^{65.5}$ chosen messages and $2^{65.5}$ queries. Then, this distinguisher was used to recover the internal state(\cite{Yuan1},\cite{Yuan2}). However, a flaw is found in the internal state recovery attack. The complexity of recovering the internal state is up to $2^{81}$ exhaustive search. And the complexity of the whole attack will be up to $2^{67}$ chosen messages and $2^{81}$ exhaustive search. To repair the flaw, a modified 2-round differential path of ALPHA-MAC is present and a new distinguisher based on this path is proposed. Finally, an attack with about $2^{65.5}$ chosen messages and $2^{65.5}$ queries is obtained under the new distinguisher.

SMS4 is a 128-bit block cipher with a 128-bit user key and 32 rounds, which is used in the Chinese National Standard for Wireless LAN WAPI. In this paper, all possible differential patterns are divided into several sections by six designed rules. In order to evaluate the security against the differential cryptanalysis of SMS4, we calculate the lower bounds on the number of active S-Boxes for all kinds of sections, based on which the lower bounds on the number of active S-Boxes in all possible differential patterns can be derived. Finally, the upper bounds on differential characteristic probabilities of arbitrary round numbers are given, which can be used to estimate the strength of SMS4 against differential attack and linear attack.

In this note we de¯ne small scale variants of the block cipher present [1]. The main reason for this is that the running time of some recent attacks (e.g. [2, 3]) remain unclear as they are based on heuristics that are hard or even impossible to verify in practice. Those attacks usually require the full code bock of present to be available and they work only if some independence assumptions hold in practice. While those assumptions are clearly wrong from a theoretical point of view, the impact on the running times of the attacks in question is not clear. With versions of present with smaller block size it might be possible to verify how those attacks scale for those versions and hopefully learn something about present itself.

In this paper, we propose a new double-piped mode of operation for multi-property-preserving domain extension of MACs~(message authentication codes), PRFs~(pseudorandom functions) and PROs~(pseudorandom oracles). Our mode of operation performs twice as fast as the original double-piped mode of operation of Lucks while providing comparable security. Our construction, which uses a class of polynomial-based compression functions proposed by Stam, makes a single call to a $3n$-bit to $n$-bit primitive at each iteration and uses a finalization function $f_2$ at the last iteration, producing an $n$-bit hash function $H[f_1,f_2]$ satisfying the following properties. \begin{enumerate} \item $H[f_1,f_2]$ is unforgeable up to $O(2^n/n)$ query complexity as long as $f_1$ and $f_2$ are unforgeable. \item $H[f_1,f_2]$ is pseudorandom up to $O(2^n/n)$ query complexity as long as $f_1$ is unforgeable and $f_2$ is pseudorandom. \item $H[f_1,f_2]$ is indifferentiable from a random oracle up to $O(2^{2n/3})$ query complexity as long as $f_1$ and $f_2$ are public random functions. \end{enumerate} To our knowledge, our result constitutes the first time $O(2^n/n)$ unforgeability has been achieved using only an unforgeable primitive of $n$-bit output length. (Yasuda showed unforgeability of $O(2^{5n/6})$ for Lucks' construction assuming an unforgeable primitive, but the analysis is sub-optimal; in this paper, we show how Yasuda's bound can be improved to $O(2^n)$.) In related work, we strengthen Stam's collision resistance analysis of polynomial-based compression functions (showing that unforgeability of the primitive suffices) and discuss how to implement our mode by replacing $f_1$ with a $2n$-bit key blockcipher in Davies-Meyer mode or by replacing $f_1$ with the cascade of two $2n$-bit to $n$-bit compression functions.

The low degree relation for algebraic attacks on E0 combiner given in \cite{DBLP:conf/crypto/ArmknechtK03} had an error. The correct version of low degree relation for the E0 combiner for use in algebraic attack is given.

This paper presents a formal security analysis of SSH in counter mode in a security model that accurately captures the capabilities of real-world attackers, as well as security-relevant features of the SSH specifications and the OpenSSH implementation of SSH. Under reasonable assumptions on the block cipher and MAC algorithms used to construct the SSH Binary Packet Protocol (BPP), we are able to show that the SSH BPP meets a strong and appropriate notion of security: indistinguishability under buffered, stateful chosen-ciphertext attacks. This result helps to bridge the gap between the existing security analysis of the SSH BPP by Bellare et al. and the recently discovered attacks against the SSH BPP by Albrecht et al. which partially invalidate that analysis.

Some new near $5$ rounds impossible differential properties of AES are first presented in this paper, in which active bytes of $1^{st}$ round or $5^{th}$ round are in different columns and in favor of extension. Additionally, we first propose the complexities expressions of an universal impossible differential attack, which can help us to rapidly search appropriate impossible differential paths. More importantly, our near $5$ rounds impossible differential properties and complexities expressions lead to a series of new impossible differential attacks on 7 rounds AES-128, 7-9 rounds AES-192, and 8-12 rounds AES-256.

Hash function Skein is one of the 14 NIST SHA-3 second round candidates. Threefish is a tweakable block cipher as the core of Skein, defined with a 256-, 512-, and 1024-bit block size. The 512-bit block size is the primary proposal of the authors. Skein had been updated after it entered the second round, the only differences between the original and the new version are the rotation constants. In this paper we construct related-key boomerang distinguishers on round-reduced Threefish-512 based on the new rotation constants using the method of \emph{modular differential}. With these distinguishers, we mount related-key boomerang key recovery attacks on Threefish-512 reduced to 32, 33 and 34 rounds. The attack on 32-round Threefish-512 has time complexity $2^{195}$ with memory of $2^{12}$ bytes. The attacks on Threefish-512 reduced to 33 and 34 rounds has time complexity of $2^{325.56}$ and $2^{483}$ encryptions respectively, and both with negligible memory. The best key recovery attack known before is proposed by Aumasson et al. Their attack, which bases on the old rotation constants, is also a related-key boomerang attack. For 32-round Threefish-512, their attack requires $2^{312}$ encryptions and $2^{71}$ bytes of memory.

An earlier paper by the same author (IACR Eprint 2008/473) suggested combining a block cipher and a stream cipher to get a strong hybrid cipher. This paper proposes a specific cipher based on those ideas, using the HC-128 stream cipher and a tweakable block cipher based on Serpent.

Hamsi is one of the second round candidates of the SHA-3 competition. In this study, we present non-random differential properties for the compression function of the hash function Hamsi-256. Based on these properties, we first demonstrate a distinguishing attack that requires a few evaluations of the compression function and extend the distinguisher to 5 rounds with complexity $2^{83}$. Then, we present a message recovery attack with complexity of $2^{10.48}$ compression function evaluations. Also, we present a pseudo-preimage attack for the compression function with complexity $2^{254.25}$. The pseudo-preimage attack on the compression function is easily converted to a pseudo second preimage attack on Hamsi-256 hash function with the same complexity.

Square is 8-round SPN structure block cipher and its round function and key schedule have been slightly modified to design building blocks of Rijndael. Key schedule of Square is simple and efficient but fully affie, so we apply a related-key attack on it. We find a 3-round related-key differential trail with probability 2^28, which have zero differences both on its input and output states, and this trail is called the local collision in [5]. By extending of this related-key differential, we construct a 7-round related-key boomerang distinguisher and successful attack on full round Square. The best attack on Square have ever been known is the square attack on 6-round reduced variant of Square. In this paper, we present a key recovery attack on the full round of Square using a related-key boomerang distinguisher. We construct a 7-round related-key boomerang distinguisher with probability 2^119 by finding local collision, and calculate its probability using ladder switch and local amplification techniques. As a result, one round on top of distinguisher is added to construct a full round attack on Square which recovers 16-bit key information with 2^36 encryptions and 2^123 data.

We study algebraic degree profile of reduced-round block cipher schemes. We show that the degree is not maximal with elementary combinatorial and algebraic arguments. We discuss on how it can be turned into distinguishers from balanced random functions.

The 128-bit block cipher TWIS was proposed by Ojha et al in 2009. It is a lightweight block cipher and its design is inspired from CLEFIA. In this paper, we first study the properties of TWIS structure, and as an extension we also considered the generalized TWIS-type structure which can be called G-TWIS cipher, where the block size and round number can be arbitrary values. Then we present a series of 10-round differential distinguishers for TWIS and a n-round differential distinguisher for G-TWIS whose probabilities are all equal to 1. Therefore, by utilizing these kinds of differential distinguishers, we can break the full 10-round TWIS cipher and n-round G-TWIS cipher.

SMS4 is a 128-bit block cipher used in the WAPI standard for wireless networks in China. In this paper, we analyze the security of SMS4 block cipher against differential cryptanalysis. Firstly, we prove three theorems and one corollary that reflect relationships of 5- and 6-round SMS4. Nextly, by these relationships, we clarify the minimum number of differentially active S-boxes in 6-, 7- and 12-round SMS4 respectively. Finally, based on the above results, we present a family of about $2^{14}$ differential characteristics for 19-round SMS4, which leads to an attack on 23-round SMS4 with $2^{115}$ chosen plaintexts and $2^{124.3}$ encryptions. Our attack is the best known attack on SMS4 so far.

In the paper on the example of the cryptosystem DES, the successful method of a cryptanalysis is presented. As a result, it is offered as a criterion of the cryptographic security to use a complexity of building and solving the system of Boolean functions, describing the cipher construction procedure.

The Advanced Encryption Standard (AES) is the most widely deployed block cipher. It follows the modern iterated block cipher approach, iterating a simple round function multiple times. The last round of AES slightly differs from the others, as a linear mixing operation (called MixColumns) is omitted from it. Following a statement of the designers, it is widely believed that the omission of the last round MixColumns has no security implications. As a result, the majority of attacks on reduced-round variants of AES assume that the last round of the reduced-round version is free of the MixColumns operation. In this note we refute this belief, showing that the omission of MixColumns does affect the security of (reduced-round) AES. First, we consider a simple example of 1-round AES, where we show that the omission reduces the time complexity of an attack with a single known plaintext from 2^{48} to 2^{16}. Then, we examine several previously known attacks on 7-round AES-192 and show that the omission reduces their time complexities by a factor of 2^{16}.

ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities 2^67.4 and 2^134.7. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.

In 1994 Langford and Hellman introduced differential-linear cryptanalysis, which involves building a differential-linear distinguisher by concatenating a linear approximation with such a (truncated) differential that with probability 1 does not affect the bit(s) concerned by the input mask of the linear approximation. In 2002 Biham, Dunkelman and Keller presented an enhanced approach to include the case when the differential has a probability smaller than 1; and in 2005 they proposed several extensions of differential-linear cryptanalysis, including the high-order differential-linear analysis, the differential-bilinear analysis and the differential-bilinear-boomerang analysis. In this paper, we show that Biham et al.'s methodologies for computing the probabilities of a differential-linear distinguisher, a high-order differential-linear distinguisher, a differential-bilinear distinguisher and a differential-bilinear-boomerang distinguisher do not have the generality to describe the analytic techniques. Thus the previous cryptanalytic results obtained by using these techniques of Biham et al. are questionable. Finally, from a mathematical point we give general methodologies for computing the probabilities. The new methodologies lead to some better cryptanalytic results, for example, differential-linear attacks on 13-round DES and 10-round CTC2 with a 255-bit block size and key.

This paper describes a differential fault analysis (DFA) on AES with 192 and 256-bit keys. We show a new attack in which both 192 and 256-bit keys are retrieved within a feasible computational time. In order to verify the proposed attack and estimate the calculation time, we implement the proposed attack using C code on a PC. As a result, we successfully recover the original 192-bit key using 3 pairs of correct and faulty ciphertexts within 5 minutes, and 256-bit key using 2 pairs of correct and faulty ciphertexts and 2 pairs of correct and faulty plaintexts within 10 minutes.

In SAC'08, an improved fast correlation attack on stream ciphers was proposed. This attack is based on the fast correlation attack proposed at Crypto'00 and combined with the fast Walsh transform. However, we found that the attack results are wrong. In this paper, we correct the results of the attack algorithm by analyzing it theoretically. Also we propose a threshold of the valid bias.

This paper introduces the related-key boomerang and the related-key rectangle attacks. These new attacks can expand the cryptanalytic toolbox, and can be applied to many block ciphers. The main advantage of these new attacks, is the ability to exploit the related-key model twice. Hence, even ciphers which were considered resistant to either boomerang or related-key differential attacks may be broken using the new techniques. In this paper we present a rigorous treatment of the related-key boomerang and the related-key rectangle distinguishers. Following this treatment, we devise optimal distinguishing algorithms using the LLR (Logarithmic Likelihood Ratio) statistics. We then analyze the success probability under reasonable independence assumptions, and verify the computation experimentally by implementing an actual attack on a 6-round variant of KASUMI. The paper ends with a demonstration of the strength of our new proposed techniques with attacks on 10-round AES-192 and the full KASUMI.

This paper provides a unified framework for {\em improving} \PRF(pseudorandom function) advantages of several popular MACs (message authentication codes) based on a blockcipher modeled as \tx{RP} (random permutation). In many known MACs, the inputs of the underlying blockcipher are defined to be some deterministic affine functions of previously computed outputs of the blockcipher. Keeping the similarity in mind, we introduce a class of \tx{ADE}s (affine domain extensions) and a wide subclass of \tx{SADE}s (secure \tx{ADE}) containing $\mathcal{C} = \{ \tx{CBC-MAC},\ \tx{GCBC}^*,\ \tx{OMAC},\ \tx{PMAC} \}$. We define a parameter $N(t,q)$ for each domain extension and show that all \tx{SADE}s have \PRF advantages $O(tq/2^n + N(t,q)/2^n)$ where $t$ is the total number of blockcipher computations needed for all $q$ queries. We prove that \PRF advantage of any \tx{SADE} is $O(t^2/2^n)$ by showing that $N(t,q)$ is always at most ${t \choose 2}$. We provide a better estimate $O(tq)$ of $N(t,q)$ for all members of $\mathcal{C}$ and hence these MACs have {\em improved advantages $O(tq / 2^n)$}. Our proposed bounds for \tx{CBC-MAC} and $\tx{GCBC}^*$ are better than previous best known bounds.

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of $2^{ -14}$. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, $2^{26}$ data, $2^{30}$ bytes of memory, and $2^{32}$ time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the $2^{128}$ complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.

The paper presents a differential cache trace attack against CLEFIA, a $128$ bit block cipher designed by Sony Corporation. The attack shows that such ciphers based on the generalized Feistel structures leak information of the secret key if the cache trace pattern is revealed to an adversary. The attack that we propose is a three staged attack and reveals the entire key with $2^{43}$ CLEFIA encryptions. The attack is simulated on an Intel Core 2 Duo Processor with a cache architecture with $32$ byte lines as a target platform.

It is a difficult task to compute the $r$-th order nonlinearity of a given function with algebraic degree strictly greater than $r>1$. Even the lower bounds on the second order nonlinearity is known only for a few particular functions. We investigate the lower bounds on the second order nonlinearity of cubic Boolean functions $F_u(x)=Tr(\sum_{l=1}^{m}\mu_{l}x^{d_{l}})$, where $u_{l} \in F_{2^n}^{*}$, $d_{l}=2^{i_{l}}+2^{j_{l}}+1$, $i_{l}$ and $j_{l}$ are positive integers, $n>i_{l}> j_{l}$. Especially, for a class of Boolean functions $G_u(x)=Tr(\sum_{l=1}^{m}\mu_{l}x^{d_{l}})$, we deduce a tighter lower bound on the second order nonlinearity of the functions, where $u_{l} \in F_{2^n}^{*}$, $d_{l}=2^{i_{l}\gamma}+2^{j_{l}\gamma}+1$, $i_{l}> j_{l}$ and $\gamma\neq 1$ is a positive integer such that $gcd(n,\gamma)=1$. \\The lower bounds on the second order nonlinearity of cubic monomial Boolean functions, represented by $f_\mu(x)=Tr(\mu x^{2^i+2^j+1})$, $\mu\in F_{2^n}^*$, $i$ and $j$ are positive integers such that $i>j$, have recently (2009) been obtained by Gode and Gangopadhvay. Our results have the advantages over those of Gode and Gangopadhvay as follows. We first extend the results from monomial Boolean functions to Boolean functions with more trace terms. We further generalize and improve the results to a wider range of $n$. Also, our bounds are better than those of Gode and Gangopadhvay for monomial functions $f_\mu(x)$.

Format-preserving encryption (FPE) encrypts a plaintext of some specified format into a ciphertext of identical format—for example, encrypting a valid credit-card number into a valid creditcard number. The problem has been known for some time, but it has lacked a fully general and rigorous treatment.We provide one, starting off by formally defining FPE and security goals for it.We investigate the natural approach for achieving FPE on complex domains, the “rank-then-encipher” approach, and explore what it can and cannot do. We describe two flavors of unbalanced Feistel networks that can be used for achieving FPE, and we prove new security results for each. We revisit the cycle-walking approach for enciphering on a non-sparse subset of an encipherable domain, showing that the timing information that may be divulged by cycle walking is not a damaging thing to leak.

In this paper we investigate the security of the encryption mode of the HAS-160 hash function. HAS-160 is a Korean hash standard which is widely used in Korea's industry. The structure of HAS-160 is similar to SHA-1 but includes some improvements. The encryption mode of HAS-160 is defined similarly as the encryption mode of SHA-1 that is called SHACAL-1. In 2006, Dunkelman et. al. successfully broke the full 80-round SHACAL-1. In this paper, we present the first cryptographic attack that breaks the encryption mode of the full 80-round HAS-160. SHACAL-1 and the encryption mode of HAS-160 are both blockciphers with key size 512 bits and plain-/ciphertext size of 160 bits. We will apply a key recovery attack that needs about 2^{155} chosen plaintexts and 2^{375.98} 80-round HAS-160 encryptions. The attack does not aim for a collision, preimage or 2nd-preimage attack, but it shows that HAS-160 used as a block cipher can be differentiated from an ideal cipher faster than exhaustive search.

We observe that the function introduced by Z. Tu and Y. Deng in the ePrint Archive paper 2009/272 is weak against fast algebraic attacks. We propose an alternative function sharing all the properties of the Tu-Deng function but having not this weakness.

In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has $2^{99.5}$ time and data complexity, while the recent attack by Biryukov-Khovratovich-Nikolic works for a weak key class and has much higher complexity. The second attack is the first cryptanalysis of the full AES-192. Both our attacks are boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers and enhanced with the boomerang switching techniques to gain free rounds in the middle.

The nonlinearity profile of a Boolean function is the sequence of its minimum Hamming distances $nl_r(f)$ to all functions of degrees at most $r$, for $r\geq 1$. The nonlinearity profile of a vectorial function is the sequence of the minimum Hamming distances between its component functions and functions of degrees at most $r$, for $r\geq 1$.The profile of the multiplicative inverse functions has been lower bounded in a previous paper by the same author. No other example of an infinite class of functions with unbounded algebraic degree has been exhibited since then, whose nonlinearity profile could be efficiently lower bounded. In this preprint, we lower bound the whole nonlinearity profile of the simplest Dillon bent function $(x,y)\mapsto xy^{2^{n/2}-2}$, $x,y\in F_{2^{n/2}}$.

We study cubic monomial Boolean functions of the form $Tr_1^n(\mu x^{2^i+2^j+1})$ where $\mu \in \mathbb{F}_{2^n}$. We prove that the functions of this form do not have any affine derivative. A lower bound on the second order nonlinearities of these functions is also derived.

The known 3-round distinguisher of Rijndael-256 is byte- oriented and 2^8 plaintexts are needed to distinguish 3-round Rijndael from a random permutation. In this paper, we consider the influence of the order of the plaintexts and present a new 3-round distinguisher which only needs 32 plaintexts.

In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.

This paper shows a key recovery attack on QuiSci (quick stream cipher), designed by Stefan Müller (FGAN-FHR, a German research institute) in 2001. With one or few know plaintexts it's possible to recover most of the key with negligible time complexity. This paper shows a way how to exploit the weak key setup of QuiSci.

Abstract. The cube attack has been introduced by Itai Dinur and Adi Shamir [8] as a known plaintext attack on symmetric primitives. The attack has been applied to reduced variants of the stream ciphers Trivium [3, 8] and Grain-128 [2], reduced to three rounds variant of the block cipher Serpent [9] and reduced version of the hash function MD6 [3]. In the special case the attack has appeared in the M. Vielhaber ePrint articles [13, 14], where it has been named AIDA (Algebraic Initial Value Differential Attack ) and applied to the modified versions of Trivium. In this paper, we present the experimental results of application the cube attack to four rounds of the Courtois Toy Cipher (CTC) with the full recovery of 120-bit key. After that we extend the attack to five rounds by applying the meet-in-the-middle principle. Key words: Cube attack, symmetric primitives, Boolean polynomials, CTC, the meet-in-the-middle method

Impossible boomerang attack \cite{lu} (IBA) is a new variant of differential cryptanalysis against block ciphers. Evident from its name, it combines the ideas of both impossible differential cryptanalysis and boomerang attack. Though such an attack might not be the best attack available, its complexity is still less than that of the exhaustive search. In impossible boomerang attack, impossible boomerang distinguishers are used to retrieve some of the subkeys. Thus the security of a block cipher against IBA can be evaluated by impossible boomerang distinguishers. In this paper, we study the impossible boomerang distinguishers for block cipher structures whose round functions are bijective. Inspired by the $\mathcal{U}$-method in \cite{kim}, we provide an algorithm to compute the maximum length of impossible boomerang distinguishers for general block cipher structures, and apply the algorithm to known block cipher structures such as Nyberg's generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, etc.

In this paper, we present a preimage attack for 42 step-reduced SHA-256 with time complexity $2^{251.7}$ and memory requirements of order $2^{12}$. The same attack also applies to 42 step-reduced SHA-512 with time complexity $2^{502.3}$ and memory requirements of order $2^{22}$. Our attack is meet-in-the-middle preimage attack.

In this paper, we propose preimage attacks on 41-step SHA-256 and 46-step SHA-512, which drastically increase the number of attacked steps compared to the best previous preimage attack working for only 24 steps. The time complexity for 41-step SHA-256 is $2^{253.5}$ compression function operations and the memory requirement is $2^{16}\times 10$ words. The time complexity for 46-step SHA-512 is $2^{511.5}$ compression function operations and the memory requirement is $2^{3}\times 10$ words. Our attack is a meet-in-the-middle attack. We first consider the application of previous meet-in-the-middle attack techniques to SHA-2. We then analyze the message expansion of SHA-2 by considering all previous techniques to find a new independent message-word partition. We first explain the attack on 40-step SHA-256 whose complexity is $2^{249}$ to describe the ideas. We then explain how to extend the attack.

The hash function Blue Midnight Wish (BMW) is a candidate in the SHA-3 competition organised by the U.S. National Institute of Standards and Technology (NIST). BMW was selected for the second round of the competition, but the algorithm was tweaked in a number of ways. In this paper we describe cryptanalysis on the original version of BMW, as submitted to the SHA-3 competition in October 2008. When we refer to BMW, we therefore mean the original version of the algorithm. The attacks described are (near-)collision, preimage and second preimage attacks on the BMW compression function. These attacks can also be described as pseudo-attacks on the full hash function, i.e., as attacks in which the adversary is allowed to choose the initial value of the hash function. The complexities of the attacks are about 2^{14} for the near-collision attack, about 2^{3n/8+1} for the pseudo-collision attack, and about 2^{3n/4+1} for the pseudo-(second) preimage attack, where n is the output length of the hash function. Memory requirements are negligible. Moreover, the attacks are not (or only moderately) affected by the choice of security parameter for BMW.

We describe an SPA attack on an 8-bit smart card implementation of the Serpent block cipher. Our attack uses measurements taken during an on-the-fly key expansion together with linearity in the cipher's key schedule algorithm to drastically reduce the search time for an initial key. An implementation finds 256-bit keys in 3.736 ms on average. Our work shows that linearity in key schedule design and other cryptographic applications should be carefully evaluated for susceptibility to side-channel attacks and that search algorithm design can greatly speed up side-channel attacks.

In this paper we present a theoretical framework to quantify the information brought by several linear approximations of a block-cipher without putting any restriction on these approximations. We quantify here the entropy of the key given the plaintext-ciphertext pairs statistics which is a much more accurate measure than the ones studied earlier. The techniques which are developed here apply to various ways of performing the linear attack and can also been used to measure the entropy of the key for other statistical attacks. Moreover, we present a realistic attack on the full DES with a time complexity of $2^{48}$ for $2^{41}$ pairs what is a big improvement comparing to Matsui's algorithm 2 ($2^{51.9}$).

Abstract. BLUE MIDNIGHT WISH hash function is the fastest among 14 algorithms in the second round of SHA-3 competition [1]. At the beginning of this round authors were invited to add some tweaks before September 15th 2009. In this paper we discuss the tweaked version (BMW). The BMW algorithm [3] is of the type AXR, since it uses only operations ADD (sub), XOR and ROT (shift). If we substitute the operation ADD with operation XOR, we get a BMWlin, which is an affine transformation. In this paper we consider only a BMWlin function and its building blocks. These affine transformations can be represented as a linear matrix and a constant vector. We found that all matrices of main blocks of BMWlin have a full rank, or they have a rank very close to full rank. The structure of matrices was examined. Matrices of elementary blocks have an expected non-random structure, while main blocks have a random structure. We will also show matrices for different values of security parameter ExpandRounds1 (values between 0 and 16). We observed that increasing the number of rounds ExpandRounds1 tends to increase randomness as was intended by designers. These observations hold for both BMW256lin and BMW512lin. In this analysis we did not find any useful property, which would help in cryptanalysis, nor did we find any weaknesses of BMW. The study of all building blocks will follow.

In this work, we apply the rebound attack to the AES based SHA-3 candidate LANE. The hash function LANE uses a permutation based compression function, consisting of a linear message expansion and 6 parallel lanes. In the rebound attack on LANE, we apply several new techniques to construct a collision for the full compression function of LANE-256 and LANE-512. Using a relatively sparse truncated differential path, we are able to solve for a valid message expansion and colliding lanes independently. Additionally, we are able to apply the inbound phase more than once by exploiting the degrees of freedom in the parallel AES states. This allows us to construct semi-free-start collisions for full LANE-256 with $2^{96}$ compression function evaluations and $2^{88}$ memory, and for full LANE-512 with $2^{224}$ compression function evaluations and $2^{128}$ memory.

The hash function Skein is the submission of Ferguson et al. to the NIST Hash Competition, and is arguably a serious candidate for selection as SHA-3. This paper presents the first third-party analysis of Skein, with an extensive study of its main component: the block cipher Threefish. We notably investigate near collisions, distinguishers, impossible differentials, key recovery using related-key differential and boomerang attacks. In particular, we present near collisions on up to 17 rounds, an impossible differential on 21 rounds, a related-key boomerang distinguisher on 34 rounds, a known-related-key boomerang distinguisher on 35 rounds, and key recovery attacks on up to 32 rounds, out of 72 in total for Threefish-512. None of our attacks directly extends to the full Skein hash. However, the pseudorandomness of Threefish is required to validate the security proofs on Skein, and our results conclude that at least 36 rounds of Threefish seem required for optimal security guarantees.

eSTREAM called for new stream ciphers designed for niche areas such as exceptional performance in software and hardware where resources are restricted. This project provides an open platform to discuss these ciphers. Trivium is one of the promising new ciphers submitted to it. Until now, no attack has been successfully applied to it. This paper illustrates new design principles of stream ciphers based on the structure of Trivium and introduces the definition of k-order primitive polynomials. New designs of Trivium are also given according to the principles in this paper.

In this paper we show how to use an old mathematical concept of diophantine analysis, the approximation theorem of Kronecker, in symmetric cryptography. As a first practical application we propose and analyze the new symmetric 128-bit block cipher KronCrypt. The cipher is a 4-round Feistel network with a non-bijective round function f made up of a variable number of large key-dependent S-boxes, XORs and modular additions. Its key length is variable but not less than 128 bit. The main innovation of KronCrypt in the area of symmetric cryptography is the fact that the key-dependent S-boxes are based upon a constructive proof of the approximation theorem of Kronecker used as a boolean function. We prove the correctness of our concept in general and show how we designe the new cipher KronCrypt. Furthermore, results concerning statistical behaviour, i.e. confusion, diffusion and completeness, and differential cryptanalysis are presented.

In this paper, we give a security proof for Abreast-DM in terms of collision resistance and preimage resistance. As old as Tandem-DM, the compression function Abreast-DM is one of the most well-known constructions for double block length compression functions. The bounds on the number of queries for collision resistance and preimage resistance are given by O(2^n). Based on a novel technique using query-response cycles, our security proof is simpler than those for MDC-2 and Tandem-DM. We also present a wide class of Abreast-DM variants that enjoy a birthday-type security guarantee with a simple proof.

In this paper, we analyze the hash functions Dynamic SHA and Dynamic SHA2, which have been selected as first round candidates in the NIST hash function competition. These hash functions rely heavily on data-dependent rotations, similar to certain block ciphers, e.g., RC5. Our analysis suggests that in the case of hash functions, where the attacker has more control over the rotations, this approach is less favorable than in block ciphers. We present practical, or close to practical, collision attacks on both Dynamic SHA and Dynamic SHA2. Moreover, we present a preimage attack on Dynamic SHA that is faster than exhaustive search.

This paper describes a second preimage attack on the CubeHash cryptographic one-way hash function. The attack finds a second preimage in less time than brute force search for these CubeHash variants: CubeHash $r$/$b$-224 for $b > 100$; CubeHash$r$/$b$-256 for $b > 96$; CubeHash$r$/$b$-384 for $b > 80$; and CubeHash$r$/$b$-512 for $b > 64$. However, the attack does not break the CubeHash variants recommended for SHA-3. The attack requires minimal memory and can be performed in a massively parallel fashion. This paper also describes several statistical randomness tests on CubeHash. The tests were unable to disprove the hypothesis that CubeHash behaves as a random mapping. These results support CubeHash's viability as a secure cryptographic hash function.

Misty schemes are classic cryptographic schemes used to construct pseudo-random permutations from $2n$ bits to $2n$ bits by using $d$ pseudo-random permutations from $n$ bits to $n$ bits. These $d$ permutations will be called the ``internal'' permutations, and $d$ is the number of rounds of the Misty scheme. Misty schemes are important from a practical point of view since for example, the Kasumi algorithm based on Misty schemes has been adopted as the standard blockcipher in the third generation mobile systems. In this paper we describe the best known ``generic'' attacks on Misty schemes, i.e. attacks when the internal permutations do not have special properties, or are randomly chosen. We describe known plaintext attacks (KPA), non-adaptive chosen plaintext attacks (CPA-1) and adaptive chosen plaintext and ciphertext attacks (CPCA-2) against these schemes. Some of these attacks were previously known, some are new. One important result of this paper is that we will show that when $d=5$ rounds, there exist such attacks with a complexity strictly less than $2^{2n}$. Consequently, at least 6 rounds are necessary to avoid these generic attacks on Misty schemes. When $d \geq 6$ we also describe some attacks on Misty generators, i.e. attacks where more than one Misty permutation is required.

AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the $2^{128}$ complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require $2^{176}$ and $2^{119}$ time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems. In this paper we describe several attacks which can break {\it with practical complexity} variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and $2^{39}$ time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and $2^{120}$ time). Another attack can break a 10 round version of AES-256 in $2^{45}$ time, but it uses a stronger type of {\it related subkey attack} (the best previous attack on this variant required 64 related keys and $2^{172}$ time). While neither AES-128 nor AES-256 can be directly broken by these attacks, the fact that their hybrid (which combines the smaller number of rounds from AES-128 along with the larger key size from AES-256) can be broken with such a low complexity raises serious concern about the remaining safety margin offered by the AES family of cryptosystems.

\begin{abstract} In this paper, we explain the encryption algorithm used by the Queen of France, Marie-Antoinette, to send letters to Axel von Fersen during the French Revolution. We give the complete deciphering of some letters for which we found differences with the text taken from historical books. We also provide the deciphering of one letter that seems to be unknown so far. The results we get bring new proofs on Marie-Antoinette's deep affection for Fersen. Finally, we mention some open questions about Marie-Antoinette's correspondence with Axel von Fersen.

The stream cipher BIVIUM (both BIVIUM-A and BIVIUM-B), a modification of the eSTREAM finalist TRIVIUM, can be broken completely by the Algebraic IV Differential Attack, AIDA, using $2^{27.5}$ simulations or one minute of dual core processing. AIDA uses the subspaces of two 32-dimensional vector spaces over subsets of IV bits to recover 56 of the 80 key bits. The remaining 24 key bits are most easily determined by brute force search. We applied the Fast Reed-Muller Transform to speed up the search for linear equations in the key bits and the Wavefront Model to rule out nonlinear relations in the key bits early on.

Abstract. NESHA-256 is a cryptographic hash function designed by Esmaeili et al. and presented at WCC '09. We show that NESHA-256 is highly insecure.

In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of {\em differential $q$-multicollision} and show that for AES-256 $q$-multicollisions can be constructed in time $q\cdot 2^{67}$ and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least $O(q\cdot 2^{\frac{q-1}{q+1}128})$ time. Using similar approach and with the same complexity we can also construct $q$-pseudo collisions for AES-256 in Davies-Meyer hashing mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial $q$-multicollisions in time $q\cdot 2^{37}$ on a PC to verify our results. These results show that AES-256 can not model an ideal cipher in theoretical constructions. Finally, we extend our results to find the first publicly known attack on the full 14-round AES-256: a related-key distinguisher which works for one out of every $2^{35}$ keys with $2^{120}$ data and time complexity and negligible memory. This distinguisher is translated into a key-recovery attack with total complexity of $2^{131}$ time and $2^{65}$ memory.

The Edon-R compression function has a large set of useful differentials that produce easily detectable output bit biases. We show how to construct such differentials, and use them to create a distinguisher for Edon-R-512 that requires around $2^{54}$ compression function evaluations (or $2^{28}$ evaluations after a pre-computation of $2^{66}$ evaluations). The differentials can also be used to attack a variety of MAC and KDF constructions when they use Edon-R-512.

In this paper, we study GF-NLFSR, a Generalized Unbalanced Feis- tel Network (GUFN) which can be considered as an extension of the outer function FO of the KASUMI block cipher. We show that the differential and linear probabilities of any n + 1 rounds of an n-cell GF-NLFSR are both bounded by p^2, where the corresponding probability of the round function is p. Besides analyzing security against differential and linear cryptanalysis, we provide a frequency distribution for upper bounds on the true differential and linear hull probabilities. From the frequency distribution, we deduce that the proportion of input-output differences/mask values with probability bounded by p^n is close to 1 whereas only a negligible proportion has probability bounded by p^2. We also recall an n^2-round integral attack distinguisher and (n^2+n-2)-round impossible impossible differential distinguisher on the n-cell GF-NLFSR by Li et al. and Wu et al. As an application, we design a new 30-round block cipher Four-Cell+ based on a 4-cell GF-NLFSR. We prove the security of Four-Cell+ against differential, linear, and boomerang attack. Four-Cell+ also resists existing key recovery attacks based on the 16-round integral attack distinguisher and 18-round impossible differential distinguisher. Furthermore, Four-Cell+ can be shown to be secure against other attacks such as higher order differential attack, cube attack, interpolation attack, XSL attack and slide attack.

We address the practice of key-wrapping, where one symmetric cryptographic key is used to encrypt another. This practice is used extensively in key-management architectures, often to create an ``adapter layer'' between incompatible legacy systems. Although in principle any secure encryption scheme can be used for key wrapping, practical constraints (which are commonplace when dealing with legacy systems) may severely limit the possible implementations, sometimes to the point of ruling out any ``secure general-purpose encryption.'' It is therefore desirable to identify the security requirements that are ``really needed'' for the key-wrapping application, and have a large variety of implementations that satisfy these requirements. This approach was developed in a work by Rogaway and Shrimpton at EUROCRYPT 2006. They focused on allowing deterministic encryption, and defined a notion of deterministic authenticated encryption (DAE), which roughly formalizes ``the strongest security that one can get without randomness.'' Although DAE is weaker than full blown authenticated encryption, it seems to suffice for the case of key wrapping (since keys are random and therefore the encryption itself can be deterministic). Rogaway and Shrimpton also described a mode of operation for block ciphers (called SIV) that realizes this notion. We continue in the direction initiated by Rogaway and Shirmpton. We first observe that the notion of DAE still rules out many practical and ``seemingly secure'' implementations. We thus look for even weaker notions of security that may still suffice. Specifically we consider notions that mirror the usual security requirements for symmetric encryption, except that the inputs to be encrypted are random rather than adversarially chosen. These notions are all strictly weaker than DAE, yet we argue that they suffice for most applications of key wrapping. As for implementations, we begin by observing that many standard encryption modes satisfy the key-warpping notion that mirrors CPA-security, even when used with a fixed IV (with the notable exception of CTR mode). To achieve the notion that mirrors authenticated encryption, we investigate a template of Hash-then-Encrypt (HtE), which seems practically appealing: In this method the key is first ``hashed'' into a short nonce, and then the nonce and key are encrypted using some standard encryption mode. We consider a wide array of ``hash functions'', ranging from a simple XOR to collision-resistant hashing, and examine what ``hash function'' can be used with what encryption mode.

Let $\rF$ be a finite field and suppose that a single element of $\rF$ is used as an authenticator (or tag). Further, suppose that any message consists of at most $L$ elements of $\rF$. For this setting, usual polynomial based universal hashing achieves a collision bound of $(L-1)/|\rF|$ using a single element of $\rF$ as the key. The well-known multi-linear hashing achieves a collision bound of $1/|\rF|$ using $L$ elements of $\rF$ as the key. In this work, we present a new universal hash function which achieves a collision bound of $m\lceil\log_m L\rceil/|\rF|$, $m\geq 2$, using $1+\lceil\log_m L\rceil$ elements of $\rF$ as the key. This provides a new trade-off between key size and collision probability for universal hash functions.

Block ciphers are the very foundation of computer and information security. FOX, also known as IDEA NXT, is a family of block ciphers published in 2004 and is famous for its provable security to cryptanalysis. In this paper, we apply impossible differential cryptanalysis on FOX cipher. We find a 4-round impossible difference, by using which adversaries can attack 5, 6 and 7-round FOX64 with $2^{71}$, $2^{135}$ and $2^{199}$ one-round encryptions respectively. Compared to the previous best attack with $2^{109.4}$, $2^{173.4}$ and $2^{237.4}$ full-round encryptions to 5, 6 and 7-round FOX64, the method in this paper is the best attack to FOX cipher. This attack can also be applied to 5-round FOX128 with $2^{135}$ one-round encryptions.

The overall structure is one of the most important properties of block ciphers. At present, the most common structures include Feistel structure, SP structure, MISTY structure, L-M structure and Generalized Feistel structure. In \cite{29}, Choy et al. proposed a new structure called GF-NLFSR (Generalized Feistel-NonLinear Feedback Shift Register), and designed a new block cipher called Four-Cell which is based on the 4-cell GF-NLFSR. In this paper, we first study properties of the $n$-cell GF-NLFSR structure, and prove that for an $n$-cell GF-NLFSR, there exists an $(n^2+n-2)$ rounds impossible differential. Then we present an impossible differential attack on the full 25-round Four-Cell using this kind of 18-round impossible differential distinguisher together with differential cryptanalysis technique. The data complexity of our attack is $2^{111.5}$ and the time complexity is less than $2^{123.5}$ encryptions. In addition, we expect the attack to be more efficient when the relations between different round subkeys can be exploited by taking the key schedule algorithm into consideration.

ARIA is a block cipher proposed at ICISC'03. Its design is very similar to the advanced encryption standard (AES). The authors propose that on 32-bit processors, the encryption speed is at least 70% of that of the AES. They claim to offer a higher security level than AES. In this paper we present two attacks of reduced round ARIA which shows some weaknesses of the cipher. Moreover, our attacks have the lowest memory requirements compared to existing attacks on ARIA with an increase in the time complexity.

Fault analysis is a powerful attack to stream ciphers. Up to now, the major idea of fault analysis is to simplify the cipher system by injecting some soft faults. We call it soft fault analysis. As a hardware--oriented stream cipher, Trivium is weak under soft fault analysis. In this paper we consider another type of fault analysis of stream cipher, which is to simplify the cipher system by injecting some hard faults. We call it hard fault analysis. We present the following results about such attack to Trivium. In Case 1 with the probability not smaller than 0.2396, the attacker can obtain 69 bits of 80--bits--key. In Case 2 with the probability not smaller than 0.2291, the attacker can obtain all of 80--bits--key. In Case 3 with the probability not smaller than 0.2291, the attacker can partially solve the key. In Case 4 with non--neglectable probability, the attacker can obtain a simplified cipher, with smaller number of state bits and slower non--linearization procedure. In Case 5 with non--neglectable probability, the attacker can obtain another simplified cipher. Besides, these 5 cases can be checked out by observing the key--stream.

\begin{abstract} Generic attacks against classical (balanced) Feistel schemes, unbalanced Feistel schemes with contracting functions and unbalanced Feistel schemes with expanding functions have been studied in \cite {P01}, \cite{Jut}, \cite{PNB06}, \cite{PNB07}. In this paper we study schemes where we use alternatively contracting random functions and expanding random functions. We name these schemes ``Alternating Unbalanced Feistel Schemes''. They allow constructing pseudo-random permutations from $kn$ bits to $kn$ bits where $k \geq 3$. At each round, we use either a random function from $n$ bits to $(k-1)n$ bits or a random function from $(k-1)n$ bits to $n$ bits. We describe the best generic attacks we have found. We present``known plaintext attacks'' (KPA) and ``non-adaptive chosen plaintext attacks'' (CPA-1). Let $d$ be the number of rounds. We show that if $d \leq k$, there are CPA-1 with 2 messages and KPA with $m$ the number of messages about $2^{\frac {(d-1)n}{4}}$. For $d \geq k+1$ we have to distinguish $k$ even and $k$ odd. For $k$ even, we have $m=2$ in CPA-1 and $m \simeq 2^{\frac {kn}{4}}$ in KPA. When $k$ is odd, we show that there exist CPA-1 for $d \leq 2k-1$ and KPA for $d \leq 2k+3$ with less than $2^{kn}$ messages and computations. Beyond these values, we give KPA against generators of permutations. \end{abstract}

This thesis studies the ring of boolean functions. A simple algorithm that performs similarly to the euclidian algorithm is derived, and it's performance for solving multivariate boolean equation systems is evaluated. Furthermore, the Raddum-Semaev equation system solving algorithm is put into geometric context, and the pseudo-euclidian algorithm is generalized to multivariate polynomial rings over arbitrary finite fields.

In this paper, we propose a combinatoric conjecture on binary string, on the premise that our conjecture is correct we mainly obtain two classes of functions which are both algebraic immunity optimal: the first class of functions are also bent, moreover, from this fact we conclude that the algebraic immunity of bent functions can take all possible values except one. The second class are balanced functions, which have optimal algebraic degree and the best nonlinearity up to now.

At Asiacrypt’99, Vaudenay modified the structure in the IDEA cipher to a new scheme, which they called as the Lai-Massey scheme. It is proved that 3-round Lai-Massey scheme is sufficient for pseudorandomness and 4-round Lai-Massey scheme is sufficient for strong pseudorandomness. But the author didn’t point out whether three rounds and four rounds are necessary for the pseudorandomness and strong pseudorandomness of the Lai-Massey Scheme. In this paper we find a two round pseudorandomness distinguisher and a three-round strong pseudorandomness distinguisher, thus prove that three rounds is necessary for the pseudorandomness and four rounds is necessary for the strong pseudorandomness.

Edon-R is one of the fastest SHA-3 candidate. In this paper we study the security of Edon-R, and we show that using Edon-R as a MAC with the secret prefix construction is unsafe. We present a practical attack in the case of Edon-R256, which requires 32 queries, 2^30 computations, negligible memory, and a precomputation of 2^50 . This does not directly contradict the security claims of Edon-R or the NIST requirements for SHA-3, but we believe it shows a strong weakness in the design.

We provide the first proof of security for Abreast-DM, one of the oldest and most well-known constructions for turning a block cipher with $n$-bit block length and $2n$-bit key length into a 2n-bit cryptographic hash function. In particular, we prove that when Abreast-DM is instantiated with AES-256, i.e. a block cipher with 128-bit block length and 256-bit key length, any adversary that asks less than 2^124.42 queries cannot find a collision with success probability greater than 1/2. Surprisingly, this about 15 years old construction is one of the few constructions that have the desirable feature of a near-optimal collision resistance guarantee. We generalize our techniques used in the proof of Abreast-DM to a huge class of double block length (DBL) hash functions that we will call Cyclic-DM. Using this generalized theorem we are able to derive several DBL constructions that lead to compression functions that even have a higher security guarantee and are more efficient than Abreast-DM. Furthermore we give DBL constructions that have the highest security guarantee of all DBL compression functions currently known in literature. We also provide an analysis of preimage resistance for Cyclic-DM compression functions. Note that this work has been already presented at Dagstuhl '09.

In this paper, we compare the implementation costs of various SHA-3 candidates on low-cost 8-bit CPUs by estimating RAM/ROM requirements of them. As a first step toward this kind of research, in our comparison, we make reasonable estimations of RAM/ROM requirements of them which can be done without implementation.

We present a refined chosen-prefix collision construction for MD5 that allowed creation of a rogue Certification Authority (CA) certificate, based on a collision with a regular end-user website certificate provided by a commercial CA. Compared to the previous construction from Eurocrypt 2007, this paper describes a more °exible family of differential paths and a new variable birthdaying search space. Combined with a time-memory trade-off, these improvements lead to just three pairs of near-collision blocks to generate the collision, enabling construction of RSA moduli that are sufficiently short to be accepted by current CAs. The entire construction is fast enough to allow for adequate prediction of certificate serial number and validity period: it can be made to require about 2^{49} MD5 compression function calls. Finally, we improve the complexity of identical-prefix collisions for MD5 to about 2^{16} MD5 compression function calls and use it to derive a practical single-block chosen-prefix collision construction of which an example is given.

Datatype-Preserving Encryption (DTP) enables encryption of values within a certain character set into ciphertext restricted to the same set, while still keeping data length. This is in contrast to conventional block cipher modes which produce binary data, i e each encrypted character may have an arbitrary value, possibly outside the original character set, often accompanied with a length expansion caused by padding. Format-Controlling Encryption (FCE) is an extension to DTP, for which data length still is kept, but the output character range is allowed to be larger, though not covering the range of all possible values (i e binary data). With FCE it is possible to handle certain DTP limitations, like limited key rotation and integrity support.

SMS4 is a 32-round unbalanced Feistel block cipher with its block size and key size being 128 bits. As a fundamental block cipher used in the WAPI standard, the Chinese national standard for WLAN, it has been widely implemented in Chinese WLAN industry. In this paper, we present a modified branch-and-bound algorithm which can be used for searching multiple linear characteristics for SMS4-like unbalanced Feistel block ciphers. Furthermore, we find a series of 5-round iterative linear characteristics of SMS4 when applying the modified algorithm in SMS4. Then based on each 5-round iterative linear characteristic mentioned above, an 18-round linear characteristic of SMS4 can be constructed, thus leading to a list of 18-round linear characteristics of SMS4. According to the framework of Biryukov $et\ al.$ from Crpto 2004, a key recovery attack can be mounted on 22-round SMS4 by utilizing the above multiple linear characteristics. As a matter of fact, our result has much lower data complexity than the previously best known cryptanalytic result on 22-round SMS4, which is also the previously best known result on SMS4.

Here we present practical differential $q$-multicollisions for AES-256, which can be tested on any implementation of AES-256. In our paper "Distinguisher and Related-Key Attack on the Full AES-256" $q$-multicollisions are found with complexity $q\cdot 2^{67}$. We relax conditions on the plaintext difference $\Delta_P$ allowing some bytes to vary and find multicollisions for 13 and 14 round AES with complexity $q\cdot 2^{37}$. Even with the relaxation there is still a large complexity gap between our algorithm and the lower bound that we have proved in Lemma 1. Moreover we believe that in practice finding even two fixed-difference collisions for a good cipher would be very challenging.

Cube testers are a generic class of methods for building disstinguishers, based on cube attacks and on algebraic property-testers. In this paper, we report on an efficient FPGA implementation of cube testers on the stream cipher Grain-128. Our best result (a distinguisher on Grain-128 reduced to 237 rounds, out of 256) was achieved after a computation involving 2^54 clockings of Grain-128, with a 256×32 parallelization. An extrapolation of our results with standard methods suggests the possibility of a distinguishing attack on the full Grain-128 in time 2^83, which is well below the 2^128 complexity of exhaustive search. We also describe the method used for finding good cubes (a simple evolutionary algorithm), and report preliminary results on Grain-v1 obtained with a bitsliced C implementation.

A new construction of block cipher based tweakable enciphering schemes (TES) is described. The major improvement over existing TES is that the construction uses only the encryption function of the underlying block cipher. Consequently, this leads to substantial savings in the size of hardware implementation of TES applications such as disk encryption. This improvement is achieved without loss in efficiency of encryption and decryption compared to the best previously known schemes.

We revisit the problem of constructing a protocol for performing authenticated encryption with associated data (AEAD). A technique is described which combines a collision resistant hash function with a protocol for authenticated encryption (AE). The technique is both simple and generic and does not require any additional key material beyond that of the AE protocol. Concrete instantiations are shown where a 256-bit hash function is combined with some known single-pass AE protocols employing either 128-bit or 256-bit block ciphers. This results in possible efficiency improvement in the processing of the header.

In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to $2^0$ and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity $2^{23}$ and close to $2^0$, respectively. We implemented the attacks and provide examples of appropriate pairs of $H,M$ values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.

In this paper, we present an enhanced cryptanalysis of the Substitution Cipher Chaining mode (SCC)~\cite{scc}. In~\cite{scc_attack}, SCC-128 (SCC which uses AES with 128-bit key) was broken using 5 attacks, where the authors used an active attack model (where the attacker can force the disk encryption application to re-encrypt a sector for her), the complexity of these attacks are at most 2$^{40}$ cipher executions. In this paper, we enhance the main attack on SCC-128, this enhancement decrease the complexity of SCC-128 attacks to be at most 2$^{14}$ cipher executions. We also cryptanalze SCC-128 in a less restrictive attack model, our attacks are upper bounded with 2$^{40}$ cipher executions.

Shabal is based on a new provably secure mode of operation. Some related-key distinguishers for the underlying keyed permutation have been exhibited recently by Aumasson et al. and Knudsen et al., but with no visible impact on the security of Shabal. This paper then aims at extensively studying such distinguishers for the keyed permutation used in Shabal, and at clarifying the impact that they exert on the security of the full hash function. Most interestingly, a new security proof for Shabal's mode of operation is provided where the keyed permutation is not assumed to be an ideal cipher anymore, but observes a distinguishing property i.e., an explicit relation verified by all its inputs and outputs. As a consequence of this extended proof, all known distinguishers for the keyed permutation are proven not to weaken the security of Shabal. In our study, we provide the foundation of a generalization of the indifferentiability framework to biased random primitives, this part being of independent interest

Ring signcryption, a cryptographic primitive to protect security and privacy, is an encryption and authentication scheme in a single logical step which allows a user to anonymously signcrypt a plaintext on behalf of a group of users that decrypter cannot know who is the actual signcrypter. In 2009, Zhang, Gao, Chen and Geng proposed a novel anonymous signcryption scheme(denoted as the ZGCG scheme) which is more efficient in computational cost and ciphertext length than the related schemes. In this paper, however, we show that the ZGCG scheme has not anonymity secure for the receiver, and then we propose an improved anonymous signcryption scheme that remedies the weakness of the ZGCG scheme. Our proposed scheme satisfies the semantic security, unforgeability, signcrypter identity's ambiguity, and public authenticity. We also give the formal security proof in the random oracle model.

MiFare Classic is the most popular contactless smart card with about 200 millions copies in circulation worldwide. At Esorics 2008 Dutch researchers showed that the underlying cipher Crypto-1 can be cracked in as little as 0.1 seconds if the attacker can access or eavesdrop the RF communications with the (genuine) reader. We discovered that a MiFare classic card can be cloned in a much more practical card-only scenario, where the attacker only needs to be in the proximity of the card for a number of minutes, therefore making usurpation of identity through pass cloning feasible at any moment and under any circumstances. For example, anybody sitting next to the victim on a train or on a plane is now be able to clone his/her pass. Other researchers have also (independently from us) discovered this vulnerability, however our attack requires less queries to the card and does not require any precomputation. In addition, we discovered that certain versions or clones of MiFare Classic are even weaker, and can be cloned in 1 second. The main security vulnerability that we need to address with regard to MiFare Classic is not about cryptography, RFID protocols and software vulnerabilities. It is a systemic one: we need to understand how much our economy is vulnerable to sophisticated forms of electronic subversion where potentially one smart card developer can intentionally (or not), but quite easily in fact, compromise the security of governments, businesses and financial institutions worldwide.

A block cipher is intended to be computationally indistinguishable from a random permutation of appropriate domain and range. But what are the properties of a random permutation? By the aid of exponential and ordinary generating functions, we derive a series of collolaries of interest to the cryptographic community. These follow from the Strong Cycle Structure Theorem of permutations, and are useful in rendering rigorous two attacks on Keeloq, a block cipher in wide-spread use. These attacks formerly had heuristic approximations of their probability of success. Moreover, we delineate an attack against the (roughly) millionth-fold iteration of a random permutation. In particular, we create a distinguishing attack, whereby the iteration of a cipher a number of times equal to a particularly chosen highly-composite number is breakable, but merely one fewer round is considerably more secure. We then extend this to a key-recovery attack in a “Triple-DES” style construction, but using AES-256 and iterating the middle cipher (roughly) a million-fold. This attack is $2^{119.237}$ times faster than brute-force search. It is hoped that these results will showcase the utility of exponential and ordinary generating functions and will encourage their use in cryptanalytic research.

In this paper, we present a new tweakable narrow-block mode of operation, the Extended Substitution Cipher Chaining mode (ESCC), that can be efficiently deployed in disk encryption applications. ESCC is an extention of Substitution Cipher Chaining mode (SCC)~\cite{scc}. Unlike SCC, ESCC is resistant to the attacks in~\cite{scc_attack,scc_attack2}.

In this paper, we present a near-collision attack on the compression functions of Dynamic SHA2 for all the output sizes. For the Dynamic SHA2-224/256, the complexity is about $2^{45}$ operations and for the Dynamic SHA2-384/512, the complexity is about $2^{75}$.

Trivium is a hardware-oriented stream cipher, and one of the finally chosen ciphers by eSTREAM project. Michal Hojsik and Bohuslav Rudolf presented an effective attack to Trivium, named floating fault analysis, at INDOCRYPT 2008. Their attack makes use of the fault injection and the fault float. In this paper, we present an improvement of this attack. Our attack is under following weaker and more practical assumptions.The fault injection can be made for the state at a random time.The positions of the fault bits are from random one of 3 NFSRs, and from a random area within 8 neighboring bits.We present a checking method, by which either the injecting time and fault positions can be determined, or the state differential at a known time can be determined. Each of these two determinations is enough for floating attack. After the determination, the attacker can averagely obtain 67.167 additional linear equations from 82 original quadratic equations, and obtain 66 additional quadratic equations from 66 original cubic equations.

In this note we give an overview on the current state of the SHA-3 candidates. First, we classify all publicly known candidates and, second, we outline and summarize the performance data as given in the candidates documentation for 64-bit and 32-bit implementations. We define performance classes and classify the hash algorithms. Note, that this article will be updated as soon as new candidates arrive or new cryptanalytic results get published. Comments to the authors of this article are welcome.

We present a second pre-image attack on ECOH. Our attack requires $2^{143}$ time for ECOH-224 and ECOH-256, $2^{206}$ time for ECOH-384, and $2^{287}$ time for ECOH-512. The attack sets the checksum block to a fixed value and uses a collision search on the elliptic curve points.

The Feedback with Carry Shift Registers (FCSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for the design of stream ciphers. FCSRs have good statistical properties and they provide a built-in non-linearity. However, two attacks have shown that the current representations of FCSRs can introduce weaknesses in the cipher. We propose a new ``ring'' representation of FCSRs based upon matrix definition which generalizes the Galois and Fibonacci representations. Our approach preserves the statistical properties and circumvents the weaknesses of the Fibonacci and Galois representations. Moreover, the ring representation leads to automata with a quicker diffusion characteristic and better implementation results. As an application, we describe a new version of F-FCSR stream ciphers.

We revisit the rate-1 blockcipher based hash functions as first studied by Preneel, Govaerts and Vandewalle (Crypto'93) and later extensively analysed by Black, Rogaway and Shrimpton (Crypto'02). We analyze a further generalization where any pre- and postprocessing is considered. By introducing a new tweak to earlier proof methods, we obtain a simpler proof that is both more general and more tight than existing results. As added benefit, this also leads to a clearer understanding of the current classification of rate-1 blockcipher based schemes as introduced by Preneel et al. and refined by Black et al.

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an $n$-bit secret $W$, which might not be uniformly random, but the adversary has at least $k$ bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use $W$ to agree on a nearly uniform key $R$, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when $k < n/2$, and require poor parameters even when $n/2< k << n$. On the other hand, for arbitrary values of $k$, we design a communication efficient two-round (challenge-response) protocol extracting nearly $k$ random bits. This dramatically improves the only previously known protocol of Renner and Wolf~\cite{RennerW03}, which required $O(\lambda)$ rounds where $\lambda$ is the security parameter. Our solution takes a new approach by studying and constructing ``non-malleable'' seeded randomness extractors --- if an attacker sees a random seed $X$ and comes up with an arbitrarily related seed $X'$, then we bound the relationship between $R= \Ext(W;X)$ and $R' = \Ext(W;X')$. We also extend our two-round key agreement protocol to the ``fuzzy'' setting, where Alice and Bob share ``close'' (but not equal) secrets $W_A$ and $W_B$, and to the Bounded Retrieval Model (BRM) where the size of the secret $W$ is huge.

A cryptographer with week algorithm get his feedback almost instantly by the open crypto community. But what about government cryptanalysis ? Given the fact that there is a considerable amount of cryptanalysis behind closed doors, what is to be done to get COMINT deaf ? The NSA, as the most closely examined SIGINT agency, has a workforce of 38,000 [2], among them several thousand cryptologist. The actual wiretapping is done by the Central Security Service with 25,000 women and men. Other industrialised states have also thousands cryptologist at their wage role. The block cipher 1024 is an attempt to make cryptanalysis more difficult especially with differential (DC) and linear cryptanalysis. The assumption is that the increased security will defeat other cryptanalytical not yet known by the open crypto community. 1024 has a block size of 1024 bits and a key length of 2048 bits.

This paper proposed a first order recursive construction of Boolean function with optimum algebraic immunity. We also show that the Boolean functions are balanced and have good algebraic degrees.

At IEEE GLOBECOM 2008, a lightweight cipher based on a Multiple Recursive Generator (MRG) was proposed for use in resource limited environment such as sensor nodes and RFID tags. This paper proposes two efficient attacks on this MRG cipher. A distinguishing attack is firstly introduced to identify the use of an MRG cipher that has a modulus suggested by its designers. It requires $2^{18}$ words of ciphertext and the most significant bit of each corresponding plaintext word. Then an efficient known plaintext attack is proposed to construct the cipher's current state and generate subkeys used for all subsequent encryption. The known plaintext attack, when targeted at the MRG ciphers optimized for efficiency, only requires 2k words of known plaintext and trivial computation where k is the MRG order. Even the ciphers based on complicated and inefficient MRGs can be attacked with low complexity, e.g., in the magnitude of $2^{12}$ words of known plaintext for all MRG ciphers with order 47, regardless of which MRG modulus is used. These two attacks indicate that the examined MRG cipher structure is seriously flawed.

In this paper we formalize the notion of {\it leakage attacks} on iterated block ciphers, in which the attacker can find (via physical probing, power measurement, or any other type of side channel) one bit of information about the intermediate state of the encryption after each round. Since bits computed during the early rounds can be typically represented by low degree multivariate polynomials, cube attacks seem to be an ideal generic key recovery technique in these situations. However, the original cube attack requires extremely clean data, whereas the information provided by side channel attacks can be quite noisy. To address this problem, we develop a new variant of cube attack which can tolerate considerable levels of noise (affecting more than 11\% of the leaked bits in practical scenarios). Finally, we demonstrate our approach by describing efficient leakage attacks on two of the best known block ciphers, AES (requiring about $2^{35}$ time for full key recovery) and SERPENT (requiring about $2^{18}$ time for full key recovery).

In this note, we present a full key recovery attack on HMAC-AURORA-512 when 512-bit secret keys are used and the MAC length is 512-bit long. Our attack requires $2^{257}$ queries and the off-line complexity is $2^{259}$ AURORA-512 operations, which is significantly less than the complexity of the exhaustive search for a 512-bit key. The attack can be carried out with a negligible amount of memory. Our attack can also recover the inner-key of HMAC-AURORA-384 with almost the same complexity as in HMAC-AURORA-512. This attack does not recover the outer-key of HMAC-AURORA-384, but universal forgery is possible by combining the inner-key recovery and 2nd-preimage attacks. Our attack exploits some weaknesses in the mode of operation.

The $r$-th order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code $\mathcal{R}(r, n)$. In this paper we deduce the lower bounds of the second order nonlinearity of the two classes of Boolean functions of the form \begin{enumerate} \item $f_{\lambda}(x) = Tr_1^n(\lambda x^{d})$ with $d=2^{2r}+2^{r}+1$ and $\lambda \in \mathbb{F}_{2^{n}}$ where $n = 6r$. \item $f(x,y)=Tr_1^t(xy^{2^{i}+1})$ where $x,y \in \mathbb{F}_{2^{t}}, n = 2t, n \ge 6$ and $i$ is an integer such that $1\le i < t$, $\gcd(2^t-1, 2^i+1) = 1$. \end{enumerate} For some $\lambda$, the first class gives bent functions whereas Boolean functions of the second class are all bent, i.e., they achieve optimum first order nonlinearity.