About 2-cascade finite automata cryptographic generators and their cryptanalysis | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 35. DOI: 10.17223/20710410/35/4

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