一道国际赛题洞悉块加密的差分攻击-先知社区

一道国际赛题洞悉块加密的差分攻击

UMDCTF-2025有这么一题，运用了ARX密码差分攻击

task.py

加密函数的逆置换

key是随机生成的32字节密钥。需要我们输入明文，然后对明文进行进行32字节一组的块加密。我们看加密函数

这里有旋转移位，异或，是ARX型密码。这里我们的block先加上key，然后将block与两次旋转结果再异或。对于这个rot函数，就是把一个数的低r位拿到前面，也就是

图片加载失败

这个算法是可逆的。我这边可以解释一下：

首先，找到M定义为最小的正整数n这样

图片加载失败

让我们从扩展函数squared开始：

图片加载失败

比如

我们n有

图片加载失败

如果 n是奇数，则简化为 I；如果 n 是偶数，则结果为零。因此，要使其成为可逆函数，n必须是奇数。

这里就是我们通过的逆函数

所以我们在这题这部分的逆函数是

差分攻击

现在的话我们就要考虑怎么输入明文，进行选择明文攻击。这里就需要用到差分攻击的思想

什么是差分攻击

简单的例子，比如一个简单的异或加密算法

c为密文，m是明文，k是密钥

我们可以从一对密文中直接得到一对明文的异或，经过一次异或运算消除了密钥

差分攻击的核心思想

差分对

选取或构造一对明文$ (P,P^′)$，它们之间满足已知的差分 $ΔP=P⊕P^′$

差分传播

跟踪 $ΔP$ 在每一轮的非线性／线性层（如加法、XOR、旋转、S-box）中如何变成中间差分 $ΔX_i$;

轮内统计

某些差分对在某轮后落到特定位时具有较高概率；利用这些高概率特征，对给定密文对 $(C,C^′)$ 统计出现频次，来验证或排除某个子密钥假设；

ARX密码的差分攻击

图片加载失败

我们要恢复K(256位)，则需要

构造明文差分

我们先不考虑旋转直接看这段代码如何让明文序列在最低位（bit 0）线性递增

我们选

它在二进制里是什么样子？

在二进制里就是一个在第 246 位上有一个 1，其它位全是 0

乘以 j（不管 j是 1、2、3……），都只会影响那第 246 及更高位上的排列组合，高达第 ∞ 位都在那一串“高位”里；而低于 246 位的所有位——也就是 bit 0 到 bit 245——

始终都是 0

。

然后我们做

也就是占据了最低 8 位（bit 0…7）。因为 k<256，做加法

base + k

：

它只会在“低 8 位”上产生进位或翻转，因为最高也就到 bit 7；

bit 8…bit 245 上仍然是 0，不会被 kkk 干扰（因为 kkk 只能把前 8 位从 00000000 → 11111111）；

bit 246 及以上保持跟

base

一样，和

无关。

当k从0到255变化时，base+k只会让最低8bit变化

图片加载失败

它们之间的差分

但这有个问题，就是如果有进位会导致差分异或结果不对

因为

base + k

的差分会落在最低的 8 个比特（bit 0…7）上；而这 8 个比特在加法中都可能触发进位，并影响后续 XOR/rot 层的多个位置

所以我们要进行旋转

旋转后，这些差分就恰好分布在新位置

即 “以

keyindex

为起点、长度 8 的那一段”——而其它 248 位都一样没有差分。

统计与猜测

重复多次（25 轮，每轮 256 个样本），累计每个样本的“carry 权重”；

按奇偶性将样本分成两类：若偶数编号样本的高权重更多，就猜 key 比特为 1，反之为 0；

这样就能用差分概率偏差把 key 的每一位排除一半（从 2 候选到 1）。

组合与容错

前 250 位用上述方法逐 bit 猜出，剩下 6 位由于统计噪声较大，改用暴力枚举；

举一个例子回顾刚才过程

我们假设要猜的

key_index = 3

（倒数第 3 位，从 0 开始编号），

在真实脚本里会把最低位的差分旋转到这个位置，这里为了演示直接在明文里操作。

令两条明文：

也就是说，只有

bit 3

从 0→1。

经过“加 key”层

设对应的

key = 0b k₇k₆k₅k₄ k₃k₂k₁k₀

，这里我们只关心 k₃（第 3 位）：

加法和进位

用二进制加法列竖式（只看低 5 位以示意）：

对

，因为 P' 在 bit 3 上多了 1，就在加到 key 的那一位上会产生“进位”：

●

如果 k₃ = 0，则 1 + 0 → bit 3 变 1，无进位；

●

如果 k₃ = 1，则 1 + 1 → bit 3 变 0，并

向 bit 4 产生进位

。

于是，

X ⊕ X'

在 bit 3、bit 4 会表现出不同：

k₃ 值	bit 3 的 Δ	bit 4 的 Δ
0	1	0
1	0	1

其它更高位除了进位连锁，也可能被影响，但我们只看最前面几位作为示例。

经过 “XOR + Rotate” 层，并撤销最后一轮

真实脚本里，下一步是

我们用

undo_rotations

把最后一轮的这一步撤销，只恢复到 “加 key 后” 的中间态

、

。

这样我们就可以直接对

做分析。

取出 ΔX（差分异或）并统计 carry 痕迹

假设我们观察到的 ΔX\Delta XΔX（只列低 6 位）是：

上述表格告诉我们：如果 k₃=0，那么 C3=1,C4=0,C₃=1, C₄=0,C3=1,C4=0；如果 k₃=1，那么 C3=0,C4=1，C₃=0, C₄=1,C3=0,C4=1。

这就给我们一个“区分”k₃ 的

统计特征

：

k₃=0 时，ΔX 在 bit 3 上更有可能是 1；

k₃=1 时，ΔX 在 bit 4 上更有可能是 1。

脚本的

get_weight

正是把这些关键位（在 256 bit 里对应到

(172 - key_index)...(176 - key_index)

）抽出来加权累加：

累计 25 轮 × 256 个样本后，“正确的 k₃ 假设” 会在这些位置积累明显更大的权重；

“错误的 k₃ 假设” 则更分散，难以同时满足所有位的高权重。

最终脚本对这 256 个样本分奇偶号统计高于阈值的次数，就能判断 k₃ 是 0 还是 1。

我们的脚本是

这里的选值这样是因为

2**6, 2**4, 2**3, 2**2, 2**1

这些值不是随意选的，它们体现了“越接近起点（bit

key_index

）的 carry 传播越重要、越可靠”，所以权重越大。

这段代码里，把第一个位置给了最高权重

2**6=64

，下一个给

2**4=16

，依次递减到

2**1=2

。

如果某条样本在第一个被关注的位发生了差分，就加 64 分；如果只在更远的位翻了，就只加 2、4、8、16 等较小分。

所以我们的脚本是

EXP