Cryptautomata: definition, cryptanalysis, example

G. P. Agibalov

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 106-110.

Résumé

This conference paper is an extended abstract of a recent article in Prikladnaya Diskretnaya Matematika (2017, No. 36), where we presented the definition of the cryptautomata and described some cryptanalysis techniques for them. In cryptosystems, the cryptautomata are widely used as its primitives including cryptographic generators, s-boxes, filters, combiners, key hash functions as well as symmetric and public-key ciphers, and digital signature schemes. A cryptautomaton is defined as a class $C$ of automata networks of a fixed structure $N$ constructed by means of the series, parallel, and feedback connection operations over initial finite automata (finite state machines) with transition and output functions taken from some predetermined functional classes. A cryptautomaton key can include initial states, transition and output functions of some components in $N$. Choosing a certain key $k$ produces a certain network $N_k$ from $C$ to be a new cryptographic algorithm. In case of invertibility of $N_k$, this algorithm can be used for encryption. The operation (functioning) of any network $N_k$ in the discrete time is described by the canonical system of equations of its automaton. The structure of $N_k$ is described by the union of canonical systems of equations of its components. The cryptanalysis problems for a cryptautomaton are considered as the problems of solving the operational or structural system of equations of $N_k$ with the corresponding unknowns that are key $k$ variables and (or) plaintexts (input sequences). For solving such a system $E$, the method DSS is used. It is the iteration of the following three actions: 1) $E$ is Divided into subsystems $E'$ and $E''$, where $E'$ is easy solvable; 2) $E'$ is Solved; 3) the solutions of $E'$ are Substituted into $E''$ by turns. The definition and cryptanalysis of a cryptautomaton are illustrated by giving the example of the autonomous alternating control cryptautomaton. It is a generalization of the LFSR-based cryptographic alternating step generator. We present a number of attacks on this cryptautomaton with the states or output functions of its components as a key.

Détail

Keywords: finite automaton, automata network, alternating control cryptautomaton, “divide-and-solve-and-substitute”, partially defined function completion.
Mots-clés : cryptautomaton, cryptanalysis

Bibliographie

[1] Agibalov G. P., “Cryptautomata with functional keys”, Prikladnaya Diskretnaya Matematika, 2017, no. 36, pp, 59–72 (in Russian) | DOI

[2] Agibalov G. P., Pankratova I. A., “About 2-cascade finite automata cryptographic generators and their cryptanalysis”, Prikladnaya Diskretnaya Matematika, 2017, no. 35, 38–47 (in Russian) | DOI | MR

[3] Menezes A., van Oorshot P., Vanstone S., Handbook of Applied Cryptography, CRC Press Inc., 1997, 661 pp. | MR | Zbl

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