# Android (re, 94p, 131 solved)
## Description
In the task we get [an app](https://raw.githubusercontent.com/TFNS/writeups/master/2020-08-24-GoogleCTF/android/reverse.apk) to reverse.Once launched the app asks us for a flag, and then validates it for us.Unlike in many android challenges, there are no native libraries included, so we're working with pure JVM/Dalvik code.
## Static analysis
### Decompilation
Static analysis seems to be a bit tricky, because all general decompilation tools (like ByteCodeViewer or more directly dex2jar) fail on the key classes.
One class `R` that we can decompile has just one recursive function:
```javapublic static long[] ő(final long n, final long n2) {    if (n == 0L) {        return new long[] { 0L, 1L };    }    final long[] result = ő(n2 % n, n);    return new long[] { result[1] - n2 / n * result[0], result[0] };}```
Remaining 2 key classes -> main Activity and some OnClickListener are causing issues to dex2jar.
### Reversing Smali
While we can't decompile those classes or even create a standard JVM bytecode, we must be able to dump Smali Dalvik bytecode, since this is what is actually executed.We can do that with `baksmali` tool.
From this we get [activity](https://raw.githubusercontent.com/TFNS/writeups/master/2020-08-24-GoogleCTF/android/activity.smali) and [listener](https://raw.githubusercontent.com/TFNS/writeups/master/2020-08-24-GoogleCTF/android/listener.smali) (renamed to simplicity).
#### Main activity
We start by looking at the smaller file - activity.There are 3 fields in this class:
```# instance fields.field class:[J
.field ő:I
.field ő:[J```
`Long array` called `class`, `Long array` called `ő` and `Integer` called `ő`
First array is assigned from:
```    const/16 v0, 0xc
    new-array v1, v0, [J
    fill-array-data v1, :array_18
    iput-object v1, p0, Lcom/google/ctf/sandbox/ő;->class:[J```
`0xc` is the size of the array, then it's loaded with constant labelled `array_18`, and finally this is assigned to `Long array` called `class`.
The constant initializer is:
```    :array_18    .array-data 8        0x271986b        0xa64239c9L        0x271ded4b        0x1186143        0xc0fa229fL        0x690e10bf        0x28dca257        0x16c699d1        0x55a56ffd        0x7eb870a1        0xc5c9799fL        0x2f838e65    .end array-data```
Second array is assigned from:
```    new-array v0, v0, [J
    iput-object v0, p0, Lcom/google/ctf/sandbox/ő;->ő:[J```
So it's also `0xc` in size, but it's empty.
Finally the integer is assigned from:
```    const/4 v0, 0x0
    iput v0, p0, Lcom/google/ctf/sandbox/ő;->ő:I```
So it's initalized with 0.
Rest of this class is irrelevant for us.It basically creates a listener for the button on the screen, and that's about it.
#### Listener
The real flag checking logic is hidden in the listener in `onClick` method.It might look at bit scary, because it's long, however most of it is just a red herring...
##### Red herring
The code starts by a very long repeating code like:
```    new-array v2, v2, [Ljava/lang/Object;
    const/16 v8, 0x41
    .line 45    invoke-static {v8}, Ljava/lang/Integer;->valueOf(I)Ljava/lang/Integer;
    move-result-object v8
    aput-object v8, v2, v3
    const/16 v8, 0x70
    invoke-static {v8}, Ljava/lang/Integer;->valueOf(I)Ljava/lang/Integer;
    move-result-object v9
    aput-object v9, v2, v6
    invoke-static {v8}, Ljava/lang/Integer;->valueOf(I)Ljava/lang/Integer;
    move-result-object v8
    aput-object v8, v2, v5```
There is nothing particularly interesting about this code, we're only interested in:
```const/16 v8, 0x70```and```invoke-static {v8}, Ljava/lang/Integer;->valueOf(I)Ljava/lang/Integer;```
It loads value to a register and then calls `valueOf` to create Integer object.Later in the code it takes those ints and uses StringBuilder to construct a string out of them.The string is: `Apparently this is not the flag. What's going on?` and is just a red herring...
##### Actual flag checking
What we're really interested in starts at `.line 61` marker.
```    .line 61    .local v3, "flagString":Ljava/lang/String;    invoke-virtual {v3}, Ljava/lang/String;->length()I
    move-result v5
    const/16 v6, 0x30
    if-eq v5, v6, :cond_21f
    .line 62    iget-object v4, v1, Lcom/google/ctf/sandbox/ő$1;->val$textView:Landroid/widget/TextView;
    const-string v5, "\u274c"
    invoke-virtual {v4, v5}, Landroid/widget/TextView;->setText(Ljava/lang/CharSequence;)V
    .line 63    return-void```
They take length of our input flag string and compare it against `0x30`.If it's matching we go to `cond_21f`, otherwise we get `\u274c` printed (red X) and function returns, so we failed.
If we got the size right we get to:
```    .line 65    :cond_21f    const/4 v5, 0x0
    .line 65    .local v5, "i":I    :goto_220    invoke-virtual {v3}, Ljava/lang/String;->length()I
    move-result v6
    div-int/2addr v6, v7
    if-ge v5, v6, :cond_272```
This is a loop `for(int i=0;i<flagString.length()/4;i++)` with `i` at `v5`Then inside this loop we have 4 very similar blocks:
```    .line 66    iget-object v6, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget-object v6, v6, Lcom/google/ctf/sandbox/ő;->ő:[J
    mul-int/lit8 v8, v5, 0x4
    add-int/2addr v8, v4
    invoke-virtual {v3, v8}, Ljava/lang/String;->charAt(I)C
    move-result v8
    shl-int/lit8 v8, v8, 0x18
    int-to-long v8, v8
    aput-wide v8, v6, v5```
1. Load reference to the empty array we have in `activity` class to `v6` register2. Multiply `i` loop counter by `4` and add `v4` (which is constant `3`), and store to `v8`3. Use this value as index in the array with our input flag4. Take value at this index, shift by 0x18, convert result to long and put in the empty array we have.
Otherwise:
```pythonv8 = i * 4 + 3v8 = flag_string[v8]v8 = v8 << 0x18v6[i] = v8```
We could go through the next 3 blocks the same way, but they do pretty much the same, with some small const changes.At the very end of the loop we have:
```    .line 65    add-int/lit8 v5, v5, 0x1```
so as expected, loop couter `i` is bumped by 1 each iteration. Python version of those 4 similar blocks is:
```pythondef fill_array(flag_string):    v6 = [None for _ in range(0xc)]    for i in range(len(flag_string) / 4):        v8 = i * 4 + 3        v8 = flag_string[v8]        v8 = v8 << 0x18
        v10 = i * 4 + 2        v10 = flag_string[v10]        v10 = v10 << 0x10        v8 = v8 | v10
        v10 = i * 4 + 1        v10 = flag_string[v10]        v10 = v10 << 0x8        v8 = v8 | v10
        v10 = i * 4        v10 = flag_string[v10]        v8 = v8 | v10        v6[i] = v8    return v6```
It's not difficult to recognize that this is in fact simply conversion of a character string into array of 4-byte integer values, big endian.
Going further:
```    const-wide v4, 0x100000000L
    .line 73    .local v4, "m":J```
Long variable `m` is loaded with constant `0x100000000L`
```    iget-object v6, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget-object v7, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget-object v7, v7, Lcom/google/ctf/sandbox/ő;->ő:[J
    iget-object v8, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget v8, v8, Lcom/google/ctf/sandbox/ő;->ő:I
    aget-wide v8, v7, v8
    invoke-static {v8, v9, v4, v5}, Lcom/google/ctf/sandbox/R;->ő(JJ)[J
    move-result-object v6
    .line 74    .local v6, "g":[J```
Here we finally see a call to the function we managed to decompile initially!We take value from those big endian longs we generated, at index pointed by the integer class field in `activity`, and invoke the function as `g = R_fun(array[idx], m)`.
Then we have:
```    const/4 v7, 0x0
    aget-wide v7, v6, v7
    rem-long/2addr v7, v4
    add-long/2addr v7, v4
    rem-long/2addr v7, v4
    .line 75    .local v7, "inv":J```
And this translates to `inv = g[0] % m` using registers loaded before.Then we have:
```    iget-object v9, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget-object v9, v9, Lcom/google/ctf/sandbox/ő;->class:[J
    iget-object v10, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget v10, v10, Lcom/google/ctf/sandbox/ő;->ő:I
    aget-wide v10, v9, v10
    cmp-long v9, v7, v10
    if-eqz v9, :cond_2a3```
Here note that we use `Lcom/google/ctf/sandbox/ő;->class:[J` so the array loaded with static values in `activity` class!What we do, is we check `static_array[idx] == inv`
Then we either go to failure branch or do:
```    .line 79    :cond_2a3    iget-object v9, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget v10, v9, Lcom/google/ctf/sandbox/ő;->ő:I
    const/4 v11, 0x1
    add-int/2addr v10, v11
    iput v10, v9, Lcom/google/ctf/sandbox/ő;->ő:I```
So pretty much just increment the integer field in `activity` by 1.And finally:
```    .line 81    iget-object v9, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget v9, v9, Lcom/google/ctf/sandbox/ő;->ő:I
    iget-object v10, v1, Lcom/google/ctf/sandbox/ő$1;->this$0:Lcom/google/ctf/sandbox/ő;
    iget-object v10, v10, Lcom/google/ctf/sandbox/ő;->ő:[J
    array-length v10, v10
    if-lt v9, v10, :cond_2be```
So once this integer matches length of the array, we finish.
So this whole part is simply doing something like:
```pythonfor idx in range(len(array)):    m = 0x100000000    g = R(array[idx], m)    inv = g[0] % m    assert (static_array[idx] == inv)```
##### Pythonized code:
Finally the flag checker basically does:
```pythonflag = 'CTF{something here....}'static_array = [0x271986b, 0xa64239c9, 0x271ded4b, 0x1186143, 0xc0fa229f, 0x690e10bf, 0x28dca257, 0x16c699d1, 0x55a56ffd, 0x7eb870a1, 0xc5c9799f,0x2f838e65]array = [bytes_to_long_be(c) for c in chunk(flag, 4)]for idx in range(len(array)):    m = 0x100000000    g = R_fun(array[idx], m)    inv = g[0] % m    assert (static_array[idx] == inv)```
## Solver
Now the question is how do we solve this!We could try to invert the `R_fun`, but we're too lazy for that.The checker works chunk by chunk, and each chunk is just 4 bytes long.We can easily brute-force all possible printable values of such chunk, and simply test which one produces matching block...
```pythondef worker(data):    a, static_index = data    static_array = [0x271986b, 0xa64239c9, 0x271ded4b, 0x1186143, 0xc0fa229f, 0x690e10bf, 0x28dca257, 0x16c699d1, 0x55a56ffd, 0x7eb870a1, 0xc5c9799f,                    0x2f838e65]    for b in string.printable:        for c in string.printable:            for d in string.printable:                potential = a + b + c + d                val = bytes_to_long_be(potential)                if compare_b(val, static_array[static_index]):                    print('found', a + b + c + d)                    return a + b + c + d
def main_d():    charset = '_' + string.printable    data = [(c, 0) for c in charset]    brute(worker, data, processes=6)
if __name__ == '__main__':    freeze_support()    main_d()```
We need to run this 12 times, each time changing the block index in data.We can kill the processes once we hit "found" message.It takes a moment and we recover: `CTF{y0u_c4n_k3ep_y0u?_m4gic_1_h4Ue_laser_b3ams!}`