分组密码的差分分析读书报告
近期，学习了差分密码分析和线性密码分析，借此机会整理一下学习心得，方便自己梳理一遍知识，也能发出来和大家一起交流。本篇主要讲差分分析，如果有描述错误或者不准确的地方，欢迎大家在帖子下方回复，谢谢~
1、简介
1990年国际密码年会上，Biham和Shamir首次提出了对DES的差分攻击，从此国际上开启了分组密码分析的热潮[1]。差分分析方法是用于攻击分组密码的，准确地说，它是攻击迭代型分组密码最有效地方式之一，经过这么多年地发展，差分分析已经成为了衡量密码*安全性的重要指标之一，许多密码设计者必须考虑密码算法的抗差分攻击的能力。
2、预备知识
其实差分分析的过程并不算复杂，我们学习起来的难点主要在于高概率差分路径的选择和差分攻击的成功概率以及算法复杂度的估计，为了后面更加方便地讲述差分分析地流程，这里需要先给出差分分析的一些名词。
说到差分这个词，学习数学的同学们都不陌生，但是在密码分析学中，差分不完全等同于数学中的差分（形式上有些不同，本质上还是一回事）。
(定义1)[差分] 对于两个 n n n元比特串 x x x和 x ∗ x^{*} x∗，定义 Δ x = x ⨁ x ∗ \Delta x=x \bigoplus x^{*} Δx=x⨁x∗，称 Δ x \Delta x Δx为 x x x和 x ∗ x^{*} x∗的差分。（有些书直接叫做异或值）
(定义2)[差分对和差分特征] 设有一个迭代分组密码，对 ∀ α , β ∈ { 0 , 1 } n \forall \alpha ,\beta \in \lbrace0,1\rbrace ^{n} ∀α,β∈{0,1}n,考虑某一次迭代，设迭代的输入是两个比特串 x , x ∗ x,x^{*} x,x∗,并且有 α = x ⨁ x ′ \alpha =x \bigoplus x' α=x⨁x′,经过一次迭代加密之后，得到的输出为 y , y ∗ y,y^{*} y,y∗并且有 β = y ⨁ y ′ \beta =y \bigoplus y' β=y⨁y′，就称 ( α , β ) (\alpha,\beta) (α,β)是一个差分对(有时直接称为差分)；相应的，考虑整个密码*的迭代过程，从明文的差分 α \alpha α开始，经过第一轮迭代差分变成 β \beta β，再经过一次迭代变成 γ ⋯ \gamma \cdots γ⋯ 直至迭代结束，得到的一串差分 ( α , β , γ , ⋯ ) (\alpha,\beta,\gamma,\cdots) (α,β,γ,⋯)称为一个差分特征(也称为差分路径)，记作 Ω = ( α , β , γ , ⋯ ) \Omega =(\alpha,\beta,\gamma,\cdots) Ω=(α,β,γ,⋯)，差分特征表征了加密过程中的差分传播特性。
(定义3)[差分概率和差分特征概率] 对于某次迭代，设输入的比特串差分为 α i \alpha_{i} αi时，输出的比特串差分为 α i + 1 \alpha_{i+1} αi+1的概率叫做差分对 ( α i , α i + 1 ) (\alpha_{i},\alpha_{i+1}) (αi,αi+1)的差分概率，记作 D P ( α i → α i + 1 ) DP(\alpha_{i} \rightarrow \alpha_{i+1}) DP(αi→αi+1)；同理，对于整个加密过程，设初始差分为 α 0 \alpha_{0} α0时，第一轮迭代的差分对为 ( α 0 , α 1 ) (\alpha_{0},\alpha_{1}) (α0,α1)，第二轮迭代的差分对为 ( α 1 , α 2 ) (\alpha_{1},\alpha_{2}) (α1,α2),……第 n n n轮差分对为 ( α n − 1 , α n ) (\alpha_{n-1},\alpha_{n}) (αn−1,αn)的概率叫做差分特征 Ω = { α 0 , α 1 , α 2 , ⋯ , α n } \Omega=\lbrace \alpha_{0},\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\rbrace Ω={α0,α1,α2,⋯,αn}的差分特征概率，由于每一轮加密都是互相独立的，所以有 D P ( Ω ) = ∏ i = 0 n − 1 D P ( α i → α i + 1 ) DP(\Omega)=\prod_{i=0}^{n-1}DP(\alpha_{i}\rightarrow\alpha_{i+1}) DP(Ω)=i=0∏n−1DP(αi→αi+1)
(定义4)[正确对和错误对] 给定一个差分路径 Ω = { α 0 , α 1 , α 2 , ⋯ , α n } \Omega=\lbrace \alpha_{0},\alpha_{1},\alpha_{2},\cdots,\alpha_{n}\rbrace Ω={α0,α1,α2,⋯,αn}，对于一个数据对 ( X , X ∗ ) (X,X^{*}) (X,X∗)，它在加密的每一轮中的差分都满足 Ω \Omega Ω，则称该数据对为正确对，反之为错误对。
这也说明了，S盒对应的变换是一个一一映射(正是这一点保证了求S盒逆可以成功)。
3、差分分析的基本原理
与线性逼近攻击(已知明文攻击)不同，差分分析是选择明文攻击。一句话概括，差分攻击的第一步是利用前 n − 1 n-1 n−1轮的差分特征恢复出第 n n n轮密钥的部分或者全部信息。这里先给出一个对于 n n n轮迭代的简单的差分攻击的步骤：
目的：对于 n n n轮迭代的分组密码，差分攻击的目标是尽可能恢复出最后一轮的子密钥( k n k_{n} kn)的尽可能多的信息(也有改进的算法恢复最后好几*密钥)
s t e p 1 step1 step1：针对给定的S盒，找一条 n − 1 n-1 n−1轮的高概率的差分路径 ( α 0 , α 1 , ⋯ , α n − 2 , α n − 1 ) (\alpha_{0},\alpha_{1},\cdots,\alpha_{n-2},\alpha_{n-1}) (α0,α1,⋯,αn−2,αn−1)；
s t e p 2 step2 step2：设 k n k_{n} kn的长度为 l l l比特，那么对每个可能的候选密钥 c k i ck_{i} cki都设置一个计数器，总共有 2 l 2^{l} 2l个计数器，初始化为0；
s t e p 3 step3 step3：随机均匀地选取明文 X X X，并令 X ∗ = X ⨁ α 0 X^{*}=X\bigoplus\alpha_{0} X∗=X⨁α0，这就产生了多条明文数据对，对明文对 ( X , X ∗ ) (X,X^{*}) (X,X∗)进行加密，得到密文对 ( Y , Y ∗ ) (Y,Y^{*}) (Y,Y∗)；
s t e p 4 step4 step4：对密文对进行过滤。具体的，计算每个密文对的差分，对于正确对来说，最后一轮的输入差分应该为 α n − 1 \alpha_{n-1} αn−1，根据S盒的性质就可以推断出最后一轮的输出差分(密文对的差分)的所有可能取值，将那些不可能的出现的差分对应的密文对删除，这个操作就称为过滤；
s t e p 5 step5 step5：对保留下的密文对 ( Y , Y ∗ ) (Y,Y^{*}) (Y,Y∗)，应用第 n n n轮的每个候选子密钥对密文对进行解密，计算解密之后的差分 Δ = S c k i − 1 ( Y ) ⨁ S c k i − 1 ( Y ∗ ) \Delta = S_{ck_{i}}^{-1}(Y) \bigoplus S_{ck_{i}}^{-1}(Y^{*}) Δ=Scki−1(Y)⨁Scki−1(Y∗)，若 Δ = α n − 1 \Delta = \alpha_{n-1} Δ=αn−1，则 c k i ck_{i} cki的计数器加1(看作是给 c k i ck_{i} cki作了一个投票)；
s t e p 6 step6 step6：将 2 l 2^{l} 2l个计数器中计数值明显大于其他计数器的那个候选密钥作为正确密钥。
尽管算法流程看起来并不复杂，但是要真正做出来还有很多细节需要理解。
- 如何找高概率差分路径
寻找高概率差分路径一直是差分分析中的难题，不同的S盒差分分布不一样，找起来的难易程度也不一样。一般来说，首先根据S盒画出差分分布表，从差分分布表可以看出差分转移的概率，前面说到，差分路径的概率等于每一步迭代的差分转移概率的乘积，所以我们在差分分布表中寻找概率最大的差分路径。有结论表明， n n n轮S盒迭代一定存在着差分分布的不均匀性，但是能否有效地找到是一个难题。(这个问题类似于在无向图中寻找最优路径的问题，可以借用图论方法去寻找最优路径)
- 攻击成功概率分析
显然，当正确的密钥得到的票数明显多于错误密钥时，攻击就可以成功。我们定义信噪比( S N \frac{S}{N} NS)为正确密钥得到的票数 ÷ \div ÷平均每个错误密钥的票数，所以若 S N > 1 \frac{S}{N}>1 NS>1，攻击可以成功。为了计算信噪比，先定义几个参数：
- p p p --所有数据对中正确对的比例
- λ \lambda λ --过滤强度，即平均每个数据对经过过滤被保留下来的概率
- γ \gamma γ --每个数据对平均投票数
- κ \kappa κ --子密钥 k r i kr_{i} kri的比特长度
那么假设一开始我们选取了 N N N个明文对，则正确对有 N p Np Np个，通过过滤的数据对有 N λ N\lambda Nλ个。所有正确对一定能够通过过滤，而错误对不一定能够通过过滤，换言之就是过滤操作删除了部分错误对，则通过过滤的错误对有 N λ − N p N\lambda-Np Nλ−Np个。考虑投票过程，正确对会给正确密钥和错误密钥投票，而错误对只会给错误密钥投票，不会给正确密钥投票，所以1个正确对会给正确密钥投1票，给错误密钥投 γ − 1 \gamma -1 γ−1票，1个错误对的 γ \gamma γ票全部投给错误密钥。那么信噪比为
S N = N p N p ( γ − 1 ) + ( N λ − N p ) γ 2 κ − 1 = ( 2 κ − 1 ) p λ γ − p \frac{S}{N}=\frac{Np}{\frac{Np(\gamma - 1)+(N\lambda - Np)\gamma}{2^{\kappa}-1}}=\frac{(2^{\kappa}-1)p}{\lambda \gamma - p} NS=2κ−1Np(γ−1)+(Nλ−Np)γNp=λγ−p(2κ−1)p
由此计算信噪比，当 S / N > 1 S/N>1 S/N>1时，攻击可以成功。
- 要多少条数据对
通过对差分攻击成功的概率分析的公式我们发现，信噪比和数据对 N N N无关，表面上看似无论选取多少数据对都可以。但实际不是这样的：数据对是随机选的，选取的数据对不同，用同一个差分特征进行过滤，通过过滤的数据对数量不同，含有的正确对数量也不同(即 p p p和 λ \lambda λ不同)。一个直观的想法是我们希望过滤后的数据对中正确对占比能够尽量大，换言之就是希望我们找到的高概率差分的差分优势能够最大程度显现出来，最好的办法就是增加数据对个数。当然数据对最多是 2 n − 1 2^{n-1} 2n−1个( n n n是明文比特数)。
- 算法复杂度估计
存储复杂度：由于要对预恢复的密钥进行计数(投票)，所以初始化一个 2 κ 2^{\kappa} 2κ的数组( κ \kappa κ是预恢复的比特长度)，所以存储复杂度为 2 κ 2^{\kappa} 2κ。
时间复杂度：对 N N N个数据对进行加密，初始化计数器( O ( 2 κ ) \mathcal{O}(2^{\kappa}) O(2κ))，对每个候选密钥进行投票( O ( 2 κ λ ) ) \mathcal{O}(2^{\kappa}\lambda)) O(2κλ)))，所以总共为 O ( N + 2 κ + 2 κ λ ) \mathcal{O} (N+2^{\kappa}+2^{\kappa}\lambda) O(N+2κ+2κλ)。
4、总结
总的来说，以上就是差分分析的过程，个人觉得最难的还是如何找最好的差分特征(很大程度依赖攻击者的敏锐的直觉)，建议大家实打实的实现一个小型加密算法的差分攻击才能有更好的理解（文献[3]的第六章有实例分析）。
参考文献
[1] 李超, 孙兵, 李瑞林. 分组密码的攻击方法与实例分析[M]. 科学出版社, 2010.
[2] Stinson D R . Cryptography Theory and Practice[M]. CRC Press, 1995.
[3] Basin D , Maurer U . Information Security and Cryptography: Texts and Monographs[J]. Lhrgateway.nu.edu.pk, 2012.