heterograms

Are you repeating yourself?

5 min read

[ + ]Overview

After grabbing a copy of the ELF binary and giving it a go, we are prompted with a simple Send me some data to get the flag!, and when the incorrect text is sent, we see Na, I don't like that.

[ + ]Reversing

To start the challenge, you loop through process until a non-1 value is returned, then the flag is printed.

To begin, some input is read (128 bytes) which is then evaluated against some initial conditions:

1. The first value of the input must be equal to the length of the input
2. There must be at least 3 bytes
3. The checksum applied must be valid such that the second byte is equal to 255 - sum(string[2:])

Once completed, the input is read as follows - starting with the third byte, the following rules are applied:

1. if byte b == 0 , continue to byte at position index of b + 2 and set the globalstate to value at index of b + 1
2. if byte b == 1, find the byte at index b + 1 (def: b2), then the byte at index of b2 + (b + 1) (def: b3), and iterate b2 times setting the global arr[b3] = 1
3. if byte b == 2, continue to byte at position index of b + 2 and set the global arr to be cleared.

To end the while loop, we note the fact that 128 (BUFFSIZE) is read. So, the input string must be of length 127 and padded with \x00.

This is important when considering the solution as a whole.

After the while loop terminates, the sub-routine handle is called where some checks happen.

The first check is for globalstate which is incremented with each valid input, starting at 0 (see further bellow).

The second is if the global arr is set to be cleared.

Finally, if the globalstate is set and valid, and the global arr is not set to be cleared, run check.

Finally, we reach the final check sub-routine that returns 1. The first for-loop checks if all values of global arr[string - 97] is set to 1. If so, check the number of values set to 1 and ensure it is equal to the length of the string (this condition prevents you from setting each and every value of global arr to 1).

If both are satisfied, and the global state is 7, then we have solved the challenge.

You may be thinking, what are these magical strings? After some searching in the data, here they are:

So in short, we need to satisfy all of the conditions listed above, 7 times, for the following words:

• unforgivable
• troublemakings
• computerizably
• hydromagnetics
• flamethrowing
• copyrightable
• undiscoverably

[ + ]Solution

Here is the main piece of the solver script that satisfies the conditions found while reversing:

def generate_payload(word, index):
    payload = b"".join([b"\x01\x01" + struct.pack("B", ord(x) - 97) for x in word])
    if len(payload) % 2 != 0:
        payload += b"\x01\x01\x00"
    padding = b"\x00" * (124 - len(payload))
    cleaning =  b"\x00"  + struct.pack("B", index)
    pos_1 = struct.pack("B", 127)
    pos_2 = struct.pack("B", 255 - sum(payload) - sum(padding) - sum(cleaning))
    res = b''.join([pos_1, pos_2, payload, padding, cleaning])

    padding = b"\x00" * (122 - len(payload))
    cleaning =  b"\x00"  + struct.pack("B", index + 1) + b"\x02\x02"
    pos_1 = struct.pack("B", 127)
    pos_2 = struct.pack("B", 255 - sum(payload) - sum(padding) - sum(cleaning))
    
    res += b''.join([pos_1, pos_2, payload, padding, cleaning])
    return res

Let's go through this line by line.

payload = b"".join([b"\x01\x01" + struct.pack("B", ord(x) - 97) for x in word])

Here we are satisfying the condition 2 from the reversing section. The first byte is 1 which means that the binary will looks at the second byte, and set the index in the global arr[x-97]=1 , where x is the integer representation of a character in a given word.

if len(payload) % 2 != 0:
    payload += b"\x01\x01\x00"

Here we are padding the payload with \x01\x01\x00 . Why are we setting the 0th index to 1? If you look closely at the hex dump of the words, you will see that all words are padded with a 00 byte if they are not of even length.

padding = b"\x00" * (124 - len(payload))

Here we are just padding the payload with 0s. Doesn't this set the global state to 0? Yes, but it's okay. We handle this bellow. We are simply doing this to fill the data that is being read.

cleaning =  b"\x00"  + struct.pack("B", index)
pos_1 = struct.pack("B", 127)
pos_2 = struct.pack("B", 255 - sum(payload) - sum(padding) - sum(cleaning))
res = b''.join([pos_1, pos_2, payload, padding, cleaning])

Here we are setting the global state to the index of the word that is passed to the function, then calculating the first two bytes to satisfy the initial conditions. Remember, b0 must be equal to the length of the string, and b1 must be equal to 255 - sum(b2 -> bn) . Once we have that ready, we can join everything into the res.

padding = b"\x00" * (122 - len(payload))
cleaning =  b"\x00"  + struct.pack("B", index + 1) + b"\x02\x02"
pos_1 = struct.pack("B", 127)
pos_2 = struct.pack("B", 255 - sum(payload) - sum(padding) - sum(cleaning))
res += b''.join([pos_1, pos_2, payload, padding, cleaning])

But we're not done, we need a way to clear the global arr after satisfying each word. As a result, we append a secondary payload which is filled with \x00 , but sets the global state to index + 1, then clears the global arr with \x02\x02. Why? This is to satisfy the global state check before erase is called.

Then we do the same as before, satisfying the initial checks.

Put it all together! Now we can generate the sequence of bytes required for each word!

from pwn import *
from pwnlib.util.packing import *
import struct
# Context
context.arch = 'amd64'
context.log_level = 'DEBUG'


# Main vars
NETID = ''
HOST, PORT = 'host', 7331


def generate_payload(word, index):
    payload = b"".join([b"\x01\x01" + struct.pack("B", ord(x) - 97) for x in word])
    if len(payload) % 2 != 0:
        payload += b"\x01\x01\x00"
    padding = b"\x00" * (124 - len(payload))
    cleaning =  b"\x00"  + struct.pack("B", index)
    pos_1 = struct.pack("B", 127)
    pos_2 = struct.pack("B", 255 - sum(payload) - sum(padding) - sum(cleaning))
    res = b''.join([pos_1, pos_2, payload, padding, cleaning])

    padding = b"\x00" * (122 - len(payload))
    cleaning =  b"\x00"  + struct.pack("B", index + 1) + b"\x02\x02"
    pos_1 = struct.pack("B", 127)
    pos_2 = struct.pack("B", 255 - sum(payload) - sum(padding) - sum(cleaning))
    res += b''.join([pos_1, pos_2, payload, padding, cleaning])

    return res

def pwn():
    conn = remote(HOST, PORT)
    conn.recvuntil(b'(something like abc123): ')
    conn.sendline(NETID)
    conn.recvuntil(b'Send me some data to get the flag!\n')

    words = ["unforgivable", "troublemakings", "computerizably", "hydromagnetics", "flamethrowing", "copyrightable",
             "undiscoverably"]
    solution = []
    for i, w in enumerate(words):
        solution.append(generate_payload(w, i))
    conn.send(b"".join(solution))
    conn.recvuntil(b'flag{')
    response = conn.recvline()
    conn.close()
    print("flag{" + response.decode().strip())


if __name__ == "__main__":
    pwn()