Challenge #1: yourock

Category: rev

Author: jazz

Challenge prompt:

Forget Enigma, forget Caesar. The only cipher you need is 2009's infamous password dump.

Challenge handout has two files inside, one of them is a target ELF named encode and the other one is an encrypted file named encoded.rj. Before we begin decompilation let's see what happens when we run the program:

Usage: ./encode "your message"

So the program expects a string, let's try a random string for now:

Failed to open ./rockyou.txt

So the program needs rockyou.txt to be in the same directory, I'm guessing it uses it to encode the input string. This is also explains what the challenge prompt is referring to "The only cipher you need is 2009's infamous password dump."

So after placing rockyou.txt in the same directory, we pass in a string "random":

cosmos@cosmos-VirtualBox:~/workspace/corctf/yourock$ ./encode random
Encoded output:
hellokitty 00000 qwerty lovely 12345678 12345678 1234567

If we compare this with our encoded.rj file, we can see that both of them have a similar format, where the encoded output has words separated by a space. I think it is safe to assume that the encoded.rj file is encoded output of the flag when it was ran against the given program.

Another interesting thing to notice is that the number of words in the encoded output is always 1 more than the length of the input string, this suggests that the encode program could be doing some kind of byte-by-byte operation on the input string outputting an extra word with it.

DECOMPILATION

Let's look at the program decompilation in IDA:

std::allocator<char>::allocator(&wordlist_map, argv, a3);
std::string::basic_string<std::allocator<char>>(&input, argv[1], &wordlist_map);
std::allocator<char>::~allocator(&wordlist_map);
std::vector<std::string>::vector(&wordlist_lines);
std::unordered_map<std::string,unsigned long>::unordered_map(&wordlist_map);
if ( (unsigned __int8)load_file(&wordlist_lines, &wordlist_map) != 1 )

Looking at this we can safely say that this is a C++ binary and at first it can be hard to read, but let's try to dig in and see what the binary is trying to do.

So the binary allocates an empty string vector named wordlist_lines and an unordered map named wordlist_map. If you don't know what an unordered map is, you can think of it as a python dictionary which holds values in key-value pairs as they are both implementations of hash maps.

Encoding

Upon successfully opening rockyou.txt it generates a key using generate_key and encodes the given string using encode function which takes 4 args.:

- encoded_words (empty vector for now)

- input (input string)

- wordlist_lines (vector containing all passwords from rockyou.txt)

- key (generated from generate_key)

And after execution of this function the binary prints out the encoded_words buffer separated by a space.

Let's look inside the encode function first:

  std::vector<std::string>::vector(encoded_words);
  word = std::vector<std::string>::operator[](wordlist_lines, key);
  std::vector<std::string>::push_back(encoded_words, word);
  for ( i = 0LL; i < std::string::size(input); ++i )
  {
    xored_byte = key ^ *(_BYTE *)std::string::operator[](input, i);
    if ( xored_byte >= (unsigned __int64)std::vector<std::string>::size(wordlist_lines) )
      exit(1);
    new_line = std::vector<std::string>::operator[](wordlist_lines, xored_byte);
    std::vector<std::string>::push_back(encoded_words, new_line);
    key ^= i ^ xored_byte;
  }
  return encoded_words;

so the encode function boils down to this:

- It takes the key and uses it as an index in the wordlist_lines array, grabs the word from that index and puts that word into the encoded_words array. (This is the reason why we always have an extra word in the encoded output)

- After that it kicks off a loop based on the size of the input string, and XOR's every byte of the input string with the key.

- Then it uses the XOR'ed value as an index into the wordlist array and puts that word into the encoded words array.

- Then it updates the key by XOR'ing it with the index and the xored_byte variable

Updating the key is a simple XOR operation which can be reversed if we know the index i and the xored_byte, we already know i but the xored_byte depends on the initial key. So all we need to break this encoding is the initial key, let's see how that is being generated.

Key generation

Key generation is pretty simple, we take a time-based seed and feed it to srand and then generate a random number from it. But we compute the modulus of it with 256 means that the returned value will be within the range [0, 255]

__int64 __fastcall generate_key(__int64 *a1)
{
  unsigned int v1; // eax

  v1 = time(a1);
  srand(v1);
  return (unsigned int)(rand() % 256);
}

Since our key is used as an index in the wordlist array, it means that our initial word will always be within the first 255 words of rockyou.txt. So basically given an encoded output we just need to find the index of the first encoded word and that will be our key.

Looking at encoded.rj the first word is charlie, let's look for its index in rockyou.txt

head -n255 rockyou.txt | cat -n | grep charlie

the output comes out to be 64 charlie, but since this is 1-indexed we can set our key as 63.

Solution

Now that we know our initial key we can reverse the XOR operation and get the actual string back, While encoding the input string we did:

xored_byte = input[i] ^ key

so to reverse this we just need to do:

input[i] = xored_byte ^ key

This is the final solve script:

with open("encoded.rj") as fp:
    encoded = fp.read().strip()

encoded_words = encoded.split(" ")
print(encoded_words)

flag = ""

with open("rockyou.txt", encoding='utf-8', errors="ignore") as fp:
    pwds = [line.strip() for line in fp]

key = pwds.index(encoded_words[0])
encoded_words = encoded_words[1:]

for i in range(len(encoded_words)):
    xored_byte = pwds.index(encoded_words[i])
    flag += chr(key^xored_byte)
    key ^= i^xored_byte

print(flag)

And we get the flag: corctf{r0cky0u_3nc0d1ng_r0cks} 🎉

Challenge #2: tagme

Category: rev

Author: maxster

We are greeted with a dynamically linked, stripped binary. Classic crackme style challenge which takes in a input string and validates it, our input is also our flag.

Looking at the binary in IDA the binary isn't completely stripped, libc functions are there, but we still need to make sense of some functions and rename them:

void __fastcall __noreturn main(int a1, char **a2, char **a3)
{
  char v3; // [rsp+3h] [rbp-3Dh]
  char *lineptr; // [rsp+8h] [rbp-38h] BYREF
  size_t n; // [rsp+10h] [rbp-30h] BYREF
  unsigned __int64 i; // [rsp+18h] [rbp-28h]
  __ssize_t v7; // [rsp+20h] [rbp-20h]
  char *v8; // [rsp+28h] [rbp-18h]
  unsigned __int64 v9; // [rsp+30h] [rbp-10h]
  unsigned __int64 v10; // [rsp+38h] [rbp-8h]

  v10 = __readfsqword(0x28u);
  puts("Enter flag:");
  lineptr = 0LL;
  n = 0LL;
  v7 = getline(&lineptr, &n, stdin);
  if ( v7 == -1 )
    sub_1209("Illiterate");
  if ( v7 <= 8 )
    sub_1209("Short");
  if ( v7 > 39 )
    sub_1209("Long");
  if ( strncmp("corctf{", lineptr, 7uLL) )
    sub_1209("Ineligible");
  if ( strncmp("}\n", &lineptr[v7 - 2], 2uLL) )
    sub_1209("Ineligible");
  sub_126D();
  v8 = lineptr + 7;
  v9 = v7 - 9;
  for ( i = 0LL; i < v9; ++i )
  {
    v3 = v8[i];
    if ( (i & 1) != 0 )
    {
      if ( i % 6 > 3 )
      {
        if ( v3 <= 112 )
          sub_1209("Forbidden");
      }
      else if ( v3 <= 107 || v3 == 115 )
      {
        sub_1209("Forbidden");
      }
    }
    else if ( v3 == 99 || v3 > 108 )
    {
      sub_1209("Forbidden");
    }
    sub_12A4((unsigned int)v3);
  }
  while ( !(unsigned int)sub_13F8() )
    ;
  sub_1209("Boring");
}

We take input from stdin using getline, which returns the number of chars taken input. This means that v7 has the flag_length and lineptr is basically a pointer to the input string.

v8 is flag_ptr + 7, since flag format starts with corctf{, v8 basically points to the first character inside the brackets aka the flag_bytes. v9 is v7 - 9 and since v7 was our flag_length, v9 is the length of our flag_bytes which is the string inside the brackets.

By the looks of it sub_1209() looks like some kind of fail condition function, since it prints Rejected and exits the program.

void __fastcall __noreturn sub_1209(const char *a1)
{
  printf("%s\nRejected\n", a1);
  exit(1);
}

We'll rename sub_1209 to fail for now. We can also rename v8 and v9 to flag_chars and flag_len based on what we discussed above.

Looking at the for loop, we loop until the end of the input string and store the current byte in v3. We can rename v3 as flag_byte. Now if we look inside the for loop it is laid out with traps which instantly trigger the fail condition, if we manage to avoid these we get to a function named sub_12A4

Now let's look at this other function sub_12A4:

__int64 __fastcall sub_12A4(char a1)
{
  __int64 result; // rax

  byte_4060[qword_4048] = a1;
  if ( ++qword_4048 == 4600 )
    qword_4048 = 0LL;
  result = qword_4040;
  if ( qword_4048 == qword_4040 )
    sub_123B("Interesting");
  return result;
}

If we manage to avoid the traps, we pass the flag_byte as input to this function which writes it to a global buffer byte_4060. The index is decided by another value stored in the .bss qword_4048. This global buffer is interesting because it writes upto size 4600 and then loops back around to the start of the buffer by setting the index pointer to 0.

This means that byte_4060 is some kind of circular buffer with length 4600. We also take another pointer qword_4040 and compare it with our index pointer. If these two pointers match then we take this other function sub_123B and if we look inside it we can see that it prints Accepted and exits. This clearly means that this is our success case and we have to somehow reach here to get the flag!

So based on all of this we can re-define:

- byte_4060 to circular_buffer

- qword_4048 to write_ptr

- qword_4040 to read_ptr

- sub_123B to success

There's another interesting function in a while loop at the end, let's uncover that:

__int64 sub_13F8()
{
  size_t j; // rax
  char v2; // [rsp+Ah] [rbp-26h]
  char v3; // [rsp+Bh] [rbp-25h]
  int i; // [rsp+Ch] [rbp-24h]
  size_t v5; // [rsp+10h] [rbp-20h]
  __int64 v6; // [rsp+18h] [rbp-18h]
  char *s; // [rsp+28h] [rbp-8h]

  if ( (unsigned int)sub_138A() )
    return 1LL;
  v2 = sub_1318();
  v6 = sub_13AB((unsigned int)v2);
  if ( v6 == -1 )
    fail("Bizzare");
  for ( i = 1; i <= 1; ++i )
  {
    if ( (unsigned int)sub_138A() )
      return 1LL;
    v3 = sub_1318();
    if ( sub_13AB((unsigned int)v3) == -1 )
      fail("Bizzarre");
  }
  s = (char *)*((_QWORD *)&unk_3CE0 + 2 * v6 + 1);
  v5 = 0LL;
  for ( j = strlen(s); v5 < j; j = strlen(s) )
    sub_12A4(s[v5++]);
  return 0LL;
}

If we look at sub_1318, we check if our write_ptr is the same as qword_4040. If not we use the qword_4040 to read values from the circular_buffer and return it. From this we can rename qword_4040 to be our read_ptr

__int64 sub_1318()
{
  unsigned __int8 v1; // [rsp+Fh] [rbp-1h]

  if ( qword_4040 == write_ptr )
    fail("Dry");
  v1 = circular_buffer[qword_4040];
  if ( ++qword_4040 == 4600 )
    qword_4040 = 0LL;
  return v1;
}

This also makes sense because at the start of the function, we check if read_ptr and write_ptr are not same, otherwise it would mean that the buffer is empty. From this we can also rename sub_138A to is_buffer_empty as it does the same. We can also rename sub_1318 to circular_buffer_read.

Now let's look at sub_13AB:

__int64 __fastcall sub_13AB(char a1)
{
  unsigned __int64 i; // [rsp+Ch] [rbp-8h]

  for ( i = 0LL; i <= 9; ++i )
  {
    if ( a1 == *((_BYTE *)&unk_3CE0 + 16 * i) )
      return i;
  }
  return -1LL;
}

This is comparing a1(char from circular_buffer_read) to a dereferenced value from the global buffer/struct. But it's hard to read like this:

But looking at this we can see a clear defined structure, so let's go ahead and make a custom struct for this so it is more readable. So every entry has:

- 1 byte char

- 7 null bytes

- pointer to a string in .rodata (double-click aNs or aJjj to check)

Let's go over to Local types and make this struct:

we save this and we go over to our data in the global section and we hit y on the unk_3CE0 to change it's type to lookup_entry[10]; since we have 10 entries in total. And BOOM! we get a much more readable version:

From this we can get this mapping:

a ---> "ns"
b ---> "jjj"
c ---> "flag"
d ---> "q"
e ---> "tt"
f ---> "gg"
j ---> "gg"
n ---> "a"
p ---> "cor"
s ---> "aaa"

So if we look closely, the code takes each byte of input and checks it against the keys in this struct, if they don't match, it immediately reverts to a fail case and exits the program. So using this we've constrained our flag_bytes to only these 10 characters.

If we look further into the function it does circular_buffer_read twice that means it gets the current and the next flag_byte, but it only uses the flag_byte at the current index to modify the input string.

s = char_lookup_table[char_index].value;
v5 = 0LL;
for ( j = strlen(s); v5 < j; j = strlen(s) )
	circular_buffer_write(s[v5++]);

This piece of code just appends the value from the lookup_table to the end of the input string. So if our string was anp (assuming we pass the checks in our main function), it would become:

anp --------> npns
npns -------> pnsa
pnsa -------> nsacor
nsacor -----> sacora
sacora -----> acoraaaa
acoraaaa ---> coraaaans
coraaaans --> oraaaansflag
oraaaansflag --> Invalid ❌ 

Thinking about this we can rule out some more characters from our lookup_entry table as they'll lead to bad input characters i.e. characters which our not present in the lookup table after expansion. Therefore:

Bad input chars: ['b', 'c', 'd', 'e', 'f', 'j', 'p']

Good input chars: ['a', 'n', 's']

Now if we go back and look at the constraints present in the main function, we can maybe shorten our search space even more. The constraints in the main function are for odd/even indices and can be summarized like this:

There are only 3 types of possible input chars, if we hold the above assumption of good chars. to be true:

Odd1 indices ---> [1, 3, 7, 9, 13, 15...]  
these can only have char "n"  

Odd2 indices ---> [5, 11, 17...] 
these can only have char "s"

Even indices ---> [0, 2, 4, 6...] 
these can only have char "a"

Now that we know which indices can have which chars. we still need to know the length of the flag, but we can just try every flag length upto 30 and one of them should be correct. So we just write a simple script which does that.

Final solve script

from pwn import *

PREFIX = "corctf{"
SUFFIX = "}"

def generate_flags(len):
    
    candidate = []

    for i in range(len):
        if i%2 == 0:
            candidate.append("a")
        elif i % 6 > 3:
            candidate.append("s")
        else:
            candidate.append("n")

    return f"{PREFIX}{''.join(candidate)}{SUFFIX}"

for i in range(31):
    flag = generate_flags(i)
    
    with process("tagme", level="CRITICAL") as p:
        p.sendline(flag)
        
        out = p.recvall()
        if b'Accepted' in out:
            print(out)
            print(flag)

Flag: corctf{ananasananasananasananasana} 🎉