Mathematical Methods of Cryptography

Flaws of hypercube-like ciphers

D. I. Trifonov

Academy of Cryptograhy of Russian Federation, Moscow, Russia

Abstract: 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$.

Keywords: XSLP-ciphers, cryptoanalysis, linear method, branch numbers, hypercube structure.

UDC: 519.719.2+512.542.74

DOI: 10.17223/20710410/57/4