# HTB University CTF 2023 - Brains & Bytes [CRYPTO]
In this markdown, I will publish and explain all my solvers as I played for the team of Mohammed Premier University (UMP)
## [Easy] MSS

### Overview
We are giving the following [server.py](https://github.com/hackthebox/uni-ctf-2023/blob/main/uni-ctf-2023/crypto/%5BEasy%5D%20MSS/challenge/server.py) script which contain the *MSS* class.

class MSS:
    def __init__(self, BITS, d, n):
        self.d = d
        self.n = n
        self.BITS = BITS
        self.key = bytes_to_long(os.urandom(BITS//8))
        self.coeffs = [self.key] + [bytes_to_long(os.urandom(self.BITS//8)) for _ in range(self.d)]

    def poly(self, x):
        return sum([self.coeffs[i] * x**i for i in range(self.d+1)])

    def get_share(self, x):
        if x > 2**15:
            return {'approved': 'False', 'reason': 'This scheme is intended for less users.'}
        elif self.n < 1:
            return {'approved': 'False', 'reason': 'Enough shares for today.'}
        else:
            self.n -= 1
            return {'approved': 'True', 'x': x, 'y': self.poly(x)}
    
    def encrypt_flag(self, m):
        key = sha256(str(self.key).encode()).digest()
        iv = os.urandom(16)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        ct = cipher.encrypt(pad(m, 16))
        return {'iv': iv.hex(), 'enc_flag': ct.hex()}

### MSS Class analysis
Let's examine the MSS class and discuss each of its functions:

1. `__init__()`: This is the class constructor. It uses the following parameters to initialise the MSS (Multi-Secret Sharing) scheme: `n` (number of shares permitted), `d` (degree of the polynomial), and `BITS` (bit length for randomness). It produces the polynomial's coefficients and a random key which is in the coefficient of $x^0 =1$.
2. `poly(x)`: This method evaluates the polynomial defined by the coefficients in `self.coeffs`   at the given a value `x`.
3. `get_share(x)`: For a given `x`, this method returns a share. It determines whether there are still enough shares and whether the supplied `x` less than `2^15`. It returns a share with the evaluated `y`-value of the polynomial at `x` if the necessary requirements are met. Shares that are available are reduced in number by one for each request.
4. `encrypt_flag(m)`: This method uses AES in CBC mode to encrypt a message `m` (in this case, the `FLAG`). It uses SHA-256 to extract a key from the starting key, creates a random initialization vector (IV), then encrypts the data. The end product is a dictionary that has both the encrypted message and the IV.
### Vulnerability
Now let's talk about the weakness for `x=0`:
Denoting the polynomial in the class by: $$p(x) = \sum_{i=0}^d p_i x^i = p_0 + p_1 x +p_2x^2 + \ldots p_dx^d$$
A check is made in the get_share function to see if `x` is bigger than $2^{15} =32768$. It passes the check and the share is given without any modular reduction if x is zero.
The evaluation of the polynomial at `x=0` returns $p_0$, which is the key. This indicates that the key is directly visible by requesting a share with `x=0`.

Since the key is used to derive the AES key for encrypting the `FLAG`, if an attacker requests a share with `x=0`, they can obtain the key directly. With this key, they can then decrypt the encrypted `FLAG` after using sha256 algorithm to derive the AES key.

In summary, the vulnerability lies in the lack of preventing an attacker to ask a share for `x=0`, allowing them to retrieve the key and subsequently decrypt the encrypted FLAG.

### Python Script

from pwn import * 
import json
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad


address = '83.136.251.50'
port    =  54878
r = remote(address, port)
def json_recv():
    line = r.recvline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)
    
r.recvuntil(b"query = ").decode()
to_send ={"command":"get_share","x":str(0)}
json_send(to_send)
rvd = json.loads(r.recvline()[:-1])

r.recvuntil(b"query = ").decode()
to_send ={"command":"encrypt_flag"}
json_send(to_send)

flag = r.recvline_contains(b"Here is").split(b" : ")[1][:-1]
flag = json.loads(flag)
iv   = bytes.fromhex(flag["iv"])
enc  = bytes.fromhex(flag["enc_flag"])

key = sha256(str(rvd["y"]).encode()).digest()

cipher = AES.new(key, AES.MODE_CBC, iv)
print(unpad(cipher.decrypt(enc),16).decode())
#HTB{thr3sh0ld_t00_sm4ll_______CRT_t00_str0nk!}

## [Easy] MSS Revenge
This challenges is a rectification for the previous challenge, that means our previous solution is not the intendend one (Clearly from the flag phrase).

Let's analyze the changes and devise a strategy to obtain the secret key.

### Overview

In this challenge we are given [server.py](https://github.com/hackthebox/uni-ctf-2023/blob/main/uni-ctf-2023/crypto/%5BEasy%5D%20MSS%20Revenge/challenge/server.py) which modifies the `get_share` method, now it includes an additional check for `x`, ensuring that it is both greater than 0 and less than $2^{15}$.

    def get_share(self, x):
        if x < 1 or x > 2**15:
            return {'approved': 'False', 'reason': 'This scheme is intended for less users.'}
        elif self.n < 1:
            return {'approved': 'False', 'reason': 'Enough shares for today.'}
        else:
            self.n -= 1
            return {'approved': 'True', 'x': x, 'y': self.poly(x)}

### Analysis
To retrieve the secret key, a fresh approach is necessary. Because there are so few shares available (limited by $n<d$), we are unable to do a direct Lagrange interpolation. Alternatively, we can aggregate several evaluations of the polynomial at various primes by using the Chinese Remainder Theorem ([CRT](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#:~:text=In%20mathematics%2C%20the%20Chinese%20remainder,are%20pairwise%20coprime%20(no%20two))).

### A solution:

Here's a methodical approach:

- Choose a collection of unique prime numbers that are all less than $2^{15}$ (15-bit primes). Since the hash size is 256-bit then we need $\lceil\frac{256}{15} \rceil = 18$ prime number and requested share.
- Utilise these primes to determine the polynomial's evaluation points $(q,p(q))$ modulo $q$. We know that $$p(q)= p_0 + p_1 q +p_2q^2 +\ldots +p_d q^d \mod q =p_0 \mod q$$ for each prime number $q$.
- Calculate the residues ($key = p_0 \mod M$) using the chinese remainder theorem such that $M = \prod_q q$. Since we have many primes such that $M \geq2^{255}$ then we are sure that we retrieved the right $key=p_0$.
- hash the key and decrypt to get the flag.

### SageMath Script

from pwn import * # pip install pwntools
import json
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad


def json_send(hsh):
    request = json.dumps(hsh).encode()


def json_recv():
    line = r.recvline()
    return json.loads(line.decode())


pr = [getPrime(15) for _ in range(18)]

r = remote('94.237.48.55', int(45135))  
welcome = r.recvline()


points = []
for i in range(len(pr)):
    r.recvuntil(b"query = ").decode()
    to_send ={"command":"get_share","x":str(pr[i])}
    json_send(to_send)
    rvd = json.loads(r.recvline()[:-1])
    points.append((rvd["x"],rvd["y"]))
    
r.recvuntil(b"query = ").decode()
to_send ={"command":"encrypt_flag"}
json_send(to_send)

flag = r.recvline_contains(b"Here is").split(b" : ")[1][:-1]
flag = json.loads(flag)


mods = []
res = []
for i in range(len(points)):
    mods.append(points[i][0])
    res.append(lift(Mod(points[i][1],points[i][0])))
    

key = crt(res,mods)
iv = bytes.fromhex(flag["iv"])
enc = bytes.fromhex(flag["enc_flag"])

key1 = sha256(str(int(key)).encode()).digest()

cipher = AES.new(key1, AES.MODE_CBC, iv)


print(unpad(cipher.decrypt(enc),16).decode())

#HTB{R3venge_0f_7he_sm4ll_thr3sh0ld_!}

## [Medium] Mayday Mayday

### Overview

### Analysis

### Script

## [Hard] Zombie Rolled

### Overview

### Analysis

### Script