CodeShell.kr - Ten Gates

Challenge

十道门串成一条流水线，规格与输入全部给出。难度在于实现细节容易错在看不见的地方，而题目自带多个校验值，可以用来定位出错的那一步。

Ten gates. Submit the keys in order. The final gate yields an uppercase password.

十道门，按顺序提交钥匙。最后一道门给出大写密码。

https://codeshell.kr/challenges/oracle-map-ten-gates/

Solution

这题是一份完整规格 + 全部输入的确定性流水线（作者 rayaseiren，schema oracle-map/2.0），没有任何在线 oracle，所以本质是实现题。bundle 里给了 challenge_public_en.md（规格）、instance.json（输入）、oracle_book.bin。

关键约定：

token(T) = SHA256(ASCII(T)) 取前 12 字节，每字节拆高低 nibble，
           经 ABCDEFGHIKLMNOPQ 映射成 24 个字符
S(K)     = 5×5 keyed square，保留 K 中首次出现的字母（去掉 J），
           再用 ABCDEFGHIKLMNOPQRSTUVWXYZ 补齐，逐行填充

十道门依次是：hex→ASCII、重复密钥 Vigenère、带密钥的列置换、S(K3) 坐标的仿射 变换（含 2 个坏点）、一个 8000 个候选的自动机 oracle（枚举 (a,b,c,d,t,o,k) 得 ID M0000–M7999）、分块 Bifid、明文自密钥 Vigenère、区分全部候选的最短 词、XOR 加密的观测手册、最后拼哈希。

Step 1：前四道门直接解：

K1 = OBSERVE                        (4F425345525645)
K2 = QZALQX                         Vigenère with K1
K3 = VXKQZRPAVNHTX                  列置换，6 列，plaintext_length 13
K4 = WQFZNVXDRKUTPBHAG              仿射变换；15625 组系数里恰有 1 组
                                    满足「正好 2 个校准点错」

K4 的唯一性是第一个自检点：(a,b,c,d,e,f) 全枚举后只有一组满足恰好 2 个 错误，说明 K3 和置换读法都对。

Step 2：第五道门。用 K4 的前两个不同字母（W→0、Q→1）把 encoded_response 解成 0/1 串，再拿 4 行训练数据过滤 8000 个模型：

candidates = 6   == gate5.expected_candidate_count   ✓ 第二个自检点
K5 = token("OM2/G5" || LF || IDs joined by LF)
   = GPNQDCLIHPGHKAIGINIPINPN

候选数正好等于期望值，说明 K4、解码方式和 oracle 语义全部正确。

Step 3：第六道门的 Bifid 我第一版写错了，坑值得记：

# 错：把坐标拆成「所有行 + 所有列」再配对
flat = [r for r, _ in coords] + [c for _, c in coords]
P[k] = sq[flat[k]][flat[m+k]]        # 这恰好是恒等变换，输出 == 密文

# 对：v 是密文字母坐标的「交错」列表
v = []
for ch in block:
    r, c = pos(ch); v += [r, c]
P[k] = sq[v[k]][v[m+k]]

因为加密是「明文的行坐标 + 明文的列坐标」再两两配对成密文，所以反解时 v 必须 按 (r,c) 交错重建。写错时输出长度仍然正确（长度只由密文长度和 period 决定）， 所以长度校验抓不到这个 bug，真正抓住它的是 oracle_book.bin 的 SHA-256。

K6 = VQXNDKRAWTYCFPHZBMSUELGO        明文自密钥 Vigenère ->
K7 = EBGHANNAKBBPOHKMMDHGHEHDGMFIGBQQDAELACILKBEEMEFIKBIHAKPOFELCEMEAMIOMPPQHQIPEQHLELBK

Step 4：第八道门要找最短的、能把 6 个候选全部区分开的词（字母表 {0,1,W}，长度 ≤ 8，含 W 也计数，并列取字典序）：答案是长度 6 的 0W1000， 于是 K8 = ACBAAA。

Step 5：第九道门用 K7 解 oracle_book.bin：

keystream block j = SHA256("OM2/BOOK" || NUL || K7 || NUL || BE32(j))

解出的明文 SHA-256 与 gate9.book_plaintext_sha256 逐位相符，这是第三个 也是最强的一个自检点（它同时验证了 K6、K7 和密钥流构造）。手册是 oracle-map/probe-book/1，max_length 8，存了 9840 条响应。用 0W1000 的响应 反查，唯一命中 M6742 = (4,1,4,2,0,1,0)，模拟 target_word 得到 R：

K9 = token("OM2/G9" || LF || "M6742" || LF || R) = NAKQQACCPOGPHBFQGPQCAEIC

Step 6：十把钥匙用冒号连接后取 SHA-256，与 gate10.ciphertext_hex 的前 30 字节异或：

$ uv run python solvers/ten_gates.py

K1 = OBSERVE
K2 = QZALQX
K3 = VXKQZRPAVNHTX
K4 = WQFZNVXDRKUTPBHAG
K5 = GPNQDCLIHPGHKAIGINIPINPN
K6 = VQXNDKRAWTYCFPHZBMSUELGO
K7 = EBGHANNAKBBPOHKMMDHGHEHDGMFIGBQQDAELACILKBEEMEFIKBIHAKPOFELCEMEAMIOMPPQHQIPEQHLELBK
K8 = ACBAAA
K9 = NAKQQACCPOGPHBFQGPQCAEIC

最终密码是可读英文大写，长度 30 与 gate10.plaintext_length 一致：

这题的方法论：三个内置校验值（候选数 6、手册 SHA-256、各段长度）让它变成 「先跑通校验点再往下走」的题。第 6 道门的 bug 只靠长度发现不了，是靠手册哈希 抓出来的：遇到「输出长度对但内容不对」的情况，要去找一个能覆盖内容的校验值。

Script

#!/usr/bin/env python3
"""CodeShell.kr — Oracle Map: The Ten Gates (Crypto, 200p) solver.

The bundle is fully specified and deterministic, so this is an implementation
exercise with several built-in checkpoints:

  * gate5.expected_candidate_count  (must match the model set size)
  * gate6.plaintext_length, gate7.plaintext_length
  * gate9.book_plaintext_sha256     (proves the K7-derived keystream is right)
  * gate10.plaintext_length

Usage: uv run python solvers/ten_gates.py
"""

import hashlib
import json
import itertools
from pathlib import Path

PUB = (Path('codeshell')
       / 'extracted' / 'oracle-map-ten-gates' / 'public')

ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
NOJ = 'ABCDEFGHIKLMNOPQRSTUVWXYZ'          # 25 letters, J removed
NIB = 'ABCDEFGHIKLMNOPQ'                   # nibble 0..15 -> letter


def token(text: str) -> str:
    """First 12 raw SHA-256 bytes, each nibble mapped through NIB -> 24 chars."""
    h = hashlib.sha256(text.encode('latin-1')).digest()[:12]
    return ''.join(NIB[b >> 4] + NIB[b & 0xF] for b in h)


def square(key: str):
    """5x5 keyed square S(key): first occurrence (J dropped), then the rest."""
    seen = []
    for ch in key:
        if ch != 'J' and ch not in seen:
            seen.append(ch)
    for ch in NOJ:
        if ch not in seen:
            seen.append(ch)
    assert len(seen) == 25, len(seen)
    return [seen[i * 5:(i + 1) * 5] for i in range(5)]


def pos_of(sq, letter):
    for r in range(5):
        for c in range(5):
            if sq[r][c] == letter:
                return r, c
    raise KeyError(letter)


def letter_at(sq, r, c):
    return sq[r][c]


def modinv(a, m=5):
    a %= m
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    raise ValueError(f'no inverse for {a} mod {m}')


# ---------------------------------------------------------------- gates 1-4
def gates_1_to_4(d):
    K1 = bytes.fromhex(d['gate1']['ciphertext_hex']).decode('ascii')
    print(f"K1 = {K1}")

    ct2 = d['gate2']['ciphertext']
    K2 = ''.join(ALPHA[(ALPHA.index(c) - ALPHA.index(K1[i % len(K1)])) % 26]
                 for i, c in enumerate(ct2))
    print(f"K2 = {K2}  (len {len(K2)})")

    # gate 3: columnar transposition with len(K2) columns
    g3 = d['gate3']
    ct3, plen = g3['ciphertext'], g3['plaintext_length']
    ncols = len(K2)
    nrows = (plen + ncols - 1) // ncols
    assert len(ct3) == nrows * ncols, (len(ct3), nrows * ncols)
    order = sorted(range(ncols), key=lambda c: (K2[c], c))
    cols = [''] * ncols
    for idx, c in enumerate(order):
        cols[c] = ct3[idx * nrows:(idx + 1) * nrows]
    grid = ''.join(cols[c][r] for r in range(nrows) for c in range(ncols))
    K3 = grid[:plen]
    print(f"K3 = {K3}  (len {len(K3)})")

    # gate 4: affine transform on S(K3), exactly `errors` bad calibration rows
    g4 = d['gate4']
    sq = square(K3)
    calib = g4['calibration']
    target = g4['target_coordinates']
    want_err = g4['errors']

    solutions = []
    for a, b, c, cc, e, f in itertools.product(range(5), repeat=6):
        if (a * cc - b * c) % 5 == 0:
            continue
        bad = 0
        for entry in calib:
            r, s = pos_of(sq, entry['letter'])
            R = (a * r + b * s + e) % 5
            S = (c * r + cc * s + f) % 5
            if [R, S] != entry['observed']:
                bad += 1
        if bad == want_err:
            solutions.append((a, b, c, cc, e, f))
    print(f"gate4: {len(solutions)} transform(s) with exactly {want_err} bad rows")

    K4s = set()
    for a, b, c, cc, e, f in solutions:
        det = (a * cc - b * c) % 5
        di = modinv(det)
        letters = []
        for R, S in target:
            # invert F:  R = a*r+b*s+e ; S = c*r+d*s+f
            R2, S2 = (R - e) % 5, (S - f) % 5
            r = (di * (cc * R2 - b * S2)) % 5
            s = (di * (-c * R2 + a * S2)) % 5
            letters.append(letter_at(sq, r, s))
        K4s.add(''.join(letters))
    assert len(K4s) == 1, K4s
    K4 = K4s.pop()
    print(f"K4 = {K4}  (len {len(K4)})")
    return K1, K2, K3, K4


# ------------------------------------------------------------------- gate 5
def model_ids():
    """(id, (a,b,c,d,t,o,k)) in lexicographic enumeration order."""
    out = []
    for a in range(1, 5):
        for b in range(5):
            for c in range(5):
                for d in range(1, 5):
                    for t in range(5):
                        for o in range(2):
                            for k in range(2):
                                out.append((a, b, c, d, t, o, k))
    return out


def run_word(model, word):
    """Response of `model` to `word` from a cold state (x=y=0)."""
    a, b, c, d, t, o, k = model
    x = y = 0
    out = []
    for ch in word:
        if ch == 'W':
            out.append('-')
            if k == 0:
                y = 0
            else:
                x = 0
            continue
        u = int(ch)
        if o == 0:
            x = (a * x + b * y + u + t) % 5
            y = (c * x + d * y + u + 1) % 5
        else:
            y = (c * x + d * y + u + 1) % 5
            x = (a * x + b * y + u + t) % 5
        out.append('1' if x == y else '0')
    return ''.join(out)


def gate5(d, K4):
    g5 = d['gate5']
    first, second = K4[0], K4[1]
    dec = {first: '0', second: '1', '-': '-'}
    train = [(r['word'], ''.join(dec[ch] for ch in r['encoded_response']))
             for r in g5['training']]
    print(f"gate5: decoded training -> {train}")

    cands = []
    for i, m in enumerate(model_ids()):
        if all(run_word(m, w) == want for w, want in train):
            cands.append((f"M{i:04d}", m))
    print(f"gate5: {len(cands)} candidates "
          f"(expected {g5['expected_candidate_count']})")
    assert len(cands) == g5['expected_candidate_count']

    ids = [cid for cid, _ in cands]
    K5 = token('OM2/G5' + '\n' + '\n'.join(ids))
    print(f"K5 = {K5}")
    return cands, K5


# ---------------------------------------------------------------- gates 6-7
def gate6(d, K5):
    g6 = d['gate6']
    sq = square(K5)
    ct, period, plen = g6['ciphertext'], g6['period'], g6['plaintext_length']
    out = []
    i = 0
    while i < len(ct):
        block = ct[i:i + period]
        m = len(block)
        # Encryption concatenates the plaintext block's m row coords followed by
        # its m col coords, then reads successive PAIRS as ciphertext letters.
        # So a ciphertext letter j contributes coords (v[2j], v[2j+1]) -- the v
        # list is the INTERLEAVED (row, col) of the ciphertext letters, and the
        # plaintext is square[v[j]][v[m+j]].
        v = []
        for ch in block:
            r, c = pos_of(sq, ch)
            v += [r, c]
        out.append(''.join(letter_at(sq, v[j], v[m + j]) for j in range(m)))
        i += period
    K6 = ''.join(out)
    print(f"K6 = {K6}  (len {len(K6)}, expected {plen})")
    assert len(K6) == plen
    return K6


def gate7(d, K6):
    g7 = d['gate7']
    ct, plen = g7['ciphertext'], g7['plaintext_length']
    L = len(K6)
    P = []
    for i, ch in enumerate(ct):
        s = K6[i] if i < L else P[i - L]
        P.append(ALPHA[(ALPHA.index(ch) - ALPHA.index(s)) % 26])
    K7 = ''.join(P)
    print(f"K7 = {K7}  (len {len(K7)}, expected {plen})")
    assert len(K7) == plen
    return K7


# ------------------------------------------------------------------- gate 8
def gate8(d, cands):
    maxlen = d['gate8']['max_length']
    models = [m for _, m in cands]
    n = len(models)

    def responses(word):
        return [run_word(m, word) for m in models]

    for length in range(1, maxlen + 1):
        for tup in itertools.product('01W', repeat=length):
            word = ''.join(tup)
            resp = responses(word)
            if len(set(resp)) == n:
                print(f"gate8: word {word} (len {length}) distinguishes all {n}")
                K8 = word.translate(str.maketrans('01W', 'ABC'))
                print(f"K8 = {K8}")
                return word, K8
    raise RuntimeError('no distinguishing word found')


# ------------------------------------------------------------------- gate 9
def gate9(d, K7, cands, g8word):
    g9 = d['gate9']
    blob = (PUB / g9['book_file']).read_bytes()
    ks = bytearray()
    j = 0
    while len(ks) < len(blob):
        ks += hashlib.sha256(b'OM2/BOOK' + b'\x00' + K7.encode('ascii')
                             + b'\x00' + j.to_bytes(4, 'big')).digest()
        j += 1
    plain = bytes(p ^ k for p, k in zip(blob, ks))
    got = hashlib.sha256(plain).hexdigest()
    print(f"gate9: book sha256 {got}")
    print(f"        expected {g9['book_plaintext_sha256']}")
    assert got == g9['book_plaintext_sha256'], 'keystream mismatch'
    book = json.loads(plain.decode('utf-8'))
    resp_map = book['responses'] if 'responses' in book else book
    print(f"gate9: book schema {book.get('schema')}, max_length "
          f"{book.get('max_length')}, {len(resp_map)} stored responses")

    resp = resp_map[g8word]
    matches = [(cid, m) for cid, m in cands if run_word(m, g8word) == resp]
    print(f"gate9: Gate 8 word response {resp!r} matches {len(matches)} model(s)")
    assert len(matches) == 1, matches
    mid, model = matches[0]
    print(f"gate9: selected model {mid} = {model}")

    R = run_word(model, g9['target_word'])
    K9 = token('OM2/G9' + '\n' + mid + '\n' + R)
    print(f"K9 = {K9}")
    return K9


# ------------------------------------------------------------------ gate 10
def gate10(d, keys):
    g10 = d['gate10']
    joined = ':'.join(keys)
    digest = hashlib.sha256(joined.encode('ascii')).digest()
    ct = bytes.fromhex(g10['ciphertext_hex'])
    n = len(ct)
    pw = bytes(a ^ b for a, b in zip(digest[:n], ct))
    print(f"gate10: {pw!r}  (expected length {g10['plaintext_length']})")
    assert len(pw) == g10['plaintext_length']
    return pw.decode('ascii')


def main():
    d = json.loads((PUB / 'instance.json').read_text())
    K1, K2, K3, K4 = gates_1_to_4(d)
    cands, K5 = gate5(d, K4)
    K6 = gate6(d, K5)
    K7 = gate7(d, K6)
    g8word, K8 = gate8(d, cands)
    K9 = gate9(d, K7, cands, g8word)
    keys = [K1, K2, K3, K4, K5, K6, K7, K8, K9]
    print("\nkeys:")
    for i, k in enumerate(keys, 1):
        print(f"  K{i} = {k}")
    pw = gate10(d, keys)
    print(f"\nFINAL PASSWORD: {pw}")
    print(f"as flag: CodeShell{{{pw}}}")


if __name__ == '__main__':
    main()

CodeShell{OBSERVATIONSEPARATESHYPOTHESES}