iCTF 2013: mathconsole

Dec 10, 2013

mathconsole (iCTF 2013): writeup

For the iCTF 2013 competition, I developed the service called mathconsole. This writeup will be a a little bit different than usual: I will try not only to explain how to exploit this service, but also to justify some design choices I made while developing it. Additionally, I will also give some insights about how teams have exploited and patched this service.

iCTF is a CTF competition organized by UCSB, its rules are different than usual CTF and tend to change from year to year. You can read the description of the 2013 edition rules here. My main goal for this service was to implement a server with two well-known vulnerabilities found in the gaming consoles Wii and Playstation 3. As far as I know, both vulnerabilities have been discovered by team Twiizers/fail0verflow [1][2][3][4].

The first vulnerability (found in the Wii console) is caused by wrongly checking a RSA signature, the second (found in the Playstation 3) is caused by using a non-random nonce in the generation of an ECDSA signature. I will explain these vulnerabilities in detail later in this writeup. Unfortunately, nobody exploited the second vulnerability (about the ECDSA signature), probably because the other one was easier and, given the structure of the competition, it was not really worthing to exploit it. If you are not interested in this vulnerability, you can skip sections "Authorization level bug" and "ECDSA vulnerability".

This zip file contains the source code of the service, the scripts used to generate benign traffic, the .deb package installed on teams' machines, and all the other files I will refer during this writeup (forgive me for the "not exactly clean" code).

Overview

This service has been written in Python 2.7 and it is implemented as a classical forking server. For the networking part, I mainly reused the code I wrote for the service PowerPlan that I wrote for the previous iCTF (you can read a very good writeup here about it). The service is listening on port 9898; when you connect to it you get the following message:

When a command is inserted (in the format <command>|<p1>|<p2>) a signature is asked. Different commands require different authorizations that a user can get by providing a (base64 encoded) 256-byte long signature. We will see how a valid L1 signature can be trivially forged, and that both the verifications of L2 and L3 signatures contain fundamental problems that can be exploited. When a correct signature is provided, the specified command will be executed.

The commands sum, multiply, mod, and power just perform the corresponding mathematical operations and return the result to the user. write allows the user to write a file in the folder service_files (we used this command to set the flags in teams' machines). read_protected returns the content of a file in the service_files folder but it requires a password. Specifically, it checks that the provided password matches with the first line of the content of the file that has been requested. We used this command to check that the flags we stored in the teams' machines were not deleted.

Finally, read_encrypted1 and read_encrypted2 read and return the content of a file in the folder service_files, however they need the correct authentication. In theory, it would not be possible to execute them without having the correct RSA and ECDSA private keys (you can find both private keys in file private_keys.txt). In practice, the vulnerabilities of this service allow an attacker to skip almost entirely the verification of the RSA signature and to recover the private ECDSA signature.

In this service, flags were written by us using the command write. Specifically, the first line was a random password protecting a file (which value was only known by us), whereas the second line was the flag. The name of the file was the flag_id. Attackers had to write exploits that were able to steal the flag corresponding to the provided flag_id. To do so, the only possibility was to use the commands read_encrypted1 or read_encrypted2. Replay attacks were not possible since the requested flag_id (and so the command that an attacker needed to sign) were random and always different.

Anti-decompilation

I tried to make this service a little bit tricky to be decompiled. From my experience, uncopyle2 is usually able to recover "almost perfectly" the original Python code, given the compiled .pyc file. My goal was to create a .pyc file that was perfectly working when executed by the Python interpreter, but that made the decompilation process to fail.

By randomly fuzzing a .pyc file and looking a little bit in the Python bytecode specification I realized that:

a division operation (like this: a = 0/0) is compiled to the following 10-byte sequence: 15 5A 12 00 64 04 00 64 04 00
changing the second byte from 0x5A to 0x00 makes uncompyle2 to fail with the following error:
[...]
194    LOAD_CONST        0
197    LOAD_CONST        0
200    BINARY_DIVIDE     None
201    STOP_CODE         None
202    <18>              None
203    STOP_CODE         None

204    LOAD_CONST        0
207    LOAD_CONST        0
210    BINARY_DIVIDE     None
211    STORE_NAME        'a'

214    LOAD_CONST        0
217    LOAD_CONST        0
220    BINARY_DIVIDE     None
221    STORE_NAME        'a'
[...]
Syntax error at or near `STOP_CODE' token at offset 201

So, I inserted in my code (at the "top-level" of the game_server.py file) the following code (that obviously is never executed):

#uncompyle trick
fff=False
if(fff):
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0
    a = 0/0

compile.py compiles game_server.py in game_server.pyc (using the "standard" Python mechanism), then it looks for the byte sequence corresponding to the 15 division instructions I showed before. When it finds this sequence, it patches the second byte of the first division instruction from 0x5A to 0x00. This makes uncompyle2 unable to decompile the .pyc file correctly.

The easiest way to fix this is to change the byte at 0xE7 from 0x00 to 0x5A in the file game_server.pyc. After this this modification, uncompyle2 is able to recover the original source code.

Signatures and authorization levels

Before executing a command, the service checks if the provided signature grants the authorization level required to execute it. For instance, to execute the command multiply users have to provide a L1 signature, to execute the command power a L3 signature is necessary, and to execute the command sum they can provide either a L1 or a L2 signature. Every signature is 256-byte long, before sending it to the server, it needs to be base64-encoded.

I will now explain how L1, L2, and L3 signature are legitimately created by scripts generating benign traffic (see benign1.py, benign2.py, benign3.py, benign4.py). In this context, command is the full string of the requested command, for instance: "mod|23|5":

L1: a sha1 hash of the sent command:
hash = self.sha1(command)
cert = "X"*(256-len(hash)) + hash
Of course, this can be trivially forged by anyone.
L2: a RSA signature of the sent command:
signer = PKCS1_v1_5.new(private_key_rsa)
digest = SHA.new()
digest.update(command)
cert = signer.sign(digest)
To compute it, I use a (secret) private key and the PyCrypto library. See the file benign1.py for the complete source code.
L3: an ECDSA signature of the sent command:
cert_key = private_key_ec.sign_digest(hash,k=4)
cert = "X"*(256-len(cert_key)) + cert_key
To compute it, I use a (secret) private key and the Python ecdsa library (install it by using pip install ecdsa). See the file benign2.py for the complete source code.

Authorization level bug

The code managing this authorization-checking functionality is contained in functions init_access and check_security_level. I implemented this in a deliberately over-complicated way, to be able to hide a subtle bug. My goal was to allow the command read_encrypted2 to be used providing a L3 signature (even if in the textual description of the commands it is written that read_encrypted2 needs a L2 signature). This will be relevant for the full exploitation of the ECDSA vulnerability, if you are not interested in it, you can just skip this section.

I will now explain the permission checking in terms of mathematical operations, the actual implementation is slightly different. A function indexOf() is defined, such that, given a tuple p = <command, permission>, it returns an index between 1 and 24. For instance: indexOf(<sum, L3>) = 3 and indexOf(<multiply, L1>) = 4. The variable access_summary is computed with the following formula:

access_summary=∏pP((primes[indexOf(p)])2)

Where primes is a sorted list of all the prime numbers up to 97 and P is a list of tuples <command, permission> as specified in the textual description of each command. For instance:

<sum,L1>∈P,but<power,L2>∉P

To check if a given command C, can be accessed by a signature of level L, it is checked if:

(access_summary%primes[indefOf(C,L)])==0

If true, then the command C can be executed by providing a signature of level L, otherwise it cannot.

indexOf(<read_encrypted2, L3>) = 21. The list of primes has been deliberately set incorrectly, so that primes[21] = 75 (instead of 79). Since access_summary contains twice the factor 5 (corresponding to the tuple <sum, L2>) and 3 (corresponding to the tuple <sum, L1>), access_summary is divisible by 75 and so the command read_encrypted2 can be used by providing a L3 signature, differently from the textual specification.

RSA vulnerability

As I said, in implementing the RSA vulnerability I tried to mimic the one found in the Wii console [2]. For a general overview of how RSA can be used to sign a message look here [5]. In theory, to produce a valid L2 signature (that can be used to read the flags by invoking the command read_encrypted1 or read_encrypted2), it is necessary to have the original private key. However, there is a fundamental bug in how the signature it is checked:

def verify_with_pubkey_rsa(self,public_key_rsa,local_hash,certificate):
    m = public_key_rsa.encrypt(certificate,None)[0]
    m = "\x00"*(256-len(m)) + m
    remote_hash = m[-20:] #the padding is not checked
    libc = ctypes.CDLL("libc.so.6")
    if(libc.strncmp(local_hash,remote_hash,20)==0):#strncmp is REALLY bad here
        return True
    else:
        return False

As you can see strncmp is used, instead of memcmp (I used ctypes to directly invoke the libc implementation of strncmp). strncmp returns 0 and stops the comparison between the signed hash and the computed one as soon as 0x00 bytes are encountered in the same position in both strings. In addition, the padding of the original (20-byte long) message is not checked.

The easiest way to exploit this is to provide a signature of all 0x00 bytes: given the mathematical properties of RSA, this makes m = "\x00" * 256. At this point it is just necessary to provide a command whose sha1 hash starts with 0x00. It is possible to bruteforce it by changing the value <key> of the command read_encrypted1 or read_encrypted2 (<key> cannot be bigger than 4000, however, as we will see, we do not actually need so many tries).

Assuming that the sha1 function returns values with a random distribution, the probability of randomly find such a hash in N tries is:

1−(255/256)N

For instance, trying as <key> all the numbers between 0 and 2000, the probability of finding a command whose hash starts with 0x00 is more that 99.9%. So, a value of <key> generating a hash with the wanted property can be found in a negligible amount of time. This attack is implemented in exploit.py.

It is important to notice that, even if the checking of the padding had been implemented correctly, it would have been still possible to forge a signature. Refer to [2] for further details.

An easy patch to this vulnerability is to change strncmp to memcmp (or use the == Python operator). Alternatively, it is possible to directly use the verify function provided by PyCrypto (that also checks the validity of the padding).

To have a complete and working exploit, it is also necessary to revert the manipulation that the service does to the content of the file read before sending it to the client. In fact, the commands read_encrypted1 use (<key> % 256) as a xor-key, whereas read_encrypted2 works similarly, but it rotates right the value (<key> % 256) before xoring it to a new character. Both operations can be trivially reverted (knowing the value of <key>).

ECDSA vulnerability

The code generating the ECDSA signature (see benign2.py):

cert_key = private_key_ec.sign_digest(hash,k=4)

uses a fixed value for k. This is a well-known implementation problem that can be exploited to recover the private_key. See [4] (or [3] at minute 35:30) for the mathematical explanation.

To do so, it is necessary to obtain two tuples <message1, signature1>, <message2, signature2>. This can be done by recording the signatures used when the command power (that requires a L3 signature) is invoked (benign2.py invokes such a command). The service nicely prints these values on standard output. The script recover_ecdsa_key.py recovers the private key in this way.

The code performing the mathematical operations is the following:

#using the same variable names as in: http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
n = curve_order
s1 = string_to_number(sig1[-24:])
s2 = string_to_number(sig2[-24:])
r = string_to_number(sig1[-48:-24])

z1 = string_to_number(sha1(c1))
z2 = string_to_number(sha1(c2))

sdiff_inv = inverse_mod(((s1-s2)%n),n)
k = ( ((z1-z2)%n) * sdiff_inv) %n
r_inv = inverse_mod(r,n)
da = (((((s1*k) %n) -z1) %n) * r_inv) % n

recovered_private_key_ec = SigningKey.from_secret_exponent(da)

Refer to the file recover_ecdsa_key.py for the full implementation.

After the recovery of the private key it is possible to use it to generate a valid L3 signature that, due to the bug explained in the section "Authorization level bug", can be used to invoke the command read_encrypted2.

Once the private key has been recovered, an attacker can produce traffic indistinguishable from the "benign" one. In fact, in this case, the vulnerability is not in the service, but it is in how the client (that I wrote to generate "benign" traffic) use the (secret) private ECDSA signature.

The generated benign traffic never targets the read_encrypted2 using a L3 signature both because this is against the textual description of the permissions and because, otherwise, it would have been impossible for teams to distinguish between benign and malicious traffic.

For this reason, an easy patch is to change the value 75 in the list of primes to 79, making the command read_encrypted2 inaccessible by using a L3 signature (see section "Authorization level bug").

What happened during the iCTF

Unfortunately nobody exploited the ECDSA vulnerability, even if two hours before the ending of the competition I gave this hint:

HINT: http://xkcd.com/221/ (and 75 is not prime!)

35 exploits were submitted, out of which 18 were working. 12 working exploits were just a copy of the exploit for the RSA vulnerability I developed (teams could buy exploits from us). Interestingly, one team obfuscated the source code of its attack. This was pointless, in fact, teams could not see the source code of attacks developed by other teams.

Some teams submitted exploits generating a signature different than "\x00" * 256. Specifically, some signatures with the following property were generated:

rsa_public_key.encrypt((b64decode(signature)))[−20]==0x00

Given the bug in the hash comparison, such signatures were still considered as valid if the hash of the submitted command was starting with a 0x00 byte.

The first working exploit was submitted by PPP (congratulations!).

I did not dig into all the teams' machines, but from a quick look I have seen some teams patching the service by changing the strncmp instruction either with the standard "==" Python operator or the memcmp libc function.

References

[1] http://hackmii.com/2008/04/keys-keys-keys
[2] http://wiibrew.org/wiki/Signing_bug
[3] http://www.youtube.com/watch?v=PR9tFXz4Quc
[4] http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
[5] http://en.wikipedia.org/wiki/RSA_%28algorithm%29

CTF