Overcome insurmountable obstacles then find the secret combination to get the flag.
The attached ZIP contains an APK (875.9KB)
To pass the first & second levels you need to jump from the ground to the top floor, if you miss you fall back to the start, pretty exhausting, would be easier if we could jump higher.
We searched for the string “GROUND” and found the enum @ com.google.ctf.game.f$a#a, followed the xref to com.google.ctf.game#a
private void a(c _c) {
_c.c += 0.9f;
_c.a.e -= _c.c;
int v0 = (((int)(_c.a.e + _c.b.e))) / this.a.f;
int v1 = (((int)(_c.a.e + _c.b.e / 2f))) / this.a.f;
int v2 = (((int)_c.a.e)) / this.a.f;
int v4 = (((int)_c.a.d)) / this.a.e;
int v3 = (((int)(_c.a.d + _c.b.d / 2f))) / this.a.e;
int v5 = (((int)(_c.a.d + _c.b.d))) / this.a.e;
int v6 = this.a.c[v2][v4] == _enum._ground && this.a.c[v2][v3] == _enum._ground || this.a.c[v2][v5] == _enum._ground && this.a.c[v2][v3] == _enum._ground ? 1 : 0;
int v3_1 = this.a.c[v0][v4] == _enum._ground && this.a.c[v0][v3] == _enum._ground || this.a.c[v0][v5] == _enum._ground && this.a.c[v0][v3] == _enum._ground ? 1 : 0;
int v4_1 = this.a.c[v1][v4] == _enum._ground ? 1 : 0;
int v1_1 = this.a.c[v1][v5] == _enum._ground ? 1 : 0;
if(v3_1 != 0) {
_c.a.e = (float)(this.a.f * (v0 - 1));
_c.c = 0f;
}
else if(v6 != 0) {
_c.a.e = (float)(this.a.f * (v2 + 1));
_c.c = 0f;
_c.f = false;
}
...We used Frida to jump higher
// $ frida -Uf com.google.ctf.game --no-pause --enable-jit -e
Java.perform(() => {
Java.use('com.google.ctf.game.g').a.overload('com.google.ctf.game.c').implementation = function(_c) {
Java.cast(_c, Java.use('com.google.ctf.game.c')).c.value -= 0.7; // original value = 0.5
this.a(_c);
}
})
To pass the last level (3) we need to put in order 15 eggs inside optional 16 pairs (total 32) of boxes,
afterwards we need to get to the highest floor and click on the computer icon which will calculate if the eggs in the right order.
“Close, but no cigar.” is the popup you will get if the eggs are not in order.
The computer icon invokes the native method from the class com.google.ctf.game.Checker#nativeCheck and pass a byte array which represents the eggs positions.
If this function returns true – it passes it on further to check the SHA256 of the key – if it equals a specific hardcoded value it goes on to decrypt the cipher text (again hardcoded) using the key and some hardcoded IV.
This really looked suspicious to us – since there is really no need to run a check twice on a key… just try to decrypt it and validate the result if you must… so it must be a clue 🙂
The APK contains the native library called rary – so library.so (cudos for the pun :))
We loaded it into IDA and saw that it has 3 main function.
nativeCheck
int __fastcall Java_com_google_ctf_game_Checker_nativeCheck(JNINativeInterface **a1, int a2, int a3)
{
JNINativeInterface **v3; // r5
int v4; // r4
int v6; // [sp+0h] [bp-30h]
v3 = a1;
v4 = a3;
if ( ((int (__fastcall *)(JNINativeInterface **, int))(*a1)->GetArrayLength)(a1, a3) != 32 )
return 0;
qmemcpy(&v6, (const void *)((int (__fastcall *)(JNINativeInterface **, int, _DWORD))(*v3)->GetByteArrayElements)(v3, v4, 0), 0x20u);
return C((char *)&v6);
}C function:
int __fastcall C(char *a1)
{
int i; // r1
char v2; // r4
char v4[15]; // [sp+4h] [bp-1Ch]
unsigned __int8 v5; // [sp+13h] [bp-Dh]
for ( i = 0; i != 16; ++i )
v4[i] = a1[2 * i] + a1[2 * i + 1];
v2 = 0;
p = 0;
c = 1;
M(v4, 16);
if ( v5 < 0x10u )
v2 = 1;
return (c != 0) & (unsigned __int8)v2;
}M function:
char *v2; // r11
unsigned int v3; // r10
signed int v4; // r9
int v5; // r6
int v6; // r3
int v7; // r4
int v8; // r5
signed int v9; // r8
unsigned int v10; // r2
unsigned int v11; // r1
char v12; // r1
int v14; // [sp+14h] [bp-34h]
char v15[16]; // [sp+18h] [bp-30h]
int v16; // [sp+28h] [bp-20h]
v2 = a1;
v3 = a2;
if ( a2 >= 2 )
{
v4 = (unsigned int)a2 >> 1;
M(a1, (unsigned int)a2 >> 1);
if ( c )
{
v5 = (int)&v2[v3 >> 1];
M(&v2[v3 >> 1], v3 - (v3 >> 1));
if ( c )
{
v6 = v3 - (v3 >> 1);
v14 = v3 - (v3 >> 1);
if ( (int)(v3 - (v3 >> 1)) >= 1 )
{
v7 = 0;
v8 = 0;
v9 = 0;
while ( 1 )
{
v10 = *(unsigned __int8 *)(v5 + v8);
v11 = (unsigned __int8)v2[v9];
if ( v11 >= v10 )
{
if ( v11 <= v10 || d[p] )
{
LABEL_21:
c = 0;
return _stack_chk_guard - v16;
}
++p;
v12 = *(_BYTE *)(v5 + v8++);
}
else
{
if ( d[p] != 1 )
goto LABEL_21;
v6 = v14;
++p;
v12 = v2[v9++];
}
v15[v7++] = v12;
if ( v9 >= v4 || v8 >= v6 )
goto LABEL_16;
}
}
v9 = 0;
v8 = 0;
v7 = 0;
LABEL_16:
if ( v4 > v9 )
{
qmemcpy(&v15[v7], &v2[v9], v4 - v9);
v6 = v14;
v7 = v7 + v4 - v9;
}
if ( v8 < v6 )
qmemcpy(&v15[v7], &v2[v8 + v4], v3 - v8 - v4);
qmemcpy(v2, v15, v3);
}
}
}
return _stack_chk_guard - v16;As you can see – it ain’t pretty…
It looks like the C function takes the sum of each two cells (eggs) and creates a new array of length 16.
This array is passed to the M function.
M is the main logic which does some wierd annoying recursive algorithm which looks like merge sort – but it uses an external array d[p] to decide on things – this was hardcoded.
Rather than understand this function we loaded it into KLEE and let it figure it out for us.
It quickly gave us one solution. This was a good sign 🙂
So now all we had to do was take the 16 values and expand them to 32 (there are not too many and we can validate using the SHA256 on the key).
We now had the correct egg combination to enter in the game.
code we passed to KLEE
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/stat.h>
#include <fcntl.h>
#ifdef KLEE
#include <klee/klee.h>
#endif
int g_stop_flag = 1;
/* we need to figure this value out...*/
char g_aux_arr[45] = {0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0};
int g_aux_index = 0;
int test_func(char *pairs_sum_arr, int size)
{
signed int half_arr; // r9
char* mid_ptr; // r6
int starting_half_size; // r3
int v7; // r4
int i; // r5
signed int j; // r8
char val_i; // r2
char v11; // r1
char v12; // r1
int current_half_size; // [sp+14h] [bp-34h]
char v15[16]; // [sp+18h] [bp-30h]
int v16; // [sp+28h] [bp-20h]
if ( size >= 2 )
{
printf("testing with size: %d\n", size);
half_arr = (unsigned int)size >> 1;
test_func(pairs_sum_arr, (unsigned int)size >> 1);
if ( g_stop_flag )
{
mid_ptr = &pairs_sum_arr[(unsigned int)size >> 1];
test_func(&pairs_sum_arr[(unsigned int)size >> 1], size - ((unsigned int)size >> 1));
if ( g_stop_flag )
{
starting_half_size = size - ((unsigned int)size >> 1);
current_half_size = size - ((unsigned int)size >> 1);
if ( (int)(size - ((unsigned int)size >> 1)) >= 1 )
{
v7 = 0;
i = 0;
j = 0;
while ( 1 )
{
printf("in while\n");
val_i = *(char *)(mid_ptr + i);
v11 = pairs_sum_arr[j];
if ( v11 >= val_i )
{
printf("v11 >= val_i\n");
if ( v11 <= val_i || g_aux_arr[g_aux_index] )
{
LABEL_21:
printf("got to the exit and g_stop_flag = 0\n");
g_stop_flag = 0;
return g_stop_flag;
}
++g_aux_index;
v12 = *(char *)(mid_ptr + i++);
}
else
{
printf("got to the else case\n");
if ( g_aux_arr[g_aux_index] != 1 ){
goto LABEL_21;
}
starting_half_size = current_half_size;
++g_aux_index;
v12 = pairs_sum_arr[j++];
}
printf("assing to v15\n");
v15[v7++] = v12;
if ( j >= half_arr || i >= starting_half_size )
goto LABEL_16;
}
}
j = 0;
i = 0;
v7 = 0;
LABEL_16:
if ( half_arr > j )
{
printf("got to memcpy1\n");
memcpy(&v15[v7], &pairs_sum_arr[j], half_arr - j);
starting_half_size = current_half_size;
v7 = v7 + half_arr - j;
}
if ( i < starting_half_size ) {
printf("got to memcpy2\n");
memcpy(&v15[v7], &pairs_sum_arr[i + half_arr], size - i - half_arr);
}
printf("got to memcpy3\n");
memcpy(pairs_sum_arr, v15, size);
}
}
}
return g_stop_flag;
}
int main(int argc, char *argv[])
{
// char in_array[16] = {1, 2, 3, 4, 5, 6 ,7 ,8 ,9 ,10 ,11, 12, 13, 14, 15, 0};
char in_array[16] = {0};
int i;
int res;
char cur = 0;
#ifdef KLEE
klee_make_symbolic(in_array, sizeof(in_array), "in_array");
for (i = 0; i < sizeof(in_array); ++i) {
klee_assume((in_array[i] <= 0x20) && (in_array[i] >= 0));
}
#else
printf("opening %s\n", argv[1]);
int fd = open(argv[1], O_RDONLY);
if (fd < 0) {
printf("open error\n");
return 2;
}
read(fd, in_array, sizeof(in_array));
close(fd);
for (int j =0; j < sizeof(in_array); j++) {
printf("%02x ", in_array[j]);
}
printf("\n");
#endif
if (test_func(in_array, 16) != 1) {
return 0;
}
res = in_array[sizeof(in_array)-1] < 0x10;
if (res) {
printf("good sample\n");
}
return res;
}python script we used to expand the 16 bytes array into the 32 eggs array
import struct
import hashlib
pair_sum = [9, 8, 7, 2, 11, 15, 13, 10, 6, 5, 14, 4, 3, 0, 12, 1]
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
def make_keys():
for z in product(*[((x, 0), (0, x)) for x in pair_sum]):
yield z
l = [46, 50, 92, -111, -55, 20, 120, -77, 92, 46, 12, -74, 91, 120, 81, -58, -6, -104, -123, 90, 119, -61, -65, -45, -16, 8, 64, -68, -103, -84, -30, 107]
expected_hash = struct.pack("b" * len(l), *l)
for z in make_keys():
m = hashlib.sha256()
key = struct.pack("B" * 32, *sum(z, tuple()))
m.update(key)
if m.digest() == expected_hash:
print "found key:", key.encode('hex')
print zscript to place the eggs
Java.perform(() => {
Java.choose('com.google.ctf.game.f', {
onMatch: f => {
[9, 0, 0, 8, 0, 7, 2, 0, 0, 11, 0, 15, 13, 0, 10, 0, 6, 0, 0, 5, 14, 0, 0, 4, 0, 3, 0, 0, 12, 0, 1, 0
].forEach((egg, box) => f.a(box, egg));
},
onComplete: () => {}
})
})
This revealed a new level with the flag