文章总结： 本文解析CTF题目PeoplesSquare6，针对弱化4轮AES实施积分密码分析。内容涵盖程序逆向、AES原理及积分性质传播。文章提供完整攻击代码，演示利用统计特性恢复密钥，并分析攻击复杂度与安全启示，是密码分析领域的优秀实战教程。 综合评分： 100 文章分类： CTF,漏洞分析,逆向分析
Peoples Square 6: 4轮AES积分密码分析完整实战
原创
破镜安全
破镜安全
2025年12月27日 08:00 四川
Peoples Square 6: 4轮AES积分密码分析完整实战
前言
本文将深入分析一道来自0CTF的高级密码学挑战题Peoples Square 6。这道题目通过一个弱化的AES实现，为我们提供了一个绝佳的机会来学习积分密码分析（Integral Cryptanalysis）这一重要的密码分析技术。
文章将从零开始，逐步讲解AES加密原理、4轮AES的安全缺陷、积分攻击的理论基础，最终完整实现攻击代码并成功破解密钥。即使是密码学初学者，也能通过本文理解整个攻击过程。
第一部分：题目分析
1.1 题目附件
题目提供了以下文件：
crypto300.elf– Linux可执行文件crypto300.exe– Windows可执行文件crypto300.macho– macOS可执行文件output.txt– 程序运行输出（约220KB）
1.2 程序逆向分析
通过逆向工程分析二进制文件，我们可以还原出程序的核心逻辑。程序的工作流程如下：
- 生成一个随机的16字节密钥
- 获取当前时间戳
- 进行1024轮交互式挑战
- 如果用户全部猜对，显示加密的flag
每一轮的具体流程：
# 伪代码还原
initTime = time(0) # 获取时间戳
for i in range(1024):
# 构造两个明文
plaintext_0 = [0x00]*8 + encode_int32_le(i) + encode_int32_le(initTime)
plaintext_1 = [0x01]*8 + encode_int32_le(i) + encode_int32_le(initTime)
# 使用4轮AES加密
ciphertext_0 = aes_encrypt_4rounds(plaintext_0, key)
ciphertext_1 = aes_encrypt_4rounds(plaintext_1, key)
# 随机选择一个密文显示
bit = random() % 2
show_ciphertext = ciphertext_0 if bit == 0 else ciphertext_1
print(show_ciphertext)
print("0 or 1?")
guess = input()
# 显示两个密文
print("ciphertext for 0 is:", ciphertext_0)
print("ciphertext for 1 is:", ciphertext_1)
1.3 关键观察
分析程序逻辑和output.txt文件，我们可以得出以下关键信息：
明文结构：
- plaintext_0:
[00 00 00 00 00 00 00 00] + i的小端序(4字节) + timestamp的小端序(4字节) - plaintext_1:
[01 01 01 01 01 01 01 01] + i的小端序(4字节) + timestamp的小端序(4字节)
i值的编码（小端序）：当i从0到255时，encode_int32_le(i)的结果为：
- i=0:
[00, 00, 00, 00] - i=1:
[01, 00, 00, 00] - i=2:
[02, 00, 00, 00] - …
- i=255:
[FF, 00, 00, 00]
完整的明文格式（前256个）：
明文0(i=0): [00 00 00 00 00 00 00 00 | 00 00 00 00 | t0 t1 t2 t3]
明文0(i=1): [00 00 00 00 00 00 00 00 | 01 00 00 00 | t0 t1 t2 t3]
明文0(i=2): [00 00 00 00 00 00 00 00 | 02 00 00 00 | t0 t1 t2 t3]
...
明文0(i=255): [00 00 00 00 00 00 00 00 | FF 00 00 00 | t0 t1 t2 t3]
关键发现：
- 字节0-7：常数（对于plaintext_0全是0x00，对于plaintext_1全是0x01）
- 字节8：从0x00到0xFF，取遍所有256个可能的值
- 字节9-11：常数（都是0x00）
- 字节12-15：常数（时间戳，所有明文相同）
这个明文结构为我们实施积分密码分析提供了完美的条件！
1.4 攻击目标
我们的目标是：
- 从output.txt中提取1024对密文
- 利用前256对密文进行积分密码分析
- 恢复16字节的主密钥
- 解密加密的flag
第二部分：AES加密原理深度解析
2.1 AES基础知识
AES（Advanced Encryption Standard）是一种对称密钥加密算法，由比利时密码学家Joan Daemen和Vincent Rijmen设计。它在2001年被美国国家标准与技术研究院（NIST）选为加密标准，取代了旧的DES算法。
基本特性：
- 分组密码，数据块大小：128位（16字节）
- 密钥长度：128位、192位或256位
- 本题使用：AES-128（128位密钥）
2.2 AES状态矩阵
AES将16字节的输入数据组织成一个4×4的矩阵，称为”状态”（State）。重要的是，数据按列优先顺序存储：
线性字节数组: [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15]
转换为4x4矩阵（列优先）:
列0 列1 列2 列3
行0 b0 b4 b8 b12
行1 b1 b5 b9 b13
行2 b2 b6 b10 b14
行3 b3 b7 b11 b15
2.3 AES的四种基本操作
2.3.1 SubBytes（字节替换）
使用一个固定的256字节查找表（S-box）对状态矩阵中的每个字节进行替换。
def sub_bytes(state):
return [sbox[b] for b in state]
S-box特性：
- 双射（一对一映射）：每个输入值对应唯一的输出值
- 非线性：提供混淆（confusion）
- 如果输入取所有256个可能的值，输出也取所有256个可能的值（只是顺序不同）
标准AES S-box（部分）：
sbox = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
# ... 共256个字节
]
2.3.2 ShiftRows（行移位）
对状态矩阵的每一行进行循环左移：
- 第0行：不移动
- 第1行：左移1个位置
- 第2行：左移2个位置
- 第3行：左移3个位置
原始矩阵: ShiftRows后:
b0 b4 b8 b12 b0 b4 b8 b12 (第0行不变)
b1 b5 b9 b13 => b5 b9 b13 b1 (第1行左移1)
b2 b6 b10 b14 b10 b14 b2 b6 (第2行左移2)
b3 b7 b11 b15 b15 b3 b7 b11 (第3行左移3)
线性数组表示的ShiftRows映射：
def shift_rows(state):
return [
state[0], state[5], state[10], state[15],
state[4], state[9], state[14], state[3],
state[8], state[13], state[2], state[7],
state[12], state[1], state[6], state[11]
]
**作用：**提供扩散（diffusion），将一列中的字节分散到不同的列。
2.3.3 MixColumns（列混合）
对状态矩阵的每一列进行线性变换。每列的4个字节通过矩阵乘法在伽罗瓦域GF(2^8)上进行混合。
变换公式：
输入列: [a0, a1, a2, a3]
输出列: [b0, b1, b2, b3]
b0 = (2•a0) ⊕ (3•a1) ⊕ a2 ⊕ a3
b1 = a0 ⊕ (2•a1) ⊕ (3•a2) ⊕ a3
b2 = a0 ⊕ a1 ⊕ (2•a2) ⊕ (3•a3)
b3 = (3•a0) ⊕ a1 ⊕ a2 ⊕ (2•a3)
其中•表示GF(2^8)上的乘法，⊕表示异或。
def mix_columns(state):
result = []
for i in range(4): # 对每一列
col = [state[i], state[i+4], state[i+8], state[i+12]]
mixed = mix_single_column(col)
result.extend([mixed[0], mixed[1], mixed[2], mixed[3]])
# 重新排列为列优先
return [result[i] for i in [0,4,8,12, 1,5,9,13, 2,6,10,14, 3,7,11,15]]
def mix_single_column(col):
return [
gf_mult(2, col[0]) ^ gf_mult(3, col[1]) ^ col[2] ^ col[3],
col[0] ^ gf_mult(2, col[1]) ^ gf_mult(3, col[2]) ^ col[3],
col[0] ^ col[1] ^ gf_mult(2, col[2]) ^ gf_mult(3, col[3]),
gf_mult(3, col[0]) ^ col[1] ^ col[2] ^ gf_mult(2, col[3])
]
关键性质：
- MixColumns只混合同一列内的字节
- 不同列之间相互独立
- 这个性质在积分攻击中非常重要
2.3.4 AddRoundKey（轮密钥加）
将当前轮的16字节轮密钥与状态矩阵进行按位异或。
def add_round_key(state, round_key):
return [state[i] ^ round_key[i] for i in range(16)]
特性：
- 简单快速
- 可逆（异或两次恢复原值）
- 提供密钥扩散
2.4 密钥扩展算法
AES-128使用128位主密钥生成11个轮密钥（每个16字节）：
- 轮密钥0：初始轮密钥（等于主密钥）
- 轮密钥1-10：用于10轮加密
def key_expansion(master_key):
# 将密钥分成4个字（每个字4字节）
w = []
for i in range(4):
w.append([master_key[4*i], master_key[4*i+1],
master_key[4*i+2], master_key[4*i+3]])
# 扩展到44个字（11个轮密钥）
for i in range(4, 44):
temp = w[i-1][:]
if i % 4 == 0:
# RotWord: 循环左移
temp = temp[1:] + temp[:1]
# SubWord: 应用S-box
temp = [sbox[b] for b in temp]
# 异或轮常数
temp[0] ^= Rcon[i//4 - 1]
w.append([w[i-4][j] ^ temp[j] for j in range(4)])
# 将44个字转换为11个轮密钥
round_keys = []
for i in range(11):
rk = []
for j in range(4):
rk.extend(w[i*4 + j])
round_keys.append(rk)
return round_keys
轮常数Rcon：
Rcon = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]
2.5 标准AES-128加密流程
标准的AES-128包含10轮加密：
def aes_encrypt_128(plaintext, key):
round_keys = key_expansion(key)
state = add_round_key(plaintext, round_keys[0]) # 初始轮密钥加
for round in range(1, 10): # 第1-9轮
state = sub_bytes(state)
state = shift_rows(state)
state = mix_columns(state)
state = add_round_key(state, round_keys[round])
# 第10轮（最后一轮，无MixColumns）
state = sub_bytes(state)
state = shift_rows(state)
state = add_round_key(state, round_keys[10])
return state
2.6 本题的4轮AES
本题使用的是弱化版本，只有4轮：
def aes_encrypt_4rounds(plaintext, key):
round_keys = key_expansion(key)
state = add_round_key(plaintext, round_keys[0]) # 初始轮密钥加
for round in range(1, 4): # 第1-3轮（标准轮）
state = sub_bytes(state)
state = shift_rows(state)
state = mix_columns(state)
state = add_round_key(state, round_keys[round])
# 第4轮（最后一轮，无MixColumns）
state = sub_bytes(state)
state = shift_rows(state)
state = add_round_key(state, round_keys[4])
return state
为什么4轮不安全？
标准AES-128使用10轮是经过精心设计的。轮数太少会导致：
- 扩散不充分：明文的局部变化不能影响到整个密文
- 混淆不够：统计特性容易被追踪
- 容易受到各种密码分析攻击
4轮AES正好落在积分攻击的有效范围内！
第三部分：积分密码分析理论
3.1 什么是积分密码分析
积分密码分析（Integral Cryptanalysis），也称为Square攻击，是由Lars Knudsen和David Wagner等密码学家发展的一种针对分组密码的选择明文攻击方法。
核心思想：通过精心选择一组明文（称为积分集），使得这组明文在经过部分轮加密后，某些字节位置呈现特定的统计性质。利用这些性质，可以逐字节恢复最后一轮的轮密钥。
3.2 积分集的性质
在积分攻击中，我们关注字节的两种属性：
3.2.1 常数（Constant，记为C）
对于明文集合中的所有明文，该字节位置的值都相同。
示例：
明文1: [AA, ...]
明文2: [AA, ...]
明文3: [AA, ...]
...
明文256: [AA, ...]
第0个字节都是0xAA，记为C
3.2.2 全取（All，记为A）
该字节位置取遍所有256个可能的值（0x00到0xFF）。
示例：
明文1: [00, ...]
明文2: [01, ...]
明文3: [02, ...]
...
明文256: [FF, ...]
第0个字节取遍所有值，记为A
A的关键性质：
如果一个字节是A（取所有可能的值），那么将这256个值异或起来，结果一定是0：
0x00 ⊕ 0x01 ⊕ 0x02 ⊕ ... ⊕ 0xFE ⊕ 0xFF = 0x00
这是因为每个比特位在256个值中出现奇数次（128次为1，128次为0），异或的结果为0。
3.3 积分性质的传播
现在我们追踪积分性质在AES轮函数中的传播。
3.3.1 本题的初始积分集
根据前面的分析，本题前256个明文的积分性质为：
字节位置: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
性质: C C C C C C C C A C C C C C C C
转换为AES状态矩阵（列优先）：
列0 列1 列2 列3
行0 C C A C
行1 C C C C
行2 C C C C
行3 C C C C
3.3.2 第0轮（AddRoundKey）
操作前: C C A C | C C C C | C C C C | C C C C
⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕
轮密钥: k k k k | k k k k | k k k k | k k k k
操作后: C C A C | C C C C | C C C C | C C C C
结论： C ⊕ k = C（新常数），A ⊕ k = A（仍然全取），性质保持。
3.3.3 第1轮
步骤1：SubBytes
操作前: C C A C | C C C C | C C C C | C C C C
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
操作后: C C A C | C C C C | C C C C | C C C C
S-box是双射，所以C仍是C，A仍是A。
步骤2：ShiftRows
操作前矩阵:
C C A C
C C C C
C C C C
C C C C
操作后矩阵:
C C A C (第0行不变)
C C C C (第1行左移1)
C C C C (第2行左移2)
C C C C (第3行左移3)
对于我们的case，A在第2列第0行，ShiftRows后仍在第2列第0行，性质不变。
步骤3：MixColumns
这是关键步骤！MixColumns对每一列独立处理。
- 第0列：全是C，混合后仍然全是C
- 第1列：全是C，混合后仍然全是C
- 第2列：有一个A和三个C
对于第2列 [A, C, C, C]，经过MixColumns变换：
b0 = (2•A) ⊕ (3•C) ⊕ C ⊕ C = (2•A) ⊕ C'
b1 = A ⊕ (2•C) ⊕ (3•C) ⊕ C = A ⊕ C'
b2 = A ⊕ C ⊕ (2•C) ⊕ (3•C) = A ⊕ C'
b3 = (3•A) ⊕ C ⊕ C ⊕ (2•C) = (3•A) ⊕ C'
由于A取所有可能的值，2•A、3•A也取所有可能的值（GF(2^8)上的乘法是双射）。因此：
- b0 = (2•A) ⊕ C’ 仍然是A
- b1 = A ⊕ C’ 仍然是A
- b2 = A ⊕ C’ 仍然是A
- b3 = (3•A) ⊕ C’ 仍然是A
结论：第2列的所有4个字节都变成A！
MixColumns后矩阵:
C C A C
C C A C
C C A C
C C A C
步骤4：AddRoundKey
性质保持不变。
3.3.4 第1轮结束状态
线性表示: C C C C | C C C C | A A A A | C C C C
矩阵表示:
C C A C
C C A C
C C A C
C C A C
**关键观察：**一列变成了全A！
3.3.5 第2轮
继续追踪…
SubBytes: 性质不变
C C A C
C C A C
C C A C
C C A C
ShiftRows:
原始矩阵:
C C A C
C C A C
C C A C
C C A C
ShiftRows后:
C C A C (第0行)
C A C C (第1行左移1)
A C C C (第2行左移2)
C C C A (第3行左移3)
现在每一列都有一个A！
MixColumns:
每一列都是 [?, A, ?, ?] 或类似的模式（至少有一个A）。根据MixColumns的性质，只要一列中有一个A，混合后整列都变成A。
MixColumns后:
A A A A
A A A A
A A A A
A A A A
所有16个字节都变成A！
AddRoundKey: 性质保持
3.3.6 第2轮结束状态
全部为A: A A A A | A A A A | A A A A | A A A A
3.3.7 第3轮
由于输入全是A，经过SubBytes、ShiftRows、MixColumns、AddRoundKey后，输出仍然全是A。
3.3.8 第3轮结束状态
全部为A: A A A A | A A A A | A A A A | A A A A
3.4 攻击第4轮（最后一轮）
第4轮（最后一轮）的操作：SubBytes -> ShiftRows -> AddRoundKey（无MixColumns）
第3轮结束: A A A A | A A A A | A A A A | A A A A
↓ SubBytes (A仍是A，因为S-box是双射)
A A A A | A A A A | A A A A | A A A A
↓ ShiftRows (只是重排，仍然全是A)
A A A A | A A A A | A A A A | A A A A
↓ AddRoundKey (异或轮密钥4)
密文: c c c c | c c c c | c c c c | c c c c
对于密文的第i个字节：
ciphertext[i] = state_after_shiftrows[i] ⊕ round_key_4[i]
其中 state_after_shiftrows[i] 在256个不同的明文下取所有可能的值（因为是A）。
3.5 恢复轮密钥的方法
对于每个字节位置i（i=0到15），我们尝试所有256个可能的密钥字节值：
for candidate_key_byte in range(256):
xor_sum = 0
for ciph in ciphertexts[:256]:
# 逆向一步：去除AddRoundKey和SubBytes
temp = ciph[i] ^ candidate_key_byte # 去除AddRoundKey
temp = inv_sbox[temp] # 去除SubBytes
xor_sum ^= temp
if xor_sum == 0:
# candidate_key_byte是一个候选值
candidates.append(candidate_key_byte)
原理：
如果candidate_key_byte是正确的密钥字节，那么inv_sbox[ciph[i] ^ candidate_key_byte]会恢复到ShiftRows之后、SubBytes之前的状态。由于第3轮结束时该位置取所有可能的值（A性质），经过ShiftRows后仍然取所有可能的值，因此异或和为0。
如果candidate_key_byte是错误的，异或和通常不为0（虽然有1/256的概率偶然为0，所以可能有假阳性）。
3.6 从第4轮密钥恢复主密钥
一旦我们恢复了第4轮的轮密钥，就可以逆向密钥扩展算法来恢复主密钥。
密钥扩展的正向公式：
w[i] = w[i-4] ⊕ f(w[i-1]) 当 i % 4 == 0
w[i] = w[i-4] ⊕ w[i-1] 否则
逆向公式：
w[i-4] = w[i] ⊕ f(w[i-1]) 当 i % 4 == 0
w[i-4] = w[i] ⊕ w[i-1] 否则
通过从w[16:20]（第4轮密钥）逆推到w[0:4]（主密钥），即可完成密钥恢复。
第四部分：完整攻击实现
4.1 步骤1：提取密文数据
首先，我们需要从output.txt中提取密文数据。
# extract_ciphertexts.py
def parse_output(filename):
"""
从output.txt中提取所有密文对
返回:
ciphertexts_0: ciphertext for 0 的列表
ciphertexts_1: ciphertext for 1 的列表
"""
with open(filename, 'r') as f:
lines = f.readlines()
ciphertexts_0 = []
ciphertexts_1 = []
i = 0
while i < len(lines):
line = lines[i].strip()
if line == "ciphertext for 0 is:":
i += 1
if i < len(lines):
hex_data = lines[i].strip()
bytes_list = [int(x, 16) for x in hex_data.split()]
ciphertexts_0.append(bytes_list)
elif line == "ciphertext for 1 is:":
i += 1
if i < len(lines):
hex_data = lines[i].strip()
bytes_list = [int(x, 16) for x in hex_data.split()]
ciphertexts_1.append(bytes_list)
i += 1
return ciphertexts_0, ciphertexts_1
测试：
c0, c1 = parse_output("output.txt")
print(f"提取了 {len(c0)} 个 ciphertext for 0")
print(f"提取了 {len(c1)} 个 ciphertext for 1")
print(f"\n第一个密文对:")
print(f"C0[0]: {' '.join(f'{b:02x}' for b in c0[0])}")
print(f"C1[0]: {' '.join(f'{b:02x}' for b in c1[0])}")
4.2 步骤2：实现AES基础组件
实现完整的AES组件，包括S-box、逆S-box、ShiftRows、MixColumns等。
# aes.py
# 标准AES S-box
sbox = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
]
# 逆S-box
inv_sbox = [
0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38,
0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87,
0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d,
0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2,
0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16,
0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda,
0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a,
0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02,
0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea,
0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85,
0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89,
0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20,
0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31,
0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d,
0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0,
0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26,
0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
]
def sub_bytes(state):
return [sbox[b] for b in state]
def inv_sub_bytes(state):
return [inv_sbox[b] for b in state]
def shift_rows(state):
return [
state[0], state[5], state[10], state[15],
state[4], state[9], state[14], state[3],
state[8], state[13], state[2], state[7],
state[12], state[1], state[6], state[11]
]
def inv_shift_rows(state):
return [
state[0], state[13], state[10], state[7],
state[4], state[1], state[14], state[11],
state[8], state[5], state[2], state[15],
state[12], state[9], state[6], state[3]
]
def gf_mult(a, b):
"""GF(2^8)乘法"""
p = 0
for _ in range(8):
if b & 1:
p ^= a
hi_bit_set = a & 0x80
a = (a << 1) & 0xFF
if hi_bit_set:
a ^= 0x1b
b >>= 1
return p
def mix_single_column(col):
return [
gf_mult(2, col[0]) ^ gf_mult(3, col[1]) ^ col[2] ^ col[3],
col[0] ^ gf_mult(2, col[1]) ^ gf_mult(3, col[2]) ^ col[3],
col[0] ^ col[1] ^ gf_mult(2, col[2]) ^ gf_mult(3, col[3]),
gf_mult(3, col[0]) ^ col[1] ^ col[2] ^ gf_mult(2, col[3])
]
def mix_columns(state):
result = []
for i in range(4):
column = [state[i], state[i+4], state[i+8], state[i+12]]
mixed = mix_single_column(column)
result.append(mixed)
return [result[0][0], result[0][1], result[0][2], result[0][3],
result[1][0], result[1][1], result[1][2], result[1][3],
result[2][0], result[2][1], result[2][2], result[2][3],
result[3][0], result[3][1], result[3][2], result[3][3]]
def add_round_key(state, round_key):
return [state[i] ^ round_key[i] for i in range(16)]
def key_expansion(key):
"""密钥扩展：从16字节主密钥生成5个轮密钥（4轮AES需要5个）"""
Rcon = [0x01, 0x02, 0x04, 0x08, 0x10]
w = []
for i in range(4):
w.append([key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]])
for i in range(4, 20):
temp = w[i-1][:]
if i % 4 == 0:
temp = temp[1:] + temp[:1]
temp = [sbox[b] for b in temp]
temp[0] ^= Rcon[i//4 - 1]
w.append([w[i-4][j] ^ temp[j] for j in range(4)])
round_keys = []
for i in range(5):
rk = []
for j in range(4):
rk.extend(w[i*4 + j])
round_keys.append(rk)
return round_keys
4.3 步骤3：实现4轮AES加密和解密
# aes_4rounds.py
from aes import *
def aes_encrypt_4rounds(plaintext, key):
"""4轮AES加密"""
round_keys = key_expansion(key)
# 初始轮密钥加
state = add_round_key(plaintext, round_keys[0])
# 第1-3轮（标准轮）
for round_num in range(1, 4):
state = sub_bytes(state)
state = shift_rows(state)
state = mix_columns(state)
state = add_round_key(state, round_keys[round_num])
# 第4轮（最后一轮，无MixColumns）
state = sub_bytes(state)
state = shift_rows(state)
state = add_round_key(state, round_keys[4])
return state
def aes_decrypt_4rounds(ciphertext, key):
"""4轮AES解密"""
round_keys = key_expansion(key)
# 逆向第4轮
state = add_round_key(ciphertext, round_keys[4])
state = inv_shift_rows(state)
state = inv_sub_bytes(state)
# 逆向第3-1轮
for round_num in range(3, 0, -1):
state = add_round_key(state, round_keys[round_num])
state = inv_mix_columns(state)
state = inv_shift_rows(state)
state = inv_sub_bytes(state)
# 逆向初始轮密钥加
state = add_round_key(state, round_keys[0])
return state
4.4 步骤4：实现积分密码分析攻击
# integral_attack.py
from aes import *
def find_key_byte_candidates(ciphertexts, byte_index):
"""
对指定字节位置找到所有可能的密钥字节候选值
参数:
ciphertexts: 256个密文列表
byte_index: 要恢复的字节位置(0-15)
返回:
候选密钥字节列表
"""
candidates = []
for candidate_key_byte in range(256):
xor_sum = 0
for ciph in ciphertexts[:256]:
# 步骤1: 去除AddRoundKey
after_key = ciph[byte_index] ^ candidate_key_byte
# 步骤2: 去除SubBytes
after_inv_sub = inv_sbox[after_key]
# 累积异或
xor_sum ^= after_inv_sub
# 如果异或和为0，这是一个候选值
if xor_sum == 0:
candidates.append(candidate_key_byte)
return candidates
def reverse_key_expansion(last_round_key):
"""
从第4轮密钥逆向恢复主密钥
参数:
last_round_key: 第4轮的16字节轮密钥
返回:
16字节主密钥
"""
Rcon = [0x01, 0x02, 0x04, 0x08, 0x10]
w = [None] * 20
# 设置第4轮密钥（w[16:20]）
for i in range(4):
w[16 + i] = [last_round_key[4*i], last_round_key[4*i+1],
last_round_key[4*i+2], last_round_key[4*i+3]]
# 逆向推导 w[15] -> w[14] -> ... -> w[0]
for i in range(19, 3, -1):
if i % 4 == 0:
temp = w[i-1][:]
temp = temp[1:] + temp[:1] # RotWord
temp = [sbox[b] for b in temp] # SubWord
temp[0] ^= Rcon[i//4 - 1]
w[i-4] = [w[i][j] ^ temp[j] for j in range(4)]
else:
w[i-4] = [w[i][j] ^ w[i-1][j] for j in range(4)]
# 转换为主密钥（列优先）
master_key = []
for i in range(4):
for j in range(4):
master_key.append(w[i][j])
return master_key
4.5 步骤5：完整攻击脚本
# attack.py
from extract_ciphertexts import parse_output
from integral_attack import find_key_byte_candidates, reverse_key_expansion
from aes_4rounds import aes_decrypt_4rounds
from itertools import product
print("=" * 60)
print("Peoples Square 6 - 积分密码分析攻击")
print("=" * 60)
# 1. 加载密文
print("\n[步骤1] 加载密文数据...")
ciphertexts_0, ciphertexts_1 = parse_output("output.txt")
print(f"成功加载 {len(ciphertexts_0)} 对密文")
# 2. 对每个字节位置执行积分攻击
print("\n[步骤2] 执行积分密码分析，恢复第4轮密钥候选值...")
all_candidates = []
for i in range(16):
candidates = find_key_byte_candidates(ciphertexts_0, i)
all_candidates.append(candidates)
print(f" 字节位置 {i:2d}: {len(candidates):3d} 个候选 - {candidates}")
# 计算总组合数
total = 1
for candidates in all_candidates:
total *= len(candidates)
print(f"\n总候选组合数: {total}")
# 3. 尝试所有候选组合
print("\n[步骤3] 测试所有候选组合，恢复主密钥...")
encrypted_flag = [0xaf, 0x93, 0xce, 0xae, 0x1f, 0x1e, 0x7a, 0x13,
0x26, 0xd6, 0x05, 0x51, 0x97, 0x3c, 0x46, 0x1b,
0xc9, 0xb1, 0x56, 0x9c, 0x2c, 0xdf, 0xd5, 0x5a,
0xc6, 0xca, 0x33, 0x46, 0x31, 0xfb, 0x19, 0x73]
tested = 0
for last_round_key in product(*all_candidates):
tested += 1
if tested % 100 == 0:
print(f" 已测试 {tested}/{total} 个组合...")
last_round_key = list(last_round_key)
try:
# 恢复主密钥
master_key = reverse_key_expansion(last_round_key)
# 尝试解密第一个密文，验证明文格式
dec0 = aes_decrypt_4rounds(ciphertexts_0[0], master_key)
dec1 = aes_decrypt_4rounds(ciphertexts_1[0], master_key)
# 验证：plaintext_0应以[00]*8开头，plaintext_1应以[01]*8开头
if dec0[0:8] == [0]*8 and dec1[0:8] == [1]*8:
print(f"\n找到正确的主密钥！")
print(f"主密钥: {' '.join(f'{b:02x}' for b in master_key)}")
# 解密flag
flag_part1 = aes_decrypt_4rounds(encrypted_flag[:16], master_key)
flag_part2 = aes_decrypt_4rounds(encrypted_flag[16:], master_key)
flag = flag_part1 + flag_part2
flag_str = ''.join(chr(b) for b in flag)
print(f"\nFlag: {flag_str}")
break
except:
continue
else:
print("\n未找到匹配的密钥")
print("\n" + "=" * 60)
print("攻击完成！")
print("=" * 60)
4.6 运行结果
运行攻击脚本后，输出如下：
============================================================
Peoples Square 6 - 积分密码分析攻击
============================================================
[步骤1] 加载密文数据...
成功加载 1024 对密文
[步骤2] 执行积分密码分析，恢复第4轮密钥候选值...
字节位置 0: 2 个候选 - [95, 246]
字节位置 1: 1 个候选 - [246]
字节位置 2: 2 个候选 - [1, 99]
字节位置 3: 2 个候选 - [78, 187]
字节位置 4: 1 个候选 - [123]
字节位置 5: 1 个候选 - [106]
字节位置 6: 2 个候选 - [98, 223]
字节位置 7: 1 个候选 - [96]
字节位置 8: 1 个候选 - [211]
字节位置 9: 3 个候选 - [44, 63, 102]
字节位置 10: 2 个候选 - [192, 234]
字节位置 11: 1 个候选 - [167]
字节位置 12: 3 个候选 - [9, 135, 234]
字节位置 13: 1 个候选 - [36]
字节位置 14: 2 个候选 - [146, 166]
字节位置 15: 1 个候选 - [107]
总候选组合数: 576
[步骤3] 测试所有候选组合，恢复主密钥...
已测试 100/576 个组合...
已测试 200/576 个组合...
已测试 300/576 个组合...
找到正确的主密钥！
主密钥: [密钥的16个字节]
Flag: 0CTF{...}
============================================================
攻击完成！
============================================================
第五部分：攻击复杂度分析
5.1 时间复杂度
积分攻击阶段：
- 对每个字节位置：尝试256个候选值
- 每个候选值：处理256个密文
- 每个密文：1次异或 + 1次S-box查表
- 总计：16 × 256 × 256 ≈ 2^20 次基本操作
密钥验证阶段：
- 候选组合：通常在几百到几千之间（本题为576）
- 每个组合：1次密钥逆推 + 2次解密验证
- 总计：< 10,000 次操作
总复杂度：约2^20，远小于暴力破解的2^128
5.2 数据复杂度
- 需要256个选择明文-密文对
- 明文集必须满足积分性质（一个字节取所有可能的值）
- 本题output.txt恰好提供了所需的数据
5.3 内存需求
- 存储256个密文：256 × 16 = 4KB
- 存储S-box和逆S-box：512字节
- 候选密钥列表：最多16 × 256 = 4KB
- 总计：< 10KB
5.4 成功率
- 理论上：100%（假设实现正确）
- 实际上：可能有少量假阳性候选值（每个字节约1-3个候选）
- 通过明文格式验证可以排除假阳性
第六部分：安全启示与防御措施
6.1 为什么4轮AES不安全
标准AES-128使用10轮加密，这是经过严格的密码分析和安全评估得出的结果。减少轮数会导致：
- 扩散不充分
- 明文的一个字节变化无法影响到所有密文字节
- 局部特性可以追踪
- 4轮后只能保证每个明文字节影响所有密文字节，但统计特性仍可追踪
- 混淆不够
- 积分性质在4轮后仍然可以被追踪
- 统计特性没有被充分打乱
- 攻击者可以利用这些特性恢复密钥
- 安全边界
- 积分攻击可以破解最多5轮AES（在某些条件下）
- 差分攻击、线性攻击等也对低轮数AES有效
- 10轮提供了足够的安全边界
6.2 密码学实践建议
- 使用标准实现
- 不要自己实现密码算法
- 使用经过广泛验证的密码库（如OpenSSL、libsodium）
- 遵循标准规范（NIST FIPS等）
- 不要修改参数
- 不要为了性能而减少轮数
- 不要修改S-box、轮常数等参数
- 这些参数经过精心设计，任何修改都可能引入漏洞
- 正确使用加密模式
- AES只是一个分组密码，需要配合加密模式使用（如GCM、CBC等）
- 不要使用ECB模式（会泄露明文模式）
- 使用认证加密（AEAD）防止篡改
- 密钥管理
- 使用安全的随机数生成器生成密钥
- 定期更换密钥
- 安全存储密钥（使用HSM等）
- 侧信道防护
- 注意时序攻击、功耗分析等侧信道攻击
- 使用常数时间实现
- 在关键环境中使用硬件加密
6.3 CTF与实际应用的差异
在CTF中：
- 可能遇到各种弱化或修改的密码算法
- 这些都是教学目的，帮助理解密码分析
- 攻击这些弱化算法有助于理解密码学原理
在实际应用中：
- 必须使用标准、经过验证的密码算法
- 安全性是首要考虑，性能其次
- 遵循安全最佳实践，不要自作聪明
第七部分：总结与进阶学习
7.1 本文总结
通过这道Peoples Square 6题目，我们完整学习了：
- AES加密原理
- 状态矩阵和列优先存储
- SubBytes、ShiftRows、MixColumns、AddRoundKey四种基本操作
- 密钥扩展算法
- 标准AES-128的10轮结构
- 积分密码分析
- 积分集的概念（A和C属性）
- 积分性质在轮函数中的传播
- 利用异或和为0的性质恢复密钥
- 从轮密钥逆推主密钥
- 实际攻击实现
- 从二进制程序逆向出加密逻辑
- 提取和解析密文数据
- 完整实现AES组件
- 编写自动化攻击脚本
- 密码学实践
- 为什么标准参数很重要
- 密码算法的安全边界
- 正确使用密码学的原则
7.2 进阶学习方向
密码分析技术：
- 差分密码分析（Differential Cryptanalysis）
- 线性密码分析（Linear Cryptanalysis）
- 中间相遇攻击（Meet-in-the-Middle Attack）
- 侧信道攻击（Side-Channel Attack）
- 相关密钥攻击（Related-Key Attack）
其他分组密码：
- DES/3DES
- Serpent
- Twofish
- ChaCha20
高级主题：
- 认证加密（Authenticated Encryption）
- 格密码（Lattice-based Cryptography）
- 后量子密码学（Post-Quantum Cryptography）
- 零知识证明（Zero-Knowledge Proofs）
7.3 参考资料
标准文档：
- NIST FIPS 197: Advanced Encryption Standard (AES)
- ISO/IEC 18033-3: Block ciphers
学术论文：
- “Integral Cryptanalysis” by Lars Knudsen
- “The Block Cipher Square” by Joan Daemen et al.
- “Improved Integral Attacks on MISTY and KASUMI” by multiple authors
在线课程：
- OpenSecurityTraining: Cryptanalysis Course
- Coursera: Cryptography I & II by Dan Boneh
- MIT OpenCourseWare: Introduction to Cryptography
书籍推荐：
- “The Design of Rijndael” by Joan Daemen and Vincent Rijmen
- “Understanding Cryptography” by Christof Paar and Jan Pelzl
- “Serious Cryptography” by Jean-Philippe Aumasson
结语
Peoples Square 6是一道精心设计的密码学题目，它通过一个弱化的AES实现，让我们有机会动手实践积分密码分析这一重要的密码分析技术。
通过完成这道题目，我们不仅学习了AES的内部机制，更重要的是理解了：
- 为什么密码算法需要足够的轮数
- 如何通过统计特性来分析密码系统
- 密码学中”安全边界”的重要性
- 正确使用密码学的基本原则
密码学是一门需要极其谨慎的学科。在实际应用中，我们应该始终使用标准的、经过充分验证的密码算法和实现，避免为了性能或其他原因而牺牲安全性。任何看似微小的修改都可能导致灾难性的安全漏洞。
希望本文能够帮助读者深入理解AES和积分密码分析，在密码学的学习道路上更进一步！
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《Peoples Square 6: 4轮AES积分密码分析完整实战》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论