Hackover CTF 2016 Writeup

“are_you_serialz” - Reverse Engineering

Posted by André on October 9, 2016

This was a nice reverse engineering challenge! Only 18 teams managed to solve it. You can download the binary here.

I started by decompiling the binary and inspecting the main function:

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  __int64 result;
  __int64 v4;
  signed int i;
  char v6;
  char s[136];
  __int64 v8;

  setbuf(stdout, 0LL);
  alarm(0xAu);
  puts("--------------------------------------");
  puts("                                      ");
  puts("-- ░█▀▀░█░░░█▀█░█▀▀░▀▀█░█▀▀░█▀▀░█▀█ --");
  puts("-- ░█▀▀░█░░░█▀█░█░█░░▀░░█░█░█▀▀░█░█ --");
  puts("-- ░▀░░░▀▀▀░▀░▀░▀▀▀░░▀░░▀▀▀░▀▀▀░▀░▀ --");
  puts("                                      ");
  puts("------------------------------v2016---");
  puts("Welcome to FLAG?GEN!");
  printf("Please enter your Name: ", 0LL);
  fgets(s, 128, stdin);
  printf("Now please enter your Product Key: ", 128LL);
  fgets(&v6, 32, stdin);
  if ( (unsigned int)sub_AAC((__int64)s, (__int64)&v6) )
  {
    puts("It seems the Product Key you entered is invalid.");
    puts("Please try again...");
    result = 0LL;
  }
  else
  {
    puts("Thank you for purchasing FLAG?GEN!\n");
    memset(s, 0, 0x80uLL);
    sub_A00((__int64)s, 12LL);
    for ( i = 0; i <= 11; ++i )
      s[i] = (unsigned __int8)s[i] % 0x1Au + 97;
    puts("My friend would also like to enjoy this software...");
    printf("Can you give him a serial?\nHis name: %s\n", s);
    printf("Now please enter his Product Key: ");
    do
      fgets(&v6, 32, stdin);
    while ( v6 == 10 );
    if ( (unsigned int)sub_AAC((__int64)s, (__int64)&v6) )
    {
      puts("It seems the Product Key you entered is invalid.");
      puts("Please try again...");
      result = 0LL;
    }
    else
    {
      putchar(10);
      puts("Generating Flag now...");
      printf("<CENSORED|THE_FLAG_WOULD_BE_HERE>", &v6);
      putchar(10);
      puts("Enjoy your flag! ^_^");
      result = 0LL;
    }
  }
  return result;
}

By looking at this code, I realized that if sub_AAC returns 0, the entered serial number is correct. In order to solve the challenge I need to find a valid name/serial pair. Plus, I also need to generate the serial number for a random friend - sub_A00 returns a random name from /dev/urandom. Let's take a look on the serial number validation function!

_DWORD dword_1028[10] =
{
  4294966276,
  4294966282,
  4294966288,
  4294966294,
  4294966300,
  4294966306,
  4294966312,
  4294966318,
  4294966324,
  4294966330
};

__int64 __fastcall sub_AAC(__int64 a1, __int64 a2)
{
  unsigned __int8 v2;
  __int64 result;
  __int64 v4;
  unsigned __int8 v5;
  signed int i;
  int v7;
  int v8;
  unsigned int v9;
  int v10;
  int v11;

  v7 = 0;
  v9 = 0;
  v10 = 0;
  for ( i = 0; i <= 30; ++i )
  {
    v2 = 66
       * (*(_BYTE *)((signed int)(((((unsigned int)((unsigned __int64)i >> 32) >> 29) + (_BYTE)i) & 7)
                                - ((unsigned int)((unsigned __int64)i >> 32) >> 29))
                   + a1)
        + 35);
    v11 = v2 + 2 * i + v10;
    v8 = ((i + v7) ^ 0x66) - v11;
    v5 = (unsigned __int8)(i
                         + *(_BYTE *)((signed int)(((((unsigned int)((unsigned __int64)i >> 32) >> 29) + (_BYTE)i) & 7)
                                                 - ((unsigned int)((unsigned __int64)i >> 32) >> 29))
                                    + a1)
                         + *(_BYTE *)((signed int)(((((unsigned int)((unsigned __int64)i >> 32) >> 29) + (_BYTE)i) & 7)
                                                 - ((unsigned int)((unsigned __int64)i >> 32) >> 29))
                                    + a1)
                         + v2
                         - *(_BYTE *)((signed int)(((((unsigned int)((unsigned __int64)i >> 32) >> 29) + (_BYTE)i) & 7)
                                                 - ((unsigned int)((unsigned __int64)i >> 32) >> 29))
                                    + a1)
                         + 71
                         - 17)
       % 0xAu;

    if ( v5 <= 9u )
      JUMPOUT(__CS__, (char *)dword_1028 + dword_1028[(unsigned __int64)v5]);

    v9 += (unsigned __int8)(v5 ^ *(_BYTE *)(i + a2));
    v7 = v9 * v8;
    v10 = (unsigned __int8)(v5 - 15) + v11 - v5;
  }
  result = v9;
  return result;
}

Well, this code is kinda spooky! So, v9 must be 0 after the loop. XORing the expected serial number v9 with the given serial a2 is a common practice to avoid timing attacks, since the function doesn't simply returns if the first char is wrong, it executes the loop until the end, making the execution time constant.

Before programming the keygen, we need to uncover something: There is a JUMP bastard inside the for loop. I used both static and dynamic analysis, IDA PRO (Hopper disassembler was not working correctly for disassembling) and GDB, respectively, to find out what the target addresses do. Basically, there are 10 possible addresses where the program can jump in this state of execution. When the jump is taken, v5 changes like this:

values = [0x30, 0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31]
v5 = values[v5]

There is another catch: Since i is a signed int, and we have this code ((unsigned int)((unsigned __int64)i >> 32) >> 29), what is being shifted right is not i, but v7, which is the next unsigned int in the stack. So, this code is the same as v7 >> 29.

Then, I translated the code to python. In order to find a valid serial for a given name I changed the code to return how much cycles it executed if a given char is incorrect, instead of continuously XORing the result until the loop ends. This allows us to bruteforce the serial char by char, which is obviously faster than the traditional bruteforcing.

This was my final script:

from pwn import *
import numpy as np

values = [0x30, 0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31]

def stuff(i, v7):
	return np.int32(((np.uint32(v7 >> 29) + (i & 0xff)) & 7) - np.uint32(v7 >> 29))

def validSerial(name, serial):
	v7 = 0
	v10 = 0
	v9 = 0

	for i in range(0, 31):
		v2 = 66 * (name[stuff(i, v7)] + 35)
		v11 = v2 + 2*i + v10
		v8 = ((i + v7) ^ 0x66) - v11

		aux = np.uint8(i + name[stuff(i, v7)] + v2 + 54)

		v5 = aux % 0xA
		v5 = values[v5]

		if (v5 ^ serial[i]) != 0:
			return i+1

		v9 += np.uint8(v5 ^ serial[i])
		v7 = v9 * v8
		v10 = np.uint8(v5 - 15) + v11 - v5;

	return -1

def sToOrdList(s, length):
	l = [0]*length
	ls = list(s)
	for i in range(0, len(s)):
		l[i] = ord(s[i])
	return l

def generateSerial(name):
	name = sToOrdList(name, 128)
	print("> Generating serial...")
	currentSerial = [0]*31
	for j in range(0, 31):
		for i in range(1, 256):
			currentSerial[j] = i
			if (validSerial(name, currentSerial) != (j+1)):
				break

	s = ""
	for n in currentSerial:
		s += chr(n)

	print("> Serial number: %s" % s)
	return s

name = "randomuser"
serial = generateSerial(name)

r = remote("challenges.hackover.h4q.it", 4242)
s = r.recvuntil("Name:")
r.sendline(name)
s = r.recvuntil("Key:")
r.sendline(serial)
s = r.recvuntil("Key:")
name = s[s.find("name:")+6:s.find("Now")-1]
serial = generateSerial(name)
r.sendline(serial)
r.interactive()
> Generating serial...
> Serial number: 2023305842455270646774928689961
[+] Opening connection to challenges.hackover.h4q.it on port 4242: Done
> Generating serial...
> Serial number: 6915455687376778095989902171011
[*] Switching to interactive mode

Generating Flag now...
hackover2016{S3rialzWh3r3Fun}
Enjoy your flag! ^_^