Flaws of hypercube-like ciphers

D. I. Trifonov

Prikladnaâ diskretnaâ matematika, no. 3 (2022), pp. 52-66.

Résumé

A class of block XSLP cryptographic algorithms called “hypercube” is considered. These algorithms have a block size ${n=n' \cdot m = n' \cdot m' \cdot k}$ bits. A hypercube-like algorithm is an iterative block algorithm consisted of four main operations: (1) key addition (by XOR), (2) $n'$-bit S-box application, (3) block-diagonal diffusion matrix $\mathrm{diag}\,(A_1,\ldots,A_k)$, $A_i \in \text{GF}(2)_{n'm',n'm'}$, multiplication with diffusion degree $\rho$, and (4) permutation. The main results are the following: 1) the idea of constructing linear correlations and probabilities of distribution of differences, determined by hypercube-like algorithms, has been described; 2) the linear environment propagation index for any number of rounds has been evaluated; 3) the relevance of branch number $\theta(r)$ for differential trails probability and correlation of linear trails for any $r \in \mathbb{N}$, $r\geq 2$, rounds has been formally represented; 4) for hypercube-like algorithms, it is shown that when constructing a $\mathrm{P}$-transform using de Bruijn graphs, the avalanche effect may not occur, which means that the (time) complexity of determining the encryption key will be much less than the exhaustive key search (time) complexity. Let $n=n' (m')^d$ and $\mathrm{P}:V_n \to V_n$ affect $a=(a_0, \ldots, a_{m-1}) \in V_{n}$, $a_i \in V_{n'}$, as follows. Numbers $l \in \{ 0, \ldots, (m')^d-1 \}$ of $a_l \in V_{n'}$ in $a \in V_n$ are considered as $l= j_0 + j_1 m' + \ldots + j_{d-1} (m')^{d-1}$, $j_t = 0,\ldots,m'-1$, $t=0,\ldots,d-1$. Let the mapping $\mathrm{P}$ is defined as $\mathrm{P}(a)=\mathrm{P}(a_0, \ldots, a_{(m')^d-1})= (a_{\tau(0)}, \ldots, a_{\tau((m')^d-1)}),$ $\tau \in S_{(m')^d}$, $\tau(l)= \tau(j_0,\ldots,j_{d-1})$, $l=1,\ldots,(m')^d$. In the case $d=3$ it is obtained that if $\mathrm{P}$ is rotation of hypercube, i.e., $\tau(j_0,j_{1},j_2)= (j_1,j_2,j_0)$, then $\theta(r) \leq t(r)$, $t(1) = m'$, $ t(r) = ((m')^2 + m') \left[ {r}/{2} \right] + m' (r \bmod{2}), $ $r\geq2$. In the case $\tau(i_0,i_1,i_2)= (i_0, i_1+i_0\bmod{m'},i_2+i_0\bmod{m'}) $ we obtain $\theta(r) = \theta(r-4) + \rho^2$, $\theta(1) = 1$, $\theta(2) = \rho$, $\theta(3) = 2\rho -1$, $r\in \mathbb{N}$, $r>4$.

Détail

Keywords: XSLP-ciphers, cryptoanalysis, linear method, branch numbers
Mots-clés : hypercube structure.

Bibliographie

[1] Trifonov D. I. and Fomin D. B., “Invariant subspaces in SPN block c ipher”, Prikladnaya Diskretnaya Matematika, 2021, no. 54, 59–77 (in Russian)

[2] GOST R 34.12-2015. Information Technology. Cryptographic Information Protection. Block ciphers, Standartinform, M., 2015 (in Russian)

[3] Burov D. A. and Pogorelov B. A., “An attack on 6 rounds of KHAZAD.”, Matem. Vopr. Kriptogr., 7:2 (2016), 35–46 | MR | Zbl

[4] Gluhov M. M., Elizarov V. P., and Nechaev A. A., Algebra, v. 1, Gelios ARV Publ., M., 2003, 336 pp. (in Russian)

[5] Gluhov M. M., Elizarov V. P., and Nechaev A. A., Algebra, v. 2, Gelios ARV Publ., M., 2003, 416 pp. (in Russian)

[6] Malyshev F. M. and Tarakanov V. E., “Generalized de Bruijn graphs”, Matem. Zametki, 62:4 (1997), 540–548 (in Russian) | Zbl

[7] Daemon J. and Rijmen V., The Design of Rijndael: AES — The Advanced Encryption Standard, Springer, Berlin–Heidelberg, 2002, 238 pp. | MR

[8] Erokhin A. V., Malyshev F. M., and Trishin A. E., “Multidimensional linear method and diffusion characteristics of linear medium of ciphering transform”, Matem. Vopr. Kriptogr., 8:4 (2017), 29–62 (in Russian) | MR | Zbl

[9] Advanced Encryption Standard (AES), 2001 https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.197.pdf

[10] GOST R 34.11-2012. Information Technology. Cryptographic Information Protection. Hash Function, Standartinform, M., 2012 (in Russian)

[11] Brown L., Kwan M., Pieprzyk J., and Seberry J., “Improving resistance to differential cryptanalysis and the redesign of LOKI”, LNCS, 739, 1993, 36–50 | Zbl

[12] Knudsen L. R., “Cryptanalysis of LOKI”, LNCS, 739, 1993, 22–35 | Zbl

[13] Data Encryption Standard (DES). NIST FIPS PUB 46, 1977

[14] Massey J. L., “SAFER K-64: A byte-oriented block-ciphering algorithm”, LNCS, 809, 1994, 1–17 | Zbl

[15] Massey J. L., “SAFER K-64: One year later”, LNCS, 1008, 1995, 212–241 | Zbl

[16] Feistel N., “Cryptography and computer privacy”, Scientific Amer., 228:5 (1973), 15–23 | DOI

[17] Malyshev F. M., “The duality of differential and linear methods in cryptography”, Matem. Vopr. Kriptogr., 5:3 (2014), 35–48 (in Russian)

[18] Malyshev F. M. and Trishin A. E., “Linear and differential cryptanalysis: Another viewpoint.”, Matem. Vopr. Kriptogr., 11:2 (2020), 83–98 | MR | Zbl

[19] Malyshev F. M. and Trifonov D. I., “Diffusion properties of XSLP-ciphers”, Matem. Vopr. Kriptogr., 7:3 (2016), 47–60 (in Russian) | MR | Zbl

[20] Fedchenko V. A., “Diffusion rates of linear medium in AES-like ciphers”, Matem. Vopr. Kriptogr., 8:3 (2017), 109–126 (in Russian) | MR | Zbl