On the Efficiency of the Probabilistic Neutral Bits Method in Statistical Cryptanalysis of Synchronous Stream Ciphers
- PDF / 121,676 Bytes
- 6 Pages / 594 x 792 pts Page_size
- 25 Downloads / 222 Views
CYBERNETICS ON THE EFFICIENCY OF THE PROBABILISTIC NEUTRAL BITS METHOD IN STATISTICAL CRYPTANALYSIS OF SYNCHRONOUS STREAM CIPHERS A. N. Alekseychuk1† and S. N. Konyushok1‡
UDC 519.7
Abstract. Achievable upper bounds are obtained for the relative distance between a Boolean function f and a function nearest to it and independent of variables with numbers from a given set and also between the function f and its subfunction obtained by fixing the mentioned variables to zeros. The expressions for the obtained bounds depend on metric characteristics of derivatives of the function f , which makes it possible to apply these bounds to the estimation and substantiation of the efficiency of the probabilistic neutral bits method. Keywords: synchronous stream cipher, statistical cryptanalysis, method of probabilistic neutral bits, approximation of Boolean functions.
The method of probabilistic neutral bits [1, 2] is proposed that is destined for the construction of statistical attacks on synchronous stream ciphers and consists of approximating Boolean functions connected with enciphering algorithms specified by functions of a smaller number of variables. Note that similar (and also more general) approximations were studied in [3–9] and some other publications. In [1, 2], in the capacity of approximations of a Boolean function f = f ( x1 , ... , x n ) , it is proposed to use its subfunctions obtained by fixing variables x i for which the number of 1s in the vector of values of the derivative D i f = f ( x1 , K , x i -1 , x i , x i + 1 , ..., x n ) Å f ( x1 , ... , x i -1 , x i Å 1, x i +1 , ..., x n ) does not exceed a given (small) threshold to constants. It is illustrated by concrete examples that these approximations lead to more efficient attacks on reduced versions of a number of synchronous stream ciphers in comparison with an exhaustive search for keys, but the efficiency of the proposed method of construction of approximations is not investigated in the general case. In this article, achievable upper bounds are obtained for the relative distance between a Boolean function f and a function that is nearest to it and is independent of the variables with the numbers from a given set and also between the function f and its approximations obtained by the method of probabilistic neutral bits [1, 2]. The expressions for the obtained bounds make it possible to establish the numerical parameters of the derivatives of the function f on which the mentioned relative distances depend and also to formulate the conditions under which the method of probabilistic neutral bits leads to approximations of the given function that are acceptable from the practical viewpoint. We introduce the following designations: Vn is the space of binary vectors of length n ; B n = { f | f :Vn ® {0, 1}} is the set of Boolean functions of n variables; # M is the cardinality of a set M ; d ( f , g ) = 2 - n # { x ÎVn : f ( x ) ¹ g ( x )} is the relative distance between functions f , g Î B n ; 1
Institute of Special Communication and Information Security
Data Loading...
