Space Pirates

Jones and his crew have started a long journey to discover the legendary treasure left by the guardians of time in the early beginnings of the universe. Mr Jones, though, is wanted by the government for his crimes as a pirate. Our agents entered his base and discovered digital evidence about the way captain Jones contacts with his closest friends back home. We managed to get his last message, sent to his best friend. Could you help us decrypt it?

Category: crypto

Solver: n1k0

Flag: HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}

Writeup

TL;DR: If a crypto paper says that you should choose some numbers at random, don’t use MD5 to derive them deterministically from each other.

First, we looked into the code and tried to understand what was going on. We saw that the challenge implements Shamir’s Secret Sharing. It creates a random secret (which is secret-shared) and uses this to seed the random module. Then, an AES key is generated and used to encrypt the flag in ECB mode. Besides the encrypted flag and one secret share, we retrieve the first coefficient of the secret sharing polynomial. We remember that Shamir’s Secret Sharing uses a polynomial with random coefficients to split a secret into multiple shares where a certain fraction of shares is required to reconstruct the secret.

For a scheme where t shares are required to reconstruct the secret s, the polynomial looks like this:

f(x) = s + a_1 * x + a_2 * x^2 + ... + a_{t-1} * x^{t-1} mod p

Any t points from the polynomial allow to recover it unambiguously. If only provided with t-1 points of the polynomial, one does not learn anything about the value of s. The scheme works in Z_p with p being a prime number, so we quickly checked that the used number actually is prime.

In the implemented scheme the coefficients are calculated using the MD5 hash function by evaluating it on the previous coefficient (starting with the secret s = a_0). While n = 18 coefficients are calculated, only k = 10 are actually used (k corresponds to t - 1). While this seems weird, it does not pose any problems security-wise. Finally, n = 18 random points are chosen randomly. These are the secret shares from which the first one is provided to us.

We notice two suspicious things: the MD5-thingy and the ECB mode for the encryption. While the latter does not seem to be a problem here, we have a closer look at the first one.

As the first coefficient is just the MD5 hash of the secret, our first idea is to check whether we can quickly find a pre-image of the coefficient. So we encode it as hex and look it up online, but this does not provide any results. So it seems, the secret is actually random. Quite obvious in hindsight. Brute-forcing the hash does not seem reasonable because of the size of p and the many possible values for the secret.

After some time, we then notice that we can reconstruct the other coefficients because they are deterministically calculated based on the first coefficient. This brought us to our second idea to simply recover all coefficients and compute the secret. For that we modified the challenge code to initialize the coefficients with self.coeffs = [0, coeff1] instead of self.coeffs = [self.secret]. With that, we can easily run the provided calc_coeffs method and calculate all other coefficients.

def next_coeff(self, val):
    return int(md5(val.to_bytes(32, byteorder="big")).hexdigest(),16)

def calc_coeffs(self):
    for i in range(1,self.n+1):
        self.coeffs.append(self.next_coeff(self.coeffs[i-1]))

Now our polynomial is initialized; the only difference being the secret set to 0.

We can now recover the secret using the one secret share that was provided to us.

share_y := f(share_x) = s + a_1 * x + ... + a_k * x^k mod p
y' = f'(share_x) = 0 + a_1 * x + ... + a_k * x^k mod p

=> share_y = s + y' mod p
=> s = share_y - y' mod p

This gives us the secret and we quickly verify that this is correct by computing the MD5 hash and comparing it to the first coefficient. Then, we seed the random module and decrypt the encrypted flag.

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

Writeup#

Writeup