新型相关密钥密码分析攻击解析

### 新型相关密钥密码分析攻击解析 在当今的信息安全领域，密码分析是保障数据安全的关键环节。本文将深入探讨利用相关密钥进行的新型密码分析攻击，这些攻击方法为我们理解和评估密码系统的安全性提供了新的视角。 #### 1. 引言 在密码学中，密钥调度算法对分组密码的强度有着至关重要的影响。许多分组密码的密钥调度算法会使密钥之间存在明显的关系，而这些关系可被攻击者利用来实施攻击。本文介绍了两种新型攻击：一是通过选择明文来降低穷举搜索攻击的复杂度，以及基于互补性质的更快变体攻击；二是低复杂度的选择密钥攻击。这些攻击与密码系统的轮数和 F 函数的细节无关，复杂度可能极低。 这些攻击的基础在于，在许多分组密码中，密钥调度算法可看作一组算法，每个算法从前面几轮的子密钥中提取一个特定的子密钥。若各轮提取子密钥的算法相同，给定一个密钥，就可以将所有子密钥向后移动一轮，得到一组可从其他密钥派生的有效子密钥，我们称这些密钥为相关密钥。 相关密钥攻击的一个有趣特点是，它们与被攻击密码系统的轮数无关。这些攻击适用于 LOKI 的两个变体和 Lucifer，但 DES 由于密钥调度算法中各轮的移位模式不同，对相关密钥攻击具有抗性。不过，如果 DES 密钥调度中的一位移位被两位移位取代，DES 也会变得容易受到此类攻击。 相关密钥还有一个潜在应用，即分析哈希函数（基于分组密码的哈希函数或通用哈希函数）。在这些函数中，有可能通过选择消息，利用相关密钥特性找到具有相同哈希值的另一条消息。目前虽未发现具体应用，但哈希函数的设计者应谨慎设计，使函数免受此弱点影响。 攻击结果如下表所示： | 密码系统 | 选择明文攻击复杂度 | 选择密钥选择明文攻击复杂度 | 选择密钥已知明文攻击复杂度 | | --- | --- | --- | --- | | LOKI89 | 约 1.5 × 2^54 | 约 2^32 | 约 2^32 | | LOKI91 | 约 1.375 × 2^61 | 约 2^32 | 约 2^48 | | Lucifer | 约 2^32 | - | - | #### 2. LOKI89 和 LOKI91 的描述 LOKI 是一组分组密码，有两个变体：原始的 LOKI 密码重命名为 LOKI89，较新的变体为 LOKI91。这两个变体的结构与 DES 类似，但替换了 F 函数、初始和最终置换以及密钥调度算法。 新的 F 函数将数据的右半部分与子密钥进行异或运算，然后将结果扩展为 48 位，输入到四个 12 位到 8 位的 S 盒中。S 盒的输出进行拼接和置换，形成 F 函数的输出。 在 LOKI89 中，初始和最终置换被替换为将数据与密钥进行异或运算的变换。密钥调度算法取一个 64 位密钥，将其左半部分定义为 K1，右半部分定义为 K2。其他子密钥 Ki（K3 到 K16）通过将第 j = i - 2 轮的子密钥 Kj 向左旋转 12 位得到（Ki = ROL12(Kj)）。因此，所有奇数轮的子密钥共享相同的位，所有偶数轮的子密钥也共享相同的位。 LOKI91 与 LOKI89 的区别在于 S 盒的选择，这些 S 盒经过选择以更好地抵抗差分密码分析。初始和最终置换被消除。新的密钥调度算法将密钥的左半部分定义为 K1，将其向左旋转 12 位得到 K2；将密钥的右半部分定义为 K3，将其向左旋转 12 位得到 K4。其他子密钥 Ki（K5 到 K16）通过将第 j = i - 4 轮的子密钥 Kj 向左旋转 25 位得到（Ki = ROL25(Kj)）。子密钥仍然以非常结构化的顺序共享位。 下面是 LOKI89 和 LOKI91 密钥调度的 mermaid 流程图： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([64位密钥]):::startend --> B(LOKI89):::process A --> C(LOKI91):::process B --> B1(左半部分 = K1):::process B --> B2(右半部分 = K2):::process B1 --> B3(K3 = ROL12(K1)):::process B2 --> B4(K4 = ROL12(K2)):::process B3 --> B5(K5 = ROL12(K3)):::process B4 --> B6(K6 = ROL12(K4)):::process C --> C1(左半部分 = K1):::process C --> C2(ROL12(左半部分) = K2):::process C --> C3(右半部分 = K3):::process C --> C4(ROL12(右半部分) = K4):::process C3 --> C5(K5 = ROL25(K1)):::process C4 --> C6(K6 = ROL25(K2)):::process ``` #### 3. 选择密钥攻击 在选择密钥攻击中，使用具有特定关系的两个相关密钥对多个明文进行加密。攻击者只知道两个密钥之间的关系，而不知道密钥本身。攻击者接收密文并利用它们来找到两个密钥。研究了两种选择密钥攻击：选择密钥已知明文攻击和选择密钥选择明文攻击。这些攻击与被攻击密码系统的精确轮数无关，即使轮数增加（特别是翻倍），得到的密码系统仍然容易受到相同的攻击。 ##### 3.1 LOKI89 的选择密钥攻击 在 LOKI89 中，任意选择一个奇数轮和一个偶数轮的两个子密钥，都对应一个 64 位密钥。由于从两个前轮子密钥派生子密钥的所有算法相同，两个子密钥所在轮次的位置不影响后续子密钥（或前轮子密钥）的派生。 如果固定一个密钥 K 的两个子密钥 K2 和 K3，并定义第二个密钥 K' 为 K1' = K2，K2' = K3，那么密钥 K' 的子密钥 Ki' 与密钥 K 的后续子密钥 Ki + 1 相同。在这种情况下，K' = (K2, K3) = (KR, ROL12(KL))。 对于这样的两个相关密钥，有以下性质：如果在密钥 K 下加密时第二轮之前的数据等于在密钥 K' 下加密时第一轮之前的数据，那么在两次执行中，数据和 F 函数的输入相同，只是相差一轮。 如果明文 P 在密钥 K 下加密，第二轮之前的数据为 (PR ⊕ KR, PL ⊕ KL ⊕ F(PR ⊕ KR, KL))。这个数据等于在密钥 K' 下加密时第一轮之前的数据 P' ⊕ K' = (PR ⊕ KR, PL ⊕ ROL12(KL))，因此在这样的一对中： P' = (PR, PL ⊕ KL ⊕ ROL12(KL) ⊕ F(PR ⊕ KR, KL)) 同样，密文之间也存在类似的关系： C'