Spectral probabilistic and statistical analysis of~Markov ciphers

O. V. Denisov

Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 12-31.

Résumé

Let an Abelian group $(\mathcal{X},+)$ be the alphabet of $R$-round Markov block cipher with matrix $\mathcal{P}$ of transition probabilities of differentials; matrix size equals $M=|\mathcal{X}'|$, $\mathcal{X}'=\mathcal{X}\setminus\{0\}$. Suppose spectrum of $\mathcal{P}$ satisfies the condition $\lambda_1=1>|\lambda_2|>|\lambda_3|\ge\ldots\ge\lambda_M$. 1. Extremal transition probabilities $p_{ab}(R)$ and rows $\mathcal{P}^R$ for a large number of rounds. Let $\mathcal{P}$ be diagonalizable: $B\mathcal{P} C=D=\mathrm{diag}(1,\lambda_2,\ldots,\lambda_M)$, $B=C^{-1}$, and there exist $a,b\in\mathcal{X}'$ such that $|C_{a2}|>|C_{i2}|$, $|B_{2b}|>|B_{jb}|$ for all $i\ne a$, $j\ne b$. Then $\mathop{\operatorname{arg\,max}}\limits_{(i,j)\in\mathcal{X}'\times\mathcal{X}'} |p_{ij}(R)-\frac1{M}|=(a,b)$ and $\mathop{\operatorname{arg\,max}}\limits_{i\in\mathcal{X}'} |\mathbf{P}_i^{(R)}-\frac1{M} \mathbf{1}|=a$ for all sufficiently large $R$, $p_{ab}(R)-\frac1{M}\sim C_{a2}B_{2b}\lambda_2^R$ and $|\mathbf{P}_a(R)-\frac1{M} \mathbf{1}| \sim |C_{a2}| |\mathbf{B}_2| |\lambda_2|^R$ as $R\to\infty$. 2. Distinguishing attack by independent full codebooks. Let the cipher with alphabet $\mathcal{X}=\mathbb{Z}_2^n$ be Markovian (provided random uniformly distributed set of round keys $\mathbf{k}\sim U(\mathscr{K}^R)$) with matrix $\mathcal{P}$, $z_i=z_i(\mathbf{k})$ be the result of block $i\in\mathcal{X}$ transformation either by cipher (hypothesis $H_2$) or random uniformly distributed substitution $z(\mathbf{k})$ (hypothesis $H_1$). Let $(\lambda_2,u)$ or $(\lambda_2,v)$ be left or right eigenpair of $\mathcal{P}$, $|u|=|v|=1$, $\mu_2(R)=\mathbf{u} \mathcal{P}^R v\downarrow\ne0$, $S(\mathbf{k})=M \sum\limits_{\{i,j\}\subset \mathcal{X}} u_{j-i} v_{z_j-z_i}$. We prove that mean and variance of statistic $S(\mathbf{k})$ equal $0$ and $M^2 \frac{M+1}{2(M-2)}$ respectively under hypothesis $H_1$. If sets $\mathbf{k}(1),\ldots,\mathbf{k}(N_b)\sim U(\mathscr{K}^R)$ are independent, $N_b\to\infty$, then for all $0\alpha1$ criterion $d: S'(N_b) \mathrm{sign}(\mu_2(R)) > \kappa_{1-\alpha}\sqrt{\frac{NM}{M-2}} \Longrightarrow H_2$, where $N=\dbinom{M+1}2 N_b$, has error probability $\alpha_1(d)\to\alpha$. We show that $\alpha_2(d)\approx \beta$ for large values of $R$ and $N_b\approx \frac{2(\kappa_{1-\alpha}+\kappa_{1-\beta})^2 }{(2^n \mu_2(R))^2}$.

Détail

Keywords: Markov block ciphers, distinguishing attack, matrix spectrum, transition probabilities of differentials, independent full codebooks.
Mots-clés : second dominant eigenvalue

Bibliographie

[1] Lai X., Massey J., Murphy S., “Markov ciphers and differential cryptanalysis”, LNCS, 547, 1991, 17–38 | 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) | Zbl

[3] Denisov O. V., “Criteria for Markov block ciphers”, Prikladnaya Diskretnaya Matematika, 2018, no. 41, 28–37 (in Russian) | Zbl

[4] Denisov O. V., “Spectral criterion for testing hypotheses about random substitutions”, Matematicheskie Voprosy Kriptografii, 7:3 (2016), 19–28 (in Russian) | Zbl

[5] Lankaster P., Theory of Matrices, Academic Press, N.Y.–London, 1969

[6] Al'pin Yu. A., Al'pina V. S., “Perron — Frobenius theorem: proof using Markov chains”, Zapiski Nauchnyh Seminarov POMI, 359, 2008, 5–16 (in Russian)

[7] Denisov O. V., “Distinguishing attacks on block ciphers by differentials of 2-blocks texts”, Prikladnaya Diskretnaya Matematika, 2020, no. 48, 43–62 (in Russian) | Zbl

[8] Albrecht M., Leander G., “An all-in-one approach to differential cryptanalysis for small block ciphers”, LNCS, 7707, 2013, 1–15 | Zbl

[9] Horn R., Johnson C., Matrix Analysis, Cambridge University Press, 1986

[10] Borovkov A. A., Probability Theory, URSS, M., 1999, 472 pp. (in Russian)

[11] 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.

[12] Xue W., Lin T., Shun X., et al., “On the estimation of the second largest eigenvalue of Markov ciphers”, Security Comm. Networks, 9 (2016), 2093–2099 | DOI

[13] Vaudenay S., “On the security of CS-cipher”, LNCS, 1636, 1999, 260–274 | Zbl