本文仅为思路简述，具体过程参考参考文献所述
概述
一个对称密钥密码通常需要在加密网络中引入非线性部分以保证密码的安全性。而如果可用线性关系去近似表达非线性关系，那么问题必然能够进行简化。我们将在基于按位异或(xorKey)、分组替代(sbox)与位重排(permutation)一个简单的的分组密码上考虑这种思想。
考虑一个关于密码部分输入输出位的异或和关系式\(\sum input_i+\sum output_i=0\)，我们知道其不会恒成立，而理想非线性情况下，对于随机输出，其成立的概率应为0.5。如果这一概率产生明显偏移，即证明在正确加密的过程中，对于大量随机输入输出，线性趋势将会显著表现。
我们枚举部分密钥，然后考虑可求的两组过程值之间的有偏的线性趋势。可以通过类似假设检验的手法，验证枚举的密钥是否可能成立。
概率堆叠引理
考虑独立01随机变量列\(\{X_i\}\)，设\(P(X_i=0)=p_i=0.5+\varepsilon_i\)，称\(\varepsilon_i\)为\(X_i\)的线性系数(Linear bias)。成立：
\[ P(X_i\ \mathrm{xor}\ X_j = 0)=P(X_i=X_j)=p_ip_j+(1-p_i)(1-p_j)=1+2\varepsilon_i\varepsilon_j \]
上式在计算过程中频繁使用。
0ctf 2018 zer0SPN
本题是经典的模板题，即给定65536对输入输出，求一个 xorKey->8bitBlockSbox->permutation 四层64bit加密网络的第一层密钥值。
Sbox为整个过程中唯一的非线性环节，我们可以单独计算其输入输出共16bits中，选择任意数量的bits的异或和为0的概率，记录在表\(sProb[0..255][0..255]\)中。
我们确定一个第一层sbox输出与最终输出两处的部分bits的异或和关系式，保证其线性系数绝对值\(\mathrm{abs}(bias)>\frac{1}{256}\)。枚举第一层的相关block的key值，计算key值假设下的实际数据表现出的线性系数，通常绝对值最大者即为答案（若出现两个数值接近的最大与次大值，可能需要进一步判断）
参考文献
- [1] Heys, Howard M. "A tutorial on linear and differential cryptanalysis." Cryptologia 26.3 (2002): 189-221.
- [2] 線形解読法 - 東京工業大学デジタル創作同好会traP