SPN线性密码分析

在学习SPN线性密码分析时，我找了很多资料。但是很多时候都感觉这些材料不算细致，我也遇到了非常多的困惑，所以希望能细致入微的记录一下。

本文基本上是 A Tutorial on Linear and Differential Cryptanalysis 的翻译，用自己的语言复述了一遍，加了部分自己的理解。

一、块加密

块加密(Block Cipher)，或称为分组加密，是一种对称加密算法。它将明文分成多个等长的块（block），使用确定的算法和对称密钥对每组分别加密解密。通常来说，每个块使用的加密算法是相同的，但是密码组件不一定相同，例如不同块的S盒不一定相同。

二、SPN

SPN——代换-置换网络(Substitution–permutation network), 是一系列被应用于分组密码中相关的数学运算，最典型的就是AES。这种加密网络使用明文块和密钥块作为输入，并通过交错的若干“轮”代换操作和置换操作产生密文块。代换（Substitution）和置换（Permutation）的组件分别被称作S盒（替换盒，S-boxes）和P盒（排列盒，P-boxes）。

我在解SPN和Feistel相关算法的密码时，常常会觉得代换密码和置换密码的区别十分有限，非常困惑，后来我在写本文时想通了，如果你也有这个困惑，可以参考一下我的这篇博客：代换密码和置换密码在块加密中的作用与区别

下图是 Heys 在 A Tutorial on Linear and Differential Cryptanalysis 中设计的一个非常基础的"Toy Cipher"。

我们可以通过这个基础的"Toy Cipher"，来学习一下SPN。

这个SPN密码中，输入16bit的明文和16bit的密钥，输出16bit的密文。分为4个块，每个块中, 分别有4bit明文、密文。共有4轮加密，每一轮加密由3个过程组成：

1. 轮密钥异或
2. 代换 (Substitution)
3. 置换 (Permutation)

在第四轮，没有置换过程，增加了一个轮密钥异或的过程。

没有置换是因为置换密码主要起到的是扩散功能，使字母分布失去统计特征。置换密码是一个完全线性的过程，因此在最后一轮中，置换加密不会提升安全性。

增加了一轮 轮密钥异或，主要是为了防止最后一轮的代换密码在密码分析中被非常容易的绕过。

某种意义上，也可以认为是为了加密过程与解密过程的对称。

1. 轮密钥异或

本例中，每一轮密钥都未知，每轮密钥之间的关系也未知。

2. 代换 (Substitution)

这是一个4x4的s盒，通常一个加密算法中会有多个s盒，s盒的数量与input的长度有关：

$$Count(SBoxs) = len(input)/\sqrt{len(SBox)}$$

这里的s盒是4x4(4bit输入，4bit输出), 16bit的s盒，input是16bit，因此有4个s盒。

这里的例子中，所有的s盒都相同。但也可以设计不同的s盒，例如0ctf2018的zer0SPN中每一轮的s盒相同，但是不同轮的s盒不同；DES中，每一轮的s盒不相同，但不同轮的s盒相同。

s盒最重要的属性是要能提供非线性的能力，s盒设计的好坏，决定了加密算法抗线性分析的能力。

3. 置换 (Permutation)

置换是将输入的每bit的位置互换，即：

$$Output[i] = Input[PBox[i]]$$

通常每轮只有一个 p 盒，每轮 p 盒都相同。p 盒的作用主要使字母失去统计意义。

三、线性密码分析

1. 基本思路

线性密码分析是一种已知明文攻击——攻击者已知密钥相同的多组明密文对，求解密钥。与选择明文攻击或选择密文攻击相比，攻击者无法任意选择一段明文或密文，获得对应的密文或明文。

线性密码分析的思路是，分析明文和密文之间的线性表达式成立的概率。其中明密文之间的线性表达式为：

$$X_{i_1} \oplus X_{i_2} \oplus … \oplus X_{i_u} \oplus Y_{j_1} \oplus Y_{j_2} \oplus … \oplus Y_{j_v} = 0$$

其中Xi表示的是输入中的第i个bit，Yj表示的是输出中的第j的bit。

这个表达式不是必然成立的， 对于一个优秀的密码算法，它成立的概率应当是 1/2 ， 即左边的结果可能为 0 ，也可能为 1 。如果该表达式成立的概率距离 1/2 越远，则越容易使用线性分析法，获得明密文之间的线性关系，从而通过多组明密文对分析出密钥的值。假设线性表达式成立的概率为 P，那么 |P-1/2| 越大，越容易受到线性密码分析攻击。

在本文中，我们分析了一个输入(明文)，和输出(第4轮轮密钥异或的结果)的线性逼近。(我们希望一直迭代下去，直到只剩一轮密钥作为未知数，因此使用第4轮轮密钥异或的结果作为输出。经过线性分析的密钥可以忽略不作为未知数，具体原因在下文中解释。)

2. 堆积引理(Piling-Up Principle)

堆积引理提供了概率计算中的一些理论支撑，可以跳过这一节中的推导过程，直接看结论。但是如果直接看下去，也很简单。

对于简单的两个随机变量X1, X2, 有：

$$ \begin{align} P_r(X_1=i)=\begin{cases} p_1,&\quad i = 0 \newline 1-p_1,&\quad i=1 \end{cases} \end{align} $$

$$ \begin{align} P_r(X_2=i)=\begin{cases} p_2,&\quad i = 0 \newline 1-p_2,&\quad i=1 \end{cases} \end{align} $$

如果这两个随机变量的取值是独立的， 则有：

$$ \begin{align} P_r(X_1=i, X_2=j)=\begin{cases} p_1p_2,&\quad i = 0,j=0 \newline p_1(1-p_2),&\quad i = 0,j=1 \newline (1-p_1)p_2,&\quad i = 1,j=0 \newline (1-p_1)(1-p_2),&\quad i=1,j=1 \end{cases} \end{align} $$

上式也可以表示为

$$ \begin{align} P_r(X_1\oplus X_2=0) &= P_r(X_1=X_2) \newline &= P_r(X_1=0, X_2=0) + P_r(X_1=1, X_2=1) \newline &= p_1p_2 + (1-p_1)(1-p_2) \end{align} $$

假设

$$ \begin{align} p1 = 1/2 + \varepsilon_1 \newline p2 = 1/2 + \varepsilon_2 \end{align} $$

其中 $\varepsilon_1,\varepsilon_2$ 分别是p1,p2距离1/2的偏差。且有： $$ -1/2 \leq \varepsilon_1,\varepsilon_2 \leq 1/2 $$

因此有：

$$ P_r(X_1 \oplus X_2 = 0) = 1/2 + 2\varepsilon_1 \varepsilon_2 $$

则 $X_1 \oplus X_2 = 0的偏差\varepsilon_{1,2}=2\varepsilon_1 \varepsilon_2$

推广到多个随机变量的情况:

$$ \begin{align} &对 X_1=0, 到 X_n=0 的概率分别为p_1 = 1/2+\varepsilon_1 到 p_n = 1/2 + \varepsilon_n \newline &如果这个n个随机变量是独立的，根据堆积引理有： \newline &P_r(X_1 \oplus … \oplus X_n = 0) = 1/2 + 2^{n-1}\prod_{i=1}^n\varepsilon_i \newline & 即 \newline &\varepsilon_{1,2,…,n}=2^{n-1}\prod_{i=1}^n\varepsilon_i \end{align} $$

这个式子会在下面具体计算偏差时用到。

另外，堆积引理还可以这样应用：

$$ \begin{align} &假设有: \newline &P_r(X_1\oplus X_2=0)=1/2 + \varepsilon_{1,2} \newline &P_r(X_2\oplus X_3=0)=1/2 + \varepsilon_{2,3} \newline &则 \newline &P_r(X_1 \oplus X_3 = 0) = P_r(X_1 \oplus X_2 \oplus X_2 \oplus X_3=0) =1/2+2\varepsilon_{1,2}\varepsilon_{2,3} \newline &即 \newline &\varepsilon_{1,3}=2\varepsilon_{1,2}\varepsilon_{2,3} \end{align} $$

四、SPN线性密码分析

1. 单个S盒线性分析

因为SPN中只有s盒是非线性的，因此我们可以先分析单个S盒的线性关系

对于本例中的4X4的S盒，有4个bit的输入：X1,X2,X3,X4, 会得到4个bit的输出: Y1,Y2,Y3,Y4。

根据本例中的S盒，对于所有可能的输入，对应的输出分别为:

下面我们以一个线性表达式为例，计算该表达式的偏差

$$ X_2 \oplus X_3 \oplus Y_1 \oplus Y3 \oplus Y4 = 0 $$

我们分别使用16组输入输出，计算上述表达式成立的概率为12/16, 关于1/2的偏差为12/16-1/2=1/4

对于其他的线性表达式，我们也可以计算出来一个偏差，最终我们可以得到256个偏差。用一个表展示出来如下

根据这个表，我们可以直接得到某个线性表达式的偏差，例如

$$ \begin{align} &P_r(X_2 \oplus X_3 \oplus Y_1 \oplus Y_3 \oplus Y_4) = 1/2 + NlTable[0b0110][0b1101]/16 = 1/2 + 4/16 \newline &\varepsilon = 4/16 =1/4 \end{align} $$

实际在计算某个表达式的概率时，具体计算的公式为

$$ \begin{align} &\sum_{0ba_4a_3a_2a_1=0}^{15}\sum_{0bb_4b_3b_2b_1=0}^{15} (a_1 \cdot X_1) \oplus (a_2 \cdot X_2) \oplus (a_3 \cdot X_3) \oplus (a_4 \cdot X_4) \oplus (b_1 \cdot Y_1) \oplus (b_2 \cdot Y_2) \oplus (b_3 \cdot Y_3) \oplus (b_4 \cdot Y_4) \newline &\iff \newline &\sum_{i=0}^{15}\sum_{j=0}^{15}(0bX_4X_3X_2X_1 \cdot i)\oplus(0bY_4Y_3Y_2Y_1 \cdot j) \newline &(\cdot 符号指位运算中的与运算) \end{align} $$

需要注意下，这里在计算X1,X2,X3,X4的10进制值时，X1对应的是高位，X4对应的是低位。在后续的计算中，也应该一以贯之。即，对于一个10进制的明文，在转换成二进制(P1,P2,P3,P4)后，P1对应的是高位。

2. 多组S盒的线性逼近

这一节中，我们以第二个块中明文中的(P5, P7, P8)作为输入。(没有特别的理由，只是这个作为例子比较简单)

这样的输入经过的S盒分别为：S12->S22->S32,S34->S42,S44

可以分析出，这个例子简单之处在于经过的S盒相对少，且最后输出为分布在两个块中，既不会需要爆破过多组密钥，也保证了偏差比较大。

对要进行线性分析的S盒（前3轮），每一轮的S盒, 输入、输出、偏差分别为：

$$ \begin{align} &S_{12}: X_1\oplus X_3 \oplus X_4 = Y_2 &bias: 1/4 \newline &S_{22}: X_2 = Y_2 \oplus Y_4 &bias: -1/4 \newline &S_{32}: X_2 = Y_2 \oplus Y_4 &bias: -1/4 \newline &S_{34}: X_2 = Y_2 \oplus Y_4 &bias: -1/4 \end{align} $$

我们假定Ui,j, Vi,j分别为第i轮S盒的第jbit输入、输出(1<=i<=4, 1<=j<=16); Ki,j为第i轮轮密钥的第jbit。(1<=i<=5, 1<=j<=16)

所以有：

Round1:

$$ \begin{align} \newline U_1 &= P\oplus K1 \newline V_{1,6}&= U_{1,5}\oplus U_{1,7} \oplus U_{1,8} \newline &= ((P_5) \oplus K_{1,5})\oplus (P_7\oplus K_{1,7}) \oplus (P_8 \oplus K_{1,8}) &bias: 1/4 \end{align} $$

Round2:

$$ \begin{align} \newline U_{2,6} &= V_{1,6} \oplus K_{2,6} \newline V_{2,6} \oplus V_{2,8} &= U_{2,6} \newline &=V_{1,6} \oplus K_{2,6}& bias: -1/4 \newline &=P_5 \oplus K_{1,5}\oplus P_7\oplus K_{1,7}\oplus P_8 \oplus K_{1,8} \oplus K_{2,6} &bias: 2*1/4*-1/4=-1/8 \end{align} $$

Round3:

$$ \begin{align} \newline U_{3,6} &= V_{2,6} \oplus K_{3,6} \newline U_{3,14} &= V_{2,14} \oplus K_{3,14} \newline V_{3,6} \oplus V_{3,8} &= U_{3,6} \newline &=V_{2,6} \oplus K_{3,6} & bias: -1/4 \newline V_{3,14} \oplus V_{3,16} &= U_{3,14} \newline &=V_{2,8} \oplus K_{3,14} & bias: -1/4 \newline V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} &=V_{2,6}\oplus V_{2,8} \oplus K_{3,6} \oplus K_{3,14} \newline &= P_5 \oplus P_7\oplus P_8\oplus K_{1,5}\oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6}\oplus K_{3,14} \newline bias&= 2^{3-1}*-\frac{1}{8}*-\frac{1}{4}-\frac{1}{4}=-\frac{1}{32} \end{align} $$

Round4:

$$ \begin{align} \newline U_{4,6} &= V_{3,6}\oplus K_{4,6} \newline U_{4,8} &= V_{3,14}\oplus K_{4,8} \newline U_{4,14} &= V_{3,8}\oplus K_{4,14} \newline U_{4,16} &= V_{3,16}\oplus K_{4,16} \newline U_{4,6} \oplus U_{4,8}\oplus U_{4,14}\oplus U_{4,16} &= V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \oplus K_{4,6}\oplus K_{4,8}\oplus K_{4,14}\oplus K_{4,16} \newline &= P_5 \oplus P_7\oplus P_8\oplus \sum K \newline \sum K &= K_{1,5}\oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6}\oplus K_{3,14} \oplus K_{4,6}\oplus K_{4,8}\oplus K_{4,14}\oplus K_{4,16} \end{align} $$

在计算每一轮的偏差时，我们使用了堆积引理。其中(U,P,K)的偏差为-1/32。

因为K是固定的，每个K要么是0，要么是1，因此有

$$ \begin{align} &\sum K = 0 或 1 \newline &P_r(U_{4,6} \oplus U_{4,8}\oplus U_{4,14}\oplus U_{4,16}\oplus P_5 \oplus P_7\oplus P_8 = 0) = 1/2 - 1/32 或 1/2 + 1/32 \end{align} $$

经过线性分析的K可以在线性表达式中忽略，因此我们一直分析到第4轮轮密钥异或的结果，从而留下K5作为未知数爆破

从而我们获得了一组U4,K5,P的线性关系，它距离1/2的偏差为1/32。当我们有n组明密文对时:

$$ \sum(U_4\oplus K_5\oplus P=0)=n*1/32 $$

3. 爆破密钥

当我们有足够多的明密文对时，爆破[K5,5…K5,8], [K5,13…K5,16]，对每一种可能的K5（共256种）我们可以根据K5, 和Cipher的值，计算得出[U4,5…U4,8], [U4,13…U4,16]，从而计算实际的偏差。正确的K5, 偏差应该接近1/32。对于一个错误的K5, 计算出来的偏差应该接近于0。

假设我们有10000组明密文对，计算出来的实际偏差如下：

我们发现最大的偏差是0.0336， 接近于1/32=0.03125。 因此我们可以认为 [K5,5…K5,8] = 0b0010, [K5,13…K5,16] =0b0100

在获得第二、四块K5后，我们可以继续寻找其他线性表达式，计算出所有的K5。然后根据轮密钥之间的关系，或重复进行前几轮的线性分析，得出所有轮轮密钥。

4. 线性密码分析的复杂性

作者认为，应该需要 $\varepsilon^{-2}$ 组明密文对。我们可以认为，如果可以获得$\varepsilon^{-2}$组明密文对，则该密码算法是可以被线性分析攻击的。

从以上的分析，我们可以知道一个密码算法抵御线性分析的能力取决于S盒的设计。通常，S盒的偏差越大，线性表达式的偏差越大；S盒的数量越少，线性表达式的偏差越大。因此为了抵御线性密码分析，通常会优化S盒（降低S盒的最大偏差），增加S盒的数量。Rijndael就是这样一个绝佳的例子。

这个例子中，我们假设每个S盒是独立的，但是现实中的S盒不是独立的，这可能会对概率的计算产生比较大的影响。可能不同的S盒的组合产生的偏差可能会比相同的S盒的偏差更大，这个概念称为linear hull. 值得注意的是，如果每个S盒的偏差很小，但当多个S盒组合在一起时，它们可能会产生一个非常大的偏差。

五、扩展

1. 找出所有的线性逼近
2. S盒不同的情况

在0ctf2018的zer0SPN一题中，涉及了以上两种情况。可以参考我的另一篇博客 0ctf2018 zer0SPN (线性密码分析)

六、代码实现

完整代码参见: linear_cryptanalysis/spn, 本文我们只介绍部分重要函数的功能。

func CalcNlTable(sBox []int) common.Matrix {和func CalcBiasTable(nlTable common.Matrix) map[NlKey]int {用于计算所有的线性表达式的偏差。

因为U是未知数，所以我们相应的异或、置换、代换等运算，都需要基于变量来计算，因此我们需要定义自己的数据结构，自己的异或、置换、代换等运算。

Element表示U或V或W

// U =====Substitute=====> V =====Permutation=====> W ======subKey mixing======> U'
type Element struct {
	Value int
	Round int
	Col   int
}

func Substitute(uList []Element, biasTable map[lib.NlKey]int) ([][]Element, []int) {和func Permutation(pBox []int, vList []Element) []Element {函数分别是基于Element的代换和置换运算。

AnalysisForEachRound是每一轮的运算（第一轮例外，需要单独计算）

type Round struct {
	Round    int
	SBox     []int
	PBox     []int
	UList    []Element
	VCombo   [][]Element
	BiasList []int
}

func (r *Round) AnalysisForEachRound(biasTable map[lib.NlKey]int) []Round {
	var nextRoundList []Round
	r.VCombo, r.BiasList = Substitute(r.UList, biasTable)
	for _, vList := range r.VCombo {
		nextRoundUList := Permutation(r.PBox, vList)
		nextRound := Round{
			Round: r.Round + 1,
			SBox:  r.SBox,
			PBox:  r.PBox,
			UList: nextRoundUList,
		}
		nextRoundList = append(nextRoundList, nextRound)
	}
	return nextRoundList
}

func Analysis(sBox, pBox []int, keySize, pair, biasProductLine, iteratorTime int) {实现了密码分析的过程，输出偏差大于biasProductLine的线性表达式。iteratorTime指定最大可爆破的密钥块。每次爆破，需要读取n组明密文对, 时间复杂度为O(2^iteratorTime*n)。一般来说，对于一个8bit的block，如果要爆破两块密钥，需要爆破2^8*2^8次， 假设共65535组明密文对，则大约要执行2^32次循环，是可接受的。但是如果要爆破3个密钥块，则是不可接受的。

func Check(sBoxInv []int, plainTextList, cipherTextList [][]byte, x, y, pair int, plainBitMap, cipherBitMap []BitMap) int {函数根据线性分析的结果，对密钥进行爆破。基于goroutine，实现了CPU 100%的利用。

附

1. 参考资料

• 2002年的一篇文章，很多材料都引用了这篇，这篇文章广泛传播主要是因为使用了一个非常容易理解的例子 A Tutorial on Linear and Differential Cryptanalysis
• 中文环境中写的相对详细的文章: 线性分析法
• 线性分析法 分析 DES加密算法
• 密码学原理（华中科技大学）
• Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis

2. 排版

本文涉及了一些数学公式，在排版时参考了以下资料

• https://note.qidong.name/2018/03/hugo-mathjax/
• https://butui.me/post/yet-best-math-formula-support-for-hugo-with-mathjax/
• https://www.jianshu.com/p/e74eb43960a1
• https://juejin.im/post/5a6721bd518825733201c4a2
• https://blog.csdn.net/bendanban/article/details/77336206

但是对于我的博客，我使用的是新的一套排版方案，可以查看我的另一篇博客hugo支持数学公式方案探索，我会尽快更新。