About 2-cascade finite automata cryptographic generators and their cryptanalysis
A cryptographic generator under consideration is a serial connectiom G = A1 · A2 of two finite state machines (finite automata) A1 and A2 both defined over the two-element field F2. The first one is an autonomous automaton A1 = (Fn, F2,g1, f1) with the state set Fn, n > 1, the output alphabet F2, a transition function g1 : Fn ^ Fn, and an output function f1 : Fn ^ F2. The second one is a non-autonomous automaton A2 = (F2,Fn,F2,g2,f2) with the state set F™, m > 1, the input and output alphabets F2, an output function f2 : F2 x Fn ^ F2, and a transition function g2 : F2 x F™ ^ F™, for which there exist a map g : F™ ^ F™ and some different integers 6 and т such that, for all u € F2 and y € F™, g2(u, y) = -ug^(y) + ugT(y), where g0(y) = y and gr(y) = g(gr-1(y)) for every integer r ^ 1. Thus, the generator G is a finite autonomous automaton G = A1 · A2 = (Fn x F^, F2,h, f), where h : Fn x F™ ^ Fn x F™ and h(x,y) = Ыж)^(Д(ж), y)), f : F?? x F™ ^ F2 and f(x,y) = f2(f1(x),y), ж € Fn, y € Frn. As we see, all the functions in the definition of G are Boolean ones, and the functions g1 and g2,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 f2 are denoted by C1 and C2 respectively. At any time moment t = 1, 2,..., the automaton A1 goes from its state x(t) to a state x(t + 1) = g1(x(t)) and produces an output symbol u(t) = f1(x(t)), the automaton A2 receives u(t) and goes from its state y(t) to a state y(t + 1) = g2(u(t),y(t)) and produces an output symbol z(t) = f2(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), f1,g1, f2,g2,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 A1 and A2. It is shown that in G with the linear A2, 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 A1) with the complexity 2n which is much less than 2n+™ - the complexity of the bruitforce attack. For an arbitrary G with the known g2 and f2, a method is proposed allowing to compute from 7 a string of the output sequence в = u(1)u(2)... u(l) of A1 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 A1, that is, to determine the key of A1 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 fi, this key can be determined by identifying fi with a function f e Ci satisfying the equalities f (x(t)) = u(t), t = 1,2,...,l. Similarly, if the key of G is f2, the determination of f2 is reduced to the construction of a function f e C2 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.