对称密码学备忘，课程证明太多，所以整理得很简略

对称密码学备忘

分组密码的统计测试原理与分析攻击方法

分组密码的统计测试原理

数据变换的有效性测试原理

• 随机性测试

  • 样本数据：若干密文分组组成的样本
  • 频数检验：0 ，1 个数
  • 跟随性检验：相邻比特

• 明密文独立性测试

  • 测试密文是否有不依赖于明文统计特性的性质

算法对明文的扩散性测试原理

• 明文的雪崩现象：改变明文分组的任一比特，密文分组中大约一半比特变化

密钥更换的有效性检测原理

• 密钥的雪崩现象：改变密钥的任一比特，密文分组中大约一半比特变化

分组密码的分析攻击方法

什么是密码分析攻击

• 一个能够把某个密码算法与一个随机函数区分开的算法
• 攻击的复杂度
  • 数据复杂度：所需明密文数目
  • 存储复杂度
  • 时间复杂度：通常是多少次加解密或内存读取

基本的分析攻击方法

字典攻击

• 两个阶段
  • 预计算阶段：对某未知的密钥 $K$，对每个可能的明文 $P_i$，计算 $C_i=E_{K}(P_i)$，最后按 $C_i$ 索引 $P_i$
  • 在线攻击阶段：一旦获得相应密文，便查表查出明文
• 攻击复杂度

  • 数据复杂度：$2^n$ 个明文——密文对

  • 存储复杂度：$n*2^n$ bits

  • 时间复杂度：一次查表

    • 预计算表生成时间通常不计入

密码本攻击

• 两个阶段
  • 预计算阶段：对某一个特定明文 $P$，对每个可能的密钥 $K_i$，计算 $C_i=E_{K_i}(P)$，最后按 $C_i$ 索引 $K_i$
  • 在线攻击阶段：一旦获得相应密文，便查表查出密钥
• 攻击复杂度

  • 数据复杂度：$2^K$ 个密文

  • 存储复杂度：$n*2^K$ bits

  • 时间复杂度：一次查表

    • 预计算表生成时间通常不计入

穷尽密钥搜索攻击（穷搜索）

• 给定一个已知的明密文对 $(P,C)$，遍历密钥 $K$ 是否满足 $C=E_K(P)$
• 攻击复杂度
  • 数据复杂度：1 个已知明密文对
  • 存储复杂度：可忽略
  • 时间复杂度：$2^K$ 次加密

时空折中分析

• 穷搜索攻击和密码本/字典攻击的组合折中，以时间换取空间
• 对流密码很有效

差分攻击

• 一般工作在选择明/密文攻击场景

• 基本思想

  • 通过分析明文对的差分对密文对的差分的影响来恢复某些密钥比特
  • 差分的定义：最常用的异或
  • 输入间的差分：输入差分
  • 函数输出的差分：输出差分
  • 内部值的差分：中间差分

• 攻击原理

  • 基于一个差分/差分特征
    • 一个差分是一输入差分和一输出差分的组合。 一个差分特征是一条始于输入差分终于输出差分的中间 差分路径（differential path）。 一个 n 比特分组密码 $\mathbb{E}$ 的差分 $(\alpha,\beta)$ ，写作 $\Delta \alpha \rightarrow \Delta \beta$ ，其概率定义为为 $\operatorname{Pr}_{\mathbb{E}}(\Delta \alpha \rightarrow \Delta \beta)=\operatorname{Pr}_{P \in\{0,1\}^{n}}(\mathbb{E}(P) \oplus \mathbb{E}(P \oplus \alpha)=\beta)$

• 对于一个（具有同样参数的）随机的置换，任意（非零 ）差分的期望概率为 $2^{-n}$ 。 因此，如果 $\operatorname{Pr}_{\mathrm{E}}(\Delta \alpha \rightarrow \Delta \beta)$ 大于 $2^{-n}$ ，可利用该差分/差分特征将 $\mathbb{E}$ 与一个随机置换区分开来

  • DDT表:

    • 每一行表示输入（或输出）差分的可能值;
    • 每一列表示输出（或输入）差分的可能值;
    • 每一项表示满足相应输入输出差分对的输入的数目

  • 分组密码的一个差分（differential)

    • 一个一轮的差分特征通常由该轮的每个基本操作的一个差分特征连接而成
      • 前一个基本操作的输出差分是后一个基本操作的输入差分。
    • 多轮的差分特征通常是由其中每轮的一个差分特征连接而成
      • 前一轮的输出差分是后一轮的输入差分。

• 攻击复杂度

  • 数据复杂度：选择明文数量
  • 存储复杂度：运行攻击需要的内存，通常包含明密文对的存储
  • 时间复杂度
    • $K_{a}$ 下 ~$\mathbb{E}_{K_{a}}^{a}$ 中的部分加密。
    • $\left\{K_{a}, K_{b}\right\}$ 下 $\mathbb{E}_{K_{b}}^{b}$ 中的部分解密。
    • 查找表（内存访问）
    • 恢复剩余密钥 $K-\left\{K_{a}, K_{b}\right\}$ 的时间复杂度
    • 明密文对的生成时间通常不计入攻击的时间复杂度（保守地，可以计入）。如果攻击比穷尽密钥搜索快，则认为攻击有效。

截断差分分析

• 差分分析的一个变形

• 一般工作在选择明密文攻击场景

• 攻击原理：基于一个截断差分（特征）。

  • 截断差分（特征）是只标记输入/输出（中间) 差分的部分细节的差分（特征）或对零/非零差分仅标记为零/非零差分。
  • 相应地，计算截断差分（特征） 的概率。
  • 如果截断差分的概率大于其在随机置换下的概率，即可用它将该分组密码与随机置换区分开来。

• 主要应用结果

  • 8 轮的 CRYPTON 分组密码
  • 整轮的 KLEIN-64 分组密码

高阶差分分析

• 差分分析的一个扩展

• 一般工作在选择明密文攻击场景

• 攻击原理：基于一个高阶差分

  • $\mathbf{f}$ 是一个函数, $\mathbf{f}$ 在点 $\alpha$ 的导数定义为
    $\Delta_{\alpha} \mathbf{f}(x)=\mathbf{f}(x+\alpha)-\mathbf{f}(x)$
    $\mathbf{f}$ 在点 $\left(\alpha_{1}, \cdots, \alpha_{i}\right)$ 的 $i$ 阶导数定义为
    $\Delta_{\alpha_{1}, \cdots, \alpha_{i}}^{(i)} \mathbf{f}(x)=\Delta_{\alpha_{i}}\left(\Delta_{\alpha_{1}, \cdots, \alpha_{i-1}}^{(i-1)} \mathbf{f}(x)\right)$
    那么, $\mathbf{f}$ 的一个 $i$-阶差分是一个满足 $\Delta_{\alpha_{1}, \cdots, \alpha_{i}}^{(i)} \mathbf{f}(x)=\beta$ 的 $i+1$ 阶元组 $\left(\alpha_{1}, \cdots, \alpha_{i}, \beta\right)$ 。

• 计算一个高阶差分的概率（通常为1，其他情况比较复杂，难以计算）

• 如果高阶差分的概率比其在随机置换下的概率大，即可用它将该分组密码与随机置换区分开来

不可能差分攻击

• 差分密码分析的一个特例
• 攻击原理：基于一个不可能差分
  • 不可能差分：概率为 0 的差分
  • 一个不可能差分通常是利用 miss-in-the-middle 方法构建
    • 连接两个概率 1 的短差分：一个为加密方向，另一个为解密方向，两者在连接处的差分不相等
  • 对于随机置换，不可能差分的期望概率为 $2^{-n}$，其中 $n$ 是分组大小
  • 因此，对于一个猜测的密钥，如果存在一个满足上述要求的明密文对，那么猜测该密钥一定不正确
    • 只要明密文对数量差分，那么通过排除所有错误密钥便可以找到正确的密钥

飞去来器攻击

• 差分攻击的一个扩展，工作与适应性选择明密文攻击场景

• 使用两个较短的、概率较大的差分，而不像差分分析使用一个小概率的较长差分

• 基于一个飞去来区分器

放大飞去来器攻击

• 飞去来器攻击的一个变形，简化了攻击场景
• 基于一个放大飞去来区分器

矩形攻击

• 放大飞去来器攻击的改进方法

• 基于一矩形攻击器

不可能飞去来器攻击

• 飞去来器攻击的一个扩展
• 基于一个不可能飞去来区分器

线性分析

• 工作于已知明文/密文工作场景

• 基本思想：利用明文的某特定线性函数和密文的某特定线性函数之间的相关性

  • 最常用的线性函数是计算输入/输出与某具体二进制向量的点乘
  • 用于输入的线性函数称为输入掩码
  • 用于输出的线性函数称为输出掩码
  • 输入与特定二进制向量的点乘结果称为输入校验
  • 输出与特定二进制向量的点乘结果称为输出校验

• 攻击原理：基于有个线性近似

  • 一个线性近似是两个线性函数的组合
  • 线性近似表 LAT、差分分布表 BDT

零线性分析

• 工作于选择明文/密文场景
• 基于一个零相关线性近似
  • 零相关近似是相关性为 0 的线性近似

差分-线性攻击

• 差分攻击和线性攻击的结合体

• 工作于选择明文/密文场景

• 基于一个差分-线性区分器

积分攻击

• 使用一个不同于差分分析或线性分析的方法

  • 有时等价于高阶差分分析

• 一般工作于选择明/密文攻击场景

• 正方形攻击和饱和攻击的归纳版本

• 基于一个积分区分器

正方形攻击

• 基于正方形区分器
  • 基本输入单位：某一字节数值变化（取所有可能的值），其它字节固定为常量的输入集合
  • 考虑：输入某个字节的和为 0 或其他已知的常数
  • 概率一般为 1（也有小于 1 的情况）
  • 对于随机置换，一个字节下的期望概率为 $2^{-8}$

饱和攻击

• 应用于 Feistel 结构

• 是正方形攻击的特例

• 基于饱和区分器

滑动攻击

（基本）滑动攻击

• 工作于已知或选择明/密文攻击场景

• 针对具有特定架构和特定轮密钥的分组密码，即轮密钥相同且轮密钥满足一定关系

• 通常于密码算法的轮数无关

• 打破通过增加加密算法的轮数，弱加密算法可以变强的常规认知

• 攻击原理：基于一个滑动属性

  • 基本输入：一组满足 $x_1=\bar{x_0}$ 的输入 $(x_0,\bar{x_0})$
  • 考虑：$x_t=\bar{x_{t-1}}$
  • 概率为 1
  • 对于随机置换，期望概率为 $2^{-n}$，其中 $n$ 是分组大小

• 主要应用结果

  • DES 的变形

  • Blowfish 的变形

    ※：主要是攻击者认为的变形，概率为 1 的滑动攻击没有攻击任何现有的分组密码

    ※：分组密码设计中加入了轮常数来防止滑动攻击

互补滑动攻击

• 滑动攻击的变形
• 工作于已知或选择明/密文攻击场景
• 对具有特定结构和特定轮密钥的 Feistel 密码有效，具体是
  • 轮函数相同
  • 奇数轮使用相同的轮密钥
  • 偶数轮使用相同的轮密钥
• 基于一个互补滑动属性

扭曲滑动攻击

• 滑动攻击的变形

• 工作于已知或选择明/密文攻击场景

• 对具有特定结构和特定轮密钥的 Feistel 密码有效，具体是

  • 轮函数相同
  • 奇数轮使用相同的轮密钥
  • 偶数轮使用相同的轮密钥

• 基于一个扭曲滑动属性

反射攻击

• 工作于选择明/密文攻击场景

• 非一般的分析方法，对特定结构的分组密码有效，具体是：一边操作是另一边操作的逆，且中间存在部分固定点

  • 固定点：再某一函数下，相等的输入和输出

• 攻击原理：基于一个反射属性

  • 基本输入：一个输入/明文（可能在中间部位产生固定点）
  • 考虑：输出（密文）的等于输入（明文）
  • 概率：依赖于中间部分的固定点数目

中间相遇攻击

原始的中间相遇攻击

• 一个半高级的密码分析方法
• 工作于已知明文攻击场景
• 非一般的分析方法，对有简单密钥生成的分组密码有效，具体是：密码算法的前部分仅包含用户密钥的一部分，后部分仅包含用户密钥的剩余部分
• 后来改进为在选择明文攻击场景中可攻击具有复杂密钥生成的分组密码，此时是一般性分析

已知明文下的攻击

选择明文下的攻击

反射中间相遇攻击

• 反射攻击和中间相遇攻击的一个结合
• 工作与已知明文攻击场景
• 非一般的分析方法，对具有反射属性且密钥生成相对简单的分组密码有效

高阶中间相遇攻击

• 中间相遇攻击的一个扩展

• 工作于选择明文攻击场景

• 有时是一般性的分析方法，有时不是一般性的分析方法，取决于使用的属性

• 攻击原理

  • 在构建一个基本的关注中间值时，通过利用多个输入/明文，消除一个或多个与密钥相关的中间未知参数/部件

    ※：2 个明文的情况不新颖，之前常使用：将中间相遇攻击与一个常规差分属性结合——异或两个中间值以减少一些秘密参数

• 构造方法：将中间相遇攻击与积分分析结合

  • 积分中间相遇攻击

相关密钥分析

• 利用密钥生成的弱点，对分组密码攻击
• 利用在不同但相关的两个或多个密钥下生成的明-密文对
• 攻击目标：在相关密钥场景下，把密码算法与随机置换区分出来，或恢复一个或多个其中的密钥
• 没有具体攻击原理，只要发现的密钥生成的弱点能够将分组密码和随机置换区分开，或恢复出密钥
  • 通常基于结合密钥生成算法的弱点与已有的分组密码分析方法
  • 最常用的相关密钥分析方法
    • 相关密钥差分攻击
    • 相关密钥飞去来器攻击
    • 相关密钥矩形攻击
  • 一个抗单密钥分析的分组密码可能无法抵抗相关密钥下的密码攻击

弱密钥攻击

• 是一些密钥，在其下分组密码更容易受到攻击

• 弱密钥仅是整个密钥空间的一部分

• 一类弱密钥通常在一个特定密码分析方法下找到，如之前的任一方法

• 会弱化密码算法的安全性，尤其是当弱密钥所占的比例占整个密钥空间非常大时

• 通常攻击只能用于弱密钥情形下，但有时多个弱密钥的集合可以覆盖整个密钥空间，进而攻击可扩展至整个密钥空间

• 没有具体的攻击原理

已知密钥攻击

• 假设攻击者知道密钥算法中使用的密钥

• 攻击目标：将密码算法与随即置换区分开，而不是恢复密钥

• 不是一个针对分组密码的分析方法

  • 该攻击不用于破译分组密码算法，而是用于攻击当分组密码被用作哈希函数时

• 没有具体的攻击原理

  • 探索任何可能的区分器，将密钥下的分组密码与随机置换区分开来
  • 通常基于一个已知的密码分析方法

选择密钥攻击

• 假设密码算法中的密钥可以由攻击者选择
• 攻击目标：将密码算法与随机置换区分开，而不是恢复密钥
• 取决于选择密钥后的具体情况，有时可以转化为弱密钥的情况，有时不是一个针对分组密码的分析方法。一般地，该攻击不用于破译分组密码算法，而是用于攻击当分组密码被用作哈希函数时
• 没有具体的攻击原理

分组密码的操作模式

定义

• 分组密码的操作模式：一种能够使分组密码加密任意长度的消息/明文的算法
• 几乎所有早期的操作模式只提供机密性，一些后来的操作模式还可以提供认证性/完整性
• 按功能分，有两种
  • 加密操作模式：仅提供机密性
  • 认证加密操作模式：同时提供机密性和认证性/完整性

要求

• 一个加密操作模式通常应该提供
  • 数据机密性（这意味密钥是不可恢复的）
• 一个认证加密操作模式通常应该提供
  • 数据机密性
  • 数据认证性（这意味着认证标签是不可伪造的）
  • 关联数据的完整性
  • 一次性常数的完整性

加密操作模式

• 通常一个加密操作模式包含以下两个子算法
  • 加密
    • 输入：明文、密钥
      • 一些模式还包括：公用的初始向量、一次性常数
    • 输出：密文
  • 解密
    • 输入：密文和密钥
    • 输出：明文

针对加密操作模式的攻击

• 主要有两类
  • 密钥恢复攻击
  • 明文恢复攻击

电子密码本 ECB

• 最简单的加密模式——消息分块，每一块分别加密
• 优点：加解密可以并行进行
• 缺点：消息必须填充为密码块大小的倍数
• 安全性：存在安全缺点
  • 相同的明文块被加密为相同密文块
  • 对明文的主动攻击是可能的，消息块可被替换、重排等

分组密码链接 CBC

• 加密前：明文块与前一个密文块异或；第一个明文块与一个初始向量异或
• 优点
  • 解密可以并行进行
  • 用错误 IV 解密只影响第一个明文块，后续明文块可正确解密
  • 对密文 1 比特的更改会导致对应明文块完全损坏，并在下一个明文块中反转对应的比特，但其余的块保持不变
• 缺点
  • 加密不可并行进行
  • 消息必须填充为密码块大小的倍数
  • 明文或 IV 中 1 比特变化将影响后续所有密文块
• 安全性：没有公开的安全缺点

传播密码分组链接/明文密码分组链接 PCBC

• 优点：当解密和加密时，密文中的小变化会无限传播
• 缺点
  • 消息必须填充为密码块大小的倍数
  • 加密和解密是顺序进行的
• 安全性：交换两个相邻的密文块不会影响后续块的解密

密码反馈 CFB

• 与 CBC 近似的加密操作模式。把分组密码变成自同步流密码的操作模式

• 优点

  • 加解密模式中都只用了分组密码加密算法（因此无需分组密码解密算法），减少实现的空间
  • 消息无需填充为密码块大小的倍数
  • 解密可以并行进行
  • 解密期间允许随机访问属性

• 缺点

  • 加密按顺序进行，不可并行进行

• 安全性：没有公开的安全缺点

输出反馈 OFB

• 一个把分组密码变成同步流密码的加密模式
• 优点
  • 加解密中都只使用了分组密码加密算法
  • 消息无需填充为密码块大小的倍数
  • 分组密码操作模式可以提前执行，允许在获取明密文的同时并行执行最后一步
• 缺点
  • 加解密顺序执行，不可并行
• 安全性：不支持截断反馈——只有在全反馈时，才能获得一个接近可得最大值的平均周期长度

计数器模式 CTF

• 一个把分组密码变成同步流密码的加密模式

• 优点

  • 加解密模式中都只使用了分组密码加密算法
  • 消息无需填充为密码块大小的倍数
  • 加解密可并行进行。因此这种模式非常适合在多处理器机器上运行
  • 解密期间允许随机访问属性

• 缺点：加密计数器的连续值，可以说任何长时间都不会产生重复序列的函数，如最简单最普通的加 1 计数器

• 安全性：没有公开的安全缺点

认证加密操作模式

认证加密模式

• 通常一个认证加密操作模式包含如下两个子算法
  • 加密和标签生成
    • 输入：明文、密钥和可选的关联数据（如数据头）
    • 输出：密文和认证标签
  • 解密和标签认证
    • 输入：密文、密钥、认证标签和可选的认证数据
    • 输出：如果计算的认证标签和接收的认证标签一致，则输出明文；否则，输出错误

针对认证加密模式的攻击

• 主要有三种
  • 密钥恢复攻击
  • 明文恢复攻击
  • 伪造攻击：主要包含两个子类别
    • 存在性伪造攻击：给定一个或多个明文-密文-标签，找到一个之前没出现的
    • 选择/全局性伪造攻击：给定一个或多个明文-密文-标签，找到任何一个之前没出现的

OCB

• 优点

  • 加解密可并行进行
  • 可将任意长度的比特串加密成最小长度的密文
  • 与不具备认证能力的经典操作模式相比，性能额外开销很小
  • 不需要初始向量

• 缺点：无明显缺点

• 安全：有一个基于生日悖论的琐碎攻击，其限制了单密钥下可以安全处理的数据量，但不违反安全性证明

EAX

• 优点
  • 加解密在一定程度上可并行进行
  • 在线——它接受任意长度的输入，并在接收明文块时输出密文块
  • 消息加解密只使用分组密码加密算法
• 缺点：无明显缺点

GCM

• 应用广泛
  • IEEE 各种安全标准
  • ANSI 光纤通道安全协议
  • SSH TLS

COPA

• 处理关联数据
• 优点
  • 加解密在一定程度上可以并行
  • 在线——它接受任意长度的输入，并在接受到一明文块时可以输出相应密文块，不必等到要收完所有的明文块才能开始加密
• 缺点
  • 需要加密算法和解密算法的实现
  • 效率不是很高，比率为 2，即每个消息块加密/解密需要 2 次分组密码加解密操作
• 安全性：存在违背安全证明的有效攻击

OTR

• 消息加密和标签生成
• 优点
  • 加解密可以在两个块分区下并行进行
  • 在线
  • 每个消息块加密/解密只需要 1 次分组密码加解密操作
  • 消息加解密只使用分组密码的加密算法
• 缺点：无明显缺点
• 安全性：存在违背安全证明的有效攻击

序列密码简介

序列密码的基本概念

• 序列密码/流密码
  • 提供数据机密性
• 一次一密
• 优点：执行速度快、硬件复杂度低
• 缺点：安全缺点通常致命
• 设计方法
  • 基于线性反馈移位寄存器：通常比特级
  • 基于非线性状态更新器：通常字节级
  • 基于分组密码的流密码：某些操作模式

序列密码的分类

同步序列密码

• 密钥序列独立于消息序列

• 使用相同密钥流情况下的插入攻击

• 优点

  • 没有差错传播
  • 可以防止明文中的插入和删除

• 缺点

  • 需要发方和收方精确同步

自同步/非同步序列密码

• 密钥流是密钥及固定大小的以往的密文/明文位的函数

• 优点：自动同步

• 缺点：错误传播

密钥流生成器的结构

• 序列密码关键点

  • 密钥流生成器的随机性和不可预测性

  • 管理密钥

序列的随机性

• r-游程
• 自相关函数
• Golomb 随机性公设
  • 满足公设的的序列称为伪随机序列

线性移位寄存器结构与设计

• 移位寄存器与移位寄存器序列

• n 阶反馈移位寄存器

  • 级数
  • 状态
  • 反馈函数
  • 初始状态

• m 序列：周期为 $2^n-1$ 的 LFSR 序列

典型序列密码

A5

• 仍用于 GSM，但是已相当不安全
• 算法结构
  • 同步流密码
    • 3 个LFSR 在主要函数下以停止前进的方式相互计时

RC4

• 慎用
• 算法结构
  • 同步流密码
    • 基于非线性更新函数的查找表

SNOW

• 1.0 被攻破，故提出 2.0 和 3G
• 算法结构
  • 同步流密码
    • 基于 16 个 32 比特的 LFSR

ZUC

• 算法结构
  • 同步流密码
    • 1 个基于 16 个 31 比特的 LFSR，1 个比特重排 BR 和 1 个非线性函数 F
    • GF 域乘法：可用一个旋转操作实现

PKZIP

• 广泛用于文档压缩程序，算法简单，但是不安全

WAKE

• 一种字节自动密钥加密算法，工作在 CFB 模式下
• 速度快
• 对于某些选择明文和选择密文攻击来说不安全

SEAL

• 适于软件实现，特别适于 32 比特处理器

• 基于伪随机函数的原理进行设计，根据 160 比特的密钥 $K$ 和 32 比特 $n$，计算一个长的随机字串 $K(n)$

• 优点

  • 可以轻易访问密钥序列中的任何位置
  • 简化了标准序列密码中的同步问题

• 算法思想

  • 使用一个大的、秘密的、密钥派生的 S 盒
  • 必须将密钥预处理到内部表中，否则无法使用
  • 根据轮数改变轮密钥，根据迭代次数改变迭代函数

• 算法分析

  • 速度快
  • 没有明显缺陷

序列密码分析攻击方法

时间-存储折中攻击

Hellman 表密码分析方法

• 均匀选择 $m$ 个起始点，将 $m$ 对 $(SP_i,EP_i)$ 存储到按终点排序的表中（删除中间值），即为 Hellman 表
• 复杂度
  • 存储复杂度：$m$ 个单元
  • 时间复杂度：$m*t$ 次 $f$ 的计算
    • $f$ 是随机函数，给定 $y=f(x)$，求解 $x$
  • 攻击复杂度
    • 成功率：取决于表的覆盖率

彩虹表密码分析方法

• 动机：在 Hellman 表中，若两相同数值来自不同列，会出现部分相同的链，在实际中很难检测，降低了覆盖率

• 主要区别：

猜测决定攻击

分治攻击

相关攻击

代数攻击

立方攻击