Challenge author: pspaul

Can you unravel the secret of the Soul Splitter?

The challenge features a console app written in python. The app will give you 16 shards to recover a soul from. In order to solve the challenge, you need to recover 20 souls in a row.

👹 I am the Soul Splitter!
👹 If you can recover 20 souls, I will tell you my secret.
👹 Here are 16 shards:
eJw7tOAQVvhoWgN2CQTkwif5aFoLXqOwaibCUhx6kawjYDAxmnG6gwtFC5HOJSq8KNZK2M34dWMEQQuSZgLBi8NiDCeRYAwXio+waMQb+LQNaqxOADuRC6fLiEgrAGgFZ9M=
eJx7NK3h0ALyINejaS2HFjwizwAuEEGyXqgGLjQ+Fg4Bm8myFkhxwQRacKvFKUWGzZheJlV3C9l60azF4zEsdoKdjdVitGjCiDW4PRQFFzkpA4unkfRiMQSruRSENgC1aWjz
eJx7NK3l0IJDCx5NawBRpEEuZA6JJnCRopgMrTicg1PvI0g4wDWj8OEKaGI1lXyM5gfaWkswtvFaS0A37UMKq0Ow6MUaoljtJTH5oygHAGsIY6k=
eJw7tOAQBnw0rQUHBxVy4dVIQAJDMz74aFoDil4wH02QSHvBNoPF8fgMN+TC6iACAQVXTZKnKQgvPFqBboGGHkokY3gH3dVw9cR6nXRPYzGZCnoJe5RgmBHwL4b3cScSwhAAzwprZw==
eJw7tODRtIZDCxDw0bQWZC4+yIUpRLRuLhLsIWgv3AtgBhKvBbsKiOV4XYBHEou38UEUk7jQQpskB5BoMUVakdxJlF4c4YVVLxa1QCFyPQx0KdZA5UIowOo0vNFPw/DCmwIAEvhqPw==
eJw7tOAQHD6a1gAl0CFWwUMLuCByLdjkEFqxSgOFuYhQhgty4XUXUXrJgVi0Qh0OdQncG1hdRpbNUCNJ0osSmkCnYNWM5ES8oY9bM15tUOPJDu1H0zqI1gt2CFqQkxhgDdRxNUVaAWDlaQs=
eJw7tOAQCfDRtAYEhwuF92haCw4ODkEuAvI4bMWhmXhIvL3E6300rYMI83A4mij7certQAkjHGZh1Y2mFkso47Uau5ENZOulwFoMJ1DfWgyfYQ1pLjzBSAgCAMi7Z1E=
eJw7tOAQFD6a1nBoATpEE3w0rQWZy4WpAa4Gq3EENePVCZSAygEpnNoJQ5K04vIykitRmC04jQErw6afCM0N5IYZlX2Nx24whdULeFyNmVQwfEJJROMMURrrJd/JALfqasU=
eJw7tOAQGfDRtIZDC7iIU9kCVQ7nQSCGbrgiLAagQxxWY1WLYQNR7sYOqa8Vh69RJIBMSi0mEDI4XUO2veS5GWw/auLCGUCYenGnLRJDi+hgQnMcBfYCAEf3ZgE=
eJw7tOAQmZALQj2a1oJP1aNpDXg0Y9eB10C8eol0Mxan4XAnmma42wg6EkMBQVej6EBzDheSKBEupU14UVkrRgghCSD7F5tOLMJIglw4TCXKJLwpE6tzsOglMY7AygFrHGc5
eJw7tODQgkfTGg4tIB7ClXMRVtmC0wguvLbi1EmUzXh1c6H5AqvXcJpI0M9kO5psrYTDCs1bcC5QJ5CNIdtCmZ9RzCNJL5pLqBlgSL5qwK8VqBI1bRIIXzRloKRNvrsBZP5qMw==
eJw7tOAQGD6a1nBoASkQqIGLKFVYmCDIhSKKIvloWguYD6RRzWpBMwC36eS5HcMQNCvR3E4OxKkVaDdBP3AR9CkeSYKORtOL4ndSNdM6tEjQSkTKwFBCWyfjdBEAhq5o6w==
eJw7tOAQBnw0rQFEtKCKtWAq5MIqC9aOCyJJcuFWRQji1YrVqUTqpcBaSn2LpBYjBAloxutjDL0EwgfFcuoGFloyIeRoAgmpBacZMN1oBuA1jxS78QQaF1ZR4iAAuWRoaQ==
eJw7tOAQHD6a1nJoAbEQqJiLeNXokAthTAPZenE7DcNMuBAJboYGB5JpXCSHEpGuxmImihDlIY1hA1HeoEYMEx3HyAFNZiDDLSaoH24ZWCV6HBPlZqhOFItI9zUCAgDPRWff
eJw7tOAQmZALU+jRtAYcHAxBLLoJaEVItnARqRSrErw2EzAFQy8R1sPtBTocwydYvYdVnAuHeqwuBatEcRtpQYZhNREOJ0Iv0TZDFXIhaaDc1URbi6QXh634o5Jom7GYDgCXuWrB
eJw7tOAQXvhoWgMuKS6CKrAZ1wJESLrJsJegXrymEK0XiwlcRPkX6kG8FhMwBMMIUjQT7WMizOGCqiHRSqgPuBC8BlRJHKZhhjapkLjURVZwITkSRxSTYS+SjwEqsWfH
👹 Recover the soul to prove you are worthy:

Walk through the code

When no environment vars are present, the main function loops 20 times. According to the output of the challenge connection, the challenge host also uses 20 here.

The loop is generating something, then asks for an input. If the given input does not match the expected input, the loop exits. If we complete all 20 iterations without exiting early, we get the flag.

This is python3, so input does not use eval anymore 🥲.

SOULS = int(os.getenv('SOULS', '20'))


def main():
    print('👹 I am the Soul Splitter!')
    print(f'👹 If you can recover {SOULS} souls, I will tell you my secret.')
    for _ in range(SOULS):
        soul, shards = generate_challenge()
        print(f'👹 Here are {len(shards)} shards:')
        print('\n'.join(shards))
        recovered = input('👹 Recover the soul to prove you are worthy: ')
        if recovered != soul:
            print('👹 Wrong! You are unworthy. ' + soul)
            return
        print('👹 You got lucky with this one...')
    print('👹 You haven proven yourself! Here\'s my secret:')
    print(FLAG)

generate_challenge will just call two functions: select_soul and split_soul. select_soul is just generating a random string of 16 characters. The string could look like this 'Rb6izPy6oVv-KLvYfR9VQg'.

SHARDS = int(os.getenv('SHARDS', '17'))


def select_soul():
    return secrets.token_urlsafe(16)


def generate_challenge():
    soul = select_soul()
    shards = split_soul(soul, SHARDS)
    return soul, random.sample(shards, SHARDS - 1)

In order to understand split_soul, we first have to have a look at soul_code and code_atoms.

soul_code will take our random string and make a qrcode from it. Note that error-correction is set to high.

def soul_code(data):
    code = qrcode.QRCode(
        border=0,
        error_correction=qrcode.constants.ERROR_CORRECT_H,
    )
    code.add_data(data)
    code.make()
    return code

Code atoms takes the qrcode and flattens the modules into a list of tuples.

def code_atoms(code):
    size = len(code.modules)
    atoms = []
    for y in range(size):
        for x in range(size):
            atoms.append((x, y, code.modules[y][x]))
    return atoms, size

The modules of the qrcode object are pretty much a boolean representation of the pixels of the code in a 2d array. For example, you can see one of the ID-squares as true & false values.

modules is a 2d list of booleans, representing the qr code like pixels

So after code_atoms is done, we have a list of pixels.

The atoms list contains tuples with an x and y coordinate, and the value of that coordinate (true or false)

Now we finally get to split_soul. The function will shuffle these atoms. This will order them randomly. The atoms are then grouped into equally sized chunks. Each chunk now contains some of the pixels of the qrcode. The chunk is called shard_code.

def split_soul(soul, n):
    code = soul_code(soul)
    atoms, size = code_atoms(code)
    random.shuffle(atoms)
    atom_count = len(atoms)
    r = atom_count % n
    atoms_per_shard = atom_count // n
    shard_codes = []
    for i in range(0, atom_count - r, atoms_per_shard):
        shard_codes.append(atoms[i:i + atoms_per_shard])
    for i in range(r):
        shard_codes[i].append(atoms[-1 - i])
    return [atoms_token(size, shard_code) for shard_code in shard_codes]

Using list-comprehension, shard_code is turned into something else using atoms_token. The function is not very spectacular. It calls atoms_to_text, compresses the result and turns it into base64. So atoms_to_text contains all the magic.

atoms_to_text first make a 1d-buffer that can hold all pixels of the qrcode. The buffer is later used like a 2d-buffer (buf[y * size + x]).

The shard_code is now called atoms again, yay. The list of pixels is now turned back into a pseudo-2d-array again. So now we have a buffer with some randomly selected pixels of a qrcode.

That buffer is then iterated, but every second line is skipped (for y in range(0, size, 2): stepsize is 2).

Depending on the value of the current pixel a and the value of the same pixel in the next line (b), a character is printed.

So in the end, we get a string that represents a subset of all the pixels in a qrcode, and each character tells the value of two pixels.

BLOCK_FULL = chr(9608)
BLOCK_UPPER = chr(9600)
BLOCK_LOWER = chr(9604)
BLOCK_EMPTY = chr(160)


def atoms_token(size, atoms):
    text = atoms_to_text(size, atoms)
    return base64.b64encode(zlib.compress(text.encode('utf-8'))).decode('utf-8')


def atoms_to_text(size, atoms):
    buf = [False] * size ** 2
    for atom in atoms:
        x, y, is_set = atom
        buf[y * size + x] = is_set
    text = io.StringIO()
    for y in range(0, size, 2):
        for x in range(size):
            a = buf[y * size + x]
            b = buf[(y + 1) * size + x] if (y + 1) * size + x < len(buf) else False
            if a and b:
                text.write(BLOCK_FULL)
            elif a:
                text.write(BLOCK_UPPER)
            elif b:
                text.write(BLOCK_LOWER)
            else:
                text.write(BLOCK_EMPTY)
        text.write('\n')
    return text.getvalue().strip('\n')

Now we have a list of 17 of these strings. split_soul will select 16 of these. The main will print these.

TL;DR

The program generates a qrcode from a random string. The pixels of the qrcode are randomly selected, distributed into chunks and converted into 17 strings. From these 17 strings, only 16 are printed in the main. So some data is missing.

Our task is reconstructing the value of the qrcode 20 times in a row.

Reconstructing the qrcode

Let's start by connecting to the server. That's probably the easiest part 😜.

from pwn import remote


def main():
    conn = remote("flu.xxx", 10120)

    for _ in range(20):
        conn.recvuntil(b'Here are 16 shards:\n')
        shards = conn.recvuntil(b'Recover the soul to prove you are worthy')
        shardlines = shards.splitlines()

        restore_qr(shardlines[:-1])

        code = input("Enter code:")

        conn.sendline(code.encode())

    conn.interactive()

restore_qr accepts an array of bytes (shards).

But first we need to undo base64 and zlib compression for each line:

def decode_qr(qr):
    for q in qr:
        yield zlib.decompress(base64.b64decode(q)).decode()

We make a 2d array of booleans that represents the pixels of the qrcode.

We loop over the result. Each shard is now a text of 4 different characters, each line relates to two lines of the original qr code.

Depending on the character we find, we either set one or two pixels in the current and/or the next line.

def restore_qr(shards):
    cols = 32
    buf = [[False for _ in range(cols)] for _ in range(cols)]

    for shard in decode_qr(shards):
        # make 2d
        image = shard.splitlines()
        for y in range(len(image)):
            for x in range(len(image[0])):
                pixel = image[y][x]

                if pixel == BLOCK_FULL:
                    buf[y * 2][x] = True
                    buf[y * 2 + 1][x] = True

                elif pixel == BLOCK_UPPER:
                    buf[y * 2][x] = True

                elif pixel == BLOCK_LOWER:
                    buf[y * 2 + 1][x] = True

                elif pixel == BLOCK_EMPTY:
                    pass
                else:
                    print(f"Unknown value {ord(pixel)}")

    image = boolean_array_to_image(buf)
    with open("code.png", "wb") as f:
        image.save(f)

After putting all the pixels into the buffer, we make an image from it. (ChatGPT wrote that code. Nice!)

def boolean_array_to_image(array):
    width, height = len(array[0]), len(array)
    image = Image.new("1", (width, height))

    for y in range(height):
        for x in range(width):
            pixel_color = 0 if array[y][x] else 1
            image.putpixel((x, y), pixel_color)

    return image

Our goal was to simply scan it with a smartphone. Scanning 20 codes shouldn't be that big of a deal. But it turns out that the missing pixels were a problem for a our scanner app.

Try scanning it on your phone (Trust me bro, Kappa).

The resulting qr code with some features missing

For reference, I dumped the original qrcode from the script. You can clearly see some differences.

The original qrcode for reference

Of course, we did not have that for the challenge. So we had to find another way to make the scanner app scan it. We found that by accident.

We found this image on Wikipedia. It was drawn by Wtuvell. Thank you!

The interesting parts are the Red and Purple ones. These are used to identify the qrcode.

A great qrcode explanation

We tried fixing the code manually in Paint. We accidentally filmed the process with the scanner app and at some point it detected the code and read it.

Since that worked one time, we decided to repeat that 19 more times. Get the code, fix it by hand, scan it, send the resulting text to the server, repeat.

To quickly get the text from the phone to the PC, we paired it using KDE Connect and used the Clipboard Sharing-Feature.

ZeroFlagsInc

Soul Splitter | hack.lu 2023

Walk through the code

TL;DR

Reconstructing the qrcode

Walk through the code

TL;DR

Reconstructing the qrcode

links

social