Blizzard CTF 2017 – The LichKing Reverse Engineering challenge walkthrough

The Lichking challenge

Challenge demo. Click on the picture to enlarge it.

I created this challenge for the Blizzard 2017 CTF competition that took place on 11/05/2017 in the eSports Arena in Santa Ana, Orange County, CA.
(https://ctftime.org/event/487). After the CTF event was over, I decided to release it to public and see who can crack it.

This challenge is inspired by the picture password login feature from Windows 8. When you run the challenge, you will be presented with a picture. Your goal is guess what are the 4 secret coordinates (hidden spots) in the picture that you should be clicking using the correct sequence. Once guessed correctly, a congratulatory message box is displayed. If you fail to guess the right 4 points coordinates, then you will see an error message.

This is a pure reverse engineering puzzle and therefore you won’t find any obfuscation or anti-debugging/reverse engineering tricks whatsoever. In the challenge, I left a bunch of hints to make it easy for others to solve the puzzle. Nonetheless, taking the brute-force approach leads to uncovering the hidden message, however this is not the proper solution I am expecting from participants.

Table of contents

How to use

  1. Download the challenge from here
  2. Unzip and run BlizzardLichKing.exe
  3. There are 4 hidden spots in the image
  4. Click on the image 4 times at random locations (click sequence makes a big difference)
  5. If you find the correct sequence you will get a nice message congratulating you

Note: You might need to download the Visual Studio C++ 2017 redistributable package from here.

Challenge goals

When the challenge was released, I provided 5 questions that can be answered as you make progress:

  1. What’s the general idea about the challenge and how it works behind the scene?
  2. What are the approximate locations / coordinates and their proper sequence that lead to successfully unscrambling the hidden message?
  3. If you were given another binary with different coordinates and secret message, can you generically crack it (or at least with little efforts and manual intervention)?
  4. Any cool stuff you appreciated in the challenge or any other things that were not directly obvious?
  5. Did you find any Easter eggs or hints in the binary?

Important note: revealing the hidden message without giving the coordinate sequence is an acceptable solution but not the preferred one.

Walkthrough

I am aware that there are multiple ways to approach and solve this challenge, however I will show you the solution that fulfills all of the 5 challenge goals above.

Getting started

My favorite tools for most RE tasks is IDA Pro. Let’s load the binary in IDA and see what we get:

IDA detected two possible ways to load the file:

  • .NET assembly file
  • PE64 file

From this we can conclude that this is a mixed mode C++ program. It contains both managed (MSIL) and native code.

In a mixed mode program, the .NET managed code executes first, therefore let’s load the file as a .NET assembly and see what we get:

Unless you are a .NET IL assembly language expert, it is better to use one of the free .NET decompilers (such as Telerik’s JustDecompile or dnSpy for instance).

Inspecting the managed code

In this section, we will take a look at the decompiled C# code. Let’s find the main() function in the decompiled output of dnSpy by expanding the “{}-” node and then the “<Module>” node where the main function is found:

internal static int main(string[] args)
{
  <Module>.FreeConsole();
  MyForm frm = new MyForm();
  int i = 0;
  if (0 < args.Length)
  {
    do
    {
      if (args[i] == "WhereAmI")
      {
        frm.ShowCoords = true;
      }
      else if (args[i] == "ShowItToMe")
      {
        frm.ShowFirstPoint = true;
      }
      else if (args[i] == "Cred1ts")
      {
        MessageBox.Show("This challenge has been created by Elias Bachaalany @0xeb!");
      }
      i++;
    }
    while (i < args.Length);
  }
  Application.Run(frm);
  return 0;
}

From the code above, we learn that there are 3 secret command line arguments: WhereAmI, ShowItToMe and Cred1ts.

Let’s now dive into the MyForm code and see how the ShowCoords and ShowFirstPoint boolean member variables are used.

The ShowCoords variable seems to display the mouse coordinates in the form’s title. This is useful for precision clicking / remembering the exact coordinates where you clicked as you debug the code:

private void pictureBox1_MouseMove(object sender, MouseEventArgs e)
{
  if (this.ShowCoords)
  {
    this.Text = string.Format("{0} - {1} {2}", this.Title, e.X, e.Y);
  }
}

Let’s inspect the executable’s managed resources (also using dnSpy) and in particular the embedded picture (in order to extract its dimensions):

After saving the picture and looking at its header, we can tell that it is a JPEG picture. Open it and inspect its dimensions (using your favorite picture viewer):

  • WIDTH = 851
  • HEIGHT = 541

Going back to the main() function, the ShowFirstPoint variable is used inside a timer callback. When timer_1 elapses and when ShowFirstPoint is specified, one hard-coded coordinate is queued into the m_points list:

private int CX0 = 543;
private int CY0 = 175;

private void timer1_Tick(object sender, EventArgs e)
{
  if (this.ShowFirstPoint)
  {
    this.ShowFirstPoint = false;
    Point item = new Point(this.CX0, this.CY0);
    this.m_points.Add(item);
  }
  ...
}

Is it safe to assume that CX0 and CY0 are valid first coordinates? For now yes, since we had to guess the secret argument ShowFirstPoint, which apparently serves as a hint to help the reverse engineer.

Who else queues coordinates in the list?

private void pictureBox1_MouseUp(object sender, MouseEventArgs e)
{
  if (!this.timer2.Enabled)
  {
    Point this2 = new Point(e.X, e.Y);
    this.m_points.Add(this2);
  }
}

When the user clicks on the picture, the MouseUp event does not immediately check for the validity of the coordinate. Instead, it just queues the point coordinates.

Let’s take a look at the remaining code in the timer1 handler:

private void timer1_Tick(object sender, EventArgs e)
{
  if (this.ShowFirstPoint)
  { 
     ...
  }
  else if (this.m_points.Count != 0)
  {
    Point pt = this.m_points[0];
    this.m_points.RemoveAt(0);
    if (this.m_coll.Count == 0)
    {
      int v;
      if (Math.Sqrt(Math.Pow((double)Math.Abs(this.CX0 - pt.X), 2.0) + Math.Pow((double)Math.Abs(this.CY0 - pt.Y), 2.0)) < 25.0)
      {
        v = 1;
      }
      else
      {
        v = 0;
      }
      this.b_pass1 = (v != 0);
    }
    this.pictureBox1.CreateGraphics().DrawEllipse(Pens.Red, pt.X - 25, pt.Y - 25, 50, 50);
    ulong e2 = (ulong)((ulong)((long)(pt.X + 1981)) << 32);
    ulong encoded_pt = (ulong)(((long)(pt.Y + 17) | (long)e2) ^ -6148914692668172971L);
    this.m_coll.Add(encoded_pt);
    if (this.m_coll.Count == 4)
    {
      this.timer2.Enabled = true;
      this.timer1.Enabled = false;
    }
  }
}

We can see that timer1 checks to see if there are queued points, then it:

  1. Dequeues a point
  2. Checks if the m_coll list was still empty
    1. If it is empty, the code checks the distance between the first point clicked against the hard-coded initial coordinate (CX0, CY0).
    2. If the distance is within 25 pixels range, then b_pass1 is set to true.
    3. If (CX0, CY0) is the center of the circle, then any point within a 25 pixel radius passes the check.
    4. So the first correct coordinate is around the circle with radius R=25 and center C(543, 175)
  3. Draws an ellipse with width=height=50 having the x and y coordinates of the upper-left corner of the ellipse 25 pixels away from the clicked point. Because width and height are equal, DrawEllipse() draws a circle.
    1. The drawn circle’s center is at (x, y)
    2. If the point (x,y) is a correct coordinate, then many more points around it are also valid. In theory, the total valid points would be equal to the area of the circle: 3.14 * 25^2 == 1962.5 possible correct coordinates for each point.
  4. Encodes the (x, y) into a 64-bit number. This encoding is used to create extra work for the reverse engineer. Coordinate encoding as a 64-bits number follows this formula:unsigned __int64 encoded_pt = (((pt.X + 1981) << 32L) | (pt.Y + 17)) ^ 0xAAAAAAAA55555555i64
  5. When 4 points are collected and encoded, the first timer (timer1) is disabled and the second timer (timer2) is enabled
    1. This is a nice technique to make the coordinate checks code a bit asynchronous and out of order.
    2. This forces the reverse engineer to look elsewhere in order to understand how the coordinates checks work.

What we learned so far:

  1. Coordinates are collected into a list and de-queued from a timer callback
  2. The timer callback draws a circle with its center set to the clicked coordinates
  3. Each coordinate (up to 4) is encoded and queued as a single 64-bit integer into another list (m_coll)

Let’s now see how m_coll is used and how the remaining 3 points are checked:

private unsafe void timer2_Tick(object sender, EventArgs e)
{
  this.timer2.Enabled = false;
  if (this.b_pass1)
  {
    StringBuilder s = new StringBuilder();
    int i = 0;
    int c = this.m_coll.Count;
    if (0 < c)
    {
      do
      {
        s.AppendFormat("{0:X16}", this.m_coll[i]);
        i++;
      }
      while (i < c);
    }
    byte* this2 = s.ToString();
    if (this2 != null)
    {
      this2 = (ulong)RuntimeHelpers.OffsetToStringData + this2;
    }
    char* wch = this2;
    string hidden_message = new string(<Module>.native_verify(wch));
    if (hidden_message.Length != 0)
    {
      MessageBox.Show(hidden_message.Replace("@", "\r"), "Congratulations!");
      goto IL_AA;
    }
  }
  MessageBox.Show("Sorry, invalid sequence, please try again!");
  IL_AA:
  this.m_coll.Clear();
  this.b_pass1 = false;
  this.pictureBox1.Refresh();
  this.timer1.Enabled = true;
}

Timer2 callback checks to see if b_pass1 is true and if not, it immediately displays a message saying that the clicked coordinates are wrong. Now we can confirm that indeed, the first point (CX0, CY0) is the correct first point.

If the first coordinate is correct (whether set using the command line hint or guessed correctly), then all the coordinates are serialized into a string in hexadecimal form and then passed to a native method called native_verify. The native verification function returns a Unicode string on success or an empty string on failure.

This concludes our investigation in the managed code part. The next step is to locate and reverse engineer the native function native_verify.

Inspecting the native code

In the first part of this walk-through, we mentioned that we can disassemble the program in two different ways. Let us disassemble the file once more but this time let’s select the “Portable Executable for AMD64 (PE)” file loader.

The next step is to locate the entry point of the native function native_verify. Using dnSpy, we can click on the native_verify function which is called from the timer2 callback to get the metadata associated with this function:

// Token: 0x06000051 RID: 81 RVA: 0x000017FC File Offset: 0x00000BFC
[SuppressUnmanagedCodeSecurity]
[MethodImpl(MethodImplOptions.Unmanaged | MethodImplOptions.PreserveSig)]
internal unsafe static extern char* native_verify(char*);

We can then use the “File Offset” value given by dnSpy and use IDA’s “Jump/Jump to file offset” menu item to locate the native_verify entrypoint:

.text:00000001400017FC                         ; WCHAR *__fastcall native_verify(wchar_t *encoded_coords)
.text:00000001400017FC                         native_verify proc near
.text:00000001400017FC ; DATA XREF: .pdata:ExceptionDir↓o
.text:00000001400017FC
.text:00000001400017FC                         lpWideCharStr= qword ptr -58h
.text:00000001400017FC                         cchWideChar= dword ptr -50h
.text:00000001400017FC                         var_48= dword ptr -48h
.text:00000001400017FC                         num= qword ptr -40h
.text:00000001400017FC                         buf= byte ptr -38h
.text:00000001400017FC                         var_10= qword ptr -10h
.text:00000001400017FC                         var_8= byte ptr -8
.text:00000001400017FC
.text:00000001400017FC                         ; __unwind { // __GSHandlerCheck
.text:00000001400017FC 4C 8B DC                mov     r11, rsp
.text:00000001400017FF 49 89 5B 10             mov     [r11+10h], rbx
.text:0000000140001803 49 89 6B 18             mov     [r11+18h], rbp
.text:0000000140001807 49 89 73 20             mov     [r11+20h], rsi
.text:000000014000180B 57                      push    rdi
.text:000000014000180C 48 83 EC 70             sub     rsp, 70h
.text:0000000140001810 48 8B 05 31 EF 09 00    mov     rax, cs:__security_cookie
.text:0000000140001817 48 33 C4                xor     rax, rsp
.text:000000014000181A 48 89 44 24 68          mov     [rsp+78h+var_10], rax
.text:000000014000181F 33 C0                   xor     eax, eax
.text:0000000140001821 48 8B D9                mov     rbx, rcx
.text:0000000140001824 33 D2                   xor     edx, edx; Val
.text:0000000140001826 89 44 24 30             mov     [rsp+78h+var_48], eax
.text:000000014000182A 49 8D 4B C8             lea     rcx, [r11-38h]; Dst
.text:000000014000182E 44 8D 40 22             lea     r8d, [rax+22h]; Size
.text:0000000140001832 E8 6B 1D 00 00          call    j_memset
.text:0000000140001832
.text:0000000140001837 48 8D 7C 24 30          lea     rdi, [rsp+78h+var_48]
.text:000000014000183C BE 04 00 00 00          mov     esi, 4
.text:0000000140001841 48 8D 2D B8 E7 FF FF    lea     rbp, cs:140000000h
.text:0000000140001841
.text:0000000140001848
.text:0000000140001848                         loc_140001848:
.text:0000000140001848 ; CODE XREF: native_verify+113↓j
.text:0000000140001848 41 B8 10 00 00 00       mov     r8d, 16; MaxCount
.text:000000014000184E 48 8D 4C 24 40          lea     rcx, [rsp+78h+buf]; Dst
.text:0000000140001853 48 8B D3                mov     rdx, rbx; Src
.text:0000000140001856 E8 E5 37 00 00          call    sub_140005040
.text:0000000140001856
.text:000000014000185B 4C 8D 44 24 38          lea     r8, [rsp+78h+num]
.text:0000000140001860 48 8D 15 31 57 00 00    lea     rdx, Format; "%llx"
.text:0000000140001867 48 8D 4C 24 40          lea     rcx, [rsp+78h+buf]; Src
.text:000000014000186C E8 CB 01 00 00          call    sub_140001A3C

After scrolling a bit in the function, I observed various calls leading to function pointers with no apparent indications on how those pointers get initialized. These function pointers could be part of the native code or they could be function pointers in the managed code.

(Function calls)

Let’s take the function sub_140005040 for example which is called from 0x0000000140001856:

.nep:0000000140005040                         sub_140005040   proc near
.nep:0000000140005040 ; CODE XREF: native_verify+5A↑p
.nep:0000000140005040 EB 08                        jmp     short loc_14000504A
.nep:0000000140005040
.nep:0000000140005042 0F 0B                        ud2
.nep:0000000140005042
.nep:0000000140005044 FF 25 BE B6 09 00            jmp     cs:qword_1400A0708
.nep:000000014000504A
.nep:000000014000504A                   loc_14000504A:
.nep:000000014000504A ; CODE XREF: sub_140005040↑j
.nep:000000014000504A FF 25 C0 B6 09 00            jmp     cs:qword_1400A0710
.nep:000000014000504A
.nep:000000014000504A                   sub_140005040   endp

.data:00000001400A0708 06 00 00 06 00 00 00 00 qword_1400A0708 dq 6000006h
.data:00000001400A0710 06 00 00 06 00 00 00 00 qword_1400A0710 dq 6000006h

That stub function jumps into qword_1400A0710 which has the value 0x6000006. This value is the function token id. We can search for that function in dnSpy:

// Token: 0x06000006 RID: 6 RVA: 0x000017E4 File Offset: 0x00000BE4
internal unsafe static int wcsncpy_s<17>($ArrayType$$$BY0BB@_W* _Destination, char* _Source, ulong _Count)
{
  return <Module>.wcsncpy_s(_Destination, 17UL, _Source, _Count);
}

The function sub_140001A3C, from the way it is used, looks like the sscanf function.

The function sub_140005000 is a managed function with token id == 0x6000003, which resolves to:

// Token: 0x06000003 RID: 3 RVA: 0x000010A0 File Offset: 0x000004A0
internal unsafe static uint Marvin32_Hash(void* buf, ulong len, ulong seed)

There are no more mysterious functions called from native_verify. Let’s now try to understand the algorithm.

Coordinate verification algorithm

The native_verify function receives the encoded coordinates (as we learned from the managed code side):

; WCHAR *__fastcall native_verify(wchar_t *encoded_coords)

The following code clearly decodes the coordinates:

native_verify+4C                           @@next_coord:
native_verify+4C   ; CODE XREF: native_verify+113↓j
native_verify+4C   41 B8 10 00 00 00       mov     r8d, 16; MaxCount
native_verify+52   48 8D 4C 24 40          lea     rcx, [rsp+78h+buf]; Dst
native_verify+57   48 8B D3                mov     rdx, rbx; Src
native_verify+5A   E8 E5 37 00 00          call    wcsncpy_s_0
native_verify+5A
native_verify+5F   4C 8D 44 24 38          lea     r8, [rsp+78h+num]
native_verify+64   48 8D 15 31 57 00 00    lea     rdx, Format; "%llx"
native_verify+6B   48 8D 4C 24 40          lea     rcx, [rsp+78h+buf]; Src
native_verify+70   E8 CB 01 00 00          call    sscanf
native_verify+70
native_verify+75   48 8B 44 24 38          mov     rax, [rsp+78h+num]
native_verify+7A   48 B9 55 55 55 55 AA AA+mov     rcx, -6148914692668172971
native_verify+84   48 33 C1                xor     rax, rcx
native_verify+87   48 83 C3 20             add     rbx, 32
native_verify+8B   4C 8B D0                mov     r10, rax
native_verify+8E   48 89 44 24 38          mov     [rsp+78h+num], rax
native_verify+93   49 C1 EA 20             shr     r10, 20h
native_verify+97   41 81 EA BD 07 00 00    sub     r10d, 1981; X coordinate
native_verify+9E   44 8D 48 EF             lea     r9d, [rax-17]; Y coordinate

At the end of the code snippet above, the registers r10d and r9d will contain the user clicked X and Y coordinates respectively.

We can replicate the coordinate decoding function in Python like this:

def decode_coords(s):
    for i in range(0, 4):
       idx = i * 16
       n = int(s[idx:idx+16], 16) ^ 0xAAAAAAAA55555555
    
       x = (n >> 32) - 1981
       y = (n & 0xffffffff) - 17
       
       print("%16X -> x = %d y=%d" % (n, x, y))

Let’s continue with the function:

native_verify+A2   B8 65 83 F5 4E          mov     eax, 4EF58365h
native_verify+A7   41 8D 49 32             lea     ecx, [r9+50]
native_verify+AB   F7 E9                   imul    ecx
native_verify+AD   C1 FA 08                sar     edx, 8
native_verify+B0   8B C2                   mov     eax, edx
native_verify+B2   C1 E8 1F                shr     eax, 31
native_verify+B5   03 D0                   add     edx, eax
native_verify+B7   69 C2 3E 03 00 00       imul    eax, edx, 830
native_verify+BD   2B C8                   sub     ecx, eax
native_verify+BF   B8 65 83 F5 4E          mov     eax, 4EF58365h
native_verify+C4   4C 63 C1                movsxd  r8, ecx; IDX1
native_verify+C7
native_verify+C7   41 8D 4A 19             lea     ecx, [r10+25]
native_verify+CB   F7 E9                   imul    ecx
native_verify+CD   C1 FA 08                sar     edx, 8
native_verify+D0   8B C2                   mov     eax, edx
native_verify+D2   C1 E8 1F                shr     eax, 31
native_verify+D5   03 D0                   add     edx, eax
native_verify+D7   69 C2 3E 03 00 00       imul    eax, edx, 830
native_verify+DD
native_verify+DD   42 0F B6 94 85 A0 62 00+movzx   edx, byte ptr ss:rva tbl2[rbp+r8*4]
native_verify+E6   2B C8                   sub     ecx, eax
native_verify+E8   48 63 C1                movsxd  rax, ecx; IDX2
native_verify+EB   0F B6 8C 85 A0 62 00 00 movzx   ecx, byte ptr ss:rva tbl2[rbp+rax*4]
native_verify+F3   0F AF D1                imul    edx, ecx
native_verify+F6   41 69 C1 53 03 00 00    imul    eax, r9d, 851
native_verify+FD   41 03 C2                add     eax, r10d
native_verify+100  48 63 C8                movsxd  rcx, eax
native_verify+103
native_verify+103  32 94 29 90 00 03 00    xor     dl, (tbl1 - __IMAGEBASE)[rcx+rbp]
native_verify+A2   B8 65 83 F5 4E          mov     eax, 4EF58365h
native_verify+A7   41 8D 49 32             lea     ecx, [r9+50]
native_verify+AB   F7 E9                   imul    ecx
native_verify+AD   C1 FA 08                sar     edx, 8
native_verify+B0   8B C2                   mov     eax, edx
native_verify+B2   C1 E8 1F                shr     eax, 31
native_verify+B5   03 D0                   add     edx, eax
native_verify+B7   69 C2 3E 03 00 00       imul    eax, edx, 830
native_verify+BD   2B C8                   sub     ecx, eax
native_verify+BF   B8 65 83 F5 4E          mov     eax, 4EF58365h
native_verify+C4   4C 63 C1                movsxd  r8, ecx; IDX1
native_verify+C7
native_verify+C7   41 8D 4A 19             lea     ecx, [r10+25]
native_verify+CB   F7 E9                   imul    ecx
native_verify+CD   C1 FA 08                sar     edx, 8
native_verify+D0   8B C2                   mov     eax, edx
native_verify+D2   C1 E8 1F                shr     eax, 31
native_verify+D5   03 D0                   add     edx, eax
native_verify+D7   69 C2 3E 03 00 00       imul    eax, edx, 830
native_verify+DD
native_verify+DD   42 0F B6 94 85 A0 62 00+movzx   edx, byte ptr ss:rva tbl2[rbp+r8*4]
native_verify+E6   2B C8                   sub     ecx, eax
native_verify+E8   48 63 C1                movsxd  rax, ecx; IDX2
native_verify+EB   0F B6 8C 85 A0 62 00 00 movzx   ecx, byte ptr ss:rva tbl2[rbp+rax*4]
native_verify+F3   0F AF D1                imul    edx, ecx
native_verify+F6   41 69 C1 53 03 00 00    imul    eax, r9d, 851
native_verify+FD   41 03 C2                add     eax, r10d
native_verify+100  48 63 C8                movsxd  rcx, eax
native_verify+103
native_verify+103  32 94 29 90 00 03 00    xor     dl, (tbl1 - __IMAGEBASE)[rcx+rbp]
native_verify+10A  88 17                   mov     [rdi], dl; key[i] = v
native_verify+10C  48 FF C7                inc     rdi
native_verify+10F  48 83 EE 01             sub     rsi, 1
native_verify+113  0F 85 33 FF FF FF       jnz     @@next_coord

With the passed X and Y, we see additional arithmetic operations taking place. X & Y, after some transformation, are used to read from tbl2 to compute an 8-bits key value (let’s call it pk) into the dl register and the linear coordinate value into rcx.

The pk value is then XORed with tbl1[linear_pt==rcx]. The resulting value is a single byte of the decryption key.

Looking back in the disassembly, we see that rsi is initialized with 4 == key size, rdi is a 4 bytes buffer containing the key computed based on the X, Y coordinates and the tables tbl1 and tbl2.

native_verify+3B   48 8D 7C 24 30          lea     rdi, [rsp+78h+key]
native_verify+40   BE 04 00 00 00          mov     esi, 4; KEY SIZE
native_verify+45   48 8D 2D B8 E7 FF FF    lea     rbp, __IMAGEBASE

Before delving into too much details, we know one correct coordinate (CX0=543, CY0=175). Since at native_verify+103 is where the decryption key is computed based on the coordinates, let’s do a small experiment and insert a non-breaking conditional breakpoint with the following IDC expression:

auto tk = Byte(LocByName("tbl1")+rcx);
Message("i=%d x=%d y=%d xy=%08X pk=%02X tk=%02X -> %02X\n", 4 - rsi, r10d, r9d, rcx, dl, tk, tk ^ dl);

Recap:

  • tk = tbl1[rcx]. Rcx is computed from Y*WIDTH+x
  • pk = Hash(X, Y, tbl2) & 0xff
  • key[i] = tk ^ pk

The assumption would be that if we click anywhere around (CX0, CY0) within 25 pixels radius, we should get the same decryption key value:

All the 4 points were within 25 pixels of the first correct point. The key value was 0x15 for all of the coordinates. Let’s repeat the experiment with another set of coordinates near (CX0, CY0):

This observation leads to an important revelation about the algorithm:

  1. The correct key value is repeated near the correct coordinate
  2. If we try to compute the key for all coordinates, we should reveal all the valid spots because they have the same decryption key

Understanding the hashing function

The following code takes the (X,Y) values and returns a byte, basically acting like “Hash(X, Y) -> uint8_t”.

native_verify+A2   B8 65 83 F5 4E          mov     eax, 4EF58365h
native_verify+A7   41 8D 49 32             lea     ecx, [r9+50]; Y + 50
native_verify+AB   F7 E9                   imul    ecx
native_verify+AD   C1 FA 08                sar     edx, 8
native_verify+B0   8B C2                   mov     eax, edx
native_verify+B2   C1 E8 1F                shr     eax, 31
native_verify+B5   03 D0                   add     edx, eax
native_verify+B7   69 C2 3E 03 00 00       imul    eax, edx, 830
native_verify+BD   2B C8                   sub     ecx, eax
native_verify+BF   B8 65 83 F5 4E          mov     eax, 4EF58365h
native_verify+C4   4C 63 C1                movsxd  r8, ecx; IDX1
native_verify+C7
native_verify+C7   41 8D 4A 19             lea     ecx, [r10+25]
native_verify+CB   F7 E9                   imul    ecx
native_verify+CD   C1 FA 08                sar     edx, 8
native_verify+D0   8B C2                   mov     eax, edx
native_verify+D2   C1 E8 1F                shr     eax, 31
native_verify+D5   03 D0                   add     edx, eax
native_verify+D7   69 C2 3E 03 00 00       imul    eax, edx, 830
native_verify+DD
native_verify+DD   42 0F B6 94 85 A0 62 00+movzx   edx, byte ptr ss:rva tbl2[rbp+r8*4]
native_verify+E6   2B C8                   sub     ecx, eax
native_verify+E8   48 63 C1                movsxd  rax, ecx; IDX2
native_verify+EB   0F B6 8C 85 A0 62 00 00 movzx   ecx, byte ptr ss:rva tbl2[rbp+rax*4]
native_verify+F3   0F AF D1                imul    edx, ecx
native_verify+F6   41 69 C1 53 03 00 00    imul    eax, r9d, 851
native_verify+FD   41 03 C2                add     eax, r10d
native_verify+100  48 63 C8                movsxd  rcx, eax

The compiler used a technique called “division by invariant integers using multiplication” to achieve the division/modulo operation. If you had the Hex-Rays decompiler, you should see something like this:

// .rdata:00007FF7051162A0 ; int tbl2[830]
unsigned char Hash(int x, int y)
{
    return (tbl2[(x + 25) % sizeof(tbl2)] * tbl2[(y + 50) % sizeof(tbl2)]) & 0xff;
}

The key is then computed as such:

native_verify+F6   41 69 C1 53 03 00 00    imul    eax, r9d, 851 ; WIDTH*Y
native_verify+FD   41 03 C2                add     eax, r10d ; EAX = WIDTH*Y + X
native_verify+100  48 63 C8                movsxd  rcx, eax ; ECX = linear_pt
native_verify+103
native_verify+103  32 94 29 90 00 03 00    xor     dl, (tbl1 - __IMAGEBASE)[rcx+rbp] ; dl ^ tbl1[lin_pt]
native_verify+10A  88 17                   mov     [rdi], dl; key[i] = v
native_verify+10C  48 FF C7                inc     rdi
native_verify+10F  48 83 EE 01             sub     rsi, 1
native_verify+113  0F 85 33 FF FF FF       jnz     @@next_coord

And in pseudo-code, the key[i] value is compute as:

unsigned char key[4];
for (int i=0;i<4;i++)
{
  int linear_pt = pt[i].y * WIDTH + pt[i].x;
  key[i] = Hash(pt[i].x, pt[i].y, tbl2) ^ tbl1[linear_pt]
}

From the usage of the tbl1 array, we can deduce that this table should be big enough to hold all the pixels in the picture. Let’s inspect its size in IDA:

.data:00007FF705140090                         ; _BYTE tbl1[460391]
.data:00007FF705140090 6B 58 F2 35 AB 39 B3 0A+tbl1 db 6Bh, 58h, 0F2h, 35h, 0ABh, 39h
.data:00007FF705140090 26 1A 53 9D 4F 39 6B 37+; DATA XREF: native_verify+103↑r

The size 460391 is really WIDTH*HEIGHT == 851 * 541.

Scrolling further in the rest of the function, we see a decryption loop using the computed 4 bytes key followed by a hash check (using the Marvin function):

...
decryption loop
...
native_verify+1C5  49 B8 EB 00 81 19 17 04+mov     r8, 417198100EBh; seed
native_verify+1CF  48 8B D6                mov     rdx, rsi; len
native_verify+1D2  48 8B CF                mov     rcx, rdi; buf
native_verify+1D5  E8 2A 36 00 00          call    Marvin32_Hash
native_verify+1D5
native_verify+1DA  3D 82 4A 85 70          cmp     eax, 70854A82h ; Check for the correct hash
native_verify+1DF  75 34                   jnz     short loc_7FF6981D1A11

When the message is decrypted, if its hash does not match the value 0x70854A82 then an empty message is returned. Otherwise, the decrypted string is returned in Unicode:

native_verify+1E1  48 8D 2D FC F1 09 00    lea     rbp, unk_7FF698270BE0
native_verify+1E8  C7 44 24 28 D2 00 00 00 mov     [rsp+78h+cchWideChar], 0D2h; cchWideChar
native_verify+1F0  44 8B CE                mov     r9d, esi; cbMultiByte
native_verify+1F3  48 89 6C 24 20          mov     [rsp+78h+lpWideCharStr], rbp; lpWideCharStr
native_verify+1F8  4C 8B C7                mov     r8, rdi; lpMultiByteStr
native_verify+1FB  33 D2                   xor     edx, edx; dwFlags
native_verify+1FD  33 C9                   xor     ecx, ecx; CodePage
native_verify+1FF  E8 6C 1B 00 00          call    j_MultiByteToWideChar

Detecting the hidden spots in the picture

We now have an understanding of the key generation algorithm. Basically, for each (X, Y) coordinate, if they are part of a correct hidden spot, then we should have the same decryption key.

What if we compute the key for all the coordinates in the picture, trying to see what key each coordinate reveals?

If a coordinate belongs the the correct hidden spot, then we should see a bunch of sequential bytes containing the same values. We can use that trick to reliably guess all the hidden spots.

Here’s a pseudo-code of what I want to achieve:

def find_hidden_spots(encrypted_pixels, decrypted_pixels):
    # encrypted_pixels (tbl1) and decrypted_pixels are arrays with size = [WIDTH * HEIGHT]

    lin_pt = 0
    for y in range(0, HEIGHT):
        for x in range(0, WIDTH):
            decrypted_pixels[lin_pt] = Hash(x, y, tbl2) ^ encrypted_pixels[lin_pt]
            lin_pt += 1

When find_hidden_spots() returns, the decrypted_pixels array should contain a bunch of random bytes (for the incorrect coordinates) and a bunch of consecutive bytes having the same value (in a circular pattern when visualized) revealing the hidden spots (but not their correct click sequence of course).

After that, I want to iterate over the decrypted_pixels array and replace all the equal consecutive byte values with the value 1 and the non-equal bytes with 0. This will aid in the visualization of the hidden spots.

To demonstrate some IDA features, I opt to using this hashing algorithm as a blackbox algorithm. Basically, the goal is to implement both find_hidden_spots() and marking the equal consecutive bytes in IDAPython during a debugging session.

To do that, I need:

  1. The Hash(x, y, tbl2) function code
  2. Access to tbl1 (encrypted_pixels) and a work buffer to store the decrypted_pixels

We are going to use IDA’s Appcall feature:

//
// Initialize the needed Appcall prototypes
//
Appcall.set_appcall_options(0)

WIDTH  = 851
HEIGHT = 541
RADIUS = 25

VirtualAlloc = Appcall.proto(LocByName("kernel32_VirtualAlloc"), "unsigned __int64 __fastcall x(unsigned __int64 lpAddress, unsigned __int64 dwSize, unsigned __int32 flAllocationType, unsigned __int32 flProtect);")
CopyMemory = Appcall.proto(LocByName("ntdll_RtlCopyMemory"), "void __fastcall x(unsigned __int64 Dest, unsigned __int64 Src, unsigned __int64 Size);")
GetModuleHandle = Appcall.proto(LocByName("kernel32_GetModuleHandleA"), "unsigned __int64 __fastcall x(unsigned __int64 lpModuleName);")

base = GetModuleHandle(0).value

Now, let’s allocate a work buffer for the decrypted_pixels storage:

bitmap = VirtualAlloc(0, WIDTH * HEIGHT, Appcall.Consts.MEM_COMMIT, Appcall.Consts.PAGE_READWRITE)
print("Allocated memory for the the bitmap at %X" % bitmap.value)

Then let’s allocate writable executable memory to hold the hashing algorithm + custom ASM code to iterate over all the pixels:

algo = VirtualAlloc(0, 4*1024, Appcall.Consts.MEM_COMMIT, Appcall.Consts.PAGE_EXECUTE_READWRITE)
print("Allocated memory for the algorithm %X" % algo.value)
idc.RefreshDebuggerMemory()

Here’s the handwritten custom ASM driver code that calls the hashing function for all pixels:

[bits 64]
xor r9, r9 ; Y
xor r10, r10 ; X
xor rax, rax ; last value

main:
   .next:
  ; save work registers
  push r9
  push r10
  push rdi
  push rax

  call algo ; returns value in DL
  ; pop work registers
  pop rax
  pop rdi
  pop r10
  pop r9

  ; check for repeating bytes
  cmp ah, dl
  setz al
  stosb

  mov ah, dl ; remember previous value

  ; ++x
  inc r10
  cmp r10, 851 ; WIDTH
  jl .next

  ; x = 0
  xor r10, r10
  ; ++y
  inc r9

  cmp r9, 541 ; HEIGHT
  jl .next

  ret

algo:
  ; unsigned char __usercall algo@<dl>(unsigned __int64 base@<rbp>,unsigned __int32 x@<r10d>, unsigned __int32 y@<r9d>)
  algo:

Basically, the code above is position independent shellcode. It iterates over all the pixels and calls the Hash() function which is located just after this driver code.

Let’s use NASM to assemble this code:

nasm -f bin -o code.bin code.asm

Now let’s copy the driver code + the hash function into the remote memory we just allocated:

ea = algo.value

# Copy the driver code
f = open(r'code.bin', 'rb')
t = f.read()
f.close()
    
idaapi.put_many_bytes(ea, t)
ea += len(t)

# Copy part of the hash (algo) function    
f = LocByName('native_verify') + 0xA2
sz = 0x10A - 0xA2
CopyMemory(ea, f, sz)
PatchDbgByte(ea + sz, 0xC3)            # Append a return instruction

Note how I appended a RET instruction after copying the hash function’s body from “native_verify+A2” to “native_verify+0x10A“.

The last step is to create an Appcall prototype for the driver code that has been written into the process memory:

decrypt_keys = Appcall.proto(algo.value, "void __usercall x(unsigned __int64 base@<rbp>, unsigned __int64 buf@<rdi>);")

The decrypt_keys remote function takes the image base (in the RBP register) and a work buffer as big as WIDTH*HEIGHT (in the RDI register).

Let’s now dump the hidden spots by calling the decrypt_keys() function and then visualize the returned buffer as a bitmap with just two colors: black and red:

from PIL import Image
def get_key_bitmap():
    decrypt_keys(base, bitmap.value)
    b = idaapi.get_many_bytes(bitmap.value, WIDTH*HEIGHT)
    return [ord(x) for x in b]

def dump_key_bitmap():
    bitmap = get_key_bitmap()
    i = 0
    img = Image.new('RGB', (WIDTH, HEIGHT), "black")
    pixels = img.load()
    for h in range(0, HEIGHT):
        for w in range(0, WIDTH):
            pixels[w, h] = (0xFF if bitmap[i] != 0 else 0, 0, 0)
            i += 1

    img.save(r'spots.bmp')

Note that I am using the Python image library to visualize the resulting decrypted pixels. The resulting picture looks like this:

Hidden spots revealed by calling dump_key_bitmap()

Note how we have some tiny red dots, but the real hidden spots are clearly visible as bigger circles. Now, we can re-use the dump_key_bitmap() function for any hidden spots configuration in any future similar challenge.

We can also reveal the hidden spots in ASCII:

def get_pixel_pt(bitmap, x, y):
    lin_pt = (y * WIDTH) + x
    return 0 if lin_pt >= LIN_PT_MAX else bitmap[lin_pt]


def dmp_txt(bitmap):
    for y in range(0, HEIGHT):
        line = []
        for x in range(0, WIDTH):
            line.append(str(get_pixel_pt(bitmap, x, y)))
            
        print "".join(line)

dmp_txt()
Text view inside Visual Studio with a very small font

The last required to solve this challenge is to figure out the click order of the hidden spots. We know that the first spot is the top red dot. We are left with 3 other permutations / possibilities. Basically the total number of permutations is 3 factorial == 6 tries. We can brute-force the 6 tries by calling the native_verify() until it returns a non-empty string.

Guessing the right points sequence

Guessing the right points sequence is the last step in solving this problem. Before we can do that, we need to write a function that finds the circles in the bitmap:

def get_sum(bitmap, x, y, radius, tp=2):
    xsum = 0
    ysum = 0
    if tp & 1:
        xsum = sum([get_pixel_pt(bitmap, i, y) for i in range(x-radius, x+radius)])
    if tp & 2:
        ysum = sum([get_pixel_pt(bitmap, x, i) for i in range(y-radius, y+radius)])
        
    return (xsum, ysum)
        

def find_spots(bitmap):
    y = -1
    points = []
    while y < HEIGHT:
        y += 1
        x = -1
        while x < WIDTH:
            x += 1
            
            if     (x - RADIUS < 0) or (x + RADIUS >= WIDTH) \
               or  (y - RADIUS < 0) or (y + RADIUS >= HEIGHT):
               continue
               
            xsum, ysum = get_sum(bitmap, x, y, RADIUS, 1)
            
            if xsum < DIAMETER-5:
                continue
            
            print("Center at (%d, %d)" % (x, y))
            
            points.append((x, y))

            # Skip to next spot. Algorithm assumes one hidden spot per row
            x += RADIUS                    
            y += RADIUS
            
    return points


points = find_spots(get_key_bitmap())

When we run it, we get:

Python>points = find_spots(b)
Center at (537, 157)
Center at (470, 290)
Center at (631, 346)
Center at (134, 372)
Python>points
[(537, 157), (470, 290), (631, 346), (134, 372)]

Notice how the first point is very close to C0(543, 175). To find out the correct sequence, we can call the native_verify() and exercise all the possible permutations:

import itertools

native_verify = Appcall.proto(idc.LocByName('native_verify'), 'unsigned __int64 __fastcall x(WCHAR *);')

def encode_coords(points):
    s = ''
    for x, y in points:
       n = (((x + 1981) << 32) | (y + 17)) ^ 0xAAAAAAAA55555555
       s += "%16X" % n
    return s

def find_right_combination(points):
    for p in itertools.permutations(points):
        s_ptr = native_verify(Appcall.unicode(encode_coords(p)))
        s = get_strlit_contents(s_ptr.value, -1, ASCSTR_UNICODE)
        if s is not None and (len(s) != 0):
            print("Found correct coordinates: %r -> %s" % (p, s))


find_right_combination(points)

And we get:

Found correct coordinates: ((537, 157), (470, 290), (631, 346), (134, 372)) -> HackTheNexus - Blizzard CTF Challenge 2017 was solved successfully!@@@Lich king! Cut the chain!

Finally, the puzzle is solved! You can download the IDAPython script snippet used in this article from here.

Challenge goals revisited

Let’s go over the initial challenge goals and answer the questions:

  1. What’s the general idea about the challenge and how it works behind the scene?
    • The challenge binary was a mixed mode program. Part of the algorithm is in the managed code and the rest is in the native code. Parts of the 4-bytes secret key are encoded at all the valid coordinates in the bitmap. The correct key for a given spot (with a radius of 25 pixels) contains the same byte value. This is a big tell; this is how we can generically guess where the hidden spots are. We cannot tell their sequence though, instead just where the hidden spots are. This knowledge reduces the brute-force space from 2^24 to Factorial(Number_of_Hidden_Spots – 1) (given that the first point is given).
  2. What are the approximate locations / coordinates and their proper sequence that lead to successfully unscrambling the hidden message?
    • The following sequence of points are the approximate locations of the hidden spots:
      (537, 157), (470, 290), (631, 346), (134, 372)
  3. If you were given another binary with different coordinates and secret message, can you generically crack it (or at least with little efforts and manual intervention)?
    • Yes, the methodology described in this write-up is generic. All we have to do is locate the native_verify() function and find where tbl1 and tbl2 exist. We can then call these function to get the solution: find_right_combination(find_spots(get_key_bitmap()))
  4. Any cool stuff you appreciated in the challenge or any other things that were not directly obvious?
    • I wrote the challenge, so it is hard to objectively answer this question. I enjoyed while designing the puzzle and the key encoder actually (the program that generates the encrypted pixels table).
    • What I assume not to be very obvious to others is what is the relationship between the clicked coordinates and the correct key bytes. Solving the problem generically and uncovering the hidden spots bitmap is cool.
  5. Did you find any Easter eggs or hints in the binary?
    • The only Easter eggs worthwhile mentioning are the hidden command line arguments which gave the first correct coordinate.

Other solutions

When I released the challenge to the public, a few people participated:

  • The occasional trolls I guess: I received some messages on Twitter, not sure if they were trolling me. They said: “Yeah sure, we ran the strings.exe utility and the hidden message is: ‘Congratulations’. Your challenge was lame, it took me two minutes!”
  • Lucas G: He solved the challenge the same day and put this write-up here: https://lucasg.github.io/2017/11/11/Solving-BlizzardCTF-Challenge/
    • I liked how Lucas used detailed descriptions, good illustrations and how he used WinDbg’s SOS extension to debug and get metadata from the managed code
    • The coordinates he shared were: (543, 175), (568, 175), (567, 191), (535, 196). They seem to work to decrypt the message, but they are not the right solution
    • He wrote a mouse clicker to test his solution. Cool!
  • Axel ‘0vercl0k’ Souchet, found some free time and solved this challenge a few days later. He called his solution “King No More
    • He found the following coordinates that compute the right decryption key: (x = 550, y = 165), (x = 1, y = 489), (x = 2, y = 209), (x = 1, y = 17)
    • Unfortunately, these are not the real hidden spots coordinates

Thanks for taking part in this CTF. If you find mistakes in this write-up or have questions then please let me know in the comments below.

StarCraft: Emulating a buffer overflow for fun and profit – REcon Brussels, 2018

Today I present my talk at REcon Brussels. It was about a problem I had to solve at work.

Basically, the classic StarCraft 1.16.1 had a buffer overflow that was exploited to create impressive maps well beyond the original game programming.

In this talk, I explained how I tackled the problem and emulated the buffer overflow so that exploited maps work on the latest version of StarCraft.

By the way, “StarCraft: Remastered” is free (in low-resolution, the HD resolution must be purchased). Download it from Battle.net.

Here’s the full talk abstract:

StarCraft 1.16.1 and older had a buffer overflow bug in the map parsing code. The hackers in South Korea leveraged the buffer overflow to create mods for the game. The mods became so popular that if we fix the buffer overflows we kill all the mods.

This talk shares the technical difficulties faced while solving this problem and also illustrates the various reverse engineering techniques used along the way:

  • How I approached the problem and how the reverse engineering efforts helped solving them
  • How I developed the tracers and instrumentation tools needed for the job
  • How the emulator was designed

You can also download the slides from here:

Introducing Ganxo v0.1 Alpha – An open source API hooking framework

Hello,

Today I release the first Alpha version of Ganxo (pronounced as “Gun Show” or “Gan Chou”), an open source API hooking framework. In Catalan, Ganxo means “hook”, thus the framework’s name.

Writing an API hooking framework was always on my to do list. I started developing Ganxo back in April 2016 and after two weeks of development during my free time, I got busy with other things and abandoned my efforts.

My initial goals were to accomplish the following before going public with it:

  • Support x86 and x64 hooking
  • Write a more extensive test suite
  • Fully document it

This past weekend, I decided to release Ganxo even though I have not met all my goals. As of today, Ganxo works on MS Windows and supports x86 API hooking. The groundwork is laid down and it should be easy to add x64 bits hooking support on Windows or even just port it to other operating systems.

Feel free to clone the code from here and start using it today.

Stay tuned, I plan more features in the coming future!

While at it, check out my Batchography book!

Genesis

Hi there,

This is not the real genesis! This is a continuation from my WordPress hosted blog http://0xeb.wordpress.com/.

This blog will be dedicated to programming, reverse engineering and ranting about the IT industry.

Notable previous blog posts: