On Large Distributions for Linear Cryptanalysis
Calculating the distribution of certain functions during the linear cryptanalysis of stream ciphers is a frequently encountered problem. Let a function N (or a noise variable) be expressed via k mutually independent and uniformly distributed n-bit random
- PDF / 256,081 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 112 Downloads / 218 Views
Abstract. Calculating the distribution of certain functions during the linear cryptanalysis of stream ciphers is a frequently encountered problem. Let a function N (or a noise variable) be expressed via k mutually independent and uniformly distributed n-bit random variables X1 , X2 , . . . , Xk . The possibility to construct its distribution depends on the form of the expression N , and sometimes it becomes a bottleneck of the cryptanalysis. In this paper we propose several new techniques to construct such distributions and widen the class of functions for which its distribution can efficiently be calculated. Keywords: Linear cryptanalysis, complexity reduction, approximations, large distributions, pseudo-linear functions.
1
Introduction
Linear cryptanalysis is an important type of analysis of cryptographic primitives. It is, for example, the best known attack on DES [1,2]. Many recently proposed stream ciphers, such as Scream [3], SNOW 2.0 [4], A5/1 [5], E0 [6], RC4 [7], SOBER t16/t32 [8,9], and others, are shown to be weak agains linear cryptanalysis [10,11,12,13,14,15,16]. In this kind of analysis, nonlinear blocks are substituted by a linear transformation. Due to such an approximation a new variable, called noise variable, is added to the result of the linear transformation. When the cipher becomes linear, a certain equation connecting words of the plaintext, the ciphertext and the secret key 1 can be derived. These equations are usually time invariant, one side of which is a known value – a sample value Zt at time t, and on the other side of the equation is a linear combination N of noise variables. This allows to collect samples Zt , the distribution of which converges to the distribution of N . A sufficient number of samples can allow to recover the complete or a part of the secret key. The efficiency of such attacks usually depends on the possibility to construct the distribution of the noise. This particular problem often becomes a bottleneck in various linear cryptanalyses, since the construction of the distribution for a complex function can be computationally infeasible for nowadays resources. To 1
In stream ciphers it is assumed that the keystream is available, which is usually a word based addition of the plaintext and the ciphertext.
K.-H. Nam and G. Rhee (Eds.): ICISC 2007, LNCS 4817, pp. 89–101, 2007. c Springer-Verlag Berlin Heidelberg 2007
90
A. Maximov
be more specific, assume that the operation XαY is replaced by X⊕Y , where is the addition modulo 2n and α is some element of the field F2n . The effectiveness of the approximation is given by the probability Pr{(X αY ) ⊕ (X ⊕ Y ) = γ}. However, its distribution is hard to compute. When n = 32, a straightforward solution requires 264 of operations, whereas the algorithm proposed in this paper needs only 237 of time. Similar problems were studied in several previous papers, see, e.g. [17,18,19,20]. A recent paper [21], however, introduces the most general class called pseudo linear functions (PLFs), for which their distributions can be calc
Data Loading...
