nest
space-pirates.
Posted on

Space Pirates

tl;dr

Exploiting a flaw in Shamir's Encryption when a share and the calculation of the coefficients is known, into decryption of an afine cipher

Analysis

Shamir's Secret Sharing (SSS) is used to secure a secret in a distributed way, most often to secure other encryption keys. The secret is split into multiple parts, called shares. These shares are used to reconstruct the original secret.

Basically a polynomial is created using random coefficients, and shares are created for x = 0, x = 1 etc.

In our case, we can see that the first coefficient is the secret and that it's randomly generated:

Logi

However, we're also given the second coefficient at the encrypted file:

Logi

We can also see the way of calculating the next coefficients. Basically, coefficient[i + 1] = MD5(coefficient[i]), so this is somewhat of a MD5 chain:

Logi

Clearly, we can tell that the second coefficient that we are given is the MD5 of the secret. Sadly this is not reversible.

Breaking The Secret

Knowing the second coefficient, however, we can calculate every other coefficient using MD5. We can see that n is set to 10, so we only need to calculate the 9 first coefficients as we don't know the secret.

Therefore, we will have an equation of something like:

y = (coeff[0]x^0 + coeff[1]x^1 + coeff[2]x^3 + ... + coeff[9]x^9) % m

However, we know that coeff[0] is the secret, so this becomes something like:

y = (secret + coeff[1]x^1 + coeff[2]x^3 + ... + coeff[9]x^9) % m

Gets more clear now, right? We also have a pair of y and x. That pair tells us that if we put x = 21202245407317581090 in that polynomial, the output will be y = 11086299714260406068.

So let's sum up. We know y given x, we know m and we also know all coefficients other than secret. This means that coeff[1]x^1 + coeff[2]x^3 + ... + coeff[9]x^9 is known to us. Let's call that entire thing b. Summing up we have:

y = (secret + b) % m

This can be rewritten as:

y = (1secret + b) % m

We know that an affine cipher of type:

y = (ax + b) % m

can be decrypted as:

x = (a^-1)*(y - b)

where a^-1 is the GCD(a, m). Because a = 1, the GCD will be equal to 1. Therefore, it will look like this:

x = y - b

Solvescript

We assemble a python script

# solve.py
import base64
from Crypto import Random
from Crypto.Cipher import AES
from random import randint, randbytes,seed
from hashlib import md5
import math

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

def calc_coeffs(init_coeff, coeffs):
	for i in range(8):
		coeffs.append(next_coeff(coeffs[i]))

def rev_secret(init_coeff, init_x, init_y, p):
	coeffs = [init_coeff]
	calc_coeffs(init_coeff, coeffs)
	# init_y = (secret + coeffs[1] * init_x + coeffs[2] * init_x^1 + ... + coeffs[9] * init_x^9) % P
	sum = 0

	for i in range(len(coeffs)):
		init_y -= coeffs[i] * (init_x ** (i + 1))

	GCD = math.gcd(p, 1)
	secret = (GCD * (init_y)) % p
	return secret

secret = rev_secret(93526756371754197321930622219489764824, 21202245407317581090, 11086299714260406068, 92434467187580489687)

enc = '1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c'

seed(secret)
key = randbytes(16)
cipher = AES.new(key, AES.MODE_ECB)
enc_FLAG = cipher.decrypt(bytes.fromhex(enc)).decode("ascii")
print(enc_FLAG)

Flag

Running the script:

Flag