Although we haven’t managed to submit the flag correctly, I’m still publishing this write-up. Maybe it helps someone.

The Google CTF 2018 “shall we play a game?” challenge:

This was in the reverse engineering category, only included a link to an apk file (mirror) and the short description to win the game 1’000’000 times to get the flag.

I already had the setup to run and investigate Android Apps from a very great BSides Munich workshop Fun with Frida. In the end I didn’t end up using Frida to solve the challenge, but the setup alone helped a lot already.

Looking at the game, it is a very simple tic-tac-toe game with a win counter that goes up to 1’000’000:

Starting to reverse it I’ve used unpack-apk.sh to extract the apk file and attempt to decompile it as well. Looking at the source code at app/extracted/src/main/java/com/google/ctf/shallweplayagame/GameActivity.java we find that this is the main program. Two functions there are of interest to us (comments by me):

    // Display flag and some magic we don't understand
    void m() {
        Object _ = N._(Integer.valueOf(0), N.a, Integer.valueOf(0));
        Object _2 = N._(Integer.valueOf(1), N.b, this.q, Integer.valueOf(1));
        N._(Integer.valueOf(0), N.c, _, Integer.valueOf(2), _2);
        ((TextView) findViewById(R.id.score)).setText(new String((byte[]) N._(Integer.valueOf(0), N.d, _, this.r)));
        o();
    }

    void n() {
        // Reset the board, remove X and O from the board
        for (int i = 0; i < 3; i++) {
            for (int i2 = 0; i2 < 3; i2++) {
                this.l[i2][i].a(a.EMPTY, 25);
            }
        }
        k();
        // Increase win counter
        this.o++;
        // Some magic we don't understand
        Object _ = N._(Integer.valueOf(2), N.e, Integer.valueOf(2));
        N._(Integer.valueOf(2), N.f, _, this.q);
        this.q = (byte[]) N._(Integer.valueOf(2), N.g, _);
        // Check if win counter is 1'000'000
        if (this.o == 1000000) {
            // Show the flag
            m();
            return;
        }
        ((TextView) findViewById(R.id.score)).setText(String.format("%d / %d", new Object[]{Integer.valueOf(this.o), Integer.valueOf(1000000)}));
    }

My first attempts were to start the game with a win counter of already 999’999 or decrease the 1’000’000 to 2. But neither worked, we won the game but instead of the flag we’d get binary garbage displayed. It’s clear that the magic we don’t understand needs to run 1’000’000 to produce the correct string (line 21 – 23).

I’ve started to look at the assembly file app/extracted/smali/com/google/ctf/shallweplayagame/GameActivity.smali and the method n() as that’s where we need to make changes:

.method n()V
    .locals 10

    const v9, 0xf4240

This must be the right place, 0xf4240 is 1’000’000 in hex. We can somewhat easy find the increase of the win counter:

    iget v0, p0, Lcom/google/ctf/shallweplayagame/GameActivity;->o:I

    add-int/lit8 v0, v0, 0x1

    iput v0, p0, Lcom/google/ctf/shallweplayagame/GameActivity;->o:I

And further down is the win check:

    iget v0, p0, Lcom/google/ctf/shallweplayagame/GameActivity;->o:I

    if-ne v0, v9, :cond_2

    invoke-virtual {p0}, Lcom/google/ctf/shallweplayagame/GameActivity;->m()V

Between those sections, we need to add a new loop which runs 1’000’000 times. I’ve did that with the following patch:

--- orig/GameActivity.smali	2018-06-26 10:47:29.072510136 +0200
+++ patched/GameActivity.smali	2018-06-26 11:21:00.495157390 +0200
@@ -664,7 +664,8 @@
 .end method
 
 .method n()V
-    .locals 10
+    # Increase local variable count by one
+    .locals 11
 
     const v9, 0xf4240
 
@@ -676,6 +677,9 @@
 
     const/4 v6, 0x2
 
+    # Add new variable v10 with value 0
+    const v10, 0x0
+
     move v2, v1
 
     :goto_0
@@ -716,8 +720,20 @@
 
     add-int/lit8 v0, v0, 0x1
 
+    # move 1'000'000 into the win counter, we now only need to win once
+    move v0, v9
+
     iput v0, p0, Lcom/google/ctf/shallweplayagame/GameActivity;->o:I
 
+    # add new loop, goto_3 label
+    :goto_3
+
+    # break out condition, if v10 is 1'000'000 goto cond_3
+    if-ge v10, v9, :cond_3
+
+    # increase loop counter v10 by 1
+    add-int/lit8 v10, v10, 0x1
+
     new-array v0, v7, [Ljava/lang/Object;
 
     invoke-static {v6}, Ljava/lang/Integer;->valueOf(I)Ljava/lang/Integer;
@@ -786,6 +802,12 @@
 
     iput-object v0, p0, Lcom/google/ctf/shallweplayagame/GameActivity;->q:[B
 
+    # end of the for loop, jump back up to goto_3 label until v10 is 1'000'000
+    goto :goto_3
+
+    # break out label, jump here if v10 is 1'000'000
+    :cond_3
+
     iget v0, p0, Lcom/google/ctf/shallweplayagame/GameActivity;->o:I
 
     if-ne v0, v9, :cond_2

Now we just need to build a new apk file, zipalign it, sign it, install it on our emulator and run it:

# apktool b
# zipalign -v 4 dist/app.apk app.aligned.apk
# jarsigner -verbose -storepass android -keystore ~/.android/debug.keystore app.aligned.apk signkey
# adb install app.aligned.apk

And when we run it finally this screen is displayed:

The flag is CTF{ThLssOfInncncIsThPrcOfAppls} or CTF{ThLssOfInncncIsThPrcOfAppIs} or CTF{ThLssOflnncncIsThPrcOfAppls} – I’m still not sure.