We revisit the randomized approach followed in the design of the RMAC message authentication code in order to construct a MAC with similar properties, but based on Wegman-Carter's $\varepsilon$-universal hash families instead of a classical CBC chain. This yields a new message authentication code called FRMAC whose security bounds are, as in RMAC, beyond the birthday paradox limit. With efficient hash functions in software, the performance of FRMAC for large messages is similar to those of the fastest previously known schemes. FRMAC can also be more efficient for small messages. Furthermore, due to relaxed requirements about the nonces in the security proof, the implementation of FRMAC in real applications tends to be easier.

We consider the scenario where Alice wants to send a secret(classical) $n$-bit message to Bob using a classical key, and where only one-way transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then $n$. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns $n$ bits of information on the key in a known plaintext attack. We also show that there is a limit to how different the classical and quantum cases can be: the most probable key, given matching plain- and ciphertexts, has the same probability in both the quantum and the classical cases. We suggest an application of our results in the case where only a short secret key is available and the message is much longer.

Recently an algorithmic schema was proposed for converting any existing block cipher into one which excepts variable length inputs with the computational workload increasing in proportion to the block size. The resulting cipher is referred to as an elastic block cipher. The initial work presented immunity to certain key recovery attacks, and left open further analysis of the method and its possible instantiations. In order to provide a concrete example of an elastic block cipher, we design and implement an elastic version of the Advanced Encryption Standard (AES) cipher which accepts all block sizes in the range 128 to 255 bits. To validate the design we perform differential cryptanalysis on elastic AES which confirms that the cipher does not introduce potential differential attacks as a result of a subset of bits being omitted from each round (which is at the heart of the elastic design). We also compare the performance of software implementations of elastic AES and regular AES on variable size inputs, as a step in determining the practicality of the elastic version.

We introduce the new concept of elastic block ciphers, symmetric-key encryption algorithms that (1) for a variable-size input do not expand the plaintext (i.e., do not require plaintext padding) and (2) adjust their computational load proportionally to the size increase. Contrary to stream ciphers, elastic block ciphers maintain the diffusion property and non-synchronicity of traditional block ciphers. Elastic block ciphers are ideal (when combined with encryption modes) for applications where length-preserving encryption is most beneficial, such as protecting variable-length database fields or network packets. We present a general algorithm for converting a traditional block cipher, such as AES, to its elastic version, and analyze the security of the resulting cipher against key recovery attacks. Our approach allows us to ``stretch'' the supported block size of a block cipher up to twice the original length, while increasing the computational load proportionally to the expanded block size. Our approach does not allow us to use the original cipher as a ``black box'' (i.e., as an ideal cipher or a pseudorandom permutation as is used in constructing modes of encryption). Nevertheless, under some reasonable conditions on the cipher's structure and its key schedule, we reduce certain key recovery attacks of the elastic version to such attacks on the fixed-size block cipher. This schema and the security reduction enable us to capitalize on secure ciphers and their already established security properties in developing elastic designs. We note that we are not aware of previous ``reduction type'' proofs of security in the area of concrete (i.e., non ``black-box'') block cipher design. Our work puts forth the notion of elasticity in block cipher design.

The class of Rotation Symmetric Boolean Functions (RSBFs) has received serious attention recently in searching functions of cryptographic significance. These functions are invariant under circular translation of indices. In this paper we study such functions on odd number of variables and interesting combinatorial properties related to Walsh spectra of such functions are revealed. In particular we concentrate on plateaued functions (functions with three valued Walsh spectra) in this class and derive necessary conditions for existence of balanced rotation symmetric plateaued functions. As application of our result we show the non existence of 9-variable, 3-resilient RSBF with nonlinearity 240 that has been posed as an open question in FSE 2004. Further we show how one can make efficient search in the space of RSBFs based on our theoretical results and as example we complete the search for unbalanced 9-variable, 3rd order correlation immune plateaued RSBFs with nonlinearity 240.

In this paper we find two near-collisions of the full compression function of SHA-0, in which up to 142 of the 160 bits of the output are equal. We also find many full collisions of 65-round reduced SHA-0, which is a large improvement to the best previous result of 35 rounds. We use the very surprising fact that the messages have many neutral bits, some of which do not affect the differences for about 15--20 rounds. We also show that 82-round SHA-0 is much weaker than the (80-round) SHA-0, although it has more rounds. This fact demonstrates that the strength of SHA-0 is not monotonous in the number of rounds.

This work describes a mode of operation, EME*, that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. Specifically, the resulting scheme can handle any bit-length, not shorter than the block size of the underlying cipher, and it also handles associated data of arbitrary bit-length. Such a scheme can either be used directly in applications that need encryption but cannot afford length expansion, or serve as a convenient building block for higher-level modes. The mode EME* is a refinement of the EME mode of Halevi and Rogaway, and it inherits the efficiency and parallelism from the original EME.

Recently, Courtois and Pieprzyk proposed an attack on symmetric ciphers that takes advantage of a previously-unexploited property of substitution boxes, or s-boxes, in the round function. This paper gives a brief overview of this ``overdefined system of equations'' attack and shows how the attack may be avoided through the use of round functions that contain a variety of protection mechanisms, including combinations of operators from different algebraic groups, a circular rotation step, and substitution boxes (s-boxes) of large dimension.

A general method to secure cryptographic algorithm implementations against side-channel attacks is the use of randomization techniques and, in particular, masking. Roughly speaking, using random values unknown to an adversary one masks the input to a cryptographic algorithm. As a result, the intermediate results in the algorithm computation are uncorrelated to the input and the adversary cannot obtain any useful information from the side-channel. Unfortunately, previous AES randomization techniques have based their security on heuristics and experiments. Thus, flaws have been found which make AES randomized implementations still vulnerable to side-channel cryptanalysis. In this paper, we provide a formal notion of security for randomized maskings of arbitrary cryptographic algorithms. Furthermore, we present an AES randomization technique that is provably secure against side-channel attacks if the adversary is able to access a single intermediate result. Our randomized masking technique is quite general and it can be applied to arbitrary algorithms using only arithmetic operations over some even characteristic finite field. We notice that to our knowledge this is the first time that a randomization technique for the AES has been proven secure in a formal model.

DES is not only very widely implemented and used today, but triple DES and other derived schemes will probably still be around in ten or twenty years from now. We suggest that, if an algorithm is so widely used, its security should still be under scrutiny, and not taken for granted. In this paper we study the S-boxes of DES. Many properties of these are already known, yet usually they concern one particular S-box. This comes from the known design criteria on DES, that strongly suggest that S-boxes have been chosen independently of each other. On the contrary, we are interested in properties of DES S-boxes that concern a subset of two or more DES S-boxes. For example we study the properties related to Davies-Murphy attacks on DES, recall the known uniformity criteria to resist this attack, and discuss a stronger criterion. More generally we study many different properties, in particular related to linear cryptanalysis and algebraic attacks. The interesting question is to know if there are any interesting properties that hold for subsets of S-boxes bigger than 2. Such a property has already been shown by Shamir at Crypto'85 (and independently discovered by Franklin), but Coppersmith et al. explained that it was rather due to the known S-box design criteria. Our simulations confirm this, but not totally. We also present several new properties of similar flavour. These properties come from a new type of algebraic attack on block ciphers that we introduce. What we find is not easily explained by the known S-box design criteria, and the question should be asked if the S-boxes of DES are related to each other, or if they follow some yet unknown criteria. Similarly, we also found that the s5DES S-boxes have an unexpected common structure that can be exploited in a certain type of generalised linear attack. This fact substantially decreases the credibility of s5DES as a DES replacement. This paper has probably no implications whatsoever on the security of DES.

In these lecture notes we survey the state of the art in symmetric key encryption, in particular in the block ciphers and stream ciphers area. The area of symmetric key encryption has been very active in the last five years due to growing interest from academic and industry research, standardization efforts like AES, NESSIE and CRYPTREC, as well as due to ease of government control over export of cryptography.

HC-256 is a software-efficient stream cipher. It generates keystream from a 256-bit secret key and a 256-bit initialization vector. The encryption speed of the C implementation of HC-256 is about 1.9 bits per clock cycle (4.2 cycle/byte) on the Intel Pentium 4 processor. A variant of HC-256 is also introduced in this paper.

Key pre-distribution (KPD) schemes, are inherently trade-offs between security and complexity, and are perhaps well suited for securing large-scale deployments of resource constrained nodes without persistent access to a trusted authority (TA). However, the need to offset their inherent security limitations, calls for some degree of tamper - resistance of nodes. Obviously, if absolute tamper-resistance is guaranteed, KPD schemes are rendered secure. In practice, however, tamper-resistance will have some limitations which will be exploited by attackers. In this paper, we analyze the security of deployments of random key pre-distribution schemes based on some assumptions on the "extent of tamper-resistance." We argue that a "limited extent of tamper resistance" when used in conjunction with a mechanism for "periodic key updates," drastically improves the security of (especially random) KPD schemes.

Whitenoise Substitution Stream Cipher is a multi-key-Super key hierarchical cryptographic process. This cryptographic system utilizes a method of encryption that can reasonably be described conceptually as an algorithmic representation of a multi-dimensional encrypting cipher matrix. The Whitenoise algorithm takes several sub keys and then creates a very long non-repeating key stream. This was revised to respond to security concerns brought up in 2003/250.

In this paper we describe our new CS$^2$ block cipher which is an extension of the original CS-Cipher. Our new design inherits the efficiency of the original design while being upgraded to support a larger block size as well as use a slightly improved substitution box. We prove that our design is immune to differential and linear cryptanalysis as well as argue it resists several other known attacks.

Recently proposed algebraic attacks [AK03,CM03] and fast algebraic attacks [A04,C03] have provided the best analyses against some deployed LFSR-based ciphers. The process complexity is exponential in the degree of the equations. Fast algebraic attacks were introduced [C03] as a way of reducing run-time complexity by reducing the degree of the system of equations. Previous reports on fast algebraic attacks [A04,C03] have underestimated the complexity of substituting the keystream into the system of equations, which in some cases dominates the attack. We also show how the Fast Fourier Transform (FFT) [CT65] can be applied to decrease the complexity of the substitution step, although in one case this step still dominates the attack complexity. Finally, we show that all functions of degree d satisfy a common, function-independent linear combination that may be used in the pre-computation step of the fast algebraic attack and provide an explicit factorization of the corresponding characteristic polynomial. This yields the fastest known method for performing the pre-computation step.

In this paper I propose a tweakable block cipher construction with a mode of operation that combines counter and chaining methods. Using a single key, the direct application of this mode produces unrepeatable message authentication tags.

This report presents the results from the completed computation of an algorithm introduced by the authors in [11] for evaluating the provable security of the AES (Rijndael) against linear cryptanalysis. This algorithm, later named KMT2, can in fact be applied to any SPN [8]. Preliminary results in [11] were based on 43\% of total computation, estimated at 200,000 hours on our benchmark machine at the time, a Sun Ultra 5. After some delay, we obtained access to the necessary computational resources, and were able to run the algorithm to completion. In addition to the above, this report presents the results from the dual version of our algorithm (KMT2-DC) as applied to the AES.

In this paper we study the long standing problem of information extraction from multiple linear approximations. We develop a formal statistical framework for block cipher attacks based on this technique and derive explicit and compact gain formulas for generalized versions of Matsui's Algorithm 1 and Algorithm 2. The theoretical framework allows both approaches to be treated in a unified way, and predicts significantly improved attack complexities compared to current linear attacks using a single approximation. In order to substantiate the theoretical claims, we benchmarked the attacks against reduced-round versions of DES and observed a clear reduction of the data and time complexities, in almost perfect correspondence with the predictions. The complexities are reduced by several orders of magnitude for Algorithm 1, and the significant improvement in the case of Algorithm 2 suggests that this approach may outperform the currently best attacks on the full DES algorithm.

Side-channel analysis has been recognized for several years as a practical and powerful means to reveal secret keys of [publicly known] cryptographic algorithms. Only very recently this kind of cryptanalysis has been applied to reverse engineer a non-trivial part of the specification of a proprietary (i.e., secret) algorithm. The target here is no longer the value of secret key but the secret specifications of the cryptographic algorithm itself. In a recent paper, Roman Novak (2003) describes how to recover the value of one (out of two) substitution table of a secret instance of the A3/A8 algorithm, the GSM authentication and session-key generation algorithm. His attack presents however two drawbacks from a practical viewpoint. First, in order to retrieve one substitution table ($T_2$), the attacker must know the value of the other substitution table ($T_1$). Second, the attacker must also know the value of secret key $K$. In this paper, we improve Novak's attack and show how to retrieve \emph{both} substitution tables ($T_1$ and $T_2$) \emph{without any prior knowledge about the secret key}. Furthermore, as a side-effect, we also recover the value of the secret key. With this contribution, we intend to present a practical SCARE (Side Channel Analysis for Reverse Engineering) attack, anticipate a growing interest for this new area of side-channel signal exploitation, and remind, if needed, that security cannot be achieved through obscurity alone.

Whitenoise is a stream cipher with specification given at http://eprint.iacr.org/2003/249. In this paper, we show that Whitenoise is extremely weak. It can be broken by solving about 80,000 linear equations. And only about 80,000 bytes keystream are needed in the attack.

In this paper we study the additive crosscorrelation spectra between two Boolean functions whose supports are union of certain cosets. These functions on even number of input variables have been introduced by Dillon and we refer to them as Dillon type functions. Our general result shows that the crosscorrelation spectra between any two Dillon type functions are at most $5$-valued. As a consequence we find that the crosscorrelation spectra between two Dillon type bent functions on $n$-variables are at most $3$-valued with maximum possible absolute value at the nonzero points being $\leq 2^{\frac{n}{2}+1}$. Moreover, in the same line, the autocorrelation spectra of Dillon type bent functions at different decimations is studied. Further we demonstrate that these results can be used to show the existence of a class of polynomials for which the absolute value of the Weil sum has a sharper upper bound than the Weil bound. Patterson and Wiedemann extended the idea of Dillon for functions on odd number of variables. We study the crosscorrelation spectra between two such functions and then use the results for the calculating the autocorrelation spectra too.

We prove that the fast pseudo-Hadamard transform (FPHT) over a finite field has a bounded branch number. We shall demonstrate that the transform has an efficient implementation for various platforms compared to an equal dimension MDS code. We prove that when using a CS-Cipher\cite{CSC} like construction the weight of any $2R$ trail is bounded for the case of an $8 \times 8$ transform. We show that the FPHT can also be combined with MDS codes to produce efficient transforms with half of the branch of a comparable sized MDS code. We present the FPHT-HASH one-way hash function which is constructed using a $32 \times 32$ FPHT which produces a $256$-bit digest and processes the input at 24 cycles per byte with ISO C source code on an AMD Athlon XP processor.

In this paper we show how to combine the design concepts of the SQUARE and CS block ciphers to produce a pseudo-random permutation CSQUARE suitable for use in block cipher and hash design with a very high multi-round trail weight. The new design inherits the hardware efficiency of the SQUARE linear transform pattern as well as the efficiency of the fast pseudo-Hadamard transform over a finite field. We demonstrate the DMWT hash function which makes use of our new results.

This paper analyses the 3GPP confidentiality and integrity schemes adopted by Universal Mobile Telecommunication System, an emerging standard for third generation wireless communications. The schemes, known as $f8$ and $f9$, are based on the block cipher KASUMI. Although previous works claim security proofs for $f8$ and $f9'$, where $f9'$ is a generalized versions of $f9$, it was recently shown that these proofs are incorrect. Moreover, Iwata and Kurosawa (2003) showed that it is \emph{impossible} to prove $f8$ and $f9'$ secure under the standard PRP assumption on the underlying block cipher. We address this issue here, showing that it is possible to prove $f8'$ and $f9'$ secure if we make the assumption that the underlying block cipher is a secure PRP-RKA against a certain class of related-key attacks; here $f8'$ is a generalized version of $f8$. Our results clarify the assumptions necessary in order for $f8$ and $f9$ to be secure and, since no related-key attacks are known against the full eight rounds of KASUMI, lead us to believe that the confidentiality and integrity mechanisms used in real 3GPP applications are secure.

We present a cryptanalysis of a provably secure cryptographic hash function proposed by Augot, Finiasz and Sendrier on eprint. Our attack is a variant of Wagner's generalized birthday attack. It is significantly faster than the attack considered by the authors, and it is practical for two of the three proposed parameters.

In this paper we study the minimum distance between the set of bent functions and the set of 1-resilient Boolean functions and present a lower bound on that. The bound is proved to be tight for functions up to $10$ input variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of $1$-resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied upto $12$-variable functions and we show that the construction provides a large class of $1$-resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of $8$-variable, $1$-resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from $10$ variables and above, where we need to go for complicated combinatorial analysis with trial and error using computational facility.

One of the approaches to deliver real-time video encryption is to apply permutations to the bytes within a frame of a fully encoded MPEG stream as presented in [2]. We demonstrate that this particular algorithm is vulnerable to a known-plaintext attack, and hence its use should be carefully considered. We also discuss modifications that can make the algorithm resistant to our attack.

We introduce CWC, a new block cipher mode of operation for protecting both the privacy and the authenticity of encapsulated data. CWC is currently the only such mode having all five of the following properties: provable security, parallelizability, high performance in hardware, high performance in software, and no intellectual property concerns. We believe that having all five of these properties makes CWC a powerful tool for use in many performance-critical cryptographic applications. CWC is also the only appropriate solution for some applications; e.g., standardization bodies like the IETF and NIST prefer patent-free modes, and CWC is the only such mode capable of processing data at 10Gbps in hardware, which will be important for future IPsec (and other) network devices. As part of our design, we also introduce a new parallelizable universal hash function optimized for performance in both hardware and software.

Many modern stream ciphers consist of a keystream generator and a key schedule algorithm. In fielded systems, security of the keystream generator is often based on a large inner state rather than an inherently secure design. Note, however, that little theory on the initialisation of large inner states exists, and many practical designs are based on an ad-hoc approach. As a consequence, an increasing number of attacks on stream ciphers exploit the (re-)initialisation of large inner states by a weak key schedule algorithm. In this paper, we propose a strict separation of keystream generator and key schedule algorithm in stream cipher design. A formal definition of inner state size is given, and lower bounds on the necessary inner state size are proposed. After giving a construction for a secure stream cipher from an insecure keystream generator, the limitations of such an approach are discussed. We introduce the notion of inner state size efficiency and compare it for a number of fielded stream ciphers, indicating that a secure cipher can be based on reasonable inner state sizes. Concluding, we ask a number of open questions that may give rise to a new field of research that is concerned with the security of key schedule algorithms.

SOBER-128 joins the SOBER family of stream ciphers, with the added functionality of incorporating a Message Authentication Code generator if required. SOBER-128 draws on the research into the previous SOBER ciphers: the design does not differ significantly from its predecessor SOBER-t32. The biggest change is the replacement of the stuttering with a strengthened non-linear function. SOBER-128 is faster and more secure than SOBER-t32.

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 with a keyed mixing function reminiscent of a block cipher round. Aspects of the block mixer round have been derived from Rijndael, Twofish, tc24 and SAFER.

Rijndael, or the Advanced Encryption Standard, is an interesting cipher from a designer's viewpoint. Over the last few decades, the most notable, and successful attacks against the best block ciphers were linear and differential cryptanalysis. On the other hand, Rijndael is designed from the ground up to resist these attacks, as well as many others, by employing special algebraic properties of its primitive operations. The byte inversion operation over finite field $\mathbb{F}_{256}$ was chosen by its designer to thwart all possibly useful linear and difference invariances, the basic ingredients of linear and differential cryptanalysis. However, by using simple algebraic operations with known properties, the combinations of them may possess many interesting, and unexpected, algebraic properties that were not known at design time. This paper presents such new unknown properties on the combinations of primitive operations of AES.

Key exposures, known or inconspicuous, are a real security threat. Recovery mechanisms from such exposures are required. For digital signatures such a recovery should ideally ---and when possible--- include invalidation of the signatures issued with the compromised keys. We present new signature schemes with such recovery capabilities. We consider two models for key exposures: full and partial reveal. In the first, a key exposure reveals {\em all} the secrets currently existing in the system. This model is suitable for the pessimistic inconspicuous exposures scenario. The partial reveal model permits the signer to conceal some information under exposure: e.g., under coercive exposures the signer is able to reveal a ``fake'' secret key. We propose a definition of {\em generalized key-evolving signature scheme}, which unifies forward-security and security against the coercive and inconspicuous key exposures (previously considered separately \cite{BM99,NPT02-mono,I02-TE}). The new models help us address repudiation problems inherent in the monotone signatures \cite{NPT02-mono}, and achieve performance improvements.

The VMPC Stream Cipher is a simple encryption algorithm, designed as a proposed practical application of the VMPC one-way function. The general structure of the Cipher is based on an internal 256-element permutation. The VMPC Cipher, together with its Key Scheduling Algorithm, were designed in particular to eliminate some of the known weaknesses characteristic of the alleged RC4 keystream generator.

The SecurID hash function is used for authenticating users to a corporate computer infrastructure. We analyse an alleged implementation of this hash function. The block cipher at the heart of the function can be broken in few milliseconds on a PC with 70 adaptively chosen plaintexts. The 64-bit secret key of 10$\%$ of the cards can be discovered given two months of token outputs and $2^{48}$ analysis steps. A larger fraction of cards can be covered given more observation time.

This report studies the security of Whitenoise, a stream cipher invented by BSB Utilities Inc. http://bsbutil.com "Even if we hypothesized the existence of some magic computer that could test a trillion trillion key trials per second (very unlikely!), and even if we could place a trillion trillion such computers somewhere throughout the universe (even more unlikely!), and even if we were willing to wait a trillion trillion years (not a chance!), then the probability that we would discover the correct key would be negligible (about (1/2)^1340, which is unimaginably small)."

We present a cryptanalysis of a MAC proposal at CRYPTO 2003 due to Cary and Venkatesan. Our attacks find collisions for the MAC and yield MAC forgeries, both faster than a straightforward application of the birthday paradox would suggest.

We consider the problem of constructing perfect nonlinear multi-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-ouput perfect nonlinear functions satisfying higher order SAC. This construction is achieved using the theory of bilinear forms and symplectic matrices. Next we build on a known connection between 1-factorization of a complete graph and SAC to construct more examples of 2 and 3-output perfect nonlinear functions. In certain cases, the constructed S-boxes have optimal trade-off between the following parameters: numbers of input and output variables, nonlinearity and order of SAC. In case the number of input variables is odd, we modify the construction for perfect nonlinear S-boxes to obtain a construction for maximally nonlinear S-boxes satisfying higher order SAC. Our constructions present the first examples of perfect nonlinear and maximally nonlinear multioutput S-boxes satisfying higher order SAC. Lastly, we present a simple method for improving the degree of the constructed functions with a small trade-off in nonlinearity and the SAC property. This yields functions which have possible applications in the design of block ciphers.

In this paper, we present a new stream cipher called Hiji-bij-bij (HBB). The basic design principle of HBB is to mix a linear and a nonlinear map. Our innovation is in the design of the linear and the nonlinear maps. The linear map is realised using two 256-bit maximal period 90/150 cellular automata. The nonlinear map is simple and consists of several alternating linear and nonlinear layers. We prove that the mixing achieved by the nonlinear map is complete and the maximum bias in any non-zero linear combination of the input and output bits of the nonlinear map is at most $2^{-13}$. We also identify a self-synchronizing mode ({\bf SS}) of operation for HBB. The performance of HBB is reasonably good in software and is expected to be very fast in hardware. To the best of our knowledge, a generic exhaustive search seems to be the only method of attacking the cipher.

We study the relationship between the Walsh transform and the algebraic normal form of a Boolean function. In the first part of the paper, we carry out a combinatorial analysis to obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. The second part of the paper is devoted to simplify this formula and develop an algorithm to evaluate it. Our algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.

We propose a block-cipher mode of operation, called EAX, for authenticated-encryption with associated-data (AEAD). Given a nonce N, a message M, and a header H, the mode protects the privacy of M and the authenticity of both M and H. Strings N,M,H$ are arbitrary, and the mode uses $2\lceil |M|/n \rceil + \lceil |H|/n\rceil + \lceil |N|/n\rceil$ block-cipher calls when these strings are nonempty and n is the block length of the underlying block cipher. Among EAX's characteristics are that it is on-line (the length of a message isn't needed to begin processing it) and a fixed header can be pre-processed, effectively removing the per-message cost of binding it to the ciphertext. EAX is obtained by instantiating a simple generic-composition method, and then collapsing its two keys into one. EAX is provably secure under a standard complexity-theoretic assumption. EAX was designed in response to the expressed need of several standardization bodies, including NIST, IETF and IEEE 802.11, for a patent-free AEAD scheme. Such a scheme would have to be conventional, meaning it would make two passes, one aimed at achieving privacy and one aimed at achieving authenticity. EAX aims to fill this need by doing as well as possible within the space of conventional schemes with regard to issues of efficiency, simplicity, elegance, ease of correct use, and provable-security guarantees. EAX is an alternative to CCM.

A classical model is used for the power consumption of cryptographic devices. It is based on the Hamming distance of the data handled with regard to an unknown but constant reference state. Once validated experimentally it allows an optimal attack to be derived called Correlation Power Analysis. It also explains the defects of former approaches such as Differential Power Analysis.

In 1983, Patterson and Wiedemann constructed Boolean functions on $n = 15$ input variables having nonlinearity strictly greater than $2^{n-1} - 2^{\frac{n-1}{2}}$. Construction of Boolean functions on odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for $n = 15, 21$. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all $GF(2)$-linear transformations of $GF(2^{ab})$ which acts on $PG(2,2^a)$.

In this paper, we introduce HAshed Random Preloaded Subset (HARPS) key distribution, a scalable key predistribution scheme employing only symmetric crypto primitives. HARPS is ideally suited for resource constrained nodes that need to operate without a trusted authority (TA) for extended periods (as is the case for nodes forming mobile ad hoc networks (MANETs)). The performance of HARPS is compared with that of two other key predistribution schemes. The first, RPS, is a based on random intersection of keys preloaded in nodes. The second, is (a slight modification to) a scheme proposed by Leighton and Micali (LM). HARPS is a generalization of both RPS and LM. All the three schemes, rely on some degree of resistance to hardware tampering, and have probabilistic measures for the ``merit'' of the system. The merit of the schemes is a function of the probability that an attacker who has compromised N nodes (or has access to keys buried in N nodes) can ``eavesdrop'' on a conversation between R nodes (R=2 for unicast communications). We analyze and compare the performance of the three schemes for unicast and multicast communications. We show that HARPS has significant performance advantage over SIMS and LM.

Stream ciphers are often used in applications where high speed and low delay are a requirement. The Solitaire stream cipher was developed by B. Schneier as a paper-and-pencil cipher. Solitaire gets its security from the inherent randomness in a shuffled deck of cards. In this paper we investigate semigroups and groups properties of the Solitaire stream cipher and its regular modifications.

In this paper we propose an attack on the key stream generator underlying the encryption system $E_0$ used in the Bluetooth specification. We show that the initial value can be recovered by solving a system of nonlinear equations of degree 4 over the finite field GF(2). This system of equations can be transformed by linearization into a system of linear equations with at most $2^{24.056}$ unknowns. To our knowledge, this is the best attack on the key stream generator underlying the $\mbox{E}_0$ yet.

We describe a new method for authenticated encryption, which uses information from the internal state of the cipher to provide the authentication. This methodology has a number of benefits. The encryption has properties similar to CBC mode, yet the encipherment and authentication mechanisms can be parallelized and/or pipelined. The authentication overhead is minimal, so the computational cost of the authenticated encryption is very nearly that of the encryption process. Also, the authentication process remains resistant against some IV reuse. We present a class of encryption algorithms that are based on cryptographic hash functions. Because of the hash function construction, the MTC4 class of methods supports variable encryption block sizes up to twice the hash output block length and trivially supports variable key lengths. We also provide a more general construction for using the internal state of any round-based block cipher as an authenticator. We give a concrete example of the general construction that uses AES as the encryption primitive. We provide performance measurements for all of our constructions.

We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m>=2. When the underlying block cipher is secure in the sense of a strong pseudorandom permutation (PRP), our scheme is secure in the sense of tweakable, strong PRP. Such an object can be used to encipher the sectors of a disk, in-place, offering security as good as can be obtained in this setting. CMC makes a pass of CBC encryption, xors in a mask, and then makes a pass of CBC decryption; no universal hashing, nor any other non-trivial operation beyond the block-cipher calls, is employed. Besides proving the security of CMC we initiate a more general investigation of tweakable enciphering schemes, considering issues like the non-malleability of these objects.

We describe a block-cipher mode of operation, EME, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m \in [1..n]. The mode is parallelizable, but as serial-efficient as the non-parallelizable mode CMC. EME can be used to solve the disk-sector encryption problem. The algorithm entails two layers of ECB encryption and a "lightweight mixing" in between. We prove EME secure, in the reduction-based sense of modern cryptography. We motivate some of the design choices in EME by showing that a few simple modifications of this mode are insecure.

On January 8th 2003, Eric Filiol published on the eprint a paper (eprint.iacr.org/2003/003/) in which he claims that AES can be broken by a very simple and very fast ciphertext-only attack. If such an attack existed, it would be the biggest discovery in code-breaking since some 10 or more years. Unfortunately the result is very hard to believe. In this paper we present the results of computer simulations done by several independent people, with independently written code. Nobody has confirmed a single anomaly in AES, even for much weaker versions of the bias claimed by the author. We also studied the source code provided by the author to realize that the first version had various issues and bugs, and the latest version still does not confirm the claimed result on AES.

In their paper, G.Gong and S.Q.Jiang construct a new pseudo-random sequence generator by using two ternary linear feedback shift registers (LFSR). The new generator is called an editing generator which a combined model of the clock-controlled generator and the shrinking generator. For a special case (Both the base sequence and the control sequence are mm-sequence of degree $n$), the period, linear complexity, symbol distribution and security analysis are discussed in the same article. In this paper, we expand the randomness results of the edited sequence for general cases, we do not restrict the base sequence and the control sequence has the same length. For four special cases of this generator, the randomness of the edited sequence is discussed in detail. It is shown that for all four cases the editing generator has good properties, such as large periods, high linear complexities, large ratio of linear complexity per symbol, and small un-bias of occurrences of symbol. All these properties make it a suitable crypto-generator for stream cipher applications.

Camellia is the final winner of 128-bit block cipher in NESSIE. In this paper, we construct some efficient distinguishers between 4-round Camellia and a random permutation of the blocks space. By using collision-searching techniques, the distinguishers are used to attack on 6,7,8 and 9 rounds of Camellia with 128-bit key and 8,9 and 10 rounds of Camellia with 192/256-bit key. The 128-bit key of 6 rounds Camellia can be recovered with $2^{10}$ chosen plaintexts and $2^{15}$ encryptions. The 128-bit key of 7 rounds Camellia can be recovered with $2^{12}$ chosen plaintexts and $2^{54.5}$ encryptions. The 128-bit key of 8 rounds Camellia can be recovered with $2^{13}$ chosen plaintexts and $2^{112.1}$ encryptions. The 128-bit key of 9 rounds Camellia can be recovered with $2^{113.6}$ chosen plaintexts and $2^{121}$ encryptions. The 192/256-bit key of 8 rounds Camellia can be recovered with $2^{13}$ chosen plaintexts and $2^{111.1}$ encryptions. The 192/256-bit key of 9 rounds Camellia can be recovered with $2^{13}$ chosen plaintexts and $2^{175.6}$ encryptions.The 256-bit key of 10 rounds Camellia can be recovered with $2^{14}$ chosen plaintexts and $2^{239.9}$ encryptions.

A major problem in using iterative number generators of the form $x_i=f(x_{i-1})$ is that they can enter unexpectedly short cycles. This is hard to analyze when the generator is designed, hard to detect in real time when the generator is used, and can have devastating cryptanalytic implications. In this paper we define a measure of security, called \emph{sequence diversity}, which generalizes the notion of cycle-length for non-iterative generators. We then introduce the class of counter assisted generators, and show how to turn any iterative generator (even a bad one designed or seeded by an adversary) into a counter assisted generator with a provably high diversity, without reducing the quality of generators which are already cryptographically strong.

KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that the four round version is pseudorandom and the six round version is super-pseudorandom.

In 2001, Nyberg proved three important correlation theorems and applied them to several cryptanalytic contexts. We continue the work of Nyberg in a more theoretical direction. We consider a general functional form and obtain its Walsh transform. Two of Nyberg's correlation theorems are seen to be special cases of our general functional form. S-box look-up, addition modulo $2^{2k}$ and X-OR are three frequently occuring operations in the design of symmetric ciphers. We consider two methods of combining these operations and in each apply our main result to obtain the Walsh transform.

This paper presents several multiset and boomerang attacks on SAFER++ up to 5.5 out of its 7 rounds. These are the best known attacks for this cipher and significantly improve the previously known results. The attacks in the paper are practical up to 4 rounds. The methods developed to attack SAFER++ can be applied to other substitution-permutation networks with incomplete diffusion.

Vaudenay has shown in [5] that a CBC encryption mode ([2], [9]) combined with the PKCS#5 padding [3] scheme allows an attacker to invert the underlying block cipher, provided she has access to a valid-padding oracle which for each input ciphertext tells her whether the corresponding plaintext has a valid padding or not. Having on mind the countermeasures against this attack, different padding schemes have been studied in [1]. The best one is referred to as the ABYT-PAD. It is designed for byte-oriented messages. It removes the valid-padding oracle, thereby defeating Vaudenay's attack, since all deciphered plaintexts are valid in this padding scheme. In this paper, we try to combine the well-known cryptographic message syntax standard PKCS#7 [8] with the use of ABYT-PAD instead of PKCS#5. Let us assume that we have access to a PKCS#7CONF oracle that tells us for a given ciphertext (encapsulated in the PKCS#7 structure) whether the deciphered plaintext is correct or not according to the PKCS#7 (v1.6) syntax. This is probably a very natural assumption, because applications usually have to reflect this situation in its behavior. It could be a message for the user, an API error message, an entry in the log file, different timing behavior, etc. We show that access to such an oracle again enables an attacker to invert the underlying block cipher. The attack requires single captured ciphertext and approximately 128 oracle calls per one ciphertext byte. It shows that we cannot hope to fully solve problems with side channel attacks on the CBC encryption mode by using a “magic” padding method or an obscure message-encoding format. Strong cryptographic integrity checks of ciphertexts should be incorporated instead.

OMAC, TMAC and XCBC are CBC-type MAC schemes which are provably secure for arbitrary message length. In this paper, we present a more tight upper bound on ${\tt Adv}^{\sf mac}$ for each scheme, where ${\tt Adv}^{\sf mac}$ denotes the maximum success (forgery) probability of adversaries. Our bounds are expressed in terms of the \textit{total length} of all queries of an adversary to the MAC generation oracle while the previous bounds are expressed in terms of the \textit{maximum length} of each query. In particular, a significant improvement occurs if the lengths of queries are heavily unbalanced.

$PC(l)$ of order $k$ is one of the most general cryptographic criteria of secure Boolean functions. In this paper, we introduce its $\epsilon$-almost version. The new definition requires {\it only} that $f(X)+f(X+\Delta)$ is {\it almost} uniformly distiributed (while the original definition of $PC(l)$ of order $k$ requires that it is {\it strictly} uniformly distiributed). We next show its construciton. Better parameters are then obtained than normal $PC(l)$ of order $k$ functions.

CCM is a conventional authenticated-encryption scheme obtained from a 128-bit block cipher. The mechanism has been adopted as the mandatory encryption algorithm in an IEEE 802.11 draft standard [15], and its use has been proposed more broadly [16,17]. In this note we point out a number of limitations of CCM. A related note provides an alternative to CCM [5].

In this paper, we consider the statistical decision processes behind a linear and a differential cryptanalysis. By applying techniques and concepts of statistical hypothesis testing, we describe precisely the shape of optimal linear and differential distinguishers and we improve known results of Vaudenay concerning their asymptotic behaviour. Furthermore, we formalize the concept of ``sequential distinguisher'' and we illustrate potential applications of such tools in various statistical attacks.

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 shrinking generator is a well-known keystream generator composed of two linear feedback shift registers, LFSR$_1$ and LFSR$_2$, where LFSR$_1$ is clock-controlled according to regularly clocked LFSR$_2$. The keystream sequence is thus a decimated LFSR$_1$ sequence. Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the keystream sequence from a purely random sequence. Previously proposed statistical distinguishers for the shrinking generator are based on detecting binary linear relations in the keystream sequence that hold with a probability sufficiently different from one half. In this paper a novel approach which significantly reduces the required computation time is introduced. It is based on a probabilistic reconstruction of the bits in the regularly clocked LFSR$_1$ sequence that satisfy the LFSR$_1$ recurrence or any linear recurrence derived from low-weight multiples of the LFSR$_1$ characteristic polynomial. The keystream sequence length and the computation time required for a reliable statistical distinction are analyzed both theoretically and experimentally.

We describe a block-cipher mode of operation, EMD, that builds a strong pseudorandom permutation (PRP) on $nm$ bits ($m\ge2$) out of a strong PRP on $n$ bits (i.e., a block cipher). The constructed PRP is also tweaked (in the sense of [LRW02]): to determine the $nm$-bit ciphertext block $C=\E_K^T(P)$ one provides, besides the key $K$ and the $nm$-bit plaintext block $P$, an $n$-bit tweak $T$. The mode uses $2m$ block-cipher calls and no other complex or computationally expensive steps (such as universal hashing). Encryption and decryption are identical except that encryption uses the forward direction of the underlying block cipher and decryption uses the backwards direction. We suggest that EMD provides an attractive solution to the disk-sector encryption problem, where one wants to encipher the contents of an $nm$-bit disk sector in a way that depends on the sector index and is secure against chosen-plaintext/chosen-ciphertext attack.

In this paper we describe an integral distinguisher over 2 rounds of Safer++. It allows a practical attack against 3 rounds of Safer++128, as well as attacks on 4 rounds of Safer++128 and Safer++256, under the chosen-plaintext hypothesis. These results achieve much lower complexity than the currently known best attacks on Safer++, namely weak-key linear cryptanalysis by Nakahara. As a side result, we prove that the byte-branch number of the linear transform of Safer++ is 5. We also discuss a way for further research in order to extend integral cryptanalysis.

In this paper we extend the conditional correlation attack ([LCPP96]) against the nonlinear filter generator (NLFG) by introducing new conditions and generalisations and present two known-plaintext attacks, called hybrid correlation attack and concentration attack. The NLFG is a well known LFSR-based keystream generator which could be used as a basic building block in a synchronous stream cipher system. Both new attacks use methods from the conditional correlation attack and additional from fast correlation attacks to derive the unknown initial state of the LFSR of the NLFG. The basic principle of iteratively cumulating and updating conditional correlations for the NLFG was proposed in [Loh01] and for general combiners with memory in [GBM02]. With the hybrid correlation attack it is possible to successfully attack the NLFG by applying a fast correlation attack, even if the filter function $f$ of the NLFG is highly nonlinear, e.g. the normalised nonlinearity $p_{e,f}$ is $\ge 0.45$. The concentration attack maps all computed conditional correlations to $D-B$ unknown LFSR bits, where $D \ge k$ and $1 \le B \le k$ are parameters which can be chosen by the attacker, and $k$ is the length of the LFSR of the NLFG. Even with low values of conditional correlations, it is possible to mount the hybrid correlation attack and the concentration attack successfully. This is not the case for the originally version of the conditional correlation attack ([LCPP96]) in a time lower than a full search over all possible initial states.

This paper presents a new ``operational'' cryptanalysis of block ciphers based on the use of a well-known error-correcting code: the repetition codes. We demonstrate how to describe a block cipher with such a code before explaining how to design a new ciphertext only cryptanalysis of these cryptosystems on the assumption that plaintext belongs to a particular class. This new cryptanalysis may succeed for any block cipher and thus is likely to question the security of those cryptosystems for encryption. We then apply this cryptanalysis to the 128-bit key AES. Our results have been experimentallly confirmed with 100 {\bf effective} cryptanalysis. Our attack enables to recover two information bits of the secret key with only $2^{31}$ ciphertext blocks and a complexity of $\mathcal{O}(2^{31})$ with a success probability of 0.68.

In threshold cryptography the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.

At the recent AES Modes of Operation Conference, several modes of operation were proposed for using a block cipher to provide both confidentiality and authentication. These modes require only a little more work than the cost of encryption alone, and come with proofs of security. However, these modes require the entire message to be sent in encrypted form. This can cause problems in situations where some of the message neeeds to be sent in plaintext while still being authenticated. This paper describes a simple variation that allows any choice of message blocks to be sent in plaintext form rather than in encrypted form. This mode, Partial Encryption with Message Integrity (PEMI), is shown to be secure for message integrity and message secrecy.

An (n,k) pair is a pair of binary nxm matrices (A,B), such that the weight of the modulo-two sum of any i rows, 1\leq i \leq k, from A or B is equal to a_i or b_i, respectively, and moreover, a_i=b_i, for 1\leq i < k, while a_k \neq b_k. In this note we first show how to construct an (n,k) Threshold Visual Secret Sharing Scheme from an (n,k) pair. Then, we explicitly construct an (n,k)-pair for all n and k with 1 \leq k <n.

In this paper, we present a new visual crypto system based on the polarisation of light and investigate the existence and structure of the associated threshold visual secret sharing schemes. It is shown that very efficient $(n,n)$ schemes exist and that $(2,n)$ schemes are equivalent to binary codes. The existence of $(k,n)$ schemes is shown in general by two explicit constructions. Finally, bounds on the physical properties as contrast and resolution are derived.

A recent trend in message authentication is the use of a randomizing parameter, such that the authentication tag is based not only on the message and the key, but a public nonce which is changed for every authenticated message. This generally affords a better security proof. However, several new classes of attacks are made available by these techniques. We examine these attacks, and apply some of them to RMAC, a recently published MAC mechanism.

In this paper, we give the theoretical analysis of Chi-square attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the novel method of security evaluation against Chi-square attack precisely including key dependency by introducing a technique ``Transition Matrix Computing.'' On the other hand, the way of security evaluation against Chi-square attack has not been known except the computer experiment. We should note that it is the first results the way of security evaluation against Chi-square attack is shown theoretically. Using this method, we can obtain the ``weakest keys'' against the attack.

A large number of stream cipher were proposed and implemented over the last twenty years. In 1987 Rivest designed the RC4 stream cipher, which was based on a different and more software friendly paradigm. It was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL, and many other applications, and has thus become the most widely used a software-based stream cipher. In this paper we describe some properties of an output sequence of RC4. It is proved that the distribution of first, second output values of RC4 and digraphs are not uniform, which makes RC4 trivial to distinguish between short outputs of RC4 and random strings by analyzing their first, or second output values of RC4 or digraphs.

Several recently proposed ciphers are built with layers of small S-boxes, interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this hypothesis is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt'00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack is very powerful, but heuristic and it is very difficult to evaluate its complexity. The XSL attack has a parameter P, and in theory we show that P should be a constant. The XSL attack would then be polynomial in Nr, with a huge constant that is double-exponential in the size of the S-box. We demonstrated by computer simulations that the XSL attack works well enough on a toy cipher. It seems however that P will rather increase very slowly with Nr. More simulations are needed for bigger ciphers. Our optimistic evaluation shows that the XSL attack might be able to break Rijndael 256 bits and Serpent for key lengths 192 and 256 bits. However if only $P$ is increased by 2 (respectively 4) the XSL attack on Rijndael (respectively Serpent) would become slower than the exhaustive search. At any rate, it seems that the security of these ciphers does NOT grow exponentially with the number of rounds.

We consider the problem of constructing randomness extractors which are {\em locally computable}, i.e. only read a small number of bits from their input. As recently shown by Lu (CRYPTO `02), locally computable extractors directly yield secure private-key cryptosystems in Maurer's bounded storage model (J. Cryptology, 1992). In this note, we observe that a fundamental lemma of Nisan and Zuckerman (J. Computer and System Sciences, 1996) yields a general technique for constructing locally computable extractors. Specifically, we obtain a locally computable extractor by combining any extractor with any randomness-efficient (averaging) sampler. Plugging in known extractor and sampler constructions, we obtain locally computable extractors, and hence cryptosystems in the bounded storage model, whose parameters improve upon previous constructions and come quite close to the lower bounds. Along the way, we also present a refinement of the Nisan--Zuckerman lemma, showing that random sampling bits from a weak random source preserves the min-entropy rate up to an arbitrarily small additive loss (whereas the original lemma loses a logarithmic factor).

This paper is the full book of the 240 dual ciphers of Rijndael, in which only the constants differ from Rijndael. See: ``In How Many Ways Can You Write Rijndael?'', http://eprint.iacr.org.

In this paper we ask the question what happens if we replace all the constants in Rijndael, including the replacement of the irreducible polynomial, the coefficients of the MixColumn operation, the affine transformation in the S box, etc. We show that such replacements can create new dual ciphers, which are equivalent to the original in all aspects. We present several such dual ciphers of Rijndael, such as the square of Rijndael, and dual ciphers with the irreducible polynomial replaced by primitive polynomials. We also describe another family of dual ciphers consisting of the logarithms of Rijndael. We then discuss self-dual ciphers, and extend our results to other ciphers.

This paper presents an analysis of the PES cipher in a similar setting as done by Daemen et al. at Crypto'93 for IDEA. The following results were obtained for 8.5 round PES: a linear weak-key class of size $2^{48}$; two distinct differential weak-key classes of size $2^{41}$; two differential-linear weak-key classes of size $2^{62}$. For 17-round PES (double-PES): a linear weak-key class of size $2^7$, and a differential weak-key class of size $2^7$ were found. Daemen suggested a modified key schedule for IDEA in order to avoid weak keys. We found a differential weak-key class of size $2^{83}$ for 2.5-round IDEA under his redesigned key schedule, and differential-linear relations for 3.5-round IDEA.

Recently Filiol proposed to test cryptographic algorithms by making statistics on the number of low degree terms in the boolean functions. The paper has been published on eprint on 23th of July 2002. In this paper we reproduce some of Filiol's simulations. We did not confirm his results: our results suggest that DES, AES, and major hash functions have no significative bias and their output bits behave just like random boolean functions.

This paper presents a new, powerful statistical testing of symmetric ciphers and hash functions which allowed us to detect biases in both of these systems where previously known tests failed. We first give a complete characterization of the Algebraic Normal Form (ANF) of random Boolean functions by means of the Möbius transform. Then we built a new testing based on the comparison between the structure of the different Boolean functions Algebraic Normal Forms characterizing symmetric ciphers and hash functions and those of purely random Boolean functions. Detailed testing results on several cryptosystems are presented. As a main result we show that AES, DES Snow and Lili-128 fail all or part of the tests and thus present strong biases.

In this paper, we show that all the coordinate functions of the Advanced Encryption Standard (AES) round function are equivalent under an affi ne transformation of the input to the round function. In other words, let $f_i$ and $f_j$ be any two distinct output coordinates of the AES round function, then there exists a nonsingular matrix $A_{ji}$ over $GF(2)$ such that $f_j(A_{ji} x) + b_{ji}= f_i(x), b_{ji} \in GF(2)$. We also show that such linear relations will always exist if the Rijndael s-b ox is replaced by any bijective monomial over $GF(2^8)$. %We also show that replacing the s-box by any bijective monomial will not change this property.

We demonstrate that the existence of distinguishing attacks against stream ciphers is unrelated to their security in practical use, and in particular that the amount of data required to perform a distinguishing attack is unrelated to the key length of the cipher. The implication for the NESSIE Project is that no submitted symmetric cipher would be accepted under the unpublished rules for distinguishing attacks, not even the block ciphers in Counter Mode or Output Feedback Mode.

We consider communication sessions in which a pair of parties begin by running an authenticated key-exchange protocol to obtain a shared session key, and then secure successive data transmissions between them via an authenticated encryption scheme based on the session key. We show that such a communication session meets the notion of a secure channel protocol proposed by Canetti and Krawczyk if and only if the underlying authenticated encryption scheme meets two new, simple definitions of security that we introduce, and the key-exchange protocol is secure. In other words, we reduce the secure channel requirements of Canetti and Krawczyk to easier to use, stand-alone security requirements on the underlying authenticated encryption scheme.

We show that any scheme to encrypt m blocks of size n bits while assuring message integrity, that apart from using m+k invocations of random functions (from n bits to n bits) and vn bits of randomness, is linear in (GF2)^n, must have k+v at least Omega(log m). This lower bound is proved in a very general model which rules out many promising linear modes of operations for encryption with message integrity. This lower bound is tight as linear schemes to encrypt m blocks while assuring message integrity by using only m+2+log m invocations are known. of random permutations.

Vaudenay [1] has presented an attack on the CBC mode of block ciphers, which uses padding according to the PKCS#5 standard. One of the countermeasures, which he has assumed, consisted of the encryption of the message M´= M || padding || hash(M || padding) instead of the original M. This can increase the length of the message by several blocks compared with the present padding. Moreover, Wagner [1] showed a security weakness in this proposal. The next correction, which Vaudenay proposed ("A Fix Which May Work") has a general character and doesn't solve practical problems with the real cryptographic interfaces used in contemporary applications. In this article we propose three variants of the CBC mode. From the external point of view they behave the same as the present CBC mode with the PKCS#5 padding, but they prevent Vaudenay's attack.

From a view point of cryptography, we define a new covering radius of Reed-Muller codes as the maximum distance between $t$-{\it resilient} functions and the $r$-th order Reed-Muller code $RM(r,n)$. We next derive its lower and upper bounds. We also present a table of numerical data of our bounds.

In this paper, we propose TMAC, Two-Key CBC Message Authentication Code. TMAC is a refinement of XCBC (which is a variant of CBC MAC) shown by Black and Rogaway. We use only $(k+n)$-bit key for TMAC while XCBC uses $(k+2n)$-bit key, where $k$ is the key length of the underlying block cipher and $n$ is its block length. The cost for reducing the size of secret keys is almost negligible; only one shift and one conditional XOR. Similarly to XCBC, our algorithm correctly and efficiently handles messages of arbitrary bit length.

The recently proposed multiplicative masking countermeasure against power analysis attacks on AES is interesting as it does not require the costly recomputation and RAM storage of S-boxes for every run of AES. This is important for applications where the available space is very limited such as the smart card applications. Unfortunately, it is here shown that this method is in fact inherently vulnerable to differential power analysis. Other possible random masking methods are also discussed.

Many bitstream generators are based on linear feedback shift registers. A widespread technique for the cryptanalysis of those generators is the linear consistency test (LCT). In this paper, we consider an application of the LCT in cryptanalysis of clock-controlled bitstream generators, called \textsl{clock control guessing}. We give a general and very simple method for estimating the efficiency of clock control guessing, yielding an upper bound on the effective key length of a whole group of bitstream generators. Finally, we apply the technique against a number of clock-controlled generators, such as the A5/1, alternating step generator, step1-step2 generator, cascade generator, and others.

In this paper we describe several fault attacks on the Advanced Encryption Standard (AES). First, using optical fault induction attacks as recently publicly presented by Skorobogatov and Anderson \cite{SA}, we present an implementation independent fault attack on AES. This attack is able to determine the complete $128$-bit secret key of a sealed tamper-proof smartcard by generating $128$ faulty cipher texts. Second, we present several implementation-dependent fault attacks on AES. These attacks rely on the observation that due to the AES's known timing analysis vulnerability (as pointed out by Koeune and Quisquater \cite{KQ}), any implementation of the AES must ensure a data independent timing behavior for the so called AES's {\tt xtime} operation. We present fault attacks on AES based on various timing analysis resistant implementations of the {\tt xtime}-operation. Our strongest attack in this direction uses a very liberal fault model and requires only $256$ faulty encryptions to determine a $128$-bit key.

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a ``non-linear process'' (say, akin to a round function in block ciphers), and a ``linear process'' such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the ``non-linear process'' that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property. In this report we analyze two specific ``distinguishing properties''. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly $2^{95}$ words of output, with work-load of about $2^{100}$. The other is a ``low-diffusion'' attack, that we apply to the cipher Scream-0. The latter attack needs only about $2^{43}$ bytes of output, using roughly $2^{50}$ space and $2^{80}$ time.

We report on the design of Scream, a new software-efficient stream cipher, which was designed to be a ``more secure SEAL''. Following SEAL, the design of Scream resembles in many ways a block-cipher design. The new cipher is roughly as fast as SEAL, but we believe that it offers a significantly higher security level. In the process of designing this cipher, we re-visit the SEAL design paradigm, exhibiting some tradeoffs and limitations.

The encryption system \(E_{0}\), which is the encryption system used in the Bluetooth specification, is a two level system where a key and a packet nonce is given to a level 1 key stream generator, which produces the key for a level 2 key stream generator, whose output is used to encrypt. We give a method for recovering the key for the level 1 key stream generator given the internal keys for two or three level 2 key stream generators. This method, combined with published methods for recovering keys for the level 2 key stream generator, can be used to recover the \(E_{0}\) second key with $O(2^{65})$ work, and $O(2^{80})$ precomputation time. Although this attack is of no advantage if \(E_{0}\) is used with the recommended security parameters (64 bit encryption key), it shows that no addition security would be made available by enlarging the encryption key, as discussed in the Bluetooth specification.

Most guidelines for implementation of the RC4 stream cipher recommend discarding the first 256 bytes of its output. This recommendation is based on the empirical fact that known attacks can either cryptanalyze RC4 starting at any point, or become harmless after these initial bytes are dumped. The motivation for this paper is to find a conservative estimate for the number of bytes that should be discarded in order to be safe. To this end we propose an idealized model of RC4 and analyze it applying the theory of random shuffles. Based on our analysis of the model we recommend dumping at least 512 bytes.

The boomerang attack is a new and very powerful cryptanalytic technique. However, due to the adaptive chosen plaintext and ciphertext nature of the attack, boomerang key recovery attacks that retrieve key material on both sides of the boomerang distinguisher are hard to mount. We also present a method for using a boomerang distinguisher, which enables retrieving subkey bits on both sides of the boomerang distinguisher. The rectangle attack evolved from the boomerang attack.In this paper we present a new algorithm which improves the results of the rectangle attack. Using these improvements we can attack 3.5-round SC2000 with $2^{67}$ adaptive chosen plaintexts and ciphertexts, and 10-round Serpent with time complexity of $2^{173.8}$ memory accesses (which are equivalent to $2^{165.3}$ Serpent encryptions) with data complexity of $2^{126.3}$ chosen plaintexts.

We address the problem of testing the hypothesis H_0 that the letters from some alphabet A= {a_1,a_2,..., a_k }, are distributed uniformly against the alternative hypothesis H_1 that the true distribution is not uniform, in case k is large. (It is typical for random number testing and some cryptographic problems where k= 2^{10} - 2^{30} and more). In such a case it is difficult to use the chi-square test because the sample size must be greater than k. We suggest the adaptive chi-square test which can be successfully applied for testing some kinds of H_1 even in case when the sample size is much less than k. This statement is confirmed theoretically and experimentally. The theoretical proof is based on the consideration of one kind of the alternative hypothesis H_1 where the suggested test rejects the null hypothesis when the sample size is O( \sqrt{k} ) (instead of const k for the usual chi-square test ). For experimental investigation of the suggested test we consider a problem of testing ciphered Russian texts. It turns out that the suggested test can distinguish the ciphered texts from random sequences basing on a sample which is much smaller than that required for the usual chi-square test.

For independent binary random variables x_1,...,x_n and a Boolean function f(x), x=(x_1,...,x_n), we suppose that |1/2 - P{x_i = 1}|<=e, 1<=i<=n. Under these conditions we present new characteristics D_F(f(),e) = max{|1/2 - P{y=1}|} of the probability properties of Boolean functions, where y = F(x), and F(x) being equal to 1) F(x)=f(x), 2) F(x)=f(x)+(a,x), 3) F(x)=f(x)+f(x+a), and investigate their properties. Special attention is paid to the classes of balanced and correlation immune functions, bent functions, and second order functions, for which upper estimates of D_F(f(),e) are found and statements on behaviour of sequences f^{(n)}(x) of functions of n arguments are made.

This report surveys on a series of Square attacks on reduced-round versions of the Skipjack block cipher. {\bf Skipjack} is an iterated block cipher encrypting 64-bit plaintext blocks into 64-bit ciphertext blocks, using an 80-bit key. Its design is based on a generalized Feistel Network making up 32 rounds of two different types. This cipher was developed by the National Security Agency for the Clipper chip and Fortezza PC card.