Substitution block ciphers with functional keys

We define a substitution block cipher $\mathcal C$ with the plaintext and ciphertext blocks in $\mathbb F_2^n$ and with the keyspace $K_{s_0,n}(g)$ that is the set $\{f(x)\colon f(x)=\pi_2(g^{\sigma_2}(\pi_1(x^{\sigma_1})));\ \sigma_1,\sigma_2\in\mathbb F_2^n;\ \pi_1,\pi_2\in S_n\}$, where $s_0$ is an integer, $1\leq s_0\leq n$; $g\colon\mathbb F_2^n\to\mathbb F_2^n$ is a bijective vector function $g(x)=g_1(x)g_2(x)\dots g_n(x)$ such that every its coordinate function $g_i(x)$ essentially depends on some $s_i\leq s_0$ variables in the string $x=x_1x_2\dots x_n$; $S_n$ is the set of all permutations of the row $(1\ 2\dots n)$; $\pi_i$ and $\sigma_i$ are the permutation and negation operations, that is, $(\pi=(i_1i_2\dots i_n))\Rightarrow(\pi(a_1a_2\dots a_n)=a_{i_1}a_{i_2}\dots a_{i_n})$, $(\sigma=b_1b_2\dots b_n)\Rightarrow((a_1a_2\dots a_n)^\sigma=a_1^{b_1}a_2^{b_2}\dots a_n^{b_n})$ and, for $a$ and $b$ in $\mathbb F_2$, $a^b=a$ if $b=1$ and $a^b=\neg a$ if $b=0$. Like $g$, any key $f$ in $K_{s_0,n}(g)$ is a bijection on $\mathbb F_2^n$, $f(x)=f_1(x)f_2(x)\dots f_n(x)$, and every its coordinate function $f_i(x)$ essentially depends on not more than $s_0$ variables in $x$. The encryption of a plaintext block $x$ and the decryption of a ciphertext block $y$ on the key $f$ are defined in $\mathcal C$ as follows: $y=f(x)$ and $x=f^{-1}(y)$. Here, we suggest a known plaintext attack on $\mathcal C$ with the threat of discovering the key $f$ that was used. Let $P_1,P_2,\dots,P_m$ be some blocks of a plaintext, $C_1,C_2,\dots,C_m$ be the corresponding blocks of a ciphertext, i.e., $C_l=f(P_l)$ for $l=1,2,\dots,m$, and $P_l=P_{l1}P_{l2}\dots P_{ln}$, $C_l=C_{l1}C_{l2}\dots C_{ln}$. The object is to determine the coordinate function $f_i(x)$ of $f$ for each $i\in\{1,2,\dots,n\}$. The suggested attack consists of two steps, namely we first determine the essential variables $x_{i_1},\dots,x_{i_s}$ of $f_i(x)$ and then compute a Boolean function $h(x_{i_1},\dots,x_{i_s})$ such that $h(a_{i_1},\dots,a_{i_s})=f_i(a_1,\dots,a_n)$ for all $n$-tuples $(a_1a_2\dots a_n)\in\mathbb F_2^n$. For determining the essential variables of $f_i$, we construct a Boolean matrix $\|\inf D(f_i)\|$ with the set of rows $\inf D(f_i)$, where $D(f_i)=\{P_l\oplus P_j\colon C_{li}\neq C_{ji};\ l,j =1,2,\dots,m\}$, $C_{li}=f_i(P_l)$, $l=1,\dots,m$, $i=1,\dots,n$, and $\inf D(f_i)$ is the subset of all the minimal vectors in $D(f_i)$. Then the numbers of essential variables for $f_i$ are the numbers of columns in the intersection of all covers of $\|\inf D(f_i)\|$ with the cardinalities not more than $s_0$, where a cover of a Boolean matrix $M$ is defined as a subset $C$ of its columns such that each row in $M$ has '1' in a column in $C$. For computing $h(x_{i_1},\dots,x_{i_s})$, we first set $h(P_{li_1},\dots,P_{li_s})=C_{li}$ for $l=1,\dots,m$ and then, if $h_i$ is not yet completely determined on $\mathbb F_2^s$, we increase the number $m$ of known blocks $(P_i,C_i)$ of plain- and ciphertexts or extend $h_i$ on $\mathbb F_2^s$ in such a way that the vector function $h=h_1h_2\dots h_n$ with the completely defined coordinate functions is a bijection on $\mathbb F_2^n$. We also describe some special known plaintext attacks on substitution block ciphers with keyspaces being subsets of $K_{s_0,n}(g)$.