块加密的差分攻击：从国际赛题洞悉ARX密码攻击技术

1. 加密算法分析

1.1 加密函数结构

给定一个256位的ARX(Addition-Rotation-XOR)加密算法，其核心加密函数如下：

def rot(n, r):
    return (n >> r) | ((n << (256 - r)) & (2**256 - 1))

round_constants1 = [3, 141, 59, 26, 53, 58]
round_constants2 = [2, 7, 18, 28, 182, 8]
M = 2**256

def encrypt(key, block):
    for i in range(6):
        block = (block + key) & (M-1)  # 加法层
        block = block ^ rot(block, round_constants1[i]) ^ rot(block, round_constants2[i])  # 旋转和异或层
    return block

1.2 旋转函数分析

rot(n, r)函数实现了循环右移操作：

• 将n右移r位
• 将n左移(256-r)位并取低256位
• 将两部分进行或运算

数学表达式为：rot(n, r) = (n >> r) | ((n << (256 - r)) & (2**256 - 1))

2. 差分攻击原理

2.1 差分攻击基本概念

差分攻击是一种选择明文攻击，通过分析特定差分对在加密过程中的传播来恢复密钥。核心思想：

1. 差分对：选取一对明文(P, P')，它们之间满足已知的差分ΔP = P⊕P'
2. 差分传播：跟踪ΔP在每一轮的非线性/线性层中如何变成中间差分ΔX_i
3. 统计特征：利用高概率差分特征来验证或排除子密钥假设

2.2 ARX密码差分攻击特点

ARX密码由加法(Addition)、旋转(Rotation)和异或(XOR)组成，其差分特性：

1. 加法层：会产生进位传播，导致差分非线性扩散
2. 旋转层：将差分位移动到不同位置
3. 异或层：线性操作，差分直接异或传播

3. 攻击实施步骤

3.1 构造明文差分

选择特殊的明文对使得差分集中在特定位置：

base = 2**246 * j  # 在246位设置1，低位全0

这样base + k（k∈[0,255]）只会影响最低8位，高位保持不变。

3.2 差分传播分析

1. 加法层分析：

   • 设要猜测的密钥位为k_index
   • 如果k_index位为0，差分直接传播
   • 如果k_index位为1，会产生进位影响更高位

2. 旋转层影响：

   • 旋转将差分位移动到新位置
   • 需要跟踪旋转后差分的位置变化

3.3 密钥恢复技术

1. 差分统计：

   • 对每个密钥位，收集大量样本
   • 统计差分在关键位置的出现频率

2. 权重分配：

   • 越接近起点的进位传播越重要，赋予更高权重
   • 典型权重分配：2^6, 2^4, 2^3, 2^2, 2^1

3. 密钥位判断：

   • 累计25轮×256个样本
   • 统计高权重出现次数
   • 根据统计偏差判断密钥位是0还是1

4. 攻击实现细节

4.1 旋转操作的逆函数

由于加密中的旋转异或操作不是单次可逆的，需要迭代逼近：

def undo_rotations(block, a, b):
    """逆转 block ^ rot(block,a) ^ rot(block,b) 操作"""
    for _ in range(8):  # 8次迭代足够收敛
        block = block ^ rot(block, a) ^ rot(block, b)
        a = (a + a) & 0xff  # 同步更新旋转常数
        b = (b + b) & 0xff
    return block

4.2 具体攻击步骤

1. 选择明文对，差分集中在特定位置
2. 获取密文对并逆向最后一轮操作
3. 分析中间差分的统计特征
4. 对每个密钥位进行统计判断
5. 前250位通过统计恢复，最后6位暴力枚举

5. 防御建议

1. 增加轮数：更多轮次使差分特征更难追踪
2. 使用更复杂的非线性操作：如S-box替换
3. 引入密钥相关常数：使攻击者难以预测差分传播
4. 使用掩码技术：隐藏实际的差分路径

6. 总结

本案例展示了如何对ARX结构的块密码实施差分攻击，关键在于：

1. 精心构造明文差分对
2. 准确分析加法进位对差分传播的影响
3. 利用统计方法从噪声中提取密钥信息
4. 结合部分暴力破解完成最后几位密钥的恢复

这种攻击方法不仅适用于本题，也是分析许多ARX结构密码(如ChaCha20, Salsa20等)的基础技术。