BugkuCTF LoopAndLoop(阿里CTF)

TOC

  1. 1. 分析
  2. 2. 思路

来自BugkuCTF的一道题，链接：https://ctf.bugku.com/challenges。本站也提供该程序下载：LoopAndLoop.apk。

分析

先安装一下，看出程序要我们输入密码进行验证，然后直接对程序进行解压操作：

unzip LoopAndLoop.apk -d LoopAndLoop

然后用d2j-dex2jar 将 classes.dex 生成 classes-dex2jar.jar。如下所示

ex@Ex:~/test$ cd LoopAndLoop/
ex@Ex:~/test/LoopAndLoop$ ls
AndroidManifest.xml  classes.dex  lib  META-INF  res  resources.arsc
ex@Ex:~/test/LoopAndLoop$ ~/tools/android/dex2jar/
d2j-baksmali.sh                d2j-jar2jasmin.sh
d2j-dex2jar.sh                 d2j-jasmin2jar.sh
d2j-dex2smali.sh               d2j-smali.sh
d2j-dex-recompute-checksum.sh  d2j-std-apk.sh
d2j_invoke.sh                  lib/
d2j-jar2dex.sh                 
ex@Ex:~/test/LoopAndLoop$ ~/tools/android/dex2jar/d2j-dex2jar.sh classes.dex 
dex2jar classes.dex -> ./classes-dex2jar.jar
ex@Ex:~/test/LoopAndLoop$ ls
AndroidManifest.xml  classes-dex2jar.jar  META-INF  resources.arsc
classes.dex          lib                  res

再用jd-gui对classes-dex2jar.jar进行查看MainActivity.java：

package net.bluelotus.tomorrow.easyandroid;

import android.os.Bundle;
import android.support.v7.app.AppCompatActivity;
import android.view.Menu;
import android.view.MenuInflater;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity {
    static {
        System.loadLibrary("lhm");
    }

    public native int chec(int paramInt1, int paramInt2);

    public int check(int paramInt1, int paramInt2) {
        return chec(paramInt1, paramInt2);
    }

    public int check1(int paramInt1, int paramInt2) {
        int j = 1;
        int i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 100) {
            i += paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }

    public int check2(int paramInt1, int paramInt2) {
        if (paramInt2 % 2 == 0) {
            j = 1;
            i = paramInt1;
            paramInt1 = j;
            while (paramInt1 < 1000) {
                i += paramInt1;
                paramInt1 += 1;
            }
            return chec(i, paramInt2);
        }
        int j = 1;
        int i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 1000) {
            i -= paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }

    public int check3(int paramInt1, int paramInt2) {
        int j = 1;
        int i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 10000) {
            i += paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }

    public String messageMe(String paramString) {
        return "LoopOk" + paramString;
    }

    protected void onCreate(Bundle paramBundle) {
        super.onCreate(paramBundle);
        setContentView(2130968600);
        paramBundle = (Button) findViewById(2131492946);
        final TextView localTextView1 = (TextView) findViewById(2131492945);
        final TextView localTextView2 = (TextView) findViewById(2131492947);
        paramBundle.setOnClickListener(new View.OnClickListener() {
            public void onClick(View paramAnonymousView) {
                paramAnonymousView = this.val$ed.getText().toString();
                try {
                    int i = Integer.parseInt(paramAnonymousView);
                    if (MainActivity.this.check(i, 99) == 1835996258) {
                        localTextView1.setText("The flag is:");
                        localTextView2.setText("alictf{" + MainActivity.this.stringFromJNI2(i) + "}");
                        return;
                    }
                } catch (NumberFormatException paramAnonymousView) {
                    localTextView1.setText("Not a Valid Integer number");
                    return;
                }
                localTextView1.setText("Not Right!");
            }
        });
    }

    public boolean onCreateOptionsMenu(Menu paramMenu) {
        getMenuInflater().inflate(2131558400, paramMenu);
        return true;
    }

    public boolean onOptionsItemSelected(MenuItem paramMenuItem) {
        if (paramMenuItem.getItemId() == 2131492961) {
            return true;
        }
        return super.onOptionsItemSelected(paramMenuItem);
    }

    public native String stringFromJNI2(int paramInt);
}

从上面的代码看出程序要求用户输入一个int值，然后在用该值进行check()验证，check函数调用了chec，而chec()来自于liblhm.so，再对该动态库进行反汇编：

int __fastcall Java_net_bluelotus_tomorrow_easyandroid_MainActivity_chec(int a1, int a2, int a3, int a4)
{
  int v4; // r4
  int v5; // r7
  int result; // r0
  int v7; // [sp+Ch] [bp-34h]
  int v8; // [sp+10h] [bp-30h]
  int v9; // [sp+14h] [bp-2Ch]
  int v10; // [sp+1Ch] [bp-24h]
  int v11; // [sp+20h] [bp-20h]
  int v12; // [sp+24h] [bp-1Ch]

  v9 = a2;
  v8 = a4;
  v4 = a1;
  v7 = a3;
  v5 = (*(int (**)(void))(*(_DWORD *)a1 + 24))();
  v10 = _JNIEnv::GetMethodID(v4, v5, "check1", "(II)I");
  v11 = _JNIEnv::GetMethodID(v4, v5, "check2", "(II)I");
  v12 = _JNIEnv::GetMethodID(v4, v5, "check3", "(II)I");
  if ( v8 - 1 <= 0 )
    result = v7;
  else
    result = _JNIEnv::CallIntMethod(v4, v9, *(&v10 + 2 * v8 % 3), v7, v8 - 1);
  return result;
}

思路

到这里就已经很简单了，仅需对该程序进行爆破就好，先说说我刚开始踩的一个坑，一开始我为了移植方便，直接用Java写的爆破程序，代码如下：

bruteforce.java

public class bruteforce {
    public static void main(String args[]) {
        System.out.println("start");
        for (int i = 0; i < 0x7fffffff; i++) {
            if(i % 0x1000000 == 0){
                System.out.println("Now i is " + i);
            }
            System.out.println("Now i is " + i);
            if (check(i, 99) == 1835996258) {
                System.out.println("Succeed, the value is " + i);
                System.exit(0);
            }
        }
    }

    public static int check(int paramInt1, int paramInt2) {
        return chec(paramInt1, paramInt2);
    }

    public static int chec(int paramInt1, int paramInt2) {
        int result = 0;
        if (paramInt2 - 1 <= 0) {
            return paramInt1;
        } else {
            int temp = paramInt2 - 1;
            switch (paramInt2 * 2 % 3) {
            case 0:
                result = check1(paramInt1, temp);
                break;
            case 1:
                result = check2(paramInt1, temp);
                break;
            case 2:
                result = check3(paramInt1, temp);
                break;

            default:
                System.err.println("Error");
                break;
            }
        }
        return result;
    }

    public static int check1(int paramInt1, int paramInt2) {
        int j = 1;
        int i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 100) {
            i += paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }

    public int check2(int paramInt1, int paramInt2) {
        // 这里有问题，所以进行了更改，可能是jd-gui的问题
        int j = 1;
        int i = paramInt1;
        if (paramInt2 % 2 == 0) {
            j = 1;
            i = paramInt1;
            paramInt1 = j;
            while (paramInt1 < 1000) {
                i += paramInt1;
                paramInt1 += 1;
            }
            return chec(i, paramInt2);
        }
        j = 1;
        i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 1000) {
            i -= paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }

    public static int check3(int paramInt1, int paramInt2) {
        int j = 1;
        int i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 10000) {
            i += paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }
}

但是由于Java的速度不高，而且主要原因是这段代码的时间复杂度本身就非常大，Java不支持代码优化，所以半个小时都没跑完一轮，之后我就用C语言重新写了一遍，并开启了代码优化，正是因为代码优化所以编译出来的程序时间复杂度就缩小了很多（代码优化很重要，不开启的话即使是C语言也快不到哪里去）：

bruteforce.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

time_t global_start;
clock_t global_cpu_start;

int chec(int paramInt1, int paramInt2);

int check1(int paramInt1, int paramInt2)
{
    int j = 1;
    int i = paramInt1;
    paramInt1 = j;
    while (paramInt1 < 100)
    {
        i += paramInt1;
        paramInt1 += 1;
    }
    return chec(i, paramInt2);
}

int check2(int paramInt1, int paramInt2)
{
    int j = 1;
    int i = paramInt1;
    if (paramInt2 % 2 == 0)
    {
        j = 1;
        i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 1000)
        {
            i += paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }
    j = 1;
    i = paramInt1;
    paramInt1 = j;
    while (paramInt1 < 1000)
    {
        i -= paramInt1;
        paramInt1 += 1;
    }
    return chec(i, paramInt2);
}

int check3(int paramInt1, int paramInt2)
{
    int j = 1;
    int i = paramInt1;
    paramInt1 = j;
    while (paramInt1 < 10000)
    {
        i += paramInt1;
        paramInt1 += 1;
    }
    return chec(i, paramInt2);
}

int chec(int paramInt1, int paramInt2)
{
    int result = 0;
    if (paramInt2 - 1 <= 0)
    {
        return paramInt1;
    }
    else
    {
        int temp = paramInt2 - 1;
        switch (paramInt2 * 2 % 3)
        {
        case 0:
            result = check1(paramInt1, temp);
            break;
        case 1:
            result = check2(paramInt1, temp);
            break;
        case 2:
            result = check3(paramInt1, temp);
            break;

        default:
            fprintf(stderr, "Error");
            exit(-1);
            break;
        }
    }
    return result;
}

int check(int paramInt1, int paramInt2)
{
    return chec(paramInt1, paramInt2);
}

int main()
{
    puts("start");
    global_cpu_start = clock();
    global_start = time(NULL);
    for (int i = 0; i < 0x7fffffff; i++)
    {
        if (i % 0x1000000 == 0)
        {
            printf("Now i is %d\n", i);
        }
        if (check(i, 99) == 1835996258)
        {
            printf("Succeed, the value is %d\n", i);
            printf("Time of CPU taken: %lf seconds.\n", 
                (double)(clock() - global_cpu_start) / (double)CLOCKS_PER_SEC);
            printf("Time of process taken: %ld seconds.\n", 
                (time(NULL) - global_start));
            exit(0);
        }
    }
}

我用gcc编译的，编译的时候开启了-O3（最高优化），如果你喜欢用MSVC来编译的话，在用cl编译的时候加上参数 /Ox 即可开启最高优化，结果如下：

ex@Ex:~/test$ gcc -o bruteforce -O3 bruteforce.c
ex@Ex:~/test$ ./bruteforce 
start
Now i is 0
Now i is 16777216
Now i is 33554432
Now i is 50331648
Now i is 67108864
Now i is 83886080
Now i is 100663296
Now i is 117440512
Now i is 134217728
Now i is 150994944
Now i is 167772160
Now i is 184549376
Now i is 201326592
Now i is 218103808
Now i is 234881024
Succeed, the value is 236492408
Time of CPU taken: 40.920522 seconds.
Time of process taken: 41 seconds.

所以密码就是236492408，输入改密码即可得到flag。

为了更加快速的进行的爆破了，我还写了一个多线程版本的，兼容Windows和Linux，还要一件事，具体的线程数还要看看自己的机器，代码如下：

bruteforce_thread.c

#include <stdio.h>
#include <stdlib.h>

#include <time.h>

#ifdef __GNUC__
#include <pthread.h>
#endif

#ifdef _WIN32
#include <windows.h>
#endif

// 设置线程数，具体的数值看个人机器
#define THREAD 2

time_t global_start;
clock_t global_cpu_start;

int chec(int paramInt1, int paramInt2);

int check1(int paramInt1, int paramInt2)
{
    int j = 1;
    int i = paramInt1;
    paramInt1 = j;
    while (paramInt1 < 100)
    {
        i += paramInt1;
        paramInt1 += 1;
    }
    return chec(i, paramInt2);
}

int check2(int paramInt1, int paramInt2)
{
    int j = 1;
    int i = paramInt1;
    if (paramInt2 % 2 == 0)
    {
        j = 1;
        i = paramInt1;
        paramInt1 = j;
        while (paramInt1 < 1000)
        {
            i += paramInt1;
            paramInt1 += 1;
        }
        return chec(i, paramInt2);
    }
    j = 1;
    i = paramInt1;
    paramInt1 = j;
    while (paramInt1 < 1000)
    {
        i -= paramInt1;
        paramInt1 += 1;
    }
    return chec(i, paramInt2);
}

int check3(int paramInt1, int paramInt2)
{
    int j = 1;
    int i = paramInt1;
    paramInt1 = j;
    while (paramInt1 < 10000)
    {
        i += paramInt1;
        paramInt1 += 1;
    }
    return chec(i, paramInt2);
}

int chec(int paramInt1, int paramInt2)
{
    int result = 0;
    if (paramInt2 - 1 <= 0)
    {
        return paramInt1;
    }
    else
    {
        int temp = paramInt2 - 1;
        switch (paramInt2 * 2 % 3)
        {
        case 0:
            result = check1(paramInt1, temp);
            break;
        case 1:
            result = check2(paramInt1, temp);
            break;
        case 2:
            result = check3(paramInt1, temp);
            break;

        default:
            fprintf(stderr, "Error");
            exit(-1);
            break;
        }
    }
    return result;
}

int check(int paramInt1, int paramInt2)
{
    return chec(paramInt1, paramInt2);
}

#ifdef _WIN32
DWORD WINAPI run(LPVOID p)
#else
void run(void *p)
#endif
{
    int i;
    for (i = *(int *)p ; i < 0x7fffffff; i+=THREAD)
    {
        if (i % 0x1000000 == 0)
        {
            printf("Now i is %d\n", i);
        }
        // printf("Now i is %d\n", i);
        if (check(i, 99) == 1835996258)
        {
            printf("Succeed, the value is %d\n", i);
            printf("Time of CPU taken: %lf seconds.\n", 
                (double)(clock() - global_cpu_start) / (double)CLOCKS_PER_SEC);
            printf("Time of process taken: %ld seconds.\n", 
                (time(NULL) - global_start));
            exit(0);
        }
    }
}

int main()
{
    int i, arg[THREAD];
#ifdef __GNUC__
    pthread_t thread[THREAD];
#endif

#ifdef _WIN32
    HANDLE thread[THREAD];
#endif
    puts("start");
    global_cpu_start = clock();
    global_start = time(NULL);

#ifdef __GNUC__
    // 启动线程
    for(i =0 ;i < THREAD; i++)
    {
        arg[i] = i;
        pthread_create(&thread[i], NULL, (void *)&run, (void *)&arg[i]);
    }

    // 等待线程
    for(i = 0;i < THREAD; i++)
    {
        pthread_join(thread[i],NULL);
    }
#endif

#ifdef _WIN32
    // 启动线程
    for(i=0 ;i < THREAD; i++)
    {
        arg[i] = i;
        thread[i] = CreateThread(NULL, 0, run, (void *)&arg[i], 0, NULL);
    }

    // 等待线程
    for(i = 0;i < THREAD; i++)
    {
        WaitForSingleObject(thread[i],INFINITE);
    }
#endif

#ifndef __GNUC__
#ifndef _WIN32
    for (i = 0; i < 0x7fffffff; i++)
    {
        if (i % 0x1000000 == 0)
        {
            printf("Now i is %d\n", i);
        }

        if (check(i, 99) == 1835996258)
        {
            printf("Succeed, the value is %d\n", i);
            printf("Time of CPU taken: %lf seconds.\n", 
                (double)(clock() - global_cpu_start) / (double)CLOCKS_PER_SEC);
            printf("Time of process taken: %ld seconds.\n", 
                (time(NULL) - global_start));
            exit(0);
        }
    }
#endif
#endif
}

结果如下：

ex@Ex:~/test$ gcc -o bruteforce_thread -O3 -pthread bruteforce_thread.c 
ex@Ex:~/test$ ./bruteforce_thread 
start
Now i is 0
Now i is 16777216
Now i is 33554432
Now i is 50331648
Now i is 67108864
Now i is 83886080
Now i is 100663296
Now i is 117440512
Now i is 134217728
Now i is 150994944
Now i is 167772160
Now i is 184549376
Now i is 201326592
Now i is 218103808
Now i is 234881024
Succeed, the value is 236492408
Time of CPU taken: 41.634385 seconds.
Time of process taken: 21 seconds.