hvhpgs{synt}

Reversing a simple encryption algorithm

Description

CS1 ciphers go brrrrr

author: spamakin

Opinions

An awesome beginner-friendly challenge and a great way to welcome those new to reversing. Among all the BabyREs in CTFs I've solved, this one was by far the most approachable without being ridiculously simple to solve. Kudos to the creators!

Solution

Kowalski, Analysis!

As always, the first step is to identify what kind of file we're working with. This is easily done using the file utility that comes pre-installed in all Linux distributions. As I'm lazy and don't want to spin up a Linux VM just to identify what is probably an executable binary, I open it in a hex editor and see the ELF file signature. Great, so it's a Linux compiled binary!

Now we know what we're dealing with, it's time to begin analysis. I fire up IDA Pro and decompile the binary. Here's what we see:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  size_t input_length; // rax
  unsigned __int64 const_1; // rax
  void *mem_ptr; // rsp
  int str_ptr; // [rsp+8h] [rbp-480h] BYREF
  int i; // [rsp+Ch] [rbp-47Ch]
  int *offsets_arr; // [rsp+10h] [rbp-478h]
  size_t unused_1; // [rsp+18h] [rbp-470h]
  char *dest; // [rsp+20h] [rbp-468h]
  char s[64]; // [rsp+28h] [rbp-460h] BYREF
  char user_input[1000]; // [rsp+68h] [rbp-420h] BYREF
  unsigned __int64 v14; // [rsp+450h] [rbp-38h]

  v14 = __readfsqword(0x28u);
  offsets_arr = generate();
  str_ptr = 0;
  while ( !str_ptr )
  {
    puts("enter input with the form: flag_words_with_underscores_and_letters");
    __isoc99_scanf("%s", user_input);
    input_length = strlen(user_input);
    unused_1 = input_length - 1;
    const_1 = 16 * ((input_length + 15) / 0x10);
    while ( &str_ptr != (int *)((char *)&str_ptr - (const_1 & 0xFFFFFFFFFFFFF000LL)) )
      ;
    mem_ptr = alloca(const_1 & 0xFFF);
    if ( (const_1 & 0xFFF) != 0 )
      *(_QWORD *)((char *)&str_ptr + (const_1 & 0xFFF) - 8) = *(_QWORD *)((char *)&str_ptr + (const_1 & 0xFFF) - 8);
    dest = (char *)&str_ptr;
    strcpy((char *)&str_ptr, user_input);
    for ( i = 0; i <= 1336; ++i )
    {
      rot(dest, offsets_arr[i]);
      shift(dest, offsets_arr[i]);
    }
    if ( !strcmp(dest, "azeupqd_ftq_cgqefuaz_omz_ymotuzqe_ftuzwu_bdabaeq_fa_o") )
    {
      str_ptr = 1;
    }
    else if ( !strcmp(dest, "qe_mzp_xqffqderxms_iadpe_iuft_gzpqdeoad") )
    {
      puts("very funny");
    }
    else
    {
      puts("incorrect");
    }
  }
  qmemcpy(s, "uiuctf{", 7);
  for ( i = 0; i <= 52; ++i )
    s[i + 7] = user_input[i];
  s[60] = 125;
  puts(s);
  return 0;
}

Our initial look at the binary's function is arguably one of the most important steps - identifying what goes where and does what will contribute majorly especially when we get into the nitty gritty details of how exactly this binary runs. From a brief glance, I see:

  • An array, v9, being returned by the generate() call later passed as an argument to both rot() and shift(),

  • A strcmp() call to what appears to be an encrypted flag, and

  • A series of memory operations that IDA doesn't quite recognize, but yield a pointer to the user input read in line 21 by scanf()

Into The Thick Of It

I have a sneaking suspicion that the values read from v9 will turn out to be offsets, given as to how the ROT and shifting operations require an offset. Opening up either the rot() or shift() functions in the decompiler confirms that suspicion.

At this point, we can conclude a few things, simply based on the decompiled code that IDA has presented us with.

  • A flag is read into memory,

  • It is randomly shifted and subjected to ROT operations by the for loop, 1337 times, and

  • The final result is compared to the hardcoded encrypted flag in memory.

We now have enough information to begin reversing.

Breaking It Down

The generate() function and the rot() function are simple enough that they can be translated from decompiled C into Python with no issues. With reference to the decompiled generate() code, we can replicate it in Python as follows:

def generate() -> list:
    out = [0] * 1338
    counter = 1
    out[0] = 2

    temp_1 = 3 # v2
    while counter <= 1337:
        temp_2 = 1 # v3
        for i in range(counter):
            if not (temp_1 % out[i]):
                temp_2 = 0
        if temp_2:
            out[counter] = temp_1
            counter += 1
        temp_1 += 2
    
    return out

This yields us the array which is later referred to by both encryption functions to provide offsets.

Similarly, rot() implemented:

def rot(in_str: str, offset: int) -> str:
    out = []
    for char in in_str:
        char_ptr = ord(char)
        if char_ptr != 95:
            out.append((char_ptr - 97 + offset) % 26 + 97)
        else:
            out.append(95)
    return ''.join([chr(char) for char in out])

Now, the shift() function appears a bit unapproachable. This makes sense as C-strings are immutable objects in memory, so modifying them in-place is out of the question. The binary has to allocate memory to store another instance of the same string, ensure that the stored string does not exceed allocated memory, et cetera. This is before the shifting can even be implemented!

Note the similarities between lines 17 to 26 of the shift function here and lines 22 to 31 of the main driver code above - they are almost identical! The code is demonstrating memory management here - it iterates through every character in the string to be copied, ensuring that the character does not take up more bytes than it has been allocated until it reaches the null terminator at the end of the string. After this check is completed, a strcpy() call can be seen moving the string to its new home.

Interpreted languages abstract away the need for such memory management - our Python solution is a one-liner.

def shift(in_str: str, offset: int) -> str:
    return in_str[offset:] + in_str[:offset]

Sweet Success

We combine our reversed functions, to yield the flag

enc_flag = "azeupqd_ftq_cgqefuaz_omz_ymotuzqe_ftuzwu_bdabaeq_fa_o"
    offsets = generate()

    for i in range(1337):
        enc_flag = shift(rot(enc_flag, -offsets[i]), -offsets[i])
    
    print(enc_flag)

PreviousTediousNextSEETF

Last updated