Author @sem1tonos

This challenge is a cool introduction to Shamir Secret Sharing (SSS).

msg.enc

share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c

Overview

We are given some parameters : p = 92434467187580489687 , k = 10 , n = 18

At first glance, we can see that the coefficients array (coeffs) is initialized with a random secret value, say s. self.coeffs = [self.secret]

This value is later used as seed to generate the random AES key which is used to encrypt the flag.

The coeffs array contain repeated md5 hashes of the initial secret value. Of course this hash is converted to an integer. That is:

• element 0 : secret = s
• element 1 : md5(secret) = hs
• element 2 : md5(md5(secret)) = hhs …

and so on and so forth. This repeats n = 18 times.

By the end of create_pol coeffs will contain only the first k = 10 hash values because of self.coeffs = self.coeffs[:self.k].

The important part are the two arrays, x_vals and y_vals.

x is just some random value < p but y is calculated based on the corresponding x value and the coefficients array as below:

y = (s + hs * x + hhs * x^2 + hhhs * x^3 + ... + hhhhhhhhhs * x^9) % p    (1)

Solution

We are given the md5 hash of the secret value. That means that we can hash it, then hash again and again to recover all the coefficients but the secret.

We know all the hash values and just one pair of x, y values. Let’s solve (1) for the secret:

secret = (y - hs * x - hhs * x^2 - hhhs * x^3 - ... - hhhhhhhhhs * x^9) % p =
       = [y - (hs * x + hhs * x^2 + hhhs * x^3 + ... + hhhhhhhhhs * x^9)] % p

Now we can subtitute for the coefficients that we calculated above, the x and y value to get the secret, find the key and decrypt the flag.

solve.py

 1from hashlib import md5
 2from Crypto.Cipher import AES
 3from Crypto.Util.Padding import pad
 4from random import randbytes, seed
 5
 6x, y = 21202245407317581090, 11086299714260406068
 7hs = 93526756371754197321930622219489764824
 8k = 10
 9n = 18
10p = 92434467187580489687
11coeffs = [hs]
12
13ct = bytes.fromhex('...')
14
15def next_coeff(val):
16    return int(md5(val.to_bytes(32, byteorder="big")).hexdigest(),16)
17
18def calc_coeffs():
19    for i in range(1, k-1):
20        coeffs.append(next_coeff(coeffs[i-1]))
21
22def calc_rhs():
23    sum = 0
24    for i in range(len(coeffs)):
25        sum += coeffs[i] * x**(i+1)
26    return sum % p
27
28calc_coeffs()
29rhs = calc_rhs()
30
31secret = y - rhs
32secret %= p
33
34seed(secret)
35key = randbytes(16)
36cipher = AES.new(key, AES.MODE_ECB)
37msg = cipher.decrypt(ct)
38
39print(msg)

Message

b'The treasure is located at galaxy VS-708.\nOur team needs 3 light years to reach it.\nOur solar cruise has its steam canons ready to fire in case we encounter enemies.\nNext time you will hear from us brother, everyone is going to be rich!\nHTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}\x08\x08\x08\x08\x08\x08\x08\x08'

Flag

HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}