Write up LACTF 2025

Blog

Write up LACTF 2025

February 11, 2025

big e

I'm so confident in my big e's, I'll give them to you twice!

Source:

from Crypto.Util.number import bytes_to_long, getPrime

flag = REDACTED

pt = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p*q

e_1 = getPrime(16)
e_2 = getPrime(16)



ct_1 = pow(pt, e_1, n)
ct_2 = pow(pt, e_2, n)
print("ct_1 = ", ct_1)
print("ct_2 = ", ct_2)

print("e_1 = ", e_1)
print("e_2 = ", e_2)

print("n = ", n)

Solutions:

Because $e_1$ , $e_2$ is primes, we can use extended euclidean algorithm to find $x$ , $a$ , $b$ such that $a * e_1+b*e_2 = x$ , $x = gcd(e_1,e_2) = 1$ .

ct_1 = pt^{e_1} \; \% \; n

ct_2 = pt^{e_2} \; \% \; n

x,a,b = xgcd(e_1,e_2)

ct_1^{a}*ct_2^{b} = pt^{a*e_1+b*e_2} = pt^{x} \; \% \; n = pt

ct_1 = ..
ct_2 =  ..
e_1 =  ..
e_2 =  ..
n =  ..
x,a,b = xgcd(e_1,e_2)
print(x,a,b)
from Crypto.Util.number import long_to_bytes
m = pow(ct_1, a, n) * pow(ct_2, b, n) % n
print(long_to_bytes(m))
# lactf{b1g_3_but_sm4ll_d!!!}

Extremely Convenient Breaker

Source:

I won't let you decrypt the flag, but you can use my Extremely Convenient Breaker.

#!/usr/local/bin/python3

from Crypto.Cipher import AES
import os

key = os.urandom(16)
with open("flag.txt", "r") as f:
    flag = f.readline().strip()
cipher = AES.new(key, AES.MODE_ECB)

flag_enc = cipher.encrypt(flag.encode())
print("Here's the encrypted flag in hex: ")
print(flag_enc.hex())
print("Alright, lemme spin up my Extremely Convenient Breaker (trademark copyright all rights reserved). ")

while True:
    ecb = input("What ciphertext do you want me to break in an extremely convenient manner? Enter as hex: ")
    try:
        ecb = bytes.fromhex(ecb)
        if not len(ecb) == 64:
            print("Sorry, it's not *that* convenient. Make your ciphertext 64 bytes please. ")
        elif ecb == flag_enc:
            print("No, I'm not decrypting the flag. ")
        else:
            print(cipher.decrypt(ecb))
    except Exception:
        print("Uh something went wrong, please try again. ")

Solutions:

It's ECB mode, so just break the flag by block and sent each block to get the flag.

from pwn import *

io = remote('chall.lac.tf',31180)

io.recvuntil(b'hex:')
io.recvline()
ct_hex  = io.recvline().strip().decode()

ct = bytes.fromhex(ct_hex)
flag = ''
for i in range(0, len(ct), 16):
    x = ct[i:i+16]
    x = x + b'\x00' * (64 - len(x))
    # io.interactive()
    io.sendlineafter(b'hex',x.hex())
    x = (io.recvline().strip().decode())
    flag+=x[:16]

print(flag)  
# lactf{seems_it_was_extremely_convenient_to_get_the_flag_too_heh}

RSAaaS

Tired of doing RSA on your own? Try out my new service!

Source:

#!/usr/local/bin/python3

from Crypto.Util.number import isPrime


def RSAaaS():
    try:
        print("Welcome to my RSA as a Service! ")
        print("Pass me two primes and I'll do the rest for you. ")
        print("Let's keep the primes at a 64 bit size, please. ")

        while True:
            p = input("Input p: ")
            q = input("Input q: ")
            try:
                p = int(p)
                q = int(q)
                assert isPrime(p)
                assert isPrime(q)
            except:
                print("Hm, looks like something's wrong with the primes you sent. ")
                print("Please try again. ")
                continue

            try:
                assert p != q
            except:
                print("You should probably make your primes different. ")
                continue

            try:
                assert (p > 2**63) and (p < 2**64)
                assert (q > 2**63) and (q < 2**64)
                break
            except:
                print("Please keep your primes in the requested size range. ")
                print("Please try again. ")
                continue

        n = p * q
        phi = (p - 1) * (q - 1)
        e = 65537
        d = pow(e, -1, phi)

        print("Alright! RSA is all set! ")
        while True:
            print("1. Encrypt 2. Decrypt 3. Exit ")
            choice = input("Pick an option: ")

            if choice == "1":
                msg = input("Input a message (as an int): ")
                try:
                    msg = int(msg)
                except:
                    print("Hm, looks like something's wrong with your message. ")
                    continue
                encrypted = pow(msg, e, n)
                print("Here's your ciphertext! ")
                print(encrypted)

            elif choice == "2":
                ct = input("Input a ciphertext (as an int): ")
                try:
                    ct = int(ct)
                except:
                    print("Hm, looks like something's wrong with your message. ")
                    continue
                decrypted = pow(ct, d, n)
                print("Here's your plaintext! ")
                print(decrypted)

            else:
                print("Thanks for using my service! ")
                print("Buh bye! ")
                break

    except Exception:
        print("Oh no! My service! Please don't give us a bad review! ")
        print("Here, have a complementary flag for your troubles. ")
        with open("flag.txt", "r") as f:
            print(f.read())

RSAaaS()

Solutions:

The service will print out the flag when we make error, the only block that do not have try catch is line 40-44, so just brute for some prime $p$ which $gcd(e,\phi_p) \; != 1$ .

from Crypto.Util.number import isPrime,getPrime
from math import gcd
while True:
    p = getPrime(64)
    q = getPrime(64)
    phi = (p-1)*(q-1)
    if gcd(phi,65537)!=1:
        print(p)
        print(q)
        
# 11044759569016762319
# 14533580375381402089
# lactf{actually_though_whens_the_last_time_someone_checked_for_that}

crypto-civilization

Source:

In Crypto Civilization, nobody commits the beef.

#!/usr/local/bin/python3

import hashlib
import os
import binascii


# s is 16 bits long, 32 bit output
def PRG(s: bytes) -> bytes:
    assert len(s) == 2, "You're trying to cheat! Go to Crypto Prison!"
    s_int = int.from_bytes(s, byteorder="big")

    h = hashlib.new("sha3_256")
    h.update(s)

    out = h.digest()

    return out[:4]


def xor_bytes(bytes1: bytes, bytes2: bytes) -> bytes:
    if len(bytes1) != len(bytes2):
        raise ValueError("Byte objects must be of the same length")

    return bytes(b1 ^ b2 for b1, b2 in zip(bytes1, bytes2))


print("In Crypto Civilization, nobody commits the beef. 0 = chicken and 1 = beef.")
print(
    "Every day, Crypto Noobs have 1.5 seconds to do the commitment challenge. Exceptional performers will level up to Crypto Pro."
)
print("Can you level up to a Crypto Pro?")

number_correct = 0

for i in range(200):
    print(f"Crypto test #{i + 1}")

    # generate 32-bit value
    y = os.urandom(4)
    print(f"Here's y: {y.hex()}")

    print("What's your commitment (hex)?")

    com_hex = input("> ").encode()

    try:
        com = binascii.unhexlify(com_hex)
    except:
        print("You're trying to cheat! Go to Crypto Prison!")
        exit(0)

    assert len(com) == 4, "You're trying to cheat! Go to Crypto Prison!"

    choice = int.from_bytes(os.urandom(1), byteorder="big") & 1  # random bit

    if choice == 0:
        print("Did you commit the chicken? Show me (hex).")

    elif choice == 1:
        print("Did you commit the beef? Show me (hex).")

    decom_hex = input("> ").encode()

    try:
        decom = binascii.unhexlify(decom_hex)
    except:
        print("You're trying to cheat! Go to Crypto Prison!")
        exit(0)

    assert len(decom) == 2, "You're trying to cheat! Go to Crypto Prison!"

    if choice == 0:
        if PRG(decom) == com:
            print("Good work. See you tomorrow.")
            number_correct += 1
        else:
            print("Ouch. You don't want to keep doing that.")

    elif choice == 1:
        if xor_bytes(PRG(decom), y) == com:
            print("Good work. See you tomorrow.")
            number_correct += 1
        else:
            print("Ouch. You don't want to keep doing that.")

print(f"{number_correct}/200 trials passed")

if number_correct > 132:
    print("Congrats! You leveled up to a Crypto Pro! Here's your flag.")
    print(open("flag.txt", "r").read())
else:
    print("You messed up too many tasks. You go to Crypto Prison.")

Solutions:

So in this challenge, we have to guess the output of PRG function and it have 2 cases:

If $choice = 0$ , guess $com = PRG(decom)$
If $choice = 1$ , guess $com = PRG(decom) \oplus y$

The decom is only 2 bytes long, so we can bruteforce it. Because we must sent $com$ before $decom$ , so to ensure it corrects in both cases, we must find $com$ to that it have $PRG(decom_1) = com$ and $PRG(decom_2) \oplus y = com$ .

import hashlib
import os
import binascii
from pwn import *
import pickle
from tqdm import *
io = remote('chall.lac.tf',31173)
def xor_bytes(bytes1: bytes, bytes2: bytes) -> bytes:
    if len(bytes1) != len(bytes2):
        raise ValueError("Byte objects must be of the same length")

    return bytes(b1 ^ b2 for b1, b2 in zip(bytes1, bytes2))
with open("hashes.pickle", "rb") as f:
    loaded_data = pickle.load(f)  # loaded_data[com] = decom 
keys = loaded_data.keys()
def brute_t(y):
    for key in tqdm(keys):
        z = xor_bytes(key, y)
        if z in loaded_data:
            return z
print(io.recvuntil(b'Crypto Pro?\n'))
default = list(filter(lambda k: loaded_data[k] == b'\x00\x00', loaded_data))
for i in range(200):
    io.recvline()
    io.recvuntil(b'y: ')
    hex_y = io.recvline().strip()
    y = bytes.fromhex(hex_y.decode())
    t = brute_t(y)
    if t is None:
        io.sendlineafter(b'>', default[0].hex())
        io.recvline().strip()
        io.sendlineafter(b'>', b'0000')
        print(io.recvline())
    else:
        io.sendlineafter(b'>', t.hex())
        x = io.recvline().strip()
        if b'chicken' in x:
            io.sendlineafter(b'>', loaded_data[t].hex())
        elif b'beef' in x:
            var_need = xor_bytes(t, y)
            if var_need in loaded_data:
                io.sendlineafter(b'>', loaded_data[var_need].hex())
            else:
                io.sendlineafter(b'>', b'0000')
        print(io.recvline())
io.interactive()

quickprime

Behold: my revolutionary new algorithm to generate primes QUICKLY and SECURELY.

Source:

#!/usr/local/bin/python3

from secrets import randbits
from Crypto.Util.number import isPrime


class LCG:

    def __init__(self, a: int, c: int, m: int, seed: int):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state


while True:
    a = randbits(512)
    c = randbits(512)
    m = 1 << 512
    seed = randbits(512)
    initial_iters = randbits(16)
    # https://en.wikipedia.org/wiki/Linear_congruential_generator#m_a_power_of_2,_c_%E2%89%A0_0
    if (c != 0 and c % 2 == 1) and (a % 4 == 1):
        print(f"LCG coefficients:\na={a}\nc={c}\nm={m}")
        break

L = LCG(a, c, m, seed)
for i in range(initial_iters):
    L.next()

P = []
num = 0
while len(P) < 2:
    test = L.next()
    num += 1
    if isPrime(test):
        print(num)
        P.append(test)

p, q = P

n = p * q

t = (p - 1) * (q - 1)

e = 65537

d = pow(e, -1, t)
print(f"p={p}")
print(f"q={q}")
print(f"n={n}")

Solutions:

The LCG will make p, q have the form:

p = a * state + c \; \% \; m

q = a * state + c \; \% \; m

But we can assume that q is LCG.next() from p $\rightarrow$ we can have $q = a * p + c \; \% \; m$ ; or

q = a^b *p + \frac{a^b-1}{a-1}* c \; \% \; m

with $b$ is the number of next in the LCG.

Another thing to keep in mind that is $gcd(a-1,m) != 1$ so we can't not find

\frac{a^b-1}{a-1} = (a^b-1)*(a-1)^{-1} \; \% \; m

and must expand

\frac{a^b-1}{a-1} = a^{b-1} + a^{b-2} + ... + 1 \; \% \; m

from tqdm import *
from Crypto.Util.number import long_to_bytes

a= ..
c= ..
m= ..
n= .. 
ct= ..
# p
# q = a^m * p + ((a^m - 1) / (a - 1)) * c
def geom_sum(a, e, m):
    S = 0
    term = 1
    for _ in range(e):
        S = (S + term) % m
        term = (term * a) % m
    return S

Pr.<p> = PolynomialRing(Zmod(m))
for e2 in trange(1,10000):
    q = pow(a,e2,m)*p + geom_sum(a,e2,m)*c
    f =q*p - n 
    roots = f.roots(multiplicities=False)
    flag = False
    for i in roots:
        # print(i)
        if gcd(n,int(i)) != 1:
            print('bingo',i)
            p = int(i)
            flag = True
            break
    if flag:
        break
q = n//p
phi = (p-1)*(q-1)
d = pow(65537,-1,phi)
pt = pow(ct,d,n)
print(long_to_bytes(pt))
lactf{w41t_th1s_1snt_s3cur3_4t_4ll_???}

good-hash

I learned about hash-length extension attacks, so I'm going to use a good hash instead

Source:

from Crypto.Cipher import AES
import os

FLAG = REDACTED

if __name__ == "__main__":
    print("Can you guess the secret?")
    secret = os.urandom(16)
    key  = os.urandom(16)
    iv = os.urandom(12)
    print(secret.hex())
    for attempt in range(4):
        choice = input().strip()
        if choice == "1":
            leftextend = bytes.fromhex(input("input > "))
            rightextend = bytes.fromhex(input("input > "))
            cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
            _, mac = cipher.encrypt_and_digest(leftextend + secret + rightextend)
            print(mac.hex())
        if choice == "2":
            guess = bytes.fromhex(input("guess > "))
            if guess == secret:
                print(FLAG)
            else:
                print("WRONG !!")
                exit()
    print("You're out of time!")

Solutions:

This is a AES-GCM challange for more about GCM you can read here:> GCM. So when we sent $leftextend$ and $rightextend$ , it will encrypt $leftextend + secret + rightextend$ and return the mac. Assume we fix $leftextend$ and $rightextend$ at a block size, we will have form of mac

mac = H^4 * (leftextend \oplus keystream_1) + H^3 * (secret \oplus keystream_2) + H^2 * (rightextend \oplus keystream_3) + H * LENGTH + T

We have 4 queries, 1 of them is to get the flag, so which 3 queries left, I think about setting enough equations to solve of $H$ and then solve for $secret$ . Using $leftextend$ and $rightextend$ as null bytes for easy to calculate $\texttt{b'\textbackslash x00'} * 16 \oplus ks_1 = ks_1$ . The oracle is reusing $key$ and $iv$ so $T$ and $H$ will be the same.

mac_1 = H^4 * ks_1 + H^3 * ks_2 + H^2 * (secret \oplus ks_3) + H * LENGTH + T

mac_2 = H^4 * ks_1 + H^3 * (secret \oplus ks_2) + H^2 * ks_3 + H * LENGTH + T

mac_3 = H^4 * (secret \oplus ks_1) + H^3 * ks_2 + H^2 * ks_3 + H * LENGTH + T

mac_1 + mac_2 = H^3 * secret + H^2 * secret = f_1

mac_1 + mac_3 = H^4 * secret + H^2 * secret = f_2

mac_2 + mac_3 = H^4 * secret + H^3 * secret = f_3

f_1 * f_2^{-1} =\frac{H^3+H^2}{H^4+H^2}

From this we can solve for $H$ and $serect = \frac{f_1}{H^3+H^2}$

from pwn import *
io = remote('chall.lac.tf',32222)
context.log_level = 'ERROR'
# Implement for GF2e is yeet from https://github.com/jvdsn/crypto-attacks/blob/master/attacks/gcm/forbidden_attack.py because me lazy.
gf2e = GF(2 ** 128, name="y", modulus=x ** 128 + x ** 7 + x ** 2 + x + 1)
# Converts an integer to a gf2e element, little endian.
def _to_gf2e(n):
    return gf2e([(n >> i) & 1 for i in range(127, -1, -1)])
# Converts a gf2e element to an integer, little endian.
def _from_gf2e(p):
    n = p._integer_representation()
    ans = 0
    for i in range(128):
        ans <<= 1
        ans |= ((n >> i) & 1)
    return ans

print(io.recvline())
io.sendline(str(1))
io.sendlineafter('input > ','00'*32)
io.sendlineafter('input > ',''*16)

mac = io.recvline().strip().decode() # H^4(ks1) + H^3*ks2+H^2(ks3+secret)
print(mac)
io.sendline(str(1))
io.sendlineafter('input > ','00'*16)
io.sendlineafter('input > ','00'*16)
mac2 = io.recvline().strip().decode() # H^4(ks1) + H^3*(ks2+secret)+H^2(ks3)
io.sendline(str(1))
io.sendlineafter('input > ','')
io.sendlineafter('input > ','00'*32)
mac3 = io.recvline().strip().decode() # H^4(ks1+secret) + H^3(ks2)+H^2(ks3)
from Crypto.Util.number import *

secret_3 = int(mac,16)
secret_2 = int(mac2,16)
secret_1 = int(mac3,16)
secret_3 = _to_gf2e(secret_3)
secret_2 = _to_gf2e(secret_2)
secret_1 = _to_gf2e(secret_1)

f1 = secret_1+secret_2 # H^4*secret + H^3*secret 
f2 = secret_1+secret_3 # H^4*secret + H^2*secret
f3 = secret_2+secret_3 # H^3*secret + H^2*secret
# print(f1+f2+f3)
h = gf2e["h"].gen()
f = (h^4+h^3)*(h^4+h^2)^-1 -f1*(f2^-1)
f_poly = f.numerator()
H = f_poly.roots()[0][0]
secret = f1*(H^4+H^3)^-1
print(secret)
t = _from_gf2e(secret)
io.sendline(str(2))
io.sendlineafter('guess > ',hex(t)[2:])
print(io.recvline())
# lactf{g_d03s_n0t_s7and_f0r_g00d}

Last updated on February 11, 2025

Write up ASCIS CTF 2024 - Crypto