STACK The Flags 2022 Writeups

import requests
from string import ascii_letters, digits, punctuation

url = "http://167.99.77.149:30930/api/compare"

def query(x):
    res = requests.post(f"{url}", params={"guess": x})
    enc = "".join([ i["letter"] for i in res.json()])
    return enc

charset = ascii_letters + digits + punctuation
def brute_force_tail(head, find):
    assert len(head) == 31
    for i in charset:
        res = query(f"{head}{i}")
        if find == res:
            return i
    return None

pad = "@" * 32
known = ""

while known[-1:] != "}":
    pad = pad[:-1]
    find = query(pad)
    tail = brute_force_tail(pad + known, find)
    known = known + tail
    print(known)

# My stdlib @ https://github.com/4yn/sage_army_knife
from sage_army_knife.untwister import Untwister
from pwn import *

r =  remote("167.99.77.149", 32219)

def query():
    r.recvuntil(b"\n> ")
    r.sendline(b"1")
    data = 0
    for s in ["STR", "DEX", "INT", "LUK"]:
        r.recvuntil(f"{s}: ".encode())
        data = data * (2 ** 16) + int(r.recvline().decode().strip())
    return data

ut = Untwister()
for _ in range(624 // 2):
    res = bin(query())[2:].zfill(64)
    ut.submit(res[32:])
    ut.submit(res[:32])

rnd = ut.get_random()

ans = rnd.getrandbits(64)
r.sendline(f"2\n{ans}".encode())
r.recvuntil(b"Enter your lucky number: ")
print(r.recvuntil(b"}").decode())

from gmpy2 import mpz, powmod
from pwn import *

conn = remote("167.99.77.149", 30302)

conn.recvuntil(b"option: ")
conn.sendline(b"1")
conn.recvuntil(b"n: ")
n = mpz(int(conn.recvline().decode().strip()))
conn.recvuntil(b"e: ")
e = mpz(int(conn.recvline().decode().strip()))
conn.sendline(b"2")
conn.recvuntil(b"Encrypted Flag: ")
cipher = mpz(conn.recvline().decode().strip(), 16)

print(f"{n = }")
print(f"{e = }")
print(f"{cipher = }")

# Custom oracle implementation
query_ctr = 0
def query(base, morphic, log):
    global query_ctr
    print(log, end="", flush=True)
    if query_ctr % 100 == 99:
        print()
    query_ctr += 1
    x = (base * powmod(mpz(morphic), e, n)) % n
    conn.recvuntil(b"ion: ")
    conn.sendline(b"3")
    conn.recvuntil(b"Enter Encrypted Flag: ")
    conn.sendline(hex(x)[2:].zfill(512).encode())
    res = conn.recvuntil(b"\nopt")
    return b"Invalid Padding" not in res

# From https://github.com/alexandru-dinu/bleichenbacher/blob/master/src/main.py

k = 256
B = mpz(pow(2, 8 * (k - 2)))
# Adjust padding bounds
B2 = 4 * B
B3 = B2 + B

def ceildiv(a, b):
    return (a // b) + 1 if (a % b) else 0
def floordiv(a, b):
    return a // b
def interval(a, b):
    return range(a, b + 1)

c_0 = cipher
set_m_old = {(B2, B3 - 1)}
i = 1
s_old = 0

while True:
    if i == 1:
        s_new = ceildiv(n, B3)
        while not query(c_0, s_new, "."):
            s_new += 1

    elif i > 1 and len(set_m_old) >= 2:
        s_new = s_old + 1
        while not query(c_0, s_new, "?"):
            s_new += 1

    elif len(set_m_old) == 1:
        a, b = next(iter(set_m_old))
        found = False
        r = ceildiv(2 * (b * s_old - B2), n)
        while not found:
            for s in interval(ceildiv(B2 + r*n, b), floordiv(B3 - 1 + r*n, a)):
                if query(c_0, s, "!"):
                    found = True
                    s_new = s
                    break
            r += 1

    set_m_new = set()
    for a, b in set_m_old:
        r_min = ceildiv(a * s_new - B3 + 1, n)
        r_max = floordiv(b * s_new - B2, n)
        for r in interval(r_min, r_max):
            new_lb = max(a, ceildiv(B2 + r*n, s_new))
            new_ub = min(b, floordiv(B3 - 1 + r*n, s_new))
            if new_lb <= new_ub:  # intersection must be non-empty
                set_m_new |= {(new_lb, new_ub)}

    if len(set_m_new) == 1:
        a, b = next(iter(set_m_new))
        if a == b:
            print()
            print("Found decryption", a)
            break

    i += 1
    s_old = s_new
    set_m_old = set_m_new

flag = bytes.fromhex(hex(a)[2:].zfill(512))
print(flag)

from numba import njit
from tqdm.auto import tqdm
from pwn import *
context.log_level = "error"

@njit
def ror(n, k):
    return ((n << k) | (n >> (16 - k))) & 0xffff

@njit
def rol(n, k):
    return ((n >> k) | (n << (16 - k))) & 0xffff

@njit
def round(l, r, k1, k2):
    res = (((ror(r,4) ^ rol(r,5) ^ k1) + r) ^ (k2 + r + 0xe78e)) & 0xffff
    return (r, l ^ res)

@njit
def encrypt(num, k):
    l, r = (num >> 16) & 0xffff, num & 0xffff
    k1, k2 = (k >> 16) & 0xffff, k & 0xffff
    for i in range(128):
        l, r = round(l, r, k1, k2)
    return (l << 16) + r

@njit
def encrypt_magic(k):
    MAGIC = 0x8ac31542
    return encrypt(MAGIC, k)

# Precompute 2**24 outputs
lookup = {}
precompute_to = 2 ** 24

for x in tqdm(range(precompute_to)):
    lookup[encrypt_magic(x)] = x

MAGIC = 0x8ac31542

# Repeatedly connect until we get a known output
ctr = 0
while True:
    outcome = "."

    r = remote("167.99.77.149", 30708)
    r.recvuntil(b"1 = encrypt, 2 = submit key\n")
    r.sendline(f"1\n{MAGIC}".encode())
    r.recvuntil(b"encrypted = ")
    res = int(r.recvline().decode().strip())

    if res in lookup:
        outcome = "?"
        r.recvuntil(b"1 = encrypt, 2 = submit key\n")
        r.sendline(f"2\n{lookup[res]}".encode())
        res = r.clean(timeout=1).decode()
        if "Wrong" not in res:
            print("!")
            print(res)
            break
    r.close()

    print(outcome, end="", flush=True)
    if ctr % 100 == 99:
        print()
    ctr += 1

from Crypto.PublicKey import RSA
from math import gcd
from pwn import *
from tqdm.auto import tqdm
from multiprocessing import Pool

# Load all n
keyfiles = os.listdir("crypto_thatsalotofrsa/pubkeys")
ns = []
for keyfile in tqdm(keyfiles):
    with open("crypto_thatsalotofrsa/pubkeys/" + keyfile, "r") as f:
        k = RSA.import_key(f.read())
        assert k.e == 0x10001
        ns.append(k.n)
len(keyfiles)

def solve(n):
    for on in ns:
        p = gcd(n, on)
        if p != 1:
            return p

r = remote("167.99.77.149", 32382)
r.recvuntil(b"n[")

# Collect all inputs
chal_ns = []
for _ in tqdm(range(200)):
    r.recvuntil(b"] = ")
    n = int(r.recvline().decode())
    chal_ns.append(n)

# Multithreaded GCD finding
chal_ps = []
with Pool(processes=4) as pool:
    for p in tqdm(pool.imap(solve, chal_ns), total=200):
        chal_ps.append(p)

r.sendline("\n".join([str(p) for p in chal_ps]).encode())
r.recvuntil(b"[199] = ?\n")
print(r.recvline().decode())