This article is cited in
5 papers
Mathematical Methods of Cryptography
About $2$-cascade finite automata cryptographic generators and their cryptanalysis
G. P. Agibalov,
I. A. Pankratova National Research Tomsk State University, Tomsk, Russia
Abstract:
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.
Keywords:
finite automaton, cryptographic generator, $(\delta,\tau)$-step generator, cryptanalysis, linearization attack, “devide and solve” attack, “devide–solve–substitute” attack, “meet-in-the middle” attack.
UDC:
519.7
DOI:
10.17223/20710410/35/4