Javex' Blog

secuinside 2014 - "pillow" Writeup

 Sun 01 June 2014 by Javex

So the Secuinside CTF 2014 just finished. Overall we did okay, but could have rocked this one more. Unfortunately, there was a lot of reversing stuff, not my strong suit. However, the first challenge I attempted was one of those that really deserve to be categorized as crypto: It had literally no guessing! So let's get started!

The Example Packet

You get a zip with three files:

- PKI.pyc
- pillow_reader.pyc
- admin_secret.pcap

From here there are obviously two ways to go: Either tackle the pyc files by decompiling them or look at the pcap. Let's see the pcap first.

Screenshot of the TCP stream

This is the only data inside the pcap: A single TCP conversation. We can already see some things here: First of all, the hex values in the beginning look like a python representation (with the "L" at the end, it is typical for Python 2). Secondly, the first part seems to be plain, the latter part is either some weird binary format or it is actually encrypted. We can't do a lot from here right now so let's tackle the python files.

Decompiling Python

I am going to make this one really short, for one because because a lot of credit belongs to my teammates here (I don't know how exactly they accomplished it). Additionally, this was a very tedious but non-crypto part, just some roadblocks to get rid of.

Here are some facts:

  • The code is Python 3.2
  • Thus the usual tools like uncompyle2 won't work
  • uncompyle3 and unpyc3 failed as well
  • I think they finally used pycdc to get it running
  • Even then, some patches were necessary
  • Finally, the source code had to be manually fixed where the decompiler made errors, most of which was very straightforward

So here is PKI.py (with some modification made by me):

class PrivKey:

    def __init__(self, p, q, n):
        self.p = p
        self.q = q
        self.n = n
        self.l = (p - 1) * (q - 1)
        self.m = int(gmpy.invert(self.l, n))



class PubKey:

    def __init__(self, n):
        self.n = n
        self.n_sq = n * n
        self.g = n + 1


class PKI:

    def __init__(self, pubkey=None, privkey=None):
        if pubkey is not None:
            self.pubkey = pubkey
            self.privkey = privkey
            return
        self.privkey, self.pubkey = PKI.gen_keypair()


    @staticmethod
    def gen_keypair(bits = 512):
        p = get_prime(bits // 2)
        q = get_prime(bits // 2)
        n = p * q
        return PrivKey(p, q, n), PubKey(n)

    def encrypt(self, plain):
        pubkey = self.pubkey
        while True:
            r = get_prime(int(round(math.log(pubkey.n, 2))))
            if r > 0 and r < pubkey.n:
                break
        cipher = (pow(pubkey.g, plain, pubkey.n_sq) * pow(r, pubkey.n, pubkey.n_sq)) % pubkey.n_sq
        return cipher


    def decrypt(self, cipher):
        if self.privkey is None:
            raise AssertionError('Private key must be exist')
        if self.pubkey is None:
            raise AssertionError('Public key must be exist')
        privkey = self.privkey
        pubkey = self.pubkey
        plain = privkey.m * ((pow(cipher, privkey.l, pubkey.n_sq) - 1) // pubkey.n) % pubkey.n
        return plain

Some of the modifications include the part where it calls get_prime which was actually missing (you couldn't run the files natively, the PrimeUtils module was missing). However, there are two critically important functions here: encrypt and decrypt. We'll take a look at them soon.

First look at what pillow_reader.py decompiles to:

import socket
import struct
import sys
import binascii
import gmpy
from PKI import PKI
from PKI import PubKey
g_guestkey = b'\xc3\xa1\xc3\xa7\xc2\xac\xc2\xa9\x19c\x0c\xc3\xb0'
g_pki_client = PKI()
g_pki_server = PKI()


def s2i(s):
    b = s2b(s)
    t = binascii.hexlify(b)
    return int(t, 16)


def b2s(b):
    res = ''
    for x in b:
        res += chr(x)

    return res


def s2b(s):
    res = b''
    for x in s:
        res += bytes([
            ord(x)])

    return res


def i2s(i):
    d = hex(i)
    if d[-1] == 'L':
        d = d[:-1]
    if d[:2] == '0x':
        d = d[2:]
    if len(d) % 2 == 1:
        d = '0' + d
    res = bytes.fromhex(d)
    res = b2s(res)
    return res


def create_socket(host, port):
    global s
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((host, port))
    return s


def exchange_key():
    s.recv(1024)
    write(hex(g_pki_client.pubkey.n), False)
    data = read(1024, False)
    if data[-1] == 76:
        data = data[:-1]
    n = int(data, 16)
    return PubKey(n)


def write(data, with_encryption = True):
    plain = data
    if with_encryption:
        if not len(data) < 4.63871e+18:
            raise AssertionError
        data = None(g_pki_server.encrypt(s2i(data)))
    size = b2s(struct.pack('<I', len(data)))
    send_data = size + data
    s.send(s2b(send_data))


def read(size, with_encryption = True):
    size_str = s.recv(4)
    print(size_str)
    if not size_str:
        size_str = s.recv(4096)
        print(size_str)
    size = struct.unpack('<I', size_str)[0]
    data = s.recv(size)
    if size != len(data):
        print('Wrong data size.\n')
        sys.exit(1)
    if with_encryption:
        data_int = s2i(b2s(data))
        data = i2s(g_pki_client.decrypt(data_int))
    return data


def read_files(authkey, filenames):
    cmd = 'cat '
    for filename in filenames:
        cmd += filename + ' '

    cmd = cmd.rstrip() + '\n'
    write(authkey + cmd)
    res = ''
    for _ in range(len(filenames)):
        res += read(1024)

    return res


def main():
    global s, g_pki_server
    if len(sys.argv) < 2:
        print('Usage> %s <host> <port> <filename> <optional:authkey>' % sys.argv[0])
        return 1
    host = sys.argv[1]
    port = sys.argv[2]
    filename = sys.argv[3]
    if len(sys.argv) >= 5:
        key = sys.argv[4]
    else:
        key = g_guestkey
    s = create_socket(host, int(port))
    pubkey_server = exchange_key()
    g_pki_server = PKI(pubkey_server)
    print(read_files(key, [
          filename]))

if __name__ == '__main__':
    main()

Don't worry, we'll cover it. Hopefully I removed all my modifications from it so this should be very close to the original source code.

encrypt and decrypt

Take a good look at those functions, write them down. The first thing you can do when you find such a pair of decrypt and encrypt is look at the correctness to get a feeling for what happens inside it. What you want to see is if plain = decrypt(encrypt(plain)) holds. While you do it, you will notice a very complex formula. I leave the execution of this step as an exercise to the reader, but if you are stuck just ask in the comments.

While doing the correctness, I noticed it looked very similar to the Paillier Encryption Scheme. If you look at your formula and compare it with the one on Wikipedia you will notice that it is actually the same, so we have here an implementation of it (actually, it is heavily "inspired" by this code).

If you read Wikipedia or have some cryptographic experience you know that this scheme is secure under assumptions we consider to currently hold, thus if the implementation is correct & secure (which it seems) then you cannot break the system itself.

But you can notice that this is a homomorphic encryption. If you don't know what this means, you need to read up on it: This is the key property we will use for our attack later on.

The Protocol and the Ciphertext

Before we do that though, we need to look at what we actually want to achieve: Where is the flag? What's in the pcap and what does it mean? If we take a good look at pillow_reader.py we can see the key methods exchange_key and read_files. The key exchange sends its own public key and receives the server's public key. That's the plain part we saw in the pcap above.

It then encrypts a message with the sever's public key that contains cat file1 file2 .... It also prepends an auth_key and this is what we are missing: There is a guest key in the source code but it surely won't allow you to read the flag. So we have to assume that it is hidden inside the ciphertext. However, as shown above, it is highly unlikely that we will be able to decrypt it.

But what we can do is replay the message captured in the pcap. A prerequisite is that the server always sends the same public key (otherwise, we wouldn't be able to replay the message, it was encrypted for a specific key). We do that and get a response similar to this:

Read [secret]
To get the flag concatenate flag1 and flag2

So it seems that we can replay the message just fine and it seems it is reading the file secret and giving us the content. So instead of reading secret we now want to read flag1 and flag2.

For this we need to modify the ciphertext in such a way that we request those two files (either in one or two requests).

Modifying the Ciphertext

Remember homomorphic encryption from above? Great, we use that now. There are two key properties here:

Enc(m1) * Enc(m2) --> m1 + m2
Enc(m1)^x --> m1 * x

This is just roughly pictured what we can do to the ciphertext: We can add stuff to the message by multiplying two encryptions. But we can also multiply the plaintext with a value.

Let's tackle addition first: Via trial and error we found out that in order to change the last character of the filename we need to encrypt something like 256 * desired_value. This means that if we want to change the last character from t (as in secret) to u we need to set desired_value to 1, for v it would be 2 and so on. Note that we can also overflow the value and start from the top (so we can reach things like a). We don't use this property in the final attack, though.

Next, we take a look at multiplication: Our idea here is to make some space in the ciphertext so we can append our own text. Basically we want to append null bytes that we can then fill with the above technique. So how do you achieve this on a plaintext, represented as a number? Answer: By shifting the ciphertext by one byte which essentially means multiplication by 256. Thus, if you want to have x characters of space after the original plaintext, you need to multiply the original plaintext by 256 ^ x.

So if we want to achieve this on the ciphertext, we need the exponentiation from above: Enc(m1) ^ (256 ^ x) which yields additional nullbytes at the end of the plaintext. We can now fill these nullbytes with the above method of adding values (and since everything is null now, we cann achieve any character we want).

So as a result, if we want to turn cat secret into cat secret flag1 flag2, we need to first make room for it and then add the string flag1 flag2. Since we need a space after secret the length of the string is 12. (Implementation detail: There is a newline at the end that needs to be replaced by this space and then the newline in turn needs to be appended at the end).

So let's make room and add our string:

Enc(m1) ^ (256 ^ 12) * Enc(" flag1 flag2")

Note

In reality, exponentation can be performed modulo N squared so you can keep your value small (otherwise it would quickly explode).

And if we now request this ciphertext, it actually reads all three files. Amazing, isn't it? Sadly, I lost the flag and the original output. However, I have the modified source code of pillow_reader where I added some methods that do the core work, including a method that tests the above behaviour. Just take a look at it if you are interested in the details:

import socket
import struct
import sys
import binascii
import gmpy
from PKI import PKI
from PKI import PubKey
g_guestkey = b'\xc3\xa1\xc3\xa7\xc2\xac\xc2\xa9\x19c\x0c\xc3\xb0'
g_pki_client = PKI()
g_pki_server = PKI()


data = [
    0x80, 0x00, 0x00, 0x00, 0x1f, 0x59, 0x85, 0x6d,
    0xbb, 0xbe, 0x90, 0x99, 0x5c, 0xf9, 0x49, 0x75,
    0xaf, 0xd9, 0x4d, 0xcf, 0x46, 0xbf, 0x2d, 0x16,
    0xd8, 0xb8, 0xa3, 0x75, 0x46, 0x85, 0xd3, 0xeb,
    0x37, 0x65, 0xd6, 0x91, 0x84, 0x62, 0x37, 0x8a,
    0x2f, 0x7e, 0x94, 0x81, 0x82, 0xe8, 0x4a, 0x85,
    0x7a, 0x25, 0xbe, 0x05, 0x7a, 0x12, 0x2e, 0x9d,
    0x65, 0xe3, 0x2f, 0xb0, 0x1a, 0x98, 0x4f, 0x44,
    0x2e, 0x78, 0x1f, 0xa0, 0x2e, 0x8a, 0x4d, 0x27,
    0x28, 0xb1, 0xa4, 0xc3, 0xea, 0x39, 0x05, 0xaa,
    0x95, 0xab, 0x9f, 0xba, 0x7b, 0x7d, 0xfa, 0x3b,
    0x39, 0x11, 0x6d, 0x49, 0xc1, 0x0d, 0x16, 0x17,
    0x25, 0xaa, 0x0b, 0xee, 0xac, 0x18, 0xb7, 0xa2,
    0xa9, 0xc9, 0xd5, 0x5a, 0x0b, 0xf6, 0xf1, 0xa2,
    0xb2, 0xca, 0x90, 0x3e, 0xb1, 0x50, 0x86, 0x99,
    0x5b, 0x2f, 0x77, 0xd7, 0x7d, 0x3f, 0x01, 0x67,
    0x87, 0x08, 0xee, 0x60
]
data = bytes(data)

def s2i(s):
    b = s2b(s)
    t = binascii.hexlify(b)
    return int(t, 16)


def b2s(b):
    res = ''
    for x in b:
        res += chr(x)

    return res


def s2b(s):
    res = b''
    for x in s:
        res += bytes([
            ord(x)])

    return res


def i2s(i):
    d = hex(i)
    if d[-1] == 'L':
        d = d[:-1]
    if d[:2] == '0x':
        d = d[2:]
    if len(d) % 2 == 1:
        d = '0' + d
    res = bytes.fromhex(d)
    res = b2s(res)
    return res


def create_socket(host, port):
    global s
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((host, port))
    return s


def exchange_key():
    s.recv(1024)
    write(hex(g_pki_client.pubkey.n), False)
    data = read(1024, False)
    if data[-1] == 76:
        data = data[:-1]
    n = int(data, 16)
    return PubKey(n)


def write(data, with_encryption = True):
    plain = data
    if with_encryption:
        if not len(data) < 4.63871e+18:
            raise AssertionError
        data = None(g_pki_server.encrypt(s2i(data)))
    size = b2s(struct.pack('<I', len(data)))
    send_data = size + data
    s.send(s2b(send_data))


def read(size, with_encryption = True):
    size_str = s.recv(4)
    print(size_str)
    if not size_str:
        size_str = s.recv(4096)
        print(size_str)
    size = struct.unpack('<I', size_str)[0]
    data = s.recv(size)
    if size != len(data):
        print('Wrong data size.\n')
        sys.exit(1)
    if with_encryption:
        data_int = s2i(b2s(data))
        data = i2s(g_pki_client.decrypt(data_int))
    return data


def read_files(authkey, filenames):
    cmd = 'cat '
    for filename in filenames:
        cmd += filename + ' '

    cmd = cmd.rstrip() + '\n'
    write(authkey + cmd)
    res = ''
    for _ in range(len(filenames)):
        res += read(1024)

    return res


def add_shit(original, to_add):
    new = g_pki_server.encrypt(to_add)
    original_data = s2i(b2s(original[4:]))
    result = s2b(i2s(original_data * new))
    return struct.pack('<I', len(result)) + result


def mutate_string(original, goal):
    start = "cat secret"
    add_num = 0
    old_overflow = False
    for index, c in enumerate(goal[::-1], 1):
        orig_c = start[-index]
        if ord(orig_c) > ord(c):
            overflow = True
            goal_num = 256 - ord(orig_c) + ord(c)
            print("%s > %s --> goal = 256 - %d + %d = %d" % (orig_c, c, ord(orig_c), ord(c), goal_num))
        else:
            overflow = False
            goal_num = ord(c) - ord(orig_c)
            print("%s < %s --> goal = %d - %d = %d" % (orig_c, c, ord(c), ord(orig_c), goal_num))
        if old_overflow:
            goal_num -= 1
        print("Add num: 256 ** %d * %d" % (index, goal_num))
        add_num += 256 ** index * goal_num
        old_overflow = overflow
    return add_shit(original, add_num)


def append_string(original, to_append, replace=""):
    if replace:
        original = mutate_string(original, replace)
    first, tail = to_append[0], to_append[1:]
    chars = len(tail)
    original = add_shit(original, ord(first) - 0xA)
    orig_int = s2i(b2s(original[4:]))
    enlarged = pow(orig_int, 256 ** chars, g_pki_server.pubkey.n_sq)
    for index, c in enumerate(tail[::-1]):
        new = g_pki_server.encrypt(256 ** index * ord(c))
        enlarged *= new
    result = s2b(i2s(enlarged))
    print(len(original), len(result))
    return struct.pack('<I', len(result)) + result


def test_homo():
    msg1 = s2i(b2s(b'fooooooo'))
    msg2 = s2i(b2s(b'YOMOMMAISSOFAT!!!!'))
    expected = msg1 + msg2
    c1 = g_pki_client.encrypt(msg1)
    c2 = g_pki_client.encrypt(msg2)
    res = g_pki_client.decrypt(c1 * c2)
    assert expected == res

    msg1 = s2i(b2s(g_guestkey + b'cat secret'))
    app = 256 ** 30
    expected = msg1 * app

    c1 = g_pki_client.encrypt(msg1)
    res =g_pki_client.decrypt(pow(c1, app, g_pki_client.pubkey.n_sq))
    assert expected == res


def main():
    global s, g_pki_server
    test_homo()
    if len(sys.argv) < 2:
        print('Usage> %s <host> <port> <filename> <optional:authkey>' % sys.argv[0])
        return 1
    host = sys.argv[1]
    port = sys.argv[2]
    #filename = sys.argv[3]
    #if len(sys.argv) >= 5:
    #    key = sys.argv[4]
    #else:
    #    key = g_guestkey
    s = create_socket(host, int(port))
    pubkey_server = exchange_key()
    print(pubkey_server.n)
    g_pki_server = PKI(pubkey_server)
    print(data)
    #s.send(add_shit(data, 256 * 256 * 1 + 256 * 189))
    #s.send(add_shit(data, 20551425315438157721877760))
    #s.send(mutate_string(data, "cat " + "x" * 6))
    #s.send(mutate_string(data, "[xxxx"))
    #s.send(append_string(data, " flag1 flag2\n"))
    #s.send(append_string(data, "flag1 flag2\n"))
    s.send(append_string(data, " flag1 flag2\n"))
    #s.send(data)
    ret = read(4096)
    print(ret)
    ret = read(4096)
    print(ret)
    ret = read(4096)
    print(ret)
    #print(read_files(key, [
    #    filename]))

if __name__ == '__main__':
    main()

So that concludes this writeup of one of the best crypto challenges I have seen so far: No part of it was guessing and most of it actually was cryptographic work exploiting a flaw in a provable-secure encryption scheme! What to take away from this flaw? Always authenticate your ciphertext!

hack.lu 2013 - "What's wrong with this?" Writeup
Sat 11 January 2014 by Javex

Note

This article took some time to get published. I wrote it in November but I had to put off finishing it until now. Sorry for the delay.

So the hack.lu 2013 CTF is over and it was a blast again. Thanks to everyone for their participation and especially …

read more

iCTF 2013 "secretvault" Writeup - Why ECB is a Bad Idea
Sat 07 December 2013 by Javex

So I wasn't too fond of this year's iCTF with their ever returning complexity that drives your focus away from the actual exploiting and security fixes. The concept sounded great but as with the previous two years it was just to much work besides acutally exploiting stuff. And the results …

read more

plaidCTF 2013 "pyjail" Writeup - Part II: Breaking our brain (nonalpha code)
Tue 23 April 2013 by qll

Note

This is part two of the two part process describing how we broke the pyjail challenge on plaidCTF 2013. The first part described how we broke the sandbox. This part describes how we circumvented the nonalpha stuff.

I will now describe how we encoded our payload and what we …

read more

plaidCTF 2013 "pyjail" Writeup - Part I: Breaking the Sandbox
Mon 22 April 2013 by Javex

Note

This is part one of the two part process describing how we broke the pyjail challenge on plaidCTF 2013. The second part is written by qll and covers the nonalpha stuff. This first part covers how to escape the sandbox.

The pyjail challenge was one of the toughest ones …

read more

plaidCTF 2013 "cyrpto" Writeup
Mon 22 April 2013 by Javex

A lot of the plaidCTF 2013 challenges were binary this year. Since I am more the Python guy, I looked for Python code to exploit. There were only very few of those and most of them weren't even about Python :-(

One of those challenges was "cyrpto". I don't know if …

read more