blog > STACK The Flags 2022 Writeups

4 Dec 2022 ctfcrypto

STACK The Flags 2022 Writeups

Encryptdle

A popular word game, but encrypted!

Attachment: crypto_encryptdle.zip

Challenge server.py
python
KEY = os.urandom(32)
IV = os.urandom(16)
MAX_LEN = 32

def pad(bstring):
    return (bstring + FLAG + b'\x00' * MAX_LEN)[:MAX_LEN]

def encrypt(bstring):
    padded_data = pad(bstring)
    cipher = Cipher(algorithms.Camellia(KEY), modes.CBC(IV))
    encryptor = cipher.encryptor()
    return encryptor.update(padded_data) + encryptor.finalize()

From the webserver we get first 32 bytes of the Camellia encryption of user_input + FLAG + pad in CBC mode. The server reuses its key and IV each time. This is vulnerable to chosen plaintext attack.

python
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)
output
S
ST
STF
STF2
[...many lines...]
STF22{iNS3CuR3!_S+4+iC_IVs
STF22{iNS3CuR3!_S+4+iC_IVs!
STF22{iNS3CuR3!_S+4+iC_IVs!!
STF22{iNS3CuR3!_S+4+iC_IVs!!}

jagacha

JAGATSA

Attachment: crypto_jagacha.zip

Challenge jagacha.py
python
# ...
import random
# ...
async def handler(reader: asyncio.StreamReader, writer: asyncio.StreamWriter):
    # ...
    rand = random.Random(get_seed())
    try:
        option = None
        while option != 3:
            await print_menu(writer)
            option = await read_number(reader, writer)
            if option == 1:
                num = rand.getrandbits(64)
                gacha = GACHA_KEYS[num % len(GACHA_KEYS)]
                writer.writelines(
                    (
                        f"Congrats! You have pulled a {gacha}!\n".encode(),
                        GACHAS[gacha],
                        b"Here are the stats of your character:\n",
                        f"STR: {num>>48 & 0xffff}\n".encode(),
                        f"DEX: {num>>32 & 0xffff}\n".encode(),
                        f"INT: {num>>16 & 0xffff}\n".encode(),
                        f"LUK: {num & 0xffff}\n".encode(),
                        b'\n',
                    )
                )
                # ...
            elif option == 2:
                num = rand.getrandbits(32)
                lucky_number = await read_number(
                    reader, writer, b"Enter your lucky number: "
                )
                if lucky_number == num:
                    writer.writelines((
                        b"Congrats! You have pulled the limited SSS-rated rarity flag-chan!\n",
                        FLAG,
                    ))
                    # ...
            # ...

The server uses the python PRNG function .getrandbits(64) to randomly generate a character and its stats. With enough rolls we can recover the state of the PRNG using z3 and predict the next roll to claim the flag.

python
# 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())
output
[x] Opening connection to 167.99.77.149 on port 32219
[x] Opening connection to 167.99.77.149 on port 32219: Trying 167.99.77.149
[+] Opening connection to 167.99.77.149 on port 32219: Done
Solving...
sat
Solved! (in 1.266s)
Congrats! You have pulled the limited SSS-rated rarity flag-chan!
STF22{W@IFU5_L@1FU5}

Pad the flag

Pad the Flag

Attachment: crypto_padtheflag.zip

Challenge source.py
python
PADDING = b"\x00\x04"
with open("private_key.pem", "rb") as f:
    PRIVATE_KEY = rsa.PrivateKey.load_pkcs1(f.read())

class RSA():
    def __init__(self):
        self.private_key = PRIVATE_KEY
        self.padding = PADDING

    def valid(self, plaintext):
        if len(plaintext) < 11:
            return False

        return plaintext[:2] == self.padding

    def decrypt(self, plaintext):
        # ...

    # ...

def main():
    rsa = RSA()
    while True:
        # ...
        elif option == 3:
            encrypted = input("Enter Encrypted Flag: ")
            plaintext = rsa.decrypt(encrypted)
            if plaintext is None:
                print("Decryption Failed!")
                continue

            if not rsa.valid(plaintext):
                print("Invalid Padding!")
                continue

The service returns a special error message if the padding is invalid. This is a textbook Bleichenbacher padding oracle attack except with padding bytes \x00\x04 instead of \x00\x02. We can steal an implementation from elsewhere and make the necessary edits.

python
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)
output
[x] Opening connection to 167.99.77.149 on port 30302
[x] Opening connection to 167.99.77.149 on port 30302: Trying 167.99.77.149
[+] Opening connection to 167.99.77.149 on port 30302: Done
n = mpz(277454988382683422703905418324[...]00768185786779871199)
e = mpz(65537)
cipher = mpz(215563187754089626071528576644[...]59265685370170619393)
....................................................................................................
....................................................................................................
[...many lines...]
....................................................................................................
....................................................................................................
...........................................................................!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
[...many more lines...]
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Found decryption 211361501571634421707424965336[...]60402282842373108605
b'\x00\x04IE\xde+\x97\x1fPU3\x81\n\\[...]\x9d\xa7\x0c\x90\x00STF22{p@dd1ng_pr0b13m_3v3rywh3r3}'

MysteryCrypt

We found this encryption algorithm being used after the key exchange. We suspect that it is very weak and can be cracked in a short amount of time.

Attachment: crypto_mysterycrypt.zip

Challenge crypt_generate.py
python
key = random.randint(2, 2**32-1)
delta = 0x9E37 ^ 0x79B9
def mod(x):
    return x % (2**16)
k1 = mod(key >> 16)
k2 = mod(key)
def ror(n, k):
    return (n << k) | (n >> (16 - k))
def rol(n, k):
    return (n >> k) | (n << (16 - k))
def round(l, r, k1, k2):
    res = mod((ror(r,4) ^ rol(r,5) ^ k1) + r) ^ mod(k2 + r + delta)
    return (r, l ^ res)

def encrypt(num):
    l, r = mod(num >> 16), mod(num)
    for i in range(128):
        l, r = round(l, r, k1, k2)
    return (l << 16) + r

We get an encryption service that does a feistel-like cipher operation on a 32 bit ciphertext with a 32 bit key that is randomized on each connection. We can do a meet-in-the-middle attack by precomputing the encryption of some fixed input e.g. 0x8ac31542 with keys 0 to 2**24. When connecting to the server, we encrypt the fixed input and look for the output in our precomputation, then submit a candidate key if we have one. This took around 15 seconds to calculate the 16 million key-output pairs (with the help of numba) and we expect to need 256 connections to get a connection with a key that has been precomputed.

python
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
output
..................................................................!
key = ?
STF22{mc1_8c7d5b1b2a503822}

ThatsALotOfRSA

We found this is how the keys are generated. The set of public keys are distributed. We need to crack the private keys generated as fast as possible.

Attachment: crypto_thatsalotofrsa.zip

Challenge rsa_challenge.py
python
privkeydir = os.getenv('PRIVKEYS')
keys = os.listdir(privkeydir)

# ...
for i in range(200):
    k1file, k2file = random.sample(keys, 2)
    k1 = RSA.import_key(open(f'{privkeydir}/{k1file}').read())
    k2 = RSA.import_key(open(f'{privkeydir}/{k2file}').read())
    p = random.choice([k1.p,k1.q])
    q = random.choice([k2.p,k2.q])
    n = p * q
    nstr += f'n[{i}] = {n}\n'
    ans.append((p,q))
# ...

GCD each challenge n with every other n in the folder of private keys, this will reveal at least one factor p. We can speed this up to run within the 10 seconds time limit using multiprocessing.

python
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())
output
    0%|          | 0/20000 [00:00<?, ?it/s]
[x] Opening connection to 167.99.77.149 on port 32382
[x] Opening connection to 167.99.77.149 on port 32382: Trying 167.99.77.149
[+] Opening connection to 167.99.77.149 on port 32382: Done
    0%|          | 0/200 [00:00<?, ?it/s]
    0%|          | 0/200 [00:00<?, ?it/s]
STF22{rsa_823564830a826421}