Hello Navi

def parse_puzzle(cells):
    return [[0 if cells[r * 9 + c] == "" else int(cells[r * 9 + c])
             for c in range(9)] for r in range(9)]

"""HackThisSite Programming Mission 9 — One-Time-Pad Encryption.

Flow:
  1. fetch /missions/prog/9/ and parse the comma-delimited 9x9 Sudoku + the
     Base64 Blowfish ciphertext;
  2. solve the Sudoku (backtracking, enumerate every solution);
  3. join the solution back into the same comma-delimited form, SHA1 it, and
     use the resulting SHA1 hex string as the Blowfish key;
  4. decrypt the Base64 ciphertext with the *exact* Blowfish variant shipped in
     blowfish.phps (hashcfg=1 -> SHA1, encryptmode=1 -> CBC-with-prepended-IV);
  5. submit the printable plaintext as the challenge password.

The Blowfish class below is a line-for-line Python port of the PHP reference at
/missions/prog/9/blowfish.phps.  It is NOT stock Blowfish: the round function
`F` uses `<<` (not `>>`) when slicing the four S-box indices, and the CBC "IV"
is `[time(), microtime()*1e6]` which is emitted as the first ciphertext block
instead of being transmitted separately.  Both quirks must be reproduced.

Run from the CTF workspace root:
    export HTS_COOKIE='HackThisSite=...'
    uv run python challenges/hts-prog/9/solve.py
"""

import base64
import hashlib
import os
import re
import struct
import sys
import time

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, os.path.abspath(os.path.join(HERE, "..")))
from common import session, fetch_level, body_text, submit  # noqa: E402

LEVEL = 9
FIELD = "password"


# --------------------------------------------------------------------------
# Blowfish (PHP blowfish.phps port)
# --------------------------------------------------------------------------
PBASE = [
    0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344,
    0xa4093822, 0x299f31d0, 0x082efa98, 0xec4e6c89,
    0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c,
    0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5, 0xb5470917,
    0x9216d5d9, 0x8979fb1b,
]


def _load_sboxes():
    """Read the four S-box tables straight out of the challenge's PHP source."""
    php = os.path.join(HERE, "blowfish.php")
    if not os.path.exists(php):
        raise SystemExit("blowfish.php missing — fetch it from "
                         "/missions/prog/9/blowfish.phps first")
    src = open(php, encoding="utf-8").read()
    boxes = []
    for name in ("sbox0", "sbox1", "sbox2", "sbox3"):
        m = re.search(r"\$%s\s*=\s*Array" % name, src)
        j = m.end() - 1
        depth = 0
        for k in range(j, len(src)):
            if src[k] == "(":
                depth += 1
            elif src[k] == ")":
                depth -= 1
                if depth == 0:
                    body = src[j:k]
                    break
        boxes.append([int(x, 16) for x in re.findall(r"0x[0-9a-fA-F]+", body)])
    return boxes


SBASE = _load_sboxes()
MASK32 = 0xFFFFFFFF


class Blowfish:
    """Faithful port of the PHP reference implementation."""

    def __init__(self):
        self.P = PBASE[:]
        self.S = [b[:] for b in SBASE]

    def sbox_round(self, integer):
        # NOTE: the original uses `<<` here, not `>>`.  On a 64-bit interpreter
        # (x<<24)&0xFF, (x<<16)&0xFF and (x<<8)&0xFF all collapse to 0, so only
        # the low byte survives.  Keep it exactly as written.
        b0 = (integer << 24) & 0xFF
        b1 = (integer << 16) & 0xFF
        b2 = (integer << 8) & 0xFF
        b3 = integer & 0xFF
        r = self.S[0][b0] + self.S[1][b1] % 4294967295
        r = (r ^ self.S[2][b2]) + self.S[3][b3] % 4294967295
        return r

    def block_encrypt(self, left, right):
        vl, vr = left, right
        for i in range(16):
            vl ^= self.P[i]
            vr ^= self.sbox_round(vl)
            vl, vr = vr, vl
        vl, vr = vr, vl
        vr ^= self.P[16]
        vl ^= self.P[17]
        return vl, vr

    def block_decrypt(self, left, right):
        vl, vr = left, right
        vl ^= self.P[17]
        vr ^= self.P[16]
        vl, vr = vr, vl
        for i in range(15, -1, -1):
            vl, vr = vr, vl
            vr ^= self.sbox_round(vl)
            vl ^= self.P[i]
        return vl, vr

    def keys(self, key):
        """Key schedule; `key` is the raw string the server feeds to keys()."""
        if isinstance(key, str):
            key = key.encode()
        key_hash = hashlib.sha1(key).hexdigest().encode()   # PHP sha1() -> hex
        if len(key) >= 16:
            material = key[:16]
        else:
            material = (key + key_hash * (1 + 16 // len(key_hash)))[:16]
        kw = list(struct.unpack(">4I", material))
        for i in range(18):
            self.P[i] ^= kw[i % 4]
        v0 = v1 = 0
        for i in range(0, 18, 2):
            v0, v1 = self.block_encrypt(v0, v1)
            self.P[i] = v0
            self.P[i + 1] = v1
        for bi in range(4):
            for i in range(0, 256, 2):
                v0, v1 = self.block_encrypt(v0, v1)
                self.S[bi][i] = v0
                self.S[bi][i + 1] = v1


def blowfish_cbc_decrypt(b64_text, key):
    """Decrypt Base64 CBC-Blowfish where block 0 is the prepended IV."""
    bf = Blowfish()
    bf.keys(key)
    data = base64.b64decode(b64_text)
    words = list(struct.unpack(">%dI" % (len(data) // 4), data))
    prev = (words[0], words[1])           # emitted IV block
    out = bytearray()
    for i in range(2, len(words), 2):
        pl, pr = bf.block_decrypt(words[i], words[i + 1])
        pl ^= prev[0]
        pr ^= prev[1]
        out += struct.pack(">II", pl & MASK32, pr & MASK32)
        prev = (words[i], words[i + 1])
    return bytes(out)


# --------------------------------------------------------------------------
# Sudoku
# --------------------------------------------------------------------------
def parse_puzzle(cells):
    return [[0 if cells[r * 9 + c] == "" else int(cells[r * 9 + c])
             for c in range(9)] for r in range(9)]


def solve_sudoku(grid, limit=64):
    solutions = []

    def valid(g, r, c, v):
        for i in range(9):
            if g[r][i] == v or g[i][c] == v:
                return False
        br, bc = 3 * (r // 3), 3 * (c // 3)
        for i in range(br, br + 3):
            for j in range(bc, bc + 3):
                if g[i][j] == v:
                    return False
        return True

    def backtrack(g):
        if len(solutions) >= limit:
            return
        for r in range(9):
            for c in range(9):
                if g[r][c] == 0:
                    for v in range(1, 10):
                        if valid(g, r, c, v):
                            g[r][c] = v
                            backtrack(g)
                            g[r][c] = 0
                    return
        solutions.append([row[:] for row in g])

    backtrack([row[:] for row in grid])
    return solutions


def check_solution(g):
    want = set(range(1, 10))
    for r in range(9):
        if set(g[r]) != want:
            return False
    for c in range(9):
        if {g[r][c] for r in range(9)} != want:
            return False
    for br in (0, 3, 6):
        for bc in (0, 3, 6):
            if {g[br + i][bc + j] for i in range(3) for j in range(3)} != want:
                return False
    return True


# --------------------------------------------------------------------------
# Main
# --------------------------------------------------------------------------
def parse_page(text):
    puzzle = re.search(r'copy/paste form: <input type="text" value="([^"]*)"',
                       text).group(1)
    cipher = re.search(r"Blowfish encrypted string:\s*([A-Za-z0-9+/=]+)",
                       text).group(1)
    return puzzle, cipher


def main():
    s = session()
    page = fetch_level(s, LEVEL)
    puzzle, cipher = parse_page(page)
    cells = puzzle.split(",")
    if len(cells) != 81:
        raise SystemExit("expected 81 cells, got %d" % len(cells))
    print("[*] puzzle   :", puzzle)
    print("[*] cipher   :", cipher)

    grid = parse_puzzle(cells)
    sols = solve_sudoku(grid)
    print("[*] solutions:", len(sols))

    answer = None
    for idx, sol in enumerate(sols):
        assert check_solution(sol), "invalid sudoku solution"
        solstr = ",".join(str(v) for v in sum(sol, []))
        digest = hashlib.sha1(solstr.encode()).hexdigest()
        # The server feeds the SHA1 *hex string* to keys(); keys() keeps the
        # first 16 characters because the digest is longer than 16 bytes.
        plain = blowfish_cbc_decrypt(cipher, digest.encode())
        printable = all(32 <= b < 127 for b in plain)
        print("[*] sol #%d sha1=%s -> %r (printable=%s)"
              % (idx, digest, plain, printable))
        if printable:
            answer = plain.decode().rstrip(" ")   # strip space padding
            break

    if not answer:
        raise SystemExit("no printable plaintext — key derivation wrong")

    print("[*] password :", answer)
    if os.environ.get("HTS_DRY"):
        print("[*] HTS_DRY set — skipping submission")
        return
    time.sleep(3)
    ok, resp = submit(s, LEVEL, answer, field=FIELD)
    print("[*] verdict  :", ok)
    print(body_text(resp)[-1200:])


if __name__ == "__main__":
    main()

import numpy as np
from PIL import Image

a = np.array(Image.open("chal_live.bmp").convert("RGB")).astype(int)
H, W, _ = a.shape
bm = np.array([(a[y, :, 2].min() + a[y, :, 2].max()) / 2.0 for y in range(H)])
order = sorted(range(H), key=lambda y: bm[y])      # 按估计出的原始位置排序
rank = {y: k for k, y in enumerate(order)}         # rank 0 == 原图最下面一行

import math
import re
import time

import numpy as np
import requests
from scipy.spatial import cKDTree

BASE = "https://www.hackthissite.org"
N_CHARS = 253
STEP = 0.35                      # point-cloud sampling spacing, in device px


def session(cookie):
    s = requests.Session()
    s.headers.update({
        "User-Agent": "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 "
                      "(KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36",
        "Cookie": cookie,
        "Referer": BASE + "/missions/programming/",
    })
    return s


def fetch_drawdata(s):
    """Instance page -> captcha URL -> the flat drawData array. Timer starts here."""
    page = s.get(BASE + "/missions/prog/6/", timeout=20).text
    hit = re.search(r'(?:href|src)="([^"]*prog/6/image[^"]*)"', page)
    url = hit.group(1) if hit else "/missions/prog/6/image"
    if not url.endswith("/"):
        url += "/"               # bare path 301s but the redirect body is empty
    if url.startswith("/"):
        url = BASE + url
    html = s.get(url, timeout=20,
                 headers={"Referer": BASE + "/missions/prog/6/"}).text
    m = re.search(r"new Array\(([^)]*)\)", html, re.S)
    return [int(x) for x in re.findall(r"-?\d+", m.group(1))]


def primitives(data):
    """Split drawData exactly the way drawIt() does: 4 ints = line, 5 ints = arc."""
    i, out = 0, []
    while i + 2 < len(data):
        if data[i + 2] >= 10:
            out.append(("L", *[float(v) for v in data[i:i + 4]]))
            i += 4
        else:
            out.append(("A", *[float(v) for v in data[i:i + 5]]))
            i += 5
    return out


def rasterize(prims, w, h):
    """idmap[x][y] = index of the primitive that painted that pixel."""
    idmap = [[-1] * h for _ in range(w)]
    for idx, p in enumerate(prims):
        if p[0] == "L":
            x1, y1, x2, y2 = p[1:5]
            n = max(2, int(math.hypot(x2 - x1, y2 - y1) * 2))
            pts = [(x1 + (x2 - x1) * t / n, y1 + (y2 - y1) * t / n)
                   for t in range(n + 1)]
        else:
            x0, y0, r, s, e = p[1:6]
            n = max(2, int(abs(e) / 4.0))
            pts = [(x0 + r * math.cos(math.radians(s + e * t / n)),
                    y0 - r * math.sin(math.radians(s + e * t / n)))
                   for t in range(n + 1)]
        for fx, fy in pts:
            xx, yy = int(round(fx)), int(round(fy))
            if 0 <= xx < w and 0 <= yy < h:
                idmap[xx][yy] = idx
    return idmap


def glyphs(idmap):
    """8-neighbour flood fill: one connected blob = one character."""
    w, h = len(idmap), len(idmap[0])
    seen = [[False] * h for _ in range(w)]
    out = []
    for sx in range(w):
        for sy in range(h):
            if idmap[sx][sy] < 0 or seen[sx][sy]:
                continue
            stack, pts, ids = [(sx, sy)], [], set()
            seen[sx][sy] = True
            while stack:
                x, y = stack.pop()
                pts.append((x, y))
                ids.add(idmap[x][y])
                for dx in (-1, 0, 1):
                    for dy in (-1, 0, 1):
                        nx, ny = x + dx, y + dy
                        if (0 <= nx < w and 0 <= ny < h and not seen[nx][ny]
                                and idmap[nx][ny] >= 0):
                            seen[nx][ny] = True
                            stack.append((nx, ny))
            if len(pts) >= 4:                       # drop 1-3 px specks
                xs = [q[0] for q in pts]
                ys = [q[1] for q in pts]
                out.append({"ids": sorted(ids),
                            "cx": sum(xs) / len(xs),
                            "cy": sum(ys) / len(ys),
                            "n": len(pts)})
    return out

from collections import Counter

B_LOG = math.log(1.005)


def fit_center(gs, init):
    """Grid-search the spiral centre so every glyph angle lands on the 10-deg lattice."""
    def score(cx, cy):
        tot, cnt = 0.0, 0
        for g in gs:
            if math.hypot(g["cx"] - cx, g["cy"] - cy) < 150:
                continue
            ang = math.degrees(math.atan2(g["cy"] - cy, g["cx"] - cx))
            tot += abs((ang + 5.0) % 10.0 - 5.0) ** 2
            cnt += 1
        return tot / max(1, cnt)

    best = (score(*init), init[0], init[1])
    for span, step in ((80.0, 1.0), (4.0, 0.2), (0.6, 0.05)):
        x0, y0 = best[1], best[2]
        x = x0 - span
        while x <= x0 + span:
            y = y0 - span
            while y <= y0 + span:
                sc = score(x, y)
                if sc < best[0]:
                    best = (sc, x, y)
                y += step
            x += step
    return best[1], best[2]


def order_glyphs(gs, cx, cy):
    """k = angle index + 36 * turn; k = 0 is the innermost glyph, k grows clockwise."""
    for g in gs:
        g["r"] = math.hypot(g["cx"] - cx, g["cy"] - cy)
        g["ang"] = math.degrees(math.atan2(g["cy"] - cy, g["cx"] - cx)) % 360.0
        g["slot"] = int(round(g["ang"] / 10.0)) % 36
    cnt = Counter(g["slot"] for g in gs)
    j0 = max(cnt, key=lambda s: cnt[s])       # innermost slot holds the extra glyph
    for g in gs:
        g["j"] = (g["slot"] - j0) % 36
    A = math.log(min(g["r"] for g in gs))
    for _ in range(8):                        # iterate ln r = A + B*k
        for g in gs:
            m = round((math.log(g["r"]) - A - B_LOG * g["j"]) / (36.0 * B_LOG))
            m = min(max(m, 0), 7)
            k = g["j"] + 36 * m
            g["k"] = k if 0 <= k <= N_CHARS - 1 else None
        pts = [(g["k"], math.log(g["r"])) for g in gs if g["k"] is not None]
        n = len(pts)
        mk = sum(a for a, b in pts) / n
        mr = sum(b for a, b in pts) / n
        slope = (sum((a - mk) * (b - mr) for a, b in pts)
                 / sum((a - mk) ** 2 for a, b in pts))
        A = mr - slope * mk
    return sorted([g for g in gs if g["k"] is not None], key=lambda g: g["k"])

def rotate_prim(p, cx, cy, deg):
    """Rotate a primitive about (cx, cy) by deg degrees in screen coords."""
    th = math.radians(deg)
    c, s = math.cos(th), math.sin(th)

    def R(x, y):
        dx, dy = x - cx, y - cy
        return (cx + dx * c - dy * s, cy + dx * s + dy * c)

    if p[0] == "L":
        x1, y1 = R(p[1], p[2])
        x2, y2 = R(p[3], p[4])
        return ("L", x1, y1, x2, y2)
    x, y = R(p[1], p[2])
    return ("A", x, y, p[3], p[4] - deg, p[5])   # the start angle shifts too


def sample(prims):
    """Sample canonical primitives to a point cloud, centred on its own mean."""
    pts = []
    for p in prims:
        if p[0] == "L":
            x1, y1, x2, y2 = p[1:5]
            n = max(2, int(math.hypot(x2 - x1, y2 - y1) / STEP))
            pts += [(x1 + (x2 - x1) * t / n, y1 + (y2 - y1) * t / n)
                    for t in range(n + 1)]
        else:
            x0, y0, r, s, e = p[1:6]
            n = max(2, int(abs(e) / 4.0))
            pts += [(x0 + r * math.cos(math.radians(s + e * t / n)),
                     y0 - r * math.sin(math.radians(s + e * t / n)))
                    for t in range(n + 1)]
    a = np.array(pts, dtype=np.float64)
    a -= a.mean(0)
    return a


def cloud(g):
    """Orientation-normalised point cloud of one glyph."""
    ang = round(g["ang"] / 10.0) * 10.0
    return sample([rotate_prim(p, g["cx"], g["cy"], -(ang + 90.0))
                   for p in g["prims"]])

# auto-generated canonical glyph templates (relative to cloud mean)
TEMPLATES = {
    '0': [
        ('A', -0.26, 3.31, 4.00, 180.00, 180.00),
        ('L', -3.46, -3.15, -3.86, 3.54),
        ('A', 0.14, -3.38, 4.00, 360.00, 180.00),
        ('L', 3.34, 3.08, 3.74, -3.62),
    ],
    '1': [
        ('L', 0.46, -7.29, -2.54, -3.29),
        ('L', 0.46, -7.29, 0.46, 6.71),
        ('L', -2.54, 6.71, 3.46, 6.71),
    ],
    '2': [
        ('L', 4.03, -3.38, -3.91, 6.96),
        ('A', -0.07, -2.95, 4.00, 0.00, 180.00),
        ('L', -3.91, 6.96, 4.63, 7.05),
    ],
    '3': [
        ('L', -2.53, -1.73, -1.53, -1.73),
        ('A', -1.53, 2.27, 4.00, 225.00, 230.00),
        ('A', -1.53, -4.73, 3.00, 270.00, 225.00),
    ],
    '4': [
        ('L', -1.51, -6.14, -3.21, 0.87),
        ('L', -3.21, 0.87, 4.39, 1.29),
        ('L', 0.72, -5.89, 0.46, 8.04),
    ],
    '5': [
        ('L', -2.32, -2.11, 0.50, -1.86),
        ('L', 3.81, -7.25, -2.59, -7.10),
        ('L', -2.32, -2.11, -2.59, -7.10),
        ('A', 0.13, 2.36, 4.00, 180.00, 270.00),
    ],
    '6': [
        ('L', -3.31, -0.43, 1.69, -9.09),
        ('O', 0.16, 1.57, 4.00),
    ],
    '7': [
        ('L', 0.99, 1.85, -3.47, 1.58),
        ('L', 2.76, -5.21, -3.94, -5.61),
        ('L', 2.76, -5.21, -1.64, 8.41),
    ],
    '8': [
        ('O', -0.06, -4.25, 3.00),
        ('O', 0.17, 2.82, 4.00),
    ],
    '9': [
        ('L', -1.66, 8.64, 2.36, 0.52),
        ('O', -0.12, -1.44, 4.00),
    ],
    'A': [
        ('L', 0.22, -7.18, 5.84, 7.01),
        ('L', -5.34, 7.07, 0.22, -7.18),
        ('L', 3.12, -0.58, -2.96, -0.64),
    ],
    'B': [
        ('L', -4.42, -6.64, -4.17, 7.28),
        ('L', -4.42, -6.64, 0.96, -6.81),
        ('L', -4.17, 7.28, 1.21, 7.11),
        ('A', 0.36, 3.61, 4.00, -90.00, 180.00),
        ('A', 0.87, -3.65, 4.00, -90.00, 180.00),
        ('L', 0.79, -0.49, -3.66, 0.02),
    ],
    'C': [
        ('A', 2.35, 0.31, 7.00, 55.00, 255.00),
    ],
    'D': [
        ('A', -0.29, 0.22, 7.00, 270.00, 180.00),
        ('L', -4.29, -6.71, -4.35, 7.18),
        ('L', 0.17, -6.98, -4.29, -6.71),
        ('L', -4.35, 7.18, 0.11, 6.91),
    ],
    'E': [
        ('L', -2.63, 7.00, 5.37, 7.00),
        ('L', -2.63, 7.00, -2.63, -7.00),
        ('L', 5.37, -7.00, -2.63, -7.00),
        ('L', -2.63, 0.00, 4.37, 0.00),
    ],
    'F': [
        ('L', -2.19, 1.77, 4.51, 1.37),
        ('L', -1.79, 8.47, -1.73, -5.43),
        ('L', -1.73, -5.43, 6.34, -5.46),
    ],
}

def classify(order, templates):
    tchars = sorted(templates)
    tclouds = {c: sample(templates[c]) for c in tchars}
    trees = {c: cKDTree(tclouds[c]) for c in tchars}
    chars, margins = [], []
    for g in order:
        c = cloud(g)
        ct = cKDTree(c)
        ranked = sorted((0.5 * (trees[t].query(c)[0].mean()
                                + ct.query(tclouds[t])[0].mean()), t)
                        for t in tchars)
        chars.append(ranked[0][1])
        margins.append(ranked[1][0] - ranked[0][0])
    return "".join(chars), min(margins)

def solve_once(cookie, dry=False):
    s = session(cookie)
    t0 = time.time()

    data = fetch_drawdata(s)                                  # timer starts here
    prims = primitives(data)
    w = int(max(p[1] for p in prims)) + 30
    h = int(max(p[2] for p in prims)) + 30
    gs = glyphs(rasterize(prims, w, h))
    init = (sum(g["cx"] for g in gs) / len(gs),
            sum(g["cy"] for g in gs) / len(gs))
    cx, cy = fit_center(gs, init)
    order = order_glyphs(gs, cx, cy)
    for g in order:
        ids = set(g["ids"])
        g["prims"] = [p for i, p in enumerate(prims) if i in ids]
    answer, margin = classify(order, TEMPLATES)
    t_solve = time.time()

    if dry:
        return answer, t_solve - t0
    resp = s.post(BASE + "/missions/prog/6/index.php",
                  data={"solution": answer, "submitbutton": "submit"},
                  timeout=30, headers={"Referer": BASE + "/missions/prog/6/"}).text
    ok = "successfully completed" in resp or "Congrats" in resp
    return answer, time.time() - t0, ok


def main(cookie):
    answer, t_fetch_solve = solve_once(cookie, dry=True)
    print("fetch+solve %.2fs  len=%d  margin>=%.2f"
          % (t_fetch_solve, len(answer), 0.0))
    answer, total, ok = solve_once(cookie)
    print("total %.2fs  accepted=%s" % (total, ok))

import bz2
import itertools

PNG_MAGIC = b"\x89PNG\r\n\x1a\n"

def crlf_positions(data):
    """每个 0x0D 0x0A 对的起始下标。"""
    return [i for i in range(len(data) - 1)
            if data[i] == 0x0D and data[i + 1] == 0x0A]

def rebuild(data, keep, positions):
    """删掉每一个 CRLF 对里的 CR，但 keep 里的下标保留 CR（=原始数据）。

    注意不能用 data.replace(b'\\r\\n', b'\\n')：相邻的 CRLF 会互相影响，
    必须逐对扫描。
    """
    keep = set(keep)
    out, i, j = bytearray(), 0, 0
    while i < len(data):
        if i + 1 < len(data) and data[i] == 0x0D and data[i + 1] == 0x0A:
            if j in keep:
                out.append(data[i])
            out.append(data[i + 1])
            i += 2
            j += 1
        else:
            out.append(data[i])
            i += 1
    return bytes(out)

def repair(data, max_keep=3):
    pos = crlf_positions(data)
    for k in range(max_keep + 1):
        for combo in itertools.combinations(range(len(pos)), k):
            try:
                plain = bz2.decompress(rebuild(data, combo, pos))
            except Exception:
                continue
            if plain[:8] == PNG_MAGIC:
                return rebuild(data, combo, pos), plain, [pos[i] for i in combo]
    raise SystemExit("could not repair the archive")

#!/usr/bin/env python3
"""HackThisSite Programming Mission 3 -- 只靠密文还原明文 serial 文件。

关卡页面给出的 PHP 加密链（等价形式）：

    total_0     = evalCrossTotal(md5(password))          # md5 的 32 个 nibble 之和
    enc[i]      = ord(plain[i]) + hexval(md5(pw)[i % 32]) - total_i
    total_{i+1} = evalCrossTotal(md5(plain[:i+1])[:16] + md5(str(total_i))[:16])

password 未知，真正的未知量是 h[0..31] = md5(password) 的 32 个 nibble，
以及 total0 = sum(h)。serial 模板把每列候选压到 1 个或 36 个字符，
枚举 total0(0..480) 做前向搜索即可恢复明文。

用法：python decrypt.py [ciphertext.txt]
"""

import hashlib
import os
import re
import sys

ALNUM = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
HERE = os.path.dirname(os.path.abspath(__file__))

def md5(s):
    return hashlib.md5(s.encode("ascii")).hexdigest()

def hexval(c):
    return int(c, 16)

def eval_cross_total(s):
    """PHP evalCrossTotal：'0x0' 前缀让每个字符按十六进制解释，取值 0..15。"""
    return sum(hexval(c) for c in s)

def encrypt_hash(plain, pwd_md5):
    """给定 md5(password) 的十六进制字符串，复刻 encryptString。"""
    total = eval_cross_total(pwd_md5)
    out = []
    for i, ch in enumerate(plain):
        out.append(ord(ch) + hexval(pwd_md5[i % 32]) - total)
        total = eval_cross_total(md5(plain[: i + 1])[:16] + md5(str(total))[:16])
    return out

def build_template(example_text):
    """从官方示例 serial 推每列允许的 ord 集合，返回 (template, width)。"""
    lines = [ln for ln in example_text.splitlines()
             if ln and not ln.startswith("(")]
    width = len(lines[0]) + 1
    tpl = []
    for pos in range(width - 1):
        seen = {ln[pos] for ln in lines}
        tpl.append({ord(seen.pop())} if len(seen) == 1
                   else {ord(c) for c in ALNUM})
    tpl.append({ord("\n")})              # 每行以 UNIX 换行结束
    return tpl, width

def recover(enc, template, width, max_states=2_000_000):
    """返回所有与密文、模板一致的明文。state = (total, h_tuple, prefix)。"""
    solutions = []
    for total0 in range(0, 32 * 15 + 1):          # sum(32 个 nibble) 的上界 480
        states = [(total0, (), "")]
        dead = False
        for i in range(len(enc)):
            r = i % 32
            allow = template[i % width]
            nxt = []
            for total, h, pre in states:
                cands = (h[r],) if r < len(h) else range(16)
                for hv in cands:
                    o = enc[i] - hv + total         # ord = enc - h + total
                    if o not in allow:
                        continue
                    ch = chr(o)
                    h2 = h + (hv,) if r >= len(h) else h
                    nxt.append((eval_cross_total(
                        md5(pre + ch)[:16] + md5(str(total))[:16]), h2, pre + ch))
            if not nxt or len(nxt) > max_states:
                dead = True
                break
            states = nxt
        if dead:
            continue
        for total, h, plain in states:
            if len(h) == 32 and sum(h) == total0:
                solutions.append((plain, h, total0))
    return solutions

def load_template():
    for path in (os.path.join(HERE, "serials_example.txt"), "/tmp/serials_example.txt"):
        if os.path.exists(path):
            with open(path, encoding="utf-8") as fh:
                return build_template(fh.read())
    raise SystemExit("serials_example.txt not found")

def main():
    path = sys.argv[1] if len(sys.argv) > 1 else os.path.join(HERE, "ciphertext.txt")
    with open(path, encoding="utf-8") as fh:
        enc = [int(x) for x in re.findall(r"-?\d+", fh.read())]
    template, width = load_template()
    print("ciphertext: %d values" % len(enc))
    sols = recover(enc, template, width)
    if not sols:
        raise SystemExit("no plaintext found")
    for plain, h, total0 in sols:
        pwd_hash = "".join(format(x, "x") for x in h)
        assert encrypt_hash(plain, pwd_hash) == enc, "re-encryption mismatch"
        serials = [ln for ln in plain.splitlines() if ln]
        print("total0=%d  md5(password)=%s  serials=%d"
              % (total0, pwd_hash, len(serials)))
        for ln in serials:
            print(ln)
        print("last serial: %s" % serials[-1])

if __name__ == "__main__":
    main()

#!/usr/bin/env python3
"""HackThisSite Programming level 2 solver.

Task: "Analyze the picture and find the ascii code" (15 second time limit).

Pipeline (all inside one run, well under 15 s):

  1. GET the level page  -> the server generates a fresh random answer and
     the matching 100x30 1-bit PNG for this session.
  2. GET /missions/prog/2/PNG/  (same session) -> the current image.
  3. Scan the image left-to-right / top-to-bottom.  A white pixel at linear
     position p encodes  chr(p - previous_white_position)  (the first white
     pixel is measured from 0).  The resulting characters are a Morse string:
     '-' (0x2d) = dash, '.' (0x2e) = dot, ' ' (0x20) = letter separator.
  4. Morse-decode the string -> the answer (a random uppercase A-Z0-9 word).
  5. POST it as `solution` to the level page.

The session cookie is read from the HTS_COOKIE environment variable by
common.py and never written to disk.

Set HTS_DRY=1 to decode without submitting (useful for a timing rehearsal).

Run from the workspace root:
    export HTS_COOKIE='HackThisSite=...'
    uv run python challenges/hts-prog/2/solve.py
"""

import io
import os
import sys
import time

sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from common import body_text, fetch_level, session, submit  # noqa: E402

from PIL import Image  # noqa: E402

PNG_URL = "https://www.hackthissite.org/missions/prog/2/PNG/"

# Standard international Morse.  The image only ever encodes A-Z and 0-9.
MORSE = {
    ".-": "A", "-...": "B", "-.-.": "C", "-..": "D", ".": "E", "..-.": "F",
    "--.": "G", "....": "H", "..": "I", ".---": "J", "-.-": "K", ".-..": "L",
    "--": "M", "-.": "N", "---": "O", ".--.": "P", "--.-": "Q", ".-.": "R",
    "...": "S", "-": "T", "..-": "U", "...-": "V", ".--": "W", "-..-": "X",
    "-.--": "Y", "--..": "Z",
    "-----": "0", ".----": "1", "..---": "2", "...--": "3", "....-": "4",
    ".....": "5", "-....": "6", "--...": "7", "---..": "8", "----.": "9",
}


def decode_image(data):
    """Return (morse_string, list_of_ascii_codes) for a compiled PNG blob."""
    im = Image.open(io.BytesIO(data))
    w, h = im.size
    px = im.load()
    codes = []
    prev = 0
    for y in range(h):
        for x in range(w):
            if px[x, y]:  # palette index 0 = black, 1 = white (1-bit PNG)
                cur = y * w + x
                codes.append(cur - prev)
                prev = cur
    return "".join(chr(c) for c in codes), codes


def morse_decode(morse):
    """Decode a space separated Morse string; '/' separates words."""
    out = []
    for token in morse.split(" "):
        if token == "":
            out.append(" ")
        elif token == "/":
            out.append(" ")
        elif token in MORSE:
            out.append(MORSE[token])
        else:
            raise ValueError("unrecognised Morse token: %r" % token)
    return "".join(out).strip()


def main():
    dry = bool(os.environ.get("HTS_DRY"))
    s = session()
    t0 = time.monotonic()

    # 1. load the level page -> server picks a new answer for this session
    fetch_level(s, 2, keep=os.path.join(os.path.dirname(os.path.abspath(__file__)),
                                        "live_level2.html"))
    t_page = time.monotonic()

    # 2. same session fetches the freshly generated image
    r = s.get(PNG_URL, timeout=20)
    r.raise_for_status()
    img = r.content
    t_img = time.monotonic()

    # 3. pixels -> ASCII -> Morse string
    morse, codes = decode_image(img)
    print("image bytes   :", len(img), "size:",
          Image.open(io.BytesIO(img)).size)
    print("ascii codes   :", codes[:24], "... (%d total)" % len(codes))
    print("morse string  : %r" % morse)

    # 4. Morse -> answer
    answer = morse_decode(morse)
    t_dec = time.monotonic()
    print("answer        : %s" % answer)

    if not answer or not all(c.isalnum() for c in answer):
        print("!! decoded answer does not look like a clean A-Z0-9 token")

    print("timing        : page=%.2fs img=%.2fs decode=%.2fs total=%.2fs"
          % (t_page - t0, t_img - t_page, t_dec - t_img, t_dec - t0))

    if dry:
        print("HTS_DRY set -> not submitting")
        return 0

    # 5. submit
    ok, resp = submit(s, 2, answer)
    t_end = time.monotonic()
    print("submit total  : %.2fs" % (t_end - t0))
    print("verdict       :", ok)
    print("response tail :")
    print(body_text(resp)[-900:])
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

#!/usr/bin/env python3
"""Solve HackThisSite Programming Mission 1."""

import html
import os
import re
from pathlib import Path

import requests

BASE = "https://www.hackthissite.org"
LEVEL_URL = f"{BASE}/missions/prog/1/"
WORDLIST = Path(__file__).with_name("wordlist.txt")
USER_AGENT = (
    "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 "
    "(KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36"
)


def session():
    cookie = os.environ.get("HTS_COOKIE", "").strip().strip("'\"")
    if not cookie:
        raise SystemExit("HTS_COOKIE is not set")

    client = requests.Session()
    client.headers.update(
        {
            "User-Agent": USER_AGENT,
            "Cookie": cookie,
            "Referer": f"{BASE}/missions/programming/",
            "Accept-Language": "en-US,en;q=0.9",
        }
    )
    return client


def body_text(source):
    source = re.sub(r"<script.*?</script>", "", source, flags=re.S)
    source = re.sub(r"<br\s*/?>", "\n", source)
    source = re.sub(r"</(?:p|div|tr)>", "\n", source)
    source = re.sub(r"<[^>]+>", " ", source)
    source = html.unescape(source)
    source = re.sub(r"[ \t]+", " ", source)
    return re.sub(r"\n\s*\n+", "\n", source)


def load_wordlist(path):
    table = {}
    with path.open("r", encoding="utf-8", errors="replace") as fh:
        for line in fh:
            word = line.strip()
            if word:
                table.setdefault("".join(sorted(word)), word)
    return table


def parse_scrambled(page_text):
    marker = "List of scrambled words:"
    end_marker = "Answer:"
    if marker not in page_text or end_marker not in page_text:
        raise ValueError("could not find the scrambled-word section")
    chunk = page_text.split(marker, 1)[1].split(end_marker, 1)[0]
    return [token for token in re.split(r"[\s,]+", chunk) if token]


def unscramble(words, table):
    result = []
    for word in words:
        key = "".join(sorted(word))
        candidates = [value for value in table.values() if "".join(sorted(value)) == key]
        if not candidates:
            result.append(word)
        else:
            result.append(candidates[0])
    return result


def submit(client, answer):
    response = client.post(
        f"{LEVEL_URL}index.php",
        data={"solution": answer, "submitbutton": "submit"},
        headers={"Referer": LEVEL_URL},
        timeout=30,
    )
    response.raise_for_status()
    text = body_text(response.text).lower()
    success_markers = (
        "congratulation",
        "you have completed",
        "completed this",
        "successfully",
        "correct",
        "well done",
        "mission accomplished",
        "complete!",
    )
    failure_markers = (
        "wrong",
        "incorrect",
        "not correct",
        "try again",
        "failed",
        "too late",
        "time is up",
        "sorry",
    )
    success = any(marker in text for marker in success_markers)
    failure = any(marker in text for marker in failure_markers)
    if success and not failure:
        return True
    if failure and not success:
        return False
    return None


def main():
    client = session()
    response = client.get(LEVEL_URL, timeout=20)
    response.raise_for_status()
    words = parse_scrambled(body_text(response.text))
    table = load_wordlist(WORDLIST)
    answer = ",".join(unscramble(words, table))
    print("scrambled:", words)
    print("answer   :", answer)
    print("verdict  :", submit(client, answer))


if __name__ == "__main__":
    main()