MSS Revenge

This challenge is the same as MSS, with a patched unintended solution.

Review of the challenge

The server creates a polynomial with random 256-bit coefficients:

$$ P(x) = \mathrm{key} + a_1 x + a_2 x^2 + \dots + a_{30} x^{30} $$

The objective is to find $\mathrm{key}$, which is used to derive an AES key to encrypt the flag. The server allows us to evaluate the polynomial 19 times with values of $0 < x \leqslant 2^{15}$.

We are not able to recover the full polynomial because we would need a minimum of 31 shares.

Solution

The problem of this challenge is that the polynomial is defined over the integers. As a result, if we evaluate $P(n)$ and apply modulo $n$, we will get the value of $\mathrm{key} \mod{n}$.

Knowing this, we can do the same but with prime numbers. The objective is to get this system of congruences:

$$ \begin{cases} P(p_1) = \mathrm{key} \mod{p_1} \\ P(p_2) = \mathrm{key} \mod{p_1} \\ \dots \\ P(p_k) = \mathrm{key} \mod{p_k} \\ \end{cases} $$

This system of modular congruences can be solved using the Chinese Remainder Theorem (CRT), which will output the value of $\mathrm{key} \mod{\prod p_k}$. If $\prod p_k$ is sufficiently large, the modulo will not have effect and we will find the exact value of $\mathrm{key}$.

All these prime numbers must be less than $2^{15}$, and we can use a maximum of $k = 19$. These limits are enough to get the $\mathrm{key}$ because it is a 256-bit number, and $\prod p_k$ will have a maximum of $15 \cdot 19 = 285$ bits.

Implementation

We can program the above procedure in Python:

io = get_process()

primes, remainders = [], []

for _ in range(19):
    p = getPrime(15)
    io.sendlineafter(b'query = ', json.dumps(
        {'command': 'get_share', 'x': p}).encode())
    r = json.loads(io.recvline().decode()).get('y')
    primes.append(p)
    remainders.append(r % p)

key = crt(primes, remainders)[0]

io.sendlineafter(b'query = ', json.dumps({'command': 'encrypt_flag'}).encode())  
io.recvuntil(b'[+] Here is your encrypted flag : ')
data = json.loads(io.recvuntil(b'}').decode())

iv = bytes.fromhex(data.get('iv'))
enc_flag = bytes.fromhex(data.get('enc_flag'))

key = sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc_flag), AES.block_size).decode()
io.success(flag)

Flag

And here we have the flag:

$ python3 solve.py 94.237.52.253:33222
[+] Opening connection to 94.237.52.253 on port 33222: Done  
[+] HTB{R3venge_0f_7he_sm4ll_thr3sh0ld_!}
[*] Closed connection to 94.237.52.253 port 33222

The full script can be found in here: solve.py.