クリズのBlog

Appearance

差分分析 ​

第一部分：背景与基本概念 ​

  1. 攻击模型：

    • 选择明文攻击 (Chosen Plaintext Attack, CPA)：攻击者可以自由选择任意明文 P 并获得其对应的密文 C。
    • 目标：恢复加密所用的密钥 k。

  2. 核心思想：

    • 分析输入差分 (Input Difference) 如何影响输出差分 (Output Difference)。
    • 如果一个密码算法不是完美的随机置换，那么某些特定的输入差分会导致某些输出差分以高于随机概率出现。
    • 利用这种统计上的非随机性来推断密钥信息。

  3. 关键定义：

    • 差分 (Difference)：通常使用异或 (XOR, ⊕) 来定义差分。
      • 明文差分：ΔP = P ⊕ P'
      • 密文差分：ΔC = C ⊕ C'
    • 差分特征 (Differential Characteristic)：描述差分在密码各轮之间传播的路径及其概率。
    • 安全 PRP (伪随机置换) 的理想特性：对于任何固定的输入差分 ΔP，所有可能的输出差分 ΔC 出现的概率都应该是均匀的，即 Pr[ΔC] ≈ 2⁻ⁿ（n 是块大小）。

第二部分：差分分析如何工作 ​

  1. 基本流程：

    1. 选择差分对：固定一个输入差分 ΔP。
    2. 收集数据：随机选择大量明文 Pᵢ，计算 Pᵢ' = Pᵢ ⊕ ΔP，并获取它们的密文 Cᵢ 和 Cᵢ'。
    3. 计算输出差分：对每一对 (Pᵢ, Pᵢ')，计算 ΔCᵢ = Cᵢ ⊕ Cᵢ'。
    4. 统计分析：如果 ΔCᵢ 的分布显著偏离均匀分布（即某些 ΔC 出现频率异常高），则表明该密码存在可利用的差分特征。

  2. 从区分器到密钥恢复：

    • 上述过程首先构建了一个区分器 (Distinguisher)，可以将目标密码与随机置换区分开。
    • 要恢复密钥，需要将攻击聚焦在最后一轮。
    • 核心技巧：猜测最后一轮的子密钥 K_r，用它来“解密”密文 C 和 C'，得到倒数第二轮的输出 X 和 X'。然后检查 X ⊕ X' 是否符合预期的差分特征。如果猜测正确，统计偏差会显现；如果错误，则结果看起来是随机的。

第三部分：组件分析 - S盒的差分性质 ​

  1. S盒的作用：

    • S盒（替换盒）是分组密码中提供非线性混淆的核心组件。
    • 差分分析主要针对的就是S盒的行为。

  2. 差分分布表 (Difference Distribution Table, DDT)：

    • 定义：一个二维表格，行代表输入差分 Δin，列代表输出差分 Δout。
    • 表项 DDT[Δin][Δout]：表示满足 S(x) ⊕ S(x ⊕ Δin) = Δout 的输入 x 的数量。
    • 概率计算：对于给定的 Δin，产生 Δout 的概率为 Pr = DDT[Δin][Δout] / 2ᵐ（m 是S盒输入比特数）。

  3. 分析示例：

    • 假设一个4-bit S盒，输入差分 Δin = 8 (二进制 1000)。
    • 通过查询DDT或手动计算，发现输出差分 Δout 可能为 {d, e, b, 6, 7, f}，且各自的出现频率不同（例如，d 出现4次，e 出现2次等）。
    • 关键点：如果 Δin = 8 时，Δout = d 的概率是 4/16 = 1/4，这远高于随机概率 1/16。这是一个强差分特征。

  4. 利用S盒差分进行密钥恢复：

    • 场景：假设密码只有一轮，形式为 C = S(P ⊕ k₀) ⊕ k₁。
    • 已知：(P, P', C, C')，其中 P' = P ⊕ ΔP。
    • 未知：密钥 k = k₁ || k₀。
    • 步骤：
      1. 计算 ΔC = C ⊕ C'。
      2. 根据 ΔP 和 ΔC，从DDT中找出所有可能的中间状态 U（即 P ⊕ k₀ 的值）。
      3. 对于每个候选 U，可以计算出 k₀ = U ⊕ P 和 k₁ = S(U) ⊕ C。
      4. 这样就得到了一组候选密钥。使用另一对明密文对即可验证出正确的密钥。

第四部分：多轮差分特征与概率 ​

  1. 特征构建：

    • 一个r轮的差分特征由一系列连续的输入/输出差分组成：(ΔP → Δ₁ → Δ₂ → ... → ΔC)。
    • 其中 Δᵢ 是第i轮的输出差分（也是第i+1轮的输入差分）。

  2. 特征概率：

    • 如果各轮的S盒是独立的，那么整个r轮特征的概率 p 是各轮转移概率的乘积。 p = p₁ * p₂ * ... * pᵣ
    • 活跃S盒 (Active S-box)：在一个差分特征中，输入差分不为零的S盒。只有活跃S盒对特征概率有贡献（非活跃S盒的转移概率为1）。
    • 设计准则：为了抵抗差分分析，密码设计应确保任何r轮差分特征都必须激活足够多的S盒，使得 p 极小（接近 2⁻ⁿ）。

  3. 数据复杂度：

    • 为了观察到一个概率为 p 的差分特征，大约需要 1/p 对明文。

第五部分：历史与实例 ​

  1. 历史：

    • 1970s：NSA和IBM内部已知晓此方法，但保密。
    • 1990：Eli Biham 和 Adi Shamir 独立重新发现并公开发表，引起密码学界轰动。

  2. 对DES的影响：

    • DES的设计者（IBM/NSA）早已知道差分分析，并在设计时（如S盒的选择）特意使其能够抵抗这种攻击。
    • 对完整DES的差分攻击需要约 2⁴⁷ 个选择明文，这在当时是不可行的，证明了DES设计的前瞻性。

  3. 对AES的影响：

    • AES (Rijndael) 在设计时就将抵抗差分分析（和线性分析）作为核心目标。
    • 其使用的宽轨迹策略 (Wide Trail Strategy) 保证了极低的差分特征概率，使其对差分分析具有极强的抵抗力。

📝 练习题与答案 ​

题目 1：基本概念 ​

解释为什么差分分析是一种选择明文攻击？为什么在不知道密钥的情况下，攻击者仍然可以计算明文差分 ΔP 和密文差分 ΔC？

答案:

  • 为什么是CPA：因为差分分析的有效性依赖于攻击者能够控制输入差分 ΔP。为了做到这一点，攻击者必须能够选择一对明文 P 和 P'，使得它们的差分 P ⊕ P' 等于他想要研究的特定值 ΔP。这种能力正是选择明文攻击模型的定义。
  • 如何计算差分：
    • 明文差分 ΔP：由于 P 和 P' 都是由攻击者自己选择的，所以他完全知道这两个值，因此可以直接计算 ΔP = P ⊕ P'。
    • 密文差分 ΔC：攻击者将 P 和 P' 提交给加密预言机（或实际系统），并分别获得密文 C 和 C'。虽然他不知道密钥，但他拥有 C 和 C'，因此也可以直接计算 ΔC = C ⊕ C'。
    • 关键点：差分分析巧妙地避开了直接处理密钥，而是专注于已知量（P, P', C, C'）之间的关系。

题目 2：S盒分析 ​

考虑一个简化的4-bit S盒，其映射如下：

x (输入)0123456789ABCDEF
S[x] (输出)E4D12FB83A6C5907

(a) 计算当输入差分 Δin = 8 (十六进制) 时，所有可能的输出差分 Δout 及其出现次数。 (b) 假设我们观察到一对 (P, P') 满足 P ⊕ P' = 8，且它们的输出满足 C ⊕ C' = D。请问有多少个可能的 U = P ⊕ k₀ 值？并列出它们。

答案: (a) 计算DDT条目 Δin=8: 我们需要遍历所有 x 从 0 到 F，计算 x' = x ⊕ 8，然后计算 S[x] ⊕ S[x']。

  • x=0: x'=8, S[0]=E, S[8]=3, E⊕3=D
  • x=1: x'=9, S[1]=4, S[9]=A, 4⊕A=E
  • x=2: x'=A, S[2]=D, S[A]=6, D⊕6=B
  • x=3: x'=B, S[3]=1, S[B]=C, 1⊕C=D
  • x=4: x'=C, S[4]=2, S[C]=5, 2⊕5=7
  • x=5: x'=D, S[5]=F, S[D]=9, F⊕9=6
  • x=6: x'=E, S[6]=B, S[E]=0, B⊕0=B
  • x=7: x'=F, S[7]=8, S[F]=7, 8⊕7=F
  • x=8: x'=0, S[8]=3, S[0]=E, 3⊕E=D (与x=0相同)
  • x=9: x'=1, S[9]=A, S[1]=4, A⊕4=E (与x=1相同)
  • ... (其余为重复)

统计 Δout:

  • D: 出现于 x=0, 3, 8, B → 4次
  • E: 出现于 x=1, 9 → 2次
  • B: 出现于 x=2, 6 → 2次
  • 7: 出现于 x=4, C → 2次
  • 6: 出现于 x=5, D → 2次
  • F: 出现于 x=7, F → 2次

(b) 找出 U: U 就是上面计算中使得 S[U] ⊕ S[U⊕8] = D 的 x 值。 从 (a) 中可知，这些 x (即 U) 是: 0, 3, 8, B (十六进制)。

题目 3：多轮特征与概率 ​

假设一个SPN结构的密码，其S盒的DDT显示，输入差分 α 产生输出差分 β 的概率为 1/4。该密码的扩散层（如P置换或MDS矩阵）保证了如果某一轮有1个活跃S盒，下一轮至少会有2个活跃S盒。

(a) 请构造一个2轮的差分特征，并计算其概率。 (b) 如果攻击者想利用这个2轮特征来攻击一个4轮密码，他需要多少对选择明文才能期望看到一次该特征的发生？

答案: (a) 构造2轮特征: 我们可以构造如下特征：

  • 轮1: 输入差分导致 1个 S盒的输入差分为 α，其他S盒输入差分为0。
    • 该活跃S盒以概率 1/4 产生输出差分 β。
    • 轮1输出差分：1个位置为 β，其余为0。
  • 扩散层: 将轮1的输出差分（1个 β）扩散，使得轮2的输入差分在 2个 S盒上非零。
  • 轮2: 假设这2个非零输入差分恰好都能以概率 1/4 产生某个特定的输出差分（为了简化，我们假设这是可能的，或者我们只关心其中一个S盒的输出）。
    • 为保守估计，我们只追踪一个S盒。因此，轮2的转移概率也为 1/4。

特征概率: p = (1/4) * (1/4) = 1/16.

(b) 数据复杂度:

  • 特征概率 p = 1/16。
  • 期望看到一次该特征所需的数据对数约为 1/p = 16 对。
  • 注意：在实际的4轮攻击中，攻击者会利用这个2轮特征覆盖中间两轮，然后通过猜测第一轮和最后一轮的子密钥来连接明文和密文差分。但问题只问特征本身的发生，所以答案是 16对。

CopyRight@ 2025 Klizz