#!/usr/bin/env python3 """ Solver for the regex labyrinth challenge. The pattern in enc.txt is essentially: / (?=A)A (?=B)B / where A and B are enormous nested alternations of fixed-length byte strings. Because each lookahead is paired with the exact consuming part, every branch choice is forced to be the same on both sides, leaving a single valid string for each half. Concatenating the two halves yields the flag (a PNG QR code). """
from __future__ import annotations
from functools import lru_cache from pathlib import Path from typing importList, Optional, Tuple
text = Path("enc.txt").read_text()
classNode: __slots__ = ("typ", "children", "lit")
def__init__(self, typ: str, children: Optional[List["Node"]] = None, lit: bytes = b""): self.typ = typ self.children = children self.lit = lit
# --- Parser for the limited regex grammar: (?:...), (?=...), and \xNN literals. idx = 1# skip leading slash end = len(text) - 1# skip trailing slash
defparse_expr() -> Node: terms = [parse_term()] while idx < end and text[idx] == "|": advance(1) terms.append(parse_term()) return terms[0] iflen(terms) == 1else Node("alt", terms)
defparse_term() -> Node: factors: List[Node] = [] while idx < end and text[idx] notin")|/": factors.append(parse_factor()) ifnot factors: return Node("lit", lit=b"") # empty return factors[0] iflen(factors) == 1else Node("seq", factors)
defparse_factor() -> Node: if text.startswith("(?=", idx): advance(3) expr = parse_expr() expect(")") advance(1) return Node("look", [expr]) if text.startswith("(?:", idx): advance(3) expr = parse_expr() expect(")") advance(1) return expr # non-capturing group if text.startswith("\\x", idx): start = idx while text.startswith("\\x", idx): advance(4) seq = text[start:idx] data = bytes(int(seq[i + 2 : i + 4], 16) for i inrange(0, len(seq), 4)) return Node("lit", lit=data) raise ValueError(f"Unexpected token at {idx}: {text[idx:idx+10]!r}")
defadvance(n: int) -> None: global idx idx += n
defexpect(ch: str) -> None: if text[idx] != ch: raise ValueError(f"Expected {ch!r} at {idx}, found {text[idx]!r}")
root = parse_expr() assert text[idx] == "/"and idx == end, "Did not consume full pattern"
# --- Simplify: convert seq(look(X), Y) into logical AND of X and Y. classSNode: __slots__ = ("typ", "children", "lit", "length")
def__init__( self, typ: str, children: Optional[List["SNode"]] = None, lit: bytes = b"", length: int = 0, ): self.typ = typ self.children = children self.lit = lit self.length = length
defsimplify(node: Node) -> SNode: if node.typ == "lit": return SNode("lit", lit=node.lit, length=len(node.lit)) if node.typ == "alt": kids = [simplify(ch) for ch in node.children] return SNode("alt", children=kids, length=kids[0].length) if node.typ == "seq": a, b = node.children if a.typ == "look": left = simplify(a.children[0]) right = simplify(b) assert left.length == right.length return SNode("and", children=[left, right], length=left.length) left = simplify(a) right = simplify(b) return SNode("seq", children=[left, right], length=left.length + right.length) if node.typ == "look": return simplify(node.children[0]) raise ValueError(f"Unknown node type: {node.typ}")
defsimplify_half(seq_node: Node) -> SNode: # each half is seq(look(expr), expr) assert seq_node.typ == "seq"andlen(seq_node.children) == 2 return simplify(seq_node)
# --- Language evaluation with memoization and a small safety cap. LIMIT = 20000# sanity cap; actual sets stay size 1.
@lru_cache(None) deflanguage(node: SNode) -> Tuple[bytes, ...]: if node.typ == "lit": return (node.lit,) if node.typ == "alt": res = set() for ch in node.children: res.update(language(ch)) iflen(res) > LIMIT: raise MemoryError("Language exploded") returntuple(res) if node.typ == "seq": left = language(node.children[0]) right = language(node.children[1]) res = set() for a in left: for b in right: res.add(a + b) iflen(res) > LIMIT: raise MemoryError("Language exploded") returntuple(res) if node.typ == "and": lset = set(language(node.children[0])) rset = set(language(node.children[1])) returntuple(lset & rset) raise ValueError(f"Unknown SNode type: {node.typ}")
key2 = code[0x1ba:0x1ba+0x1e] enc = b"\xF5\x49\x91\x61\x4E\x3E\x6A\x39\xDD\x26\xA8\x42\x7D\xEC\x1F\x25" \ b"\x43\x5F\x69\xB7\xF7\xCD\x08\xC7\x6C\xBB\xBB\x3C" flag = bytes(enc[i] ^ key2[i] for i in range(len(enc))) print(flag)
pairs = {} for i, b inenumerate(code): if b == 0x1fand i + 2 < len(code): dest, idx = code[i + 1], code[i + 2] # 向后几步找 0x18 同目标寄存器的比较立即数 for j inrange(1, 10): k = i + j if k + 2 >= len(code): break if code[k] == 0x18and code[k + 1] == dest: pairs[idx] = code[k + 2] break
for k insorted(pairs): v = pairs[k] ch = chr(v) if32 <= v < 127else v print(f"{ch}",end='')
wechat
