PolarisCTF2026

Above#

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

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

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

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

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

app.py

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)

似乎是非预期

ADMIN_PASS = os.getenv("ADMIN_PASS", "admin123")
FLAG = os.getenv("FLAG", "XMCTF{xxxxxx}")

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

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

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

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末尾字节和长度的关系可实现中间态的逐字节恢复

固定一个目标密文块 $C_i$
可控它前一块 $C_{i-1}$ ，或者首块时可控 IV
因为 $P_i = D_K(C_i) \oplus C_{i-1}$
不断修改 $C_{i-1}$ 的最后一个字节，直到 unpad 成功
一旦成功，说明最后一字节已经变成合法 padding，比如 0x01
于是可以推出 $D_K(C_i)$ 该字节的值
再继续做倒数第二字节，让末尾变成 0x02 0x02
一直倒推完整个块拿到 $I_i = D_K(C_i)$
再构造 $C'_{i-1} = I_i \oplus P_i$ 伪造admin token

预期Oracle打法exp

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

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)

给出了一个曲线

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

对应方程

y^2 + cy = x^3 + bx^2 + dx + e

然后需要解ECDLP

P=m\cdot G

实际上把曲线的运算代码喂给LLM 让它审计曲线的性质它会做变形

2y+c\rightarrow Y

Y^2 = 4x^3 + 4bx^2 + 4dx + 4e + c^2=f(x)

发现 $f$ 是可以因式分解为

f(x) = 4(x - r)^3

从而可换元得到

Y^2=4X^3

拷打了一下LLM 给出了这种曲线的处理手法

做换元

u = \frac{2X}{Y}

u^2 = \frac{4X^2}{Y^2}=\frac{1}{X}

故而

X=\frac{1}{u^2}\;\;Y=\frac{2}{u^3}

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

椭圆曲线的加法定义为

P_1 + P_2 + P_3' = \mathcal{O}

显式设出来直线

Y = kX + b

代入式子

\frac{2}{u^3} = k \left(\frac{1}{u^2}\right) + b

整理

bu^3 - ku + 2 = 0

由三次方程韦达定理必定有

u_1+u_2=-u_3

和这边的点加公式是完全一个代数结构的也就是说

u(P_1 + P_2) = u_1 + u_2 = u(P_1) + u(P_2)

我们把 $P$ 的坐标代入 $u$ 的运算实现了把DLP映射到一个简洁的加法

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

神秘学#

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都会认为不可解

因为给出多项式

f(x) = x^3 - a x^2 + b x - c - k n

求导后

f'(x) = 3x^2 - 2ax + b

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

简要思路就是爆破 $k$ 利用 $a\;b$ 和 $x$ 的数量级差异恢复 $a\;b$ 再假设零点关系恢复 $c$ 解密RSA

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

sda#

task.py

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
"""

给出了 $(A_i,B_i)$ 三组参数以及约束

B_i x_i^2 - \varphi(A_i) y^2 = z_i

其中

x_i^2 < A^\delta,\quad y^2 < A^\delta

truck#

非常简洁的一道哈希题

chal.py

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}')

三层验证

输入 A, B, C，要求： md5(A) = md5(B) = md5(C)
输入 D, E, F，要求： md5(md5(A) || D) = md5(md5(B) || E) = md5(md5(C) || F)
输入 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进行攻击快速实现对于任何前缀 $P$ 找到两块不同的 $S_i$ 满足

$MD5(P \parallel S_0) = MD5(P \parallel S_1)$ 这样就可以快速的通过第一次校验

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

先用 fastcoll 生成 $S_0$ 和 $S_1$ ，使得 $MD5(S_0) = MD5(S_1) = H_1$
再把 $H_1$ 作为新的前缀，再跑一次 fastcoll，生成 $T_0$ 和 $T_1$ ，使得 $MD5(H_1 \parallel T_0) = MD5(H_1 \parallel T_1)$

得到以下碰撞

$S_0 \parallel T_0$ $S_0 \parallel T_1$ $S_1 \parallel T_0$ $S_1 \parallel T_1$

所以说对于第一层令 $P$ 为"" 走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#

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的两次递推输出 $s_{i+1} \equiv a s_i + b \pmod{N}$

c_i = s_i^e \bmod N

这里的问题在于 $N$ 是不可分解的强合数故而LCG的线性输出会被模幂进行混淆

然后看向题目给出的hint

\text{leak} = \left(a,\ (b-a)^e \bmod N\right)

可以换元令 $t=b-a$ 然后代入已知的式子

s_1 \equiv a s_0 + a + t \equiv a(s_0 + 1) + t \pmod{N}

s_2 \equiv a s_1 + a + t \pmod{N}

优化一下#

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

我们最终求 $X$ 的根实际上是求 $\gcd(R(X), X^e - C_1)$ 由辗转相除的性质

$\gcd(A, B) = \gcd(A \bmod B, B)$

那么本质上只需求 $R'(X) = R(X) \bmod (X^e - C_1)$ 再做gcd也能得到我们想要的结果

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

LLM给出了具体的优化思路

注意到多项式 $f_3$ 实际上也很特殊

f_3(X,Y) = (Y + K)^e - C_2

再做结式

R(X)=\operatorname{Res}_Y\big((Y+K)^e-C_2,\ Y^e-L\big)

我们的目标结式可以看成关于 $K$ 也就是 $X$ 的单变量函数接下来LLM的关于扩域等的说明感觉不讲人话以我的理解就是

现在有两个多项式

f_2(Y) = Y^e-L

f_3(X,Y) = (Y + K)^e - C_2

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

对于这个等式

C_2^{e}=(Y+K)^{e^e}

这下子关于 $Y$ 就都是 $e$ 以上的次幂了完全可以用 $L$ 的幂次代替那么消元好剩下来关于 $K$ 的幂次很高但是都可以换元 $G=K^e$ 有

a_1G_1+\cdots+a_eG^e+b_1L+b_2L^2+\cdots+b_eL^e+S=C_2^e

太棒了我们得到了一个关于 $G$ 的263次多项式那直接插值就好了这一步就可以做了

恢复一个 $X=s_1$ 那么再由退化的 $f_3$ 和 $f_1$ 做GCD即可恢复 $t$

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

Ocean#

chal.py

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在 $\mathbf{GF(2)}$ 上可以看成关于初始向量seed的线性变换由于反馈多项式mask是已知的那么转移矩阵可以直接写出也就是LFSR的每一步都可以看成 $x$ 的矩阵乘法

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

但是对于LFSR2的输出如果我们观察到相邻的两位不一样（比如 $z_{t-1} = 0$ ，但 $z_t = 1$ ）说明LFSR2肯定更新了状态

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

那么，然后呢？#

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

优化细节#

翻转剪枝#

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

区间限制#

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

11111011111111011010110100000111011100000001001010001110110110

bash

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

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

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

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

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

线性结构不变#

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

比如假设确定 $\Delta$ 后 $1001,\ 0110$ 都是满足条件的那么始终都会满足 $c_1 \oplus c_2 = 1$ 与 $c_1 \oplus c_4 = 0$ 从这里又建立了约束

代码中就是每次猜测剪枝约束完 $\Delta$ 后把
$\left\langle \bigoplus_{i=0}^{L-1} rows1[s+i+1], x \right\rangle = \Delta \bmod 2$
压入约束系统

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

前缀约束#

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

\langle rows2[m+1], x \rangle = \langle rows2[m+2], x \rangle = \text{const}

防止搜索过深

题目本身的验证解#

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

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

ez_random#

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

task.py

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

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组数据也就是 $(a_k, b_k)=\Bigl(\texttt{getrandbits}(988),\ \texttt{random\_prime}(\texttt{get\_limit}(k))\Bigr),\quad k=1,\dots,36$ 这里魔改的random_prime会返回 $(p_k, c_k)$ ，即最终命中的素数和命中前的尝试次数但是32个块 $a_k$ 是经过shuffle的
交互选2 使用SEED起一个一样的随机流然后进行36次请求输入 $x_k$ 进行 $\texttt{random\_prime}\bigl(x_k \oplus (\texttt{getrandbits}(988) \oplus \texttt{get\_limit}(k))\bigr)$ 然后用随机流生成256bits的随机数 AES加密flag给你

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

魔改#

local_misc中关键魔改在

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 $(a_k, b_k)=\Bigl(\texttt{getrandbits}(988),\ \texttt{random\_prime}(\texttt{get\_limit}(k))\Bigr),\quad k=1,\dots,36$
交互2 $\texttt{random\_prime}\bigl(x_k \oplus (\texttt{getrandbits}(988) \oplus \texttt{get\_limit}(k))\bigr)$

我们先连一次靶机选1 取得36组打乱的 $a_i$ 然后直接断开重连这次选2 我们知道此时生成的988bits的随机数一定是 $a_0^{'}$ 但是它被shuffle了问题不大我们只有36组可能完全可以每次都试一下用 $a_i \oplus \texttt{get\_limit}(k)$ 唯有碰撞成功的时候会成功调用 $\texttt{random\_prime}\bigl(0\bigr)$ 而

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

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

Part2#

接下来就很清晰了我们知道了一个MT流中连续很多组输出数据量而言 $988\times36=35568\;\gt19968$ 但是每次生成随机数的时候都进行了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进行加密通信但是只给了公钥 $(e,N)$ $N$ 是2042bits 但是赛中完全没有分解的思路

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

n = 1359289594911861706114410263039030781889501874535854365263922081700238941971104298775704733565166223684142297360239921080802503206559783832007855750334958326368538063619171609885459927586035302195455632768752776216956554963499448005445126927786242177611054827389185330231903625073278897391670581843035646913248732183168634640757720768465749375619368398241192399373901594871829578828976563808877743744957547821735170186252185438724528024345696208656639600908162373375395068724897936084947703562847353279296559280237330305142321357271051046159817216535038453709580872952011626071015235951428711736008848437349560705229

bash

转12进制后会得到

1000010000000000000000000000000000000000000002000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000021122233242421223112412143212234212443034210112244444040402042204402242402044404442022224444404040204220440224240204440444202200000000000000000000000000000000000000001122222020201021102201121201022202221011000000000000000000000000000000000000000022444440404020422044022424020444044420221122222020201021102201121201022202221011

bash

呈现了非常不随机的结构

我们按照12进制展开 $N = \sum_{i=0}^{k} a_i 12^i$ 这里的 $a_i$ 就是已知的非常有规律的小量那么 $p\;q$ 也存在12进制下的展开

p = \sum_{i=0}^{k} b_i 12^i

q = \sum_{i=0}^{k} c_i 12^i

设 $F(x) = \sum_{i=0}^{k} a_i x^i$

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

B(x)=(x^{285}+x^{280}+2x^{240}+2x^{200}+x^{120}+2x^{40}+1) \;|\; F(x)

随后完成分解解密RSA

Above#

Login#

ECC#

神秘学#

sda#

truck#

RSA_LCG#

代数结构梳理#

相关信息攻击？#

优化一下#

Ocean#

系统总览#

代数结构分析#

那么，然后呢？#

优化细节#

翻转剪枝#

区间限制#

线性结构不变#

前缀约束#

题目本身的验证解#

ez_random#

结构梳理#

魔改#

漏洞利用#

Part1#

Part2#

Part3#

*Wispher_Line#