Fast Software Encryption

We present several attacks against the Achterbahn stream cipher, which was proposed to the eSTREAM competition. We can break the reduced and the full version with complexity of 2⁵⁵ and 2⁶¹ steps.

Extensions of our attacks are also described to break modified versions of the Achterbahn stream cipher, which were proposed following the publication of preliminary cryptanalysis results.

Grain [11] is a lightweight stream cipher proposed by M. Hell, T. Johansson, and W. Meier to the eSTREAM call for stream cipher proposals of the European project ECRYPT [5]. Its 160-bit internal state is divided into a LFSR and an NFSR of length 80 bits each. A filtering boolean function is used to derive each keystream bit from the internal state. By combining linear approximations of the feedback function of the NFSR and of the filtering function, it is possible to derive linear approximation equations involving the keystream and the LFSR initial state. We present a key recovery attack against Grain which requires 2⁴³ computations and 2³⁸ keystream bits to determine the 80-bit key.

DECIM is a hardware oriented stream cipher with an 80-bit key and a 64-bit IV. In this paper, we point out two serious flaws in DECIM. One flaw is in the initialization of DECIM. It allows to recover about half of the key bits bit-by-bit when one key is used with about 2²⁰ random IVs; only the first two bytes of each keystream are needed in the attack. The amount of computation required in the attack is negligible. Another flaw is in the keystream generation algorithm of DECIM. The keystream is heavily biased: any two adjacent keystream bits are equal with probability about \({1 \over 2}+2^{-9}\). A message could be recovered from the ciphertext if that message is encrypted by DECIM for about 2¹⁸ times. DECIM with an 80-bit key and an 80-bit IV is also vulnerable to these attacks.

We study a recently proposed design approach of Feistel structure which employs diffusion matrices in a switching way. At ASIACRYPT 2004, Shirai and Preneel have proved that large numbers of S-boxes are guaranteed to be active if a diffusion matrix used in a round function is selected among multiple matrices. However the optimality of matrices required by the proofs sometimes pose restriction to find matrices suitable for actual blockciphers. In this paper, we extend their theory by replacing the condition of optimal mappings with general-type mappings, consequently the restriction is eliminated. Moreover, by combining known lower bounds for usual Feistel structure, we establish a method to estimate the guaranteed number of active S-boxes for arbitrary round numbers. We also demonstrate how the generalization enables us to mount wide variety of diffusion mappings by showing concrete examples.

We propose a general framework for differential and linear cryptanalysis of block ciphers when the block is not a bitstring. We prove piling-up lemmas for the generalized differential probability and the linear potential, and we study their lower bounds and average value, in particular in the case of permutations of \({\mathbb{F}_p}\). Using this framework, we describe a toy cipher, that operates on blocks of 32 decimal digits, and study its security against common attacks.

We demonstrate an efficient method for computing a Gröbner basis of a zero-dimensional ideal describing the key-recovery problem from a single plaintext/ciphertext pair for the full AES-128. This Gröbner basis is relative to a degree-lexicographical order. We investigate whether the existence of this Gröbner basis has any security implications for the AES.

HAVAL is a cryptographic hash function with variable digest size proposed by Zheng, Pieprzyk and Seberry in 1992. It has three variants, 3-, 4-, and 5-pass HAVAL. Previous results on HAVAL suggested only practical collision attacks for 3-pass HAVAL. In this paper, we present collision attacks for 4 and 5 pass HAVAL. For 4-pass HAVAL, we describe two practical attacks for finding 2-block collisions, one with 2⁴³ computations and the other with 2³⁶ computations. In addition, we show that collisions for 5-pass HAVAL can be found with about 2¹²³ computations, which is the first attack more efficient than the birthday attack.

We describe a collision-finding attack on 16 rounds of the Tiger hash function requiring the time for about 2⁴⁴ compression function invocations. This extends to a collision-finding attack on 17 rounds of the Tiger hash function in time of about 2⁴⁹ compression function invocations. Another attack generates circular near-collisions, for 20 rounds of Tiger with work less than that of 2⁴⁹ compression function invocations. Since Tiger has only 24 rounds, these attacks may raise some questions about the security of Tiger. In developing these attacks, we adapt the ideas of message modification attacks and neutral bits, developed in the analysis of MD4 family hashes, to a completely different hash function design.

In this paper we present new and more accurate estimates of the biases of the linear approximation of the FSM of the stream cipher SNOW 2.0. Based on improved bias estimates we also find a new linear distinguisher with bias 2^{− − 86.9} that is significantly stronger than the previously found ones by Watanabe et al. (2003) and makes it possible to distinguish the output keystream of SNOW 2.0 of length 2¹⁷⁴ words from a truly random sequence with workload 2¹⁷⁴. This attack is also stronger than the recent distinguishing attack by Maximov and Johansson (2005). We also investigate the diffusion properties of the MixColumn transformation used in the FSM of SNOW 2.0 and present some evidence why much more efficient distinguishers may not exist.

The main application of stream ciphers is online-encryption of arbitrarily long data, for example when transmitting speech data between a Bluetooth headset and a mobile GSM phone or between the phone and a GSM base station. Many practically used and intensively discussed stream ciphers such as the E ₀ generator used in Bluetooth and the GSM cipher A5/1 consist of a small number of linear feedback shift registers (LFSRs) that transform a secret key x∈{0,1} ⁿ into an output keystream of arbitrary length. In 2002, Krause proposed a Binary Decision Diagram (BDD) based attack on this type of ciphers, which in the case of E ₀ is the best short-keystream attack known so far. However, BDD-attacks generally require a large amount of memory. In this paper, we show how to substantially reduce the memory consumption by divide-and-conquer strategies and present the first comprehensive experimental results for the BDD-attack on reduced versions of E ₀, A5/1 and the self-shrinking generator.

The security of hash functions has recently become one of the hottest topics in the design and analysis of cryptographic primitives. Since almost all the hash functions used today (including the MD and SHA families) have an iterated design, it is important to study the general security properties of such functions. At Crypto 2004 Joux showed that in any iterated hash function it is relatively easy to find exponential sized multicollisions, and thus the concatenation of several hash functions does not increase their security. However, in his proof it was essential that each message block is used at most once. In 2005 Nandi and Stinson extended the technique to handle iterated hash functions in which each message block is used at most twice. In this paper we consider the general case and prove that even if we allow each iterated hash function to scan the input multiple times in an arbitrary expanded order, their concatenation is not stronger than a single function. Finally, we extend the result to tree-based hash functions with arbitrary tree structures.

This paper describes a new software-efficient 256-bit hash function, FORK-256. Recently proposed attacks on MD5 and SHA-1 motivate a new hash function design. It is designed not only to have higher security but also to be faster than SHA-256. The performance of the new hash function is at least 30% better than that of SHA-256 in software. And it is secure against any known cryptographic attacks on hash functions.

In this article, it is discussed how to construct a compression function with 2 n-bit output using a component function with n-bit output. The component function is either a smaller compression function or a block cipher. Some constructions are presented which compose collision-resistant hash functions: Any collision-finding attack on them is at most as efficient as the birthday attack in the random oracle model or in the ideal cipher model. A new security notion is also introduced, which we call indistinguishability in the iteration, with a construction satisfying the notion.

We propose message authentication codes (MACs) that combine a block cipher and an additional (keyed or unkeyed) permutation. Our MACs are provably secure if the block cipher is pseudorandom and the additional permutation has a small differential probability. We also demonstrate that our MACs are easily implemented with AES and its 4-round version to obtain MACs that are provably secure and 1.4 to 2.5 times faster than the previous MAC modes of AES such as the CBC-MAC-AES.

The ground-breaking results of Wang et al. have attracted a lot of attention to the collision resistance of hash functions. In their articles, Wang et al. give input differences, differential paths and the corresponding conditions that allow to find collisions with a high probability. However, Wang et al. do not explain how these paths were found. The common assumption is that they were found by hand with a great deal of intuition.

In this article, we present an algorithm that allows to find paths in an automated way. Our algorithm is successful for MD4. We have found over 1000 differential paths so far. Amongst them, there are paths that have fewer conditions in the second round than the path of Wang et al. for MD4. This makes them better suited for the message modification techniques that were also introduced by Wang et al.

MD5 is a well-known and widely-used cryptographic hash function. It has received renewed attention from researchers subsequent to the recent announcement of collisions found by Wang et al. [16]. To date, however, the method used by researchers in this work has been fairly difficult to grasp.

In this paper we conduct a study of all attacks on MD5 starting from Wang. We explain the techniques used by her team, give insights on how to improve these techniques, and use these insights to produce an even faster attack on MD5. Additionally, we provide an “MD5 Toolkit” implementing these improvements that we hope will serve as an open-source platform for further research.

Our hope is that a better understanding of these attacks will lead to a better understanding of our current collection of hash functions, what their strengths and weaknesses are, and where we should direct future efforts in order to produce even stronger primitives.

In this article we present a detailed analysis of the impact of carries on the estimation of the attack complexity for SHA-1. We build up on existing estimates and refine them. We show that the attack complexity is slightly lower than estimated in all published work to date. We point out that it is more accurate to consider probabilities instead of conditions.

We present PEP, which is a new construction of a tweakable strong pseudo-random permutation. PEP uses a hash-encrypt-hash approach which has been recently used in the construction of HCTR. This approach is different from the encrypt-mask-encrypt approach of constructions such as CMC, EME and EME^*. The general hash-encrypt-hash approach was earlier used by Naor-Reingold to provide a generic construction technique for an SPRP (but not a tweakable SPRP). PEP can be seen as the development of the Naor-Reingold approach into a fully specified mode of operation with a concrete security reduction for a tweakable strong pseudo-random permutation. HCTR is also based on the Naor-Reingold approach but its security bound is weaker than PEP. Compared to previous known constructions, PEP is the only known construction of tweakable SPRP which uses a single key, is efficiently parallelizable and can handle an arbitrary number of blocks.

In this paper, we define and analyze a new blockcipher mode of operation for encryption, CENC, which stands for Cipher-based ENCryption. CENC has the following advantages: (1) beyond the birthday bound security, (2) security proofs with the standard PRP assumption, (3) highly efficient, (4) single blockcipher key, (5) fully parallelizable, (6) allows precomputation of keystream, and (7) allows random access. CENC is based on the new construction of “from PRPs to PRF conversion,” which is of independent interest. Based on CENC and a universal hash-based MAC (Wegman-Carter MAC), we also define a new authenticated-encryption with associated-data scheme, CHM, which stands for CENC with Hash-based MAC. The security of CHM is also beyond the birthday bound.

The Ideal-Cipher Model of a blockcipher is a well-known and widely-used model dating back to Shannon [25] and has seen frequent use in proving the security of various cryptographic objects and protocols. But very little discussion has transpired regarding the meaning of proofs conducted in this model or regarding the model’s validity. In this paper, we briefly discuss the implications of proofs done in the ideal-cipher model, then show some limitations of the model analogous to recent work regarding the Random-Oracle Model [2]. In particular, we extend work by Canetti, Goldreich and Halevi [5], and a recent simplification by Maurer, Renner, and Holenstein [15], to exhibit a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher.

This paper studies the state-of-the-art software optimization methodology for symmetric cryptographic primitives on the new 64-bit x64 processors, AMD Athlon64 (AMD64) and Intel Pentium 4 (EM64T). We fully utilize newly introduced 64-bit registers and instructions for extracting maximal performance of target primitives. Our program of AES with 128-bit key runs in 170 cycles/block on Athlon 64, which is, as far as we know, the fastest implementation of AES on a PC processor.

The purpose of algebraic attacks on stream and block ciphers is to recover the secret key by solving an overdefined system of multivariate algebraic equations. They become very efficient if this system is of low degree. In particular, they have been used to break stream ciphers immune to all previously known attacks. This kind of attack tends to work when certain Boolean functions used in the ciphering process have either low degree annihilators or low degree multiples. It is therefore important to be able to check this criterion for Boolean functions. We provide in this article an algorithm of complexity \(O \left( m^d\right)\) (for fixed d) which is able to prove that a given Boolean function in m variables has no annihilator nor multiple of degree less than or equal to d. This complexity is essentially optimal. We also provide a more practical algorithm for the same task, which we believe to have the same complexity. This last algorithm is also able to output a basis of annihilators or multiples when they exist.

Algebraic attacks have received a lot of attention in studying security of symmetric ciphers. The function used in a symmetric cipher should have high algebraic immunity (\({\cal AI}\)) to resist algebraic attacks. In this paper we are interested in finding \({\cal AI}\) of Boolean power functions. We give an upper bound on the \({\cal AI}\) of any Boolean power function and a formula to find its corresponding low degree multiples. We prove that the upper bound on the \({\cal AI}\) for Boolean power functions with Inverse, Kasami and Niho exponents are \(\lfloor \sqrt{n}\rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil -2\), \(\lfloor \sqrt{n} \rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil\) and \(\lfloor \sqrt{n} \rfloor + \lceil \frac{n}{\lfloor \sqrt{n} \rfloor}\rceil\) respectively. We also generalize this idea to Boolean polynomial functions. All existing algorithms to determine \({\cal AI}\) and corresponding low degree multiples become too complex if the function has more than 25 variables. In our approach no algorithm is required. The \({\cal AI}\) and low degree multiples can be obtained directly from the given formula.

Self-Synchronizing Stream Ciphers (SSSC) are a particular class of symmetric encryption algorithms, such that the resynchronization is automatic, in case of error during the transmission of the ciphertext.

In this paper, we extend the scope of chosen-ciphertext attacks against SSSC. Previous work in this area include the cryptanalysis of dedicated constructions, like KNOT, HBB or SSS. We go further to break the last standing dedicated design of SSSC, i.e. the ECRYPT proposal MOSQUITO. Our attack costs about 2⁷⁰ computation steps, while a 96-bit security level was expected. It also applies to ΓΥ (an ancestor of MOSQUITO) therefore the only secure remaining SSSC are block-cipher-based constructions.

The stream cipher Py designed by Biham and Seberry is a submission to the ECRYPT stream cipher competition. The cipher is based on two large arrays (one is 256 bytes and the other is 1040 bytes) and it is designed for high speed software applications (Py is more than 2.5 times faster than the RC4 on Pentium III). The paper shows a statistical bias in the distribution of its output-words at the 1st and 3rd rounds. Exploiting this weakness, a distinguisher with advantage greater than 50% is constructed that requires 2^84.7 randomly chosen key/IV’s and the first 24 output bytes for each key. The running time and the data required by the distinguisher are t ₂ ^84.7 and 2^89.2 respectively (t denotes the running time of the key/IV setup). We further show that the data requirement can be reduced by a factor of about 3 with a distinguisher that considers outputs of later rounds. In such case the running time is reduced to t2^84.7 (t denotes the time for a single round of Py). The Py specification allows a 256-bit key and a keystream of 2⁶⁴ bytes per key/IV. As an ideally secure stream cipher with the above specifications should be able to resist the attacks described before, our results constitute an academic break of Py. In addition we have identified several biases among pairs of bits; it seems possible to combine all the biases to build more efficient distinguishers.

WG and LEX are two stream ciphers submitted to eStream – the ECRYPT stream cipher project. In this paper, we point out security flaws in the resynchronization of these two ciphers. The resynchronization of WG is vulnerable to a differential attack. For WG with 80-bit key and 80-bit IV, 48 bits of the secret key can be recovered with about 2^31.3 chosen IVs . For each chosen IV, only the first four keystream bits are needed in the attack. The resynchronization of LEX is vulnerable to a slide attack. If a key is used with about 2^60.8 random IVs, and 20,000 keystream bytes are generated from each IV, then the key of the strong version of LEX could be recovered easily with a slide attack. The resynchronization attack on WG and LEX shows that block cipher related attacks are powerful in analyzing non-linear resynchronization mechanisms.