Skip to content

3-Way

3-Way 算法是由 Joan Daemen（后来 AES 算法的设计者之一）于 1994 年设计的一种分组密码算法。在 CTF 逆向工程竞赛中，该算法因其结构清晰、特征常量明显以及便于魔改（Modified）的特性，常被出题人用于构建自定义加密题目。

以下是关于 3-Way 算法的原理、特征识别及逆向分析策略的全面讲解。

1. 算法概述

3-Way 是一种基于 SPN（Substitution-Permutation Network，代换-置换网络） 结构的轻量级分组密码。

  • 分组长度：96 位（12 字节）。这通常在内存中表现为 3 个 32 位整数（int32）。

  • 密钥长度：96 位。

  • 轮数：标准设计为 11 轮。

  • 设计理念：该算法不仅用于加密，还被设计用于哈希函数构建。其核心优势在于软硬件实现的高效性。

2. 内部结构与核心函数

3-Way 的核心状态（State）由三个 32 字（Word）组成，记为 \(a_0, a_1, a_2\)。加密过程由一系列轮函数迭代组成，每一轮包含四个主要层级：\(\theta\)（Theta）、\(\pi_1\)（Pi-1）、\(\gamma\)（Gamma）和 \(\pi_2\)（Pi-2），合称为 \(\rho\)（Rho）函数。

2.1 Theta (\(\theta\)) 层：线性扩散

\(\theta\) 层主要负责位的扩散，使一位的变化影响到其他多位。它是线性的，通常涉及异或（XOR）和循环移位（Rotate）操作。

在标准 3-Way 中，\(\theta\) 函数通过线性反馈移位寄存器（LFSR）的原理构建，其特征是使用了大量的异或操作将 \(a_0, a_1, a_2\) 混合。

特征：在汇编中表现为密集的 XOR 和 ROL/ROR 指令，且三个状态字之间相互依赖。

2.2 Pi-1 (\(\pi_1\)) 层：置换/移位

\(\pi_1\) 层仅进行位置变换，不改变位的值。

标准操作：

  • \(a_0\) 循环左移 10 位。

  • \(a_2\) 循环左移 1 位。

  • \(a_1\) 保持不变（有些实现或变种会修改此处）。

2.3 Gamma (\(\gamma\)) 层：非线性代换

这是 3-Way 算法安全性的核心，相当于 AES 中的 S-Box，提供了非线性特性（Confusion）。它对三个状态字进行按位逻辑运算。

标准逻辑（基于 C 语言逻辑）：

\[ \begin{aligned} a_0' &= \neg a_0 \oplus (\neg a_1 \land a_2) \\ a_1' &= \neg a_1 \oplus (\neg a_2 \land a_0) \\ a_2' &= \neg a_2 \oplus (\neg a_0 \land a_1) \end{aligned} \]

特征识别：在反编译代码中，若看到三个变量之间进行 ~ (NOT)、& (AND)、^ (XOR) 的混合运算，且逻辑呈现对称性，极大概率是 Gamma 层。

2.4 Pi-2 (\(\pi_2\)) 层：置换/移位

与 \(\pi_1\) 类似，是另一层置换。

标准操作：

  • \(a_0\) 循环左移 1 位。

  • \(a_2\) 循环左移 10 位。

  • \(a_1\) 保持不变。

2.5 轮常数添加 (Key Schedule)

3-Way 算法不像 DES 或 AES 那样通过密钥扩展生成轮密钥，而是直接使用主密钥，但在每一轮中异或一个不同的轮常数（Round Constant）。

常数生成算法（Fingerprint 特征）：

常数生成基于一个 LFSR。初始常数为 0xB0B（十六进制）。

下一轮常数的生成逻辑为：

  1. 当前常数左移 1 位。

  2. 若溢出 16 位（即 x & 0x10000），则异或多项式 0x11011。

3. 加密流程

标准的加密函数 encrypt 通常遵循以下步骤：

  1. 初始 Key 加载：将明文与密钥进行异或。

  2. 轮循环（通常 \(N=11\)）：

    • 状态异或轮常数。

    • 执行 \(\rho\) 函数（顺序通常为 \(\theta \to \pi_1 \to \gamma \to \pi_2\)）。

  3. 末轮处理：

    • 状态异或通过 0xB0B 生成的最后一个轮常数。

    • 再次执行 \(\theta\) 函数（这是 3-Way 结构的一个特殊设计，为了使解密结构与加密结构对称）。

    • 最后一次异或密钥。

4. CTF 逆向中的识别特征

在拿到二进制文件进行静态分析时，可通过以下特征快速识别 3-Way 算法：

  1. 特征常数 0xB0B：搜索立即数 0xB0B (2827) 或其生成逻辑（左移后异或 0x11011）。这是最强烈的特征。

  2. 96 位块操作：代码中频繁出现三个一组的 32 位变量操作。

  3. 非线性逻辑 Gamma：查找包含取反（NOT）、与（AND）、异或（XOR）且结构对称的代码块。

  4. 移位常量：查找循环移位指令，特别是 10 和 1 这两个位移量。

5. 解密与逆向策略

由于 3-Way 是 SPN 结构，解密过程是加密过程的逆运算，且顺序相反。

5.1 标准解密流程

  1. Inv-Theta (\(\theta^{-1}\))：首先执行 \(\theta\) 的逆函数。

  2. 逆向轮循环（从第 \(N\) 轮倒推至第 0 轮）：

    • 执行 \(\pi_2^{-1}\)（逆向移位）。

    • 执行 \(\gamma^{-1}\)（逆向非线性层）。

    • 执行 \(\pi_1^{-1}\)（逆向移位）。

    • 执行 \(\theta^{-1}\)。

    • 异或对应的轮常数。

    • 异或密钥。

5.2 逆向难点与应对

在 CTF 中，出题人通常不会直接使用标准算法，而是进行魔改。

  • 魔改 \(\theta\)：\(\theta\) 可能是最复杂的线性变换。如果出题人修改了 \(\theta\) 的逻辑，且无法直观看出其逆变换，可以利用线性代数原理。将 \(\theta\) 看作一个 \(96 \times 96\) 的矩阵（在 GF(2) 域上），通过传入基向量（如 100..., 010...）获取变换矩阵，然后计算该矩阵的逆矩阵来实现解密。

  • 魔改 \(\gamma\)：如果 Gamma 层逻辑改变，不再是自我逆向的，可以通过查表法解决。因为 Gamma 通常是按位（或小块）独立的，遍历所有可能的输入（如 3 位输入对应 8 种情况），建立 输出 -> 输入 的映射表。

  • 修改常数：出题人可能更改初始常数 0xB0B 或多项式。需从汇编中提取真实的常数生成逻辑。

6. 总结

3-Way Block Cipher 是逆向工程中考察选手对分组密码结构理解的经典案例。掌握其核心在于：

  1. 识别：通过 0xB0B 和 Gamma 层的逻辑运算快速定位。

  2. 分析：逐层对比标准算法，找出被修改的 \(\pi\)（移位位数）、\(\gamma\)（逻辑运算）或 \(\theta\)（混合逻辑）。

  3. 求解：编写脚本，严格按照“后进先出”的顺序执行逆运算。对于复杂的线性层使用矩阵求逆，对于非线性层使用查表法。