About 2-cascade finite automata cryptographic generators and their cryptanalysis
A cryptographic generator under consideration is a serial connectiom G = A<sub>1</sub> · A<sub>2 </sub>of two finite state machines (finite automata) A<sub>1</sub> and A<sub>2</sub> both defined over the two-element field F<sub>2</sub>. The first one is an autonomous automaton A<sub>1</sub> = (Fn, F<sub>2</sub>,g<sub>1</sub>, f<sub>1</sub>) with the state set Fn, n > 1, the output alphabet F<sub>2</sub>, a transition function g<sub>1</sub> : Fn ^ Fn, and an output function f<sub>1</sub> : Fn ^ F<sub>2</sub>. The second one is a non-autonomous automaton A<sub>2</sub> = (F<sub>2</sub>,Fn,F<sub>2</sub>,g<sub>2</sub>,f<sub>2</sub>) with the state set F™, m > 1, the input and output alphabets F<sub>2</sub>, an output function f<sub>2</sub> : F<sub>2</sub> x Fn ^ F<sub>2</sub>, and a transition function g<sub>2</sub> : F<sub>2</sub> x F™ ^ F™, for which there exist a map g : F™ ^ F™ and some different integers 6 and т such that, for all u € F<sub>2</sub> and y € F™, g<sub>2</sub>(u, y) = -ug^(y) + ug<sup>T</sup>(y), where g<sup>0</sup>(y) = y and g<sup>r</sup>(y) = g(g<sup>r-1</sup>(y)) for every integer r ^ 1. Thus, the generator G is a finite autonomous automaton G = A<sub>1</sub> · A<sub>2</sub> = (Fn x F^, F<sub>2</sub>,h, f), where h : F<sup>n</sup> x F™ ^ F<sup>n</sup> x F™ and h(x,y) = Ыж)^(Д(ж), y)), f : F?? x F™ ^ F2 and f(x,y) = f<sub>2</sub>(f<sub>1</sub>(x),y), ж € Fn, y € Frn. As we see, all the functions in the definition of G are Boolean ones, and the functions g<sub>1</sub> and g<sub>2</sub>,g are vector functions of dimensions n and m respectively. Further, it is assumed that each of them belongs to a predetermined class of Boolean functions and the classes of functions f1 and f<sub>2</sub> are denoted by C<sub>1</sub> and C<sub>2</sub> respectively. At any time moment t = 1, 2,..., the automaton A<sub>1</sub> goes from its state x(t) to a state x(t + 1) = g<sub>1</sub>(x(t)) and produces an output symbol u(t) = f<sub>1</sub>(x(t)), the automaton A<sub>2</sub> receives u(t) and goes from its state y(t) to a state y(t + 1) = g<sub>2</sub>(u(t),y(t)) and produces an output symbol z(t) = f<sub>2</sub>(u(t),y(t)) which is the output symbol generated by G at this moment. In general, a key of the generator can be defined as any non-empty subset of the set {x(1),y(1), f<sub>1</sub>,g<sub>1</sub>, f<sub>2</sub>,g<sub>2</sub>,g, 6, т}. The cryptanalysis problem for G is the following: given a finite beginning 7 = z(1)z(2)... z(l) of a sequence generated by G, find the generator key value. For solving the problem, the generator is described by a system of logical equations, connecting bits in 7 with the initial states and values of transition and output functions in automata A<sub>1</sub> and A<sub>2</sub>. It is shown that in G with the linear A<sub>2</sub>, the key y(1) is determined with the polynomial complexity by solving a system of linear equations and the key (x(1),y(1)) - by the linearization attack (trying different initial states of A<sub>1</sub>) with the complexity 2<sup>n</sup> which is much less than 2<sup>n</sup>+™ - the complexity of the bruitforce attack. For an arbitrary G with the known g<sub>2 </sub>and f<sub>2</sub>, a method is proposed allowing to compute from 7 a string of the output sequence в = u(1)u(2)... u(l) of A<sub>1</sub> and so to reveal two possibilities for cryptanalysis of this G: 1) to determine its key (x(1),y(1)) by the meet-in-the-middle attack with the complexity 2™ or 2) to reduce the cryptanalysis problem for G to the cryptanalysis problem for A<sub>1</sub>, that is, to determine the key of A<sub>1</sub> by в. The complexity of the method is polynomial if y(1) is not included in the key and is not more than 2™ otherwise. In case when the key of an arbitrary G is f<sub>i</sub>, this key can be determined by identifying f<sub>i</sub> with a function f e C<sub>i</sub> satisfying the equalities f (x(t)) = u(t), t = 1,2,...,l. Similarly, if the key of G is f<sub>2</sub>, the determination of f<sub>2</sub> is reduced to the construction of a function f e C<sub>2</sub> satisfying the equalities f(u(t),y(t)) = z(t), t = 1,2,..., l. In connection with the last, it is told about some algorithms, known to the authors, for extending a partially defined Boolean function in a large set of variables to a function from a class of completely defined Boolean functions essentially depending on a little or bounded number of variables in this set.