# Tools- [Ghidra](https://ghidra-sre.org) for reverse engineering- [Ghidra bridge](https://github.com/justfoxing/ghidra_bridge) to run our script from outside ghidra- `gdb-multiarch`, `gcc-aarch64-linux-gnu`, `qemu-user-aarch64` Debian packages to use and debug the native library
# Getting the code
An apk file is actually just a zip file. To get the contents just unzip it. The code is in a file called `classes.dex`, which is the binary format used for the android jvm runtime.
So let's load this file into ghidra and get started.
# Search for the flag
We know the format of the flag. Let's see if we can find that string in memory.
Indeed, we've got a match! We jumped to the memory location and searched for references to this string in the code.
It's used in the `onClick` Handler of the Deepest class. We can see that the flag is assembled in here.
```javavoid onClick(Deepest this,View p1)
{  boolean bVar1;  View ref;  CharSequence ref_00;  String input;  byte[] pbVar2;  Context pCVar3;  Toast ref_01;  StringBuilder stringbuilder;   ref = this.findViewById(0x7f0a0164);  checkCast(ref,TextView);  ref_00 = ref.getText();  input = ref_00.toString();  bVar1 = this.isPassword(input);  if (bVar1 != false) {    pbVar2 = Base64.decode(input,0);    stringbuilder = new StringBuilder();    stringbuilder.append("CSR{");    input = new String(pbVar2,"UTF-8");    stringbuilder.append(input);    stringbuilder.append("}");    input = stringbuilder.toString();    pCVar3 = this.getApplicationContext();    ref_01 = Toast.makeText(pCVar3,input,0);    ref_01.show();    return;  }  pCVar3 = this.getApplicationContext();  ref_01 = Toast.makeText(pCVar3,"Nope",0);  ref_01.show();  return;}```
So the Flag is `CSR{pwd}`. Where pwd is accepted by `isPassword`. Unfortunately, isPassword is an external function.
So we should look for a native library. There's `assets/deeper/encrypted.dex` and `assets/deepest/encrypted`, we'll have to decrypt them somehow.
Where do we get the password from? When we look at the `MainActivity` class, we'll see that the app starts with a WebView displaying `assets/andsoitbegins.html`.
```javavoid onCreate(MainActivity this,Bundle p1)
{  View ref;  WebSettings ref_00;  WebChromeClient ref_01;  e ref_02;   super.onCreate(p1);  this.setContentView(0x7f0d001e);  ref = this.findViewById(0x7f0a0193);  if (ref != null) {    checkCast(ref,WebView);    WebView.setWebContentsDebuggingEnabled(true);    ref_01 = new WebChromeClient();    ref.setWebChromeClient(ref_01);    ref_00 = ref.getSettings();    ref_00.setJavaScriptEnabled(true);    ref.loadUrl("file:///android_asset/andsoitbegins.html");    ref.addJavascriptInterface(this,"x500");    return;  }  ref_02 = new e("null cannot be cast to non-null typeandroid.webkit.WebView");  throwException(ref_02);  return;}```
We also see the `weMustGoDeeper` Method, which seems to be the entry point for retrieving the flag, as it sets the `pwd` parameter to its argument, but it opens the `Deeper` class instead of `Deepest`, so there's another layer in between. We'll get to that layer later.
A naive `grep -R assets -e weMustGoDeeper` didn't work to find the javascript source, but a `grep -R assets -e x500` did (That's the Javascript object that is exposed by the MainActivity). We find this in `assets/vendor/bootstrap/bootstrap.js`:
```javascript$("#theform").on("submit",function(){var t=$("#txtUser"),e=$("#txtPass"),n=atob("d2VNdXN0R29EZWVwZXI=");return t.val()==atob("TGVvbmFyZG8=")&&e.val()==atob("VGhlQWN0b3JOb3RUaGVOaW5qYVR1cnRsZQ==")?window.x500[n](!0,t.val()+e.val()):window.x500[n](!1,""),!1});```
It looks like there are some things base64 encoded:
`d2VNdXN0R29EZWVwZXI=` = weMustGoDeeper`TGVvbmFyZG8=` = Leonard`VGhlQWN0b3JOb3RUaGVOaW5qYVR1cnRsZQ==` = TheActorNotTheNinjaTurtle
This is the prettified function:
```javascript    $("#theform").on("submit", function() {        var t = $("#txtUser"),            e = $("#txtPass"),            n = "weMustGoDeeper";        return t.val() == "Leonardo" && e.val() == "TheActorNotTheNinjaTurtle" ? window.x500[n](!0, t.val() + e.val()) : window.x500[n](!1, ""), !1```
It's calling `weMustGoDeeper` with `pwd` as `LeonardoTheActorNotTheNinjaTurtle`. Let's see where this password takes us.
# Decrypting the files
Let's resume where we left in our code. We've been seeing that `pwd` is being passed to the `Deeper` class. If we look at the onCreate method, we'll see that it calls `d.n` with an InputStream reading from `assets/deeper/encrypted.dex` and an OutputStream to a temporary location.
We see a lot of crypto code in here:
```javaint n(char[] data,InputStream in,OutputStream out)
{  boolean bVar1;  int iVar2;  SecretKeyFactory ref;  SecretKey ref_00;  byte[] pbVar3;  Cipher cipher;  int iVar4;  byte[] pbVar5;  AlgorithmParameterSpec ref_01;  SecretKey ref_02;  KeySpec key;  String pSVar6;  a ref_03;  c ref_04;  Key pKVar7;  b ref_05;   iVar2 = in.read();  iVar2 = iVar2 * 8;  if (((iVar2 != 0x80) && (iVar2 != 0xc0)) && (iVar2 != 0x100)) {    ref_03 = new(a);    iVar2 = ref_03.a();    throwException(ref_03);    return iVar2;  }  pbVar5 = new byte[0x10];  in.read(pbVar5);  ref = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1");  key = new KeySpec(data,pbVar5,0x8000,iVar2 + 0x40);  ref_00 = ref.generateSecret(key);  pbVar5 = ref_00.getEncoded();  pbVar3 = Arrays.copyOfRange(pbVar5,0,8);  pSVar6 = "AES";  ref_00 = new SecretKey(pbVar3,pSVar6);  pbVar5 = Arrays.copyOfRange(pbVar5,8,pbVar5.length);  ref_02 = new SecretKey(pbVar5,pSVar6);  ref_04 = new c(ref_02,ref_00);  pbVar3 = new byte[8];  in.read(pbVar3);  ref_00 = ref_04.b;  pbVar5 = ref_00.getEncoded();  bVar1 = Arrays.equals(pbVar5,pbVar3);  if (bVar1 == false) {    ref_05 = new(b);    iVar2 = ref_05.b();    throwException(ref_05);    return iVar2;  }  pbVar5 = new byte[0x10];  in.read(pbVar5);  cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");  pKVar7 = ref_04.a;  ref_01 = new AlgorithmParameterSpec(pbVar5);  cipher.init(2,pKVar7,ref_01);  pbVar5 = new byte[0x400];  while (iVar4 = in.read(pbVar5), 0 < iVar4) {    pbVar3 = cipher.update(pbVar5,0,iVar4);    if (pbVar3 != null) {      out.write(pbVar3);    }  }  pbVar5 = cipher.doFinal();  if (pbVar5 != null) {    out.write(pbVar5);  }  return iVar2;}```
We've got to reimplement this in python:
```pythonfrom hashlib import pbkdf2_hmacfrom Crypto.Cipher import AESimport binascii
f = open('assets/deeper/encrypted.dex', 'rb').read()
l = f[0] * 8 + 0x40
pwd = b"LeonardoTheActorNotTheNinjaTurtle"salt = f[1:0x11]
key = pbkdf2_hmac(    hash_name = 'sha1',     password = pwd,    salt = salt,    iterations = 0x8000,    dklen = l // 8)
iv = f[0x19:0x29]
print(len(key))print("KEY: ", binascii.hexlify(key))print("IV: ", binascii.hexlify(iv))
assert (key[:8] == f[0x11:0x19])
cipher = AES.new(key[8:], AES.MODE_CBC, IV=iv)
out = open('assets/deeper/decrypted.dex', 'wb')
f = f[0x29:]
out.write(cipher.decrypt(f))
out.close()```
# Reversing decrypted.dexLoad that file into Ghidra and you'll find a `isPassword` Method.
```javaboolean isPassword(String str)
{  boolean bVar1;  int len;  int last_value;  String slice;  Iterator ref;  Integer pIVar2;  Object ref_00;  BigInteger i;  ArrayList factors;  int iteration;  BigInteger target;  Vault vault;  boolean ret;   ret = false;  vault = new Vault();  factors = new ArrayList();  i = BigInteger.ONE;  iteration = 0;  last_value = 0;  while( true ) {    len = str.length();    if (len + -2 <= iteration) {      target = new BigInteger("591320437755618967257798351702211492893040132184058172662568576456153139621");      bVar1 = target.equals(i);      if ((bVar1 != false) && (last_value = str.length(), last_value== 0x17)) {        ret = true;      }      return ret;    }    slice = str.substring(iteration,iteration + 3);    len = vault.getValue(slice);    if (len <= last_value) break;    ref = factors.iterator();    while (bVar1 = ref.hasNext(), bVar1 != false) {      ref_00 = ref.next();      checkCast(ref_00,Integer);      last_value = ref_00.intValue();      bVar1 = TheDream.FUN__0050033cd0(len,last_value);      if (bVar1 == false) {        return false;      }    }    pIVar2 = Integer.valueOf(len);    factors.add(pIVar2);    target = BigInteger.valueOf((long)len & -0x100000000 |ZEXT48(len));    i = i.multiply(target);    iteration = iteration + 1;    last_value = len;  }  return false;}```
This one's a bit difficult to grasp at first, but what it does is get all substrings of length 3 and multiplies the result of `vault.getValue(substring)` together and this should result in `591320437755618967257798351702211492893040132184058172662568576456153139621`.
So what does `vault.getValue` do?
```java
int getValue(Vault this,String s)
{  boolean bVar1;  Class ref;  Method ref_00;  Object ref_01;  int iVar2;  Object[] ppOVar3;  Class[] ppCVar4;   bVar1 = s.isEmpty();  if (bVar1 == false) {    ref = this.getClass();    ppCVar4 = new Class[0];    ref_00 = ref.getDeclaredMethod(s,ppCVar4);    ppOVar3 = new Object[0];    ref_01 = ref_00.invoke(this,ppOVar3);    checkCast(ref_01,Integer);    iVar2 = ref_01.intValue();  }  else {    iVar2 = 1;  }  return iVar2;}```
It calls the method with the name of the substring and returns that result.
There are a lot of 3 character functions in the binary. Extracting this information by hand would take hours. We'll have to write a script that does so. Using GhidraBridge to connect to our Ghidra instance makes this a pleasant experience.
We can factorize the number and see if we can create the functions return value using the primes.
There's a command line utility that comes in handy to determine the primes `factor`, which is part of coreutils.
```pythonfrom ghidra_bridge import *
b = ghidra_bridge.GhidraBridge(namespace=globals())
primes = [11, 739, 857, 1013, 1879, 1907, 2017, 2503, 3793, 5869, 6043, 6619, 8101, 9857, 11593, 11933, 12241, 12781, 13963, 14033, 15361]
target = 591320437755618967257798351702211492893040132184058172662568576456153139621
addr = []
b.remote_exec("import string,itertools")
for val in b.remote_eval("[ [i.getName(), int(str(getInstructionAt(i.entryPoint).getOpObjects(1)[0]), 16)] for i in currentProgram.getFunctionManager().getFunctions(True) if len(i.getName()) == 3]"):    for x in primes:        if val[1] % x == 0:            val[1] /= x
    if val[1] == 1:        addr.append(val[0])
s = ""
x = [""] * len(addr)
print(addr)```
We're using remote_eval here, because the bridge is quite slow and looping over many functions is just so slow.
The nice thing is we can just decode the first instruction as this loads the return value into a register and they all look the same.
If we run it, we get these functions names:
```python['did', 'dth', 'ebj', 'ems', 'eto', 'het', 'idt', 'ing', 'inn', 'mhf', 'mst', 'nax', 'nin', 'nni', 'ops', 'ote', 'pin', 'psp', 'spi', 'sto', 'tem', 'the', 'top', 'tot', 'ujo']```
We'll have to reassemble them to get our password. We know it's `0x17` in length and they are overlapping by two characters. So we need only 21 of these functions and 4 are not needed.
If we try to combine them we'll find the password is `didthetotemstopspinning`. In general, the combinations can be found as Euler paths in a graph containing the 2 letter overlaps as nodes and the 3 letter names as directed edges. But here guessing that `'the'` is part of an english sentence and knowing the movie was quicker. We can use this to decrypt our last file using the same algorithm we used for encrypted.dex.
# Reversing decrypted
This time it's a native library. One thing to note is that the Java native interface prefixes functions with "Java_" and the package. So instead of looking for a `isPassword` we need to look for `Java_be_dauntless_inception_Deepest_isPassword`.
In this case it's a thin wrapper around the `ip` function.
```culonglong ip(char *param_1)
{  longlong lVar1;  size_t len;  int extracted;  longlong lVar2;  int i;  int local_318;  int index_bits;  byte local_301;  int bits [160];  uint32_t sizes [12];   sizes._40_8_ = 0x60000000d;  sizes._32_8_ = 0x1b0000000c;  sizes._24_8_ = 0x70000000f;  sizes._16_8_ = 0xa00000004;  sizes._8_8_ = 0x1f00000018;  sizes._0_8_ = 0x700000004;  index_bits = 0;  local_318 = 0;  len = strlen(param_1);  if (len == 0x14) {    s2ba(param_1,bits);    i = 0;    while (i < 0xc) {      extracted = b2i(bits,index_bits,sizes[i]);      extracted = rm(i + 1,extracted);      if (extracted == 0) {        local_318 = local_318 + 1;      }      index_bits = index_bits + sizes[i];      i = i + 1;    }    if (local_318 +        ((local_318 / 0x11 + (local_318 >> 0x1f)) -        (int)((longlong)local_318 * 0x78787879 >> 0x3f)) * -0x11 == 0)    {      local_301 = 1;    }    else {      local_301 = 0;    }  }  else {    local_301 = 0;  }  return (ulonglong)local_301;}```
The `s2ba` (string to bit array maybe?) extracts each bit as either a `1` or `0` int into the given array on the stack. The `b2i` rebuilds an int from a specific amount of bits. The size array holds the number of bits to extract each time.
Therefore the input is split into: [4 bits, 7 bits, 24 bits, 31 bits, 4 bits, 10 bits, 15 bits, 7 bits, 12 bits, 27 bits, 13 bits, 6 bits]
The extracted bits are then validated in the `rm` function. This function was basically a giant switch-case over to call the right validation function for the given index.
The validation functions were quite complicated, so we wanted to brute force them. ARM code can be run on other platforms with `qemu-user`. Problem: We haven't got an `aarch64` android setup and we needed to improvise. The Debian repository has an arm cross compilation toolchain in the package `gcc-aarch64-linux-gnu`, which is much easier to install than the android-ndk.
We tried to link the native library into our brute force code, but faced a lot of troubles, because we haven't got the android libraries it needed.
So we just built our own "dynamic" loader for `libdeepest.so`...
# Implementing dynamic linkers, the definitive guide
The core of loading a library is loading the sections (e.g. code, data) from the ELF-file, mapping them into memory with the correct access mode, and adding base addresses to the GOT (global offset table). In our case, `objdump -x libdeepest.so` told us ```[...]Sections:Idx Name          Size      VMA               LMA               File off  Algn[...]  9 .text         00000e0c  0000000000000d90  0000000000000d90  00000d90  2**2                  CONTENTS, ALLOC, LOAD, READONLY, CODE[...] 10 .rodata       00000080  0000000000001b9c  0000000000001b9c  00001b9c  2**2                  CONTENTS, ALLOC, LOAD, READONLY, DATA[...] 17 .got          000000f8  0000000000002f08  0000000000002f08  00002f08  2**3                  CONTENTS, ALLOC, LOAD, DATA```
The `VMA` column contains addresses where the sections are expected at runtime or, for position independent code, an offset from an base address. Here it contains the same values as the `File off`-sets, so we can load the library in one piece. We want to run code from it, and we want to alter the GOT, so it is mapped readable, writable, and executable.
As we already had reversed the first validation function, `z`, which checks if it's argument is 8, we have a first quick test:
```c#include <stdarg.h>#include <sys/mman.h>#include <sys/fcntl.h>#include <sys/stat.h>#include <string.h>#include <assert.h>#include <stdint.h>#include <stdlib.h>#include <stdio.h>#include <err.h>
int main(){	int fd = open("libdeepest.so", O_RDONLY);	if (fd == -1) err(EXIT_FAILURE, "open"); 	struct stat sb;	if (fstat(fd, &sb) == -1) err(EXIT_FAILURE, "stat");
	char *lib = (char*) mmap(NULL, sb.st_size, PROT_EXEC | PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);	if(lib == NULL) err(EXIT_FAILURE, "mmap");	printf("base address: %p\n", lib);
	uint64_t (*z)(unsigned) = (void*)(lib + 0x1388);	printf("z(2) = %lx, z(8) =  %lx\n", z(2), z(8));}```
We compiled with `aarch64-linux-gnu-gcc -Wall -o test test.c`.Now `qemu-aarch64 ./test` outputs `z(2) = 0, z(8) = 1` - yay:)
We don't want to call all validation functions by hand, but use `rm(index, secret)`. So we have to set up the GOT:
```c	const uint64_t got_offset = 0x2f08;	const size_t got_size = 0xf8;	uint64_t got[] = { // values copied from ghidra		0x0,0x0,0x0,0x001054,0x0016cc,0x001388,0x003000,0x001844,0x003008,0x003010,		0x0013e4,0x001948,0x0016f0,0x001b14,0x0017c8,0x003018,0x001250,0x003020,		0x000e3c,0x001484,0x00177c,0x001120,0x00196c,0x003028,0x0017ec,0x003030,		0x0015e0,0x0011ac,0x000e7c,0x003038,0x2d28};
	assert(sizeof(got) == got_size);
	for(int i=0; i<got_size/8; i++){		got[i] += (uint64_t)lib;	}	memcpy(lib + got_offset, got, sizeof(got));```
and now we can call `rm` in a loop:
```c		uint64_t (*rm)(int, unsigned) = (void*)(lib + 0x1250);
	const int bitlengths[] = {4, 7, 24, 31, 4, 10, 15, 7, 12, 27, 13, 6}; // see above.	for(int index = 0; index < sizeof(bitlengths)/sizeof(*bitlengths); index++){		for(unsigned number=0; number < (1u<<bitlengths[index]); number++){			uint64_t res = rm(index+1, number);			if(res) printf("pass[%d] = %u\n", index+1, number);		}	}```
This gives us `pass[1] = 8`, `pass[2] = 22`, and a segfault. To debug this, we use `gdb-multiarch` and attach to qemus gdb-server, which can started by passing `-singlestep -g 1234` to the `qemu-aarch64` command. We find a call to `__vsnprintf_chk` via the GOT, which was not resolved by us. A google search for `android libc __vsnprintf_chk` leads to it's signature and source, so we can supply it to the library:
```cint my_vsnprintf_chk(char* dest, int flags,                               size_t supplied_size, const char* format, va_list va) {	(void) flags;  return vsnprintf(dest, supplied_size, format, va);}```
And before the `memcpy` for the GOT, insert:
```c	const int VSNPRINTF_CHK_INDEX = 23;	assert(got[VSNPRINTF_CHK_INDEX] == (uint64_t)lib + 0x3028); // this was called by the binary	got[VSNPRINTF_CHK_INDEX] = (uint64_t)my_vsnprintf_chk;```
putting all together, we get the output:
```pass[1] = 8pass[2] = 22pass[3] = 13215336pass[4] = 1772505672pass[5] = 11pass[6] = 329pass[7] = 25196pass[8] = 20pass[9] = 1425pass[10] = 110318673pass[11] = 2746pass[12] = 18```
as the 3rd number took quite long and the 4th has more bit's, and it was quite late, we decided to let it run while going to sleep. But then the other results fell out very quick, so we we had to to postpone sleeping to get the flag.
# assembling the flag
We can copy the values into a python script and extend it to reverse the `s2ba` and `b2i` calls:
```pythonlens = [4, 7, 24, 31, 4, 10, 15, 7, 12, 27, 13, 6]answer= [8, 22, 13215336, 1772505672, 11, 329, 25196, 20, 1425,110318673, 2746, 18, ]
# the array as used by s2baa = bytearray(160)
#inverse of b2idef i2b(i, l): return [(i>>j)&1 for j in range(l)][::-1]
done = 0for l,ans in zip(lens, answer):    if done == 0:            a[-l:] = i2b(ans, l)    else:            a[-done-l:-done] = i2b(ans, l)    done += l
# invert s2ban=0for x in a:    n *= 2    n += x
password = n.to_bytes(20, "big")print(password)
# the password is base64 decoded to get the flagimport base64print("CSR{" + base64.b64decode(password).decode() + "}")```
The bit assembly yields `IWZMQEdJblRoM2RFM3Ah`, and by decoding it we find the flag `CSR{!fL@GInTh3dE3p!}`.
Now we finally had time for a short rest.