Random LCG – Cryptography Challenge Writeup | 07CTF

Oneliner:

Being honest with you solving this problem alone is totally impossible for me. I need full assist from my AI. And after some fighting and debate with my AI. We both figure out A solver script which solve this problem. But before that It's theory time, Did you really think you can pass without listening my lecture? :3

Understanding:

1. The title means a lot, It suggest us that the Cipher is Linear Congruential Generators(LCGs).
2. And the first part of the Title says Random. And the challange.py exactly tell us MT19937 is used. It's a tough one and In short, one of my most hatred fellow
3. Others normal stuff like: Temparing, Xor, Bignumber modular etc are used

Analyzing(useless):

1. The one and Only damaging part of this challange is Reversing MT19937. Because it's born to be a g*y.
2. I am not going to explain everything because even I don't understand some of its concept :3 So here is a brief overview what I imagine from this challange and Established a debate with my AI

Overview:

1. Cut the flag into 8-byte pieces like a cake
2. Then the piece is XOR with the LCG random Number and save in enc
3. Then somehow I don't understand it generate another 64 byte and print it as hint

that is the simplest explanations I can ever image. But deep inside it's totally Nasty. Oh yes lastly a honerable mension, Specially which makes the things much much easier. it's non but a python library called extend_mt19937_predictor THE LIFE SAVIOUR. I wish I could say what and how it does things. But Sorry too irrelevent for this Challange.

DO SOME HOMEWORK FELLOWS

THE MAIN EVENT:

here is the solver script, RUN it and go home

#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes
from extend_mt19937_predictor import ExtendMT19937Predictor

OUT_FILE = "out.txt"


def load_data(path=OUT_FILE):
    ctx = {}
    with open(path, "r") as f:
        code = f.read()
    # out.txt is of the form:
    # b = ...
    # p = ...
    # enc = [...]
    # hint = [...]
    exec(code, {}, ctx)
    b = ctx["b"]
    p = ctx["p"]
    enc = ctx["enc"]
    hint = ctx["hint"]
    return b, p, enc, hint


def recover_multipliers_from_hint(b, p, hint):
    """
    hint[i]   = seed_{Nenc+1+i}
    hint[i+1] = seed_{Nenc+2+i}

    seed_{k+1} = m_k * seed_k + b (mod p)

    => m_{Nenc+1+i} = (hint[i+1] - b) * inv(hint[i]) mod p
    """
    m_list = []
    for i in range(len(hint) - 1):
        s = hint[i]
        s_next = hint[i + 1]
        m = (s_next - b) * inverse(s, p) % p
        m_list.append(m)
    return m_list  # 63 values


def clone_and_find_early_values(m_list, b, n_enc):
    """
    m_list are 63 consecutive outputs of random.getrandbits(512),
    corresponding to m_{Nenc+1}..m_{Nenc+63}.

    We:
      - feed them into ExtendMT19937Predictor,
      - backtrack enough 512-bit outputs to encounter b,
      - then read seed0 and m0..m_{Nenc-1} from the backtracked list.
    """
    predictor = ExtendMT19937Predictor(check=False)

    # Feed all known 512-bit outputs in order:
    for m in m_list:
        predictor.setrandbits(m, 512)

    history = []
    max_back = 200  # plenty: total 512-bit calls are 3 + n_enc + 64 <= ~80
    idx_b = None

    for i in range(max_back):
        v = predictor.backtrack_getrandbits(512)
        history.append(v)
        if v == b:
            # First time we hit b in history.
            # Ensure we have enough newer outputs after b to pull seed0 and m0..m_{n_enc-1}
            if i >= 1 + n_enc:
                idx_b = i
                break

    if idx_b is None:
        raise RuntimeError("Failed to locate b while backtracking; check assumptions / out.txt.")

    # history[0] is most recent, history[1] previous, etc.
    # history[idx_b] == b.
    seed0 = history[idx_b - 1]

    m_prefix = []
    for i in range(n_enc):
        # m0 is the output immediately after seed0 in time, i.e. history[idx_b - 2]
        m_prefix.append(history[idx_b - 2 - i])

    return seed0, m_prefix


def decrypt_flag(b, p, enc, seed0, m_prefix):
    """
    LCG recurrence:

      seed_{k+1} = (m_k * seed_k + b) mod p

    Encryption:

      enc[i] = seed_{i+1} ^ chunk[i]
    """
    seed = seed0
    out = b""
    for i, ct in enumerate(enc):
        m_i = m_prefix[i]
        seed = (m_i * seed + b) % p
        pt_int = seed ^ ct
        out += long_to_bytes(pt_int)

    # Strip trailing zeros from last partial 8-byte chunk
    return out.rstrip(b"\x00")


def main():
    b, p, enc, hint = load_data()
    print("[+] Loaded data from out.txt")
    print(f"[+] Number of ciphertext blocks: {len(enc)}")

    m_from_hint = recover_multipliers_from_hint(b, p, hint)
    print(f"[+] Recovered {len(m_from_hint)} consecutive m values from hint")

    seed0, m_prefix = clone_and_find_early_values(m_from_hint, b, len(enc))
    print("[+] Recovered seed0 and first", len(m_prefix), "m values from MT backtracking")

    flag = decrypt_flag(b, p, enc, seed0, m_prefix)
    print("[+] Flag:", flag.decode(errors="ignore"))


if __name__ == "__main__":
    main()