Distinguishing attacks on block ciphers by~differentials of two-block texts

O. V. Denisov

Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 43-62.

Résumé

We present the observation model (random two-block texts encrypted on random independent keys) such that differential distinguishing attacks completely correspond to the generally accepted schemes of their statistical calculation. In this model, we get low bounds for data complexity of multiple differential distinguishing attacks. Let $n$ be the block size, $M=2^n-1$, $D(a)$ be a set of high-probabilily output differences at a fixed input difference $a\in\mathbb{Z}_2^n$ in $R$-round encryption, $P_1=\dfrac{|D(a)|}{M} P_2=\textstyle\sum\limits_{b\in D(a)} p_{a,b}^{(R)} \le \dfrac{1}{2}$. Let $\nu(D(a))$ be the number of these differences appearances. Suppose the attack is based on statistics $\nu(D(a))$ and have error probabilities $\alpha,\beta\in(0,1/2)$. Then attack needs $N_{1,a*}> N_{2,a*}=\dfrac{4P_1 (1-P_1)(1-\alpha-\beta)^2}{(P_2-P_1)^2}$ two-block texts. In particulary, in the case of $D(a)=\{b\}$, $1/M p_{a,b}^{(R)}\le 1/2$, we have low bound $ N_{2,a,b*}= \dfrac{4\left(1-1/{M}\right)(1-\alpha-\beta)^2}{M\left(p_{a,b}^{(R)}-1/{M}\right)^2}$. Consequently, the frequently used estimate $O(1/p_{\max})$ for data complexity is not enough for successful attack at small values of $(p_{\max}-1/{M})$, where $p_{\max}$ is the maximal transition probability of differentials. We also get asymptotic estimates for data complexity of the most powerful criterion (MPC) in the case of converging hypotheses. Let $\rho(a,R)=\big|\mathbb{P}_a^{(R)}-\dfrac1M 1\big|$ is the Euclidean distance from the row $\mathbb{P}_a^{(R)}$ of transition probabilities matrix to the uniform distribution vector. Suppose $\max_{b\ne 0} |p_{a,b}^{(R)}M-1|\to 0$ in the series scheme with a growing $R$, $ N(R)\sim N_{\rm MPC}(R,a)=\dfrac{(\kappa_{1-\alpha}+\kappa_{1-\beta})^2} {M \rho^2(a,R)}$. Then MPC errors tend to $\alpha$, $\beta$ (for some criteria bounds). We make experiments with Markov models of SmallPresent cipher for block size up to $n=28$ bits and $R=10$ rounds: we find inpute differences that minimize $N_{\rm MPC}(R,a)$ and we calculate empirical error probabilities for this number of texts.

Détail

Keywords: multiple differential cryptanalysis, distinguishing attack, two-block texts model, Kullback — Leibler divergence, converging hypotheses, capacity, Markov cipher, SmallPresent.

Bibliographie

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

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

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

[4] Blondeau C., Gérard B., “Multiple differential cryptanalysis: theory and practice”, FSE-2011, LNCS, 6733, 2011, 35–54 | Zbl

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

[6] Ambrosimov A. S., “Limit theorems for error probabilities of the first and second genera the most powerful test for two converging hypotheses regarding the probabilities of polynomial scheme outcomes in a series scheme”, Additional Chapters of Probability Theory. Educational and Methodical Manual, eds. A. S. Ambrosimov, Yu. I. Gromak, I. A. Kruglov, B. V. Stolpakov, M., 1992, 24–34 (in Russian)

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

[8] Kullback S., Information Theory and Statistics, John Wiley and Sons, 1959 | MR | Zbl

[9] Shiryaev A. N., Probability, Nauka Publ., M., 1989, 640 pp. (in Russian)

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

[11] Selçuk A. A., “On probability of success in linear and differential cryptanalysis”, J. Cryptology, 21:1 (2008), 131–147 | DOI | MR | Zbl

[12] Blondeau C., Gérard B., Tillich J., “Accurate estimates of the data complexity and success probability for various cryptanalyses”, Designs, Codes and Cryptography, 59 (2011), 3–34 | DOI | MR | Zbl

[13] Kruglov I. A., “Estimation of convergence rate to uniform distribution for products of finite group elements controlled by Markov chain”, Matematicheskie Voprosy Kriptografii, 5:1 (2014), 85–94 (in Russian) | DOI

[14] Hermelin M., Cho J., Nyberg K., “Multidimensional extension of Matsui's algorithm 2”, FSE-2009, LNCS, 5665, 2009, 209–227 | Zbl

[15] Leander G., Small Scale Variants of the Block Cipher PRESENT, Technical University of Denmark, 2010 http://eprint.iacr.org/2010/143.pdf

[16] http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=56552

[17] Albrecht M., Leander G., An All-in-one Approach to Differential Cryptanalysis for Small Block Ciphers, Cryptology ePrint Archive, Report 2012/401, , 2012 http://eprint.iacr.org