Write up LACTF 2025

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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!!!}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#!/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. ")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#!/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()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#!/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.")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#!/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}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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_???}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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!")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

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}