Rating:

Blind

=====

Task description

----------------

> Pull the flag...if you can.

>

> nc blind.q.2019.volgactf.ru 7070

>

> server.py

Solution

--------

TL;DR: Given was a RSA signature oracle, which refused to sign certain values,

that allow to execute shell commands. Use homomorphism property of RSA to

blind a value, ask the oracle to sign it and the inverse of the blinding

factor. Multiply both signature to obtain the signature of the unblinded value.

The server implements a simple plaintext protocol which allows to execute

several commands (`cd`, `cat`, `sign`, `exit`, and `leave`) with optional

parameters. Each line send to the servers starts with a signature (integer)

followed by the command and parameters; all separated by spaces.

All commands, except for `sign`, `ls`, and `dir`, validate the signature

before executing the command with its parameters. While `sign` still takes a

signature, it does not validate it. Instead, it asks for a command to sign.

Rather than signing the command with all parameters, it only signs the command

without the any parameter (see the `shlex.split` at `cmd == 'sign'`). However,

all other commands validate the signature over the command including all

parameters. Additionally, `sign` refuses to sign the commands `cat` and `cd`.

The signature is implemented as standard RSA signature without padding. We

shortly introduce the basics of RSA and modular arithmetics to understand the

vulnerability of the service.

We start with basic modular arithmetic. Our following calculations will work

like the usual calculations on integers, except for a final modulus operation.

To denote the modulus n, we append “ (mod n)” to the right, meaning that all

calculations to the left are subject to modulo operations. The modulo returns

the remainder after a division, i.e., a + b (mod n) means, that you first add

a and b, divide it by n and take the remainder as final value. For example

6 + 4 (mod 7) is 3, because 6 + 4 = 10, which divided by 7 is 1 with a

remainder of 3, i.e., 10 = 1 * 7 + 3. Many integers will have inverses in

modular arithmetic, which have the property, that, if you multiply the integer

with its inverse, you get 1. The inverse of a value a is denoted a^{-1}, so

a * a^{-1} = 1 (mod n). For a concrete example: 3 * 5 = 1 (mod 7), so 5 is the

inverse of 3 and vice versa. Having covered the most important facts about

modular arithmetics, we will continue with RSA, which makes use of it.

RSA is an asymmetric cryptography procedure that allows to encrypt and sign

values. We will focus on signatures here. For RSA, you have a public key and

a private key. The private key is used to sign values, while the public key

is used the verify the signature on values. To generate those keys, RSA first

generates two distinct primes p and q. Both primes are multiplied to form the

modulus n = p * q. You chose a value for the public exponent e, which must be

relatively prime to (p-1)(q-1). In almost all cases e = 65537 is chosen,

because it is robust and improves performance. To get the private exponet d, we

have to calculate the inverse of e (mod (p-1)(q-1)), i.e., we have

e * d = 1 (mod (p-1)(q-1)). The algorithm to calculate the inverse is called

the extended euclidean algorithm. We will not cover it here, since these

details are not important. Since we know p and q, we can calculate (p-1)(q-1)

and thus d. Since p and q are not public, an adversary cannot calculate d

without unfeasible computational resources (in fact, calculating d from the

modulus and the public exponent is equivalent to factoring n, i.e., getting p

and q from n, which is believed to be a hard problem). The values n and e form

the public key for RSA, while the values n and d form the private key.

To sign a message m with RSA, the signer calculates s = m^d (mod n). To verify

the signature, anyone can check if s^e = m (mod n), because e and n are public.

If and only if this equivalence is true, s is a valid signature for m. Since d

is private, only the signer can create signatures (the truth is: the crypto

community believes that this is the case, however, there is no proof yet).

Our vulnerable service however provides an RSA signature oracle, which,

unfortunately, does not sign all values we want it to sign. Nonetheless, there

is a property of RSA that we can use to our advantage: the multiplicative

homomorphism. This property states: Sign(m\_0) * Sign(m\_1) = Sign(m\_0 * m\_1).

Mathematically, this boils down to: m\_0^d * m\_1^d = (m\_0 * m\_1)^d (mod n).

In our attack, we combine this property together with inverses in a technique

called blinding. Assume we want a signature on m = `cat flag` (as byte sequence

which is interpreted as an large integer). Our RSA signature oracle will refuse

to sign it. However, if we choose a value k and multiply m with it, i.e.,

m\_b = m * k, there is (with high probability) no `cat` inside m\_b and we can

get a signature on m\_b using the oracle. Next, we will ask the oracle to sign

k^{-1} (the inverse of k), which is also possible since it is just a random

looking value. Using the homomorphism, we get Sign(m * k) * Sign(k^{-1} =

Sign(m * k * k^{-1}) = Sign(m * 1) = Sign(m). Yay, we just have to multiply

these two signatures (mod n) to obtain the signature for m. However, there is

one caveat left.

If you remember, the RSA signature oracle only signs the command without the

parameters, but the signatures validation is on the command with all parameters.

Our blinded value and the inverse of k are no valid command, however, they still

can contain bytes that are interpreted by shlex.split, e.g., spaces, quotes,

etc. To fix this issue, we just iterate over different values for k until we

found a value for k, for which k^{-1} and m * k contain no spaces and so on.

To summarize, our attack involves the following steps:

1. Set m = `cat flag`

2. Choose a random k

3. Calculate the inverse of k: k^{-1} (mod n)

4. Set m\_b = m * k

5. If m\_b or k^{-1} contain forbidden characters (spaces, quotes, etc.) goto

step 2.

6. Run the `sign` command with m\_b as base64 to obtain s\_0

7. Run the `sign` command with k^{-1} as base64 to obtain s\_1

8. Set s = s\_0 * s\_1 (mod n)

9. Run `cat flag` command with the signature s

10. Submit flag and gain 100 points.

You can find the python code with all these steps in exploit.py, which will

print the flag `VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}`. The original server

is provided as server.py. Note that you have to generate a new RSA key pair

to use it, since the attack cannot recover the private key. If you are lazy,

try:

n = 35712023278405967281092707335001742500880380505674767204982483064840572151157

e = 65537

d = 9178529992240568120034874381658747740627015878387549261101264681449421824145

To conclude, never use RSA without padding to avoid such attacks that involve

the homomorphic property of RSA. If possible, use the PSS padding scheme or

avoid RSA at all in favor of ECC signatures (e.g. Ed25519).

Original writeup (https://github.com/b4ckspace/ctfwriteups/tree/master/2019.03%20VolgaCTF%20Qualifiers/blind).