SB层差分分布的一个结论

我一直认为，Super-Sbox分析只是把几个sbox和一些线性层合并成一个大的sbox的无聊的技巧。不过，上周有个师弟指出论文Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations中有一个Super-Sbox相关的结论。当时我对该结论没有足够的理解，事后才耐心地推导了一次。

这个结论出现在论文的3.4小节中对“The controlled rounds”的分析中，原文是：

It is easy to see that if \(\Delta' = (\Delta_1', \cdots, \Delta_r')\) was a fully random \(r\)-tuple of output differences for the \(r\) Super-Sboxes, the average value over \(\Delta'\) would be exactly \(1/2\) (this actually holds for any permutation, independently of the fact that this permutation is a \(r\) tuple of Super-Sboxes).

由于作者说了，对于任意一个置换，该结论都成立，因此下文考虑的是任意一个\(m\)比特的置换：\(\text{sbox} : \{0, 1\}^m \rightarrow \{0, 1\}^m\)。

那么，这个结论想表达的意思是：在一个由\(r\)个sbox并联起来的SBOX中（\(\text{SBOX} = (\text{sbox}_1, \cdots, \text{sbox}_r)\)），在给定输入差分为\(\Delta = (\Delta_1, \cdots, \Delta_r)\)的情况下，随机选择输出差分\(\Delta' = (\Delta_1', \cdots, \Delta_r')\)，下面方程的解\(\{X_1, X_2\}\)的数量平均只有\(1/2\)个。其中，\(X_1 = (x_{1, 1}, \cdots, x_{1, r})\)，\(X_2 = (x_{2, 1}, \cdots, x_{2, r})\)，\(X_1 \oplus X_2 = \Delta\)。 \[ SBOX(X_1) \oplus SBOX(X_2) = \Delta' \] 这个结论看起来就挺直观的，在证明之前，先定义几个符号。对于每一个\(\text{sbox}_i\)，都可以求出其差分分布表，记为\(ddt_i\)。其中， \[ ddt_i(\Delta_i, \Delta_i') = \#\{x_i\ |\ \text{sbox}_i(x_i) \oplus \text{sbox}_i(x_i \oplus \Delta_i) = \Delta'_i\}。 \] 记方程\(\text{sbox}_i(a) \oplus \text{sbox}_i(b) = \Delta'_i\)的解的数量的分布表如下： \[ T_i(\Delta_i, \Delta_i') = \#\left\{\{a, b\}\ |\ \text{sbox}_i(a) \oplus \text{sbox}_i(b) = \Delta'_i,\ a \oplus b = \Delta_i\right\}。 \] 由于无序对\(\{x_i, x_i \oplus \Delta_i\}\)和\(\{x_i \oplus \Delta_i, x_i\}\)是同一个，方程的不重复的解的数量就是\(ddt_i(\Delta_i, \Delta_i') / 2\)，得到如下关系式。 \[ T_i(\Delta_i, \Delta_i') = ddt_i(\Delta_i, \Delta_i') / 2 \] 对于SBOX，也有类似的定义，如下。 \[ DDT(\Delta, \Delta') = \#\{X | \text{SBOX}(X) \oplus \text{SBOX}(X \oplus \Delta) = \Delta'\} \]

\[ T(\Delta, \Delta') = DDT(\Delta, \Delta') / 2 \]

由于\(\Delta = (\Delta_1, \cdots, \Delta_r)\)和\(\Delta' = (\Delta_1', \cdots, \Delta_r')\)，可以得到如下式子。 \[ DDT(\Delta, \Delta') = ddt_1(\Delta_1, \Delta_1') \times \cdots \times ddt_r(\Delta_r, \Delta_r') \] 现在，考虑输入差分\(\Delta = (\Delta_1, \cdots, \Delta_r)\)为已知的情况，同时随机选择输出差分\(\Delta' = (\Delta_1', \cdots, \Delta_r')\)。为了简化符号，同时和原论文中的符号对应上，这里使用符号\(n_i = T_i(\Delta_i, \Delta'_i)\)和\(n(\Delta') = T(\Delta, \Delta')\)。

可以注意到\(n_i\)和\(n(\Delta')\)都是关于随机变量\(\Delta'\)的随机变量。其中，\(\Delta'\)一共有\((2^m)^r\)个可能的取值（\(r\)个\(m\)比特的sbox的并联）。那么，可以计算出\(n(\Delta')\)的期望值如下。

\[ \begin{aligned} E\left(n(\Delta')\right) &= \frac{1}{|\Delta'|} \sum_{\Delta'} n(\Delta') \\ &= \frac{1}{(2^m)^r} \sum_{\Delta'} n(\Delta') \\ &= \frac{1}{2^{mr}} \sum_{\Delta_1'} \sum_{\Delta_2'} \cdots \sum_{\Delta_r'} n\left((\Delta_1', \Delta_2', \cdots, \Delta_r')\right) \\ &= \frac{1}{2^{mr}} \sum_{\Delta_1'} \sum_{\Delta_2'} \cdots \sum_{\Delta_r'} n_1 \times n_2 \times \cdots \times n_r \times 2^{r - 1} \\ &= \frac{1}{2^{mr}} \left( \sum_{\Delta_1'} n_1 \right) \times \left( \sum_{\Delta_2'} n_2 \right) \times \cdots \left( \sum_{\Delta_r'} n_r \right) \times 2^{r - 1} \\ &= \frac{1}{2^{mr}} \times 2^{m - 1} \times 2^{m - 1} \times \cdots \times 2^{m - 1} \times 2^{r - 1} \\ &= \frac{1}{2} \end{aligned} \] 其中， \[ \begin{aligned} \sum_{\Delta'_i} n_i &= \sum_{\Delta'_i} \frac{ddt_i(\Delta_i, \Delta_i')}{2} \\ &= \frac{1}{2} \sum_{\Delta'_i} ddt_i(\Delta_i, \Delta_i') \\ &= \frac{1}{2} \times 2^m \\ &= 2^{m - 1}。 \end{aligned} \] 至此，证明结束，这个结论与一个sbox时的结论是一致的（\(r = 1\)时）。

在论文中，每一个sbox都是一个Super-Sbox，是由\(r\)个\(c\)比特的更小的S盒构成，所以尺寸是\(m = rc\)比特，而SBOX就是SB层。所以这个结论和Super-Sbox根本就没有关系啊🤣认真一看，噢作者一开始不就说了嘛，any permutation🤣所以在这个section中，Super-Sbox分析用在哪了？果然还只是几个sbox简单合并起来233333