ddctf-Android第一题-RSA

前言

好久没做ctf题了，arm指令都快忘光了…..
提起去年太菜没做出的题再分析下。

ida addmap时可以直接把系统库函数全部取出来，放到一个本地文件夹中这样ida即可加载对应的so用于分析。–全部提出system/lib指定目录即可
现在的加载so，不落地手动加载是绝杀…….必须读读linker
debugger里的watch view可以查看任意形式的目标时时信息，支持c变量表达式。十分好用比如：(char*)R0

题解

这题的垃圾代码比较多，这里看下快速的分析方式。

首先运行一下：

输入flag判断正误

直接拖到jeb里看下

<?xml version="1.0" encoding="utf-8"?>
<manifest package="com.didictf.guesskey2018one" platformBuildVersionCode="24" platformBuildVersionName="7.0" xmlns:android="http://schemas.android.com/apk/res/android">
    <uses-sdk android:minSdkVersion="13" android:targetSdkVersion="24" />
    <application android:allowBackup="true" android:icon="@mipmap/ic_launcher" android:label="@string/app_name" android:supportsRtl="true" android:theme="@style/AppTheme">
        <activity android:name="com.didictf.guesskey2018one.MainActivity">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>
</manifest>

没什么特别的声明，就一个Activity。

看下他的类与layout

package com.didictf.guesskey2018one;
import android.os.Bundle;
import android.support.v7.a.u;
import android.view.View;
import android.widget.TextView;
public class MainActivity extends u {
    private TextView m;
    private TextView n;
    static {
        System.loadLibrary("hello-libs");
    }
    public MainActivity() {
        super();
    }
    public void onClickTest(View arg3) {
        this.n.setText("Empty Input");
        if(this.stringFromJNI(this.m.getText().toString())) {
            this.n.setText("Correct");
        }
        else {
            this.n.setText("Wrong");
        }
    }
    protected void onCreate(Bundle arg2) {
        super.onCreate(arg2);
        this.setContentView(2130968602);
        this.m = this.findViewById(2131427413);
        this.n = this.findViewById(2131427415);
    }
    public native boolean stringFromJNI(String arg1) {
    }
}

在public中：

1	<public id="0x7f04001a" name="activity_main" type="layout" />

activity_main:

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout android:layout_height="fill_parent" android:layout_width="fill_parent" android:paddingBottom="@dimen/activity_vertical_margin" android:paddingLeft="@dimen/activity_horizontal_margin" android:paddingRight="@dimen/activity_horizontal_margin" android:paddingTop="@dimen/activity_vertical_margin" xmlns:android="http://schemas.android.com/apk/res/android">
    <LinearLayout android:layout_centerInParent="true" android:layout_height="wrap_content" android:layout_width="wrap_content" android:orientation="vertical">
        <TextView android:id="@id/flag_prompt" android:layout_gravity="center" android:layout_height="wrap_content" android:layout_width="wrap_content" android:text="Guess Key" android:textAppearance="?android:textAppearanceLarge" />
        <EditText android:ems="10" android:id="@id/flag_entry" android:inputType="textPassword" android:layout_gravity="center" android:layout_height="wrap_content" android:layout_width="wrap_content" />
        <Button android:id="@id/button" android:layout_gravity="center_horizontal" android:layout_height="wrap_content" android:layout_width="wrap_content" android:onClick="onClickTest" android:text="Test" />
        <TextView android:id="@id/flag_result" android:layout_gravity="center" android:layout_height="wrap_content" android:layout_width="wrap_content" android:text="Empty Result" android:textAppearance="?android:textAppearanceLarge" />
    </LinearLayout>
</RelativeLayout>

可见为基本的读入字串，在libhello-libs.so中判断结果返回，返回1为正确

接下来ida分析libhello-libs.so：
该so为32位的，init_array段有内容但不影响，无jni_onload，导出部分也没有下坑。找到导出函数：

int __fastcall Java_com_didictf_guesskey2018one_MainActivity_stringFromJNI(int a1)
{
  int v1; // r5
  int v2; // r4
  int v3; // r0
  int v4; // r0
  int v5; // r4
  int v7; // [sp+4h] [bp-28h]
  char v8; // [sp+8h] [bp-24h]
  int v9; // [sp+Ch] [bp-20h]
  int v10; // [sp+10h] [bp-1Ch]
  char v11; // [sp+14h] [bp-18h]
  char v12; // [sp+18h] [bp-14h]
  v1 = 0;
  v2 = (*(int (**)(void))(*(_DWORD *)a1 + 676))(); //GetStringUTFChars
  j_GetTicks();
  do
    v10 = j_gpower(v1++);
  while ( v1 != 32 );
  j_GetTicks();
  sub_D6EC3364(&v9, v2, &v8);
  v3 = sub_D6EC2A08(&v7, &v9);
  j___aeabi_wind_cpp_prj(v3);
  v5 = v4;
  sub_D6EC28E4(v7 - 12, &v12);
  sub_D6EC28E4(v9 - 12, &v11);
  return v5;
}

分析：

GetStringUTFChars将utf编码的java字串拷贝到本地c的asll实现
v1,v10都没用上可知为垃圾代码
sub_D6EC3364为将v2的字串封装结构体为v9,根据里面库函数的字串应该是string的构造
sub_D6EC2A08动态调试结果返回和输入没区别…..
j-aeabi这个函数是关键函数
后面俩个的参数对判断结果v5毫无影响，为垃圾函数

之后来看核心判断：

void __fastcall __aeabi_wind_cpp_prj(int *a1)
{
  int inpit; // r0
  int v2; // r5
  char v3; // r2
  char v4; // ST18_1
  unsigned int length; // r0
  unsigned __int8 *v6; // r1
  int v7; // r7
  unsigned int v8; // r3
  signed int v9; // r5
  unsigned int v10; // r6
  int v11; // r1
  int v12; // r0
  int v13; // r0
  unsigned int v14; // r4
  int v15; // r5
  int v16; // r0
  int v17; // r6
  int v18; // r1
  int v19; // r5
  __int64 v20; // r2
  unsigned int v21; // [sp+4h] [bp-8Ch]
  int v22; // [sp+4h] [bp-8Ch]
  int *v23; // [sp+8h] [bp-88h]
  int v24; // [sp+8h] [bp-88h]
  unsigned __int8 *v25; // [sp+10h] [bp-80h]
  int v26; // [sp+10h] [bp-80h]
  int v27; // [sp+14h] [bp-7Ch]
  int v28; // [sp+18h] [bp-78h]
  int v29; // [sp+1Ch] [bp-74h]
  int v30; // [sp+20h] [bp-70h]
  int *v31; // [sp+24h] [bp-6Ch]
  int *v32; // [sp+28h] [bp-68h]
  int v33; // [sp+30h] [bp-60h]
  int v34; // [sp+34h] [bp-5Ch]
  int v35; // [sp+38h] [bp-58h]
  void *v36; // [sp+3Ch] [bp-54h]
  __int16 v37; // [sp+42h] [bp-4Eh]
  char v38; // [sp+48h] [bp-48h]
  char v39[10]; // [sp+4Ch] [bp-44h]
  char v40; // [sp+56h] [bp-3Ah]
  v23 = a1;
  inpit = *a1;
  if ( *(_DWORD *)(inpit - 12) == 43 )
  {
    v2 = 0;
    do
    {
      v3 = *((_BYTE *)&unk_4DEF3 - v2);
      if ( *(_DWORD *)(inpit - 4) >= 0 )
      {
        v4 = *((_BYTE *)&unk_4DEF3 - v2);
        sub_2FF8C(v23);
        v3 = v4;
        inpit = *v23;
      }
      v39[-v2] = *(_BYTE *)(inpit - v2) ^ v3;
      --v2;
    }
    while ( v2 != -43 );
//每一位^一个数列，生成与输入同大小的一个数列  
//输入应该是43位的
/*
5A 44 5C 54 4D  5D 52 5D 53 01 08 02 5A
50 0C 5B 0C 07 50 58 43  42 4B 55 4C 04 54 01 0D    
4A 57 42 09 57 00 47 0B  00 4D 59 42 5C 5F 00 
*/
//异或后产生v6字串
	
    length = *(_DWORD *)(inpit - 12);
    v6 = (unsigned __int8 *)&v37;
    v7 = 0;
    v8 = 0;
    v9 = 0;
LABEL_7:
    v21 = v8;
    v25 = v6;
    while ( v9 < 1 || v8 >= length || v6[10] == *v6 )
    {
      ++v8;
      ++v6;
      if ( ++v7 >= 10 )
      {
        v8 = v21 + 10;
        v6 = v25 + 10;
        ++v9;
        v7 = 0;
        if ( v9 < 5 )
          goto LABEL_7;
	// 保证v6[i+10]==v6[i]    v8表示v6的位置，当v6超过length时由v8过while，后面判断屏蔽
		
        v10 = 0;
        v40 = 0;
	//v6[10]=0
	
        sub_31364(&v28, v39, &v34);
        sub_2F50C(v23, &v28);
        sub_308E4(v28 - 12, &v36);
        sub_30A08(&v35, v23);
        j_str2vec(&v36, &v35);
        sub_308E4(v35 - 12, &v28);
        v24 = j_atoll(*v23);
  //取v6代表的long long整形
		
        v26 = v11;
        sub_31364(&v34, "deknmgqipbjthfasolrc", &v28);
        sub_31364(&v33, "jlocpnmbmbhikcjgrla", &v28);
        j___aeabi_memclr4(&v29, 20);
        v31 = &v29;
        v32 = &v29;
        v12 = v34;
        if ( *(_DWORD *)(v34 - 12) )
        {
          do
          {
            if ( *(_DWORD *)(v12 - 4) >= 0 )
            {
              sub_2FF8C(&v34);
              v12 = v34;
            }
            *(_DWORD *)j_std::map<char,int,std::less<char>,std::allocator<std::pair<char const,int>>>::operator[](
                         &v28,
                         v12 + v10) = (signed int)v10 / 2;
            v12 = v34;
            ++v10;
          }
          while ( v10 < *(_DWORD *)(v34 - 12) );
        }
        sub_30A08(&v27, &v33);
        v13 = v33;
        if ( *(_DWORD *)(v33 - 12) )
        {
          v14 = 0;
          do
          {
            if ( *(_DWORD *)(v13 - 4) >= 0 )
            {
              sub_2FF8C(&v33);
              v13 = v33;
            }
            v15 = *(_DWORD *)j_std::map<char,int,std::less<char>,std::allocator<std::pair<char const,int>>>::operator[](
                               &v28,
                               v13 + v14)
                + 48;
            v16 = v27;
            if ( *(_DWORD *)(v27 - 4) >= 0 )
            {
              sub_2FF8C(&v27);
              v16 = v27;
            }
            *(_BYTE *)(v16 + v14) = v15;
            v13 = v33;
            ++v14;
          }
          while ( v14 < *(_DWORD *)(v33 - 12) );
        }
        v31 = v36;
        v18 = j_atoll(v36);
        v20 = v19;
        ((void (*)(void))j_j___aeabi_uldivmod)();
        if ( v21 )
          goto LABEL_47; //余数==0
    v18        v33
//第二次的数  与第一次的数mod
//第二个数最好动调出来  为：0x91F5A65B 51BB6565注意longlong的返回用俩个寄存器R0R1
/*定义：
		__value_in_regs ulldiv_t __aeabi_uldivmod(
		 unsigned long long n, unsigned long long d)
		unsigned signed ll division, remainder,
		{q, r} = n / d [2]
		他的参数是俩个，每个参数为longlong 要占俩个32位的寄存器
		大端和小端都支持，默认是小端模式
		因此R0是低位  R1是高位
		字串是5889412424631952987    
		其16进制表示为51BB656591F5A65B    注意进制转化不能分开位数，应该整体算--因为每位都是*16的几次方-不是10的倍数
2. A pair of (unsigned) long longs is returned in {{r0, r1}, {r2, r3}}, the quotient in {r0, r1}, and the remainder in
{r2, r3}. The description above is written using ARM-specific function prototype notation, though no prototype
need be read by any compiler. (In the table above, think of __value_in_regs as a structured comment).
*/
		                          被除数           除数低高
        v22 = j_j___aeabi_uldivmod(v18, v20, v33, v35);
        v2 = 1;
		//此时可过
        v24 = 1;
        if ( v33 >= 2 )
          v24 = 0;执行
        v25 = 1;
        if ( (v35 & 0x80000000) == 0 )
          v25 = 0;
        if ( v35 )
          v24 = v25;
        if ( v24 )
          goto LABEL_47; 不可执行
		//  除数小于商    
        v26 = 1;
        v27 = v33 >= v22;  
        v28 = 1;
        if ( v27 )
          v28 = 0;
        if ( v35 >= v23 )   //判断高位，高位必须除数小于商
          v26 = 0;
        if ( v35 != v23 )    //高位不等时直接按高位的判断 ，相等时按之前低位的判断
          v28 = v26;
        if ( !v28 )   v28要=1    //结果为除数必须小于商
LABEL_47:
          v2 = 0;
        sub_308E4(v31 - 12, &v47);
        j_std::_Rb_tree<char,std::pair<char const,int>,std::_Select1st<std::pair<char const,int>>,std::less<char>,std::allocator<std::pair<char const,int>>>::_M_erase(
          &v37,
          v39);
        sub_308E4(v42 - 12, &v37);
        sub_308E4(v43 - 12, &v37);
        if ( v45 )
          return j_operator delete();
        break;
      }
    }
  }
  result = _stack_chk_guard - v50;
  if ( _stack_chk_guard == v50 )
    result = v2;
  return result;
}

基本流程就是：
对输入异或一个串，判断结果是10个一循环的，取前10位化为longlong，取一个大整数除它，要求余数==0，除数小于商。

值得说说的就是动调看汇编代码或者汇编对照idaF5看比只看F5效率高很多…..F5出来的很难看出在干什么….
把arm指令记熟了应该静态主读汇编以F5为辅也能很快分析出来。
始终确保某寄存器或某地址上的目标数据内容，知道该数据的传递在算法的一部分中可以快速理清思路。
arm大小端存储都可以，默认为小端，longlong系列的指令都是用俩个寄存器传递，R0低32位，R1高32位。遇到不懂的指令去arm手册查。
在F5的结果中参数为R0-R1放，对应的是左-右的参。且将longlong类型识别为俩个参数了

最后写出脚本：

#include <stdio.h>
int main(void)
{
	long long a=5889412424631952987;
	/*long long b=2;
	while(1)
	{
		if(a%b==0)
		{
			printf("%lld\n",b);
		}
		b++;
		if(b==a)
		{
			break;
		}
	}
	*/
	//1499419583
	char* b="14994195831499419583149941958314994195831499419583";
	char c[]={0x5A,0x44,0x5C,0x54,0x4D,0x5D,0x52,0x5D,0x53,0x01,0x08,0x02,0x5A,0x50,0x0C,0x5B,0x0C,0x07,0x50,0x58,0x43,0x42,0x4B,0x55,0x4C,0x04,0x54,0x01,0x0D,0x4A,0x57,0x42,0x09,0x57,0x00,0x47,0x0B,0x00,0x4D,0x59,0x42,0x5C,0x5F,0x00};	
	int i=0;
	for(i=0;i<43;i++)
	{
		c[i]=b[i]^c[i];
	}
	c[i]=0;
	printf("%s",c);	
}

后记

因为arm架构是基于寄存器的，注意一个反编译函数中许多变量都是寄存器。在局部内是有效的。由于idaF5出的arm代码还不是非常准确，最好是用汇编代码对照着读，c保证大体位置不走丢，汇编保证细节准确性和算法理解。动态调试最好能够配合，可以关注输入与返回等的位置与变动情况。
对于arm指令来说…..直接读汇编辅助读F5比只读F5好太多…….F5出来的简直坑…….
顺便arm指令需要背下来。