3.分组密码分析

密码分析学

教 师： 袁 征

第三章、分组密码的分析

2016年 2016 年10月 10月31日 31日

-- 2 --

本章内容

1. 分组密码设计概况 2. 分组密码分析概况 3. AES-128算法的不可能差分分析 4. AES-128算法的低数据Biclique分析 5. GOST算法全轮3-子集中间相遇攻击 6. 约束规划和自动化搜索

-- 3 --

分组密码的设计（安全性原则）

z 安全性原则主要考虑三个方面：

¾ 混乱原则 应使得明文、密文和密钥三者间的依赖关系相当复杂。 ¾ 扩散原则 扩散 则 应使得明文(密钥)的每一位数字影响密文的许多位数 字。 ¾ 抗现有攻击原则 应能抵抗所有已知的攻击。

-- 4 --

分组密码的设计（结构设计）

z 分组密码的结构特征 ¾ SP结构 ¾ Feistel结构 ¾ Lai-Massey结构 结构

分组密码的设计（结构设计）

Li1

Ri1

Ki

F

Li

Ri 一轮Feistel结构示意图

-- 5 --

-- 6 --

1

分组密码的设计（结构设计）

Xi-1

分组密码的设计（结构设计）

Xi-1

…

S盒

… 混合变换 …

Xi

…

P置换

…

Xi 一轮SP结构示意图

-- 7 --

一轮Lai-Massey结构示意图

-- 8 --

分组密码的设计（结构设计）

Feistel结构 • • • • • • • • DES Camellia FEAL Blowfish Mars CAST-256 SMS4 … • • • • • • SP结构

• IDEA • FOX • …

本章内容

1. 分组密码设计概况 2. 分组密码分析概况 3. AES-128算法的不可能差分分析 4. AES-128算法的低数据Biclique分析 5. GOST算法全轮3-子集中间相遇攻击 6. 约束规划和自动化搜索

Lai-Massey结构

Rijndael ARIA Shark Square Serpent …

-- 9 --

-- 10 --

分组密码的分析方法

分组密码的分析方法分为两类：

（1）基于数学理论的分析方法 差分分析、线性分析、积分分析、插值攻击、代 数攻击 （2）基于物理实现的分析方法 计时攻击、能量攻击、电磁攻击、故障攻击、 缓存攻击

¾ ¾ ¾ ¾ ¾

分组密码的分析方法

根据攻击条件的不同，密码分析可分为如下五种类型： 唯密文攻击 已知明文攻击 选择明文攻击 选择密文攻击 相关密钥攻击

-- 11 --

-- 12 --

2

分组密码的分析方法

根据攻击手段不同，密码分析可以分为如下四种类型：

¾

分组密码的分析方法

差分攻击和线性攻击是两种最重要的分析方法：

W 差分攻击及其变种： z 差分攻击 z 高阶差分攻击 z 截断差分攻击、 z 不可能差分攻击 z 飞来去器攻击 z 积分攻击 z 等等。

-- 14 --

朴素攻击方法：暴力破解、查表攻击、字典攻击、 时空权衡 统计攻击方法：差分攻击及其变种、线性攻击及其 统计攻击方法 差分攻击及其变种 线性攻击及其 变种 代数攻击方法：插值攻击、代数攻击 其它攻击：相关密钥攻击、滑动攻击、反射攻击、 中间相遇

-- 13 --

¾

¾ ¾

分组密码的分析方法

W 线性攻击及其变种： z 线性攻击 z 多重线性攻击 z 多维线性攻击 z 零相关线性攻击 z 等等。

分组密码的分析方法

差分攻击和线性攻击的攻击的基本思想：

W 寻找区分器：

将算法与随机置换区分开 W 假设检验： 将正确密钥与错误密钥区分开

-- 15 --

-- 16 --

分组密码的分析方法

代数攻击和插值攻击是两种最有潜力的攻击方法：

W 插值攻击： z 拉格朗日插值公式 z 傅里叶变换。 W 列方程：

分组密码的分析方法

代数攻击和插值攻击攻击的基本思想：

建立密钥、明文、密文三者相关的方程组

W 解方程

求解代数方程组

W 代数攻击： z S盒满足的代数方程 z 超定方程的求解。

-- 17 --

-- 18 --

3

本章内容

1. 分组密码设计概况 2. 分组密码分析概况 3. AES-128算法的不可能差分分析 4. AES-128算法的低数据Biclique分析 5. GOST算法全轮3-子集中间相遇攻击 6. 约束规划和自动化搜索

-- 19 --

AES-128不可能差分分析

z z z z z

基本概念 不可能差分分析方法原理 AES算法及其不可能差分分析 AES算法结构的不可能差分区分器 SPN结构不可能差分的刻画

-- 20 --

基本概念

多数分组密码算法通常 设计成迭代型。即：在 密钥参数控制下，利用 固定结构的轮函数串联 形成密码算法。 形成密码算法

差分分析

r1

加密

r

22 r2 解密

-- 21 --

-- 22 --

不可能差分分析

概率为0的差分路线 中间不可能相遇（Miss in the middle） 尽可能多的头、尾加一些轮数，猜测对应 的密钥： W 正确密钥： 一定不产生不可能差分 W 错误密钥： 一定的概率产生不可能差分 加密

差分分析VS不可能差分分析

差分分析： 利用密码算法的高概率差分（差分传递链），通过 统计方法来恢复密钥。 不可能差分分析： 利用概率为0的差分对正确密钥进行区分，如果用 候选密钥对一对明密文进行部分加脱密之后得到概 率为0的差分对应，那么该候选密钥必定是错误密 钥，应予以抛弃。当抛弃完所有的错误密钥之后剩 余的就为正确密钥。

-- 24 --

解密

-- 23 --

4

不可能差分分析的一般方法

不可能差分区分器的构造阶段 ——选出概率为0的差分（不可能差分区分器）。 密钥筛选阶段 ——利用概率为0的差分恢复密钥的阶段。

不可能差分区分器的构造

直接搜索——Shrinking[Biham 99]、Wu[ 12] 中间相错——U方法[Kim 03]，UID方法[Luo 09]。 “中间相错”是构造不可能差分区分器最基本的 方法。

-- 25 --

-- 26 --

利用中间相错技术，在F函数是双射的条件下构造5轮 Feistel结构的不可能差分区分器。

z z

不可能差分分析的一般步骤

寻找r轮不可能差分a0→ ar ； 选择满足输入差分为a0的明文对(P,P⊕a0)，并进 行r+1轮加密，将求得的密文记作C和C*； 猜测第r+1轮的密钥Kr+1的可能值，用每次猜测 的可能值 用每次猜测 的密钥对C和C*进行一轮脱密，得到r轮输出值 D和D*，判断D⊕D* = ar 是否成立，若成立， 则所猜测的Kr+1一定是错误密钥； 重复上述过程，直至密钥唯一确定。

-- 28 --

z

z

-- 27 --

复杂度分析

z

AES算法及其不可能差分分析

z

假设:

W 第r+1轮涉及的密钥长度为|K|-bit。 W 每个明密对能够淘汰2-t的密钥。

AES算法简介 分组长度：128 密钥长度：128，192，256 迭代圈数：10，12，14 基本模型：SP结构 迭代圈数与密钥长度和分组长度的关系：

密钥长度 圈 数 128 10

-- 30 --

z

在所有的2|K|密钥中，正确密钥为1个，错误密钥 为2|K| -1个。为了保证正确密钥唯一确定，所需要 的明文数量N必须满足，使剩余错误密钥数量小 于1，也即 (2|K| -1) (1-2-t)N 2t-0.53|K|。

192 12

256 14

-- 29 --

5

AES算法及其不可能差分分析

z

AES算法及其不可能差分分析

z

AES算法简介(续1)

AES算法简介(续2)

字节代替变换

行移位变换

-- 31 --

-- 32 --

AES算法及其不可能差分分析

z

AES算法及其不可能差分分析

z

AES算法简介(续3)

AES算法简介(续4)

列混合变换

密钥加

-- 33 --

-- 34 --

AES算法及其不可能差分分析

z

利用4轮不可能差分分析6轮

⎛ α1 0 0 0 ⎞ ⎛ α1 0 0 0 ⎞ ⎛ β1 0 0 0 ⎞ ⎛ β1 ⎜ ⎟ ARK0 ⎜ ⎟ SB ⎜ ⎟ SR ⎜ ⎜ 0 α 2 0 0 ⎟ → ⎜ 0 α 2 0 0 ⎟ → ⎜ 0 β2 0 0 ⎟ → ⎜ β2 ⎜ 0 0 α3 0 ⎟ ⎜ 0 0 α 3 0 ⎟ ⎜ 0 0 β3 0 ⎟ ⎜ β3 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎝ 0 0 0 α4 ⎠ ⎝ 0 0 0 α 4 ⎠ ⎝ 0 0 0 β 4 ⎠ ⎝ β4

⎛? ⎜ ⎜0 ⎜0 ⎜ ⎝? ? ? 0 0 0 ? ? 0 0⎞ ⎟ 0⎟ ?⎟ ⎟ ?⎠

⎛δ ⎜ ⎜0 ⎜0 ⎜ ⎝0 0 0 0⎞ ⎛δ ⎟ ⎜ 0 0 0 ⎟ ARK1 ⎜ 0 ← 0 0 0⎟ ⎜ 0 ⎟ ⎜ 0 0 0⎠ ⎝ 0

AES算法的4轮不可能 差分区分器

同理可得如下16条4 轮不可能差分区分器

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 ⎜ ⎝?

⎛? ⎜ ⎜? ⎜? ⎜ ⎝?

-- 35 --

? 0 0⎞ ⎛ ? ⎟ ⎜ ? ? 0 ⎟ SB−1 ⎜ 0 ← 0 ? ?⎟ ⎜0 ⎟ ⎜ 0 0 ?⎠ ⎝?

0⎞ ⎛? ⎟ ⎜ 0 ⎟ SB−1 ⎜ ? ← 0⎟ ⎜? ⎟ ⎜ 0⎠ ⎝?

? 0 0⎞ ⎛? ⎟ ⎜ ? ? 0 ⎟ SR−1 ⎜ ? ← 0 ? ? ⎟ ⎜? ⎟ ⎜ 0 0 ? ⎠ ⎝?

0⎞ ⎛ ? ⎟ ⎜ 0 ⎟ SR−1 ⎜ ? ← 0⎟ ⎜0 ⎟ ⎜ 0⎠ ⎝0

? 0 0⎞ ⎛? ⎟ ⎜ ? 0 0 ⎟ MC −1 ⎜ ? ← ? 0 0⎟ ⎜? ⎟ ⎜ ? 0 0⎠ ⎝?

0⎞ ⎛? ⎟ ⎜ ? ⎟ ARK6−1 ⎜ ? ← ⎜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 ?

0 0 ? ?

? 0 0 ?

0 0 ? ?

-- 36 --

6

⎛ α1 0 ⎜ ⎜ 0 α2 ⎜0 0 ⎜ ⎝0 0

⎛0 ⎜? ⎜ ⎜? ⎜ ⎝?

0 0

α3

0

⎞ ⎛ α1 0 ⎟ ARK0 ⎜ ⎟ → ⎜ 0 α2 ⎟ ⎜0 0 ⎟ ⎜ α4 ⎠ ⎝0 0 0 0 0

0 0

α3

0

⎞ ⎛ β1 ⎟ SB ⎜ ⎟→⎜ 0 ⎟ ⎜0 ⎟ ⎜ α4 ⎠ ⎝ 0 0 0 0

0

β2

0 0

⎛δ ⎜ ⎜0 ⎜0 ⎜ ⎝0

0 0

β3

0

0 0 0 0 0 0 0 0

⎞ ⎛ β1 ⎟ SR ⎜ ⎟ → ⎜ β2 ⎟ ⎜ β3 ⎟ ⎜ β4 ⎠ ⎝ β4 0 0 0

0⎞ ⎛δ ⎟ ⎜ 0 ⎟ ARK1 ⎜ 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⎟ ⎟ → ⎜? ? 0 0⎟ ⎜? ⎟ ⎜ ? 0 0⎠ ⎝?

? 0 0⎞ ⎛ ? ⎜ SR −1 ? 0 0⎟ ⎟ ←⎜? ? 0 0⎟ ⎜ 0 ⎟ ⎜ ? 0 0⎠ ⎝ 0

? 0 0⎞ ⎛? −1 ⎜ ARK 6 0 0 ?⎟ ⎟ ← ⎜? ⎜0 0 ? ?⎟ ⎟ ⎜ ? ? 0⎠ ⎝0

? 0 0⎞ 0 0 ?⎟ ⎟ 0 ? ?⎟ ⎟ ? ? 0⎠

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个明密对被留下。

Step 1. 选择2N组明文结构：每一组在0,5,10,15字 节处遍历{0,1}8,其余12个字节取常值。对这些明 文加密，得到相应的密文。 PS: 一个结构中包含232组明文，每个结构内部能 够生成263对差分对。全部结构能够生成263+N 对 63+N 对密文。 明文。因此可以获得2 -- 37 --

-- 38 --

⎛ α1 0 0 0 ⎞ ⎛ α1 0 0 0 ⎞ ⎛ β1 ⎜0 α ⎟ SB ⎜ ARK 0 ⎜ 0 0⎟ 2 ⎜ ⎟ → ⎜ 0 α2 0 0 ⎟ → ⎜ 0 ⎜ 0 0 α3 0 ⎟ ⎜ 0 0 α3 0 ⎟ ⎜ 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎝ 0 0 0 α4 ⎠ ⎝ 0 0 0 α4 ⎠ ⎝ 0

⎛0 ⎜ ⎜? ⎜? ⎜ ⎝? ? 0 0⎞ ⎟ ? 0 0⎟ ? 0 0⎟ ⎟ 0 0 0⎠

0

β2

0 0

⎛δ ⎜ ⎜0 ⎜0 ⎜ ⎝0

0 0

β3

0

0 ⎞ ⎛ β1 ⎜ SR 0⎟ ⎟ → ⎜ β2 0 ⎟ ⎜ β3 ⎟ ⎜ β4 ⎠ ⎝ β4

0 0 0⎞ 0 0 0⎟ ⎟ 0 0 0⎟ ⎟ 0 0 0⎠

0 0 0⎞ ⎟ 0 0 0⎟ 0 0 0⎟ ⎟ 0 0 0⎠

⎛ α1 0 0 0 ⎞ ⎛ α1 0 0 0 ⎞ ⎛ β1 ⎜ ⎟ ARK0 ⎜ ⎟ SB ⎜ ⎜ 0 α2 0 0 ⎟ → ⎜ 0 α2 0 0 ⎟ → ⎜ 0 ⎜ 0 0 α3 0 ⎟ ⎜ 0 0 α3 0 ⎟ ⎜ 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎝ 0 0 0 α4 ⎠ ⎝ 0 0 0 α4 ⎠ ⎝ 0

⎛0 ⎜ ⎜? ⎜? ⎜ ⎝? ? 0 0⎞ ⎟ ? 0 0⎟ ? 0 0⎟ ⎟ 0 0 0⎠

0

β2

0 0

⎛δ ⎜ ⎜0 ⎜0 ⎜ ⎝0

0 0

β3

0

0 ⎞ ⎛ β1 ⎟ ⎜ 0 ⎟ SR ⎜ β 2 → 0 ⎟ ⎜ β3 ⎟ ⎜ β4 ⎠ ⎝ β4

0 0 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 0 0 ⎟ ARK1 ⎜ 0 ← ⎟ ⎜0 0 0 0 ⎟ ⎜ 0 0 0⎠ ⎝0

0 0 0⎞ ⎛δ ⎟ ⎜ 0 0 0 ⎟ ARK1 ⎜ 0 ← ⎜0 0 0 0⎟ ⎟ ⎜ 0 0 0⎠ ⎝0

⎛? ⎜ ⎜? ⎜? ⎜ ⎝?

? 0 0⎞ ⎛? ⎟ ⎜ ? 0 0 ⎟ SB −1 ⎜ ? → ? 0 0⎟ ⎜? ⎟ ⎜ ? 0 0⎠ ⎝?

? 0 0⎞ ⎛ ? ⎟ ⎜ ? 0 0 ⎟ SR−1 ⎜ ? ← ? 0 0⎟ ⎜ 0 ⎟ ⎜ ? 0 0⎠ ⎝ 0

? 0 0⎞ ⎛? ⎟ −1 ⎜ 0 0 ? ⎟ ARK6 ⎜ ? ← ⎟ ⎜0 0 ? ? ⎟ ⎜ ? ? 0⎠ ⎝0

? 0 0⎞ ⎟ 0 0 ?⎟ 0 ? ?⎟ ⎟ ? ? 0⎠

⎛? ⎜ ⎜? ⎜? ⎜ ⎝?

? ? ? ?

0 0 0 0

0⎞ ⎛? ⎟ ⎜ 0 ⎟ SB −1 ⎜ ? → 0⎟ ⎜? ⎟ ⎜ 0⎠ ⎝?

? ? ? ?

0 0 0 0

0⎞ ⎛ ? ⎟ ⎜ 0 ⎟ SR−1 ⎜ ? ← 0⎟ ⎜ 0 ⎟ ⎜ 0⎠ ⎝ 0

? 0 0 ?

0 0 ? ?

0⎞ ⎛? ⎟ −1 ⎜ ? ⎟ ARK6 ⎜ ? ← ⎜0 ?⎟ ⎟ ⎜ 0⎠ ⎝0

? 0 0 ?

0 0 ? ?

0⎞ ⎟ ?⎟ ?⎟ ⎟ 0⎠

Step 3. 猜测K6的第0,1,4,7,10,11,13,14字节，对每次猜 测进行下列操作： PS: 此时的猜测不论对错，均将导致经过MC-1之后 的字节矩阵后两列差分为0。

-- 39 --

Step 3.1 记录在(0,7)/(1,4)/(2,5)/(3,6)位置为0的密文对与 相应的K6，总共记录 2N-1×4×2-8×2=2N-15个明文对。 PS: 此时留下的密文对满足不可能差分的输出差分。

-- 40 --

⎛ α1 0 0 0 ⎞ ⎛ α1 0 0 0 ⎞ ⎛ β1 ⎜ ⎟ ARK0 ⎜ ⎟ SB ⎜ ⎜ 0 α2 0 0 ⎟ → ⎜ 0 α2 0 0 ⎟ → ⎜ 0 ⎜ 0 0 α3 0 ⎟ ⎜ 0 0 α3 0 ⎟ ⎜ 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎝ 0 0 0 α4 ⎠ ⎝ 0 0 0 α4 ⎠ ⎝ 0

⎛0 ⎜ ⎜? ⎜? ⎜ ⎝? ? ? ? 0 0 0 0 0 0⎞ ⎟ 0⎟ 0⎟ ⎟ 0⎠

0

0 0

β2

0 0

⎛δ ⎜ ⎜0 ⎜0 ⎜ ⎝0

β3

0

0 0 0 0 0 0 0 0

0 ⎞ ⎛ β1 ⎟ ⎜ 0 ⎟ SR ⎜ β 2 → 0 ⎟ ⎜ β3 ⎟ ⎜ β4 ⎠ ⎝ β4

0⎞ ⎛δ ⎟ ⎜ 0 ⎟ ARK1 ⎜ 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⎠

⎛ α1 0 0 0 ⎞ ⎛ α1 0 0 0 ⎞ ⎛ β1 ⎜ ⎟ ARK0 ⎜ ⎟ SB ⎜ ⎜ 0 α2 0 0 ⎟ → ⎜ 0 α2 0 0 ⎟ → ⎜ 0 ⎜ 0 0 α3 0 ⎟ ⎜ 0 0 α3 0 ⎟ ⎜ 0 ⎜ ⎟ ⎜ ⎟ ⎜ ⎝ 0 0 0 α4 ⎠ ⎝ 0 0 0 α4 ⎠ ⎝ 0

⎛0 ⎜ ⎜? ⎜? ⎜ ⎝? ? 0 0⎞ ⎟ ? 0 0⎟ ? 0 0⎟ ⎟ 0 0 0⎠

0

β2

0 0

⎛δ

0 0

β3

0

⎞ ⎛ β1 ⎟ SR ⎜ ⎟ → ⎜ β2 ⎟ ⎜ β3 ⎟ ⎜ β4 ⎠ ⎝ β 4 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⎠

4-R

0 0 0⎞ ⎛δ ⎜ 0 0 0 0 ⎟ ARK1 ⎜ 0 ⎜ ⎟←⎜ ⎜ 0 0 0 0⎟ ⎜0 ⎜ ⎟ ⎜ ⎝ 0 0 0 0⎠ ⎝0

⎛? ⎜ ⎜? ⎜? ⎜ ⎝?

? ? ? ?

0 0 0 0

0⎞ ⎛? ⎟ ⎜ 0 ⎟ SB−1 ⎜ ? → 0⎟ ⎜? ⎟ ⎜ 0⎠ ⎝?

? ? ? ?

0 0 0 0

0⎞ ⎛ ? ⎟ ⎜ 0 ⎟ SR−1 ⎜ ? ← 0⎟ ⎜0 ⎟ ⎜ 0⎠ ⎝0

? 0 0 ?

0 0 ? ?

0⎞ ⎛? ⎟ −1 ⎜ ? ⎟ ARK6 ⎜ ? ← ⎜0 ?⎟ ⎟ ⎜ 0⎠ ⎝0

? 0 0 ?

0 0 ? ?

0⎞ ⎟ ?⎟ ?⎟ ⎟ 0⎠

⎛? ⎜ ⎜? ⎜? ⎜ ⎝?

? 0 0⎞ ⎛? ⎟ ⎜ ? 0 0 ⎟ SB−1 ⎜ ? → ? 0 0⎟ ⎜? ⎟ ⎜ ? 0 0⎠ ⎝?

? 0 0⎞ ⎛ ? ⎟ ⎜ ? 0 0 ⎟ SR−1 ⎜ ? ← ? 0 0⎟ ⎜0 ⎟ ⎜ ? 0 0⎠ ⎝0

? 0 0⎞ ⎛? ⎟ −1 ⎜ 0 0 ? ⎟ ARK6 ⎜ ? ← ⎜0 0 ? ?⎟ ⎟ ⎜ ? ? 0⎠ ⎝0

? 0 0⎞ ⎟ 0 0 ?⎟ 0 ? ?⎟ ⎟ ? ? 0⎠

Step 3.2 猜测K0的第0,5,10,15块的取值，计算经过SR 变换之后的差分值： 如果差分值在第一列仅一个字节为非零(概率为4×28×3 =2-22)，则此时对应的 (K0[0,5,10,15], K6[0,1,4,7,10,11,13,14]) 字节为错误密钥， 应予淘汰； -- 41 --

Step 4. 重复Step 3直至密钥唯一确定。

-- 42 --

7

算法分析

z

算法分析

数据复杂度为2N+32 =275.5个明密对； 时间复杂度为Step3.1和Step3.2决定，约为2114.4次6轮 AES加密； 存储复杂度由两部分构成：Step2所需要存储的明密对 +全部候选密钥，约为296

待求K0[0,5,10,15], K6[0,1,4,7,10,11,13,14]涉及的密钥 为K0的4字节和K6的8字节，总的密钥量为264+32，其 中正确密钥只有1个。故总的错误密钥量为296-1。 Step3.2 Step3 2中，对 中 对一组明密对而言 组明密对而言，一个错误密钥被保 个错误密钥被保 留下来的概率为 1 − 2−22，总共有2N-15组明密对，当 N=43.5时，错误密钥值为

(296 − 1) (1 − 2−22 )

2 N −15

z

-- 43 --

-- 44 --

AES算法的不可能差分区分器

z

差分分支数与SPS结构的不可能差分

差分分支数给出了SPS结构中 任意一条差分链的活动S盒个 数的最小值。 z 换而言之，如果SPS结构的一 条差分链的活动S盒个数小于 该最小值(差分分支数)，那么 该差分链成立的概率为0。 AES列混合变换的分支数为5，故任意一条差分链， 只要其在列混合变换层的输入输出活动S盒的个数 小于5，那么该差分链成立的概率为0。

z

线性变换的分支数

定义 设P:{0,1}mn →{0,1}mn是二元域上的线性变换，则称

Br ( P ) = min{wtm ( A) + wtm ( P × B ) : A ≠ 0}

为线性变换P相对于m比特块的差分分支数。 比特块的差分分支数

-- 45 --

任意给定SP结构，则至少存在2轮不可能差分区分 器 -- 46 --

AES算法的4轮不可能差分

z z

4轮AES算法结构变形

4轮AES的加密结构 4-AES(m)

=SB○(MC○ SR○SB)○(MC○ SR○SB)○(MC○ SR○SB)(m) =SB○(MC○ SB○SR)○(MC○ SR○SB)○(MC○ SB ○SR)(m) Super S-box Super S-box Super P-box =(SB○MC○ SB)○(SR○MC○ SR)○(SB○MC○ SB)○[(SR)(m)]

4轮变形AES算法结构图

-- 47 --- 48 --

8

AES的不可能差分最长轮数

32bit S盒 面向32bit S盒的 分支数为5，因此 活动(32bit) S盒的 个数不足5的差分 均为不可能差分。

Observation 1

Question1: 形如此类的不可能差分有多少？

-- 49 --

-- 50 --

本章内容

1. 分组密码设计概况 2. 分组密码分析概况 3. AES-128算法的不可能差分分析 4. AES-128算法的低数据Biclique分析 5. GOST算法全轮3-子集中间相遇攻击 6. 约束规划和自动化搜索

-- 51 --- 52 --

Step 1

Step 2

Step 3

Biclique分析方法

数据搜集 Biclique构造

Biclique分析方法

1、密钥分割: 将整个密钥空间分割成2k-2d个组, 每个组由 2d ×2d 个元素K[i, j]组成. 2、d 维Biclique构造: 对于任一个这样的组, 构造一个有2d个 中 间状态 Sj 和 2d 个密文Ci 的结构, 并满足条件

Ci = f K [i , j ] ( S j ) , ∀i, j ∈ {0,1,…, 2 d − 1}

匹配检查

3、数据搜集: 解密密文Ci得到相应的明文Pi.

-- 53 --- 54 --

9

Biclique分析方法

4、匹配检查: 检查是否存在 i , j 满足

[ ] [ ] Pi ⎯⎯⎯ → vi = v j ←⎯⎯ ⎯ Sj   g h −1

K i, j K i, j ?

Biclique分析方法

Biclique构造

注意：计算量可以通过预计算和重计算减少.

首先 , 计算并存储 2d 个部分加密过程 , 2d 个部分解密 过程中所涉及的所有中间状态和子密钥的值.

[ ] i = 0,1,..., 2d − 1: Pi ⎯⎯⎯ → vi 和 g

K i ,0

[ ] j = 0,1,..., 2 d − 1:i v j ←⎯⎯ ⎯ Sj h −1

K 0, j

其次， 在计算其余密钥匹配过程时，如果中间状态与 前者相同，则无须再计算。

-- 55 --- 56 --

构造Biclique结构的一种方法 -差分路径的应用

z

AES-128算法

AES-128算法的轮函数如下：

a0 a4 a8 a12 a1 a5 a9 a13 a2 a6 a10 a14 a3 a7 a11 a15 ′ a4 ′ a8 ′ a12 ′ a0

′ a4 ′ a8 ′ a12 ′ a0 ′′ ′′ a8 ′′ a4 a0 ′′ ′′ a9 ′′ a13 a5 ′′ ′′ a14 ′′ a2 a10 ′′ ′′ a3 ′′ a7 a15 ′′ a12 ′′ a1 ′′ a6 ′′ a11

用不相交的差分路径构造Biclique结构

设密钥 K [ 0,0] 将中间状态 S0 映射到密文 C0 。考虑两类差分路径： z z

∇ j -差分路径，满足： ∇ j ⎯⎯→ 0 ，其中 ∇ = 0, ∇0 = 0 f

K 0

Δi K → Δ i ，其中 差分路径 满足 0 ⎯⎯ 其中 Δ 0 = 0, 0 Δ0 = 0 Δi -差分路径，满足： f

K

∇K j

SB

′ a5 ′ a9 ′ a13 ′ a1 ′ a6 ′ a10 ′ a14 ′ a2 ′ a15 ′ ′ a7 ′ a11 a3

SR

′ a9 ′ a13 ′ ′ a1 a5 ′ a14 ′ a2 ′ a6 ′ a10 ′ a11 ′ ′ a3 ′ a7 a15

MC

AK

rk ki

如果 Δ i -差分路径和 ∇ j -差分路径不相交，则可以构造一个联合差分路径：

i j ∇ i ⎯⎯⎯⎯ → Δ j ，对所有 i, j ∈ 0,… , 2d − 1 f

AES-128算法的密钥扩展算法如下：

i +1 i i i rkcolumn (0) = rkcolumn(0) ⊕ RotWord (SubWord (rkcolumn(3) )) ⊕ C i +1 i i +1 rkcolumn ( j ) = rkcolumn( j ) ⊕ rkcolumn( j −1)

∇ K ⊕Δ K

{

}

用联合差分路径，从 S0 、 C0 和 K [ 0,0] 出发，可以构造 Sj → Ci 的一个 d 维的 Biclique 结构：

j i S0 ⊕ ∇ j ⎯⎯⎯⎯⎯⎯ → C0 ⊕ Δ i f

K [ 0,0]⊕∇ K ⊕Δ K

, j=1,2,3.

-- 58 --

-- 57 --

对AES-128的低数据Biclique分析

1、密钥分割：对末尾轮子密钥空间进行分割, 设轮子密钥rk10有 两个字节为0, 记为rk10[0, 0], 位置如左下图所示, 其它字节进行 穷举, rk10[i, j]是枚举rk10[0, 0]上所有i, j的字节差分值, 密钥有差 分的位置如右下图所示.

对AES-128的低数据Biclique分析

2、构造8维的2轮Biclique结构：

0

i

j j

i

⎛0 ⎜ 0 Ci = ⎜ ⎜0 ⎜ ⎝0

0 ∗i 0 0 0 0 0 0

i⎞ ⎟ 0⎟ 0⎟ ⎟ 0⎠

0

∗i = SB(SB−1 (0) ⊕ i ) ⊕ i

rk10[0, 0]

密钥集{rk10[i, j]}

-- 59 --

-- 60 --

10