HITB GSEC 2017: Prime (Mobile)

Do you know prime?

In this challenge, we are given an apk file. Let’s start off by using JADX to decompile it so that we can perform further examination of the code.

package com.iromise.prime;

import android.os.Bundle;
import android.support.v7.app.AppCompatActivity;
import android.util.Log;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.Toast;

public class MainActivity extends AppCompatActivity {
private static long f14N = ((long) Math.pow(10.0d, 16.0d));

class C01931 implements OnClickListener {
C01931() {
}

public void onClick(View view) {
Toast.makeText(MainActivity.this, "HITB{" + MainActivity.this.CalcNumber(MainActivity.f14N) + "}", 0).show();
}
}

protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView((int) C0194R.layout.activity_main);
Button start = (Button) findViewById(C0194R.id.start);
Log.i("Number", String.valueOf(f14N));
start.setOnClickListener(new C01931());
}

private Boolean isOk(long n) {
if (n == 1) {
return Boolean.FALSE;
}
if (n == 2) {
return Boolean.TRUE;
}
for (long i = 2; i * i < n; i++) {
if (n % i == 0) {
return Boolean.FALSE;
}
}
return Boolean.TRUE;
}

private long CalcNumber(long n) {
long number = 0;
for (long i = 1; i <= n; i++) {
if (isOk(i).booleanValue()) {
number++;
}
}
return number;
}
}


Once we decompile the apk, we are able to find MainActivity.java (above) in com/iromise/prime/. At first glance, there are a number of methods that interest us.

public void onClick(View view) {
Toast.makeText(MainActivity.this, "HITB{" + MainActivity.this.CalcNumber(MainActivity.f14N) + "}", 0).show();
}


First and foremost, we observe that onClick() prints the flag when it is run. It computes the flag by calling CalcNumber with f14N as the parameter. f14N is defined above as Math.pow(10.0d, 16.0d), which is evaluates to $10^{16}$.

private long CalcNumber(long n) {
long number = 0;
for (long i = 1; i <= n; i++) {
if (isOk(i).booleanValue()) {
number++;
}
}
return number;
}


The function CalcNumber() with f14N passed in, loops over the range $1$ to $10^{16}$ and maintains a count of integers (number) in the aforementioned range that fulfils the condition imposed by isOk().

private Boolean isOk(long n) {
if (n == 1) {
return Boolean.FALSE;
}
if (n == 2) {
return Boolean.TRUE;
}
for (long i = 2; i * i < n; i++) {
if (n % i == 0) {
return Boolean.FALSE;
}
}
return Boolean.TRUE;
}


At first glance, the function isOk() seems to be checking if a number is prime. However, one little detail that we need to pay attention to is the use of < instead of <= in the terminating condition of the for loop. Because of this nuance, it is accepting both prime numbers and squares of prime numbers. Let’s illustrate this with an example:

consider $n = 26$,

If we use <= in the terminating condition,

for (long i = 2; i * i <= n; i++) {
if (n % i == 0) {
return Boolean.FALSE;
}
}

/*
2, 3, 5, 7, 11, 13, 17, 19, 23 would pass as they are all primes.
*/


If we omit the < as per this challege,

for (long i = 2; i * i < n; i++) {
if (n % i == 0) {
return Boolean.FALSE;
}
}

/*
2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25 would pass.

4, 9, 25 also passes because they are squares of prime numbers:

2 * 2 = 4
3 * 3 = 9
5 * 5 = 25
*/


Given that $\pi(n)$ evaluates to the number of primes <= $n$, the number that CalcNumber(n) evaluates to is effectively $\pi(10^{16}) + \pi(10^{8})$. As seen above, these values are readily available on wikipedia. As such, we can sum the required values to get our flag.

Flag: HITB{279238346795380}