---
description: Reversing a simple encryption algorithm
---

# hvhpgs{synt}

## Description

CS1 ciphers go brrrrr

&#x20;**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:

```c
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.

![ROT function: notice the second argument](https://3651895838-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M_EXjpFlA1auR365Es4%2F-MgJjHAKF_7sb1rXzhDv%2F-MgJp1K4If4B9kFZAGTj%2Fimage.png?alt=media\&token=40c9171c-c368-4504-89e0-7901a21539a2)

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:

{% tabs %}
{% tab title="Python Implementation" %}
```python
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
```
{% endtab %}

{% tab title="Decompiled C" %}
```c
int *generate()
{
  int counter; // [rsp+0h] [rbp-10h]
  int v2; // [rsp+4h] [rbp-Ch]
  int v3; // [rsp+8h] [rbp-8h]
  int i; // [rsp+Ch] [rbp-4h]

  counter = 1;
  list_2495[0] = 2;
  v2 = 3;
  while ( counter <= 1337 )
  {
    v3 = 1;
    for ( i = 0; i < counter; ++i )
    {
      if ( !(v2 % list_2495[i]) )
        v3 = 0;
    }
    if ( v3 )
      list_2495[counter++] = v2;
    v2 += 2;
  }
  return list_2495;
}
```
{% endtab %}
{% endtabs %}

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

Similarly, `rot()` implemented:

{% tabs %}
{% tab title="Python Implementation" %}
```python
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])
```
{% endtab %}

{% tab title="Decompiled C" %}
```c
__int64 __fastcall rot(const char *in_str, int a2)
{
  __int64 result; // rax
  char v3; // [rsp+17h] [rbp-9h]
  unsigned int i; // [rsp+18h] [rbp-8h]
  int str_len; // [rsp+1Ch] [rbp-4h]

  str_len = strlen(in_str);
  for ( i = 0; ; ++i )
  {
    result = i;
    if ( (int)i >= str_len )
      break;
    v3 = in_str[i];
    if ( v3 != 95 )
      v3 = (v3 - 97 + a2) % 26 + 97;
    in_str[i] = v3;
  }
  return result;
}
```
{% endtab %}
{% endtabs %}

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.

{% tabs %}
{% tab title="Python Implementation" %}
```python
def shift(in_str: str, offset: int) -> str:
    return in_str[offset:] + in_str[:offset]
```
{% endtab %}

{% tab title="Decompiled C" %}
```c
unsigned __int64 __fastcall shift(char *a1, int a2)
{
  unsigned __int64 v2; // rax
  void *v3; // rsp
  char v5[4]; // [rsp+8h] [rbp-60h] BYREF
  int v6; // [rsp+Ch] [rbp-5Ch]
  char *s; // [rsp+10h] [rbp-58h]
  int i; // [rsp+18h] [rbp-50h]
  int v9; // [rsp+1Ch] [rbp-4Ch]
  __int64 v10; // [rsp+20h] [rbp-48h]
  char *dest; // [rsp+28h] [rbp-40h]
  unsigned __int64 v12; // [rsp+30h] [rbp-38h]

  s = a1;
  v6 = a2;
  v12 = __readfsqword(0x28u);
  v9 = strlen(a1);
  v10 = v9 - 1LL;
  v2 = 16 * ((v9 + 15LL) / 0x10uLL);
  while ( v5 != &v5[-(v2 & 0xFFFFFFFFFFFFF000LL)] )
    ;
  v3 = alloca(v2 & 0xFFF);
  if ( (v2 & 0xFFF) != 0 )
    *(_QWORD *)&v5[(v2 & 0xFFF) - 8] = *(_QWORD *)&v5[(v2 & 0xFFF) - 8];
  dest = v5;
  strcpy(v5, s);
  for ( i = 0; i < v9; ++i )
    s[i] = dest[(i + v6) % v9];
  return __readfsqword(0x28u) ^ v12;
}
```
{% endtab %}
{% endtabs %}

### Sweet Success

We combine our reversed functions, to yield the flag

```python
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)
```

