“中间相错”是构造不可能差分区分器最基本的 方法。
-- 25 --
-- 26 --
利用中间相错技术，在F函数是双射的条件下构造5轮 Feistel结构的不可能差分区分器。
-- 27 --
不可能差分分析的一般步骤
z 寻找r轮不可能差分a0→ ar ； z 选择满足输入差分为a0的明文对(P,P⊕a0)，并进
PS: 一个结构中包含232组明文，每个结构内部能 够生成263对差分对。全部结构能够生成263+N 对 明文。因此可以获得263+N 对密文。
-- 37 --
Step 2. 在Step1生成的263+N个密文对中，保留在第 2,3,5,6,8,9,12,15这8个字节处为0的密文对，并抛弃 其余的密文对。 PS:密文满足Step2条件的概率为(2-8)8=2-64,因此， 经过Step2，剩余2N+63-64=2N-1个明密对被留下。
W 正确密钥： 一定不产生不可能差分
W 错误密钥： 一定的概率产生不可能差分
-- 23 --
加密 解密
差分分析VS不可能差分分析
差分分析： 利用密码算法的高概率差分（差分传递链），通过 统计方法来恢复密钥。
不可能差分分析： 利用概率为0的差分对正确密钥进行区分，如果用 候选密钥对一对明密文进行部分加脱密之后得到概 率为0的差分对应，那么该候选密钥必定是错误密 钥，应予以抛弃。当抛弃完所有的错误密钥之后剩 余的就为正确密钥。
?
0
0
⎟ ⎟
⎜0 0 ? ?⎟ ⎜0 0 ? ?⎟ ⎜? ? 0 0⎟ ⎜? ? 0 0⎟
⎜
⎟⎜
⎟⎜
⎟⎜
⎟
⎝? 0 0 ?⎠ ⎝? 0 0 ?⎠ ⎝? ? 0 0⎠ ⎝? ? 0 0⎠
4-R
⎛? ? 0 0⎞ ⎛? ? 0 0⎞ ⎛? ? 0 0⎞ ⎛? ? 0 0⎞
⎜ ⎜
?
?
0
0
⎟ ⎟
SB−1
←
⎜ ⎜
行r+1轮加密，将求得的密文记作C和C*； z 猜测第r+1轮的密钥Kr+1的可能值，用每次猜测
的密钥对C和C*进行一轮脱密，得到r轮输出值 D和D*，判断D⊕D* = ar 是否成立，若成立， 则所猜测的Kr+1一定是错误密钥； z 重复上述过程，直至密钥唯一确定。
-- 28 --
复杂度分析
z 假设:
?
?
0
0
⎟ ⎟
⎜? ? 0 0⎟
⎜ ⎝
?
0
0
0
⎟ ⎠
⎛δ 0 0 0⎞ ⎛δ 0 0 0⎞
⎜ ⎜
0
0
0
⎜ ⎜
0
0
0
0
⎟ ⎟
⎜0 0 0 0⎟ ⎜0 0 0 0⎟
⎜ ⎝
0
0
0
0
⎟ ⎠
⎜ ⎝
0
0
0
0
⎟ ⎠
⎛? ? 0 0⎞ ⎛? ? 0 0⎞ ⎛? ? 0 0⎞ ⎛? ? 0 0⎞
⎜ ⎜
⎟
⎝0 0 0 0⎠ ⎝0 0 0 0⎠
⎛? ? 0 0⎞ ⎛? ? 0 0⎞ ⎛? ? 0 0⎞ ⎛? ? 0 0⎞
⎜ ⎜
?
?
0
0
⎟ ⎟
SB −1
→
⎜ ⎜
?
?
0
0
⎟ ⎟
SR−1
←
⎜ ⎜
?
0
0
?
⎟ ⎟
ARK6−1
←
⎜ ⎜
?
0
0
?
⎟ ⎟
分组密码的设计（结构设计）
Feistel结构
• DES • Camellia • FEAL • Blowfish • Mars • CAST-256 • SMS4 •…
SP结构
• Rijndael • ARIA • Shark • Square • Serpent •…
Lai-Massey结构
• IDEA • FOX •…
-- 18 --
3
本章内容
1. 分组密码设计概况 2. 分组密码分析概况 3. AES-128算法的不可能差分分析 4. AES-128算法的低数据Biclique分析 5. GOST算法全轮3-子集中间相遇攻击 6. 约束规划和自动化搜索
-- 19 --
AES-128不可能差分分析
z 基本概念 z 不可能差分分析方法原理 z AES算法及其不可能差分分析 z AES算法结构的不可能差分区分器 z SPN结构不可能差分的刻画
W 第r+1轮涉及的密钥长度为|K|-bit。 W 每个明密对能够淘汰2-t的密钥。
z 在所有的2|K|密钥中，正确密钥为1个，错误密钥 为2|K| -1个。为了保证正确密钥唯一确定，所需要 的明文数量N必须满足，使剩余错误密钥数量小 于1，也即 (2|K| -1) (1-2-t)N<1 近似等价于N > 2t-0.53|K|。
-- 24 --
4
不可能差分分析的一般方法
不可能差分区分器的构造阶段 ——选出概率为0的差分（不可能差分区分器）。
密钥筛选阶段 ——利用概率为0的差分恢复密钥的阶段。
不可能差分区分器的构造
直接搜索——Shrinking[Biham 99]、Wu[ 12]
中间相错——U方法[Kim 03]，UID方法[Luo 09]。
分组密码的分析方法
代数攻击和插值攻击是两种最有潜力的攻击方法：
W插值攻击： z 拉格朗日插值公式 z 傅里叶变换。
W代数攻击： z S盒满足的代数方程 z 超定方程的求解。
分组密码的分析方法
代数攻击和插值攻击攻击的基本思想：
W列方程： 建立密钥、明文、密文三者相关的方程组
W解方程 求解代数方程组
-- 17 --
（2）基于物理实现的分析方法 计时攻击、能量攻击、电磁攻击、故障攻击、
缓存攻击
-- 11 --
分组密码的分析方法
根据攻击条件的不同，密码分析可分为如下五种类型： ¾ 唯密文攻击 ¾ 已知明文攻击 ¾ 选择明文攻击 ¾ 选择密文攻击 ¾ 相关密钥攻击
-- 12 --
2
分组密码的分析方法
根据攻击手段不同，密码分析可以分为如下四种类型： ¾ 朴素攻击方法：暴力破解、查表攻击、字典攻击、 时空权衡
?
?
0
0
⎟ ⎟
SB−1
→
⎜ ⎜
?
?
0
0
⎟ ⎟
SR−1
←
⎜ ⎜
?
0
0
?
⎟ ⎟
ARK6−1
←
⎜ ⎜
?
0
0
?
⎟ ⎟
⎜? ? 0 0⎟ ⎜? ? 0 0⎟ ⎜0 0 ? ?⎟ ⎜0 0 ? ?⎟
⎜
⎟⎜
⎟⎜
⎟⎜
⎟
⎝? ? 0 0⎠ ⎝? ? 0 0⎠ ⎝0 ? ? 0⎠ ⎝0 ? ? 0⎠
Step 1. 选择2N组明文结构：每一组在0,5,10,15字 节处遍历{0,1}8,其余12个字节取常值。对这些明 文加密，得到相应的密文。
-- 20 --
基本概念
多数分组密码算法通常 设计成迭代型。即：在 密钥参数控制下，利用 固定结构的轮函数串联 形成密码算法。
-- 21 --
差分分析
r1 加密
r
22 r2 解密
-- 22 --
不可能差分分析
概率为0的差分路线 中间不可能相遇（Miss in the middle） 尽可能多的头、尾加一些轮数，猜测对应 的密钥：
⎜ ⎜
0
α2
0
0
⎟ ⎟
ARK0
→
⎜ ⎜
0
α2
0
0
⎟⎜
⎟
SB
→
⎜
0
β2
0
0
⎟ ⎟
SR
→
⎜ ⎜
β
2
0
0
0
⎟ ⎟
⎜0 ⎜ ⎝0
0 0
α3 0
0⎟
α
4
⎟ ⎠
⎜0 ⎜ ⎝0
0 0
α3 0
0⎟
α
4
⎟ ⎠
⎜0 ⎜ ⎝0
0 0
β3 0
0⎟
β
4
⎟ ⎠
⎜ ⎜ ⎝
β3 β4
0 0
0 0
0⎟ ⎟
0⎠
⎛0 ? 0 0⎞
⎜ ⎜
-- 3 --
分组密码的设计（安全性原则）
z 安全性原则主要考虑三个方面：
¾ 混乱原则 应使得明文、密文和密钥三者间的依赖关系相当复杂。
¾ 扩散原则 应使得明文(密钥)的每一位数字影响密文的许多位数 字。
¾ 抗现有攻击原则 应能抵抗所有已知的攻击。
-- 4 --
分组密码的设计（结构设计）
z 分组密码的结构特征 ¾ SP结构 ¾ Feistel结构 ¾ Lai-Massey结构
⎜0 ⎜ ⎝0
0 0
β3 0
0⎟
β
4
⎟ ⎠
⎜ ⎜ ⎝
β3 β4
0 0
0 0
0⎟ ⎟
0⎠
⎛0 ? 0 0⎞
⎜ ⎜
?
?
0
0
⎟ ⎟
⎜? ? 0 0⎟
⎜ ⎝
?
0
0
0
⎟ ⎠
⎛δ 0 0 0⎞ ⎛δ 0 0 0⎞
4-R
⎜ ⎜
0
0
0
0
⎟ ⎟
ARK1
←
⎜ ⎜
0
0
0
0
⎟ ⎟
⎜0 0 0 0⎟ ⎜0 0 0 0⎟