# Tedious

Reversing a XOR cipher

## Description

Enter the flag and the program will tell you if it is correct!

**author**: Chief

## Opinions

Good challenge! Simple to reverse, but tripped me up with bit manipulations. Overall, pretty fun!

## Solution

### A Once-Over

Here's the decompiled source of the binary

The important components of the binary are all here - missing is a series of XOR operations similar to the one in lines 92 to 93 above. From our initial once-over, we can determine that:

The flag is subjected to a series of XOR encryptions,

Once again, it is compared to a hardcoded array at the end, checking the flag's correctness

So! We know that the flag is 39 characters from the length of the final array, and that it is subjected to a series of very similar operations to get there. Let's get scripting!

### A Deeper Dive

Typically for flag-checker challenges such as these, there are two methods one can take when solving these, depending on the difficulty of the algorithm.

Reversing the encryption algorithm if simple enough, and running the algorithm in reverse to yield the final flag. This is often done if the encryption algorithm is symmetrical (small brain moment later).

Treating the encryption as a black box, and passing in alphanumeric characters to observe what output you get, building a map and simply looking up the flag.

Note: these methods only work for encryption systems where each character is encrypted independent of other characters. This challenge meets those requirements, others may not.

### A Program to Pwn

Initially, I didn't expect that this challenge would be too hard to solve. In the spirit of fun, I decided to implement each separate XOR function as an object on its own, passing the array through the objects in consecutive fashion to obtain the encrypted flag! I thought this whole process seemed rather similar to the forward pass when training a machine learning model, hence the function names.

So, at this point, I've initialized the objects with the corresponding values, namely offset and XOR key, and I have a function to perform a forward pass on any ASCII printable character I pass it. Together, these functions should allow me to replicate the encryption algorithm and black-box it, passing in any character I want to obtain the corresponding encrypted character and yield the flag.

### A Dire Difficulty

At this point, I implement what I think is correct logic, pass my program through it and huh? I get code points vastly out of ASCII English, so something must be wrong. What exactly is going on?

To get the answer to that, we're gonna need to trawl through some assembly instructions.

The answer lies in the XOR argument here, and in the implementation of binary subtraction in modern processors.

At the basest level, processors implement everything in binary - that ranges from assembly instructions such as those you see above, to memory and storage. It's no surprise then that values such as our `flag_input`

character are stored in binary as well.

So what happens when you subtract a bigger number from a smaller one? Mathematics would tell you that you'd get a negative number, but processors have no way of implementing that. The answer put very simply is signed integers. The first bit of a signed integer represents the sign, with the rest containing the actual number.

The downside of this is converting the resulting signed integer from C `signed int`

s to the Python `int`

type requires additional logic. With a bit of extension of the `Decryptor`

object, we have the following:

Note the modulo op in `xor_char()`

, and the `subtract()`

function that isn't actually subtracting. Disclaimer: my bit manipulations are less than stellar, but this is code I've found that works for 8-bit integers. Implementing 2's complement was a bit too much this time.

### A Flag, Finally

Combining the `Decryptor`

objects with the encrypted flag hardcoded in memory, we have a script to obtain the flag via bruteforce - passing every printable character through the encryption algorithm and comparing it with the target character.

For more complex functions, optimizations such as caching character maps, or further reducing the algorithm to a one-liner since repeated XORs can be represented using just 1 XOR operation with a key could have been done. However, for the purposes of solving this challenge, this is all we need.

Last updated