Criteria for Markov block ciphers

O. V. Denisov

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 28-37

Résumé

We study probabilistic models of block ciphers with random independent identically distributed round keys. We call they by Markov ciphers if sequence of round differentials is a simple homogeneous Markov chain. Criteria and sufficient condition for this property are adjusted and generalized. Particularly, we prove that, for an iterative $r$-round block cipher with group operation on the set $\mathcal X$ of blocks and round function $g$, the following four conditions are equivalent: 1) for any plaintext of two blocks $(X,X^*)$, the sequence of random round differentials $\Delta X=X^*X^{-1}$, $\Delta X(1)=X^*(1)X(1)^{-1},\ldots,\Delta X(r)=X^*(r)X(r)^{-1}$ is a homogeneous Markov chain under any distribution of $(X,X^*)$; 2) for all $a\in\mathcal X\setminus\{e\}$, the distribution of $g(ax)g(x)^{-1}$ doesn't depend on $x\in\mathcal X$; 3) $\forall a\in\mathcal X\setminus\{e\}$, $x\in\mathcal X$ $(g(ax)g(x)^{-1}\sim g(aX)g(X)^{-1})$ under any distribution of $X$; 4) $\forall x\in\mathcal X$ $(g(\Delta X\, x)g(x)^{-1}\sim g(\Delta X\,X)g(X)^{-1})$ under any distribution of $(X,\Delta X)$. The class of Markov ciphers constructed in Lai's dissertation is expanded. We give sufficient conditions under which formula for the transition probabilities matrix of the expanded class contains tensor product of S-box transition probabilities matrices.

Détail

Keywords: Markov ciphers, transition probabilities of differentials.
Mots-clés : random permutations

Bibliographie

[1] Lai X., Massey J., Murphy S., “Markov ciphers and differential cryptanalysis”, Eurocrypt-1991, LNCS, 547, 1991, 17–38 | MR | Zbl

[2] Pogorelov B. A., Pudovkina M. A., “Partitions on bigrams and Markov property of block ciphers”, Matematicheskie Voprosy Kriptografii, 8:1 (2017), 107–142 (in Russian) | DOI | MR

[3] Kemeny J. G., Snell J. L., Finite Markov Chains, The University Series in Undergraduate Mathematics, Van Nostrand, Princeton, 1960, 271 pp. | MR | MR | Zbl

[4] Lai X., On the Design and Security of Block Ciphers, Dissertation for the degree of Doctor of Technical Sciences, Swiss Federal Institute of Technology, Zurich, 1992, 118 pp.

[5] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, CRYPTO-1990, LNCS, 537, 1991, 2–21 | MR | Zbl

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

[7] Gluhov M. M., “On mixing linear transforms for block ciphers”, Matematicheskie Voprosy Kriptografii, 2:2 (2011), 5–40 (in Russian) | DOI

[8] Drelikhov V. O., Nikiforov M. S., “On Markov properties of averaged difference characteristics of iterative block ciphers”, Proc. RUSCRIPTO-2017, 2017 (in Russian) https://www.ruscrypto.ru/resource/archive/rc2017/files/02_drelikhov_nikiforov.pdf

[9] Aleksejchuk A. N., “Upper limits of parameters characterizing the stability of non-Markov block ciphers with respect to the methods of difference and linear cryptanalysis”, Naukovo-tekhnichnij zhurnal “Zahist Informacii”, 2006, no. 3, 20–28 (in Russian)

[10] Koval'chuk L. V., “Generalized Markov ciphers: construction of estimates of practical resistance to differential attacks”, Proc. 2nd Intern. Conf. on Security and Counter-Terrorism (October 25–26, 2006), MCCME Publ., Moscow, 2006 (in Russian)

[11] Lisickaya I. V., Dolgov V. I., “Block symmetric ciphers and Markov processes”, Prikladnaya Radioehlektronika, 11:2 (2012), 137–143 (in Russian)