Cryptautomata with functional keys

G. P. Agibalov

Prikladnaâ diskretnaâ matematika, no. 2 (2017), pp. 59-72.

Résumé

In this paper, we describe the cryptautomata and some cryptanalysis techniques for them. In cryptographic systems, the cryptautomata are widely used as its primitives including key-stream generators, s-boxes, cryptofilters, cryptocombiners, key hash functions as well as symmetric and public-key ciphers, digital signature schemes. Here, 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$. The choosing a certain key $k$ produces a certain network $N_k$ from $C$ to be a 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 cryptautomaton with the alternative control. 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, cryptautomaton generator with alternative control, linearization attack, “devide-and-solve-and-substitute”, partially defined function completion.
Mots-clés : cryptautomaton, cryptanalysis

Bibliographie

[1] Agibalov G. P., “Finite automata in cryptography”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2009, no. 2, 43–73 (in Russian)

[2] Tao R., Finite Automata and Application to Cryptography., TSINGHUA University Press, 2009, 406 pp. | MR

[3] 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)

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

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

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

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

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

[9] 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)

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