UWSP Pointer Overflow CTF 2025 Writeup

import requests
import secrets
import json
from typing import Tuple

C = bytes([0xA5]) * 16
MASK128 = (1 << 128) - 1

def _to_u128(b: bytes) -> int:
    return int.from_bytes(b, "little")

def _from_u128(x: int) -> bytes:
    return x.to_bytes(16, "little")

def _rol13(x: int) -> int:
    return ((x << 13) | (x >> (128 - 13))) & MASK128

def _ror13(x: int) -> int:
    return ((x >> 13) | (x << (128 - 13))) & MASK128

def ashes_hash(msg: bytes) -> bytes:
    if len(msg) % 16 != 0:
        msg += b"\x00" * (16 - (len(msg) % 16))

    S = 0
    c = _to_u128(C)

    for i in range(0, len(msg), 16):
        m = _to_u128(msg[i:i+16])
        if ((i // 16) % 2) == 0:
            S = _rol13(S ^ m) ^ c
        else:
            S = _ror13(S ^ m) ^ c

    return _from_u128(S)

def pad_prefix_to_block(prefix: bytes) -> Tuple[bytes,int]:
    if len(prefix) % 16 == 0:
        return prefix, len(prefix) // 16
    pad_len = 16 - (len(prefix) % 16)
    return prefix + b"\x00" * pad_len, (len(prefix) + pad_len) // 16

def make_collision(prefix: bytes):
    pref_padded, first_idx = pad_prefix_to_block(prefix)

    A1 = secrets.token_bytes(16)
    A2 = secrets.token_bytes(16)

    while True:
        delta = secrets.token_bytes(16)
        if any(b != 0 for b in delta):
            break

    delta_int = _to_u128(delta)

    if first_idx % 2 == 0:
        rot_delta = _from_u128(_rol13(delta_int))
    else:
        rot_delta = _from_u128(_ror13(delta_int))

    B1 = bytes(a ^ b for a, b in zip(A1, delta))
    B2 = bytes(a ^ b for a, b in zip(A2, rot_delta))

    m1 = pref_padded + A1 + A2
    m2 = pref_padded + B1 + B2

    min_extra = 32
    extra_needed = max(0, min_extra - (len(m1) - len(prefix)))
    if extra_needed > 0:
        zeros = b"\x00" * extra_needed
        m1 += zeros
        m2 += zeros

    return m1, m2, first_idx

BASE = "https://crypto100-4.pointeroverflowctf.com"

def get_prefix():
    r = requests.post(f"{BASE}/prefix", timeout=10, verify=False)
    r.raise_for_status()
    j = r.json()
    return j["session_id"], j["prefix"]

def submit(sid, m1_hex, m2_hex):
    payload = {"session_id": sid, "m1_hex": m1_hex, "m2_hex": m2_hex}
    headers = {"Content-Type": "application/json"}
    r = requests.post(f"{BASE}/submit", data=json.dumps(payload),
                      headers=headers, timeout=10, verify=False) #自己証明書が使用されているため
    return r

def main():
    print("[*] GET /prefix...")
    sid, prefix = get_prefix()
    print("session_id:", sid)
    print("prefix:", prefix)

    pref_bytes = prefix.encode("ascii")

    print("[*] constructing collision...")
    m1, m2, idx = make_collision(pref_bytes)
    print("first custom block index:", idx)

    h1 = ashes_hash(m1)
    h2 = ashes_hash(m2)

    print("local hash1:", h1.hex())
    print("local hash2:", h2.hex())

    if h1 != h2:
        print("local collision failed")
        return

    m1_hex = m1.hex()
    m2_hex = m2.hex()

    print("[*] submitting messages...")
    resp = submit(sid, m1_hex, m2_hex)
    print("status:", resp.status_code)
    print("response:", resp.text)

if __name__ == "__main__":
    main()

import requests
import hashlib
import hmac
import math
from Crypto.Cipher import AES
from functools import reduce

# ターゲットサーバーの URL
BASE = "http://crypto200-2.pointeroverflowctf.com:11697"

# ---- HTTP ヘルパー関数 ----
def get_params():
    """
    /params から Diffie-Hellman パラメータ p と B を取得
    p, B は decimal string で返されるので int に変換
    """
    r = requests.get(BASE + "/params")
    r.raise_for_status()
    j = r.json()
    p = int(j["p"])
    B = int(j["B"])
    return p, B

def get_nonce():
    """
    /nonce から 32 バイトのランダム nonce を取得
    """
    r = requests.get(BASE + "/nonce")
    r.raise_for_status()
    return r.content

def get_ciphertext():
    """
    /ciphertext から暗号文を取得
    16 進文字列や base64 の場合も自動デコード
    """
    r = requests.get(BASE + "/ciphertext")
    r.raise_for_status()
    data = r.content.strip()
    try:
        return bytes.fromhex(data.decode())
    except Exception:
        import base64
        try:
            return base64.b64decode(data)
        except Exception:
            return data

def oracle_query(A_int):
    """
    /oracle に自作の公開値 A を送信し、サーバーが返す HMAC を取得
    A_int: 整数形式の公開値
    返り値: HMAC の hex 文字列
    """
    j = {"A": str(A_int)}
    r = requests.post(BASE + "/oracle", json=j)
    r.raise_for_status()
    jj = r.json()
    return jj["mac"]

# ---- 数学ヘルパー関数 ----
def egcd(a, b):
    """
    拡張ユークリッドの互除法
    ax + by = gcd(a,b) の整数解 x, y を返す
    """
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def crt_pair(a1, m1, a2, m2):
    """
    2 つの合同式を中国剰余定理 (CRT) で結合
    x ≡ a1 (mod m1), x ≡ a2 (mod m2) を解く
    """
    g, s, t = egcd(m1, m2)
    if (a1 - a2) % g != 0:
        return None
    l = m1 // g * m2
    x = (a1 * (m2//g) * t + a2 * (m1//g) * s) % l
    return (x % l, l)

def crt_list(congruences):
    """
    複数の合同式 [(a1,m1), (a2,m2), ...] を CRT で結合
    """
    x, m = congruences[0]
    for a2, m2 in congruences[1:]:
        res = crt_pair(x, m, a2, m2)
        if res is None:
            raise ValueError("CRT failed")
        x, m = res
    return x, m

# ---- 小さい素数生成 ----
def primes_upto(n):
    """
    エラトステネスの篩で n 以下の素数リストを作成
    """
    sieve = bytearray(b'\x01') * (n+1)
    sieve[0:2] = b'\x00\x00'
    for i in range(2, int(n**0.5)+1):
        if sieve[i]:
            step = i
            start = i*i
            sieve[start:n+1:step] = b'\x00' * (((n - start)//step) + 1)
    return [i for i, isprime in enumerate(sieve) if isprime]

# ---- 攻撃本体 ----
def find_order_of_element(a, p, max_check=2000):
    """
    a の位数（mod p）を調べる
    小さい素数で構築した a に対して正確な位数 s を求める
    """
    if a % p == 0:
        return 0
    cur = 1
    for k in range(1, max_check+1):
        cur = (cur * a) % p
        if cur == 1:
            return k
    return None

def try_small_walk():
    """
    短周期攻撃 ("short walk") を実行して秘密指数 x を復元
    -> AES キーを生成し、暗号文を復号
    """
    p, B = get_params()
    print("[*] p bitlen:", p.bit_length())
    nonce = get_nonce()
    print("[*] got nonce len:", len(nonce))

    p_byte_len = (p.bit_length() + 7) // 8

    # 小さな素数を大量に使って小さな位数の合同式を作る
    small_primes = primes_upto(1000)
    congruences = []
    total_mod = 1

    for r in small_primes:
        # 2^{(p-1)/r} を計算して、位数が r 以下の元を作る
        exp = (p - 1) // r
        A = pow(2, exp, p)
        if A == 1:
            continue
        s = find_order_of_element(A, p, max_check=r)
        if s is None or s == 1:
            continue
        print(f"[*] Trying r={r}, detected order s={s}; querying oracle...")
        mac_hex = oracle_query(A).lower().strip()

        # HMAC を順列で計算して、正しい t を特定
        found = False
        for t in range(s):
            K = pow(A, t, p)
            K_bytes = K.to_bytes(p_byte_len, 'big')
            hm = hmac.new(K_bytes, nonce, hashlib.sha256).hexdigest()
            if hm == mac_hex:
                print(f"[+] Found congruence: x ≡ {t} (mod {s})")
                congruences.append((t, s))
                total_mod *= s
                found = True
                break
        if not found:
            for t in range(s):
                K = pow(A, t, p)
                K_min = K.to_bytes((K.bit_length()+7)//8 or 1, 'big')
                hm = hmac.new(K_min, nonce, hashlib.sha256).hexdigest()
                if hm == mac_hex:
                    print(f"[+] Found congruence with minimal K_bytes: x ≡ {t} (mod {s})")
                    congruences.append((t, s))
                    total_mod *= s
                    found = True
                    break
        if not found:
            print(f"[-] No match for r={r} (order {s}) -- skipping")
        if total_mod > (1 << 128):
            print("[*] accumulated modulus > 2^128, trying CRT combine")
            break

    if not congruences:
        raise RuntimeError("No congruences found; try more/other small primes or different base")

    # 中国剰余定理で x を復元
    x_rec, mod = crt_list(congruences)
    print(f"[*] CRT result: x ≡ {x_rec} (mod {mod})")
    x = x_rec

    # AES キーを生成（問題文の指示に従う）
    x_bytes_16 = x.to_bytes(16, 'big')
    aes_key = hashlib.sha256(x_bytes_16 + b"short-walk").digest()
    print("[*] Derived AES key (sha256):", aes_key.hex())

    blob = get_ciphertext()
    iv = blob[:16]
    ct = blob[16:]
    nonce8 = iv[:8]
    init_ctr = int.from_bytes(iv[8:], 'big')

    # AES-CTR 復号（ECB でカウンター暗号）
    aes_ecb = AES.new(aes_key, AES.MODE_ECB)
    plain = bytearray()
    blocks = (len(ct) + 15) // 16
    for i in range(blocks):
        counter = init_ctr + i
        counter_block = nonce8 + counter.to_bytes(8, 'big')
        keystream = aes_ecb.encrypt(counter_block)
        chunk = ct[i*16:(i+1)*16]
        out = bytes(a ^ b for a, b in zip(chunk, keystream[:len(chunk)]))
        plain.extend(out)

    try:
        pt = plain.decode('utf-8')
    except:
        pt = plain.decode('latin-1', errors='replace')

    print("[*] Decrypted plaintext (maybe flag):")
    print(pt)
    return pt

if __name__ == "__main__":
    print("=== Starting short-walk exploit ===")
    plaintext = try_small_walk()
    print("=== Done ===")

=== Starting short-walk exploit ===
[*] p bitlen: 1035
[*] got nonce len: 32
[*] Trying r=3, detected order s=3; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 0 (mod 3)
[*] Trying r=7, detected order s=7; querying oracle...
[+] Found congruence: x ≡ 1 (mod 7)
[*] Trying r=11, detected order s=11; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 9 (mod 11)
[*] Trying r=13, detected order s=13; querying oracle...
[+] Found congruence: x ≡ 12 (mod 13)
[*] Trying r=17, detected order s=17; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 5 (mod 17)
[*] Trying r=19, detected order s=19; querying oracle...
[+] Found congruence: x ≡ 5 (mod 19)
[*] Trying r=23, detected order s=23; querying oracle...
[+] Found congruence: x ≡ 10 (mod 23)
[*] Trying r=29, detected order s=29; querying oracle...
[+] Found congruence: x ≡ 23 (mod 29)
[*] Trying r=31, detected order s=31; querying oracle...
[+] Found congruence: x ≡ 10 (mod 31)
[*] Trying r=37, detected order s=37; querying oracle...
[+] Found congruence: x ≡ 19 (mod 37)
[*] Trying r=41, detected order s=41; querying oracle...
[+] Found congruence: x ≡ 24 (mod 41)
[*] Trying r=43, detected order s=43; querying oracle...
[+] Found congruence: x ≡ 41 (mod 43)
[*] Trying r=47, detected order s=47; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 11 (mod 47)
[*] Trying r=53, detected order s=53; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 23 (mod 53)
[*] Trying r=59, detected order s=59; querying oracle...
[+] Found congruence: x ≡ 4 (mod 59)
[*] Trying r=61, detected order s=61; querying oracle...
[+] Found congruence: x ≡ 1 (mod 61)
[*] Trying r=67, detected order s=67; querying oracle...
[+] Found congruence: x ≡ 6 (mod 67)
[*] Trying r=71, detected order s=71; querying oracle...
[+] Found congruence: x ≡ 30 (mod 71)
[*] Trying r=73, detected order s=73; querying oracle...
[+] Found congruence: x ≡ 41 (mod 73)
[*] Trying r=79, detected order s=79; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 78 (mod 79)
[*] Trying r=83, detected order s=83; querying oracle...
[+] Found congruence with minimal K_bytes: x ≡ 16 (mod 83)
[*] Trying r=89, detected order s=89; querying oracle...
[+] Found congruence: x ≡ 58 (mod 89)
[*] Trying r=97, detected order s=97; querying oracle...
[+] Found congruence: x ≡ 36 (mod 97)
[*] Trying r=101, detected order s=101; querying oracle...
[+] Found congruence: x ≡ 67 (mod 101)
[*] Trying r=103, detected order s=103; querying oracle...
[+] Found congruence: x ≡ 7 (mod 103)
[*] accumulated modulus > 2^128, trying CRT combine
[*] CRT result: x ≡ 15607543889841794955 (mod 2398482352892522817270652163869225839621)
[*] Derived AES key (sha256): 3c57430602b494c48e604c53cf81718d2ef30f096440ff716c764fc5e3b7768c
[*] Decrypted plaintext (maybe flag):
poctf{uwsp_7h3_l16h7_4nd_7h3_d4rk}
=== Done ===

import requests

import urllib3

import base64

import math

from math import gcd

#サーバーが自己証明書を利用しているため

urllib3.disable_warnings(urllib3.exceptions.InsecureRequestWarning)

# ——————————————————————-

# 連分数 (continued fraction) 展開

#   e/N を連分数に展開する

# ——————————————————————-

def continued_fraction_expansion(a, b, max_iters=10000):

    cf = []

    x, y = a, b

    for _ in range(max_iters):

        if y == 0:

            break

        q = x // y

        cf.append(q)

        x, y = y, x – q * y

        if y == 0:

            break

    return cf

# ——————————————————————-

# convergents 計算

#   連分数 cf から(K_i, D_i) の候補列を生成する。

# ——————————————————————-

def convergents_from_cf(cf):

    convs = []

    for i in range(len(cf)):

        num, den = 1, 0

        for q in reversed(cf[:i+1]):

            num, den = q * num + den, num

        convs.append((num, den))

    return convs

# ——————————————————————-

# 拡張ユークリッドで逆元を計算

# ——————————————————————-

def modinv(a, m):

    a = a % m

    if a == 0:

        return None

    g, x, y = extended_gcd(a, m)

    if g != 1:

        return None

    return x % m

# ——————————————————————-

# 拡張ユークリッド互除法

# ——————————————————————-

def extended_gcd(a, b):

    if b == 0:

        return (a, 1, 0)

    g, x1, y1 = extended_gcd(b, a % b)

    return (g, y1, x1 – (a // b) * y1)

# ——————————————————————-

# 完全平方判定

#   n が平方数なら √n を返す。それ以外は None

# ——————————————————————-

def is_perfect_square(n):

    if n < 0:

        return None

    r = int(math.isqrt(n))

    if r * r == n:

        return r

    return None

# ——————————————————————-

# バイト変換 (RSA 復号後の整数 m → バイト列)

# ——————————————————————-

def int_to_bytes(i):

    length = (i.bit_length() + 7) // 8

    return i.to_bytes(length, “big”)

# ——————————————————————-

# Wiener攻撃

#   連分数 → convergents から d 候補を生成していき

#   φ(N), p, q を再構築し、正しい場合は成功。

# ——————————————————————-

def wiener_attack(e, N):

    cf = continued_fraction_expansion(e, N)

    convs = convergents_from_cf(cf)

    for (k, d_candidate) in convs:

        if k == 0:

            continue

        # (e*d – 1) / k が整数でなければ d 候補ではない

        if (e * d_candidate – 1) % k != 0:

            continue

        phi_candidate = (e * d_candidate – 1) // k

        # p+q を s とすると s = N – phi(N) + 1

        s = N – phi_candidate + 1

        discr = s * s – 4 * N

        # 判別式が平方数なら二次方程式が解ける

        if discr >= 0:

            t = is_perfect_square(discr)

            if t is not None:

                p = (s + t) // 2

                q = (s – t) // 2

                if p * q == N:

                    return int(d_candidate), int(p), int(q)

    return None, None, None

# ——————————————————————-

# メイン処理

#   1. /pubkey を取得

#   2. N,e を読み取り

#   3. /ciphertext を取得し Base64 デコード

#   4. Wiener攻撃で d,p,q を復元

#   5. RSA 復号してフラグを表示

# ——————————————————————-

def main():

    base = “https://crypto400.pointeroverflowctf.com”

    pubkey_url = base + “/pubkey”

    ct_url = base + “/ciphertext”

    print(“[*] fetching pubkey (verify=False)”)

    r = requests.get(pubkey_url, timeout=10, verify=False)

    r.raise_for_status()

    pub = r.json()

    N = int(pub[“n”], 16)    # n は16進文字列

    e = int(pub[“e”], 16)    # e も16進

    k = pub.get(“k”, None)  # ciphertext の長さ（bytes）

    print(“[*] N:”, N)

    print(“[*] e:”, e)

    print(“[*] k:”, k)

    print(“[*] fetching ciphertext (verify=False)”)

    r = requests.get(ct_url, timeout=10, verify=False)

    r.raise_for_status()

    c_b64 = r.json()[“c_b64”]

    c = int.from_bytes(base64.b64decode(c_b64), “big”)

    print(“[*] trying…”)

    d, p, q = wiener_attack(e, N)

    if d:

        print(“[+] d:”, d)

        print(“[+] p:”, p)

        print(“[+] q:”, q)

        # 復号 m = c^d mod N

        m = pow(c, d, N)

        m_bytes = int_to_bytes(m)

        try:

            print(“[+] plaintext:”, m_bytes.decode())

        except:

            print(“[+] plaintext (hex):”, m_bytes.hex())

    else:

        print(“[-] failed”)

if __name__ == “__main__”:

    main()

using System;

// Token: 0x02000002 RID: 2

public class Program

{

    // Token: 0x06000002 RID: 2 RVA: 0x00002058 File Offset: 0x00000258

    public static void Main()

    {

        int num = 0;

        int num2;

        for (;;)

        {

            switch (num)

            {

            case 0:

            {

                int[] array = new int[]

                {

                    71,

                    88,

                    84,

                    67,

                    81,

                    76,

                    66,

                    64,

                    68,

                    71,

                    104,

                    2,

                    7,

                    90,

                    4,

                    104,

                    81,

                    91,

                    3,

                    1,

                    104,

                    0,

                    95,

                    6,

                    2,

                    104,

                    0,

                    66,

                    69,

                    89,

                    4,

                    83,

                    104,

                    7,

                    66,

                    0,

                    104,

                    0,

                    7,

                    104,

                    85,

                    4,

                    74

                };

                num2 = 0;

                string text = Console.ReadLine();

                if (text == null)

                {

                    return;

                }

                if (text.Length != 43)

                {

                    goto Block_2;

                }

                num = 1;

                continue;

            }

            case 1:

                for (int i = 0; i < 6; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 2;

                continue;

            case 2:

                for (int i = 6; i < 12; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 3;

                continue;

            case 3:

                for (int i = 12; i < 18; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 4;

                continue;

            case 4:

                for (int i = 18; i < 24; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 5;

                continue;

            case 5:

                for (int i = 24; i < 30; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 6;

                continue;

            case 6:

                for (int i = 30; i < 36; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 7;

                continue;

            case 7:

                for (int i = 36; i < 43; i++)

                {

                    int[] array;

                    string text;

                    if ((int)(text.get_Chars(i) ^ ‘7’) != array[i])

                    {

                        num2++;

                    }

                }

                num = 8;

                continue;

            case 8:

                goto IL_27E;

            }

            return;

        }

        return;

        Block_2:

        Console.WriteLine(“nope”);

        return;

        IL_27E:

        if (num2 == 0)

        {

            Console.WriteLine(“Correct!”);

            return;

        }

        Console.WriteLine(“nope”);

    }

}