Measuring block cipher round function security using spectral radii

In this post, we shall show how spectral radii and more specifically $L_{2,d}$ -spectral radii measure the security of block cipher round functions with small round key size and message size. This post will be mathematical, and it will incorporate subjects such as probability, linear algebra, and some quantum information theory. This post will be based on this previous post. We will leave the topics of algorithms for computing the $L_{2,d}$ -spectral radius, the results of such computations, and our estimates for the security level of block ciphers for future posts.

Suppose that $K,X$ are finite sets and $F:K\times X\rightarrow X$ is a function. For each $k\in K$ , define a mapping $F_k:X\rightarrow X$ by letting $F_k(x)=F(k,x)$ . We say that $F$ is a block cipher round function if $F_k$ is a bijection for each $k\in K$ . For our purposes, we shall assume all block ciphers are iterated block ciphers where a ciphertext is obtained from a plaintext simply by composing a sequence of round permutations and applying this sequence of round permutations to the plaintext.

In this post, we shall obtain from spectral radii calculations measures of security $M$ for block cipher round functions such that if $F:K\times X\rightarrow X,G:K\times Y\rightarrow Y$ are block cipher round functions, then $M(F)=M(G)$ whenever the structures $(K,X,F,(k)_{k\in K}),(K,Y,G,(k)_{k\in K})$ are isomorphic (here, we add a constant for each element in $K$ ). We shall also obtain measures of security $M$ where $M(F)=M(G)$ whenever $(J,X,F)$ and $(K,Y,G)$ are isomorphic.

These measures of security are most useful for block cipher round functions $F:K\times X\rightarrow X$ when $|K|,|X|$ are small since we will need to be able to compute the value of these measures of security. Since spectral radii are used to make conclusions about the behavior of block ciphers as the number of rounds approaches infinity, spectral radii are a more useful measure of security for block ciphers with a large number of rounds. Spectral radii calculations are best for evaluating the security of Hashspin-like round functions since for Hashspin, $|K|,|X|$ is small while many rounds of encryption are used. Unfortunately, if $|X|$ is too small, the block cipher round function $F$ is not usable to encrypt data, but the block cipher round function $F$ may still be used to construct a cryptocurrency proof of work problem.

Suppose that $F:K\times X\rightarrow X$ is a block cipher round function. Let $\phi:S_X\rightarrow GL(V)$ be a linear representation of the symmetric group $S_X$ . Then we shall write $\rho_{2,d}(\phi,F)$ for $\rho_{2,d}((\phi(F_k))_{k\in K})$ . If $U$ is a non-trivial invariant subspace of $V$ , and $d\geq\dim(U)$ , then $\rho_{2,d}(\phi,F)=|K|$ , so in this case, $\rho_{2,d}(\phi,F)$ does not tell us anything about the block cipher round function $F$ . However, if $d<\dim(U)$ for each non-trivial invariant subspace $U$ of $V$ , then a lower value of $\rho_{2,d}(\phi,F)$ indicates that the block cipher $\rho_{2,d}(\phi,F)$ is more secure. For this post, we shall therefore implicitly assume that $d<\dim(U)$ for each non-trivial invariant subspace $U$ of $V$ , and in practice $d$ will be much smaller than $\dim(U)$ for each non-trivial invariant subspace $U$ of $V$ (this is mainly because $\rho_{2,d}(\phi,F)$ is harder to compute when $d$ is larger).

If $(Z_k)_{k\in K}\in M_d(\mathbb{C})^K$ , and $\Gamma((\phi(F_k))_{k\in K},(Z_k)_{k\in K})=\rho_{2,d}((\phi(F_k))_{k\in K})$ , then $(Z_k)_{k\in K}$ inherits many properties of $(\phi(F_k))_{k\in K}$ , and one should consider $(Z_k)_{k\in K}$ to be one of the elements in $M_d(\mathbb{C})^K$ that is closest to $(\phi(F_k))_{k\in K}$ . Furthermore, $\rho_{2,d}(\phi,F)$ is a measure of how
‘close’ $(\phi(F_k))_{k\in K}$ is to the set $M_d(\mathbb{C})^K$ in the sense that a larger value of $\rho_{2,d}(\phi,F)$ means that the dynamics of $(\phi(F_k))_{k\in K}$ resembles the dynamics of some element of $M_d(\mathbb{C})^K$ more closely. For cryptographic security, we do not want the dynamics of $\rho_{2,d}(\phi,F)$ to resemble the dynamics of $M_d(\mathbb{C})^K$ , so we want the value of $\rho_{2,d}(\phi,F)$ to be small.

If $F:K\times X\rightarrow X$ is a function such that each $F_k$ is selected uniformly at random from $S_X$ and independently, $\phi:S_X\rightarrow\text{GL}(V)$ is an irreducible representation with $|V|>1$ , and $d<<\dim(V)$ , then experimental computations suggest that $\rho_{2,d}(\phi,F)$ will tend to be very close to $1$ . Therefore, if $F:K\times X\rightarrow X$ is a block cipher round function, then $F$ should resemble a system of random permutations, so $\rho_{2,d}(\phi,F)\approx 1$ suggests that the block cipher round function $F$ is secure, but if $\rho_{2,d}(\phi,F)>>1$ , then one should consider the block cipher round function $F$ to be insecure.

While $\rho_{2,d}(\phi,F)$ is a measure of security for the block cipher $F$ for all representations $\phi$ , since we have limited computational resources, we would like to compute or estimate $\rho_{2,d}(\phi,F)$ for the simplest representations. In particular, we would only like to compute or estimate $\rho_{2,d}(\phi,F)$ for $\phi:S_X\rightarrow GL(V)$ when the dimension of $V$ is minimized.

Let $K$ be a field. Let $R_{n,K}$ denote the ring of all matrices $A\in M_n(K)$ where there is some $r$ where the sum of each row and the sum of each column is $r$ . Define two subspaces $K_{h}^{n},K_{l}^{n}$ of $K^{n}$ by letting $K_{h}^{n}$ consist of all vectors $[x_{1},\dots,x_{n}]^{T}$ where $x_{1}+\dots+x_{n}=0$ and $K_{l}^{n}=\{\lambda[1,\dots,1]^{T}\mid\lambda\in K\}$ where the vector $[1,\dots,1]^{T}$ has $n$ ones. The subscripts $h,l$ stand for “hyperplane” and “line” respectively. Observe that $K^{n}=K_{h}^{n}\oplus K_{l}^{n}$ except when $K$ has prime characteristic $p$ and $p$ is a factor of $n$ . If $K$ is either the set of real or complex numbers, then $K_{h}^{n},K_{l}^{n}$ are orthogonal. Suppose now that $A\in R_{n,K}$ . The matrix $A$ restricts to a linear operator $A_{h}:K_{h}^{n}\rightarrow K_{h}^{n}$ .

If $f:X\rightarrow X$ is a permutation, then let $\phi_{K,p}(f):K^{X}\rightarrow K^{X}$ denote the permutation matrix that corresponds to $f$ . More specifically, let $(e_x)_{x\in X}$ be the standard basis for $K^X$ ; then $\phi_{K,p}(f)(e_x)=e_{f(x)}$ for $x\in X$ . Let $\phi_{K,ph}(f):K_{h}^{X}\rightarrow K_{h}^{X}$ denote the mapping where $\phi_{K,ph}(f)=(\phi_{K,p}(f))_h$ (i.e. $\phi_{K,ph}(f)$ is $\phi_{K,p}(f)$ restricted to the domain $K^X_h$ ). Write $\phi_{ph}$ for $\phi_{\mathbb{C},ph}$ . The representation $\phi_{ph}:S_X\rightarrow\text{GL}(\mathbb{C}_h^X)$ shall be called the standard representation of $S_X$ . We shall write $\rho_{2,d}(F)$ for $\rho_{2,d}(\phi_{ph},F)$ .

If $K$ has characteristic $0$ or if the characteristic of $K$ is not a factor of $|X|$ , then let $\pi_h:K^n\rightarrow K_h^n,\pi_l:K^n\rightarrow K_l^n$ be the projection mappings defined by $\pi_h(e_{x_0})=e_{x_0}-\frac{1}{|X|}\sum_{x\in X}e_x$ and $\pi_l(e_{x_0})=\frac{1}{|X|}\sum_{x\in X}e_x$ whenever $x_0\in X.$ Observe that $\pi_h+\pi_l=1_{K^n}$ . If $K\in\{\mathbb{R},\mathbb{C}\}$ , then the projections $\pi_h,\pi_l$ are orthogonal projections.

Linear approximation of conditional probability.

Suppose that $A,B$ are finite sets, and $\mathcal{A},\mathcal{B}$ are random variables supported on $A,B$ respectively. Let $p_{\mathcal{A},\mathcal{B}}:A\times B\rightarrow\mathbb{R}$ be the joint probability mass function for $(\mathcal{A},\mathcal{B})$ . Then for $a\in A,b\in B$ define the conditional non-uniformity of $b$ given $a$ as $\text{cnu}_{\mathcal{B}|\mathcal{A}}(a,b)=\text{cnu}_{\mathcal{B}|\mathcal{A}}(b|a)=p_{\mathcal{A},\mathcal{B}}(a,b)-\frac{1}{|B|}p(a)$ . In other words, $\text{cnu}_{\mathcal{B}|\mathcal{A}}(b|a)$ is the difference between the probability $p_{\mathcal{A},\mathcal{B}}(a,b)$ and what we would expect $p_{\mathcal{A},\mathcal{B}}(a,b)$ to be if the conditional distribution of $\mathcal{B}$ given $\mathcal{A}=a$ were uniform on $B.$ We observe that $(1_{\mathbb{R}^A}\otimes\pi_{h})(p_{\mathcal{A},\mathcal{B}}) =\text{cnu}_{\mathcal{B}|\mathcal{A}}.$ In the case where \mathcal{A},\mathcal{B} are understood, we shall write $\text{cnu}$ for $\text{cnu}_{\mathcal{B}\mid\mathcal{A}}$ and $p$ for $p_{\mathcal{A},\mathcal{B}}$ .

Measures of uniformity for probability vectors

Suppose that $F:K\times X\rightarrow X$ is a block cipher round function. Let $A$ be a complex Banach algebra. Let $\phi: S_{X}\rightarrow A$ be a representation. Suppose that $a_{k}\in A$ for each $k\in K$ , and $a_{k}\phi(f)=\phi(f)a_{k}$ whenever $f\in S_{X},k\in K$ . Set $\mathbf{a}=(a_{k})_{k\in K}$ . Then define $M_{\phi,\mathbf{a}}(F)=\rho(\sum_{k\in K}a_{k}\cdot \phi(F_{k}))$ . If $\mathbf{a}=(A_k)_{k\in K}\in M_d(\mathbb{C})^K$ , then define $M_{\phi,\mathbf{a}}(F)=\rho(\sum_{k\in K}A_k\otimes \phi(F_k))=\rho(\sum_{k\in K}(A_k\otimes I)(I \otimes \phi(F_k)))$ . We shall write $M_{\mathbf{a}}(F)$ for $M_{\phi_{ph},\mathbf{a}}(F)$ whenever $\mathbf{a}=(A_k)_{k\in K}\in M_d(\mathbb{C})^K$ .

We observe that $\phi(g)[\sum_{k\in K}a_{k}\cdot \phi(F_{k})]\phi(g)^{-1}=\sum_{k\in K}a_{k}\cdot \phi(gF_{k}g^{-1})$ for each function $g$ . Therefore, whenever $(K,X,F,(k)_{k\in K}),(K,Y,G,(k)_{k\in K})$ are isomorphic block ciphers, we have $M_{\phi,\mathbf{a}}(F)=M_{\phi,\mathbf{a}}(G)$ . The quantity $M_{\phi,\mathbf{a}}(F)$ is actually a measure of security of the block cipher $F$ in the sense that a lower value of $M_{\phi,\mathbf{a}}(F)$ signifies that the block cipher $F$ has a higher level of cryptographic security.

Some attacks

Suppose that $F:K\times X\rightarrow X$ is a block cipher round function. We shall now outline attacks where the quantities of the form $M_{\phi,\mathbf{a}}(F)$ measure the susceptibility of the block cipher round function $F$ to such an attack. We do not expect for these specific attacks to be practical against any reasonable block cipher round function. Nevertheless, it is not too difficult to compute or estimate numerical values for the susceptibility of a block cipher round function $F$ when $|K|,|X|$ are small, and these numerical values can be used as an indicator of the overall security of the block cipher round function $F$ .

Attack 1: (Input-output correlation): Suppose that $F:K\times X\rightarrow X$ is a block cipher round function for a block cipher that uses $N$ rounds of encryption.

Let $(\mathcal{K}_n)_{n=0}^{\infty}$ be a sequence of independent random variables where each $\mathcal{K}_n$ is has the uniform distribution on the set $K.$ Suppose that $(\mathcal{X}_n)_{n=0}^{\infty}$ is a Markov chain where $\mathcal{X}_{n+1}=F(\mathcal{K}_n,\mathcal{X}_n)$ for all $n\geq 0$ and where $\mathcal{X}_0$ is an element of $X$ selected uniformly at random. An attacker could potentially exploit some non-uniformity in the distribution of $(\mathcal{X}_{0},\mathcal{X}_{N})$ .

Attack 1-A: Suppose that our $N$ round block cipher is used to encrypt data. If an attacker has a single ciphertext $y$ , and the distribution $(\mathcal{X}_{0},\mathcal{X}_{N})$ is not uniform, then an attacker may be able to calculate the conditional probability $P(\mathcal{X}_0=x|\mathcal{X}_N=y)$ for each $x\in X$ , and then the attacker will know which plaintext is most likely to correspond to the ciphertext $y$ . If the distribution of $(\mathcal{X}_{0},\mathcal{X}_{N})$ is uniform (or close enough to uniform), then given a ciphertext $y$ each plaintext is equally likely, so an attacker will not be able to gather any information about the plaintext from a single ciphertext.

Attack 1-B: If a cryptocurrency mining algorithm (like Hashspin) requires one to compute encrypt elements using a block cipher $E$ consisting of applying $N$ rounds of the round function $F$ , then any non-uniformity in $(\mathcal{X}_0,\mathcal{X}_N)$ presents a potential security weakness in the mining algorithm. If the distribution of $(\mathcal{X}_{0},\mathcal{X}_N)$ is not uniform, then given an $x\in X$ , an adversary may be able to produce the most likely values of $E_k(x)$ without needing to compute $E_k(x)$ and without even knowing the key $k$ . A user may therefore use this information to determine which values $x\in X$ are most likely to result in a block reward.

We say that the block cipher round function $F:K\times X\rightarrow X$ is a near root of a Latin square if $(\mathcal{X}_{0},\mathcal{X}_{r})$ is uniformly distributed for some $r$ . Let $\mathbf{a}=(1)_{k\in K}$ . Then the spectral radius $M_{\mathbf{a}}(F)$ is a measure of how quickly the distribution of $(\mathcal{X}_{0},\mathcal{X}_{r})$ becomes uniform as $r\rightarrow\infty$ (a lower value of $M_{\mathbf{a}}(F)$ means $(\mathcal{X}_{0},\mathcal{X}_{r})$ becomes uniform more quickly). In particular, $M_{\mathbf{a}}(F)=0$ if and only if $F$ is a near root of Latin square.

Attack 2 (Correlation with alternate probabilistic computation):

Suppose that $F:K\times X\rightarrow X$ is a block cipher round function. Furthermore, suppose that $(\mathcal{K}_{n})_{n}$ is a sequence of independent random variables that are uniformly distributed on the set $K$ . Let $A$ be a finite set. Let $A_k:\mathbb{C}^A\rightarrow\mathbb{C}^A$ be a linear transformation for each $k\in K$ . Suppose that $\mathcal{Y}_{n}$ is a sequence of random variables supported on $A$ where $P(\mathcal{Y}_{n+1}=b\mid \mathcal{Y}_{n}=a,\mathcal{K}_{n}=k)=\langle A_ke_a,e_b\rangle$ for each $a,b\in A,k\in K$ . Let $\mathcal{X}_0=x_0$ and let $\mathcal{Y}_0=a_0$ . Let $\mathcal{X}_{n+1}=F(\mathcal{K}_{n},\mathcal{X}_{n})$ whenever $n\geq 0.$ Let $N$ be a fixed natural number, and suppose that $N$ rounds of the block cipher are used. Let $\mathbf{a}=(\frac{1}{|K|}A_k)_{k\in K}$ .

Attack 2-B: Suppose that a cryptocurrency mining algorithm requires one to compute $N$ rounds of the block cipher round function $F$ . Then a miner may be able to predict the value of $F_{k_{N-1}}\circ\dots\circ F_{k_0}(x_0)$ without needing to compute $F_{k_{N-1}}\circ\dots\circ F_{k_0}(x_0)$ . A miner would instead probabilistically compute $\mathcal{Y}_N$ subject to the condition that $\mathcal{K}_j=k_j$ for $0\leq j<N$ . Based only on the value that $\mathcal{Y}_N$ assumes, a user can decide whether the input $x_0$ and round keys $(k_0,\dots,k_{N-1})$ are likely to result in a block reward, and if a block reward is unlikely, then the miner would choose not to compute $F_{k_{N-1}}\circ\dots\circ F_{k_0}(x_0)$ . To thwart this attack, the block cipher round function $F$ should be chosen so that for each $a\in A$ , the conditional distribution of $\mathcal{X}_N$ given $\mathcal{Y}_N=a$ is close to uniform. In particular, the block cipher $F$ should be chosen to minimize $\text{cnu}_{\mathcal{X}_N\mid\mathcal{Y}_N}$ .

Let $p(b,y)=p_{\mathcal{Y}_N,\mathcal{X}_N}(b,y)$ whenever $b\in A,y\in X$ . Then for $b\in A,y\in X$ , we know that

$p(b,y)=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_p(F_k))^N(e_{a_0}\otimes e_{x_0}),e_b\otimes e_y\rangle$

and

$p(b)=\langle(\frac{1}{|K|}\sum_{k\in K}A_k)^N e_{a_0},e_b\rangle$

$=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_p(F_k))^N(e_{a_0}\otimes\sum_{x\in X}e_x),e_b\otimes e_y\rangle$ .

Therefore,

$\text{cnu}(y|b)=p(b,y)-\frac{1}{|X|}p(b)$

$=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_p(F_k))^N(e_{a_0}\otimes e_{x_0}-\frac{1}{|X|}\sum_{x\in X}e_x),e_b\otimes e_y\rangle$

$=\langle(\frac{1}{|K|}\sum_{k\in K}A_k\otimes\phi_{ph}(F_k))^N(e_{a_0}\otimes \pi_h(e_{x_0})),e_b\otimes e_y\rangle.$

Therefore, since $\rho(\sum_{k\in K}\frac{1}{|K|}A_k\otimes\phi_{ph}(F_k))=M_{\mathbf{a}}(F)$ , a lower value of $M_{\mathbf{a}}(F)$ indicates that the block cipher $F$ is more secure.

Attack 3 (Correlation with alternate quantum computation):

Let $V$ be a finite dimensional complex Hilbert space. Suppose that $\mathcal{E}_{k}\in C(V)$ is a quantum channel for each $k\in K.$ For this attack to be effective, $(\mathcal{E}_k)_{k\in K}$ must be simpler than $(F_k)_{k\in K}$ in some sense. We shall now try to predict information about $F_{k_n}\dots F_{k_1}(x_0)$ without needing to fully compute $F_{k_n}\dots F_{k_1}(x_0)$ . Suppose that $P\in L(V)$ is a fixed density operator, and $x_0\in X$ is a fixed element. Now, let $\mu:J\rightarrow L(V)$ be a mapping where
$\mu(j)$ is positive semidefinite for $j\in J$ , and $\sum_{j\in J}\mu(j)=1_V$ (i.e. $\mu$ is a measurement).

If $i\in J,y\in X$ , then let $p(i,y)$ be the probability of obtaining the measurement outcome $i$ when applying the measurement $\mu$ to the state $\mathcal{E}_{k_n}\dots\mathcal{E}_{k_1}(P)$ and where
$F_{k_n}\dots F_{k_1}(x_0)=y$ where $k_1,\dots,k_n\in K$ are selected uniformly at random and independently. We would like for $\text{cnu}(y|i)$ to be as close to zero as possible. We shall use spectral radii to determine the limiting behavior of $\text{cnu}(y|i)$ . We know that $p(i,y)=\langle\sum_{k\in K}(\frac{1}{|K|}(\mathcal{E}_k\otimes\phi_p(F_k)))^n(P\otimes e_{x_0}),\mu(i)\otimes e_{y}\rangle$ . Furthermore, $p(i)=\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k)^n(P),\mu(i)\rangle=\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes\sum_{x\in X}e_x),\mu(i)\otimes e_y\rangle.$

Therefore,

$\text{cnu}(y|i)=p(i,y)-\frac{1}{|X|}p(i)$

$=\langle (\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes e_{x_0}),\mu(i)\otimes e_y\rangle-\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes\frac{1}{|X|}\cdot\sum_{x\in X}e_x),\mu(i)\otimes e_y\rangle$

$=\langle\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_p(F_k))^n(P\otimes\pi_h(e_{x_0})),\mu(i)\otimes e_y\rangle$

$=\langle(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_{ph}(F_k))^n(P\otimes\pi_h(e_{x_0}),\mu(i)\otimes e_y\rangle.$

Let $\mathbf{a}=(\frac{1}{K}\mathcal{E}_k)_{k\in K}$ . Then since $\rho(\sum_{k\in K}\frac{1}{|K|}\cdot\mathcal{E}_k\otimes\phi_{ph}(F_k))=M_\mathbf{a}(F)$ , a lower value of $M_\mathbf{a}(F)$ gives evidence that the block cipher round function $F$ has a higher level of cryptographic security.

We do not expect for a quantum attack similar to this one to be effective against block cipher round functions, but this attack still illustrates how spectral radii calculations can be used to predict a block cipher’s level of cryptographic security.

We will leave it to the reader to find other kinds of representations $\phi:S_X\rightarrow V$ and attacks such that a lower value of $M_{\phi,\mathbf{a}}(F)$ indicates that $F$ is more resistant to such attacks.

Universality

Let $V$ be a real or complex finite dimensional vector space. I claim that at least when $F$ is a near root Latin square, then for all $\mathbf{a}\in L(V)^K$ , there is a version of Attack 2 so that the value of $M_{\mathbf{a}}(F)$ precisely measures how resistant the block cipher $F$ is to this version of Attack 2.

By considering every complex vector space of dimension $g$ as a real vector space of dimension $2g$ , for simplicity, we shall assume that the vector space $V$ is a real vector space and that $F$ is a near root Latin square. We can also assume that $V=\mathbb{R}^d_h$ for some $d$ . Let $t>0$ . Let $\mathbf{a}=(A_k)_{k\in K}$ . Suppose that $B_k=t\cdot A_k\oplus I_l$ where $I_l$ is the identity function on $\mathbb{R}^d_l$ . Then by choosing a small enough $t>0$ , we can guarantee that $B_k$ has only non-negative entries and is therefore doubly stochastic for each $k\in K$ . Let $\mathbf{b}=(B_k)_{k\in K}$ . In this case,

$M_{\mathbf{b}}(F)=\rho(\sum_{k\in K}B_k\otimes\phi_{ph}(F_k))=\rho(\sum_{k\in K}(A_k\cdot t\oplus I_l)\otimes\phi_{ph}(F_k))$

$=\max(\rho(\sum_{k\in K}A_k\cdot t\otimes\phi_{ph}(F_k)),\rho(\sum_{k\in K}\phi_{ph}(F_k)))$ $=\rho(\sum_{k\in K}A_k\cdot t\otimes\phi_{ph}(F_k))=t\cdot M_\mathbf{a}(F)$ .

Here, $M_\mathbf{b}(F)$ is a measure of how susceptible $F$ is to a version of Attack 2, so $M_\mathbf{a}(F)$ is also a measure of how susceptible $F$ is to a version of Attack 2 even though $\mathbf{a}$ is an arbitrary collection of matrices.

Maximization on a compact set

Let $V$ be a finite dimensional real or complex vector space. Let $\mathcal{C}\subseteq L(V)^r$ be a compact set. Then define $\rho_{\mathcal{C}}(A_1,\dots,A_r)$ to be the maximum value of $\rho(X_1\otimes A_1+\dots+X_r\otimes A_r)$ such that $(X_1,\dots,X_r)\in\mathcal{C}$ , and set $M_{\phi,\mathcal{C}}(F)=\rho_{\mathcal{C}}((\phi(F_k))_{j\in K})$ whenever $\phi:S_X\rightarrow \text{Gl}_n(\mathbb{C})$ is a linear representation and $F:K\times X\rightarrow X$ is a block cipher round function. Let $M_{\mathcal{C}}(F)=M_{\phi_{ph},\mathcal{C}}(F)$ . The measures of security of the form $M_{\phi,\mathcal{C}}(F)$ are typically more useful than the measures of security of the form $M_{\phi,\mathbf{a}}(F)$ since it is more important to know how well $F$ fares against an optimized attack than it is to know how well $F$ fares against unoptimized versions of Attacks 1-3. Given a specific integer $d\geq 1$ , the following sets $(\mathcal{C}_{r,d,i})_{i=1}^{15}$ are sets where $M_{\mathcal{C}_{r,d,i}}(F)$ is a useful measure of security of the block cipher round function $F$ . We set $\mathcal{C}_{r,d,i}\subseteq M_d(\mathbb{C})^r$ for $1\leq i\leq 10$ and we set $\mathcal{C}_{r,d,i}\subseteq L(M_d(\mathbb{C}))^r$ for $11\leq i\leq 15$ .

Suppose that $(X_1,\dots,X_r)\in M_d(\mathbb{C})^r$ .

$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,1}$ iff each $X_j$ is row stochastic.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,2}$ iff each $X_j$ is column stochastic.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,3}$ iff each $X_j$ is doubly stochastic.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,4}$ iff each $X_j$ is a permutation matrix.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,5}$ iff each $X_j$ is a row stochastic 0-1 matrix.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,6}$ iff each $X_j$ is a column stochastic 0-1 matrix.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,7}$ iff $\Phi(X_1,\dots,X_r)$ is a quantum channel.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,8}$ iff $\Phi(X_1,\dots,X_r)$ is unital.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,9}$ iff $\Phi(X_1,\dots,X_r)$ is a quantum channel and each $X_j$ is real.
$(X_1,\dots,X_r)\in\mathcal{C}_{r,d,10}$ iff $\Phi(X_1,\dots,X_r)$ is unital and each $X_j$ is real.
$(Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,11}$ iff each $Z_j$ is a quantum channel.
$(Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,12}$ iff each $Z_j$ is a completely positive and unital.
$(Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,13}$ iff each $Z_j$ is a unital channel.
$(Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,14}$ iff each $Z_j$ is a mixed unitary channel.
$(Z_1,\dots,Z_r)\in\mathcal{C}_{r,d,15}$ iff each $Z_j$ is a unitary channel.

Normalization

While $M_{\phi,\mathbf{a}}(F)$ is a measure of security for block cipher round functions $F$ , this measure of security is not normalized since $M_{\phi,k\mathbf{a}}(F)=k\cdot M_{\phi,\mathbf{a}}(F)$ for each scalar $k$ . We shall show that if $F$ is an ideal block cipher round function, and $\phi:S_X\rightarrow\text{Gl}(V)$ is a linear representation and $V$ has no invariant subspace of dimension $1$ , then $M_{\phi,\mathbf{a}}(F)=\rho_{2}(\mathbf{a})$ . Now, define $N_{\phi,\mathbf{a}}(F)=\frac{M_{\phi,k\mathbf{a}}(F)}{\rho_2(\mathbf{a})}$ . Then $N_{\phi,\mathbf{a}}(F)$ measures the factor by which $M_{\phi,\mathbf{a}}(F)$ deviates from the ideal value $\rho_2(\mathbf{a})$ . In practice, the value of $M_{\phi,\mathbf{a}}(F)$ will typically be close to $\rho_2(\mathbf{a})$ . Therefore, the values of $N_{\phi,\mathbf{a}}(F)$ will typically be close to $1$ which is much easier to work with than a value close to $\rho_2(\mathbf{a})$ .

The maximum value of $N_{\phi,\mathbf{a}}(F)$ for $\mathbf{a}\in M_d(\mathbb{C})^K$ is simply $\rho_{2,d}(\phi,F)$ . Therefore, $\rho_{2,d}(\phi,F)$ is a measure of security of the block cipher $F$ . We observe that $1\leq\rho_{2,d}(\phi,F)\leq\sqrt{|K|}$ , and that a value of $\rho_{2,d}(\phi,F)$ that is closer to $1$ indicates a greater level of cryptographic security.

If $X,Y$ are real or complex random variables, then define the covariance between $X$ and $Y$ by $\text{Cov}(X,Y)=E[(X-E(X))\overline{(Y-E(Y))}]$ whenever this quantity exists.

If $X$ is a random variable with values in a finite dimensional inner product space $V$ and $\text{Var}(\langle v,X\rangle)$ exists for each $v\in V$ , then there is a unique (necessarily positive semidefinite $P$ ) with $\langle Pu,v\rangle=\text{Cov}(\langle u,X\rangle,\langle v,X\rangle)$ . We shall write $\text{Cov}(X)$ for this positive semidefinite matrix $P$ so that $\langle \text{Cov}(X)u,v\rangle=\text{Cov}(\langle u,X\rangle,\langle v,X\rangle)$ .

Theorem:

$\text{Cov}(X+Y)=\text{Cov}(X)+\text{Cov}(Y)$ whenever $X,Y$ are independent.
$\text{Cov}(AX)=A\text{Cov}(X)A^*$ .

Proof:

$\langle\text{Cov}(X+Y)u,v\rangle=\text{Cov}(\langle u,X+Y\rangle,\langle v,X+Y\rangle)$

$=\text{Cov}(\langle u,X\rangle+\langle u,Y\rangle,\langle v,X\rangle+\langle v,Y\rangle)$

$=\text{Cov}(\langle u,X\rangle ,\langle v,X\rangle )+\text{Cov}(\langle u,X\rangle ,\langle v,Y\rangle )+\text{Cov}(\langle u,Y\rangle ,\langle v,X\rangle )+\text{Cov}(\langle u,Y\rangle ,\langle v,Y\rangle )$

$=\text{Cov}(\langle u,X\rangle ,\langle v,X\rangle )+\text{Cov}(\langle u,Y\rangle ,\langle v,Y\rangle )$ $=\langle\text{Cov}(X)u,v\rangle+\langle\text{Cov}(Y)u,v\rangle=\langle(\text{Cov}(X)+\text{Cov}(Y))u,v\rangle.$

Therefore, $\text{Cov}(X+Y)=\text{Cov}(X)+\text{Cov}(Y)$ .

$\langle\text{Cov}(AX)u,v\rangle=\text{Cov}(\langle u,AX\rangle,\langle v,AX\rangle)$

$=\text{Cov}(\langle A^*u,X\rangle,\langle A^*v,X\rangle)=\langle\text{Cov}(X)A^*u,A^*v\rangle=\langle A\text{Cov}(X)A^*u,v\rangle.$

Therefore, $\text{Cov}(AX)=A\text{Cov}(X)A^*$ . Q.E.D.

Suppose that $V$ is a finite dimensional inner product space, and $A_{0},\dots,A_{r-1}:V\rightarrow V$ are linear operators. Suppose now that $(X_{n})_{n=0}^{\infty}$ is a sequence of independent random variables. Suppose that there is an operator $Q_{0}$ with $\text{Cov}(X_{n})=Q_{0}$ for all $n$ .

Let $\iota:\{0,\dots,r-1\}\times\omega\rightarrow\omega$ be an injective function. Define a collection of random variables $(Z_{n,m})_{n,m\geq 0}$ by letting $Z_{n,m+1}=A_{0}Z_{\iota(0,n),m}+\dots+A_{r-1}Z_{\iota(r-1,n),m}$ for all $m,n\geq 0.$

Observe that for each $m\geq 0$ , the sequence $(Z_{n,m})_{n\geq 0}$ is a sequence of independent random variables. Observe that there is a sequence of operators $(Q_m)_{m}$ where $\text{Cov}(Z_{n,m})=Q_m$ for all $m,n\geq 0$ . In this case, we have $Q_{m+1}=\Phi(A_0,\dots,A_{r-1})(Q_m)$ for all $m\geq 0$ , so $Q_m=\Phi(A_0,\dots,A_{r-1})^m(Q_0)$ for all $m\geq 0$ .

Lemma: Suppose that $x$ is a normally distributed random variable with values
in $V$ and whose covariance operator is the identity operator. If $V$ is a complex inner product space, then suppose that when we consider $V$ as a real inner product space, then the covariance operator is $\frac{1}{2}I$ where $I$ is the identity operator on $V$ . If $u,v,a\in V$ , then

$\text{Tr}(A)=E(\langle Ax,x\rangle)$ ,
$\langle u,v\rangle=E(\langle x,v\rangle\cdot\langle u,x\rangle)$ , and
$E(\|\langle x,a\rangle\|^2)=E(\|\langle a,x\rangle\|^2)=\|a\|^2$

Proof:

Suppose that $e_1,\dots,e_n$ is a basis for $V$ and
$x=x_1e_1+\dots+x_ne_n$ where $x_1,\dots,x_n$ are real or complex-valued random variables. Then $E(\langle Ax,x\rangle=\sum_{i,j}E(\langle x_iAe_i,x_je_j\rangle)$
$=\sum_{i,j}E(x_i\cdot\overline{x_j})\langle Ae_i,e_j\rangle$ $=\sum_{i}\langle Ae_i,e_i\rangle=\text{Tr}(A)$ .

$\langle u,v\rangle=v^*u=\text{Tr}(v^*u)=\text{Tr}(uv^*) =E(\langle uv^*x,x\rangle)$ $=E(v^*x\langle u,x\rangle)$
$=E(\langle x,v\rangle\cdot\langle u,x\rangle)$ .
This is a special case of 2. Q.E.D.

Proposition: $E(\|X-E(X)\|^2)=\text{Tr}(\text{Cov}(X)).$

Proof: Let $y$ be a randomly selected element of $V$ where $y$ is given a normal distribution. As before, if $V$ is real, then suppose that the covariance matrix of $y$ is the identity matrix, and if $V$ is complex, then when we consider $V$ as a real vector space, suppose that the covariance matrix of $V$ is $1/2$ of the identity matrix. To make the proof simpler, we shall assume that $E(X)=0$ . Then

$\text{Tr}(\text{Cov}(X))=E_{y}(\langle\text{Cov}(X)y,y\rangle)=E_y(\text{Cov}(\langle y,X\rangle,\langle y,X\rangle))=E_y(\text{Var}_X(\langle y,X\rangle))$

$=E_y(E_X(|\langle y,X\rangle|^2))=E_X(E_y|\langle y,X\rangle|^2)=E_X(\|X\|^2).$ Q.E.D.

Therefore, $E(\|Z_{n,m}-E(Z_{n,m})\|^2)=\text{Tr}(\Phi(A_0,\dots,A_{r-1})^{m}(Q_0)).$ We conclude that, $\rho_2(A_0,\dots,A_{r-1})$ is a measure of the growth rate of $\|Z_{n,m}-E(Z_{n,m})\|.$

The function $\iota$ should be considered as an ideal block cipher round function. Suppose now that $E(Z_{n,m})=0$ for all $m,n$ . The collection of random variables $(Z_{n,m})_{n=0}^{\infty}$ should be considered to be an ideal model of $(A_0\otimes\phi_{ph}(F_0)+\dots+A_{r-1}\otimes\phi_{ph}(F_{r-1}))^m(\pi_h(\mathbf{x}))$ where each entry in $\mathbf{x}$ has the same distribution as $Z_{n,0}$ and is independent. Therefore, if $F$ is a good block cipher round function, then we should expect to have $M_{\mathbf{a}}(F)\approx\phi_2(\mathbf{a})$ .

When $V$ is a real vector space and $A_0,\dots,A_{r-1}$ is in general position, then the central limit theorem applies to the random variables $Z_{n,m}$ . As $m\rightarrow\infty$ , the random variables $Z_{n,m}$ will approach a multivariate normal distribution (and the standard proof of the multivariate central limit theorem that uses characteristic functions applies to the random variables $Z_{n,m}$ ).

Suppose that $F:K\times X\rightarrow X$ is a block cipher round function. Then whenever $(v_x)_{x\in X}$ is a dominant eigenvector for $\sum_{k\in K}A_k\otimes\phi_{ph}(F_k)$ , we should expect for $(v_x)_{x\in X}$ to be approximately normally distributed in $V$ and statistically significant deviations from normality may indicate that the block cipher round function $F$ has a security weakness.

Conclusion

The measure of security $\rho_{2,d}(F)$ of a block cipher round function $F$ is interesting for purely mathematical reasons but also measures how effective low memory attacks are against $F$ compared to that of an ideal block cipher round function. The measure of security $\rho_{2,d}(F)$ seems more meaningful than measures of security $M_{\phi,\mathcal{C}}(F)$ since $\rho_{2,d}(F)$ takes into account all values $\rho(\sum_{k\in K}A_k\otimes\phi(F_k))$ where $(A_k)_{k\in K}\in M_d(\mathbb{C})^K$ instead of restricting one’s attention to when $(A_k)_{k\in K}\in\mathcal{C}$ for some compact set $\mathcal{C}$ . Estimating $M_{\phi,\mathcal{C}}(F)$ may be awkward since $\rho(\sum_{k\in K}A_k\otimes\phi(F_k))$ in practice would have many local but not global maxima $(A_k)_{k\in K}\in\mathcal{C}$ while in practice, one encounters very few local but not global maxima when estimating $\rho_{2,d}(F)$ .

While we believe that $\rho_{2,d}(F)$ is a good measure of security to the block cipher $F$ , it has a few disadvantages. It is a new measure of security that has not yet stood the test of time, and $\rho_{2,d}(F)$ may be difficult to estimate when the block cipher round function $F$ is too complex or large. $\rho_{2,d}(F)$ also only measures the security against attacks that require an extremely limited amount of memory. We therefore recommend using $\rho_{2,d}$ to measure the security of block ciphers when used in conjunction with other measures of security.

Share this:

Like this:

Leave a Reply Cancel reply