About $2$-cascade finite automata cryptographic generators and their cryptanalysis

G. P. Agibalov ; I. A. Pankratova

Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 38-47.

Résumé

A cryptographic generator under consideration is a serial connectiom $G=A_1\cdot A_2$ of two finite state machines (finite automata) $A_1$ and $A_2$ both defined over the two-element field $\mathbb F_2$. The first one is an autonomous automaton $A_1=(\mathbb F_2^n,\mathbb F_2,g_1,f_1)$ with the state set $\mathbb F_2^n$, $n>1$, the output alphabet $\mathbb F_2$, a transition function $g_1\colon\mathbb F_2^n\to\mathbb F_2^n$, and an output function $f_1\colon\mathbb F_2^n\to\mathbb F_2$. The second one is a non-autonomous automaton $A_2=(\mathbb F_2,\mathbb F_2^n,\mathbb F_2,g_2,f_2)$ with the state set $\mathbb F_2^m$, $m>1$, the input and output alphabets $\mathbb F_2$, an output function $f_2\colon\mathbb F_2\times\mathbb F_2^n\to\mathbb F_2$, and a transition function $g_2\colon\mathbb F_2\times\mathbb F_2^m\to\mathbb F_2^m$, for which there exist a map $g\colon\mathbb F_2^m\to\mathbb F_2^m$ and some different integers $\delta$ and $\tau$ such that, for all $u\in\mathbb F_2$ and $y\in\mathbb F_2^m$, $g_2(u,y)=\neg ug^\delta(y)+ug^\tau(y)$, where $g^0(y)=y$ and $g^r(y)=g(g^{r-1}(y))$ for every integer $r\geq1$. Thus, the generator $G$ is a finite autonomous automaton $G=A_1\cdot A_2=(\mathbb F_2^n\times\mathbb F_2^m,\mathbb F_2,h, f)$, where $h\colon\mathbb F_2^n\times\mathbb F_2^m\to\mathbb F_2^n\times\mathbb F_2^m$ and $h(x,y)=(g_1(x),g_2(f_1(x),y))$, $f\colon\mathbb F_2^n\times\mathbb F_2^m\to\mathbb F_2$ and $f(x,y)=f_2(f_1(x),y)$, $x\in\mathbb F_2^n$, $y\in\mathbb F_2^m$. As we see, all the functions in the definition of $G$ are Boolean ones, and the functions $g_1$ and $g_2,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 $f_1$ and $f_2$ are denoted by $C_1$ and $C_2$ respectively. At any time moment $t=1,2,\dots$, the automaton $A_1$ goes from its state $x(t)$ to a state $x(t+1)=g_1(x(t))$ and produces an output symbol $u(t)=f_1(x(t))$, the automaton $A_2$ receives $u(t)$ and goes from its state $y(t)$ to a state $y(t+1)=g_2(u(t),y(t))$ and produces an output symbol $z(t)=f_2(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_1,g_1,f_2,g_2,g,\delta,\tau\}$. The cryptanalysis problem for $G$ is the following: given a finite beginning $\gamma=z(1)z(2)\dots 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 $\gamma$ with the initial states and values of transition and output functions in automata $A_1$ and $A_2$. It is shown that in $G$ with the linear $A_2$, 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_1$) with the complexity $2^n$ which is much less than $2^{n+m}$ – the complexity of the bruitforce attack. For an arbitrary $G$ with the known $g_2$ and $f_2$, a method is proposed allowing to compute from $\gamma$ a string of the output sequence $\beta=u(1)u(2)\dots u(l)$ of $A_1$ 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^m$ or 2) to reduce the cryptanalysis problem for $G$ to the cryptanalysis problem for $A_1$, that is, to determine the key of $A_1$ by $\beta$. The complexity of the method is polynomial if $y(1)$ is not included in the key and is not more than $2^m$ otherwise. In case when the key of an arbitrary $G$ is $f_1$, this key can be determined by identifying $f_1$ with a function $f\in C_1$ satisfying the equalities $f(x(t))=u(t)$, $t=1,2,\dots,l$. Similarly, if the key of $G$ is $f_2$, the determination of $f_2$ is reduced to the construction of a function $f\in C_2$ satisfying the equalities $f(u(t),y(t))=z(t)$, $t=1,2,\dots,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.

Détail

Keywords: finite automaton, cryptographic generator, $(\delta,\tau)$-step generator, linearization attack, “devide and solve” attack, “devide–solve–substitute” attack, “meet-in-the middle” attack.
Mots-clés : cryptanalysis

Bibliographie

[1] Fomichev V. M., Discrete Mathematics and Cryptology, DIALOG-MEPhI Publ., Moscow, 2003, 400 pp. (in Russian)

[2] Agibalov G. P., Pankratova I. A., “To cryptanalysis of 2-cascade finite automata cryptographic generators”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2016, no. 9, 41–43 | DOI

[3] Agibalov G. P., “Logical equations in cryptanalysis of key stream generators”, Vestnik TSU. Prilozhenie, 2003, no. 6, 31–41 (in Russian)

[4] Agibalov G. P., “Methods for solving systems of polynomial equations over a finite field”, Vestnik TSU. Prilozhenie, 2006, no. 17, 4–9 (in Russian)

[5] Pankratova I. A., Boolean Functions in Cryptography, A Tutorial, TSU Publ., Tomsk, 2014, 88 pp. (in Russian)

[6] Tokareva N. N., Symmetric Cryptography. Short Course, A Tutorial, NSU Publ., Novosibirsk, 2012, 234 pp. (in Russian)

[7] Agibalov G. P., “Some completions of partial Boolean function”, Trudy SPhTI, 49, 1970, 12–19 (in Russian)

[8] Agibalov G. P., Sungurova O. G., “Cryptanalysis of a finite-state keystream generator with an output function as a key”, Vestnik TSU. Prilozhenie, 2006, no. 17, 104–108 (in Russian)