Electric

from longnight import nosleep

When I run it I get b"m'7Y\xcaZ\xb4\x06\xbd\x92\xae\xf1B\x15\xd1IP1a\xdcs\xde&\xadWz\xb4\x12\xab\xa5]\x1e\x83\x98\xc6\xa9\x89\t\xa9\tNW\x9c\xe0\n\x9f\x11\x83\xa1\xd1\x03\xad"

Category: Reversing

Solver: MarDN, Liekedaeler

Flag: GPNCTF{wHy_1s_th3re_pyTHon_in_my_c_ahHh1!}

Writeup

The challenge consists of a simple python script which imports an encoding function enc from a library called script. A dummy flag gets read in and encoded with the enc function and there is a comment which contains the encoded real flag. Additionally, script is given as a shared object compiled with CPython for x86-64 with debug information.

Let’s reverse this!

The task seems to be rather straight-forward, so we powered on Ghidra and took a look into the library. After locating the enc function, we saw that it had about 800 lines of decompiled code. Too much for our post-midnight brains, we closed Ghidra again and went to identify some properties of the cipher in a purely black-box way.

Step one: How long is our flag?

When encoding some dummy strings with enc, we could make some interesting discoveries:

• The flag had to be of even length, otherwise we would get an error.
• In general, a longer input would yield a longer output, even if the lengths weren’t the same.

This means that we can easily find out the length of the flag by brute-forcing it:

from script import enc

flag = "GPNCTF{aa}"
ciphertext = b"m'7Y\xcaZ\xb4\x06\xbd\x92\xae\xf1B\x15\xd1IP1a\xdcs\xde&\xadWz\xb4\x12\xab\xa5]\x1e\x83\x98\xc6\xa9\x89\t\xa9\tNW\x9c\xe0\n\x9f\x11\x83\xa1\xd1\x03\xad"

# detect length of flag
for i in range(0, 100):
    if len(enc(flag)) == len(ciphertext):
        break
    # insert two more a
    flag = flag[:-1] + 'aa' + flag[-1:]

print(flag)

Turns out the flag has to consist of 34 characters, plus GPNCTF{}. That’s quite a lot of information, but it would be useless if the cipher would have good avalanche effect¹. It’s easy to test that out now.

Confusion and diffusion

To make an encoding like this hard to reverse, similar inputs should produce vastly different outputs. Changing an input character should change multiple output bytes (diffusion), and an output byte should be dependent on as many input characters as possible (confusion)². Luckily for us, the cipher at hand does not exhibit any of these properties.

When testing out two very similar strings, for example GPNCTF{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} and GPNCTF{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab}, we notice that only one byte of the output changes. Additionally, when we test what happens if we change different characters, it is always other output bytes that change. This means that we can easily brute-force the flag from here on.

Step two: Byte by byte

First, we test which input character changes which output byte by going through the input string, changing up one character at a time and noting which output byte changes. This relationship is saved in a dictionary.

Afterwards, we can iterate over the input string again, this time iterating over every possible character until the corresponding output byte matches that of the flag (Editor’s note: those steps could also be performed together, but we did it like this during the competition).

If done like that, the encoded input should match the given encoding of the flag. This means that we have found the flag!

Here’s the complete python script that solves the challenge:

from script import enc

flag = "GPNCTF{aa}"
ciphertext = b"m'7Y\xcaZ\xb4\x06\xbd\x92\xae\xf1B\x15\xd1IP1a\xdcs\xde&\xadWz\xb4\x12\xab\xa5]\x1e\x83\x98\xc6\xa9\x89\t\xa9\tNW\x9c\xe0\n\x9f\x11\x83\xa1\xd1\x03\xad"

# detect length of flag
for i in range(0, 100):
    if len(enc(flag)) == len(ciphertext):
        break
    # insert two more a
    flag = flag[:-1] + 'aa' + flag[-1:]

dict = {}
flag2 = flag

# find relationship between input and output bytes
for i in range(0, len(flag)):
    # change up one character
    flag2 = flag2[:i] + chr(ord(flag[i])+1) + flag2[i+1:]
    for j in range(0, len(enc(flag))):
        # compare for every character in output
        if enc(flag2)[j] != enc(flag)[j]:
            dict[i] = j
            break
    else:
        continue
    flag2 = flag

# brute-force output one character at a time
for i in range(0, len(flag)):
    for j in range(0, 128):
        flag2 = flag2[:i] + chr(j) + flag2[i+1:]
        if enc(flag2)[dict[i]] == ciphertext[dict[i]]:
            flag = flag2
            break

print(flag)