Write up LACTF 2025
Crypto Challenge
Write up LACTF 2025
big e
I’m so confident in my big e’s, I’ll give them to you twice!
Source:
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)
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\]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!!!}
Extremely Convenient Breaker
Source:
I won’t let you decrypt the flag, but you can use my Extremely Convenient Breaker.
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. ")
Solutions:
It’s ECB mode, so just break the flag by block and sent each block to get the flag.
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}
RSAaaS
Tired of doing RSA on your own? Try out my new service!
Source:
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()
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$.
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}
crypto-civilization
Source:
In Crypto Civilization, nobody commits the beef.
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.")
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$.
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()
quickprime
Behold: my revolutionary new algorithm to generate primes QUICKLY and SECURELY.
Source:
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}")
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\)
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_???}
good-hash
I learned about hash-length extension attacks, so I’m going to use a good hash instead
Source:
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!")
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 \(b'\text{\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}$
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}
This post is licensed under
CC BY 4.0
by the author.