Cryptautomata: definition, cryptanalysis, example.pdf 1. Definition In this paper, we will present an extended abstract of the recent article [1] devoted to the definition of the cryptautomata and to description of some cryptanalysis techniques for them. Here is a formal mathematical definition: a cryptautomaton is a three-tuple (C, I, K), where C, the network class, is a finite set of possible automaton networks; I, the keyplace, is a finite set of possible key variables, and K, the keyspace, is a finite set of possible keys. The automaton networks under consideration are constructed of some initial finite automata (finite-state machines) by using the operations of series, parallel, and feedback connections, and they themselves uniquely define some initial finite automata. The set C is completely defined by any automaton network N Е C and consists of all the automaton networks that can only differ from N in some parameters of some components. For every such a parameter, the set of these components is presented in the keyplace I, and the parameter itself - in the keyspace K as a part of a key. Here, by the parameters of an automaton Ai = (Xi, Si, Yi, gi, fi, si(1)) in N, we mean its initial state si(1), its transition function gi : Xi х Si ^ Si, and its output function f : Xi х Si ^ Yi. It is supposed, that the parameters si(1), gi, and f are elements of, respectively, the set Si of states in Ai, a class Gi of some functions g : Xi х Si ^ Si, and a class Fi of some functions f : Xi х Si ^ Yi. So, if N consists of r components A^ i Е {1, 2,..., r}, then the keyplace I is the threetuple of sets Is, It, and Io that are subsets of {1, 2,...,r}, and the keyspace K of the cryptautomaton is the Cartesian product П of sets Ks, Kt, and Ko, where Ks = П S^ ie/s Kt = П Gi, and Ko = Fi. Thus, a key in K is a three-tuple ksktko, where ks Е Ks, ie/t ie/o kt Е Kt, and ko Е Ko, that is, a cryptautomaton key can be composed of initial states of some components in N, of transition functions in Gi for some i Е {1, 2,... ,r}, and of output functions in Fj for some j Е {1, 2,..., r}. Each key k in K defines a certain automaton network Nk in C and C = {Nk : kЕK}. The operation (functioning) of this network Nk in discrete time is described by the canonical system of equations of its automaton as well as by the union of canonical systems of equations describing the operations of components in Nk. The second system of equations also describes the structure (circuit) of Nk. In case that, for any k, the automaton of Nk is invertible, the cryptautomaton (C, I,K) is a cipher. 2. Cryptanalysis There are many different cryptanalysis problems for a given cryptautomaton (C, I,K). Some of them are put as follows: given a finite output sequence 7 of a network Nk in C and, possibly, an input sequence a which Nk transforms into 7, determine the key k and (or) the sequence a. For solving these problems, we offer to solve the following two mathematical problems: 1) finding solutions of the systems of equations describing the operation or structure of the automaton networks in the network class C; 2) completing partially defined functions in a functional class, that is, for given a partially defined function ф and a class Ф of completely defined functions, it is required to find a function in Ф which coincides with ф on its domain. In fact, the second problem is connected with the first one and appears after partial determining unknown output or transition functions of some components in the network Nk by solving its system of equations. The system E of equations of any automaton network is recursively easy solvable (r.e.s.), that is, it has a nonempty subsystem E1 С E with a small effective subset U of unknowns such that assigning any possible values to them makes E1 to be easily solvable and the subsystem E2 = E \ E1 becomes r.e.s. after substitution of any solution of E1 into it. Thus, every solution of E can be computed by the method DSS [1, 2], consisting of three repeated actions: Divide E into E1 and E2, Solve E1, and Substitute solutions of E1 into E2. In [1], we illustrated the method DSS by solving canonical systems of equations of finite automata, series, parallel, and feedback automaton networks over the field f2 of two elements. The solution problem was the following one: given an output sequence of an automaton network N, find the input sequences of N. Besides, we defined an autonomous cryptautomaton with alternating control over f2 (that is a generalization of the cryptographic alternating step generator on LFSRs [3]) and illustrated the method DSS and the problem of completing partially defined functions by several attacks on this cryptautomaton with some different keyplaces I and corresponding keyspaces K. 3. Autonomous alternating control cryptautomaton Let £ be an autonomous cryptautomaton (C,I,K). It is called an alternating control cryptautomaton if each automaton network N in C is a network with alternating control, that is, N is a series-parallel connection of three automata: an autonomous automaton A1, A1 = (fm1,f2,g1, f1, s1(1)), and two unautonomous automata A2 and A3, Ai = (f2, f^, f2, gi, fi, si(1)), i E {2, 3}, both controlled by A1 in such a way that, for any their input symbol y1 (produced on the output of A1) and states s2 и s3 respectively, the alternation condition g2(y1, s2) = s2 ^ g3(y1,s3) = s3 is true, and both producing output symbols y2 and y3 respectively with the sum y2 ф y3 mod 2 on the output of N. For each i E {1, 2, 3}, it is supposed that Si = f^4, gi E Gi, and fi E Fi, where Gi and Fi are some functional classes. The following is the canonical system of equations of the network N with alternating control: y1(t) = f1(s1(t)), S1(t +1)= g1(s1(t)), y2(t) = f2(y1(t),S2(t)), S2(t +1)= g2Mt),S2(t)), уз(*) = f3Mt),S3(t)), S3(t +1)= g3(y1(t),S3(t)), y(t) = У2(t) ф У3(t), t > 1, s1(1)s2(1)s3(1) - initial state, where the first two equations describe the automaton A1, the next five equations - the parallel subnetwork N' of the automata A2 and A3. Here, for cryptanalysis of an alternating control cryptautomaton E, we describe some attacks on it with a known output sequence 7 = y(1)y(2) . ..y(l), l ^ 1, in order to determine its key k by using the method DSS in solving the canonical system of equations of a network Nk in C and by completing partially defined output functions of its components in their classes. The attacks depend on the type of keyplace I in E. 1. Is = {1}, It = Io = 0; Ks = S1 = fm1, Kt = Ko = 0; K = Ks = fm1; k = s1(1) Е K. Attack 1:1) given 7 on the output of E, use the method DSS and compute the input sequences of parallel subnetwork N' that are, simultaneously, the output sequences of the automaton A1; 2) for each of these sequences, find an initial state s1(1) of the automaton A1 by an exhaustive key search. Computational complexity of the attack equals 2mi. 2. Is = {1, 2}, It = Io = 0; Ks = х S2 = fm1 х fm2, Kt = K = 0; K = Ks = = fm1 х fm2; k = s1(1)s2(1) Е K. In this case, the key of E is computed by a meet-in-the-middle attack. In advance, before the attack, for each possible value a of unknown s1(1), compute s1(t + 1) = g1(s1(t)) and У1 (t) = f1(s1(t)) for t Е {1, 2, ...,l} and s1(1) = a and store a in memory by address H(y1(1)y1 (2)... y1(l)), where H : F2> ^ Fm1 is a hash function. Attack 2: given 7 on the output of E, use the method DSS and compute the input sequences of subnetwork N' for different values of s2(1) chosen unless, for some its value b, a sequence в will be obtained on the input of N' such that there is a value a of s1(1) in memory by address H(в); in this case the pair (a, b) is taken for the result - the key k. Computational complexity of the attack equals 2m2. Remark: the attack remains valid after exchanging roles of A2 and A3 in it. 3. Is = {1, 2,3}, It = Io = 0; Ks = S1 х S2 х S3 = fm1 х fm2 х Fm3, Kt = Ko = = 0; K = Ks = fm1 х fm2 х fm3; k = s1(1)s2(1)s3(1) Е K, and the set of variables y1 (1), y1(2),..., y1(l) is a linearization set in the system of equations E' of the subnetwork N' of the network N. Attack 3: for each s1(1) in S1, 1) compute s1(t +1) = g1(s1(t)) and y1(t) = f1(s1(t)) for t Е {1, 2,..., l}; 2) execute the linearization attack on E', namely: substitute the values y1 (1),y1(2),... ,y1(l) into E', solve the obtained system E'' of linear equations by Gauss method and find the values of unknowns s2(t) и s3(t), t Е {1, 2,..., l}; 3) from each solution of E'' satisfying the alternation condition for all t, 1 ^ t ^ l, take the values of s2(1) and s3(1) and fix the three-tuple (s1(1)s2(1)s3(1)) as one of the values of the key k. Computational complexity of the attack equals 2m1. Remark. So we have proved that in this case, the real key of the alternating control cryptautomaton is the initial state of the controlling automaton and its estending by means of initiall states of controlled automata doesn't increase the cryptographic security of the cryptautomaton. For the LFSR-based cryptographic alternating step generators, this fact was shown earlier in [4]. 4. Is = It = 0, Io = {1}; Ks = Kt = 0, Ko = F1; K = Ko = F1; k = /1 Е K. Attack 4: 1) compute s1(t + 1) = g1(s1 (t)), t Е {1, 2,..., l - 1}; 2) as in Attack 1, step 1, compute the input sequences of subnetwork N' of the network N by method DSS; 3) by any of them y1(1)y1(2) ...y1(l) and the internal sequence s1(1)s1(2) ...s1(l) of the automaton A1, construct a partially defined function /1 as /1 (s1(t)) = y1(t) for t Е {1, 2,..., l}; 4) in the class F1, find a function /1 which is an extension of /1 and, in case of success of this operation, give /1 as one of the values of the key k. Remark: to obtain all the values of the key k under which the cryptautomaton produces y, the construction in the step 3 is executed for every sequence computed in the step 2. 5. Is = / = 0, 1o = {2}; Ks = Kt = 0, Ko = F2; K = K0 = F2; k = /2 е K. Attack 5: 1) compute s1 (t + 1) = g1(s1(t)), y1(t) = /1(s1(t)) in the automaton A1 and s3(t + 1) = g3(y1(t), s3(t)), y3(t) = /3(y1, s3(t)) in the automaton A3 for t е {1, 2,..., /}; 2) construct a partially defined function /2 as /2(y1(t), s2(t)) = y(t) ф y3(t) for t е {1, 2,...,/}; 3) in the class F2, find a function /2 which is an extension of /2 and, in case of success of this operation, give /2 as one of the values of the key k. Remark: the attack remains valid after exchanging roles of A2 and A3 in it. 6. Is = It = 0, /0 = {2, 3}; Ks = Kt = 0, Ko = F х F3; K = Ko = F х F3; k = /2/3 е K. Attack 6: 1) compute s1 (t + 1) = g1(s1(t)), y1(t) = /1(s1(t)) in the automaton A1 for t е {1, 2,...,/}, s2(t + 1) = g2(y1(t), s2(t)) in the automaton A2, and s3(t + 1) = = g3(y1(t),s3 (t)) in the automaton A3 for t е {1, 2,...,/ - 1}; 2) compute 21 pairs of sequences yj (1)y2j (2)... y2j (/), y3j (1)y3j (2). ..y3j (/), j е {1, 2,...,/}, such that yj (t) = = y3j(t) = 0 V y2j(t) = y3j(t) = 1 if y(t) = 0 or (y2j(t) = 0, y3j(t) = 1) V (y2j(t) = 1, y3j(t) = 0) if y(t) = 1; 3) for each j е {1, 2,..., /}, construct partial Boolean functions /2j and /3^ as /2^(y1(t), s2(t)) = y2j(t) and /3^(y1(t), s3(t)) = y3j(t), t е {1, 2,...,/}; 4) in the classes F2 and F3, find some functions /2 and /3 respectively which are the extensions of /2j and /3j respectively and, in case of success of this operation, give /2/3 as one of the values of the key k. Computational complexity of the attack equals 21. Remark: if, in the step 4 for every j, at least one of the functions /2j or /3j- is not completed in the corresponding class, F2 or F3, then the cryptanalysis problem for the cryptautomaton £ hasn't solution in this case.

Скачать электронную версию публикации