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

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int i; // [rsp+1Ch] [rbp-D4h]
  int j; // [rsp+1Ch] [rbp-D4h]
  int k; // [rsp+1Ch] [rbp-D4h]
  int l; // [rsp+1Ch] [rbp-D4h]
  int m; // [rsp+1Ch] [rbp-D4h]
  int n; // [rsp+1Ch] [rbp-D4h]
  int ii; // [rsp+1Ch] [rbp-D4h]
  int jj; // [rsp+1Ch] [rbp-D4h]
  int kk; // [rsp+1Ch] [rbp-D4h]
  int ll; // [rsp+1Ch] [rbp-D4h]
  int mm; // [rsp+1Ch] [rbp-D4h]
  int nn; // [rsp+1Ch] [rbp-D4h]
  int i1; // [rsp+1Ch] [rbp-D4h]
  int i2; // [rsp+1Ch] [rbp-D4h]
  int i3; // [rsp+1Ch] [rbp-D4h]
  int i4; // [rsp+1Ch] [rbp-D4h]
  int i5; // [rsp+1Ch] [rbp-D4h]
  int i6; // [rsp+1Ch] [rbp-D4h]
  int i7; // [rsp+1Ch] [rbp-D4h]
  int i8; // [rsp+1Ch] [rbp-D4h]
  int i9; // [rsp+1Ch] [rbp-D4h]
  int i10; // [rsp+1Ch] [rbp-D4h]
  int v26[40]; // [rsp+20h] [rbp-D0h] BYREF
  char flag_input[40]; // [rsp+C0h] [rbp-30h] BYREF
  unsigned __int64 v28; // [rsp+E8h] [rbp-8h]

  v28 = __readfsqword(0x28u);
  puts("Enter the flag:");
  fgets(flag_input, 40, _bss_start);
  for ( i = 0; i <= 38; ++i )
    flag_input[i] = (flag_input[i] + 59) ^ 0x38;
  flag_input[i] = 0;
  for ( j = 0; j <= 38; ++j )
    flag_input[j] = (flag_input[j] + 18) ^ 0xFD;
  flag_input[j] = 0;
  for ( k = 0; k <= 38; ++k )
    flag_input[k] = (flag_input[k] + 4) ^ 0x50;
  flag_input[k] = 0;
  for ( l = 0; l <= 38; ++l )
    flag_input[l] = (flag_input[l] + 19) ^ 0x68;
  flag_input[l] = 0;
  for ( m = 0; m <= 38; ++m )
    flag_input[m] = (flag_input[m] + 12) ^ 0x79;
  flag_input[m] = 0;
  for ( n = 0; n <= 38; ++n )
    flag_input[n] = (flag_input[n] - 68) ^ 0xA0;
  flag_input[n] = 0;
  for ( ii = 0; ii <= 38; ++ii )
    flag_input[ii] = (flag_input[ii] + 10) ^ 0xCD;
  flag_input[ii] = 0;
  for ( jj = 0; jj <= 38; ++jj )
    flag_input[jj] = (flag_input[jj] - 72) ^ 0x5A;
  flag_input[jj] = 0;
  for ( kk = 0; kk <= 38; ++kk )
    flag_input[kk] = (flag_input[kk] + 11) ^ 0xBD;
  flag_input[kk] = 0;
  for ( ll = 0; ll <= 38; ++ll )
    flag_input[ll] = (flag_input[ll] - 31) ^ 0xED;
  flag_input[ll] = 0;
  for ( mm = 0; mm <= 38; ++mm )
    flag_input[mm] = (flag_input[mm] + 69) ^ 0x22;
  flag_input[mm] = 0;
  for ( nn = 0; nn <= 38; ++nn )
    flag_input[nn] = (flag_input[nn] - 66) ^ 0x6B;
  flag_input[nn] = 0;
  for ( i1 = 0; i1 <= 38; ++i1 )
    flag_input[i1] = (flag_input[i1] - 38) ^ 0x6B;
  flag_input[i1] = 0;
  for ( i2 = 0; i2 <= 38; ++i2 )
    flag_input[i2] = (flag_input[i2] + 118) ^ 0xFA;
  flag_input[i2] = 0;
  for ( i3 = 0; i3 <= 38; ++i3 )
    flag_input[i3] = (flag_input[i3] + 22) ^ 0x6B;
  flag_input[i3] = 0;
  for ( i4 = 0; i4 <= 38; ++i4 )
    flag_input[i4] = (flag_input[i4] - 75) ^ 0x6B;
  flag_input[i4] = 0;
  for ( i5 = 0; i5 <= 38; ++i5 )
    flag_input[i5] = (flag_input[i5] - 115) ^ 0x64;
  flag_input[i5] = 0;
  for ( i6 = 0; i6 <= 38; ++i6 )
    flag_input[i6] = (flag_input[i6] + 10) ^ 0xAB;
  flag_input[i6] = 0;
  for ( i7 = 0; i7 <= 38; ++i7 )
    flag_input[i7] = (flag_input[i7] + 99) ^ 0x1B;
  flag_input[i7] = 0;
  for ( i8 = 0; i8 <= 38; ++i8 )
    flag_input[i8] = (flag_input[i8] - 43) ^ 0xF0;
  flag_input[i8] = 0;
  for ( i9 = 0; i9 <= 38; ++i9 )
    flag_input[i9] = (flag_input[i9] + 117) ^ 0x6B;
  flag_input[i9] = 0;
  memset(v26, 0, sizeof(v26));
  v26[0] = 77;
  v26[1] = 185;
  v26[2] = 77;
  v26[3] = 11;
  v26[4] = 212;
  v26[5] = 102;
  v26[6] = 227;
  v26[7] = 41;
  v26[8] = 184;
  v26[9] = 77;
  v26[10] = 223;
  v26[11] = 102;
  v26[12] = 184;
  v26[13] = 77;
  v26[14] = 14;
  v26[15] = 196;
  v26[16] = 223;
  v26[17] = 212;
  v26[18] = 20;
  v26[19] = 59;
  v26[20] = 223;
  v26[21] = 102;
  v26[22] = 44;
  v26[23] = 20;
  v26[24] = 71;
  v26[25] = 223;
  v26[26] = 183;
  v26[27] = 184;
  v26[28] = 183;
  v26[29] = 223;
  v26[30] = 71;
  v26[31] = 77;
  v26[32] = 164;
  v26[33] = 223;
  v26[34] = 50;
  v26[35] = 184;
  v26[36] = 234;
  v26[37] = 245;
  v26[38] = 146;
  for ( i10 = 0; i10 <= 38; ++i10 )
  {
    if ( (unsigned __int8)flag_input[i10] != v26[i10] )
    {
      printf("WRONG!");
      return 0;
    }
  }
  printf("GOOD JOB!");
  return 0;
}

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.

1. 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).

2. 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.

reversed_objs = [Decryptor(117, 0x6B), Decryptor(-43, 0xF0), Decryptor(99, 0x1B), 
        Decryptor(10, 0xAB), Decryptor(-115, 0x64), Decryptor(-75, 0x6B),
        Decryptor(22, 0x6B), Decryptor(118, 0xFA), Decryptor(-38, 0x6B),
        Decryptor(-66, 0x6B), Decryptor(69, 0x22), Decryptor(-31, 0xED),
        Decryptor(11, 0xBD), Decryptor(-72, 0x5A), Decryptor(10, 0xCD),
        Decryptor(-68, 0xA0), Decryptor(12, 0x79), Decryptor(19, 0x68),
        Decryptor(4, 0x50), Decryptor(18, 0xFD), Decryptor(59, 0x38)]

forward_objs = reversed_objs[::-1]

def forward_pass(in_char: str) -> int:
    char_code = ord(in_char)
    for enc_obj in forward_objs:
        char_code = enc_obj.xor_char(char_code)
    return char_code

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?

Code's literally the same bruh

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

Assembly equivalent

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 ints to the Python int type requires additional logic. With a bit of extension of the Decryptor object, we have the following:

class Decryptor:
    def __init__(self, offset: int, xor_key: int) -> None:
        self._offset = offset
        self._xor_key = xor_key
        self._iter_max = 38


    def xor_char(self, in_char: int) -> int:
        if self._offset >= 0:
            in_char = (in_char + self._offset) ^ self._xor_key
        else:
            in_char = self.subtract(in_char, self._offset) ^ self._xor_key
        in_char = in_char % 0x100 # modulo to keep result within <= 255
        return in_char
        

    def subtract(self, param_1: int, param_2: int) -> int:
        result = param_1 + param_2
        out = 256 + result

        return out

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.

ENC_FLAG = [77, 185, 77, 11, 212, 102, 227, 41, 184, 77, 223, 102, 184, 77, 14, 196, 223, 212, 20, 59, 223, 102, 44, 20, 71, 223, 183, 184, 183, 223, 71, 77, 164, 223, 50, 184, 234, 245, 146]
   
    out_flag = []

    print(len(ENC_FLAG))
    for target_char in ENC_FLAG:
        for printable_char in printable:
            if forward_pass(printable_char) == target_char:
                out_flag.append(printable_char)
                continue

    print(''.join(out_flag))