58、分组密码的相关攻击与线性攻击分析

分组密码的相关攻击与线性攻击分析

1. 相关密码攻击

1.1 轮密钥演化与SQUARE密码

轮密钥 (k_t) 由加密密钥 (K) 通过迭代方式推导得出，具体公式如下：
[K = k_{(0)}]
[k_{(t + 1)} = \psi(k_{(t)})]
其中，(\psi) 是一个可逆仿射变换，(k_{(t + 1)}) 定义为：
[
\begin{align }
k_{(t + 1)[0]}&=k_{(t)[0]}\oplus rotl(k_{(t)[3]})\oplus C_{(t)}\
k_{(t + 1)[1]}&=k_{(t)[1]}\oplus k_{(t)[0]}\
k_{(t + 1)[2]}&=k_{(t)[2]}\oplus k_{(t)[1]}\
k_{(t + 1)[3]}&=k_{(t)[3]}\oplus k_{(t)[2]}
\end{align }
]
这里，(rotl(a_i)) 是对一行进行左字节旋转操作，即 (rotl([a_{i[0]}, a_{i[1]}, a_{i[2]}, a_{i[3]}]) = [a_{i[3]}, a_{i[0]}, a_{i[1]}, a_{i[2]}])，轮常数 (C_t) 也通过迭代定义为 (C_{(t)} = x\cdot C_{(t - 1)})，(C_{(0)} = x)。

SQUARE密码的第 (t) 轮函数表示为 ([k_{(t)}]\rho)：
([k_{(t)}]\rho=\sigma\circ\pi\circ\gamma\circ\theta)
SQUARE密码定义为在密钥加法 ([k_{(0)}]\sigma) 和 (\theta^{-1}) 之前进行八轮操作：
[SQUARE[k]=\rho[k_{(8)}]\circ\rho[k_{(7)}]\circ\rho[k_{(6)}]\circ\rho[k_{(5)}]\circ\theta^{-1}\circ\rho[k_{(4)}]\circ\rho[k_{(3)}]\circ\rho[k_{(2)}]\circ\rho[k_{(1)}]\circ\sigma[k_{(0)}]]
为保证安全性，设计者将轮数固定为八轮，但也允许保守用户直接增加轮数。

1.2 SQUARE密码的相关密码攻击

由于SQUARE密码的密钥调度不依赖于总轮数，不同轮数的SQUARE密码是相关的。若在不同轮数的SQUARE中使用相同密钥，则可应用相关密码攻击。

设 (c_r) 为 (r) 轮SQUARE的密文，(c_{r + \Delta r}) 为 (r + \Delta r) 轮SQUARE的密文。若 (c_r) 和 (c_{r + \Delta r}) 与同一明文相关，则称它们为一个正确对。下面分别讨论 (\Delta r = 1) 和 (\Delta r = 2) 的情况：
- (\Delta r = 1) 时 ：此时SQUARE密码简化为一轮，有如下关系：
[c_{r + 1}=\rho k_{(r + 1)} ]
由该式可推导出轮密钥 (k_{(r + 1)})：
[k_{(r + 1)}=\theta^{-1}\circ\gamma^{-1}\circ\pi^{-1}(c_{r + 1}\oplus c_{r})]
由于密钥演化 (\psi) 是可逆的，可直接从该轮密钥推导出加密密钥 (K)，该加密密钥 (K) 可用于解密所有用它加密的消息。
- (\Delta r = 2) 时 ：此时SQUARE密码简化为两轮，有如下关系：
[c_{r + 2}=\rho[k_{(r + 2)}]\circ\rho k_{(r + 1)} ]
令 (c_{r}’=\theta^{-1}\circ\gamma^{-1}\circ\pi^{-1}(c_{r}))，则上式简化为：
[c_{r + 2}\oplus c_{r}’=\theta^{-1}\circ\gamma^{-1}(k_{(r + 2)}\oplus k_{(r + 1)})]
注意到 ((k_{(r + 1)}\oplus c_{r}’)) 的一行与 ((k_{(r + 2)}\oplus c_{r + 2})) 的一列相关，因此该式可分解为四个32位块长度的块密码，其通用形式为：
[c\oplus c’=\theta^{-1}\circ\gamma(k_1\oplus k_2)]
从两对 ((c, c’)) 中可轻松确定 (k_1)（或 (k_2)）的值，从而得知轮密钥 (k_{(r + 1)})（或 (k_{(r + 2)})），进而确定加密密钥。

1.3 AES密码

AES密码的轮数是灵活的，AES - 128为10轮，AES - 192为12轮，AES - 256为14轮（其中AES - x表示具有x位秘密密钥的AES）。然而，AES密码对相关密码攻击具有抗性。

1.3.1 AES的结构

这里仅介绍AES的密钥调度，其伪代码如下：

2. !")
5. #$
6. %"
7. # !
8. & '& ("
9. # !
11. #
12. % !"
14. )#
15. !
16. *)#$"
18. )#+,-
19. ,
20. )""-./
21. *01)#"
23. )#+,
24. )"
25. *
26. #
28. )
29. # !

复制代码

在上述代码中， key[] 表示加密密钥， Nk 是加密密钥以32位字为单位的长度， Nb 是块大小（以字为单位）， w[] 是轮密钥， Nr 是轮数。 Subword 、 RotWord 和 Rcon 是一些函数，这里省略其具体说明。

1.3.2 AES对相关密码攻击的抗性

从AES的密钥调度描述可知，AES的密钥调度依赖于密钥长度 (Nk)。因此，不可能在不同轮数的AES中使用相同的密钥。即使256位密钥是128位密钥的重复，且两者都用于加密相同的消息，由于AES - 256的密钥调度与AES - 128略有不同，也无法应用相关密码攻击。可以看出，AES能够抵抗相关密码攻击，因为密钥长度和轮数之间的关系是固定的，避免了在相关密码中使用相同的密钥。

1.4 新的AES密钥调度

在ACISP2002上提出了一种新的AES密钥调度，但在相关密码攻击下，这种新的密钥调度比原始的更弱。

1.4.1 新AES密钥调度的描述

这里仅介绍AES - 192和AES - 256的新密钥调度，其伪代码如下：

1. 2
3. #3#!'*4+
4. !5'
6. #!1#!*4+
7. '61
8. *#$
10. *#$
11. !6
12. #
13. ⊕+×!1 ⊕
15. #
16. ⊕+×!1 ⊕
18. *#$
19. '
20. 7
21. +"
22. + *
23. -"
24. 8 9)"
25. 4-"
26. #

复制代码

在上述代码中，每个 (M_{kj}) 表示加密密钥的一个字节。 ByteSub 、 ShiftRow 、 MixColumn 和 AddRoundKey 是AES轮函数的组成部分。 S[] 是AES中使用的S盒。每个 (KR_r) 表示一个128位的轮密钥。

1.4.2 新AES密钥调度的弱点

考虑以下场景：假设一个64位密钥用于AES - 192和AES - 256，很可能该64位密钥分别拼接形成192位和256位密钥。那么，AES - 192和AES - 256的前12轮密钥将相同。此时，可以对AES - 256的最后两轮进行攻击。

2. 抵抗相关密码攻击的方法

2.1 通用方法

抵抗具有灵活轮数的分组密码的相关密码攻击的通用方法是将密钥调度与总轮数相关联。这样，当使用相同的密钥加密相同的明文时，(r) 轮密码中第 (i) 轮后的中间值应与 (r’) 轮密码（(r\neq r’)）中的中间值有很大不同。

2.2 SQUARE密码的示例

以SQUARE密码为例，保持其原始的密钥调度，并对其子密钥进行额外修改。在SQUARE的原始密钥调度之后，将所有子密钥表示为 (k_1, \cdots, k_n)（每个为一个字节），额外修改按以下方式进行：

1. for i = 1 to n do
2. k_{i}=S_{\gamma}[k_{i}]+S_{\gamma}[r]

复制代码

其中，(S_{\gamma}) 是SQUARE中使用的S盒，(r) 是总轮数。期望具有这种修改后的密钥调度的SQUARE能够抵抗相关密码攻击。由于目前使用的是8轮SQUARE，建议保持8轮SQUARE与之前相同，但增加轮数的SQUARE可以采用这种强化的密钥调度。

2.3 相关攻击总结

具有灵活轮数但密钥调度与总轮数无关的分组密码容易受到相关密码攻击。在设计具有灵活特性的密码时应谨慎。同时，提出了一种通过将密钥调度与总轮数相关联来抵抗相关密码攻击的方法。

引入相关密码攻击后，可以将差分攻击分类为相关消息攻击（原始差分密码分析）、相关密钥攻击和相关密码攻击。这些攻击的任何组合也会产生新的攻击。在密码设计中应考虑所有这些攻击。

下面通过一个mermaid流程图来展示SQUARE密码相关密码攻击的流程：

1. graph TD;
2. A[开始] --> B{∆r的值};
3. B -->|∆r = 1| C[根据c_r和c_r+1推导k_r+1];
4. C --> D[从k_r+1推导K];
5. D --> E[使用K解密消息];
6. B -->|∆r = 2| F[根据c_r和c_r+2推导k_r+1和k_r+2];
7. F --> G[从k_r+1和k_r+2推导K];
8. G --> E;
9. E --> H[结束];

复制代码

2.4 分组密码CIKS - 1的线性攻击

2.4.1 CIKS - 1密码概述

CIKS - 1是一种基于数据相关置换（DDP）的64位分组迭代密码，具有8轮和256位主密钥 (K)。主密钥 (K) 被分为8个32位子密钥，通过内部密钥调度注入到每一轮变换中。

2.4.2 CIKS - 1的结构

• CP盒操作 ：CIKS - 1由执行数据相关置换的CP盒组成。CP操作 (P_{n/m}(V)(X)) 是对输入向量 (X) 执行固定置换 (\Pi_V)，其中 (V) 是控制向量。CP盒可以由标准的基本 (P_{2/1}) 盒叠加而成，(P_{2/1}) 盒由一位 (v) 控制，当 (v = 0) 时，交换两个输入位；当 (v = 1) 时，位不交换。
• 一轮结构 ：CIKS - 1的一轮加密（解密）除了CP盒置换外，还使用固定置换 (\Pi_1)、(\Pi_2)、7位旋转、一个XOR操作和16个并行的模 (2^2) 加法（减法）。具体操作如下：
  1. XOR操作 ：将右数据子块与当前轮子密钥进行异或，其中子密钥根据左子块进行置换。
  2. 并行模 (2^2) 加法（减法） ：将两个32位操作数分别分为16个2位操作数，然后对相应的2位操作数对同时执行16个模 (2^2) 加法（减法）。
  3. 固定置换 ：(\Pi_1) 和 (\Pi_2) 用于改善数据扩散。
     • (\Pi_1) 的公式为：
       [V’ = (v_0’, \cdots, v_{79}’) = \Pi_1(L|L’|S’) = \Pi_1(l_0, \cdots, l_{31}, l_{16}, \cdots, l_{31}, s_0’, \cdots, s_{31}’) = (l_8, \cdots, l_{31}, s_0’, \cdots, s_7’, l_{16}, \cdots, l_{31}, l_0, \cdots, l_7, s_8’, \cdots, s_{31}’)]
       其中，(S’ = (s_0’, \cdots, s_{31}’)) 是左子块根据当前轮子密钥置换后的值。
     • (\Pi_2) 的公式为：
       [V’’ = (v_0’‘, \cdots, v_{79}’‘) = \Pi_2(S’‘|L^ |L’‘) = \Pi_2(s_0’‘, \cdots, s_{31}’‘, l_0^ , \cdots, l_{31}^ , l_0^ , \cdots, l_{15}^ ) = (s_{16}’‘, \cdots, s_{23}’‘, l_0^ , \cdots, l_3^ , s_{24}’‘, \cdots, s_{31}’‘, l_4^ , \cdots, l_{15}^ , s_0’‘, \cdots, s_7’‘, l_{16}^ , \cdots, l_{19}^ , s_8’‘, \cdots, s_{15}’‘, l_{20}^ , \cdots, l_{31}^ , l_0^ , \cdots, l_{15}^ )]
       其中，(S’’ = (s_0’‘, \cdots, s_{31}’‘) = P_{32/48}(VK >>> 7)(L^ ))。

2.4.3 CIKS - 1的线性攻击

对简化的5轮版本的CIKS - 1进行线性密码分析（LC）。考虑16个概率 (p = \frac{3}{4}) 的线性近似，用于16个并行的模 (2^2) 加法，通过堆积引理推导出一轮线性近似，概率为 (P = \frac{1}{2} + 2^{-17})。通过实验验证该概率是有效的，且实际概率优于 (\frac{1}{2} + 2^{-17})。

使用该一轮近似构造3轮线性近似，概率同样为 (P = \frac{1}{2} + 2^{-17})，并对简化的5轮、64位块、160位密钥的CIKS - 1进行线性攻击。攻击需要约 (2^{36}) 个选择明文，成功率为78.5%，约 (2^{65.7}) 次加密操作来恢复最后一轮（第5轮）密钥。

下面通过一个表格来总结不同密码的相关信息：
| 密码 | 轮数 | 密钥长度 | 相关密码攻击抗性 | 线性攻击情况 |
| ---- | ---- | ---- | ---- | ---- |
| SQUARE | 8（可增加） | - | 易受攻击 | 未提及 |
| AES - 128 | 10 | 128位 | 有抗性 | 未提及 |
| AES - 192 | 12 | 192位 | 有抗性 | 未提及 |
| AES - 256 | 14 | 256位 | 有抗性 | 未提及 |
| 新AES（192和256位） | - | 192/256位 | 较弱 | 未提及 |
| CIKS - 1（简化5轮） | 5 | 160位 | 未提及 | 可进行线性攻击 |
| CIKS - 1（完整8轮） | 8 | 256位 | 未提及 | 可通过扩展攻击 |

通过以上分析，我们对不同分组密码的结构、安全性以及攻击方法有了更深入的了解。在实际应用中，应根据具体需求选择合适的密码，并注意其安全性和性能。同时，不断研究和改进密码设计，以应对日益复杂的攻击手段。

3. CIKS - 1密码改进探讨

3.1 改进方向分析

对CIKS - 1密码进行线性攻击的结果表明，其在简化5轮版本下存在一定的安全隐患。为了提高CIKS - 1密码的安全性，需要从多个方面进行改进。主要的改进方向可以围绕增强数据混淆、扩散以及提高线性近似的难度等方面展开。

3.2 具体改进措施

3.2.1 调整数据相关置换

目前CIKS - 1使用的数据相关置换（DDP）虽然是其特色，但在面对线性攻击时可能不够强大。可以考虑增加DDP的复杂度，例如引入更多的控制参数或者更复杂的置换规则。具体操作步骤如下：
1. 增加控制向量维度 ：将控制向量 (V) 的长度增加，使得数据相关置换的可能性更多。例如，原本 (P_{n/m}(V)(X)) 中的 (V) 长度为 (m)，可以将其增加到 (m’)（(m’ > m)）。
2. 设计新的置换规则 ：重新设计固定置换 (\Pi_V) 的规则，使其更难以被线性近似。可以通过引入非线性函数或者随机化的方式来实现。例如，在置换过程中加入一个随机数生成器，根据生成的随机数对置换结果进行调整。

3.2.2 优化轮函数操作

CIKS - 1的轮函数中使用了固定置换、XOR操作和并行模 (2^2) 加法等操作。可以对这些操作进行优化，以提高密码的安全性。具体操作步骤如下：
1. 增加操作种类 ：在轮函数中加入新的操作，如乘法操作或者更复杂的逻辑运算。例如，在并行模 (2^2) 加法之后，再进行一次模 (2^3) 的乘法操作。
2. 调整操作顺序 ：改变轮函数中操作的执行顺序，使得线性攻击更难以找到有效的近似路径。例如，将XOR操作和固定置换的顺序进行交换。

3.2.3 强化密钥调度

密钥调度在密码的安全性中起着重要作用。可以对CIKS - 1的密钥调度进行强化，使其更难以被破解。具体操作步骤如下：
1. 增加密钥扩展复杂度 ：在密钥扩展过程中，引入更多的非线性变换。例如，使用S盒对密钥进行多次变换，或者加入循环移位和异或操作。
2. 引入轮数相关的密钥生成 ：将密钥生成与轮数相关联，使得不同轮次使用的密钥具有更大的差异。例如，在每一轮密钥生成时，根据当前轮数对密钥进行调整。

3.3 改进效果评估

在实施上述改进措施后，需要对改进后的CIKS - 1密码进行安全性评估。可以采用以下方法进行评估：
1. 线性攻击测试 ：再次对改进后的CIKS - 1进行线性攻击测试，观察攻击所需的选择明文数量和成功率是否有明显提高。
2. 差分攻击测试 ：进行差分攻击测试，评估改进后的密码对差分攻击的抗性。
3. 复杂度分析 ：分析改进后的密码在计算复杂度和存储复杂度方面的变化，确保改进不会导致性能过度下降。

下面通过一个mermaid流程图来展示CIKS - 1密码改进的流程：

1. graph TD;
2. A[开始] --> B[分析CIKS - 1的弱点];
3. B --> C{选择改进方向};
4. C -->|调整DDP| D[增加控制向量维度];
5. D --> E[设计新的置换规则];
6. C -->|优化轮函数| F[增加操作种类];
7. F --> G[调整操作顺序];
8. C -->|强化密钥调度| H[增加密钥扩展复杂度];
9. H --> I[引入轮数相关的密钥生成];
10. E --> J[组合改进措施];
11. G --> J;
12. I --> J;
13. J --> K[实施改进后的CIKS - 1];
14. K --> L[进行安全性评估];
15. L --> M{评估结果是否满意};
16. M -->|是| N[结束];
17. M -->|否| B;

复制代码

4. 密码攻击与设计的综合思考

4.1 攻击与设计的相互关系

密码攻击和密码设计是相互对立又相互促进的关系。攻击手段的不断发展促使密码设计者不断改进密码算法，以提高其安全性；而新的密码设计又会引发新的攻击方法的研究。例如，相关密码攻击的出现使得设计者开始关注密钥调度与总轮数的关系，从而设计出更安全的密码算法。

4.2 密码设计的原则

在密码设计过程中，需要遵循一些基本原则，以确保密码的安全性和性能。以下是一些重要的原则：
1. 混淆与扩散原则 ：密码算法应具有良好的混淆和扩散特性，使得密文与明文和密钥之间的关系尽可能复杂。例如，在CIKS - 1中，通过数据相关置换和轮函数操作来实现混淆和扩散。
2. 抗攻击原则 ：密码算法应能够抵抗各种已知的攻击方法，如线性攻击、差分攻击、相关密码攻击等。在设计过程中，需要对算法进行充分的安全性分析和测试。
3. 性能原则 ：密码算法的计算复杂度和存储复杂度应在可接受的范围内，以满足实际应用的需求。例如，在设计CIKS - 1时，考虑到其硬件实现的效率，采用了一些简单的操作。

4.3 未来密码研究的趋势

随着计算机技术的不断发展，密码学面临着新的挑战和机遇。未来密码研究的趋势可能包括以下几个方面：
1. 量子密码学 ：量子计算机的发展对传统密码学构成了威胁，因此量子密码学成为了研究的热点。量子密码学利用量子力学的原理来实现安全的通信，具有无条件安全性。
2. 后量子密码学 ：为了应对量子计算机的威胁，研究人员正在寻找能够抵抗量子攻击的密码算法，即后量子密码算法。这些算法通常基于数学难题，如格问题、编码理论等。
3. 密码协议的安全性 ：除了密码算法本身的安全性，密码协议的安全性也越来越受到关注。例如，在网络通信中，需要设计安全的密钥交换协议和认证协议，以确保通信的安全性。

4.4 总结与展望

通过对分组密码的相关攻击和线性攻击的分析，我们了解了不同密码算法的结构、安全性和攻击方法。同时，探讨了抵抗相关密码攻击的方法和对CIKS - 1密码的改进措施。在密码设计和应用过程中，需要充分考虑各种攻击手段的威胁，遵循密码设计的原则，不断研究和改进密码算法，以应对日益复杂的安全挑战。

未来，随着密码学的不断发展，我们期待出现更安全、更高效的密码算法和协议，为信息安全提供更可靠的保障。同时，也需要加强对密码学的研究和教育，培养更多的专业人才，推动密码学的发展。

下面通过一个表格来总结密码攻击与设计的相关要点：
| 方面 | 要点 |
| ---- | ---- |
| 攻击类型 | 相关密码攻击、线性攻击、差分攻击等 |
| 抵抗方法 | 将密钥调度与总轮数相关联、调整密码结构等 |
| 设计原则 | 混淆与扩散原则、抗攻击原则、性能原则 |
| 未来趋势 | 量子密码学、后量子密码学、密码协议安全性 |

通过以上的分析和总结，我们对分组密码的攻击与设计有了更全面的认识，希望能够为密码学的研究和应用提供一些有益的参考。