osu!gamingCTF 2025 문제풀이

# -*- coding: utf-8 -*-
# HIT/MISS 스케줄을 계산하는 레퍼런스 구현
# - 상태는 128바이트
# - M: out[p] = in[p-1] XOR in[p+1] (경계 밖은 0)
# - HIT: 위치 (t & 0x7F)에 c_t = (t*0x1B + 0x37) & 0xFF 를 XOR한 뒤 M
# - MISS: M 만 수행
# - 최종 상태를 목표 바이트열(Target)과 같게 만드는 h_t ∈ {0,1} 시퀀스를 Gaussian 소거로 풂 (GF(2))

from typing import List, Tuple

L = 128  # bytes
MASK_128 = (1 << L) - 1

# ---------- 비트-평면 표현 도우미 ----------

def bytes_to_planes(bs: bytes) -> List[int]:
    """128바이트 -> 8개 비트평면(각 128비트 int). plane[b]의 bit p는 bs[p]의 b번째 비트."""
    assert len(bs) == L
    planes = [0]*8
    for p, val in enumerate(bs):
        for b in range(8):
            if (val >> b) & 1:
                planes[b] |= (1 << p)
    return planes

def planes_to_bytes(planes: List[int]) -> bytes:
    """8개 비트평면 -> 128바이트"""
    out = bytearray(L)
    for p in range(L):
        v = 0
        for b in range(8):
            if (planes[b] >> p) & 1:
                v |= (1 << b)
        out[p] = v & 0xFF
    return bytes(out)

def pack_planes_to_bigint(planes: List[int]) -> int:
    """8개 평면을 1024비트 정수로 패킹(plane 0이 낮은 비트 구간). 열(column) 벡터로 취급한다."""
    big = 0
    for b in range(8):
        big ^= (planes[b] << (b * L))
    return big

def bigint_to_planes(big: int) -> List[int]:
    """1024비트 정수를 8개 평면으로 역변환"""
    planes = []
    for b in range(8):
        planes.append( (big >> (b * L)) & MASK_128 )
    return planes

# ---------- 변환 M (FUN_1400053c0) ----------

def mix_planes(planes: List[int]) -> List[int]:
    """M: out[p] = in[p-1] XOR in[p+1] on each bit-plane with zero boundary."""
    out = []
    for b in range(8):
        x = planes[b]
        out.append( ((x << 1) ^ (x >> 1)) & MASK_128 )
    return out

def advance_planes(planes: List[int], steps: int) -> List[int]:
    """M^steps (naive). T가 매우 크면 시간이 늘어남."""
    cur = planes[:]
    for _ in range(steps):
        cur = mix_planes(cur)
    return cur

# ---------- 한 스텝 HIT 효과 U_t 계산 ----------

def hit_injection_vector(t: int) -> bytes:
    """U_t: 위치 (t & 0x7F)에 c_t = (t*0x1B + 0x37) & 0xFF 만 비트가 있는 128바이트"""
    j = t & 0x7F
    c = (t * 0x1B + 0x37) & 0xFF
    bs = bytearray(L)
    bs[j] = c
    return bytes(bs)

# ---------- 가우스 소거 (GF(2))로 A*h = delta 풀기 ----------
# A = [v_0 ... v_{T-1}] (1024비트 column 들), delta = 1024비트

def solve_gf2_columns(columns: List[int], delta: int) -> Tuple[bool, List[int]]:
    """
    columns: 길이 T, 각 원소는 1024비트(int) column
    delta  : 1024비트(int)
    반환: (성공여부, h(0/1) 리스트)
    """
    T = len(columns)
    # basis: pivot_bit -> (col_vector, combination_bitmask)
    basis_vec = {}   # pivot_bit -> int(1024b)
    basis_comb = {}  # pivot_bit -> int(Tb), 원본 column들의 조합
    # 각 column에 대한 combination bitmask (초기엔 자기 자신만 1)
    combs = [1 << i for i in range(T)]
    # 빌드 (column basis 생성)
    for i, col in enumerate(columns):
        v = col
        c = combs[i]
        # pivot 낮은 비트부터/높은 비트부터 아무거나 가능. 여기선 높은 비트 우선.
        while v:
            p = v.bit_length() - 1  # pivot 위치
            if p in basis_vec:
                v ^= basis_vec[p]
                c ^= basis_comb[p]
            else:
                basis_vec[p] = v
                basis_comb[p] = c
                break
        # v==0 이면 기존 basis로 표현 가능(선형 종속)
    # delta를 basis로 소거
    w = delta
    sol_comb = 0
    while w:
        p = w.bit_length() - 1
        if p not in basis_vec:
            # 해 없음
            return False, []
        w ^= basis_vec[p]
        sol_comb ^= basis_comb[p]
    # sol_comb 의 각 비트가 해당 column(=스텝)을 사용할지(HIT) 결정
    hits = [ (sol_comb >> i) & 1 for i in range(T) ]
    return True, hits

# ---------- 메인: 스케줄 계산 ----------

def compute_schedule(
    T: int,
    init_bytes: bytes,
    target_bytes: bytes
) -> Tuple[bool, List[int]]:
    """
    주어진 T(스텝 수), 초기 상태(init_bytes), 타겟 상태(target_bytes)에 대해
    HIT/MISS 스케줄(h[t]∈{0,1})을 계산.
    """
    assert len(init_bytes) == L and len(target_bytes) == L

    # 1) base = M^T(S0)
    base_planes = advance_planes(bytes_to_planes(init_bytes), T)
    base_big = pack_planes_to_bigint(base_planes)

    # 2) columns v_t = M^{T-t}(U_t)
    columns_big = []
    for t in range(T):
        U_bytes = hit_injection_vector(t)
        U_planes = bytes_to_planes(U_bytes)
        V_planes = advance_planes(U_planes, T - t)  # M^{T-t}
        V_big = pack_planes_to_bigint(V_planes)
        columns_big.append(V_big)

    # 3) delta = TARGET ^ base
    target_big = pack_planes_to_bigint(bytes_to_planes(target_bytes))
    delta = target_big ^ base_big

    # 4) Solve A*h = delta
    ok, hits = solve_gf2_columns(columns_big, delta)
    return ok, hits

# ---------- 시뮬레이터(검증용) ----------

def simulate_with_schedule(T: int, init_bytes: bytes, hits: List[int]) -> bytes:
    """계산된 스케줄로 실제 최종 상태를 시뮬레이션해서 검증한다."""
    planes = bytes_to_planes(init_bytes)
    for t in range(T):
        if hits[t]:
            # inject U_t
            Ub = hit_injection_vector(t)
            Ubp = bytes_to_planes(Ub)
            # XOR
            for b in range(8):
                planes[b] ^= Ubp[b]
        # mix
        planes = mix_planes(planes)
    return planes_to_bytes(planes)

# ---------- 입력(초기값/타깃) 세팅 ----------

# 1) 초기 상태 (네가 준 16개 QWORD, little-endian 메모리 순서로 128바이트 구성)
QWORDS_INIT = [
    0x2cfe542af6bcdfc9, 0xf827a156b5343296,
    0xc2cf199748081bd1, 0x6e26919c7c7bf2f9,
    0x8b5b00d8abffae1b, 0x96e0cde33808f13d,
    0xc59babdd835b5d0b, 0x6b9e07b75d498495,
    0xf18c48ce17b46361, 0xf9b94c2601dfe836,
    0xdc46ed6a800e449c, 0xb67a2df488263a5b,
    0x6621c22f7d4d5b15, 0xe4b8d8381dc49605,
    0x82df48ce211e68a5, 0x1a6836a93b27b7e4,
]
INIT_BYTES = b''.join(q.to_bytes(8, 'little') for q in QWORDS_INIT)

# 2) 타깃 상태 (예: DAT_140077660) — 네가 올린 128바이트를 그대로 넣으면 됨
TARGET_HEX = """
14 64 42 4a 00 cc 14 34 21 43 26 82 98 11 2f 6f
3e 89 3a b8 d0 1c af 57 ef 3a 6b 23 dd 83 6c d8
3b ca c1 01 d4 30 52 a4 aa 8f e6 55 b6 c3 6d 1c
86 c9 2c 94 6b 7a 91 ae 31 e3 7e cd 8f e9 dd 1a
d1 c5 d0 c0 81 6f ee 9b 78 b0 aa fd 75 80 db 90
55 ff fd 90 f9 04 e9 54 2a 94 ea be 0e ec 44 35
28 18 bd 86 51 88 44 b1 d6 2d 27 d5 1b 4d 8d d2
df a4 f3 cf 94 aa 15 2d 8d 75 99 15 47 10 f7 08
"""
TARGET_BYTES = bytes(int(x,16) for x in TARGET_HEX.split())

# 3) 노트 수(T) — 정확한 값으로 채워야 함!
#    (게임 내부: T = (DAT_140099008 - DAT_140099000) >> 4)
T = 1080  # TODO: 여기에 실제 노트 개수를 넣으세요 (정확히!)

if __name__ == "__main__":
    if T <= 0:
        print("T(노트 수)를 먼저 정확히 설정하세요.")
    else:
        ok, hits = compute_schedule(T, INIT_BYTES, TARGET_BYTES)
        if not ok:
            print("[!] 주어진 T로는 정확히 맞출 수 없습니다 (선형계 해 없음). T 또는 타깃/초기값을 확인하세요.")
        else:
            print("[+] HIT/MISS 시퀀스 산출 완료.")
            print("    예: 첫 64스텝:", ''.join('1' if h else '0' for h in hits[:64]))
            print("".join("1" if h else "0" for h in hits))
            # 검증
            final_bytes = simulate_with_schedule(T, INIT_BYTES, hits)
            if final_bytes == TARGET_BYTES:
                print("[OK] 시뮬레이션 검증 통과: 최종 128바이트가 Target과 정확히 일치합니다.")
            else:
                print("[!] 시뮬레이션 검증 실패: 계산/입력 값을 점검하세요.")

dat = [None] * 128
for i in range(128):
    # 바운더리 오류 날 경우 a나 b를 0으로 처리하면 됩니다.
    a = dat[i + 1]
    b = dat[i - 1]
    dat[i] = a ^ b

import os
import re
import time
import base64
import numpy as np
from io import BytesIO
from typing import List, Tuple, Optional

import cv2
from PIL import Image

from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.chrome.options import Options
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC
from webdriver_manager.chrome import ChromeDriverManager
from selenium.webdriver.chrome.service import Service

URL = "https://modulation-master-9e36f9625dce.instancer.sekai.team/"
TOTAL_ROUNDS = 110
SAVE_DIR = "images"

# ----- 고정 경계 (원본 좌표계) -----
Y_TOP, Y_BOTTOM = 27, 331
# Y_TOP, Y_BOTTOM = 270, 300
X_BOUNDS = [60, 252, 446, 640, 834, 1028, 1221, 1415, 1607]  # 9개 → 8구역
BASE_W = X_BOUNDS[-1]  # 1607
BASE_H = Y_BOTTOM  # 331

# 템플릿 중앙 크기 비율(필요시 조정)
CENTER_FRAC_X = 0.90
CENTER_FRAC_Y = 0.90
SIM_THRESHOLD = 0.90  # 90% 이상 일치면 같은 신호(=0)

# ----- 유틸 -----
PRINT_MIN, PRINT_MAX = 32, 126
SETTLE_MS=35



def wait_for_img_loaded_and_settled(driver, timeout=15, settle_ms: int = SETTLE_MS):
    """img#textImage가 로드되고(complete/decode) 아주 짧은 텀을 준다."""
    w = WebDriverWait(driver, timeout)
    img = w.until(EC.presence_of_element_located((By.CSS_SELECTOR, "img#textImage")))
    # complete & naturalWidth>0
    w.until(
        lambda d: d.execute_script(
            "const i=document.querySelector('img#textImage');return i && i.complete && i.naturalWidth>0;"
        )
    )

    # decode() + 2 frames + short timeout
    script = f"""
    const done = arguments[0];
    (async () => {
      const i = document.querySelector('img#textImage');
      if (!i) return done(false);
      try {
        if ('decode' in i) {
          try { await i.decode(); } catch (e) {}
        } else {
          if (!i.complete) {
            await new Promise(res => { i.onload = () => res(); i.onerror = () => res(); });
          }
        }
        await new Promise(r => requestAnimationFrame(() => r()));
        await new Promise(r => requestAnimationFrame(() => r()));
        setTimeout(() => done(true), {settle_ms});
      } catch (e) {
        setTimeout(() => done(true), {settle_ms});
      }
    })();
    """
    driver.set_script_timeout(timeout)
    driver.execute_async_script(script)
    return img


def get_png_bytes_via_canvas(driver) -> Optional[bytes]:
    """현재 img#textImage를 캔버스로 그려 PNG 바이트 추출(재로드 없음)."""
    js = """
    const i = document.querySelector('img#textImage');
    if (!i || !i.complete || i.naturalWidth===0) return null;
    try {
      const c = document.createElement('canvas');
      c.width = i.naturalWidth; c.height = i.naturalHeight;
      const ctx = c.getContext('2d'); ctx.imageSmoothingEnabled=false;
      ctx.drawImage(i, 0, 0);
      return c.toDataURL('image/png');
    } catch(e){ return null; }
    """
    data_url = driver.execute_script(js)
    if not isinstance(data_url, str) or "," not in data_url:
        return None
    try:
        _, b64 = data_url.split(",", 1)
        b = base64.b64decode(b64)
        return b if len(b) > 0 else None
    except Exception:
        return None


def save_img_from_page(driver, img_el, path: str) -> Image.Image:
    """안정화 텀 이후 캔버스→PNG 저장. 실패 시 요소 스크린샷 폴백."""
    os.makedirs(SAVE_DIR, exist_ok=True)
    png_bytes = get_png_bytes_via_canvas(driver)
    if png_bytes is not None and len(png_bytes) > 0:
        with open(path, "wb") as f:
            f.write(png_bytes)
        return Image.open(BytesIO(png_bytes)).convert("RGB")
    # 폴백
    img_el.screenshot(path)
    return Image.open(path).convert("RGB")


# ===================== 비트/ASCII 유틸 =====================


def ascii_from_bits8(bits8: str) -> Optional[str]:
    if len(bits8) != 8 or re.search(r"[^01]", bits8):
        return None
    val = int(bits8, 2)
    return chr(val) if PRINT_MIN <= val <= PRINT_MAX else None


def choose_ascii(bits8: str) -> str:
    c = ascii_from_bits8(bits8)
    if c is not None:
        return c
    c = ascii_from_bits8(bits8[::-1])
    return c if c is not None else "?"


# ===================== 고정 좌표 + 템플릿 포함 판정 =====================


def binarize_crop(
    img_gray: np.ndarray, x0: int, x1: int, y0: int, y1: int
) -> np.ndarray:
    """크롭→이진화→팽창→bool mask"""
    x0 = max(0, min(x0, img_gray.shape[1] - 1))
    x1 = max(0, min(x1, img_gray.shape[1]))
    y0 = max(0, min(y0, img_gray.shape[0] - 1))
    y1 = max(0, min(y1, img_gray.shape[0]))
    if x1 <= x0 or y1 <= y0:
        return np.zeros((1, 1), dtype=bool)

    roi = img_gray[y0:y1, x0:x1]
    _, bw = cv2.threshold(roi, 230, 255, cv2.THRESH_BINARY_INV)
    if (np.count_nonzero(bw) / bw.size) < 0.002:
        _, bw = cv2.threshold(roi, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)
    bw = cv2.dilate(bw, np.ones((3, 3), np.uint8), iterations=1)
    return bw > 0


def best_subset_match_fraction(
    region_mask: np.ndarray, template_mask: np.ndarray
) -> float:
    """max overlap fraction of template inside region."""
    reg = region_mask.astype(np.uint8)
    tpl = template_mask.astype(np.uint8)

    rh, rw = reg.shape
    th, tw = tpl.shape
    if th > rh or tw > rw:
        scale = min(rh / max(th, 1), rw / max(tw, 1))
        scale = max(scale, 0.1)
        new_w = max(1, int(round(tw * scale)))
        new_h = max(1, int(round(th * scale)))
        tpl = cv2.resize(tpl, (new_w, new_h), interpolation=cv2.INTER_NEAREST)
        th, tw = tpl.shape

    tpl_ones = int(np.count_nonzero(tpl))
    if tpl_ones == 0:
        return 1.0 if int(np.count_nonzero(reg)) == 0 else 0.0

    conv = cv2.filter2D(reg.astype(np.float32), -1, tpl.astype(np.float32))
    best = float(np.max(conv)) if conv.size > 0 else 0.0
    return best / float(tpl_ones)


def bits_from_fixed_regions_with_template(
    pil_img: Image.Image,
    sim_threshold: float = SIM_THRESHOLD,
    center_frac_x: float = CENTER_FRAC_X,
    center_frac_y: float = CENTER_FRAC_Y,
) -> Tuple[str, List[float], Tuple[int, int]]:
    """
    0번 구역 중앙 조각 템플릿으로 각 구역 포함율(최대 겹침) 비교 → 비트(0/1)
    - 첫 비트는 무조건 0
    """
    img = np.array(pil_img)
    H, W = img.shape[:2]
    sx = W / float(BASE_W)
    sy = H / float(BASE_H)

    gray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)

    masks: List[np.ndarray] = []
    for i in range(8):
        x0 = int(round(X_BOUNDS[i] * sx))
        x1 = int(round(X_BOUNDS[i + 1] * sx))
        y0 = int(round(Y_TOP * sy))
        y1 = int(round(Y_BOTTOM * sy))
        masks.append(binarize_crop(gray, x0, x1, y0, y1))

    # 0번 구역 → 중앙 템플릿
    ref = masks[0]
    rh, rw = ref.shape
    tpl_w = max(1, int(round(rw * center_frac_x)))
    tpl_h = max(1, int(round(rh * center_frac_y)))
    xs = max(0, (rw - tpl_w) // 2)
    ys = max(0, (rh - tpl_h) // 2)
    template = ref[ys : ys + tpl_h, xs : xs + tpl_w]

    # 템플릿이 너무 비면 보정
    if np.count_nonzero(template) < 10:
        tpl_w2 = max(1, int(round(rw * 0.8)))
        tpl_h2 = max(1, int(round(rh * 0.8)))
        xs2 = max(0, (rw - tpl_w2) // 2)
        ys2 = max(0, (rh - tpl_h2) // 2)
        template = ref[ys2 : ys2 + tpl_h2, xs2 : xs2 + tpl_w2]
        if np.count_nonzero(template) < 10:
            template = ref

    sims: List[float] = []
    bits: List[str] = []
    for i, m in enumerate(masks):
        if i == 0:
            sims.append(1.0)
            bits.append("0")  # 첫 비트 강제 0
            continue
        s = best_subset_match_fraction(m, template)
        sims.append(s)
        bits.append("0" if s >= sim_threshold else "1")

    return "".join(bits), sims, template.shape


# ===================== 한 라운드 처리 =====================


def solve_round(driver, idx: int) -> Tuple[str, List[float], str, Tuple[int, int]]:
    img_el = wait_for_img_loaded_and_settled(driver, timeout=20, settle_ms=SETTLE_MS)
    old_src_before_submit = img_el.get_attribute("src") or ""

    # 안정화 텀 후 픽셀 추출 → 저장
    path = os.path.join(SAVE_DIR, f"{idx}.png")
    pil_img = save_img_from_page(driver, img_el, path)

    bits8, sims, tpl_shape = bits_from_fixed_regions_with_template(pil_img)
    answer = choose_ascii(bits8)

    # 입력/제출
    ans_box = WebDriverWait(driver, 10).until(
        EC.presence_of_element_located((By.CSS_SELECTOR, "input#answer"))
    )
    ans_box.clear()
    ans_box.send_keys(answer)

    submit_btn = WebDriverWait(driver, 10).until(
        EC.element_to_be_clickable((By.CSS_SELECTOR, "button#submit"))
    )
    submit_btn.click()

    # 다음 문제 로딩 대기(src 변경)
    WebDriverWait(driver, 15).until(
        lambda d: d.find_element(By.CSS_SELECTOR, "img#textImage").get_attribute("src")
        != old_src_before_submit
    )

    return bits8, sims, answer, tpl_shape


# ===================== 메인 =====================


def main():
    os.makedirs(SAVE_DIR, exist_ok=True)

    chrome_opts = Options()
    # 헤드리스 금지(요청)
    chrome_opts.add_argument("--disable-gpu")
    chrome_opts.add_argument("--no-sandbox")
    chrome_opts.add_argument("--window-size=1400,1000")
    chrome_opts.add_argument("--lang=ko-KR,ko")

    driver = webdriver.Chrome(
        service=Service(ChromeDriverManager().install()), options=chrome_opts
    )
    wait = WebDriverWait(driver, 20)

    driver.get(URL)
    start_btn = wait.until(
        EC.element_to_be_clickable((By.CSS_SELECTOR, "button#start"))
    )
    start_btn.click()

    # 첫 문제 로딩 + 안정화
    wait_for_img_loaded_and_settled(driver, timeout=20, settle_ms=SETTLE_MS)

    for i in range(1, TOTAL_ROUNDS + 1):
        try:
            bits8, sims, answer, tpl_shape = solve_round(driver, i)
            print("=" * 70)
            print(
                f"[Round {i}] saved=images/{i}.png, template={tpl_shape[0]}x{tpl_shape[1]}, settle_ms={SETTLE_MS}"
            )
            print(
                f"- 포함 유사도(max overlap, ref piece vs region): "
                + ", ".join(f"{s:.3f}" for s in sims)
            )
            print(f"- 최종 8비트         : {bits8} (bit0=0)")
            print(f"- 제출한 문자        : {answer}")
            time.sleep(0.05)  # 서버/DOM 다음 상태 준비 미세 텀
        except Exception as e:
            print("=" * 70)
            print(f"[Round {i}] 오류: {e}")
            time.sleep(0.3)

    driver.quit()
    print("\n완료.")


if __name__ == "__main__":
    main()