Aleer
Aleer
发布于 2026-11-10 / 4 阅读
0
0

CRYPTO - 少了六轮

1. 题目信息

附件两个文件:

  • chall.py:出题脚本;

  • output.json:1024 条 (pt, ct) 样本 + flag_iv + flag_ciphertext。

chall.py 的关键逻辑:

ROUNDS = 4
active_positions = SystemRandom().sample(range(16), 4)
batches = [make_delta_set(round_keys, active) for active in active_positions]
samples = [pair for batch in batches for pair in batch]
SystemRandom().shuffle(samples)

make_delta_set 生成的是一个标准的 Δ 集(Λ-set):

base = bytearray(secrets.token_bytes(16))
for value in range(256):
    plaintext = bytearray(base)
    plaintext[active] = value      # 只改一个字节,遍历 0..255
    ciphertext = encrypt_block(bytes(plaintext), round_keys)

也就是说:

  • 一共 4 组,每组 256 条;

  • 每组内 16 字节中有 15 字节固定,只有 1 个「活动字节」从 0x00 遍历到 0xff;

  • 4 组的活动位置不同(本题为 0、5、6、7);

  • 1024 条记录被完全打乱,组别和活动位置都未知。

AES 被砍成 4 轮(encrypt_block 为:初始 AddRoundKey → 3 个完整轮 → 最后一轮 SubBytes/ShiftRows/AddRoundKey,没有 MixColumns)。这正是 Square 攻击的经典适用场景。


2. 攻击原理:4 轮 AES 的积分性质

设一个 Δ 集为 256 个明文,除一个字节外全部相同,该字节取遍 0..255。跟踪 3 轮后状态中每个字节的异或和(GF(2⁸) 上的和,即逐比特异或):

  1. 第 1 轮后:SubBytes 是双射,ShiftRows 只是重排,MixColumns 把「1 个活跃字节」扩散成同一列的 4 个活跃字节。这一列的 4 个字节都是活动字节 x 的双射,其余 12 字节仍是常量。

  2. 第 2 轮后:ShiftRows 把这 4 个活跃字节分到 4 个不同的列;每列恰好只有 1 个活跃字节,而 MixColumns 是可逆线性变换,所以该列 4 个输出字节仍然是 x 的双射。于是 16 个字节全部是 x 的双射。

  3. 第 3 轮后:每列 4 个字节都是 x 的(不同)双射,经过 MixColumns 的线性组合后不再保证是双射,但「平衡性」保留:

⨁x=0255state3[ i ]=0(∀i=0,…,15)\bigoplus_{x=0}^{255} \text{state}_3[\,i\,] = 0 \quad (\forall i=0,\dots,15)


这就是 Square 攻击依赖的 balanced(平衡) 性质。

最后一轮没有 MixColumns,只有:

cj=S(state3[π(j)])⊕k4[j]c_j = S\big(\text{state}_3[\pi(j)]\big) \oplus k_4[j]


其中π\pi 是 ShiftRows 引起的字节置换,$k_4$ 是第 4 轮轮密钥。于是对某个密文字节位置jj 猜测k4[j]k_4[j]:

state3[π(j)]=S−1(cj⊕k~)\text{state}_3[\pi(j)] = S^{-1}\big(c_j \oplus \tilde{k}\big)


把该组 256 条密文在这个位置上求和:

⨁i=0255S−1(cj(i)⊕k~)={0,k~=k4[j]通常≠0,k~≠k4[j]\bigoplus_{i=0}^{255} S^{-1}\big(c_j^{(i)} \oplus \tilde{k}\big) = \begin{cases} 0, & \tilde{k} = k_4[j] \\[2pt] \text{通常}\ne 0, & \tilde{k} \ne k_4[j] \end{cases}


对每个字节位置独立枚举 256 个猜测即可。每个字节只需 256×256 次查表,16 个字节总共约 100 万次运算。


3. 解题步骤

3.1 把打乱的样本重新分组

对每个候选活动位置 p,把每条明文中「去掉第 p 字节」后的 15 字节作为哈希键:

for p in range(16):
    d = {}
    for pt, ct in samples:
        d.setdefault(pt[:p] + pt[p+1:], []).append((pt, ct))
    for v in d.values():
        if len(v) == 256:      # 恰好 256 条 → p 就是该组的活动字节
            groups[p] = v
  • 如果 p 不是活动位置,256 条记录两两之间至少差 2 个字节,分组大小全是 1;

  • 如果 p 是活动位置,同组 15 字节完全相同,键会聚成恰好 256 条。

本题得到活动位置 {0, 5, 6, 7},四组各 256 条,并且每组第 p 字节恰好是 0..255 的一个排列(脚本里做了断言)。

3.2 逐字节恢复第 4 轮轮密钥

对 16 个密文字节位置,枚举 256 个密钥猜测,计算该组 256 条密文的 INV_SBOX[c ^ k] 异或和。单个组里错误猜测也会以约 1/256 的概率碰巧为 0(本题每组每字节会留下 1~5 个候选),因此把 4 个组的结果取交集:

inter = None
for s in sets:
    good = {k for k in range(256) if xor_sum == 0}
    inter = good if inter is None else inter & good

4 组独立约束后,每个字节都只剩 唯一 候选:

k4 = 4f 59 37 93 a6 e5 44 f3 f5 5f f9 11 e2 34 83 db

3.3 逆密钥扩展,从第 4 轮轮密钥还原主密钥

AES-128 的密钥扩展是可逆的。标准扩展为(i ≥ 4):

wi=wi−4⊕{SubWord(RotWord(wi−1))⊕Rcon(i/4),i≡0(mod4)wi−1,otherwisew_i = w_{i-4} \oplus \begin{cases} \text{SubWord}(\text{RotWord}(w_{i-1})) \oplus \text{Rcon}(i/4), & i \equiv 0 \pmod 4 \\ w_{i-1}, & \text{otherwise} \end{cases}


反过来,已知w16,…,w19w{16},\dots,w{19}(即k4k_4),从i=19i=19 递减到 4:

wi−4=wi⊕{SubWord(RotWord(wi−1))⊕Rcon(i/4),i≡0(mod4)wi−1,otherwisew_{i-4} = w_i \oplus \begin{cases} \text{SubWord}(\text{RotWord}(w_{i-1})) \oplus \text{Rcon}(i/4), & i \equiv 0 \pmod 4 \\ w_{i-1}, & \text{otherwise} \end{cases}


得到w0…w3w_0\dots w_3 即主密钥:272c2ae9dd3e9cb8b843b9fa95eef72b。

注意:任意 16 字节都能作为合法的第 4 轮轮密钥(密钥扩展是双射),所以第 4 轮轮密钥本身没有额外的可校验冗余;校验来自「用还原的主密钥重新加密样本」。

3.4 校验并解密 flag

用主密钥扩展出 5 个轮密钥,重新加密全部 1024 条样本,逐条比对密文——全部吻合,说明密钥唯一正确。然后按 CBC 模式解密 flag_ciphertext(flag_iv 为 IV),去 PKCS#7 填充:

PCTF{o8ZIbudgwdjwS47v8zAqvKbz2tHqg5zv}

4. 完整脚本(solve.py)

import json
from functools import reduce
from chall import SBOX, INV_SBOX, expand_key, encrypt_block, cbc_decrypt
​
data = json.load(open("output.json"))
samples = [(bytes.fromhex(s["pt"]), bytes.fromhex(s["ct"])) for s in data["samples"]]
​
# ---- 1. 重新分组:固定 15 字节,组大小为 256 的位置就是活动字节 ----
groups = {}
for p in range(16):
    d = {}
    for pt, ct in samples:
        d.setdefault(pt[:p] + pt[p+1:], []).append((pt, ct))
    for v in d.values():
        if len(v) == 256:
            groups[p] = v
sets = [groups[p] for p in sorted(groups)]
print("active plaintext bytes:", sorted(groups))
​
# ---- 2. Square 攻击:逐字节恢复第 4 轮轮密钥 ----
k4 = []
for j in range(16):
    inter = None
    for s in sets:
        cts = [ct[j] for pt, ct in s]
        good = {k for k in range(256)
                if reduce(lambda a, c: a ^ INV_SBOX[c ^ k], cts, 0) == 0}
        inter = good if inter is None else (inter & good)
    assert len(inter) == 1, (j, inter)
    k4.append(inter.pop())
print("round-4 key:", bytes(k4).hex())
​
# ---- 3. 逆密钥扩展:k4 -> 主密钥 ----
def rcon(i):
    v = 1
    for _ in range(1, i):
        v = ((v << 1) ^ 0x1B) & 0xFF if v & 0x80 else (v << 1) & 0xFF
    return v
​
def sub_word(w):
    return bytes(SBOX[b] for b in w)
​
def inv_expand(last):
    w = {16 + i: last[4*i:4*i+4] for i in range(4)}     # words 16..19
    for i in range(19, 3, -1):
        t = w[i - 1]
        if i % 4 == 0:
            t = bytes(a ^ b for a, b in zip(sub_word(t[1:] + t[:1]),
                                            bytes([rcon(i // 4), 0, 0, 0])))
        w[i - 4] = bytes(a ^ b for a, b in zip(w[i], t))
    return b"".join(w[i] for i in range(4))
​
key = inv_expand(bytes(k4))
print("master key:", key.hex())
​
# ---- 4. 用全部样本验证密钥,再 CBC 解密 ----
rk = expand_key(key)
assert all(encrypt_block(pt, rk) == ct for pt, ct in samples)
print("key verified on all 1024 samples")
​
iv = bytes.fromhex(data["flag_iv"])
ct = bytes.fromhex(data["flag_ciphertext"])
print("FLAG:", cbc_decrypt(ct, rk, iv).decode())

运行输出:

active plaintext bytes: [0, 5, 6, 7]
round-4 key: 4f593793a6e544f3f55ff911e23483db
master key: 272c2ae9dd3e9cb8b843b9fa95eef72b
key verified on all 1024 samples
FLAG: PCTF{o8ZIbudgwdjwS47v8zAqvKbz2tHqg5zv}


评论