CSCG2021 Secure Bank (writeup)

6 minute read Published: 2021-06-06

In the "Secure Bank" challenge of the Cyber Security Challenge Germany (CSCG) 2021 we are presented with a protocol that is meant to ensure that we can only login if we know a certain PIN.

In a real world application this PIN could be generated as in TOTPs that are used for 2 factor authentication. In the challenge the PIN is simply generated randomly:

challenge = os.urandom(32).hex()
msg = 'Challenge: ' + challenge

pin = rng.randint(0000, 9999) # Random PIN
run_protocol(pin, msg)

The protocol that the server runs is executed with a message and a PIN. The protocol resembles a password based authenticated key exchange (PAKE) since a shared secret that is bound to the PIN is obtained. Normally, we would have to know the PIN to compute the shared secret. However, a flaw lets us guess and check every possible PIN. The shared secret is then used to encrypt the challenge message, and the resulting ciphertext is sent to the client. The client is supposed to send back the challenge. In short: if we can obtain the random challenge from a run of the protocol we win✨.

The challenge description also advises us not to try an online brute-force attack. To enforce this we actually have to recover the challenge twice from two consecutive protocol runs, where each has a randomly chosen PIN. That's $10000^2 = 100$ million possible combinations! Assuming 30 online guesses per second it would take 38.58 days to perform this many guesses. Even with 100 million guesses we only have a probability of success of $1-(1-\frac{1}{10000^2})^{10^8}\approx 0.63 = 63\%$. Therefore it seems much more economical (and fun!) to actually try and break the challenge.

The protocol makes use of DH parameters from RFC 3526 using a generator $g=2$ and computes everything modulo some large prime.

The protocol asks for three values from the client: The first two are an email address (that is used as a user ID) and a public parameter that is presumably generated by the generator $g$.

The client performs the following steps:

generate a user_id
generate a secret $x_a \in \mathbb{Z}_p$ where $p$ is the large known prime
compute the public parameter $c_{\mathrm{pub}} = g^{x_a}$

The user_id and the public parameter $c_{\mathrm{pub}}$ are sent to the server.

The server then computes a bunch of values. You can skip over them, but here they are for completeness sake:

$\mathrm{id}_a = g^{H(\mathrm{user\_id})}$
$m_c = \mathrm{id}_a^{-\mathrm{pin}}$
$t_a = c_{\mathrm{pub}} \cdot m_c$
$m_s = \mathrm{id}_b^{\mathrm{pin}}$
sample a random $r_b \in \mathbb{Z}_p$
$t_b = g^{r_b}$
$s_{\mathrm{pub}} = t_b \cdot m_s$

The shared secret is computed as:

$$z = t_a^{r_b}$$

However, $z$ alone is not sufficient: the key is computed as the hash of all values that occurred in the protocol run:

### Calculate shared secret
z = dh_exchange(t_a, r_b)
key = SHA256.new(long_to_bytes(id_a) + long_to_bytes(ID_SERVER) + long_to_bytes(user_pub) + long_to_bytes(server_pub) + long_to_bytes(pin) + long_to_bytes(z)).digest()

Luckily, we already know id_a, ID_SERVER, user_pub (=$c_{\mathrm{pub}}$), server_pub (=$s_{\mathrm{pub}}$). The only values that are missing are pin and z.

A major flaw that lets us abuse this protocol is that we know the discrete logarithm of the server's public parameter from the implementation:

ID_SERVER = dh_genpub(int.from_bytes(b'server', 'big'))

The discrete logarithm is simply int.from_bytes(b'server', 'big')!

Using this information we can perform an offline brute force attack on the PIN by computing a candidate $g^{\hat{r}_b}$ as:

$g^{\hat{r}_{b}} = s_{\mathrm{pub}} / g^{x_b \cdot \mathrm{pin}}$

We can compute this value because $x_b$, the server's private part was made public. The above formula follows from the last computation in the server:

$$\begin{aligned} s_\mathit{pub}&=t_b \cdot m_s \\ &=g^{r_b} \cdot {\left(g^{x_b}\right)}^{\mathrm{pin}} \end{aligned}$$

By guessing the PIN we obtain a candidate $g^{\hat{r}_{b}}$. We can then compute a candidate $\hat{z}$ as:

$$\hat{z} = {\left(g^{\hat{r}_{b}}\right)}^{x_a - \mathrm{pin} \cdot H(\mathrm{user\_id})}.$$

Using this candidate $\hat{z}$ and the guessed PIN we can derive a symmetric key to decrypt the received ciphertext. We can check whether the key is correct by comparing the decrypted text against the known plaintext prefix "Challenge: ".

Voilà! Now we need 5000 offline guesses in expectation to recover the correct PIN! Therefore this completely breaks the security of the protocol: a PAKE should prevent an adversary from guessing offline.

The flaw we discovered is analogous to one that can occur "in the real world" with SPAKE2 and the challenge description hints at this: "The SP bAnK E2 introduced a new protocol [...]". I've also found a blog post detailing this issue here. It also describes how one could pick arbitrary public parameters for which nobody knows the discrete logarithm. This is possible, since the server never actually uses the discrete log in the protocol. Therefore it is sufficient to have a single public value that everyone trusts - but nobody has its discrete log.

Full Exploit

from Crypto.Hash import SHA256

from gmpy2 import powmod
import pwnlib

s = pwnlib.tubes.process.process('ncat --ssl xxx-secure-bank.challenge.broker.cscg.live 31337'.split())

user_id = "Some ID"
email_hash = SHA256.new(user_id.encode()).digest()
email_num = int.from_bytes(email_hash, "big")

from server import *


#user_pub = pow(email_num, -1, server.PRIME)
user_x = 1337
user_pub = powmod(GEN, user_x, PRIME)
id_a = powmod(GEN, email_num, PRIME)

server_x = int.from_bytes(b'server', 'big')

def break_pin(server_pub, enc, known_plaintext):
    for pin in range(10000):
        print(pin)
        # Compute candidate g_rb
        g_rb = (server_pub * powmod(powmod(GEN, server_x * pin, PRIME), -1, PRIME)) % PRIME
        # Compute candidate z
        z = powmod(g_rb, user_x + -pin * email_num, PRIME)
        key = SHA256.new(long_to_bytes(id_a) + long_to_bytes(ID_SERVER) + long_to_bytes(user_pub) + long_to_bytes(server_pub) + long_to_bytes(pin) + long_to_bytes(z)).digest()
        # Test pin against known plaintext
        aes = AES.new(key, AES.MODE_ECB)
        dec = aes.decrypt(enc)
        if known_plaintext in dec:
            dec = str(Padding.unpad(dec, 16), 'utf-8')
            print(f"Decrypted: {dec}")
            challenge = dec[len(known_plaintext):]
            return challenge
    print("PIN not found")

def do_break(known_plaintext):
    s.sendline(f"{user_id}")
    s.sendline(f"{user_pub}")
    print(s.recvline())
    server_pub = int(s.recvline().split()[-1])
    enc = bytes.fromhex(str(s.recvline().split()[-1], 'utf-8'))
    return break_pin(server_pub, enc, known_plaintext)

s.sendline(f"{do_break(b'Challenge: ')}")
do_break(b'CSCG{')

Full Exploit

See Also