一、题目概述

本题是一道经典的密码学挑战，主要考察对重复密钥XOR加密的分析和破解能力。题目提供了以下文件：

1. challenge.py- 加密程序源码

2. cipher.txt- 加密后的密文（Base64编码）

通过分析加密程序，我们需要从密文中恢复出加密密钥，进而获取flag。

二、加密程序分析

首先查看加密程序的源代码：

from Crypto.Util.strxor import strxor
import base64
import random


def enc(data, key):
    key = (key * (len(data) / len(key) + 1))[:len(data)]
    return strxor(data, key)


poem = open('poem.txt', 'r').read()
flag = "hctf{xxxxxxxxxxx}"

with open('cipher.txt', 'w') as f:
    f.write(base64.b64encode(enc(poem, flag[5:-1])))
    f.close()

2.1 加密流程分析

通过阅读代码，可以明确以下几点：

1. 明文来源：加密的明文是一个诗歌文件（poem.txt）的内容

2. 密钥提取：密钥是flag去掉前5个字符hctf{和最后1个字符}后的内容

3. 密钥扩展：通过重复密钥使其长度与明文相同

4. 加密方式：使用XOR（异或）运算对明文和扩展后的密钥进行加密

5. 输出格式：密文经过Base64编码后保存到文件

2.2 密文信息

查看密文文件，发现是一段Base64编码的字符串。解码后得到1398字节的原始密文。

三、XOR加密原理与安全缺陷

3.1 XOR运算基础

XOR（异或）是一种基本的位运算，其真值表如下：

A | B | A ⊕ B
--|---|------
0 | 0 |  0
0 | 1 |  1
1 | 0 |  1
1 | 1 |  0

XOR运算具有以下重要性质：

1. 可逆性：A ⊕ B = C，则 C ⊕ B = A

2. 交换律：A ⊕ B = B ⊕ A

3. 结合律：(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

4. 自反性：A ⊕ A = 0，A ⊕ 0 = A

这些性质使得XOR非常适合用于加密，因为加密和解密使用相同的操作。

3.2 XOR加密的实现

在本题中，XOR加密的实现方式如下：

假设明文为 P = [P₀, P₁, P₂, ..., Pₙ]，密钥为 K = [K₀, K₁, ..., Kₘ]

加密过程：

• C₀ = P₀ ⊕ K₀

• C₁ = P₁ ⊕ K₁

• ...

• Cₘ = Pₘ ⊕ Kₘ

• Cₘ₊₁ = Pₘ₊₁ ⊕ K₀ （密钥开始重复）

• Cₘ₊₂ = Pₘ₊₂ ⊕ K₁

• ...

通用公式：Cᵢ = Pᵢ ⊕ K[i mod m]

3.3 重复密钥的致命缺陷

重复密钥XOR加密存在严重的安全问题：

问题核心：所有位置满足 i ≡ j (mod m) 的密文字节都使用了相同的密钥字节加密。

这意味着：

• 第0、m、2m、3m...位置的字节都用K₀加密

• 第1、m+1、2m+1、3m+1...位置的字节都用K₁加密

• 以此类推

攻击思路：

1. 如果能确定密钥长度m，就可以将密文按位置分成m组

2. 每组内的所有字节都是用同一个密钥字节加密的

3. 这样就把多字节XOR问题转化为m个独立的单字节XOR问题

4. 单字节XOR可以通过统计分析方法破解

四、密钥长度推测 - Hamming距离分析法

4.1 Hamming距离的定义

Hamming距离是指两个等长字符串对应位置不同字符的个数。在二进制层面，Hamming距离等于两个字节串异或后结果中二进制位为1的个数。

例如：

• 字节A = 0b10101010 (170)

• 字节B = 0b11001100 (204)

• A ⊕ B = 0b01100110

• Hamming距离 = 4（有4个1）

4.2 为什么Hamming距离能推测密钥长度

核心原理基于以下观察：

正确的密钥长度特征：

• 如果猜测的密钥长度正确，按该长度分块后，每个块都是用相同的密钥加密的

• 由于明文（英文文本）具有相似的统计特性，相邻密文块的统计分布也应该相似

• 相似的分布意味着较小的Hamming距离

错误的密钥长度特征：

• 如果猜测的密钥长度错误，分块后每个块使用的密钥字节是错位的

• 这会导致密文块之间的统计分布差异较大

• 较大的差异意味着较大的Hamming距离

4.3 Hamming距离的计算方法

对于每个候选密钥长度KEYSIZE，计算步骤如下：

1. 分块：将密文按KEYSIZE长度分成多个块

   • 块1：C[0:KEYSIZE]

   • 块2：C[KEYSIZE:2×KEYSIZE]

   • 块3：C[2×KEYSIZE:3×KEYSIZE]

   • ...

2. 计算距离：计算相邻块之间的Hamming距离

   • d₁ = hamming(块1, 块2)

   • d₂ = hamming(块2, 块3)

   • d₃ = hamming(块3, 块4)

   • ...

3. 归一化：将总距离除以密钥长度进行归一化

   • 归一化距离 = (d₁ + d₂ + d₃ + ...) / (KEYSIZE × 块数)

   • 归一化是为了消除密钥长度本身对距离的影响

4. 排序：按归一化距离从小到大排序，距离最小的几个长度最有可能是正确的密钥长度

五、单字节密钥破解 - 空格字符攻击

5.1 英文文本的统计特性

英文文本具有明显的统计特性：

1. 空格出现频率高：英文文本中，空格（ASCII 0x20）是出现频率最高的字符之一

2. 字母分布规律：大小写字母（a-z, A-Z）占据文本的主要部分

3. 特殊字符较少：标点符号和其他特殊字符相对较少

这些统计特性为破解单字节XOR提供了基础。

5.2 空格字符攻击的数学原理

假设密文中某个字节C[i]是空格加密后的结果：

• C[i] = 0x20 ⊕ K（空格与密钥异或）

假设密文中另一个字节C[j]是字母加密后的结果：

• C[j] = letter ⊕ K（字母与密钥异或）

将这两个密文字节进行异或：

• C[i] ⊕ C[j] = (0x20 ⊕ K) ⊕ (letter ⊕ K)

• = 0x20 ⊕ K ⊕ letter ⊕ K

• = 0x20 ⊕ letter（密钥K被消除）

• = 字母

关键观察：

• 空格与字母异或得到字母

• 字母与字母异或通常不是字母（大概率是特殊字符或不可打印字符）

5.3 攻击算法

基于上述原理，设计如下算法：

1. 遍历所有密文字节：假设每个字节可能是空格加密后的结果

2. 统计异或结果：将当前字节与其他所有字节异或，统计结果为字母的次数

3. 找出最优候选：异或结果为字母次数最多的字节，最有可能是空格

4. 反推密钥：该字节与0x20异或，即可得到密钥字节

伪代码：

for each byte_i in ciphertext:
    count = 0
    for each byte_j in ciphertext:
        if byte_i XOR byte_j is a letter:
            count++
    if count > max_count:
        max_count = count
        space_position = i

key = ciphertext[space_position] XOR 0x20

六、完整解题流程

6.1 步骤一：读取并解码密文

首先需要读取Base64编码的密文并解码为原始字节：

import base64

text = ''
with open('cipher.txt', 'r') as f:
    for line in f:
        text += line
ciphertext = base64.b64decode(text)

解码后得到1398字节的原始密文数据。

6.2 步骤二：实现辅助函数

需要实现两个核心函数：

1. XOR函数

def bxor(a, b):
    """对两个字节串进行异或运算"""
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])

2. Hamming距离计算函数

def hamming_distance(b1, b2):
    """计算两个字节串的Hamming距离"""
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits

这个函数通过以下步骤计算Hamming距离：

• 对两个字节串进行异或运算

• 统计异或结果中每个字节的二进制表示中1的个数

• 累加得到总的Hamming距离

6.3 步骤三：推测密钥长度

使用Hamming距离分析法推测密钥长度：

normalized_distances = []

for KEYSIZE in range(2, 40):
    # 取前6个块
    b1 = ciphertext[: KEYSIZE]
    b2 = ciphertext[KEYSIZE: KEYSIZE * 2]
    b3 = ciphertext[KEYSIZE * 2: KEYSIZE * 3]
    b4 = ciphertext[KEYSIZE * 3: KEYSIZE * 4]
    b5 = ciphertext[KEYSIZE * 4: KEYSIZE * 5]
    b6 = ciphertext[KEYSIZE * 5: KEYSIZE * 6]
    
    # 计算相邻块之间的Hamming距离
    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) +
        hamming_distance(b5, b6)
    ) / (KEYSIZE * 5)
    
    normalized_distances.append((KEYSIZE, normalized_distance))

    # 按归一化距离排序
    normalized_distances = sorted(normalized_distances, key=lambda x: x[1])

运行后得到的结果（前5个最可能的密钥长度）：

1. 长度=21, 归一化距离=2.5524
2. 长度=10, 归一化距离=2.9400
3. 长度=39, 归一化距离=3.0000
4. 长度=16, 归一化距离=3.0250
5. 长度=19, 归一化距离=3.0316

可以看到，长度为21的归一化距离最小，很可能是正确的密钥长度。

6.4 步骤四：实现单字节密钥破解函数

使用空格字符攻击破解单字节密钥：

import string

def break_single_key_xor(text):
    """使用空格字符攻击破解单字节XOR密钥"""
    possible_space = 0
    max_possible = 0
    letters = string.ascii_letters.encode('ascii')
    
    # 遍历每个字节，假设它可能是空格
    for a in range(len(text)):
        maxpossible = 0
        # 与其他所有字节异或
        for b in range(len(text)):
            if a == b:
                continue
            c = text[a] ^ text[b]
            # 如果异或结果是字母或0，计数加1
            if c in letters or c == 0:
                maxpossible += 1
        # 记录异或结果为字母次数最多的位置
        if maxpossible > max_possible:
            max_possible = maxpossible
            possible_space = a
    
    # 该位置的字节与0x20异或得到密钥
    key = text[possible_space] ^ 0x20
    return chr(key)

函数逻辑说明：

1. 外层循环遍历密文中的每个字节，假设它可能是空格加密后的结果

2. 内层循环将当前字节与其他所有字节进行异或

3. 统计异或结果为字母（或0）的次数

4. 记录异或结果为字母次数最多的字节位置

5. 该位置的字节与0x20异或，得到密钥字节

6.5 步骤五：按密钥位置分组并破解

将密文按密钥长度分组，对每组独立破解：

for KEYSIZE, _ in normalized_distances[:5]:
    # 创建KEYSIZE个空列表，用于存储分组后的字节
    block_bytes = [[] for _ in range(KEYSIZE)]
    
    # 按位置模KEYSIZE分组
    for i, byte in enumerate(ciphertext):
        block_bytes[i % KEYSIZE].append(byte)
    
    # 对每组破解单字节密钥
    keys = ''
    try:
        for bbytes in block_bytes:
            keys += break_single_key_xor(bbytes)
        
        # 重构完整密钥并解密
        key = bytearray(keys * len(ciphertext), "utf-8")
        plaintext = bxor(ciphertext, key)
        
        # 尝试解码为字符串
        s = bytes.decode(plaintext)
        print(f"密钥长度: {KEYSIZE}")
        print(f"密钥: {keys}")
        print(f"明文: {s[:200]}...")
    except Exception:
        continue

分组逻辑说明：

假设密钥长度为21，密文按如下方式分组：

• 组0：第0、21、42、63...个字节（都用K[0]加密）

• 组1：第1、22、43、64...个字节（都用K[1]加密）

• ...

• 组20：第20、41、62、83...个字节（都用K[20]加密）

每组内的字节都是用同一个密钥字节加密的，因此可以独立破解。

七、破解结果与验证

7.1 破解结果

运行完整的破解脚本后，得到以下结果：

密钥长度: 21
密钥: xor_is_interesting!@#

成功破解出密钥为 xor_is_interesting!@#，长度为21字节。

7.2 解密验证

使用破解出的密钥对密文进行解密：

from Crypto.Util.strxor import strxor

key = "xor_is_interesting!@#"
key_extended = (key * (len(ciphertext) // len(key) + 1))[:len(ciphertext)]
plaintext = strxor(ciphertext, key_extended.encode())
print(plaintext.decode())

解密后得到完整的明文（泰戈尔的诗歌《生如夏花》英文版）：

Life, thin and light-off time and time again
Frivolous tireless
one
I heard the echo, from the valleys and the heart
Open to the lonely soul of sickle harvesting
Repeat outrightly, but also repeat the well-being of
Eventually swaying in the desert oasis
I believe I am
Born as the bright summer flowers
Do not withered undefeated fiery demon rule
Heart rate and breathing to bear the load of the cumbersome
Bored
...

明文完全可读，验证了破解的正确性。

7.3 获取Flag

根据加密程序的逻辑，flag的格式为 hctf{密钥}，因此：

Flag: hctf{xor_is_interesting!@#}

八、攻击成功的关键因素分析

8.1 密钥重复使用

这是本题最致命的安全缺陷。密钥被循环重复使用，导致：

• 相同位置（模密钥长度）的字节使用相同的密钥字节

• 可以将多字节XOR问题分解为多个单字节XOR问题

• 大大降低了破解难度

8.2 明文的可预测性

英文文本具有明显的统计特性：

• 空格出现频率高且规律

• 字母分布符合统计规律

• 这些特性为统计分析攻击提供了基础

8.3 密文长度充足

密文长度为1398字节，对于长度21的密钥：

• 每个密钥字节加密了约66个明文字节

• 样本量足够大，统计分析方法才能有效

• 如果密文太短，统计特性不明显，破解难度会增加

8.4 Hamming距离的有效性

Hamming距离分析法能够准确推测密钥长度：

• 正确的密钥长度归一化距离为2.5524

• 其他候选长度的距离都明显更大

• 这为后续破解提供了正确的方向

九、安全启示与防御建议

9.1 XOR加密的局限性

通过本题可以看到，简单的XOR加密存在严重的安全问题：

1. 密钥重用是致命的：即使密钥较长，重复使用仍然可以被破解

2. 无法抵抗统计分析：明文的统计特性会泄露到密文中

3. 不适合实际应用：XOR加密只适合教学和CTF，不应用于实际数据保护

9.2 正确的加密实践

在实际应用中，应遵循以下安全原则：

1. 使用标准加密算法

• 使用AES、ChaCha20等经过广泛验证的加密算法

• 这些算法经过多年的密码学分析，安全性有保障

• 不要自己设计加密算法

2. 避免密钥重用

• 如果必须使用XOR，应使用流密码（如ChaCha20）

• 流密码生成的密钥流不重复，每个字节使用不同的密钥

• 或者使用一次一密（OTP），密钥长度等于明文长度且只使用一次

3. 使用认证加密

• 使用AEAD（Authenticated Encryption with Associated Data）模式

• 如AES-GCM、ChaCha20-Poly1305等

• 同时提供机密性和完整性保护，防止密文被篡改

4. 正确的密钥管理

• 使用足够长的随机密钥（至少128位）

• 密钥应通过安全的密钥派生函数（KDF）生成

• 定期更换密钥，不要长期使用同一密钥

5. 添加随机性

• 使用初始化向量（IV）或随机数（Nonce）

• 即使加密相同的明文，每次也会产生不同的密文

• 破坏明文的统计特性

十、技术知识点总结

10.1 密码学知识

通过本题学习到的密码学知识：

1. XOR运算的性质：理解可逆性、交换律、结合律等基本性质

2. 流密码的概念：重复密钥XOR本质上是一种简单的流密码

3. 密钥重用的危害：理解为什么密钥不能重复使用

4. 统计分析方法：利用明文的统计特性进行密码分析

10.2 密码分析技术

掌握的密码分析技术：

1. Hamming距离分析：用于推测重复密钥的长度

2. 频率分析：利用字符出现频率进行攻击

3. 空格字符攻击：针对英文文本的特定攻击方法

4. 分组转化技巧：将复杂问题转化为简单问题

10.3 编程实现能力

提升的编程技能：

1. Base64编解码：处理常见的编码格式

2. 字节串操作：Python中的字节串处理技巧

3. 算法实现：将理论攻击方法转化为实际代码

4. 调试与优化：通过多个候选方案提高成功率

十一、完整解题脚本

以下是完整的解题脚本代码：

import base64
import string


def bxor(a, b):
    """对两个字节串进行异或运算"""
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])


def hamming_distance(b1, b2):
    """计算两个字节串的Hamming距离"""
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits


def break_single_key_xor(text):
    """使用空格字符攻击破解单字节XOR密钥"""
    possible_space = 0
    max_possible = 0
    letters = string.ascii_letters.encode('ascii')
    
    for a in range(len(text)):
        maxpossible = 0
        for b in range(len(text)):
            if a == b:
                continue
            c = text[a] ^ text[b]
            if c in letters or c == 0:
                maxpossible += 1
        if maxpossible > max_possible:
            max_possible = maxpossible
            possible_space = a
    
    key = text[possible_space] ^ 0x20
    return chr(key)


# 主程序
text = ''
with open('cipher.txt', 'r') as f:
    for line in f:
        text += line
ciphertext = base64.b64decode(text)

# 推测密钥长度
normalized_distances = []
for KEYSIZE in range(2, 40):
    b1 = ciphertext[: KEYSIZE]
    b2 = ciphertext[KEYSIZE: KEYSIZE * 2]
    b3 = ciphertext[KEYSIZE * 2: KEYSIZE * 3]
    b4 = ciphertext[KEYSIZE * 3: KEYSIZE * 4]
    b5 = ciphertext[KEYSIZE * 4: KEYSIZE * 5]
    b6 = ciphertext[KEYSIZE * 5: KEYSIZE * 6]

    normalized_distance = float(
        hamming_distance(b1, b2) + hamming_distance(b2, b3) +
        hamming_distance(b3, b4) + hamming_distance(b4, b5) +
        hamming_distance(b5, b6)
    ) / (KEYSIZE * 5)
    normalized_distances.append((KEYSIZE, normalized_distance))

normalized_distances = sorted(normalized_distances, key=lambda x: x[1])

# 尝试破解
for KEYSIZE, _ in normalized_distances[:5]:
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(ciphertext):
        block_bytes[i % KEYSIZE].append(byte)

    keys = ''
    try:
        for bbytes in block_bytes:
            keys += break_single_key_xor(bbytes)
        key = bytearray(keys * len(ciphertext), "utf-8")
        plaintext = bxor(ciphertext, key)
        s = bytes.decode(plaintext)
        print(f"密钥长度: {KEYSIZE}")
        print(f"密钥: {keys}")
        print(f"Flag: hctf{{{keys}}}")
    except Exception:
        continue

十二、总结

本题是一道经典的密码学入门题目，通过对重复密钥XOR加密的完整分析和破解，我们深入理解了以下核心内容：

12.1 攻击方法论

完整的攻击流程包括：

1. 分析加密算法：理解加密实现方式，找出潜在弱点

2. 推测密钥长度：使用Hamming距离分析法确定密钥长度

3. 问题分解：将多字节XOR转化为多个单字节XOR问题

4. 统计分析攻击：利用明文的统计特性破解单字节密钥

5. 验证结果：解密密文并验证明文的可读性

12.2 实战价值

这道题目对于CTF初学者和安全研究人员具有重要的学习价值：

1. 理论与实践结合：将密码学理论转化为实际的攻击代码

2. 培养分析思维：学会从加密算法中寻找安全漏洞

3. 掌握经典技术：Hamming距离分析和频率分析是密码分析的基础技术

4. 安全意识提升：理解简单加密的危险性，认识到使用标准算法的重要性

12.3 延伸思考

在实际的安全工作中，我们应该：

1. 永远不要自己设计加密算法：使用经过验证的标准算法（AES、ChaCha20等）

2. 密钥管理至关重要：密钥的生成、存储、分发都需要严格的安全措施

3. 加密不等于安全：还需要考虑完整性、认证、密钥管理等多个方面

4. 持续学习：密码学是一个不断发展的领域，需要持续关注新的攻击技术和防御方法

通过本题的学习，希望能够帮助大家建立正确的密码学安全观念，在今后的CTF比赛和实际安全工作中灵活运用这些知识和技术。

参考资源：

• 密码学基础理论

• XOR加密与流密码

• 频率分析与统计攻击

• Python密码学编程