Ghost-In-The-Shellcode.py

#!/usr/bin/env python3
# Ghost-In-The-Shellcode v2.1 — RSA helper & 'prime bug' scanner
# Usage examples:
#   python3 ghost_shellcode_rsa.py
#   python3 ghost_shellcode_rsa.py -N 3233 -e 17 -c 2790,1515,1386,3124,2186,1197,2731,1386,1709,3124,765
#   python3 ghost_shellcode_rsa.py --scan-prime-bug --max 200000 --checker local
#
# Notes:
# - Decryption prints raw integers and several decoding attempts.
# - If the challenge uses a weird packing for plaintext blocks, check all variants printed.
# - 'Prime bug' scanner is a scaffold. Replace 'check_prime()' with your real oracle.

import argparse
import math
import random
from typing import Dict, List, Tuple, Optional

# ---------- Math utils ----------
def egcd(a: int, b: int) -> Tuple[int, int, int]:
    """Extended Euclidean Algorithm: returns (g, x, y) s.t. ax + by = g = gcd(a,b)."""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def modinv(a: int, m: int) -> int:
    """Modular inverse of a mod m. Raises ValueError if inverse doesn't exist."""
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError(f"No modular inverse for a={a} mod m={m} (gcd={g}).")
    return x % m

def is_probable_prime(n: int, k: int = 8) -> bool:
    """Miller-Rabin primality test."""
    if n < 2:
        return False
    small_primes = [2,3,5,7,11,13,17,19,23,29]
    for p in small_primes:
        if n % p == 0:
            return n == p
    # write n-1 = d * 2^r
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(k):
        a = random.randrange(2, n-1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for __ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def pollard_rho(n: int) -> int:
    """Pollard's Rho algorithm to find a non-trivial factor of n (if composite)."""
    if n % 2 == 0:
        return 2
    if is_probable_prime(n):
        return n
    while True:
        c = random.randrange(1, n)
        f = lambda x: (pow(x, 2, n) + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = math.gcd(abs(x - y), n)
        if d != n:
            return d

def factorize(n: int) -> Dict[int, int]:
    """Return prime factorization of n as {prime: exponent}."""
    def _factor(n: int, facs: Dict[int, int]):
        if n == 1:
            return
        if is_probable_prime(n):
            facs[n] = facs.get(n, 0) + 1
            return
        d = pollard_rho(n)
        _factor(d, facs)
        _factor(n // d, facs)
    facs: Dict[int, int] = {}
    _factor(n, facs)
    return dict(sorted(facs.items()))

def phi_from_factors(factors: Dict[int, int]) -> int:
    """Euler's totient from prime factorization."""
    # phi(n) = product over primes p of (p^e - p^(e-1)) = product(p^e * (1 - 1/p))
    phi = 1
    for p, e in factors.items():
        phi *= (p ** e - p ** (e - 1))
    return phi

# ---------- RSA decryption ----------
def rsa_decrypt(cipher: List[int], d: int, n: int) -> List[int]:
    return [pow(c, d, n) for c in cipher]

# ---------- Decoders / heuristics ----------
PRINTABLE_MIN, PRINTABLE_MAX = 32, 126

def as_ascii_single_bytes(blocks: List[int]) -> str:
    """Treat each m as a single byte if <=255, else '�'."""
    out = []
    for m in blocks:
        if 0 <= m <= 255:
            out.append(chr(m) if PRINTABLE_MIN <= m <= PRINTABLE_MAX else '�')
        else:
            out.append('�')
    return ''.join(out)

def as_bytes_big_endian(blocks: List[int]) -> str:
    """Map each m -> 2 bytes big-endian; keep printable, else '�'."""
    s = []
    for m in blocks:
        b = m.to_bytes(2, 'big', signed=False)  # 0..65535
        for byte in b:
            s.append(chr(byte) if PRINTABLE_MIN <= byte <= PRINTABLE_MAX else '�')
    return ''.join(s)

def as_bytes_little_endian(blocks: List[int]) -> str:
    s = []
    for m in blocks:
        b = m.to_bytes(2, 'little', signed=False)
        for byte in b:
            s.append(chr(byte) if PRINTABLE_MIN <= byte <= PRINTABLE_MAX else '�')
    return ''.join(s)

def base26_letters_zero_based(n: int) -> str:
    """Decode n in base-26 with A=0..Z=25."""
    if n == 0:
        return 'A'
    out = []
    while n > 0:
        n, r = divmod(n, 26)
        out.append(chr(ord('A') + r))
    return ''.join(reversed(out))

def decode_base26_for_blocks(blocks: List[int]) -> str:
    return ' '.join(base26_letters_zero_based(m) for m in blocks)

def smart_decimal_split(n: int) -> str:
    """
    Attempt to split the base-10 string of n into 2- or 3-digit ASCII codes (32..126)
    using DP to maximize printable chars; fall back to '?'.
    """
    s = str(n)
    L = len(s)
    dp = [None] * (L + 1)
    dp[0] = ""
    for i in range(L):
        if dp[i] is None:
            continue
        for w in (2, 3):
            if i + w <= L:
                chunk = int(s[i:i+w])
                if PRINTABLE_MIN <= chunk <= PRINTABLE_MAX:
                    cand = dp[i] + chr(chunk)
                    if dp[i + w] is None or len(cand) > len(dp[i + w]):
                        dp[i + w] = cand
    # prefer complete coverage; else take the best tail and mark the rest
    best = None
    for i in range(L, -1, -1):
        if dp[i] is not None:
            best = dp[i] + ('?' * (L - i))
            break
    return best if best is not None else '?' * L

def decode_decimal_split_for_blocks(blocks: List[int]) -> str:
    return ''.join(smart_decimal_split(m) for m in blocks)

# ---------- Prime bug scanner scaffold ----------
def is_prime(n: int) -> bool:
    return is_probable_prime(n)

def next_prime(n: int) -> int:
    if n <= 2:
        return 2
    p = n + 1 if n % 2 == 0 else n + 2
    while not is_probable_prime(p):
        p += 2
    return p

def check_prime(p: int, mode: str = "local") -> bool:
    """
    Replace this with your real oracle.
    Return True if the target CRASHES on p (i.e., bug triggered), else False.
    'mode' can be 'local' or 'http' — customize as needed.
    """
    # TODO: Implement your actual checker.
    # Example (HTTP):
    #   import requests
    #   r = requests.post('https://target/endpoint', json={'prime': p}, timeout=5)
    #   return r.status_code == 500 or 'divide by zero' in r.text.lower()
    #
    # Placeholder: never crash.
    return False

def scan_prime_bug(max_limit: int, start_from: int = 2, mode: str = "local") -> Optional[int]:
    """
    Iterate primes up to max_limit and call check_prime(p). Return the first 'bad' prime or None.
    """
    p = 2
    if start_from > 2:
        # move to the first prime >= start_from
        p = start_from if is_probable_prime(start_from) else next_prime(start_from)
    while p <= max_limit:
        if check_prime(p, mode=mode):
            return p
        p = next_prime(p)
    return None

# ---------- CLI ----------
def main():
    ap = argparse.ArgumentParser(description="RSA decrypt helper & prime-bug scanner (CTF utility)." )
    ap.add_argument("-N", "--modulus", type=int, default=3233, help="RSA modulus N")
    ap.add_argument("-e", "--exponent", type=int, default=17, help="RSA public exponent e")
    ap.add_argument("-c", "--cipher", type=str, default="2790,1515,1386,3124,2186,1197,2731,1386,1709,3124,765",
                    help="Comma-separated ciphertext integers")
    ap.add_argument("--scan-prime-bug", action="store_true", help="Run prime bug scanner instead of RSA decryption")
    ap.add_argument("--max", type=int, default=200000, help="Max prime to scan (when --scan-prime-bug)")
    ap.add_argument("--start", type=int, default=2, help="Start scanning from this integer (when --scan-prime-bug)")
    ap.add_argument("--checker", type=str, default="local", help="Checker mode for prime bug ('local' or 'http')")
    args = ap.parse_args()

    if args.scan_prime_bug:
        bad = scan_prime_bug(args.max, start_from=args.start, mode=args.checker)
        if bad is None:
            print(f"[prime-bug] No crashing prime found up to {args.max}.")
        else:
            print(f"[prime-bug] Found crashing prime: {bad}")
        return

    N = args.modulus
    e = args.exponent
    C = [int(x.strip()) for x in args.cipher.split(",") if x.strip()]

    print("[*] Input:")
    print(f"    N = {N}")
    print(f"    e = {e}")
    print(f"    C = {C}")

    print("\n[*] Factoring N ...")
    facs = factorize(N)
    print(f"    factors(N) = {facs}")
    phi = phi_from_factors(facs)
    print(f"    phi(N) = {phi}")

    try:
        d = modinv(e, phi)
    except ValueError as ex:
        print(f"[-] Couldn't compute d: {ex}")
        return
    print(f"    d (private exponent) = {d}")

    print("\n[*] Decrypting ...")
    M = rsa_decrypt(C, d, N)
    print(f"    Decrypted numeric blocks: {M}")

    print("\n[*] Decoding attempts (heuristics)")
    s1 = as_ascii_single_bytes(M)
    print(f"    ASCII-per-block (<=255 only): {repr(s1)}")

    s2 = as_bytes_big_endian(M)
    print(f"    2-byte big-endian bytes:      {repr(s2)}")

    s3 = as_bytes_little_endian(M)
    print(f"    2-byte little-endian bytes:   {repr(s3)}")

    s4 = decode_base26_for_blocks(M)
    print(f"    Base-26 A=0..Z blocks:        {repr(s4)}")

    s5 = decode_decimal_split_for_blocks(M)
    print(f"    Greedy decimal ASCII split:   {repr(s5)}")

    print("\n[!] If none are clean English, the challenge likely packs multiple chars per block in a custom way.")
    print("    Manually inspect the candidates above or adapt the decoders as needed (e.g., base-27 A=1..Z,space)." )

if __name__ == '__main__':
    main()