Writeup shallweplayagame from GOOGLE CTF Qualifier 2018

Challenge: “Win the game 1,000,000 times to get the flag.”

To get things started, I ran the apk in Anbox. We are greeted by a Tic-Tac-Toe implementation. Now from the challenge we know that we have to win the game 1 million times to get the flag. Being an avid gamer, I took this challenge and just went on a 1 million games winning streak, thanks for reading this Write-Up.

Jokes aside, this would not be a challenge, as the used AI seems to play really random, so we basically win after 3 turns anyway. So lets get us a real challenge.

Prerequisites

For this challenge, I used the following tools

• http://www.javadecompilers.com/apk to decompile the provided apk into readable (although for me not recompileable) java code
• APK Easy Tool (Windows) to decompile the apk into bytecode and to recompile this into the apk.
• Anbox - Android in a box, to run the apk
• (adb to install apks into Anbox)

Java

First thing to do was decompile the apk into some readable java code. You will find some files in which only really one is relevant, namely GameActivity.java

We can now begin to look for clues on how to achieve our goal. We know, that we need to win 1 million times, so searching for "1000000" gets us to this bit of code:

void m3215n() {
    for (int i = 0; i < 3; i++) {
        for (int i2 = 0; i2 < 3; i2++) {
            this.f2327l[i2][i].m3222a(C0648a.EMPTY, 25);
        }
    }
    m3212k();
    this.f2330o++;
    Object _ = C0644N.m3217_(Integer.valueOf(2), C0644N.f2338e, Integer.valueOf(2));
    C0644N.m3217_(Integer.valueOf(2), C0644N.f2339f, _, this.f2332q);
    this.f2332q = (byte[]) C0644N.m3217_(Integer.valueOf(2), C0644N.f2340g, _);
    if (this.f2330o == 1000000) {
        m3214m();
        return;
    }
    ((TextView) findViewById(R.id.score)).setText(String.format("%d / %d", new Object[]{Integer.valueOf(this.f2330o), Integer.valueOf(1000000)}));
}c0649a

So when we win 1 million times, the method m3214m() is called. Lets take a look.

void m3214m() {
    Object _ = C0644N.m3217_(Integer.valueOf(0), C0644N.f2334a, Integer.valueOf(0));
    Object _2 = C0644N.m3217_(Integer.valueOf(1), C0644N.f2335b, this.f2332q, Integer.valueOf(1));
    C0644N.m3217_(Integer.valueOf(0), C0644N.f2336c, _, Integer.valueOf(2), _2);
    ((TextView) findViewById(R.id.score)).setText(new String((byte[]) C0644N.m3217_(Integer.valueOf(0), C0644N.f2337d, _, this.f2333r)));
    m3216o();
}

This is the relevant part. When we win, the flag is printed to the screen. As we can see, the flag seems to depend on C0644N.m3217_()

((TextView) findViewById(R.id.score)).setText(new String((byte[]) C0644N.m3217_(Integer.valueOf(0), C0644N.f2337d, _, this.f2333r)));

If you take a look at the decompiled source, it seems that this is a native object, which means that this is not part of the java source but a different binary.

You might wonder at this point, why we didn’t just change the 1 million to 1 and so win after one game.

As it turns out, everytime C0644N.m3217_() is called, some data value we cannot easily modify changes. Lets find out where this is called. Looking back at our win condition, this is what happens before evaluating how many games we have won.

this.f2330o++;
Object _ = C0644N.m3217_(Integer.valueOf(2), C0644N.f2338e, Integer.valueOf(2));
C0644N.m3217_(Integer.valueOf(2), C0644N.f2339f, _, this.f2332q);
this.f2332q = (byte[]) C0644N.m3217_(Integer.valueOf(2), C0644N.f2340g, _);

As you can see, everytime we win, C0644N.m3217_(..., this.f2332q) is called. and its return value gets saved in this.f2332q. So to get the flag, this value needs to be correct. Now we have everything we need to break the challenge. Call this code 1 million times. This would be our solution in java:

for(int i=0; i<1000000; i++){
    this.f2330o++;
    Object _ = C0644N.m3217_(Integer.valueOf(2), C0644N.f2338e, Integer.valueOf(2));
    C0644N.m3217_(Integer.valueOf(2), C0644N.f2339f, _, this.f2332q);
    this.f2332q = (byte[]) C0644N.m3217_(Integer.valueOf(2), C0644N.f2340g, _);
}

Dalvik bytecode

As I mentioned before, my java code was not recompilable, so lets decompile the source into bytecode, and change it. Again, the place to start is our known value 1000000. Values are assigned in hex, so we need to look for 0xF4240. We get exactly one match, so we can be pretty sure to have found the correct method.

.method n()V

    .locals 12

    const v9, 0xF4240

    
    (...)
    

    goto :goto_2

.end method

Taking a look at how our register v9 is used, we soon find:

if-ne v0, v9, :cond_2

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

:goto_2
return-void

This basically means that if v0 equals v9, we call the specified method. This is the equivalent to our java code where we call the win method as soon as we hit 1 million wins. Now we know that v0 is the register that counts our wins. Tracing back a little, we find the correct bytecode line that increments our win counter:

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

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

add-int/lit8 v0, v0, 0x1

A method gets called, then our register is loaded and increased. As a reminder, this is our java code:

m3212k();
this.f2330o++;

Looks about right. Lets take a look at loops in bytecode

const v11,  0x0

:goto_3

if-eq v9, v11, :cond_3

add-int/lit8 v11, v11, 0x1


(...)


goto :goto_3

:cond_3

First, we need a new register for our loop index. Lets call this v11, as this name is not yet taken. We specify a goto mark :goto3, and then check whether our counter is equal to v9. Remember, v9 is the constant 1 million. If it is equal, we want to break out of the loop, so we want to jump to our condition :cond3. If not, we need to increase the counter and execute the loop body. Obviously, we need to place the first 4 lines directly in front of the win counter incrementation:

const v11,  0x0

:goto_3

if-eq v9, v11, :cond_3

add-int/lit8 v11, v11, 0x1

add-int/lit8 v0, v0, 0x1         #win counter

(...)

goto :goto_3

:cond_3

(...)

And, analogous to our java code, we want to loop everything up to the win check.

const v11,  0x0

:goto_3

if-eq v9, v11, :cond_3

add-int/lit8 v11, v11, 0x1

add-int/lit8 v0, v0, 0x1         #win counter

(...)

goto :goto_3

:cond_3

if-ne v0, v9, :cond_2            #win check

(...)

Oh, and one important thing to not forget is to change the number of registers used in this method:

.method n()V
    .locals 12

    (...)

.end method

We define 12 registers, as we chose v11 as our loop index. This leaves us with the registers (v0, ..., v11).

Thats all we had to do, so lets give it a spin. Recompile this into our apk, run the game, and win one time. Now our loop runs (this may take some time) and we are greeted by our flag.