Jorge Wants a Token

10 minutes to read

We are provided with the source code of the server in Python. On the one hand we have administation.py (the main file), and on the other we have library.py (auxiliary functions). The server gives us these options:

$ nc 0.cloud.chals.io 15980

    __  __           __   ____
   / / / /___ ______/ /__/ __ \____
  / /_/ / __ `/ ___/ //_/ / / / __ \
 / __  / /_/ / /__/ ,< / /_/ / / / /
/_/ /_/\__,_/\___/_/|_|\____/_/ /_/
Welcome to the HackOn administration.  

1. Log In - With token.
2. Register.
3. Make a complain.
4. Exit

[*]Option:

Source code analysis

The only useful options are 1 and 2:

def menu():
    banner()
    show_options()
    for i in range(32):
        try:
            option = int(input("[*]Option: ").strip())
        except:
            print("Wait, what?")
            exit()
            
        if option == 1:
            token = input("Token, please: ").strip()
            login(token)
            
        elif option == 2:
            new_user = input("Username: ").strip()
            algorithm = input("Alg: ").strip()
            register(new_user, algorithm)

        elif option == 3:
            print("Fuck no, send bizum to this number +34 631223245 to get the flag")  

        else:
            print("Goodbye!!")
            exit()

Although we can only use the 2 at the moment. Moreover, we have a total of 32 consultations to the server.

Registration process

When registering, they ask for a username and an algorithm to create a JWT token (JSON Web Token):

def register(username: str, algorithm: str):
    payload = dict()
    payload['username'] = username
    payload['iat'] = os.urandom(32).hex()
    payload['status'] = "Student"
    payload['dfh'] = "3+3=2, right?"
    token = jws.encode(json.dumps(payload), algorithm)  
    print(token)

In the JWS class from library.py we can see how the encode method works:

    def encode(self, payload, algorithm="HSMAC256"):
        if algorithm not in self.ALGORITHMS:
            raise ValueError(f"ALgorithm {algorithm} not supported.")
        
        try:
            self.payload = json.loads(payload)      
        except:
            raise Exception("Invalid payload format.")

        if algorithm == "HSMAC256":
            self.header = '{"alg":"HSMAC256","typ":"JWT"}'
        
        elif algorithm == "ES512":
            self.header = '{"alg":"ES512","typ":"JWS"}'

        elif algorithm == "ESBLK":
            self.header = '{"alg":"ESBLK","typ":"JWS"}'

        signature = self.sign(payload,self.header, self.key, algorithm)
        token = ".".join([JWS.base64url_encode(data).decode() for data in [self.header.encode(),payload.encode(),signature]])  
        return token

This method calls sign:

    def sign(self, payload, header, key:bytes, algorithm="HSMAC256"):
        sign_input = ".".join([header, payload])
        if algorithm not in self.ALGORITHMS:
            raise ValueError(f"ALgorithm not supported.")

        if algorithm == "HSMAC256":
            signature = hmac.new(key, sign_input.encode(), digestmod=sha256).digest()  
        else:
            signature = self.ecdsa_sign(sign_input, key, algorithm)

        return signature

And here it is distinguished between the HSMAC256 algorithm (based on SHA256 and HMAC) and the ES512 and SBLK algorithms. In this second case, ECDSA is used as a way to sign the JWT token, with the following method:

    def ecdsa_sign(self, input:str, key:bytes, algorithm:str):
        if algorithm == "ES512":
            hash = sha512()
        else:
            hash = blake2b(digest_size=46)
            
        hash.update(key + urandom(16))
        nonce = bytes_to_long(hash.digest())
        sign = self.privKey.sign(bytes_to_long(sha256(input.encode()).digest()), nonce)  
        
        return long_to_bytes(sign.r)+ b'&&' +long_to_bytes(sign.s)

And the differences between ES512 and ESBLK is the hash function to use. On the one hand, the SHA512 function, and on the other, blake2b. For the rest, the use of ECDSA is identical.

ECDSA implementation

The code for the ECDSA is almost correct (more information here). In order to sign messages, it uses a generator point $G$ of the P-384 curve and SHA256 as hash function. Then, the program computes:

$$ h = \mathrm{SHA256}{(m)} $$

$$ r = (k \cdot G)_x $$

$$ s = k^{-1} \cdot \left(h + x \cdot r\right) \mod{n} $$

Where $n$ is the order of the curve and $k$ is a random nonce. The output is the tuple $(r, s)$.

The problem is in the generation of the nonces; and specifically, when using ESBLK algorithm, since blake2b is used with a digest length of 46 bytes. Since the curve is the P-384 (384 bits, 48 bytes), these nonces have 2 bytes that are always null (The most significant bytes).

As a result, we can use a lattice-based attack and LLL to solve the Hidden Number Problem. I found this technique in this website, which points to section 4 of this paper.

Hidden Number Problem

The HNP is usually defined as:

$$ t_i \cdot \alpha + a_i \equiv b_i \pmod{p} $$

Where $\alpha$ is the hidden number and both $t_i$ and $a_i$ are known, given $i$ equations. We can apply the ECDSA signature formula to this format:

$$ s_i \equiv k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \pmod{n} $$

$$ s_i k_i \equiv h_i + x \cdot r_i \pmod{n} $$

$$ r_i \cdot x + h_i \equiv s_i k_i \pmod{n} $$

$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv k_i \pmod{n} $$

We can define a lattice that contains the solution for the HNP. In the definition, we can use the lattice spanned by the columns of:

$$ M = \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} $$

Where $X$ is an upper bound for the $b_i$ values. Notice that the vector $(b_1, \dots, b_i, \alpha, X \alpha / p, X)$ is in the lattice:

$$ \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} \cdot \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_i \\ \alpha \\ 1 \end{pmatrix} = \begin{pmatrix} c_1 p + \alpha t_1 + a_1 \\ c_2 p + \alpha t_2 + a_2 \\ \vdots \\ c_i p + \alpha t_i + a_i \\ X \alpha / p \\ X \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_i \\ X \alpha / p \\ X \end{pmatrix} $$

Observe that $c_i$ are just arbitrary integer numbers, they are irrelevant because we are working $\mod{p}$. The target vector is supposed to be short, so that it can be found in the reduced lattice after applying LLL.

If we apply this procedure on the ECDSA equations we have, we will try to find the vector $(k_1, \dots, k_i, X x / n, X)$. We know this is a likely to be a short vector within the lattice since all $k_i$ are at most 46-byte numbers and the lattice is defined over a 48-byte order.

Once the HNP is solved, we will obtain the private key $x$ to sign any JWT token.

The other option given by the server is login:

def login(token: str):
    if jws.verify(token):
        try:
            _,payload,_ = JWS.load_token(token)
            payload = json.loads(payload)
            status = payload['status']
            username = payload['username']
            iat = payload['iat']
            dfh = payload['dfh']
        except:
            print("Problem in your payload detected.")
            exit()

        if status == "Rector" and type(dfh) == int == type(iat):
            flag = bytes_to_long(FLAG.encode())
            assert flag.bit_length() > 600
            if iat > dfh and dfh.bit_length() == 200 and isPrime(dfh):
                print(f"Rector, this belongs to you: {pow(iat,flag,dfh**2)}")
            else:
                print("Bad Parameters.")
        else:
            print(f"Welcome {username},your iat is {iat} and your status is {status}")     
            print(f"This is your public key: ")
            print(jws.pubKey.point.x(),jws.pubKey.point.y()) 
    else:
        print("Fail in Log In. Invalid Token.")

To get the flag (well, a result dependent on the flag), we have to pass some attributes to the payload of the JWT token. On the one hand status must be "Rector"; and then $\mathrm{iat}$ and $\mathrm{dfh}$ must be integer numbers with $\mathrm{iat} > \mathrm{dfh}$, and $\mathrm{dfh}$ a prime 200-bit number. If all this is fulfilled, the server shows us the result of:

$$ \mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2} $$

And we also know that the flag has more than 600 bits.

Discrete Logarithm Problem

In this case, we have to solve a Discrete Logarithm Problem (DLP). That is, find $\mathrm{flag}$ such that $\mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2}$, and knowing $\mathrm{iat}$ and $\mathrm{dfh}$.

In this case, there are several forms, since we control both $\mathrm{iat}$ and $\mathrm{dfh}$, and $\mathrm{dfh}$ is a prime number.

For example, if we say that $\mathrm{iat} = \mathrm{dfh} + 1$, the Newton’s binomial expansion in $\mod{\mathrm{dfh}^2}$ is:

$$ \begin{align*} \mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2} & = (\mathrm{dfh} + 1)^\mathrm{flag} \mod{\mathrm{dfh}^2} \\ & = \sum_{i = 0}^{\mathrm{flag}} {\mathrm{flag} \choose i} \cdot \mathrm{dfh}^i \mod{\mathrm{dfh}^2} \\ & = 1 + \mathrm{flag} \cdot \mathrm{dfh} + \sum_{i = 2}^{\mathrm{flag}} {\mathrm{flag} \choose i} \cdot \mathrm{dfh}^i \mod{\mathrm{dfh}^2} \\ & = 1 + \mathrm{flag} \cdot \mathrm{dfh} \end{align*} $$

So, we can find the value of flag easily (although $\mod{\mathrm{dfh}^2}$):

$$ \mathrm{flag} \mod{\mathrm{dfh}^2} = \frac{(\mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2}) - 1}{\mathrm{dfh}} $$

On the other hand, there are algorithms to solve a DLP modulo a power of a prime number (more information in this paper or in math.stackexchange.com). This was the method I used during the CTF.

So what we get is $\mathrm{flag} \mod{\mathrm{dfh}^2}$, that is, we get an incomplete result. For this reason, we must ask for another result from the server with another value $\mathrm{dfh}$, solve the DLP and use the Chinese Remainder Theorem (CRT), joining together the solutions untilwe have the entire flag (more than 600 bits).

Solution

For the first part of the challenge (recover JWT’s private key via ECDSA biased nonces) we can define this function that solves the HNP using LLL:

def get_private_key():
    h, r, s = [], [], []

    for _ in range(31):
        token = register('a', 'ESBLK')
        header, payload, signature = token.encode().split(b'.')
        r_i, s_i = map(bytes_to_long, base64_url_decode(signature).split(b'&&'))
        h.append(bytes_to_long(sha256(base64_url_decode(header) + b'.' + base64_url_decode(payload)).digest()))  
        r.append(r_i)
        s.append(s_i)

    p = int(generator_384.order())
    a = list(map(lambda s_i, h_i: pow(s_i, -1, p) * h_i % p, s, h))
    t = list(map(lambda r_i, s_i: pow(s_i, -1, p) * r_i % p, r, s))

    X = 256 ** 46

    raw_matrix = []

    for i in range(len(a)):
        raw_matrix.append([0] * i + [p] + [0] * (len(a) - i + 1))

    raw_matrix.append(t + [X / p, 0])
    raw_matrix.append(a + [0, X])

    M = Matrix(QQ, raw_matrix)
    L = M.LLL()

    for row in L.rows():
        if row[-1] == X:
            k = list(map(int, row[:-2]))
            x = (s[0] * k[0] - h[0]) * pow(r[0], -1, p) % p
            io.info(f'Private key: {x}')
            return x

Then, we have to generate a new JWT token to ask for the flag and solve a DLP. Since we need to solve several discrete logarithms and then use the CRT, we can use a loop. I decided to restart the connection in each iteration to use a total of 31 queries of register, so that the HNP is easier to solve:

def dlog_mod_power_prime(g, g_x, p, e):
    """
    Discrete Logarithm modulo prime power
    - Calculate x, such that g_x = g^x mod p^e
    Implementation source: Discrete Logarithms and Factoring, Eric Bach
    https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf
    """

    def theta(x, p, e):
        p_2e_1 = pow(p, 2 * e - 1)
        ret = pow(x, (p - 1) * pow(p, e - 1), p_2e_1) - 1 # we can use ^ 2*(p-1)p^(e-1)  

        assert ret % (p ** e) == 0
        return ret // (p ** e)

    p_e_1 = p ** (e-1)
    theta_a = theta(g, p, 2)
    theta_b = theta(g_x, p, 2)
    x = (theta_b * inverse(theta_a, p_e_1)) % p_e_1
    return x

crt_r, crt_m = [], []

for _ in range(4):
    io = get_process()
    x = get_private_key()

    key = long_to_bytes(x)
    jws = JWS(key)
    dfh = getPrime(200)
    token = jws.encode(json.dumps({
        'iat': dfh + 1,
        'status': 'Rector',
        'dfh': dfh,
        'username': '7Rocky',
    }))

    io.sendlineafter(b'[*]Option: ', b'1')
    io.sendlineafter(b'Token, please: ', token.encode())
    io.recvuntil(b'Rector, this belongs to you: ')
    enc = int(io.recvline().decode())
    io.close()

    f = dlog_mod_power_prime(dfh + 1, enc, dfh, 2)
    assert pow(dfh + 1, f, dfh ** 2) == enc
    crt_r.append(f)
    crt_m.append(dfh)

io.success(long_to_bytes(crt(crt_r, crt_m)).decode())

Flag

With this script we can get the flag:

$ python3 solve.py 0.cloud.chals.io 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 21527056898547024587609061810343314636054103071083534282832602787779906208125346961093976190169270897359572999836562  
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 18814722945154313480948727673868769998572454698779537940745768538072367594925761035156672852090498617182007108488964
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 33961003751330092278804628895767649698903687994164285766669837669581590400494603649396321858221791508300235658238462
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 2260618360756416815541341091789168739127662042173042144222183197102177554812745377485235625697522113617557847117469
[*] Closed connection to 0.cloud.chals.io port 15980
[+] HackOn{I_c4n_s33_b14s3d_N0nc3s_3verywh3r3_I_g0.0nc3_m0r3_s4g3_1s_4lways_4_g00d_fr13nd}

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