差分分析学习（一）

Published: at 12:30 PM

本文是对 The Block Cipher Companion 的读书笔记，分为三篇文章简述差分分析的基本思想.

引入

我们熟悉的异或加密可以写成

c=m⊕kc = m\oplus k

香农证明了如果随机选择的 k 只使用过 1 次（即一次性密码本，OTP），异或加密是无条件安全的.而如果 k 被使用了 2 次，攻击者可以根据两个密文来计算两个消息的异或：

c0⊕c1=(m0⊕k)⊕(m1⊕k)=m0⊕m1c_0\oplus c_1 =(m_0\oplus k)\oplus (m_1\oplus k)= m_0\oplus m_1

在消息中包含冗余的情况下，攻击者可以从中推断出明文的信息.

从这个例子中我们可以学到：相比于只考虑 1 对明文-密文，考虑 多对 明文-密文之间的关系可能会让攻击者获得更多的信息.

CipherOne

c=S[m⊕k0]⊕k1c = S [m \oplus k_0] \oplus k_1

其中 S 盒为

xx0\texttt{0}1\texttt{1}2\texttt{2}3\texttt{3}4\texttt{4}5\texttt{5}6\texttt{6}7\texttt{7}
S[x]S[x]6\texttt{6}4\texttt{4}c\texttt{c}5\texttt{5}0\texttt{0}7\texttt{7}2\texttt{2}e\texttt{e}
xx8\texttt{8}9\texttt{9}a\texttt{a}b\texttt{b}c\texttt{c}d\texttt{d}e\texttt{e}f\texttt{f}
S[x]S[x]1\texttt{1}f\texttt{f}3\texttt{3}d\texttt{d}8\texttt{8}a\texttt{a}9\texttt{9}b\texttt{b}

假设攻击者知道两个明文-密文对 (m0,c0),(m1,c1)(m_0,c_0),(m_1,c_1). 将加密过程逐步展开如下

CipherOne (m0,k0∥k1)(m_0, k_0 \parallel k_1)CipherOne (m1,k0∥k1)(m_1, k_0 \parallel k_1)
u0=m0⊕k0u_0 = m_0 \oplus k_0u1=m1⊕k0u_1 = m_1 \oplus k_0
v0=S[u0]v_0 = S[u_0]v1=S[u1]v_1 = S[u_1]
c0=v0⊕k1c_0 = v_0 \oplus k_1c1=v1⊕k1c_1 = v_1 \oplus k_1

由于 k0k_0 是保密的，攻击者无法获取 u0,u1u_0,u_1 的值. 然而，当我们引入 差分 的概念时，攻击者实际上是知道它们的差分的：

u0⊕u1=(m0⊕k0)⊕(m1⊕k0)=m0⊕m1u_0\oplus u_1 =(m_0\oplus k_0)\oplus (m_1\oplus k_0)= m_0\oplus m_1

对于正确的 k1k_1，有 u0⊕u1=S−1[v0]⊕S−1[v1]u_0\oplus u_1=S^{-1}[v_0]\oplus S^{-1}[v_1]，攻击者可以简单地尝试所有可能的 k1k_1 值 tt，一旦获得期望的 S−1[v0]⊕S−1[v1]S^{-1}[v_0]\oplus S^{-1}[v_1] （也就是等于已知值 u0⊕u1u_0\oplus u_1），那么 tt 就是一个可能的密钥！接下来可以重复这样的攻击，直到候选的密钥唯一.

从对 CipherOne 的攻击中我们可以学到：

  1. 尽管我们可能不知道加密过程中内部变量的值，但我们能 描述这些变量的差分！
  2. 我们能够 猜测部分密钥的值，并 测试某些差分条件是否成立 来恢复密钥信息！

关于第一点，在 CipherOne 中，我们可以 确定地 描述内部变量之间的差分，但在更复杂的密码中，这种描述可能是 不确定的. 接下来请看 CipherTwo.

CipherTwo

c=S[S[m⊕k0]⊕k1]⊕k2c = S [S[m \oplus k_0] \oplus k_1]\oplus k_2

假设攻击者知道两个明文-密文对 (m0,c0),(m1,c1)(m_0,c_0),(m_1,c_1). 将加密过程分步写为

CipherOne (m0,k0∥k1∥k2)(m_0, k_0 \parallel k_1 \parallel k_2)CipherOne (m1,k0∥k1∥k2)(m_1, k_0 \parallel k_1 \parallel k_2)
u0=m0⊕k0u_0 = m_0 \oplus k_0u1=m1⊕k0u_1 = m_1 \oplus k_0
v0=S[u0]v_0 = S[u_0]v1=S[u1]v_1 = S[u_1]
w0=v0⊕k1w_0 = v_0 \oplus k_1w1=v1⊕k1w_1 = v_1 \oplus k_1
x0=S[w0]x_0=S[w_0]x1=S[w1]x_1=S[w_1]
c0=x0⊕k2c_0=x_0\oplus k_2c1=x1⊕k2c_1=x_1\oplus k_2

按照 CipherOne 的方法从下往上分析，通过猜测 k2k_2 的值来计算 x0,x1x_0,x_1，进而得到 w0,w1w_0,w_1. 这时遇到了 k1k_1 ，所以没法直接得到 v0,v1v_0,v_1，不过别忘了，计算差分 w0⊕w1w_0\oplus w_1 让我们能够得到 v0⊕v1v_0\oplus v_1.

从上往下分析，我们知道 m0⊕m1m_0\oplus m_1，也就是知道 u0⊕u1u_0\oplus u_1.

这时候我们会发现，v0⊕v1v_0\oplus v_1 和 u0⊕u1u_0\oplus u_1 之间隔了一个 S 盒，而 S 盒是 非线性的，这阻断了我们对 k2k_2 猜测的验证.

理解 S 盒的行为

v0⊕v1v_0\oplus v_1 和 u0⊕u1u_0\oplus u_1 之间隔了一个 S 盒，这个 S 盒究竟做了什么？

先讨论一个特殊情况：对于 S 盒的两个输入，ii 和 jj ，其中 j=i⊕fj=i\oplus \texttt{f}. 对于 ii 的所有值，我们计算如下：

ijS [i]S [j]S [i] ^ S [j]
0\texttt{0}f\texttt{f}6\texttt{6}b\texttt{b}d\texttt{d}
1\texttt{1}e\texttt{e}4\texttt{4}9\texttt{9}d\texttt{d}
2\texttt{2}d\texttt{d}c\texttt{c}a\texttt{a}6\texttt{6}
3\texttt{3}c\texttt{c}5\texttt{5}8\texttt{8}d\texttt{d}
4\texttt{4}b\texttt{b}0\texttt{0}d\texttt{d}d\texttt{d}
5\texttt{5}a\texttt{a}7\texttt{7}3\texttt{3}4\texttt{4}
6\texttt{6}9\texttt{9}2\texttt{2}f\texttt{f}d\texttt{d}
7\texttt{7}8\texttt{8}e\texttt{e}1\texttt{1}f\texttt{f}
8\texttt{8}7\texttt{7}1\texttt{1}e\texttt{e}f\texttt{f}
9\texttt{9}6\texttt{6}f\texttt{f}2\texttt{2}d\texttt{d}
a\texttt{a}5\texttt{5}3\texttt{3}7\texttt{7}4\texttt{4}
b\texttt{b}4\texttt{4}d\texttt{d}0\texttt{0}d\texttt{d}
c\texttt{c}3\texttt{3}8\texttt{8}5\texttt{5}d\texttt{d}
d\texttt{d}2\texttt{2}a\texttt{a}c\texttt{c}6\texttt{6}
e\texttt{e}1\texttt{1}9\texttt{9}4\texttt{4}d\texttt{d}
f\texttt{f}0\texttt{0}b\texttt{b}6\texttt{6}d\texttt{d}

很容易注意到 S[i] ^ S[j] 这一列并不均匀，d 在 16 次中出现了 10 次. 前面提到，我们对 k2k_2 的猜测被阻断了. 如果我们能够指定消息去进行加密，而不是只是简单地截取明文-密文对（也就是能够进行 选择密文攻击），我们就能够利用这种不均匀的概率分布：

随机选择 m1m_1，令 m1=m0⊕fm_1=m_0\oplus \texttt{f}，我们能够知道 u0⊕u1=m0⊕m1=fu_0\oplus u_1=m_0\oplus m_1=\texttt{f}. 当然，我们无法直接确切地知道 u0,u1u_0,u_1 具体的取值，不过根据上面的表，我们能够确定： S[u0]⊕S[u1]=dS[u_0]\oplus S[u_1]=\texttt{d} 成立的概率为 1016\frac{10}{16}.

这就为验证 k2k_2 的正确性提供了依据：我们可以假设，如果 k2k_2 的猜测是错的，那么 v0⊕v1v_0\oplus v_1 应该「看上去很随机」. 实际上我们可以这样做：维护一组初始化为 0 的计数器（对应 k2k_2 的每一种取值），对于一个给定的明文-密文对，遍历所有可能的 k2k_2 值，如果 v0⊕v1=dv_0\oplus v_1=\texttt{d}，那么将对应计数器的值 +1. 注意正确的 k2k_2 使得这个关系成立的概率是 1016\frac{10}{16}，而错误的 k2k_2 使得这个关系成立的概率只有 110\frac{1}{10}. 如果我们使用 N 个明文-密文对，正确的 k2k_2 对应的计数器应该明显大于其他计数器.

刚刚我们是在讨论 j=i⊕fj=i\oplus \texttt{f} 的特殊情况，实际上我们可以对所有可能的输入差分进行类似操作，画出一张 差分分布表. 每一行表示一个输入 dind_{in} ，表中每项表示对应的输出 doutd_{out} 出现的频率.

0123456789abcdef
016---------------
1--6----2-2--2-4-
2-66------22-----
3---6-2--2---4-2-
4---2-24--222--2-
5-22-4--42--2----
6--2-4--22-222---
7-----44-2222----
8-----2-24--4-2-2
9-2---222-42----2
a----22---44-22--
b---22-222--4--2-
c-4-2-2--2-----6-
d------22----62-4
e-2-42-----2----6
f----2-2------10-2
Previous Post
差分分析学习（二）
Next Post
GeekGame 2024 - 不经意的逆转