6 轮 ARX 块密码选择明文差分攻击:x^rot(x,a)^rot(x,b) 可逆迭代 8 次撤销末轮,单比特差分旋转定位 + 进位权重奇偶统计逐位恢复 256 位密钥,尾部 6 位与错位暴力修正
ctf/crypto · verified
6 轮 ARX 块密码选择明文差分攻击:x^rot(x,a)^rot(x,b) 可逆迭代 8 次撤销末轮,单比特差分旋转定位 + 进位权重奇偶统计逐位恢复 256 位密钥,尾部 6 位与错位暴力修正
一句话结论
对「每轮 X += K; X ^= rot(X,a) ^ rot(X,b)」的 6 轮 256 位 ARX 块密码,在仅限 2^14 次查询、单次 ≤300 块的选择明文 oracle 下:先用 M=I+C^a+C^b 满足 M^32=nI(n 奇数时为 I)的性质把 XOR+rot 层的逆写成 5 次平方迭代(a、b 逐次翻倍),从密文撤销末轮该层回到「加 key 后」中间态;再对每个 key_index 构造只在该位附近扰动 8 bit 的旋转明文差分,利用 1+key_bit 是否进位的差分位置偏差(bit3→bit4)做加权统计,25 轮 ×256 样本按奇偶分布判定每一位,250 位统计恢复 +6 位及 1~2 位错位暴力枚举,解出 flag 密文(UMDCTF-2025 实战,成功率约 25%/次尝试)。
原理
- XOR+rot 层可逆:把该层看作 GF(2) 上线性算子
M = I + C^a + C^b(C 为循环移位算子)。展开得M^2 = I + C^{2a} + C^{2b}(交叉项成对相消),归纳有M^{2^k} = I + C^{2^k a} + C^{2^k b};32 位字上C^{32a}=I故M^32 = 3I = I(256 位字则M^256 = I)。于是M^{-1} = M^{31} = M·M^2·M^4·M^8·M^16,即连续 5 轮「x ^= rot(x,a) ^ rot(x,b),然后 a、b 翻倍」的迭代即为逆变换(代码里做 8 次更保险);配合每轮X -= K即可整体解密——前提是先拿到 K。 - 差分对消除未知量:纯 XOR 层的差分
C0⊕C1 = m0⊕m1与密钥无关;ARX 中唯一的非线性来源是加 key 的进位。设ΔP只有 bit i 为 1,则X = P+K与X' = P'+K在 bit i 上的和差直接暴露K_i:K_i=0时差分留在 bit i(无进位),K_i=1时差分跳到 bit i+1(进位)。 - 统计判定:撤销末轮 XOR+rot 后对相邻样本计算
ΔX = X⊕X',在(172-key_index)...(176-key_index)五个位置加权求和(2^6,2^4,2^3,2^2,2^1,越靠近起点的进位越可靠权重越大),累计 25 轮样本后按样本编号奇偶分布(偶数号高权重多 → 猜 1)判定该位。 - 样本构造:
base = 2^246·j保证低 246 位为 0,base + k (k<256)只在低 8 位变化且不与高位进位纠缠;rot(base+k, 256-key_index)把 8-bit 差分精确旋到待测位位置;key_index>200时改用2^100·j避免与高位重叠。 - 容错:统计恢复 250 位后剩 6 位噪声大,直接 2^6 枚举;若仍有 1~2 位统计错误,组合枚举翻转位再配合前 6 位枚举,用解密结果是否含 flag 前缀校验。
触发条件
- 加密服务提供选择明文 oracle:任意明文 → 6 轮 ARX 密文(查询次数/块数有限也能在配额内完成 25×256 采样);
- 轮函数为「加常量密钥 + XOR 双旋转」,旋转常数已知(硬编码);
- 最后给出一个未知明文(flag)的密文用于验证恢复的密钥。
利用步骤
- 从题目源码抄下轮常数与 encrypt 实现,本地复现。
- 实现
undo_rotations(5~8 次x ^= rot(x,a)^rot(x,b),同步 a=(a+a)&0xff)与完整decrypt(逆序撤销 XOR+rot 层、减 key)。 - 对 key_index = 0..249 逐位攻击:构造 256 个
rot(2^246·j + k, 256-key_index)明文(每轮换 j 共 25 轮)发送 oracle;密文逐块undo_rotations后取相邻差分,get_weight累计进位权重。 - 权重 ≥600 的样本按编号奇偶统计得该位猜测,填入 guessed_key[255-key_index]。
- 发送
q结束输入,取 flag 密文;用猜测密钥 decrypt,命中 flag 前缀即成功;否则枚举前 6 位、再枚举翻转 1~2 位错误组合。
PoC
核心片段(完整 EXP 见原文):
def undo_rotations(block, a, b):
for _ in range(8):
block = block ^ rot(block, a) ^ rot(block, b)
a = (a + a) & 0xff
b = (b + b) & 0xff
return block
def get_weight(key_index, diff):
return (diff[(172-key_index)%256])*2**6 + (diff[(173-key_index)%256])*2**4 + \
(diff[(174-key_index)%256])*2**3 + (diff[(175-key_index)%256])*2**2 + \
(diff[(176-key_index)%256])*2**1
# 每位:25 轮 × 256 样本,weights>=600 的样本按 k 奇偶分布猜 0/1
变体与关联
- 变体:轮数、字长、旋转常数不同时按
M^{字长}=I重新核对逆迭代次数与权重位置偏移(172/176 等常数与轮常数具体取值相关)。 - 变体:进位判定统计可换成似然比/多数表决;查询配额更紧时可减少 attempts 提高单轮样本复用。
- 关联:[[ctf-crypto-feistel-gf2-16-cubic-rank-drop-key-recovery]](代数降秩恢复轮密钥,同为自研轮函数攻击)。
- 关联:[[ctf-crypto-blackbox-chosen-input-mapping]](黑盒选择输入映射分析)。
检测与防御
- 防御(密码设计视角):ARX 轮函数做密钥调度(每轮不同子密钥)、加轮前混合轮常数、提高轮数,避免全轮共用同一 256 位密钥使加法层差分逐位独立可测;oracle 应限制查询总数与差分结构查询。
- 检测:加密服务被高频单比特差分枚举访问(明文低位规则递增/旋转模式)可作为 oracle 滥用特征告警。