xor xor

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char to_change[] = "SECURE?";

int main()
{
    setbuf(stdout, NULL);
    setbuf(stdin, NULL);
    setbuf(stderr, NULL);
    puts("do the xor!!!!!!!!");
    int index = 0;
    for (;;) {
        if (!strcmp(to_change, "HACKED!")) {
            puts("not bad");
            system("/bin/sh");
        }
        to_change[index] = to_change[index] ^ getchar();
        index = to_change[index] % 7;
    }
}

some notes to take:

for (;;) is an infinite loop
we gain a shell if the to_change string becomes "HACKED!"
there's an index variable, which determines what character of to_change we are changing
every iteration of the loop, the program asks for a character from the user with getchar, which is xored with the character at to_change[index] and to_change[index] is updated with the result of the xor.

some smaller easier observations to make:

we can choose exactly what we want to_change[index] will equal, by using our knowledge of xor
- xor is it's own inverse, meaning that a ^ a = 0
- anything xored with zero is itself, meaning that b ^ 0 = b
- as a result, if the character we provide is to_change[index] ^ a, we can say that...
  - to_change[index] = to_change[index] ^ getchar();
  - to_change[index] = to_change[index] ^ to_change[index] ^ a;
  - to_change[index] = 0 ^ a;
  - to_change[index] = a;
we can choose what we want index to be. Because the index is calculated as to_change[index] % 7, all we need to do is choose a value for to_change[index] that, when divided by seven, leaves a remainder that is the index we want.
- We can use the values \x00 to \x06, since those characters will leave an index of zero to six when divided by seven.
- This comes at a cost. We can choose an index, but this means that we lose control of what we are writing to to_change[index] and we will NEED to return to it at one point to change it back to what character it needs to be. Inversely, we can choose the value of what we are writing but we don't really get to choose what the index is.
  - For example, starting at index zero, if we'd like to go to index six, we can send the result of 'S' ^ '\x06', which will cause to_change[0] to be \x06, and as a result will cause index to be six. THOUGH, we will need the index to be zero again so we can return to and change to_change[0] to "H". Likewise, if we decided to send the result of 'S' ^ 'H', although we'd write the first letter of 'HACKED!', the index would become 'H' % 7, which is two.

the more important observation:

Because we need to have certain values at certain places in the array to spell out "HACKED!", we'll be going with the latter case where we choose the value but not the index. Because we control the value, we don't control the index. That's ok though, since we don't necessarly need the index to be a specific value each iteration; the only requirement is that we visit each index at least once.
- Those who do computer science outside of school might have recongized this as a graph traversal problem! We need to visit each index of to_change at least once, and the path between each element of to_change is outside our control.

Let's sketch out the path we take to visit each element of to_change, starting at zero.

We first set the first element to 'H', the first letter in 'HACKED!'. The new index is 2, as 'H' % 7 is 2.

At index two, we set the third element (remember that arrays are zero indexed) to 'C'. The new index is 4, since 'C' % 7 is 4.

Continue doing this, associating each letter of 'HACKED!' with the index it points to. I wrote a little snippet to print out the connections.

for i in "HACKED!":
  print(i +": " + str("HACKED!"[ord(i) % 7]))
# H: C
# A: C
# C: E
# K: D
# E: !
# D: D
# !: D

We can arrange this setup as a graph, where nodes are the characters of 'HACKED!' and the vertices between them are the index produced by it.

Well, there's an issue. We can traverse the graph entirely except for 'K' and 'A'. What do we do once we have set 'H', 'C', 'E', '!'? Well, in order to go to 'K' and 'A', we'll need to choose a value for where 'D' usually goes that'll take us to 'A' or 'K'. This means we'll need to return to where 'D' usually goes to change it to 'D' after we choose the index, but that's possible since we can just follow the verticies in the graph to go back to it.

So, our game plan will look a little something like this:

Woah, that's a lot of colors, but don't worry, we can take it step by step. The red path covers 'H', 'C', 'E', and '!'. From there, we follow the blue path and we set what should be 'D' to '\x01', so that we go to 'A'. From there, we set 'A', 'C' again, 'E' again, and '!' again. Lastly, we follow the green path and set 'K', which sets the index to take us right back to 'D'. From there, we gain a shell.

Let's use python to calculate what are input should be.

to_change = bytearray('SECURE?')
target = bytearray('HACKED!')

idx = 0

sent_characters = []


def send_character(c):
    global idx
    to_change[idx] ^= c
    idx = to_change[idx] % 7
    sent_characters.append(c)


# red path
# set to_change[0] to 'H'
send_character(target[idx] ^ to_change[idx])
# idx is recalculated, set to_change[2] to 'C'
send_character(target[idx] ^ to_change[idx])
# E
send_character(target[idx] ^ to_change[idx])
# !
send_character(target[idx] ^ to_change[idx])
# change to '\x01', so idx goes to A
send_character(1 ^ to_change[idx])

# blue path
# A
send_character(target[idx] ^ to_change[idx])

for _ in range(3):
    # we will go from C to E to !, we don't want to change them and since anything xored with 0 is itself we wont modify C E and !
    send_character(0)

# change to '\x03', so idx goes to K
send_character(3 ^ to_change[idx])
# K
send_character(target[idx] ^ to_change[idx])

# set D and finish!
send_character(target[idx] ^ to_change[idx])

# chr converts integers to characters, repr puts it into a format which humans can read raw bytes
print repr(''.join([chr(i) for i in sent_characters]))
# '\x1b\x00\x17\x1eD\x04\x00\x00\x00\x02\x1eG'

This'll print the series of bytes we need! We can use this series of bytes

pepsipu/xor_xor.md

xor xor