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 轮后:SubBytes 是双射,ShiftRows 只是重排,MixColumns 把「1 个活跃字节」扩散成同一列的 4 个活跃字节。这一列的 4 个字节都是活动字节
x的双射,其余 12 字节仍是常量。第 2 轮后:ShiftRows 把这 4 个活跃字节分到 4 个不同的列;每列恰好只有 1 个活跃字节,而 MixColumns 是可逆线性变换,所以该列 4 个输出字节仍然是
x的双射。于是 16 个字节全部是x的双射。第 3 轮后:每列 4 个字节都是
x的(不同)双射,经过 MixColumns 的线性组合后不再保证是双射,但「平衡性」保留:
这就是 Square 攻击依赖的 balanced(平衡) 性质。
最后一轮没有 MixColumns,只有:
其中 是 ShiftRows 引起的字节置换,$k_4$ 是第 4 轮轮密钥。于是对某个密文字节位置 猜测:
把该组 256 条密文在这个位置上求和:
对每个字节位置独立枚举 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 & good4 组独立约束后,每个字节都只剩 唯一 候选:
k4 = 4f 59 37 93 a6 e5 44 f3 f5 5f f9 11 e2 34 83 db3.3 逆密钥扩展,从第 4 轮轮密钥还原主密钥
AES-128 的密钥扩展是可逆的。标准扩展为(i ≥ 4):
反过来,已知(即),从 递减到 4:
得到 即主密钥: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}