【密码分析学 笔记】ch3 3.1 差分分析

ch3 分组密码的差分分析和相关分析方法

3.1 差分分析

• 评估分组密码安全性通用方法
• 可用于杂凑函数和流密码安全性

预备知识：

• 迭代性分组密码（分组密码一般结构）
• 简化版本 mini-AES CipherFour算法

3.1.1 差分分析原理

现象：密钥在异或运算过程中被抵消 → 直接从明文对异或值得到密文对异或值（绕过密钥）【不随机现象】

差分值: X和X’是两个长度为n的二进制比特串，$\Delta X=X\oplus X^{\prime }$ 称为X和X’的差分值

• 模加运算 模减差分

i轮差分、i轮差分对（differential）: $P{\beta }_0\stackrel{i轮}{\to }{\beta }_i$ 差分经过i轮的传播特性

i轮差分概率：$DP({\beta }_0\stackrel{i轮}{\to }{\beta }_i)$

理想分组密码：$\alpha$ 是输入差分，$\beta$ 是输出差分，n是分组长度，理想分组密码满足随机置换, ∀ β ∈ { 0 , 1 } n , D P ( α → i 轮 β ) = 1 / 2 n { \forall \beta \in \{0,1\} ^{n},DP(\alpha \stackrel{i轮}\to \beta)=1/2^{n} } ∀β∈{0,1}n,DP(α→i轮β)=1/2n,构造区分器关键：找到高概率的i轮差分$\alpha \stackrel{i轮}{\to }\beta$，满足$DP(\alpha \stackrel{i轮}{\to }\beta )>1/2^n$

差分分析原理：

1. 发现长轮数、高概率的i轮差分（不随机现象）
2. 建立与部分密钥有关的带概率的方程，利用正误密钥下，中间状态满足特定差分值的明密文对数服从不同分布，恢复密钥（分割密钥空间，建立方程组/约束条件，进行密钥恢复攻击）

差分分析攻击模型

假设$DP(\alpha ,\beta )=p>1/2^n，|\tilde{K}|=k$,设置 $2^k$ 个计数器，初始化为0

1. 采样：选取满足条件的差分明文对
2. 去噪：根据β值过滤对应的密文
3. 恢复密钥：对方程组每个解都设置1个计数器，处理完所有明文对后从大到小排序，前$2^{k-a}$个作为正确密钥候选值,结合穷举攻击等确定正确密钥

3.1.2 CipherFour 算法差分分析

3.1.2.1 各运算部件差分传播特性

CipherFour算法：

• 16bit分组长度
• r轮迭代
• 密钥长度为16(r+1)bits
• 假设轮密钥相互独立

算法每一轮（除最后一轮）包含：

• 16比特的轮密钥异或
• 4个4比特的S盒
• 16比特的比特置换

最后一轮包含：

• 16比特的轮密钥异或
• 4个4比特的S盒
• 16比特的白化密钥异或

1.S盒

非线性变换S盒差分传播概率：

• 输入差分α过S盒后变为输出差分β，记为**$\alpha \stackrel{S}{\to }\beta$**
• 满足$\alpha \stackrel{S}{\to }\beta$ 的明文对的个数为**$N_S(\alpha ,\beta )$**
• 相应的$\alpha \stackrel{S}{\to }\beta$ 的差分传播概率为**$DP(\alpha \stackrel{S}{\to }\beta )=Pr(\alpha \stackrel{S}{\to }\beta )=\frac{N_S(\alpha ,\beta )}{2^m}$**

S盒差分分布表（DDT）

• 构造：α为行标，β为列标，行列交错处的项为$N_S(\alpha ,\beta )$，构造的$2^m\times 2^n$的表
• CipherFour的DDT特性
  • $DP(0x0\stackrel{S}{\to }0x0)=1$
  • $DP(0x0\stackrel{S}{\to }0xi)=1,i\ne 0$
  • 若$N_S(\alpha ,\beta )=0$，记作$\alpha \nrightarrow \beta$
    • 如$DP(0xf\stackrel{S}{\to }0x1)=0$
  • 对随机置换RP(Random Permutation)
    • $Pr(\alpha \stackrel{RP}{\to }\beta )=\frac{1}{2^4}$
  • DDT中的数都是偶数

2.P置换

拉线操作，只改变bit位置，不改变取值

输出差分等于输入差分经过P置换后的结果

$P(X)\oplus P(X^{\prime })=P(X\oplus X^{\prime })$

3.异或密钥AK

$（X\oplus K)\oplus (X^{\prime }\oplus K)=X\oplus X^{\prime }$

输出差分等于输入差分

总结可得，差分在各部件的传播特性为：

1. 过线性变换差分值确定
   1. 异或密钥差分值不变
2. 过非线性变换差分值不确定，传播概率由S盒DDT决定

3.1.2.2 CipherFour算法的多轮差分路线

i轮差分路线 ${\beta }_0\stackrel{1轮}{\to }{\beta }_1\stackrel{1轮}{\to }{\beta }_2\stackrel{1轮}{\to }...\stackrel{1轮}{\to }{\beta }_i$

i轮差分路线概率

• 分组密码输入X以及轮密钥取值相互独立且均匀分布
• 等于各轮差分路线概率乘积
• $DP({\beta }_0\stackrel{1轮}{\to }{\beta }_1\stackrel{1轮}{\to }{\beta }_2\stackrel{1轮}{\to }...\stackrel{1轮}{\to }{\beta }_i)=\prod _{j=1}^{i}DP({\beta }_{j-1}\stackrel{1轮}{\to }{\beta }_j)$

i轮最优差分路线

• 所有i轮差分路线中概率最大的（可能不止一条）

活跃S盒

• 输入差分非零的S盒

影响i轮差分路线概率的主要因素

• 活跃S盒个数
• 活跃S盒对应的输出差分

CipherFour 1轮最优差分路线

• 需要活跃S盒的个数≥1，由DDT表可得，
  • $DP(0xF\stackrel{S}{\to }0xD)=\frac{10}{2^4}=\frac{5}{8}$

2轮最优差分路线与1轮最优无关

• 直接以1轮最优差分路线的输出差分为输入差分，得到的DP为$\frac{5}{8}\cdot (\frac{3}{5}{)}^3\approx 0.033$
• 保持每轮一个S盒，概率为$DP(0x2\stackrel{S}{\to }0x2)=\frac{6}{2^4}=(\frac{3}{8}{)}^2$,更优

差分路线级联

迭代型差分概率

• 给定概率为$p_i$的i轮差分路线${\beta }_0\stackrel{1轮}{\to }{\beta }_1\stackrel{1轮}{\to }{\beta }_2\stackrel{1轮}{\to }...\stackrel{1轮}{\to }{\beta }_i$，若${\beta }_0={\beta }_i$,迭代该路线k次，得到一条ki轮的差分路线${\beta }_0\stackrel{1轮}{\to }{\beta }_1\stackrel{1轮}{\to }...\stackrel{1轮}{\to }{\beta }_0\stackrel{1轮}{\to }{\beta }_1\stackrel{1轮}{\to }...\stackrel{1轮}{\to }{\beta }_0$

3.1.2.3 CipherFour算法的多轮差分

实验得到i轮差分概率大于单条差分路线的概率。

没有必要固定中间状态的差分

（基于独立性假设）r轮差分的概率

• 共s条输入差分为${\beta }_0$,输出差分为${\beta }_i$的i轮差分路线

$$\begin{gathered} DP(bet{a}_0\stackrel{i轮}{\to }{\beta }_1)=\sum _{t=1}^{s}DP({\beta }_0\stackrel{1轮}{\to }{\beta }_1^t\to ...\to {\beta }_{i-1}^t\stackrel{1轮}{\to }{\beta }_i^t) \\ =\sum _{t=1}^s(\prod _{j=1}^{i}DP({\beta }_{j-1}^t\stackrel{1轮}{\to }{\beta }_j^t)) \end{gathered}$$

Markov密码算法：满足独立性假设的算法

通过不随机现象区分4轮CipherFour算法和随机置换 0.08>0.000015

3.1.2.4 5轮CipherFour算法的密钥恢复攻击

5轮等于4轮CipherFour算法+1 “4+1”

4轮加密后的输出是 中间变量，猜测$k_5$的取值

1. 采样
   • 选择m对满足输入差分的输入对，计算5轮加密后的密文对
2. 去噪
   • 筛选并删除错误对
   • 若四轮加密后中间状态为(0,0,2,0)，由DDT得到$(0,0,2,0)\stackrel{S}{\to }(0,0,h,0),h\in 1,2,9,a$
   • 正确对相应的密文差分只有四种可能 (0,0,1,0), (0,0,2,0), (0,0,9,0), (0,0,a,0)
3. 恢复密钥
   • 解方程$S^{-1}(k_{5,2}\oplus c_2)\oplus S^{-1}(k_{5,2}\oplus c_2^{{}^{\prime }})=2$，并对每个解设置计数器
   • 按计数器取值由大到小对去噪的明文对进行排序，前$2^{4-a}$个作为正确密钥的候选值
   • 恢复4-bit$k_{5,2}$,实现分割
   • 剩余密钥差分或者穷举

正确对:

• 一定满足区分器的头尾差分
• 代入S盒有关方程 解一定包括正确密钥

错误对:

• 一定不满足区分器的头部或尾部差分
• 代入S盒有关方程 解只包含错误密钥

复杂度：重要的是选择明文的个数

信噪比 $S_N$

• 正确密钥(信息)的计数/错误密钥（噪声）的平均计数

• 1 ≤$S_N$ ≤2，需保证有20-40正确对 $S_N$较大

• $S_N$ ≥100时，需保证有3-4个正确对