HackDay 2024 | Care the factors! | [Crypto]

HackDay 2024 - Write-Up - Care the factors ! [Crypto]

Statement

Téléchargez le fichier et déchiffrez le fichier chiffré. 

Download the file and decrypt the encrypted file.  

Author : D0ppl3gang3r
Points : 460
Solves : 22

Files analysis

This challenge consist of two files :

1. The source code: source_thefactors.sage
2. flag_thefactors.txt : two points P and Q, an IV and the encrypted flag

The file source_thefactors.sage

After analyzing the source code, we can see that there a function wo take a secret as an input and return the encrypted flag, this function consist of an AES CBC with a random IV and a key derived from the shared_secret.

def enc_flag(shared_secret):
	md5 = hashlib.md5()
	md5.update(str(shared_secret).encode())
	key = md5.digest()[:16]
	iv = os.urandom(16)
	cipher = AES.new(key, AES.MODE_CBC, iv)
	ciphertext = cipher.encrypt(pad(flag, 16))
	output = {}
	output['iv'] = iv.hex()
	output['flag'] = ciphertext.hex()
	return output

So we can deduce quickly that the vulnerability didn’t come from this function. Further down in the file, we can see this code :

p = 1410235279292998784331797202421753874063265295308568058662741299116310072677 
A = getA()
B = getB()
Fp = FiniteField(p)
E = EllipticCurve(Fp, [A, B])
P = E.random_element()
n = randint(2**30, 2**60)
Q = n * P
flag = enc_flag(n)
print(f"{P=}")
print(f"{Q=}")
print(f"{flag=}")

This is a classical implementation of the ECDLP

All in all, we “just” have to solve the ECDLP given in the sage file in order to retrieve the flag.

The file secretmessage.txt

This file just contains public values like P, Q, IV and the encrypted flag.

Solving the chall

In order to solve the ECDLP we have to recover the curve parameters. With a little bit of algebra we can easily retrieve A and B from P and Q, here is how I’ve done :

def get_a_and_b_from_two_point(x, y, x_, y_, p):
	inv_x , inv_y  = inverse_mod(x, p) , inverse_mod(y, p)
	inv_x_, inv_y_ = inverse_mod(x_, p), inverse_mod(y_, p)
	
	c = (x * inv_x_) % p
	
	b = (((y**2) - (x**3) - (y_**2 * c) + (x_**3 * c)) * inverse_mod((1 - c) % p, p) ) % p
	a = ((y_**2 - x_**3 - b) * inverse_mod(x_, p)) % p

	return a, b

Now we can build the curve like this using sage :

P = (406156291172024449433827761031736513098183950832214481256475543523051604042, 937502472800241241676075882016117499207790111193756481427079135615174871684)
Q = (92554882076587701525654416824880284407135974444455993706448015434816328085, 1067245947645250194968549384640439378373660468218406176128671131644883921569)

p = 1410235279292998784331797202421753874063265295308568058662741299116310072677 
Fp = FiniteField(p)

A, B = get_a_and_b_from_two_point(P, Q, p)
E = EllipticCurve(Fp, [A, B])

P = E(P)
Q = E(Q)

And we can check for common vulnerability by checking these values :

E_order = E.order()

# Is anomalus ?
print(E_order == p) # False -> No

# Is vulnerable to Pohlig–Hellman ?
E_order_factors = factor(E_order)
print(E_order_factors)
# [2, 3, 7, 43, 349, 409, 6199, 344222059, 58853094821, 162989330351, 284121766519, 940658041742936711869] -> YES

I immediately spotted that the order of this curve has small primes factor. This is great because we’ll be able to solve the ECDLP with the Pohlig-Hellman algorithm !
This algo is based on the following idea : we will solve several discrete logarithm problem in several subgroup and then unify answers over $p$ using CRT. Here is the algorithm : Pohlig-Hellman algorithm : Illustration taken from https://link.springer.com/book/10.1007/978-1-4939-1711-2

And here is my implentation in SageMath : (Be carefull this code works only if like in our exemple each factor f respect ord(f) = 1, otherwise you’ll need to change g_i and h_i according to the figure above)

E_order_factors = [2, 3, 7, 43, 349, 409, 6199, 344222059, 58853094821, 162989330351, 284121766519, 940658041742936711869]
all_res = []

for fact in E_order_factors:
	g_i = P * (E_order / fact)
	h_i = Q * (E_order / fact)

	current_res = discrete_log(h_i, g_i, g_i.order(), operation='+')
	all_res.append(current_res)

print("secret : ", crt(all_res, E_order_factors))
# 1883705452

Now that we have the shared_secret it is really easy :

shared_secret = 1883705452
iv = bytes.fromhex("4318aa195451964d2078e230494ef079")
flag = bytes.fromhex("75ae6944d3434c9e96affd40c6137bfe23934fddcc6693bdfdd7a1d542f3464a12abc09d87dd0dc8fd860d666dd2b337")

def dec_flag(shared_secret, iv):
	# Key du aes = md5 de shared_secret
	md5 = hashlib.md5()
	md5.update(str(shared_secret).encode())
	key = md5.digest()[:16]
	
	# Chiffrement du flag avec key et iv
	cipher = AES.new(key, AES.MODE_CBC, iv)
	ciphertext = cipher.decrypt(flag)

	print(ciphertext)

	# Build le ct et l'iv
	output = {}
	output['iv'] = iv.hex()
	output['flag'] = ciphertext

	# Renvoie le ct et l'iv
	return output

print(dec_flag(shared_secret, iv))

Flag : HACKDAY{W34k_EC_W1th_P0hlig_H3llm4n_4TT4cK}