This post explains how I beat the capture-the-flag crypto challenge “CMS” during CyberSecurityRumble 2022, as part of the 0rganizers team.

Description

The challenge comes in the form of a web application, for which we are provided full source code and a running instance. The description of the challenge heavily hints at some improper use of the RSA cryptographic signature system. The goal is to access the admin account.

When a user successfully logs in with their password, the application issues them a web cookie containing a cryptographic signature over their username. Importantly, the signature is performed using what’s known as Textbook RSA, which means it turns the username into a number the straightforward way and applies the RSA permutation to it. This is generally insecure because it allows adversaries to take advantage of the homomorphic property of RSA to modify existing signatures in unintended ways.

For a quick refresher on the homomorphic property of RSA, here’s the gist of it: let’s say the key holder signs two messages $m_1$ and $m_2$ using the private exponent $d$. They compute $s_1 \equiv m_1^d \mod n$ and $s_2 \equiv m_2^d \mod n$. Now let’s say the adversary gets $s_1$ and $s_2$. They can compute $s’ \equiv s_1s_2 \mod n$ without knowing $d$, which is a valid signature for $m_3 \equiv m_1m_2 \mod n$ like so: $s_3 \equiv s_1s_2 \equiv m_1^dm_2^d \equiv m_3^d \mod n$.

Solution

To approach this in practice, we have to look at what the system will let us sign, and what we want to forge. It turns out that we are allowed to sign only usernames with letters, numbers and underscores, with at least 1 and at most 200 characters. We are also not allowed the trivial solution of signing the admin username directly, but we can sign any other username we want by registering a dummy account.

The admin username is willi_pyjCsgC, which, when interpreted as a number, is prime. If it were composite, we could make the system sign some factors and combine them. In this case, we cannot. We also cannot use addition under homomorphism, only multiplication and division.

After scratching my head and trying some different things, I noticed that I could sign the admin username concatenated with itself since it consists of only allowable characters. The result is also a multiple of the admin username, specifically by the number f = 0x100000000000000000000000001. If we could obtain a signature for this number, we could divide the first signature by it and obtain a valid admin credential. But we cannot sign that number directly since it doesn’t correspond to a valid username.

What we can do is obtain a signature by signing some username x, and then signing f*x as well, and dividing. Provided x is the right length, f*x is also a concatenation.

What follows is a full solution script implementing this strategy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import requests
import re

baseurl = 'http://cms.rumble.host/'

# must forge a signature for this username
admin_name = 'willi_pyjCsgC'

# we can get signatures for any other username
my_name = 'julie_bettens'
assert len(admin_name) == len(my_name)

# fetch RSA pubkey
homepage = requests.get(f'{baseurl}/').text
n = int(re.search(r'n = (\d*)', homepage).group(1))
e = int(re.search(r'e = (\d*)', homepage).group(1))

sigs = {}
for name in [my_name, 2 * my_name, 2 * admin_name]:
    passwd = 'dummy_password'
    rep = requests.post(f'{baseurl}/register', data={'name': name, 'passwd': passwd})
    assert rep.ok
    rep = requests.post(
        f'{baseurl}/login', data={'name': name, 'passwd': passwd}, allow_redirects=False
    )
    assert rep.ok
    msg, sig = rep.cookies['username'].split('||')
    sigs[msg] = int(sig)

f = 1 << len(admin_name) * 8 | 1
sig_f = sigs[2 * my_name] * pow(sigs[my_name], -1, n) % n
sigs[admin_name] = sigs[2 * admin_name] * pow(sig_f, -1, n) % n


rep = requests.get(
    f'{baseurl}/home', cookies={'username': f'{admin_name}||{sigs[admin_name]}'}
)
flag = re.search(r'CSR{.*}', rep.text).group(0)
print(flag)

Flag

CSR{help....heeellllppppp...im blind}