Points: 94pt (dynamic, 131 solves)

Description: Can you find the correct key to unlock this app?

Given: reverse.apk

TL;DR

  1. notice that besides the dummy flag in the try statement there is a lot of stuff going on in the catch statement
  2. each 4 chars of the flag are encoded to a 32bit number
  3. simplyfying the given equation we know that f0 = m0(each_32bit_input,4294967296)[0] % 4294967296
  4. bruteforce 4 chars at a time/notice that m0 is actually EGCD and that f0 is actually inverse(each_32bit_input,4294967296) and get the flag

Reverse

The given application appears to be a pretty simple flag checker (classical reverse stuff, duh). To reverse the apk I chose jadx-gui since from past experiences it proved to be the most accurate/readable android decompiler. Once I opened up the apk I noticed a class named C0000 (name may vary) inside the Activity class with the same name (once again names may vary) with some interesting hardcoded values:

public C0000() {
    this.f0class = new long[]{40999019, 2789358025L, 656272715, 18374979, 3237618335L, 1762529471, 685548119, 382114257, 1436905469, 2126016673, 3318315423L, 797150821};
    this.f2 = new long[12];
    this.f1 = 0;
}

I also noticed a char array hardcoded on the try statement of the onClick event function but it was just a dummy flag the translated to “Apparently this is not the flag. What’s going on?”.

So i decided to look to the catch statement as it seemed to have a lot of weird stuff going on.

From observing the first if statement it is obvious that the flag length should be equal to 48.

if (flagString.length() != 48) {
    textView.setText("❌");
    return;
}

Taking a look at the for statement right below, it takes each 4 bytes of the flag and packs it into a 32bit number storing it in C0000.f2 (which makes sense since f2 is a array of size 12 and 12*4=48=flag.length)

for (int i = 0; i < flagString.length() / 4; i++) {
    C0000.this.f2[i] = (long) (flagString.charAt((i * 4) + 3) << 24);
    C0000.this.f2[i][i] = C0000.this.f2[i][i] | ((long) (flagString.charAt((i * 4) + 2) << 16));
    C0000.this.f2[i]2[i] = C0000.this.f2[i]2[i] | ((long) (flagString.charAt((i * 4) + 1) << '\b'));
    C0000.this.f2[i]3[i] = C0000.this.f2[i]3[i] | ((long) flagString.charAt(i * 4));
}

Now we have a equation that needs to be satisfied in order to get a valid flag R.m0(C0000.this.f2[C0000.this.f1], 4294967296L)[0] % 4294967296L) + 4294967296L) % 4294967296L != C0000.this.f0class[C0000.this.f1]. With some basic math knowledge, it is trivial to assume that the sum and the modulo after the first modulo makes absolutely no difference: m0(f2[f1], 4294967296)[0] % 4294967296) == f0[f1]. Even though this is not totally explicit in the code I assumed that f1 is a counter that iterates the 12 values in f2.

Solution

So my initial (lazy) thought was just bruteforce every 4 chars of the flag, but my teammate @icemonster (props to him) quickly realised that the m0 function was just a egcd algorithm implementation and by passing 4294967296 as the second argument, getting the first term of the result and applying the modulo with the same constant it was the same as inverting f2[f1] modulo 4294967296 and we get: f0[f1] = inverse(f2[f1],4294967296) -> f2[f1] =inverse(f0[f1],4294967296). Mapping every f0 value to its inverse and unpacking each f2 value from long to char the flag magically appears.

CTF{y0u_c4n_k3ep_y0u?_m4gic_1_h4Ue_laser_b3ams!}

Additional notes:

From looking at the code produced by other decompilers and at the autogenerated comments from jadx it looks like there was some obfuscation going on with the class and variable names but jadx translated it automatically to more readable names and thus made it a lot easier to reverse (it is what it is) so my general advice is to not trust just one decompiler and instead look at as many as you can comparing the resulting code between them.

Resources:

Solution script (with both bruteforce and inversion) and decompiled code (from jadx) can be found here: android.decompiled exploit.py