polarisCTF Crypto 方向全解教学文档

1. ez_login

1.1 题目概览

这是一个Web应用登录绕过与CBC位翻转攻击结合的密码学题目。应用初始化用户表为 {"admin": ADMIN_PASS}，禁止注册，flag只能通过admin身份获取。

1.2 漏洞分析

1.2.1 登录绕过漏洞
登录判断逻辑存在缺陷：

if USERS.get(user) == pw:  # 漏洞点
    session = create_session(user)

当表单字段user和pw完全省略时，request.form.get(...)返回None，判断变为：

USERS.get(None) == None

由于USERS字典中没有None键，USERS.get(None)也返回None，等式成立，实现无凭证登录。

1.2.2 会话机制分析
create_session函数将user=<username>格式的文本进行AES-CBC加密，将iv + ct的十六进制字符串作为cookie。当使用空表单登录时，实际加密的明文为user=None。

1.3 CBC位翻转攻击

1.3.1 攻击原理
CBC模式首块满足：P₁ = D(C₁) ⊕ IV
其中：

• P₁：第一块明文
• C₁：第一块密文
• IV：初始化向量
• D()：分组解密函数

当C₁不变时，通过修改IV可以控制解密后的明文P₁。

1.3.2 具体构造
目标：将user=None改为user=admin
原始明文块：user=None\x0c\x0c...\x0c（16字节）
目标明文块：user=admin\x08\x08...\x08（16字节）

计算新IV：

IV_new = IV_original ⊕ P_original ⊕ P_target
       = IV_original ⊕ "user=None..." ⊕ "user=admin..."

1.3.3 攻击步骤

1. 使用空表单登录，获取合法cookie（明文为user=None）
2. 提取原始IV和密文C₁
3. 计算IV_new = IV_original ⊕ ("user=None" ⊕ "user=admin")
4. 将IV_new + C₁作为新cookie提交
5. 服务端解密后得到user=admin，获得flag

2. ECC（奇异椭圆曲线）

2.1 题目设定

给定椭圆曲线方程：y² + cy = x³ + bx² + dx + e，其中a=0。已知基点G和点P = [m]G，需要恢复消息整数m。

2.2 曲线奇异化分析

2.2.1 方程变换
令Y = y + c/2，原方程变为：

Y² = x³ + bx² + dx + e + c²/4

代入题目参数后，右边可化为完全立方形式。设r = -b/3，可得：

d = 3r²
e + c²/4 = -r³

因此曲线方程为：Y² = (x-r)³

2.2.2 奇异曲线特性
这不是普通椭圆曲线，而是尖点奇异曲线。奇异点处的群结构退化，离散对数问题变得简单。

2.3 参数化表示

2.3.1 参数化方法
对非奇异点，令u = (x-r)/Y，由Y² = (x-r)³可得：

x-r = u⁻², Y = u⁻³

回代得：

x = r + u⁻²
y = u⁻³ - c/2

2.3.2 群运算退化
将参数化表示代入题目实现的加法公式，化简得：

P(u₁) + P(u₂) = P(u₁ + u₂)

标量乘法退化为：

[m]P(u) = P(mu)

群结构从椭圆曲线群退化为有限域上的加法群。

2.4 消息恢复

由P = [m]G，在参数表示下：

u(P) = m · u(G) (mod p)

因此：

m = u(P) · u(G)⁻¹ (mod p)

将G和P坐标代入参数化公式计算u(G)和u(P)，即可直接求出m，无需解离散对数。

3. truck（MD5三碰撞）

3.1 题目结构

进行10轮交互，每轮输入9段十六进制数据A-I，通过三层MD5校验：

1. 第一层：md5(A) = md5(B) = md5(C)
2. 第二层：md5(ha + D) = md5(hb + E) = md5(hc + F)
   • 其中ha = md5(A), hb = md5(B), hc = md5(C)
3. 第三层：md5(hd + G) = md5(he + H) = md5(hf + I)
   • 其中hd = md5(ha + D), he = md5(hb + E), hf = md5(hc + F)

附加约束：同一轮9段输入两两不同，10轮间不能复用任何消息。

3.2 攻击思路

3.2.1 关键观察
第一层通过后，ha = hb = hc，第二层变为同一前缀下的三碰撞问题。
第二层通过后，hd = he = hf，第三层也变为同一前缀下的三碰撞问题。

3.2.2 三碰撞构造方法
使用identical prefix collision技术：

1. 在固定前缀prefix下，生成二碰撞(m0, m1)，满足md5(prefix + m0) = md5(prefix + m1)
2. 以prefix + m0为新前缀，再生成二碰撞(n0, n1)，满足md5(prefix + m0 + n0) = md5(prefix + m0 + n1)
3. 构造第三条消息：prefix + m1 + n0
   结果得到三条不同消息，MD5值相同。

3.2.3 分层应用

• 第一层：空前缀，直接生成A、B、C
• 第二层：以ha为前缀，生成D、E、F
• 第三层：以hd为前缀，生成G、H、I

3.3 工程实现细节

3.3.1 防重复设计
在碰撞数据中嵌入轮次和层编号，确保不同轮次、不同层的碰撞上下文不同，避免数据重复。

3.3.2 数据裁剪
碰撞工具生成完整消息，但题目只需提交后缀。需要从碰撞结果中裁掉共同前缀，只保留可变部分。

3.3.3 验证流程
构造完成后需验证：

1. 同一轮内9段输入互异
2. 10轮间无重复数据
3. 满足所有MD5等式

4. 神秘学（RSA与三次多项式）

4.1 题目设定

RSA参数：n = pq，e = c⁻¹ mod φ(n)，密文cipher = mᵉ mod n。
多项式：f(x) = x³ - ax² + bx - c - kn，仅给出x₁处的导数值f'(x₁)。

目标：恢复c，解密m = cipherᶜ mod n。

4.2 系数恢复

4.2.1 导数信息利用

f'(x) = 3x² - 2ax + b
f'(x₁) = deriv1_num

令T = 3x₁² - deriv1_num = 2a x₁ - b

由于x₁约511位，a、b约120位，2a x₁占主导地位，b为小修正项。因此：

a ≈ ceil(T / (2x₁))

具体计算：a = (T + 2*x₁ - 1) // (2*x₁)

4.2.2 恢复b
由T = 2a x₁ - b得：b = 2a x₁ - T

4.3 密钥恢复

4.3.1 枚举策略
已知k = getPrime(8)，即8位素数（2-255间约54个）。
由f(x₁) = 0得：

c = x₁³ - a x₁² + b x₁ - k n

枚举所有8位素数k：

1. 计算候选c = x₁³ - a x₁² + b x₁ - k n
2. 计算m = cipherᶜ mod n
3. 检查m是否以xmctf{开头

4.3.2 复杂度分析

• 直接枚举c：不可行（搜索空间过大）
• 枚举k：约54次模幂运算，可接受

4.4 实现要点

1. 恢复a时使用整除向上取整
2. 使用flag前缀xmctf{进行精确筛选
3. 无需分解n，无需解离散对数

5. RSA_LCG

5.1 题目参数

已知：

• N, e
• a
• dᵉ mod N，其中d = b - a
• x₁ᵉ mod N, x₂ᵉ mod N

递推关系：

x₀ = secret
x₁ = (a * x₀ + b) mod N
x₂ = (a * x₁ + b) mod N

目标：4秒内恢复64字节secret。

5.2 攻击链

5.2.1 恢复d
记：

A = dᵉ mod N
B = x₁ᵉ mod N
C = x₂ᵉ mod N

由x₂ = a x₁ + b = a x₁ + (a + d)和x₁ = a x₀ + (a + d)，构造u = x₁ - 1，v = x₂ - 1，有：

v - u = a(x₁ - x₀) = a( (a-1)x₀ + d )

利用uᵉ = B和vᵉ = C，通过Newton identities构造多项式Q(T)，使得Q(T(d)) = 0，其中T(D) = D - A。

5.2.2 恢复x₁
已知d后，b = a + d mod N。x₁满足：

x₁ᵉ = B mod N
(a x₀ + b)ᵉ = B mod N

使用Franklin-Reiter相关消息攻击，计算：

gcd(Xᵉ - B, (aX + b)ᵉ - C)

得到线性因子X - x₁，提取x₁。

5.2.3 恢复secret
由x₁ = a x₀ + b mod N，考虑进位t ∈ {0,1}：

x₁ = a x₀ + b - tN
x₀ = (x₁ - b + tN) / a

枚举t，验证x₀长度和dᵉ、x₁ᵉ、x₂ᵉ。

5.3 性能优化

5.3.1 瓶颈分析

1. 构造Q(T)：大量2048位模运算
2. 多项式复合：Q(T(D)) mod (Dᵉ - A)
3. 多项式GCD：复合模数N下无法直接使用FLINT的GCD

5.3.2 优化措施

1. 使用gmpy2加速大整数模运算
2. 实现分块多项式复合（baby-step/giant-step）：
   • 预处理1, T, T², ..., T^(B-1)
   • 将Q系数分块，每块用低次幂线性组合
   • 用Y = Tᴮ进行Horner合并
3. 手动实现多项式余式链，避免复合模数下的GCD限制

5.3.3 时间分布

• 准备阶段：0.103s
• 构造Q(T)：0.557s
• 多项式复合：0.555s
• GCD求d：0.187s
• GCD求x₁：0.199s
• 恢复secret：≈0s
• 总耗时：1.602s

6. Whisper Line

6.1 题目概述

包含APK（Android应用）和PCAP（网络流量）。需要：

1. 从APK还原聊天协议和加密逻辑
2. 从PCAP提取密文
3. 分解RSA模数获取私钥
4. 解密获取flag

6.2 协议分析

6.2.1 Java层分析

• 主类：com.example.polarisctf.MainActivity
• 关键字符串：HELLO、MSG、loadLibrary
• 协议：文本行协议，十六进制编码
  • 连接：HELLO <name>
  • 消息：MSG <to> <cipher>

6.2.2 JNI层分析
libu.so中的Java_com_example_polarisctf_Z_x函数：

1. 从常量加载256字节，异或0xA7得到RSA模数n
2. 指数e = 65537
3. 加密：cipher = plaintextᵉ mod n
4. 输出：字节反转后转十六进制

加密伪代码：

def encrypt(plaintext):
    m = int.from_bytes(plaintext, 'big')
    if m >= n:
        m %= n
    c = pow(m, 65537, n)
    # 移除前导零，字节反转
    c_bytes = c.to_bytes((c.bit_length()+7)//8, 'big').lstrip(b'\x00')
    return c_bytes[::-1].hex()

6.3 流量解密

6.3.1 流量提取
从PCAP提取TCP流，十六进制解码后得到：

HELLO Adic
HELLO December
MSG December 7b5a2b...（密文）
...

6.3.2 解密流程

1. 提取MSG行的密文字段
2. 十六进制解码
3. 字节反转（抵消加密时的反转）
4. RSA解密：m = cᵈ mod n
5. 解码得到明文

解密对话：

• Adic: I think the flag is pol...
• December: ...arisCTF{wh1sp3r_1in3_...}
• 拼接得：polarisCTF{wh1sp3r_1in3_c4n_b3_h34rd}

6.4 RSA模数分解

6.4.1 关键线索
用户名Adic和December暗示12-adic表示。将模数n转换为12进制，发现：

• 所有位只有0-4
• 高位极其稀疏
• 类似"乘法几乎无进位"的结构

6.4.2 多项式分解
设x = 12，将因子表示为：

p = a(x) + x²⁸⁵
q = b(x) + x²⁸⁵

其中a(x)次数为39，系数很小。

展开n = pq：

n = (x²⁸⁵ + a(x))(x²⁸⁵ + b(x))
  = x⁵⁷⁰ + (a(x) + b(x))x²⁸⁵ + a(x)b(x)

由于a(x)次数低，a(x)x²⁸⁵贡献在[285, 324]位，a(x)b(x)最高到319次。因此325位以上的高位完全来自b(x)x²⁸⁵，可直接从n的高位读取b(x)。

6.4.3 具体分解

1. 从n的12进制表示提取高位得到q
2. 计算p = n // q
3. 计算φ = (p-1)(q-1)
4. 计算d = e⁻¹ mod φ

恢复的因子：

p = 12^285 + ...
q = 12^285 + ...

7. ez_random

7.1 题目机制

服务端使用Python random模块，option 1和option 2使用相同种子SEED。

option 1：生成36组(getrandbits(988), random_prime(...))，输出：

• Key Part A：36个988位随机数（顺序打乱）
• Key Part B0：36个素数
• Key Part B1：36个尝试次数

option 2：重新运行相同随机链，最后计算key = SHA256(str(getrandbits(256)).encode())，用AES-ECB加密flag。

7.2 攻击思路

7.2.1 顺序恢复
利用random_prime的异常机制：当参数为1时抛出ValueError。
对于第k轮，发送：

(get_limit(k) - 1) XOR candidate

如果candidate等于当前getrandbits(988)，则random_prime(1)异常，否则继续。

7.2.2 状态恢复挑战
不能仅用36个988位输出恢复MT19937状态，因为：

• random_prime消耗额外随机数
• 需要B0（成功素数）和B1（尝试次数）来补全随机流

7.2.3 完整状态恢复

1. 将988位输出拆分为31个32位块（最后一块高28位）
2. 为每个B0[i]添加top31观测
3. 考虑第10轮特殊上界，枚举额外消耗extra10 ∈ [0,7]
4. 建立MT19937状态方程，求解

7.3 实现细节

7.3.1 在线部分

• 通过异常oracle恢复Key Part A的顺序
• 获取密文
• 保守并发，避免超时

7.3.2 离线部分

• 输入：有序A、B0、B1
• 拆分为full32、top28、top31观测
• 构建MT19937约束系统
• 恢复状态，预测getrandbits(256)

7.3.3 密钥派生

next256 = 285349836549201...（恢复值）
key = SHA256(str(next256).encode())
flag = AES_ECB_decrypt(cipher, key)

8. ocean（LFSR组合）

8.1 题目设定

• seed、mask1、mask2均为64位
• seed最高位为1
• 两个LFSR：
  • lfsr1：每轮都更新
  • lfsr2：仅在lfsr1()输出为1时更新
• 输出64位output
• enc = AES_ECB(md5(str(seed)), secret)

8.2 线性关系分析

8.2.1 线性表示

• cₜ = lfsr1第t轮输出，是seed的GF(2)线性函数
• zⱼ = lfsr2更新j次后的输出位，也是seed的线性函数
• 实际输出：output[t] = z_{sum(c₀...cₜ)}

8.2.2 约束建立

1. 预计算64个cₜ的线性表达式
2. 预计算65个zⱼ的线性表达式（j=0..64）
3. 用SAT变量表示seed，添加seed最高位为1的约束
4. 用XOR约束表示cₜ和zⱼ的线性关系

8.3 优化策略

8.3.1 翻转约束
由output[t] = output[t-1] ⊕ cₜ得：
如果output[t] != output[t-1]，则cₜ = 1
这能直接固定大量控制位。

8.3.2 计数器建模
使用one-hot计数器cnt[t][j]表示"第t轮后lfsr2更新了j次"。
约束：如果cnt[t][j] = 1，则zⱼ = output[t]。

8.3.3 求解策略

1. 使用pycryptosat进行增量求解
2. 每次求解得到一个seed候选
3. 用AES验证，失败则添加blocking clause继续求解
4. 只枚举前120个候选（基于性能考虑）

8.3.4 实例选择
不同实例的求解难度不同，选择输出翻转次数多的实例（约束更强）。
阈值：min_flips = 26，跳过翻转数低的实例。

8.4 求解流程

1. 连接服务，获取output
2. 计算翻转次数，低于阈值则重连
3. 建立SAT模型，添加线性约束和翻转约束
4. 增量求解，枚举候选seed
5. 验证seed是否正确（检查最高位，AES解密）
6. 成功则输出flag

---

总结

本文档详细分析了polarisCTF中Crypto方向的8道题目，涵盖：

1. Web登录绕过与CBC位翻转
2. 奇异椭圆曲线的参数化解法
3. MD5三碰撞的构造与实现
4. RSA与三次多项式的结合攻击
5. 基于LCG的RSA相关消息攻击
6. 协议逆向与特殊RSA模数分解
7. Python随机数生成器的状态恢复
8. LFSR组合的SAT求解

每道题目的关键点、攻击思路和实现细节均已涵盖，可作为密码学攻防教学参考。