SIBCiphers~-- symmetric iterative block ciphers composed of Boolean functions depending on small number of variables

G. P. Agibalov

Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 43-48.

Résumé

A class of symmetric iterative block ciphers called SIBCiphers is defined. Each round of a cipher in this class encrypts bitstrings of length $n$ into bitstrings of length $n$ according to a system of $n$ Boolean functions each depending on $k\leq n$ arguments taken from the bitstring on the inputs of the round and jointly representing an injective mapping. Formally, for $l$-th round in a $r$-round SIBCipher, there exist an injection $g^{(l)}\colon\{0,1\}^n\to\{0,1\}^n$, Boolean functions $g_i^{(l)}\colon\{0,1\}^k\to\{0,1\}$, and mappings $\eta_i^{(l)}\colon\{1,2,\dots,k\}\to\{1,2,\dots,n\}$, $i=1,2,\dots,n$, such that $\{\eta_i^{(l)}(j)\colon i=1,2,\dots,n;\ j=1,2,\dots,k\}=\{1,2,\dots,n\}$ and if $u=u_1u_2\dots u_n\in\{0,1\}^n$, then $g^{(l)}(u)=g_1^{(l)}(v_1)g_2^{(l)}(v_2)\dots g_n^{(l)}(v_n)$, where $v_i=u_{i_1}u_{i_2}\dots u_{i_k}$ and $i_j=\eta_i^{(l)}(j)$, $i=1,2,\dots,n$; $j=1,2,\dots,k$. A round key consists of some of Boolean functions ($g_i^{(l)}$) at the round and of numbers ($\eta_i^{(l)}(j)$) of their actual arguments. The ciphertext bitstring is obtained by permuting the bits on the outputs of the last ($r$-th) round. Contemporary symmetric iterative block ciphers with additive round keys form a subclass of SIBCiphers. Two other subclusses of SIBCiphers called by names Lucifer and Feistel are constructed according to the known cryptographic schemes originally suggested by H. Feistel and implemented in ciphers LUCIFER and DES respectively. In SIBCipher of Feistel's subclass, $g^{(l)}(u)=L_1R_1$ if $u=L_0R_0$ for $L_0,R_0\in\{0,1\}^{n/2}$, $L_1=R_0$ and $R_1=p^{(l)}(L_0)\oplus f^{(l)}(R_0)$, where $p\colon\{0,1\}^{n/2}\to\{0,1\}^{n/2}$ is a permutation and, for $z=R_0$, $f^{(l)}(z)=f_1^{(l)}(v_1)f_2^{(l)}(v_2)\dots f_{n/2}^{(l)}(v_{n/2})$, $v_i=z_{i_1}z_{i_2}\dots z_{i_k}$, and $i_j=\eta_i^{(l)}(j)$ for some Boolean functions $f_i^{(l)}\colon\{0,1\}^k\to\{0,1\}$ and for a surjective system of mappings $\eta_i^{(l)}\colon\{1,2,\dots,k\}\to\{1,2,\dots,n/2\}$, $i=1,2,\dots,n/2$; $j=1,2,\dots,k$. SIBCipher of the subclass Lucifer is characterized by the folloving properties: (a) $n=ks$, $s >1$; (b) for any pair $(l,i)$, $l=1,2,\dots,r$ and $i=1,2,\dots,s$, the mapping $G_i^{(l)}\colon\{0,1\}^k\to\{0,1\}^k$ defined as $G_i^{(l)}(z)=g^{(l)}_{(i-1)k+1}(z)g^{(l)}_{(i-1)k+2}(z)\dots g^{(l)}_{ik}(z)$ for all $z\in\{0,1\}^k$, is a substitution; (c) $\eta^{(l)}_{(i-1)k+1} =\eta^{(l)}_{(i-1)k+2}=\dots=\eta^{(l)}_{ik}$; and (d) the mapping $p^{(l)}\colon\{0, 1\}^n\to\{0,1\}^n$, where $p^{(l)}(u)=p^{(l)}_1(u)p^{(l)}_2(u)\dots p^{(l)}_s(u)$ and $p^{(l)}_i(u)=u_{\eta^{(l)}_{ik}(1)}u_{\eta^{(l)}_{ik}(2)}\dots u_{\eta^{(l)}_{ik}(k)}$ for $i=1,2,\dots,s$, is a permutation.

Détail

Keywords: cryptography, Boolean functions, symmetric iterative block ciphers, Feistel network, cipher LUCIFER.

Bibliographie

[1] Khoffman L. Dzh., Sovremennye metody zaschity informatsii, Sov. radio, M., 1980, 264 pp.

[2] Agibalov G. P., “Metody resheniya sistem polinomialnykh uravnenii nad konechnym polem”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2006, no. 17, Avgust, 4–9

[3] Courtois N., Pieprzyk J., “Cryptanalysis of block ciphers with overdefined systems of equations”, ASIACRYPT 2002, LNCS, 2501, 2002, 267–287 | MR | Zbl

[4] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 4:1 (1991), 3–72 | DOI | MR | Zbl

[5] Agibalov G. P., “Elementy teorii differentsialnogo kriptoanaliza iterativnykh blochnykh shifrov s additivnym raundovym klyuchom”, Prikladnaya diskretnaya matematika, 2008, no. 1(1), 34–42

[6] Agibalov G. P., Pankratova I. A., “Statisticheskie analogi diskretnykh funktsii i ikh primenenie v kriptoanalize simmetrichnykh shifrov”, Prikladnaya diskretnaya matematika, 2010, no. 3(9), 51–68

[7] Matsui M., “Linear cryptanalysis method for DES cipher”, LNCS, 765, 1993, 386–397

[8] Matsui M., “The first experimental cryptanalysis of the Data Encryption Standard”, LNCS, 839, 1994, 1–11 | Zbl

[9] Agibalov G. P., “Raspoznavanie operatorov, realizuemykh v avtonomnykh avtomatakh”, Konf. po teorii avtomatov i iskusstvennomu myshleniyu, Annotatsii dokladov i programma (Tashkent, 27–31 maya 1968), VTs AN SSSR, M., 1968, 7–8

[10] Agibalov G. P., Levashnikov A. A., “Statisticheskoe issledovanie zadachi opoznaniya bulevykh funktsii odnogo klassa”, Tez. dokl. k Vsesoyuznomu kollokviumu po avtomatizatsii sinteza diskretnykh vychislitelnykh ustroistv (20–25 sentyabrya 1966), Novosibirsk, 1966, 40–45

[11] Agibalov G. P., “Minimizatsiya chisla argumentov bulevykh funktsii”, Problemy sinteza tsifrovykh avtomatov, Nauka, M., 1967, 96–100

[12] Agibalov G. P., “O nekotorykh doopredeleniyakh chastichnoi bulevoi funktsii”, Trudy Sibirskogo fiziko-tekhnicheskogo instituta, Problemy kibernetiki, 49, 1970, 12–19

[13] Agibalov G. P., Sungurova O. G., “Kriptoanaliz konechno-avtomatnogo generatora klyuchevogo potoka s funktsiei vykhodov v kachestve klyucha”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2006, no. 17, Avgust, 104–108

[14] V. V. Yaschenko (red.), Vvedenie v kriptografiyu, MTsNMO, “CheRo”, M., 1998, 272 pp.

[15] Pankratova I. A., Bulevy funktsii v kriptografii, Ucheb. posobie, Izdatelskii Dom Tomskogo gosudarstvennogo universiteta, Tomsk, 2014, 88 pp.