AES S-box 重复/缺失字节侧信道:区分随机块与密文 + z3 解双重 Base64 乱序表
ctf/crypto · verified
一句话结论
当题目按二进制位输出“纯随机块”或“AES 加密块”时,若 AES 实现的 S 盒把 0xCC 写了两次、0xCE 缺失,则最后一轮(无 MixColumns)的某个输出字节位置永远不会出现某个特定值;对同一位置取足够多样本(如 4500 个),随机块会覆盖全部 256 个值,AES 块则缺一个值,据此还原二进制串;再用 z3 的 LShR/& 解双重 Base64 乱序表并用 md5 过滤错误解。
原理
- S 盒非双射:标准 AES S 盒是 256 字节的置换;题目实现把
0xCC重复、0xCE缺失,导致 S 盒像集少一个值。最后一轮没有 MixColumns,输出字节 =Sbox(input) XOR round_key;对固定位置,输出也少一个值(缺失值被 round_key 平移)。 - 随机块 vs 密文块:随机块在同一字节位置取 4500 个样本,几乎必然覆盖 0..255 全部值;AES 块则始终缺少那个特定值。
len(set(x[0::16])) == 256判为随机(bit 0),否则判为 AES 密文(bit 1)。 - 二进制串:把所有块的判定位按顺序拼成
c_bin,再long_to_bytes(int(c_bin, 2))得到隐藏字符串;注意位序/填充,必要时反转或按字节对齐。 - 双重 Base64 + 乱序表:隐藏字符串是 flag 经过两次 Base64 的产物,且输出符号表被一个 64 项置换
V打乱。建模时: flag为 42 个 8 位 BitVec;按 UUID4 格式约束(flag{、}、固定位置的-、版本位4、变体位89ab、十六进制字符)。B1 = b64_enc(flag)得到第一层 6-bit 值;用标准表映射成 56 个 ASCII 字符S_ascii;B2 = b64_enc(S_ascii)得到第二层 75 个 6-bit 值。V为 64 个互不相同的 0..63 BitVec;观测串C_STR[i]是标准表下标table.index(C_STR[i]),满足V[table.index(C_STR[i])] == B2[i]。- 为什么用
LShR/&:Base64 的 6-bit 拆分本质是逻辑右移和掩码;z3 的>>对 BitVec 是算术移位,负值会补 1,导致模型卡死/错误。改用z3.LShR(x, n)和x & 0x3f才是正确语义。 - md5 过滤:z3 可能给出多组满足约束的解;对每个候选算 md5,与题目给的哈希比对,唯一命中即 flag。
触发条件
- 题目提供“输出随机块或加密块”的 oracle/数据文件,块大小 16 字节。
- 可拿到加密实现源码(如
aes.py),能数出 S 盒重复/缺失;最后一轮无 MixColumns。 - flag 格式已知(UUID4),且经过两次 Base64/符号表打乱;有 md5 校验值。
- 有 z3(BitVec + LShR)环境。
利用步骤
- 审计 AES 实现:统计 S 盒每个值出现次数,找出重复值与缺失值;确认最后一轮是否省略 MixColumns。
- 对每个块按固定字节位置取样(如 4500 个块),统计该位置出现过的值;256 个值齐全 → 随机块;缺值 → AES 块。
- 按样本顺序生成二进制串,转成字节串;确认位序(可能需要反转/字节对齐)。
- 按“flag → Base64 → ASCII → Base64 → 乱序表”建 z3 模型;用
LShR/&实现 6-bit 拆分;加 UUID4 格式约束。 solver.check()后取模型,重建 flag;对候选算 md5,与目标哈希比对,排除多解。- 用原程序/题目校验接口验证。
PoC
import ast
import hashlib
import lzma
import z3
from Crypto.Util.number import long_to_bytes
# 1) 用 S 盒 bug 区分随机块/密文块
p = ast.literal_eval(lzma.open("output", "rt").read())
c_bin = "".join("0" if len(set(x[0::16])) == 256 else "1" for x in p)
C_STR = long_to_bytes(int(c_bin, 2)).decode()
# 2) z3 建模:flag -> Base64 -> ASCII -> Base64 -> 乱序表
s = z3.Solver()
flag = [z3.BitVec(f"f_{i}", 8) for i in range(42)]
V = [z3.BitVec(f"V_{i}", 8) for i in range(64)]
s.add(z3.Distinct(V))
for i in range(64):
s.add(V[i] >= 0, V[i] < 64)
for i, c in enumerate(b"flag{"):
s.add(flag[i] == c)
s.add(flag[41] == ord("}"))
for i in (13, 18, 23, 28):
s.add(flag[i] == ord("-"))
s.add(flag[19] == ord("4"))
s.add(z3.Or([flag[24] == ord(c) for c in "89ab"]))
hex_idx = list(range(5, 13)) + list(range(14, 18)) + list(range(20, 23)) + \
list(range(25, 28)) + list(range(29, 41))
for i in hex_idx:
s.add(z3.Or(z3.And(flag[i] >= ord("0"), flag[i] <= ord("9")),
z3.And(flag[i] >= ord("a"), flag[i] <= ord("f"))))
def b64_enc(data):
res = []
for i in range(0, len(data) - len(data) % 3, 3):
res.extend([
z3.LShR(data[i], 2),
((data[i] & 3) << 4) | z3.LShR(data[i + 1], 4),
((data[i + 1] & 15) << 2) | z3.LShR(data[i + 2], 6),
data[i + 2] & 63,
])
if len(data) % 3 == 2:
res.extend([z3.LShR(data[-2], 2),
((data[-2] & 3) << 4) | z3.LShR(data[-1], 4),
(data[-1] & 15) << 2])
return res
table = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
B1 = b64_enc(flag)
S_ascii = [z3.BitVec(f"Sa_{i}", 8) for i in range(56)]
for i in range(56):
for j in range(64):
s.add(z3.Implies(B1[i] == j, S_ascii[i] == table[j]))
B2 = b64_enc(S_ascii)
for i in range(75):
s.add(V[table.index(C_STR[i].encode())] == B2[i])
if s.check() == z3.sat:
res = bytes([s.model()[f].as_long() for f in flag])
if hashlib.md5(res).hexdigest() == "ec2783d8262e2621eece6e9e236479dc":
print(res.decode())
变体与关联
- S 盒异常变体:重复/缺失值可能不同;用“统计像集大小 + 最后一轮结构”判断,不要硬编码
0xCE。 - 块分类变体:随机源可能是 PRNG/噪声;样本量要足够大(每位置至少数百到数千),否则随机块也可能缺值。
- Base64 变体:可能一次/三次 Base64、换表、反转、URL-safe 表;按实际编码函数建模。
- 求解变体:z3 位向量移位必须用
LShR;若仍慢,可手工拆 6-bit 或用 C 枚举部分变量。 - 关联卡片:[[crypto-aes-fixed-key-ecb-ciphertext-reproduce]](AES 常量/ECB 识别)、[[ctf-reverse-base64-table-index-mutation]](Base64 换表/索引魔改)、[[ctf-reverse-z3-constraint-equation-solve]](z3 约束求解)。
检测与防御
- 检测特征:自定义 AES 实现、S 盒非置换、最后一轮缺 MixColumns、oracle 返回固定长度块、flag 经过 Base64 换表。
- 修复:使用标准 AES 库/经过测试的 S 盒;对 S 盒做双射/差分/线性测试;不要用“随机块/密文块”混合输出作为隐藏通道。
- 分析建议:先验证 S 盒是否双射,再取样分类;z3 建模时先用小规模样例验证
b64_enc与 Pythonbase64一致,再加格式约束。