Fast Software Encryption

IDEA is a 64-bit block cipher with a 128-bit key designed by J. Massey and X. Lai. At FSE 2002 a slightly modified version called IDEA-X was attacked using multiplicative differentials. In this paper we present a less modified version of IDEA we call IDEA-X/2, and an attack on this cipher. This attack also works on IDEA-X, and improves on the attack presented at FSE 2002.

Serpent is a 128-bit SP-Network block cipher consisting of 32 rounds with variable key length (up to 256 bits long). It was selected as one of the 5 AES finalists. The best known attack so far is a linear attack on an 11-round reduced variant.

In this paper we apply the enhanced differential-linear cryptanalysis to Serpent. The resulting attack is the best known attack on 11-round Serpent. It requires 2^125.3 chosen plaintexts and has time complexity of 2^139.2. We also present the first known attack on 10-round 128-bit key Serpent. These attacks demonstrate the strength of the enhanced differential-linear cryptanalysis technique.

SHACAL-1 is a 160-bit block cipher with variable key length of up to 512-bit key based on the hash function SHA-1. It was submitted to the NESSIE project and was accepted as a finalist for the 2nd phase of the evaluation. In this paper we present rectangle attacks on 49 rounds out of the 80 rounds of SHACAL-1. The attacks require 2^151.9 chosen plaintexts or ciphertexts and have time complexity of 2^508.5 49-round SHACAL-1 encryptions. These are the best known attacks against SHACAL-1. In this paper we also identify and fix some flaws in previous attacks on SHACAL-1.

We cryptanalyse some block cipher proposals that are based on dedicated hash functions SHA-1 and MD5. We discuss a related-key attack against SHACAL-1 and present a method for finding ”slid pairs” for it. We also present simple attacks against MDC-MD5 and the Kaliski-Robshaw block cipher.

In this paper we study structural properties of SPN ciphers in which both the S-boxes and the affine layers are involutions. We apply our observations to the recently designed Rijndael-like ciphers Khazad and Anubis, and show several interesting properties of these ciphers. We also show that 5-round Khazad has 2⁶⁴ weak keys under a ”slide-with-a-twist” attack distinguisher. This is the first cryptanalytic result which is better than exhaustive search for 5-round Khazad. Analysis presented in this paper is generic and applies to a large class of ciphers built from involutional components.

We use the notion of covering sequence, introduced by C. Carlet and Y. Tarannikov, to give a simple characterization of bent functions. We extend it into a characterization of plateaued functions (that is bent and three-valued functions). After recalling why the class of plateaued functions provides good candidates to be used in cryptosystems, we study the known families of plateaued functions and their drawbacks. We show in particular that the class given as new by Zhang and Zheng is in fact a subclass of Maiorana-McFarland’s class. We introduce a new class of plateaued functions and prove its good cryptographic properties.

This paper reports the discovery of linear redundancy in the S-boxes of many ciphers recently proposed for standardisation (including Rijndael, the new AES). We introduce a new method to efficiently detect affine equivalence of Boolean functions, and hence we study the variety of equivalence classes existing in random and published S-boxes. This leads us to propose a new randomness criterion for these components. We present experimental data supporting the notion that linear redundancy is very rare in S-boxes with more than 6 inputs. Finally we discuss the impact this property may have on implementations, review the potential for new cryptanalytic attacks, and propose a new tweak for block ciphers that removes the redundancy. We also provide details of a highly nonlinear 8*8 non-redundant bijective S-box, which is suitable as a plug in replacement where required.

In this paper, we present differential attacks on the self-synchronizing stream cipher KNOT. Our best attack recovers 96 bits of the secret key with time complexity of 2⁶² and requires 2⁴⁰ chosen ciphertext bits.

The resynchronization attack on stream ciphers with a linear next-state function and a nonlinear output function is further investigated. The number of initialization vectors required for the secret key reconstruction when the output function is known is studied in more detail and a connection with the so-called 0-order linear structures of the output function is established. A more difficult problem when the output function is unknown is also considered. An efficient branching algorithm for reconstructing this function along with the secret key is proposed and analyzed. The number of initialization vectors required is larger in this case than when the output function is known, and the larger the number, the lower the complexity.

Sober-t32 is a candidate stream cipher in the NESSIE competition. Some new attacks are presented in this paper. A Guess and Determine attack is mounted against Sober-t32 without the decimation of the key stream by the so-called stuttering phase. Also, two distinguishing attacks are mounted against full Sober-t32. These attacks are not practically feasible, but they are theoretically more efficient than exhaustive key search.

In this paper, we present One-key CBC MAC (OMAC) and prove its security for arbitrary length messages. OMAC takes only one key, K (k bits) of a block cipher E. Previously, XCBC requires three keys, (k+2n) bits in total, and TMAC requires two keys, (k+n) bits in total, where n denotes the block length of E.

The saving of the key length makes the security proof of OMAC substantially harder than those of XCBC and TMAC.

The standardized integrity algorithm f9 of the 3GPP algorithm computes a MAC (Message Authentication Code) to establish the integrity and the data origin of the signalling data over a radio access link of W-CDMA IMT-2000. The function f9 is based on the block cipher KASUMI and it can be considered as a variant of CBC-MAC. In this paper we examine the provable security of f9. We prove that f9 is a secure pseudorandom function by giving a concrete bound on an adversary’s inability to forge a MAC value in terms of her inability to distinguish the underlying block cipher from a random permutation.

In this paper, we revisit the security of several message authentication code (MAC) algorithms based on block ciphers, when instantiated with 64-bit block ciphers such as DES. We essentially focus on algorithms that were proposed in the norm ISO/IEC 9797–1. We consider both forgery attacks and key recovery attacks. Our results improve upon the previously known attacks and show that all algorithms but one proposed in this norm can be broken by obtaining at most about 2³³ MACs of chosen messages and performing an exhaustive search of the same order as the search for a single DES key.

In this paper the newly proposed RMAC system is analysed. The scheme allows a (traditional MAC) attack some control over one of two keys of the underlying block cipher and makes it possible to mount several related-key attacks on RMAC. First, an efficient attack on RMAC when used with triple-DES is presented, which rely also on other findings in the proposed draft standard. Second, a generic attack on RMAC is presented which can be used to find one of the two keys in the system faster than by an exhaustive search. Third, related-key attacks on RMAC in a multi-user setting are presented. In addition to beating the claimed security bounds in NIST’s RMAC proposal, this work suggests that, as a general principle, one may wish to avoid designing modes of operation that use related keys.

Differential Power Analysis (DPA) on smart-cards was introduced by Paul Kocher [11] in 1998. Since, many countermeasures have been introduced to protect cryptographic algorithms from DPA attacks. Unfortunately these features are known not to be efficient against high order DPA (even of second order). In these paper we will first describe new specialized first order attack and remind how are working high order DPA attacks. Then we will show how these attacks can be applied to two usual actual countermeasures. Eventually we will present a method of protection (and apply it to the DES) which seems to be secure against any order DPA type attacks. The figures of a real implementation of this method will be given too.

Until now in cryptography the term collision was mainly associated with the surjective mapping of different inputs to an equal output of a hash function. Previous collision attacks were only able to detect collisions at the output of a particular function. In this publication we introduce a new class of attacks which originates from Hans Dobbertin and is based on the fact that side channel analysis can be used to detect internal collisions. We applied our attack against the widely used Data Encryption Standard (DES). We exploit the fact that internal collisions can be caused in three adjacent S-Boxes of DES [DDQ84] in order to gain information about the secret key-bits. As result, we were able to exploit an internal collision with a minimum of 140 encryptions yielding 10.2 key-bits. Moreover, we successfully applied the attack to a smart card processor.

We present our further observations on the structure of the AES algorithm relating to the cyclic properties of the functions used in this cipher. We note that the maximal period of the linear layer of the AES algorithm is short, as previously observed by S. Murphy and M.J.B. Robshaw. However, we also note that when the non-linear and the linear layer are combined, the maximal period is dramatically increased not to allow algebraic clues for its cryptanalysis. At the end of this paper we describe the impact of our observations on the security of the AES algorithm. We conclude that although the AES algorithm consists of simple functions, this cipher is much more complicated than might have been expected.

Hypothesis tests have been used in the past as a tool in a cryptanalytic context. In this paper, we propose to use this paradigm and define a precise and sound statistical framework in order to optimally mix information on independent attacked subkey bits obtained from any kind of statistical cryptanalysis. In the context of linear cryptanalysis, we prove that the best mixing paradigm consists of sorting key candidates by decreasing weighted Euclidean norm of the bias vector.

We present a new method for upper bounding the maximum differential probability and the maximum linear hull probability for 2 rounds of SPN structures. Our upper bound can be computed for any value of the branch number of the linear transformation and by incorporating the distribution of differential probability values and linear probability values for S-box. On application to AES, we obtain that the maximum differential probability and the maximum linear hull probability for 4 rounds of AES are bounded by 1.144 × 2^− 111 and 1.075 × 2^− 106, respectively.

We present an in-depth algorithmic study of the linear approximations of addition modulo 2 ⁿ . Our results are based on a fairly simple classification of the linear approximations of the carry function. Using this classification, we derive an Θ(logn)-time algorithm for computing the correlation of linear approximation of addition modulo 2 ⁿ , an optimal algorithm for generating all linear approximations with a given non-zero correlation coefficient, and determine the distribution of the correlation coefficients. In the generation algorithms, one or two of the selection vectors can optionally be fixed. The algorithms are practical and easy to implement.

In this paper we compare systems of multivariate polynomials, which completely define the block ciphers Khazad, Misty1, Kasumi, Camellia, Rijndael and Serpent in the view of a potential danger of an algebraic re-linearization attack.

This paper proposes the Turing stream cipher. Turing offers up to 256-bit key strength, and is designed for extremely efficient software implementation.It combines an LFSR generator based on that of SOBER [21] with a keyed mixing function reminiscent of a block cipher round. Aspects of the block mixer round have been derived from Rijndael [6], Twofish [23], tc24 [24] and SAFER++ [17].

We present a new stream cipher, Rabbit, based on iterating a set of coupled non-linear functions. Rabbit is characterized by a high performance in software with a measured encryption/decryption speed of 3.7 clock cycles per byte on a Pentium III processor. We have performed detailed security analysis, in particular, correlation analysis and algebraic investigations. The cryptanalysis of Rabbit did not reveal an attack better than exhaustive key search.

Helix is a high-speed stream cipher with a built-in MAC functionality. On a Pentium II CPU it is about twice as fast as Rijndael or Twofish, and comparable in speed to RC4. The overhead per encrypted/authenticated message is low, making it suitable for small messages. It is efficient in both hardware and software, and with some pre-computation can effectively switch keys on a per-message basis without additional overhead.

In this paper, we design a new hash function PARSHA-256. PARSHA-256 uses the compression function of SHA-256 along with the Sarkar-Schellenberg composition principle. As a consequence, PARSHA-256 is collision resistant if the compression function of SHA-256 is collision resistant. On the other hand, PARSHA-256 can be implemented using a binary tree of processors, resulting in a significant speed-up over SHA-256. We also show that PARSHA-256 can be efficiently implemented through concurrent programming on a single processor machine using a multithreaded approach. Experimental results on P4 running Linux show that for long messages the multithreaded implementation is faster than SHA-256.

This paper addresses the security of symmetric cryptosystems in the blockwise adversarial model. At Crypto 2002, Joux, Martinet and Valette have proposed a new kind of attackers against several symmetric encryption schemes. In this paper, we first show a generic technique to thwart blockwise adversaries for a specific class of encryption schemes. It consists in delaying the output of the ciphertext block. Then we provide the first security proof for the CFB encryption scheme, which is naturally immune against such attackers.

In this paper, we investigate the security, in the Luby-Rackoff security paradigm, of blockcipher modes of operation allowing to expand a one-block input into a longer t-block output under the control of a secret key K. Such ”one-block-to-many” modes of operation are of frequent use in cryptology. They can be used for stream cipher encryption purposes, and for authentication and key distribution purposes in contexts such as mobile communications. We show that although the expansion functions resulting from modes of operation of blockciphers such as the counter mode or the output feedback mode are not pseudorandom, slight modifications of these two modes provide pseudorandom expansion functions. The main result of this paper is a detailed proof, in the Luby-Rackoff security model, that the expansion function used in the construction of the third generation mobile (UMTS) example authentication and key agreement algorithm MILENAGE is pseudorandom.