On mathematical models of key mixing for iterative block encryption algorithms

D. A. Romanko ; V. M. Fomichev

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 93-96.

Résumé

For a binary symmetric iterative block encryption algorithm $\mathcal A$ with $r$ rounds, the following notation is used: $k$ is a key of $\mathcal A$, $k\in V_l=[\operatorname{GF}(2)]^l$; $x=x_1x_2\dots x_n$ is an information block, $x\in V_n$; $q$ is a round key, $q\in V_\lambda$; $\phi(x,q)$ is the round function; $q_i$ is an $i$-th round key, $i\in\{1,2,\dots,r\}$; $\phi_{q_i}\colon V_n\to V_n$ is the $i$-th round substitution, $\phi_{q_i}(x)=\phi(x,q_i)$; $\Phi_p=\phi_{q_p}\cdot\dots\cdot\phi_{q_1}$ is the $p$-round substitution, $p\in\{1,\dots,r\}$; $\rho$ is the minimal $p$ (if exists) such that every bit in $k$ is an essential argument for the function $\Phi_p$; $p(q_i)$, the exponent of $q_i$, and $p(k)$, the exponent of $k$, are the least $p$ (if exist) such that every coordinate function of $\Phi_p$ essentially depends on each bit in $q_i$ and $k$ respectively; $A$ is a Boolean matrix $(a_{ij})_{n\times n}$, where $a_{ij}=1$ iff $j$-th coordinate function of $\phi(x,q)$ essentially depends on $x_i$, $i\in\{1,\dots,n\}$; matrix $A^t(I*)$ is obtained from $A^t$ by removing rows with the numbers which aren't in a set $I$, $\emptyset\neq I\subseteq\{1,\dots,n\}$; $I*$-$\exp A$ is the (local) $I*$-exponent of $A$, that is, the least integer $\gamma$ (if exists) such that, for any $t\geq\gamma$, the matrix $A^t(I*)$ consists of positive integers; $B_{q_i}$ is the set of numbers of coordinates in $k$ which $q_i$ essentially depends on. Let $B_{q_i}\cap B_{q_j}=\emptyset$ for all $i,j\in\{1,\dots,\rho\}$, $i\neq j$. Then the following statements are true: 1) if $\Phi_r(x,k)$ depends on each bit of $k$, then $p(k)=p(1)+(\rho-1)$ and $p(q_i)=p(1)+(i-1)$, $i=1,\dots,\rho$; 2) if $\{1,\dots,l\}=B_{q_1}\cup\dots\cup B_{q_\rho}$, $n=\lambda$, and $h$ and $h'$ are any substitutions on $V_\lambda$, then $p(k)\geq I*$-$\exp A+(\rho-1)$ for $I=\{1,\dots,n\}$ in case $\phi(x,q)=h(x\oplus q)$ and for $I=\{1\}$ in case $\phi(x,q)=h'((x+q)\mod2^\lambda)$. As a consequence, if $\mathcal A$ is the Feistel algorithm, where $x=x'x''$, $|x'|=|x''|=n/2$, and $\phi(x,q)=(x'',x'\oplus\psi(x'',q))$, then $p(k)\geq I*$-$\exp A+(\rho-1)$ for $I=\{n/2+1,\dots,n\}$ in case $\psi(x'',q)= h(x''\oplus q)$ and for $I=\{n/2+1\}$ in case $\psi(x'',q)=h'((x''+q)\mod2^\lambda)$. Particularly, $p(k)\geq10$ for GOST 28147-89.

Détail

Keywords: iterative block encryption algorithm, local exponent, key exponent.

Bibliographie

[1] Fomichev V. M., Melnikov D. A., Kriptograficheskie metody zaschity informatsii. Ch. 1. Matematicheskie aspekty, v 2 ch., Izdatelstvo Yurait, M., 2016, 209 pp.

[2] Kyazhin V. M., Fomichev V. M., “Lokalnaya primitivnost grafov i neotritsatelnykh matrits”, Prikladnaya diskretnaya matematika, 2014, no. 3(25), 68–80