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:

The objective is to find , 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 .

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 and apply modulo , we will get the value of .

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

This system of modular congruences can be solved using the Chinese Remainder Theorem (CRT), which will output the value of . If is sufficiently large, the modulo will not have effect and we will find the exact value of .

All these prime numbers must be less than , and we can use a maximum of . These limits are enough to get the because it is a 256-bit number, and will have a maximum of 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.