Cryptanalysis of $2$-cascade finite automata generator with functional key

I. V. Borovkova ; I. A. Pankratova ; E. V. Semenova

Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 48-56

Résumé

A cryptographic generator under consideration is a serial connection $G= A_1\cdot A_2$ of two finite state machines (finite automata) $A_1 = (\mathbb{F}_2^n,\mathbb{F}_2, g_1, f_1)$ (it is autonomous) and $A_2 = (\mathbb{F}_2,\mathbb{F}_2^n,\mathbb{F}_2, g_2, f_2)$. The key of the generator is the function $f_1$ and possibly the initial states $x(1),y(1)$ of the automata $A_1,A_2$. The cryptanalysis problem for $G$ is the following: given an output sequence $\gamma = z(1)z(2) \ldots z(l)$, find the generator's key. Two algorithms for analysis of $A_2$ are presented, they allow to find a preimage $u(1)\ldots u(l)$ of $\gamma$ in general case and in the case when $A_2$ is the Moore automaton with the transition function $g_2(u, y) = \neg ug^\delta(y) + ug^\tau(y)$ for some $g:\mathbb{F}_2^m\rightarrow\mathbb{F}_2^m$ and $\delta,\tau\in\mathbb{N}$. This preimage is an input to $A_2$ and an output from $A_1$. The values $u(t)$ equal the values $f_1(x(t))$ where $x(t)$ is the state of $A_1$ at a time $t$, $t=1,2, \ldots, l$. If the initial state $x(1)$ and a function class $C_1$ containing $f_1$ are known, then $f_1$ can be determined by its specifying in the class $C_1$.

Détail

Keywords: finite automaton, cryptographic generator, $(\delta, \tau)$-step generator, DSS method.
Mots-clés : cryptanalysis