3.2 截断差分分析（TRUNCATED DIFFERENTIAL CRYPTANALYSIS）
3.2.1 截断差分分析原理
- 选择明文攻击
- 差分分析的变种，输入和输出差分由固定值⇒ 可能值的集合
- 截断≠截取
- 截断：将一个差分的部分取值确定为0或1的比特放宽为取0或1均可的状态，从而影响不随机事件发生的概率，导致攻击结果的改变
截断
n比特二进制串 m 0 m 1 . . . m n − 1 {m_{0}m_{1}...m_{n-1}} m0m1...mn−1, m 0 ′ m 1 ′ . . . m n − 1 ′ {m_{0}^{'}m_{1}^{'}...m_{n-1}^{'}} m0′m1′...mn−1′是 m 0 m 1 . . . m n − 1 {m_{0}m_{1}...m_{n-1}} m0m1...mn−1的截断当且仅当对于所有的 0 ≤ i ＜ n {0≤i＜n} 0≤i＜n有 m i ′ = m i {m_{i}^{'}=m_{i}} mi′=mi 或者 m i ′ {m_{i}^{'}} mi′不固定
- m 0 m 1 . . . m n − 1 {m_{0}m_{1}...m_{n-1}} m0m1...mn−1有 2 n − 2 {2^{n}-2} 2n−2种截断，除去全*和全等
i轮截断差分路线
β 0 → 1 轮 β 1 → 1 轮 β 2 → 1 轮 . . . → 1 轮 β i {\beta_{0}\stackrel{1轮}\to \beta_{1}\stackrel{1轮}\to \beta_{2}\stackrel{1轮}\to... \stackrel{1轮}\to\beta_{i}} β0→1轮β1→1轮β2→1轮...→1轮βi是一条i轮差分路线，则 β 0 ′ → 1 轮 β 1 ′ → 1 轮 β 2 ′ → 1 轮 . . . → 1 轮 β i ′ {\beta_{0}^{'}\stackrel{1轮}\to \beta_{1}^{'}\stackrel{1轮}\to \beta_{2}^{'}\stackrel{1轮}\to... \stackrel{1轮}\to\beta_{i}^{'}} β0′→1轮β1′→1轮β2′→1轮...→1轮βi′是*轮截断差分路线，其中 β j ′ ( 0 ≤ j ≤ i ) {\beta_{j}^{'}(0\le j \le i )} βj′(0≤j≤i)是 β j {\beta_{j}} βj的截断
i轮截断差分
β 0 → i 轮 β i {\beta_{0}\stackrel{i轮}\to\beta_{i}} β0→i轮βi是一条i轮差分，则 β 0 ′ → i 轮 β i ′ {\beta_{0}^{'}\stackrel{i轮}\to\beta_{i}^{'}} β0′→i轮βi′是一条i轮截断差分，其中 β j ′ ( j = 0 , i ) {\beta_{j}^{'}(j=0,i)} βj′(j=0,i)是 β j {\beta_{j}} βj的截断。
截断差分攻击的一般过程
得到了三轮截断差分,概率为1：
( 0000 0000 0010 0000 ) → 2 R ( ∗ 0 ∗ ∗ 0000 ∗ 0 ∗ ∗ ∗ 0 ∗ ∗ ) {(0000 \ 0000 \ 0010 \ 0000)\stackrel{2R}\to(*0** \ 0000 \ *0** \ *0**)} (0000 0000 0010 0000)→2R(∗0∗∗ 0000 ∗0∗∗ ∗0∗∗)
( 0000 0000 0010 0000 ) → 3 R ( ∗ 0 ∗ ∗ ∗ 0 ∗ ∗ ∗ 0 ∗ ∗ ∗ 0 ∗ ∗ ) {(0000 \ 0000 \ 0010 \ 0000)\stackrel{3R}\to(*0**\ *0** \ *0** \ *0**)} (0000 0000 0010 0000)→3R(∗0∗∗ ∗0∗∗ ∗0∗∗ ∗0∗∗)
- 一旦S盒的输入差分有1bit出现*，输出差分就需要结合S盒的DDT
3.2.2 CipherFour算法的截断差分分析
思路：利用概率为1的三轮截断差分，采用“1+3+1”的攻击模式，头尾各加一轮，进行5轮密钥恢复攻击
- 采样
-
选择明文
-
选择 2 4 {2^{4}} 24个明文对构成的结构体
-
结构体：
- 只有i改变，其他为固定常数
- 任意两两组对，大约 2 7 {2^{7}} 27对结构体
- 满足
-
-
明文组对
- 猜测4-bit的 k 0 , 2 {k_{0,2}} k0,2，筛选满足S盒输出差分 为0010的消息对
- 对密钥每一种猜测值，设有s对满足截断差分头部
- 若 k 0 , 2 {k_{0,2}} k0,2猜对，则有s对正确对
-
- 去噪
- 密文对差分无特殊性质，满足随机置换概率，无法对密文对过滤
- 密钥恢复攻击
- 思路：
- 若 k 0 , 2 {k_{0,2}} k0,2猜对，则有s对正确对满足截断差分头部和尾部
- 若 k 5 , 0 {k_{5,0}} k5,0猜对，则对应的s对正确对的密文解密到截断差分尾部，高4bit应都满足*0**
- 则至少有一个 k 5 , 0 {k_{5,0}} k5,0的计数器数值为s；否则， k 0 , 2 {k_{0,2}} k0,2 猜错
- 同理剩下的 k 5 , 1 , k 5 , 2 , k 5 , 3 {k_{5,1},k_{5,2},k_{5,3}} k5,1,k5,2,k5,3
- 需要恢复4-bit的 k 0 , 2 {k_{0,2}} k0,2和 16-bit的 k 5 {k_{5}} k5
- 即对于 k 5 , i ( i = 0 , 1 , 2 , 3 ) {k_{5,i}(i=0,1,2,3)} k5,i(i=0,1,2,3)的每种可能，需要带入下面的方程式组，验证每对密文 C i , C j {C_{i},C_{j}} Ci,Cj
- 思路：
总结
- 需要发现高概率的r轮截断差分
- 推测从明（密文）加（解）密到截断差分的头（尾）部相关的 密钥，求解带概率的方程
- 关键：探测中间状态的信息
- 截断差分分析则专注于非线性组件输出的某些特定部分，即截断后的差分。这种方法允许分析者忽略非线性组件输出的某些位，从而可能发现传统差分分析无法发现的差分路径。
- 只关注部分差分，它可能降低搜索有效差分路径的复杂度。
- 可以看作是差分分析的一种特殊形式，它通过聚焦于差分的特定部分来简化分析过程
