The Gentlemen

#!/usr/bin/env python3
"""Recherche, dans un dump mémoire, les clés par fichier du rançongiciel "The Gentlemen".

Usage défensif : récupération de données après infection. Lecture seule sur les
entrées ; les fichiers récupérés sont écrits dans --out.

Modèle (SHA-256 3ab95752…c9235, analyse statique, voir RAPPORT_ANALYSE.md) :
  priv_eph  = 32 octets aléatoires (par fichier)
  pub_eph   = X25519(priv_eph, 9)            -> dans le pied "--eph--<base64>"
  partagé   = X25519(priv_eph, pub_attaquant)
  tampon    = partagé || pub_eph             (64 o, tas Go, jamais effacé)
  clé       = tampon[0:32] ; nonce24 = tampon[32:56] = pub_eph[0:24]
  XChaCha20 : sous-clé = HChaCha20(clé, nonce24[:16]) ; nonce12 = 0000 || nonce24[16:]
  <= 1 MiB : tout le fichier, un seul flux
  >  1 MiB : 3 blocs de B = int(taille*ratio) octets aux offsets 0, off1, 2*off1
             avec off1 = (taille-3B)/2 + B ; nonce24[23] ^= indice du bloc

Sources de clé cherchées, ancrées sur pub_eph (connue grâce au pied) :
  key     32 octets juste avant pub_eph (tampon partagé||pub) et fenêtres voisines
  priv    fenêtre de 32 octets dont X25519(f, 9) == pub_eph (test exact)
  subkey  structure du chiffreur : sous-clé(32) compteur(4) 0000||nonce[16:24]
Option --scan-priv : balaye tout le dump à la recherche de clés privées (sans ancre).
"""
import argparse
import base64
import json
import os
import re
import struct
import sys
import tempfile
from concurrent.futures import ProcessPoolExecutor

import numpy as np
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey, X25519PublicKey
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat

ATTACKER_PUB = bytes.fromhex("fcb11717cab989424755a957c1d55361b119de4fdcfecdb2f2e56b15ad801922")
FULL_LIMIT = 0x100000
RATIOS = {"": 0.09, "fast": 0.03, "super": 0.01, "ultra": 0.003}
FOOTER_RE = re.compile(
    rb"--eph--([A-Za-z0-9+/=_-]{43,44})\n--marker--GENTLEMEN\nGENTLEMEN(?:--(fast|super|ultra)--\n)?\Z")
BASEPOINT = (9).to_bytes(32, "little")
MAGICS = [(b"MZ\x90\x00", "pe"), (b"PK\x03\x04", "zip/office"), (b"%PDF-", "pdf"),
          (b"\x89PNG\r\n\x1a\n", "png"), (b"\xff\xd8\xff", "jpeg"), (b"GIF8", "gif"),
          (b"7z\xbc\xaf\x27\x1c", "7z"), (b"Rar!", "rar"), (b"\xd0\xcf\x11\xe0\xa1\xb1\x1a\xe1", "ole2"),
          (b"SQLite format 3\x00", "sqlite"), (b"RIFF", "riff"), (b"OggS", "ogg"), (b"ID3", "mp3"),
          (b"<?xml", "xml"), (b"{\\rtf", "rtf"), (b"\x7fELF", "elf")]


# ---------------------------------------------------------------- primitives
def _rotl(v, n):
    return ((v << n) & 0xFFFFFFFF) | (v >> (32 - n))


def hchacha20(key, nonce16):
    s = list(struct.unpack("<4I", b"expand 32-byte k")) + list(struct.unpack("<8I", key)) \
        + list(struct.unpack("<4I", nonce16))

    def qr(a, b, c, d):
        s[a] = (s[a] + s[b]) & 0xFFFFFFFF; s[d] = _rotl(s[d] ^ s[a], 16)
        s[c] = (s[c] + s[d]) & 0xFFFFFFFF; s[b] = _rotl(s[b] ^ s[c], 12)
        s[a] = (s[a] + s[b]) & 0xFFFFFFFF; s[d] = _rotl(s[d] ^ s[a], 8)
        s[c] = (s[c] + s[d]) & 0xFFFFFFFF; s[b] = _rotl(s[b] ^ s[c], 7)

    for _ in range(10):
        qr(0, 4, 8, 12); qr(1, 5, 9, 13); qr(2, 6, 10, 14); qr(3, 7, 11, 15)
        qr(0, 5, 10, 15); qr(1, 6, 11, 12); qr(2, 7, 8, 13); qr(3, 4, 9, 14)
    return struct.pack("<8I", *(s[0:4] + s[12:16]))


def chacha_stream(key, nonce12, counter=0):
    enc = Cipher(algorithms.ChaCha20(key, struct.pack("<I", counter) + nonce12), mode=None).encryptor()
    return enc.update


def xchacha_stream(key, nonce24):
    return chacha_stream(hchacha20(key, nonce24[:16]), b"\0\0\0\0" + nonce24[16:])


def block_nonce(pub, index):
    n = bytearray(pub[:24])
    n[23] ^= index
    return bytes(n)


def x25519_pub(priv):
    return X25519PrivateKey.from_private_bytes(priv).public_key().public_bytes(Encoding.Raw, PublicFormat.Raw)


def x25519_shared(priv, peer):
    return X25519PrivateKey.from_private_bytes(priv).exchange(X25519PublicKey.from_public_bytes(peer))


# ---------------------------------------------------------------- fichiers chiffrés
def parse_encrypted(path):
    size = os.path.getsize(path)
    with open(path, "rb") as f:
        f.seek(max(0, size - 256))
        tail = f.read()
    i = tail.rfind(b"--eph--")
    m = FOOTER_RE.match(tail, i) if i >= 0 else None
    if not m:
        return None
    b64 = m.group(1).decode().replace("-", "+").replace("_", "/")
    try:
        pub = base64.b64decode(b64 + "=" * (-len(b64) % 4))
    except Exception:
        return None
    if len(pub) != 32:
        return None
    mode = (m.group(2) or b"").decode()
    orig = size - (len(tail) - i)
    return {"path": path, "pub": pub, "mode": mode, "size": orig, "blocks": blocks(orig, mode)}


def blocks(size, mode):
    if size <= FULL_LIMIT:
        return [(0, size, 0)]
    b = int(size * RATIOS[mode])
    off1 = (size - 3 * b) // 2 + b
    return [(0, b, 0), (off1, b, 1), (2 * off1, b, 2)]


def collect(paths):
    out = []
    for p in paths:
        files = [os.path.join(r, f) for r, _, fs in os.walk(p) for f in fs] if os.path.isdir(p) else [p]
        for f in files:
            e = parse_encrypted(f)
            if e:
                out.append(e)
    return out


# ---------------------------------------------------------------- recherche mémoire
def find_prefix8(path, targets):
    """Offsets (tout alignement) de chaque préfixe de 8 octets. targets: {bytes8: tag}."""
    keys = np.array(sorted({struct.unpack("<Q", t)[0] for t in targets}), dtype=np.uint64)
    arr = np.memmap(path, dtype=np.uint8, mode="r")
    chunk = 1 << 26
    hits = {}
    for base in range(0, len(arr), chunk):
        seg = arr[base:base + chunk + 8]
        for shift in range(8):
            sub = seg[shift:]
            n = (len(sub) // 8) * 8
            if n < 8:
                continue
            words = np.ascontiguousarray(sub[:n]).view(np.uint64)
            idx = np.searchsorted(keys, words)
            idx[idx == len(keys)] = 0
            for p in np.nonzero(keys[idx] == words)[0]:
                off = base + shift + int(p) * 8
                if off < base + chunk:
                    hits.setdefault(struct.pack("<Q", int(words[p])), []).append(off)
    return arr, hits


def good_window(w):
    return w.count(0) <= 3 and len(set(w)) >= 16


def _priv_chunk(args):
    path, s0, n, pubset = args
    arr = np.memmap(path, dtype=np.uint8, mode="r")
    region = arr[s0:s0 + 8 * n + 24]
    n = min(n, (len(region) - 24) // 8)
    if n <= 0:
        return []
    win = np.lib.stride_tricks.as_strided(region, shape=(n, 32), strides=(8, 1))
    keep = (win == 0).sum(1) <= 1
    srt = np.sort(win, axis=1)
    keep &= (1 + (np.diff(srt, axis=1) != 0).sum(1)) >= 24
    found = []
    for k in np.nonzero(keep)[0]:
        cand = bytes(win[k])
        if x25519_pub(cand) in pubset:
            found.append((s0 + 8 * int(k), cand))
    return found


def scan_priv(path, pubs, shifts, workers):
    size = os.path.getsize(path)
    per = 1 << 21
    jobs = [(path, sh + 8 * k0, per, pubs) for sh in shifts for k0 in range(0, max(0, (size - sh - 32) // 8), per)]
    found = []
    with ProcessPoolExecutor(workers) as ex:
        for i, r in enumerate(ex.map(_priv_chunk, jobs)):
            found += r
            if i % 50 == 0:
                print(f"  scan priv {i}/{len(jobs)}", file=sys.stderr)
    return found


# ---------------------------------------------------------------- plausibilité
def entropy(b):
    if not b:
        return 0.0
    c = np.bincount(np.frombuffer(b, dtype=np.uint8), minlength=256)
    p = c[c > 0] / len(b)
    return float(-(p * np.log2(p)).sum())


def plausible(data):
    for m, name in MAGICS:
        if data.startswith(m):
            return "magic:" + name
    if len(data) >= 256 and entropy(data[:4096]) < 6.0:
        return "entropie-basse"
    if len(data) >= 32 and sum(32 <= c < 127 or c in (9, 10, 13) for c in data[:512]) >= 0.95 * min(len(data), 512):
        return "texte"
    return None


class Cand:
    def __init__(self, kind, data, offset, nonce12=None, index=0, exact=False):
        self.kind, self.data, self.offset, self.nonce12, self.index, self.exact = kind, data, offset, nonce12, index, exact

    def stream(self, pub, index):
        if self.kind == "key":
            return xchacha_stream(self.data, block_nonce(pub, index))
        return chacha_stream(self.data, self.nonce12)

    def covers(self, index):
        return self.kind == "key" or index == self.index


def trial(entry, cand):
    covered = [b for b in entry["blocks"] if cand.covers(b[2]) and b[1] > 0]
    if not covered:
        return None
    off, ln, i = covered[0]
    with open(entry["path"], "rb") as f:
        f.seek(off)
        ct = f.read(min(ln, 4096))
    return plausible(cand.stream(entry["pub"], i)(ct))


def write_recovered(entry, cand, out_dir):
    done = [b for b in entry["blocks"] if cand.covers(b[2])]
    name = os.path.basename(entry["path"]) + (".recovered" if len(done) == len(entry["blocks"]) else ".partial")
    dst = os.path.join(out_dir, name)
    with open(entry["path"], "rb") as src, open(dst, "wb") as out:
        left = entry["size"]
        while left:
            buf = src.read(min(left, 1 << 20))
            out.write(buf)
            left -= len(buf)
        for off, ln, i in done:
            ks = cand.stream(entry["pub"], i)
            src.seek(off)
            out.seek(off)
            while ln > 0:
                buf = src.read(min(ln, 1 << 16))
                out.write(ks(buf))
                ln -= len(buf)
    return dst, len(done), len(entry["blocks"])


# ---------------------------------------------------------------- recherche principale
def recover(dump, entries, out_dir, window=128, do_scan_priv=False, shifts=(0,), workers=None, attacker_pub=ATTACKER_PUB):
    by_pub = {e["pub"]: e for e in entries}
    targets = {}
    for e in entries:
        targets[e["pub"][:8]] = ("pub", e)
        for i in range(3):
            targets[block_nonce(e["pub"], i)[16:24]] = ("nonce", e, i)
    arr, hits = find_prefix8(dump, {k: 1 for k in targets})
    cands = {e["path"]: [] for e in entries}

    def priv_cand(e, priv, off):
        c = Cand("key", x25519_shared(priv, attacker_pub), off, exact=True)
        cands[e["path"]].append(c)

    for pre, offs in hits.items():
        # deux fichiers pourraient partager un préfixe de 8 octets : on re-vérifie contre chaque entrée
        for e in entries:
            if pre == e["pub"][:8]:
                for o in offs:
                    if bytes(arr[o:o + 32]) != e["pub"]:
                        continue
                    lo = max(0, o - window)
                    ctx = bytes(arr[lo:o + 32 + window])
                    base = o - lo
                    if base >= 32:
                        cands[e["path"]].append(Cand("key", ctx[base - 32:base], o - 32))
                    for rel in range(-window, window + 1, 8):
                        p = base + rel
                        if p < 0 or p + 32 > len(ctx):
                            continue
                        w = ctx[p:p + 32]
                        if not good_window(w):
                            continue
                        if rel != -32:
                            cands[e["path"]].append(Cand("key", w, o + rel))
                        if x25519_pub(w) == e["pub"]:
                            priv_cand(e, w, o + rel)
            for i in range(3):
                if pre == block_nonce(e["pub"], i)[16:24]:
                    for o in offs:
                        if o >= 40 and bytes(arr[o - 4:o]) == b"\0\0\0\0":
                            cands[e["path"]].append(Cand("subkey", bytes(arr[o - 40:o - 8]), o - 40,
                                                         nonce12=bytes(arr[o - 4:o + 8]), index=i))
    if do_scan_priv:
        for off, priv in scan_priv(dump, set(by_pub), shifts, workers):
            priv_cand(by_pub[x25519_pub(priv)], priv, off)

    report = []
    for e in entries:
        seen, best = set(), None
        for c in cands[e["path"]]:
            sig = (c.kind, c.data, c.index)
            if sig in seen:
                continue
            seen.add(sig)
            why = "pub-match" if c.exact else trial(e, c)
            if why and (best is None or (c.exact and not best[0].exact)):
                best = (c, why)
        row = {"file": e["path"], "mode": e["mode"] or "défaut", "size": e["size"], "candidats": len(seen)}
        if best:
            dst, nb, tot = write_recovered(e, best[0], out_dir)
            row.update(recovered=dst, blocks=f"{nb}/{tot}", source=best[0].kind, dump_offset=best[0].offset,
                       confidence=best[1], key=best[0].data.hex() if best[0].kind == "key" else None)
        else:
            row["recovered"] = None
        report.append(row)
    return report


# ---------------------------------------------------------------- auto-test synthétique
def model_encrypt(plain, attacker_pub, mode, eph_priv):
    pub = x25519_pub(eph_priv)
    key = x25519_shared(eph_priv, attacker_pub)
    ct = bytearray(plain)
    for off, ln, i in blocks(len(plain), mode):
        ct[off:off + ln] = xchacha_stream(key, block_nonce(pub, i))(plain[off:off + ln])
    suffix = f"--{mode}--\n".encode() if mode else b""
    footer = b"--eph--" + base64.b64encode(pub) + b"\n--marker--GENTLEMEN\nGENTLEMEN" + suffix
    return bytes(ct) + footer, pub, key


def selftest():
    expected = bytes.fromhex("82413b4227b27bfed30e42508a877d73a0f9e4d58a74a853c12ec41326d3ecdc")
    got = hchacha20(bytes(range(32)), bytes.fromhex("000000090000004a0000000031415927"))
    assert got == expected, "HChaCha20 : vecteur de test RFC (draft-irtf-cfrg-xchacha) non respecté"
    print("HChaCha20 : vecteur de référence OK")
    tmp = tempfile.mkdtemp(prefix="gmk_")
    att_priv = os.urandom(32)
    att_pub = x25519_pub(att_priv)
    text = (b"%PDF-1.7\n" + b"Rapport trimestriel confidentiel. " * 100000)

    def mk(name, size, mode):
        plain = (text * (size // len(text) + 1))[:size]
        priv = os.urandom(32)
        ct, pub, key = model_encrypt(plain, att_pub, mode, priv)
        p = os.path.join(tmp, name)
        open(p, "wb").write(ct)
        return plain, priv, pub, key, p

    cases = {n: mk(n, s, m) for n, s, m in [("A.pdf", 300_000, ""), ("B.pdf", 3_000_000, "fast"),
                                           ("C.pdf", 2_000_000, "ultra"), ("D.pdf", 400_000, ""),
                                           ("E.pdf", 1_500_000, "super")]}
    dump = bytearray(os.urandom(6 << 20))
    for k in range(0, len(dump), 4096):                       # zones « pointeurs » peu aléatoires
        dump[k:k + 2048] = (b"\x56\x34\x12\x00\xc0\x00\x00\x00" * 256)

    def put(off, data):
        dump[off:off + len(data)] = data

    plainA, privA, pubA, keyA, _ = cases["A.pdf"]
    put(1_000_003, keyA + pubA)                               # tampon partagé||pub, adresse non alignée
    plainB, privB, pubB, keyB, _ = cases["B.pdf"]
    put(3_000_000, privB)                                     # clé privée seule, loin de toute ancre
    plainC, privC, pubC, keyC, _ = cases["C.pdf"]
    sub = hchacha20(keyC, block_nonce(pubC, 1)[:16])
    put(2_000_011, sub + struct.pack("<I", 7) + b"\0\0\0\0" + block_nonce(pubC, 1)[16:24])
    plainE, privE, pubE, keyE, _ = cases["E.pdf"]
    put(4_500_000, pubE + bytes(24) + privE)                  # clé privée à proximité de pub
    dump_path = os.path.join(tmp, "dump.bin")
    open(dump_path, "wb").write(bytes(dump))

    out = os.path.join(tmp, "out")
    os.makedirs(out)
    entries = collect([tmp + "/A.pdf", tmp + "/B.pdf", tmp + "/C.pdf", tmp + "/D.pdf", tmp + "/E.pdf"])
    rep = recover(dump_path, entries, out, do_scan_priv=True, workers=4, attacker_pub=att_pub)
    ok = True
    for r in rep:
        name = os.path.basename(r["file"])
        plain = cases[name][0]
        if name == "D.pdf":
            good = r["recovered"] is None
        elif name == "C.pdf":
            blk = blocks(len(plain), "ultra")[1]
            data = open(r["recovered"], "rb").read() if r["recovered"] else b""
            good = bool(data) and r["blocks"] == "1/3" and data[blk[0]:blk[0] + blk[1]] == plain[blk[0]:blk[0] + blk[1]]
        else:
            good = bool(r["recovered"]) and open(r["recovered"], "rb").read() == plain
        ok &= good
        print(f"  {name}: {'OK' if good else 'ECHEC'}  source={r.get('source')} blocs={r.get('blocks')} {r.get('confidence')}")
    print("auto-test :", "RÉUSSI" if ok else "ÉCHEC", f"(fichiers dans {tmp})")
    return 0 if ok else 1


def main():
    ap = argparse.ArgumentParser(description=__doc__, formatter_class=argparse.RawDescriptionHelpFormatter)
    sub = ap.add_subparsers(dest="cmd", required=True)
    sub.add_parser("selftest", help="valide l'outil sur un cas synthétique")
    r = sub.add_parser("recover")
    r.add_argument("--dump", required=True)
    r.add_argument("--encrypted", nargs="+", required=True, help="fichiers ou dossiers chiffrés")
    r.add_argument("--out", required=True)
    r.add_argument("--window", type=int, default=128)
    r.add_argument("--scan-priv", action="store_true", help="balayage complet du dump (lent)")
    r.add_argument("--priv-shifts", default="0", help="décalages d'alignement testés, ex. 0 ou 0-7")
    r.add_argument("--workers", type=int, default=os.cpu_count())
    a = ap.parse_args()
    if a.cmd == "selftest":
        return selftest()
    lo, _, hi = a.priv_shifts.partition("-")
    shifts = range(int(lo), int(hi or lo) + 1)
    os.makedirs(a.out, exist_ok=True)
    entries = collect(a.encrypted)
    print(f"{len(entries)} fichier(s) avec pied GENTLEMEN valide", file=sys.stderr)
    rep = recover(a.dump, entries, a.out, a.window, a.scan_priv, shifts, a.workers)
    json.dump(rep, sys.stdout, indent=1, ensure_ascii=False)
    print()
    return 0


if __name__ == "__main__":
    sys.exit(main())