Solving Flaggy Bird (Google CTF 2019)

A few weekends ago we participated in the Google CTF. While we didn’t make it to the top 10, we did manage to solve quite a few challenges. This is my writeup of FlaggyBird, the only mobile challenge that was available.

The challenge

The challenge was an .apk that did not require network connectivity. Installing and opening the app shows a nice game with a bird that can be controlled and after only 20 minutes of frustration, we made it to level three where there are a bunch of egg-hatching machines and a final goal machine. Pressing X at one of the egg-hatching machines allows you to choose an egg, ranging from 0000 to 1111.

After selecting some eggs, you can jump to the finish and test your combination of eggs. If the combination is correct, you will most likely get the flag. Unfortunately, after some guessing, all we got was “Close, but no cigar”

First, let’s analyze the APK by decompiling it with apktool and ByteCodeViewer. A few things stand out:

• There’s a level1.bin, level2.bin and level3.bin in the assets folder.
• There are two native libraries (libgdx.so and library.so).
• Only a few Java classes are included, all of them obfuscated.

Examining the Java code

First, I searched for the “Close, but no cigar” string, which can be found in com.google.ctf.game.f.a() :

void a() {
 byte[] arrby = new byte[32];
 for (int i = 0; i < this.l.length; ++i) {
  for (int j = 0; j < a.length; ++j) {
   if (this.l[i] != a[j]) continue;
   arrby[i] = (byte) j;
  }
 }
 if ((arrby = new Checker().a(arrby)) == null) {
  this.g.a("Close, but no cigar.");
  return;
 }
 try {
  this.o = 0;
  this.a(arrby);
  return;
 } catch (IOException iOException) {
  return;
 }
}

The method builds a byte array of length 32 and passes it to Checker().a . If that call fails, we get our Toast message. So let’s examine the Checker class:

class Checker {
    private static final byte[] a = new byte[]{46, ... , 107};
    private static final byte[] b = new byte[]{-30, ... , 62};
    private static final byte[] c = new byte[]{-113, ... , -17};

    Checker() {
    }

    private byte[] a(byte[] object, byte[] arrby) {
        try {
            IvParameterSpec ivParameterSpec = new IvParameterSpec(b);
            SecretKeySpec secretKeySpec = new SecretKeySpec((byte[])object, "AES");
            object = Cipher.getInstance("AES/CBC/PKCS5PADDING");
            ((Cipher)object).init(2, (Key)secretKeySpec, ivParameterSpec);
            return ((Cipher)object).doFinal(arrby);
        }
        catch (Exception exception) {
            return null;
        }
    }

    byte[] a(byte[] arrby) {
        if (!this.nativeCheck(arrby)) return null;
        try {
            if (!Arrays.equals(MessageDigest.getInstance("SHA-256").digest(arrby), a)) return null;
            return this.a(arrby, c);
        }
        catch (Exception exception) {
            return null;
        }
    }

    public native boolean nativeCheck(byte[] var1);
}

The public a() method checks if the array is correct via the nativeCheck() method. If this method returns true, the SHA256 of the array is calculated. Only if this SHA256 is correct, the array is passed to the private a() method, which uses the array to decrypt the Checker.c byte array. This byte array is then used to load the next level of the game.

Because of the SHA256 check, we can guess that multiple arrays will be valid according to the native check, otherwise there would be no need for the check. We might be able to use this later to figure out the correct solution for the nativeCheck function.

Examining the native code

So let’s take a look at the native code using Ghidra. Only a few methods are available: M, C and nativeCheck. The nativeCheck function takes the 32 bit array from Java and adds all the elements in pairs ( out[0] = in[0] + in[1], out[1] = in[2]+in[3], ... ). It initializes a global variable to 1 and it calls the M method on the newly created byte array. If the global variable is still 1 after M is executed, the method returns successful, indicating that we have a correct solution.

The M function is decompiled by Ghidra as follows:

void M(char *param_1,int param_2)
{
  char *param_1_00;
  char cVar1;
  char cVar2;
  int iVar3;
  int iVar4;
  int param_2_00;
  int iVar5;
  uint param_2_01;
  int iVar6;
  char acStack40 [16];
  int iStack24;
  undefined **ppuStack8;
  
  ppuStack8 = &__DT_PLTGOT;
  iStack24 = __stack_chk_guard;
  if (1 < param_2) {
    param_2_01 = (uint)param_2 >> 1;
    M(param_1,param_2_01);
    if (c != 0) {
      param_2_00 = param_2 - param_2_01;
      param_1_00 = param_1 + param_2_01;
      M(param_1_00,param_2_00);
      if (c != 0) {
        if (param_2_00 < 1) {
          iVar4 = 0;
          iVar5 = 0;
          iVar3 = 0;
        }
        else {
          iVar3 = 0;
          iVar5 = 0;
          iVar4 = 0;
          do {
            cVar2 = param_1_00[iVar5];
            cVar1 = param_1[iVar4];
            if (cVar1 < cVar2) {
              if (*(int *)(d + p * 4) != 1) {
LAB_00010725:
                c = 0;
                goto LAB_000107b4;
              }
              p = p + 1;
              acStack40[iVar3] = param_1[iVar4];
              iVar4 = iVar4 + 1;
            }
            else {
              if ((param_1[iVar4] == cVar2 || cVar1 < cVar2) || (*(int *)(d + p * 4) != 0))
              goto LAB_00010725;
              p = p + 1;
              acStack40[iVar3] = param_1_00[iVar5];
              iVar5 = iVar5 + 1;
            }
            iVar3 = iVar3 + 1;
          } while ((iVar4 < (int)param_2_01) && (iVar5 < param_2_00));
        }
        iVar6 = iVar3;
        if (param_2_01 - iVar4 != 0 && iVar4 <= (int)param_2_01) {
          iVar6 = (iVar3 + param_2_01) - iVar4;
          memcpy(acStack40 + iVar3,param_1 + iVar4,param_2_01 - iVar4);
        }
        if (iVar5 < param_2_00) {
          memcpy(acStack40 + iVar6,param_1 + iVar5 + param_2_01,(param_2 - iVar5) - param_2_01);
        }
        memcpy(param_1,acStack40,param_2);
      }
    }
  }
LAB_000107b4:
  if (__stack_chk_guard != iStack24) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return;
}

This function is a little bit daunting, but after some variable renaming, this becomes more obvious:

/* M(char*, int) */

void M(char *input_array,int input_length)

{
  int output_counter;
  int input_array_counter;
  int half_of_input_lenght2;
  int second_half_counter;
  uint half_of_input_length;
  int iVar1;
  char output_array [16];
  int stack_guard;
  char *second_half_of_input_array;
  char current_char_second_half;
  char current_char_first_half;
  
  stack_guard = __stack_chk_guard;
  if (1 < input_length) {
    half_of_input_length = (uint)input_length >> 1;
    M(input_array,half_of_input_length);
    if (BADBOY != 0) {
      half_of_input_lenght2 = input_length - half_of_input_length;
      second_half_of_input_array = input_array + half_of_input_length;
      M(second_half_of_input_array,half_of_input_lenght2);
      if (BADBOY != 0) {
        if (half_of_input_lenght2 < 1) {
          input_array_counter = 0;
          second_half_counter = 0;
          output_counter = 0;
        }
        else {
          output_counter = 0;
          second_half_counter = 0;
          input_array_counter = 0;
          do {
            current_char_second_half = second_half_of_input_array[second_half_counter];
            current_char_first_half = input_array[input_array_counter];
            if (current_char_first_half < current_char_second_half) {
              if (*(int *)(GLOBAL_D + GLOBAL_P * 4) != 1) {
LAB_00010725:
                BADBOY = 0;
                goto LAB_000107b4;
              }
              GLOBAL_P = GLOBAL_P + 1;
              output_array[output_counter] = input_array[input_array_counter];
              input_array_counter = input_array_counter + 1;
            }
            else {
              if ((input_array[input_array_counter] == current_char_second_half ||
                   current_char_first_half < current_char_second_half) ||
                 (*(int *)(GLOBAL_D + GLOBAL_P * 4) != 0)) goto LAB_00010725;
              GLOBAL_P = GLOBAL_P + 1;
              output_array[output_counter] = second_half_of_input_array[second_half_counter];
              second_half_counter = second_half_counter + 1;
            }
            output_counter = output_counter + 1;
          } while ((input_array_counter < (int)half_of_input_length) &&
                  (second_half_counter < half_of_input_lenght2));
        }
        iVar1 = output_counter;
        if (half_of_input_length - input_array_counter != 0 &&
            input_array_counter <= (int)half_of_input_length) {
          iVar1 = (output_counter + half_of_input_length) - input_array_counter;
          memcpy(output_array + output_counter,input_array + input_array_counter,
                 half_of_input_length - input_array_counter);
        }
        if (second_half_counter < half_of_input_lenght2) {
          memcpy(output_array + iVar1,input_array + second_half_counter + half_of_input_length,
                 (input_length - second_half_counter) - half_of_input_length);
        }
        memcpy(input_array,output_array,input_length);
      }
    }
  }
LAB_000107b4:
  if (__stack_chk_guard != stack_guard) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return;
}

This is a function that performs a merge sort on the input array. Merge sort is a divide-and-conquer approach to sorting, which explains why the input array is split into two arrays and sorted recursively.

A very good explanation, together with a Python script that closely resembled the code above, is given by GeeksForGeeks.com ( https://www.geeksforgeeks.org/merge-sort/ ). The image below shows how it works, but take a look at their website for more information:

We know that BADBOY needs to stay 1, which means that at each comparison of the merge sort algorithm, the check involving GLOBAL_P must fail. This means that the method expects a specific array so that when it is sorted, it matches the decisions that are set in the GLOBAL_D variable. Due to the recursiveness of the algorithm, the order of the comparisons is not straightforward, as shown by the green indexes on the image above. The GLOBAL_D array can be extracted using Ghirda (or gdb):

Each time two elements are compared, the next boolean in the GLOBAL_D array is used to see if the comparison should favour the first item (1) or the second item (0). This means that the first four comparisons need to choose the item from the ‘right’ array (0, 0, 0, 0), the fifth comparison has to choose the ‘left’ array (1), then ‘right’ again, etc. Additionally, we see that the byte array must contain unique bytes, since if the condition input_array[input_array_counter] == current_char_second_half is triggered, we also go to BADBOY.

Finding the correct combination

An easy way of getting a correctly sorted array is by implementing the mergesort algorithm and forcing the comparison based on the GLOBAL_D values instead of the actual value of the numbers. If we ‘sort’ the list [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15] according to the GLOBAL_P values, this results in [13 15 3 12 11 9 8 2 1 0 7 4 14 6 10 5] , as is the output of the following python script, which was adapted from the GeeksForGeeks page referenced earlier:

counter = 0

# Python program for implementation of MergeSort 
def shuffleSort(arr): 
    global counter, code
    if len(arr) >1: 
        mid = len(arr)//2 #Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        shuffleSort(L) # Sorting the first half 
        shuffleSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if code[counter] == 1:
                arr[k] = L[i] 
                i+=1
            else: 
                arr[k] = R[j] 
                j+=1
            k+=1

            counter += 1
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+=1
            k+=1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+=1
            k+=1
  
# Code to print the list 
def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i],end=" ") 
    print("") 
  
if __name__ == '__main__': 
    code = [0x0,0x0,0x0,0x0,
            0x1,0x0,0x0,0x1,
            0x0,0x1,0x1,0x1,
            0x1,0x0,0x0,0x0,
            0x1,0x1,0x0,0x0,
            0x1,0x0,0x1,0x0,
            0x0,0x0,0x1,0x1,
            0x1,0x0,0x0,0x0,
            0x1,0x0,0x0,0x0,
            0x0,0x1,0x1,0x1,
            0x1,0x1,0x0,0x1,
            0x0,0x0,0x1,0x0]


    arr = list("abcdefghijklmnop")
    print ("Given array is", end="\n")  
    printList(arr) 
    shuffleSort(arr) 
    print("Shuffled array is: ", end="\n") 
    printList(arr)

The result is an array indicating where each number would end up according to the specific sorting steps. As a result, we need to replace each number with its position in the sorted array. 0 becomes 9, 1 becomes 8, 2 becomes 7, 3 becomes 2, etc. In the end, we end up with the following input array:

[9, 8, 7, 2, 11, 15, 13, 10, 6, 5, 14, 4, 3, 12, 1]

Now there’s just one final step to finding the correct combination of eggs. Since every pair of ints are summed in the native C method to get from a 32 byte array to a 16 byte array, we need to figure out the correct split for each element. This is however a crazy amount of possible solutions, and far too many to brute-force. At this point, I took a guess that the game would actually never put values in both positions 0 and 1, or 2 and 3, which means we only have to figure out 2 possible positions for each number. This would also explain why some eggs magically disappeared when playing the game. The following python script brute forces all possibilities and compares them to the SHA256 string from the original Checker.a() method:

# Warning: Ugly python code ahead
a = [46, 50, 92, -111, -55, 20, 120, -77, 92, 46, 12, -74, 91, 120, 81, -58, -6, -104, -123, 90, 119, -61, -65, -45, -16, 8, 64, -68, -103, -84, -30, 107 ]
for k in range(0, len(a)):
    a[k] = (a[k] + 256) % 256  

import binascii
from hashlib import sha256
targetString = bytearray(a)
print("TARGET: " + binascii.hexlify(targetString))

def test(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p):
    ar = [0] * 32
    ar[0+a] = 9
    ar[2+b] = 8
    ar[4+c] = 7
    ar[6+d] = 2
    ar[8+e] = 11
    ar[10+f] = 15
    ar[12+g] = 13
    ar[14+h] = 10
    ar[16+i] = 6
    ar[18+j] = 5
    ar[20+k] = 14
    ar[22+l] = 4
    ar[24+m] = 3
    ar[26+n] = 0
    ar[28+o] = 12
    ar[30+p] = 1

    h1 = sha256()
    h1.update(bytearray(ar))
    aux = h1.digest()
    if aux == targetString:
        print("Match found: " + str(ar))
        print(binascii.hexlify(bytearray(ar)))

# There must be a better way, but it works   
[test(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) for a in [0, 1] for b in [0, 1] for c in [0, 1] for d in [0, 1] for e in [0, 1] for f in [0, 1] for g in [0, 1] for h in [0, 1] for i in [0, 1] for j in [0, 1] for k in [0, 1] for l in [0, 1] for m in [0, 1] for n in [0, 1] for o in [0, 1] for p in [0, 1]]

After only a few seconds, the correct answer is printed twice, since there is a 0 byte of which the position doesn’t matter:

TARGET: 2e325c91c91478b35c2e0cb65b7851c6fa98855a77c3bfd3f00840bc99ace26b
Match found: [9, 0, 0, 8, 0, 7, 2, 0, 0, 11, 0, 15, 13, 0, 10, 0, 6, 0, 0, 5, 14, 0, 0, 4, 0, 3, 0, 0, 12, 0, 1, 0]
0900000800070200000b000f0d000a00060000050e000004000300000c000100
Match found: [9, 0, 0, 8, 0, 7, 2, 0, 0, 11, 0, 15, 13, 0, 10, 0, 6, 0, 0, 5, 14, 0, 0, 4, 0, 3, 0, 0, 12, 0, 1, 0]
0900000800070200000b000f0d000a00060000050e000004000300000c000100

Submitting the combination

Finally, we have to inject this byte string into the game. Either we figure out which egg incubator matches which byte position, or we just use Frida to inject our own byte array when the validation method is called:

function myRunner()
{
    var c2 = Java.use("com.google.ctf.game.Checker")
    c2.a.overload('[B').implementation = function(arg)
    {
        var key = [9, 0, 0, 8, 0, 7, 2, 0, 0, 11, 0, 15, 13, 0, 10, 0, 6, 0, 0, 5, 14, 0, 0, 4, 0, 3, 0, 0, 12, 0, 1, 0]
       
        arguments[0] = key
        console.log("Using key: " + key)

        var result = this.a.overload('[B').apply(this, arguments);
        return result
    }
}
Java.perform(myRunner);

After jumping to the validator and pressing X, we end up on the newly decrypted level and we can read the flag!

This was a very nice challenge, and I learned a lot. It took me quite some time to solve the challenge since I waited far too long to manually reverse the M() function. The recursiveness was daunting, but after just a few minutes of renaming I recognised the sorting method, which suddenly made everything much easier. I also spent quite a lot of time using GDB to instrument the native code, and even though this didn’t give any useful results, I still learned a lot :).

About the author

Jeroen Beckers is a mobile security expert working in the NVISO Cyber Resilience team and co-author of the OWASP Mobile Security Testing Guide (MSTG). He also loves to program, both on high and low level stuff, and deep diving into the Android internals doesn’t scare him. You can find Jeroen on LinkedIn .