安卓逆向学习笔记-2:Timer Writeup

在模拟器中安装好apk后效果如下:

程序是从200000秒开始倒数。

放到jeb中分析包内容,在包中找到MainActivity类并用Q键反编译:

在MainActivity类的构造方法中将当前时间从毫秒单位化成秒单位,加上200000后存进beg。由于构造函数在一个类被声明实例时就会立即执行,所以beg会在运行主程序时立刻被覆盖上当前数据。

接着分析OnCreat()方法:

每秒运行一次run方法,获取当前时间存入now,若 beg - now <= 0 则从本地提取相应flag输出。由于beg = 程序开始时间 + 200000now = 当前时间,所以beg - now == 200000 - 过去了多少秒,相当于在不断倒数,数完200000秒后就输出flag。

注意到flag是根据k的值来找到相应字符串并输出。而在倒数完200000秒之前则会将beg - now作为参数传给is2()方法进行判断并返回一个boolean值,若为true则k += 100,否则k -= 1,此时便对k的值进行了更改。

接下来的思路就很清晰了:

  1. 修改run()方法的进入输出flag代码段的if条件判断,使其不需要200000秒即可输出flag;
  2. 根据is2()方法写一个脚本跑出倒数200000秒后k的值应该是多少;
  3. 修改run()方法中的k的值,使其为倒数200000秒后k的值;
  4. 重打包apk并在模拟器中安装运行。

在AndroidKiller中搜索run()方法在smali中什么位置:

发现在MainActivity$1.smali中。

通过apktool d BadBoyREDTimer.apk命令解包apk,找到MainActivity$1.smali:

修改的第一处是判断语句:

if-gtz的大于跳转改成if-lez的小于等于跳转,相当于把java程序的beg - now <= 0改成beg - now > 0,在第一次记录时间时就可以进入flag输出段。

根据脚本跑出k应有的值,脚本如下:

def check(n):
  ret = True
  if n > 3:
    if n % 2 != 0 and n % 3 != 0:
      tmp = 5
      while True:
        if tmp * tmp <= n:
          if n % tmp != 0 and n % (tmp + 2) != 0:
            tmp += 6
            continue
          return False
        else:
          return ret
      return False
    ret = False
  elif n <= 1:
    ret = False
  return ret

ans = 0
i = 200000	
while i > 0:
  if check(i):
    ans += 100
  else:
    ans -= 1
  i -= 1
print ans

跑出k的值应为1616384。

接下来修改第二处:

根据smali中函数参数的调用可以发现,k的值实际上就是引用了v3的值,所以将v3更改为常量1616384即可。

在v3被函数引用之前加上一行const v3, 1616384即可更改k为正确的值。

修改完毕后通过apktool b BadBoyREDTimer即可重打包apk,新生成的apk保存在dist目录下。

进入BadBoyREDTimer.apk所在目录,通过jarsigner -verbose -keystore red.keystore -signedjar BadBoyREDTimer_signed.apk BadBoyREDTimer.apk red.keystore命令将apk包进行签名。

在模拟器中安装签名好的新apk,运行就可以看到flag:

安卓逆向学习笔记-1:flag Writeup

在模拟器中安装.apk后,提示输入flag:

在jadx中打开后找到onClick()事件:

点击检查FLAG后会调用attempLogin()方法,找到attemptLogin():

用auth()方法判断输入是否是正确flag,分析auth()方法:

把input即输入的字符串用password1对其进行DES加密,并从flag.bin中读取文件存入v0。在assets中找到flag.bin:

从.apk压缩包中解压出来。回头看加密方式:

用于加密的password在MainActivity中被如下定义:

public native String stringFromJNI();

native代表被存储在了动态链接库中,在lib中可以找到每种处理器下的.so文件:

选一种解压出来拖进IDA分析。

在函数导出表中通过ctrl + F5搜索主程序中的native函数:

双击进入函数,发现确实是我们要找的stringFromJNI():

分析可疑函数sub_8E60():

根据”_S_create”字样猜测函数功能是创建一个string将”6470DBE9″存入v6中。

创建完后string的内容作为字符数组将收地址传递给v2,并通过NewStringUTF()创建java字符串v4,最后将v4作为result返回,即返回password。

故”6470DBE9″就是DES加密所用的密钥。

打开flag.bin后发现文件乱码:

写出python脚本跑出明文:

倒叙输进去:

Flag get√

CTF中的SMC

SMC

自修改代码( self-modifying code, SMC ) 意思是自我修改的代码,使程序在运行时自我修改。

百度百科

SMC与壳类似,在可执行文件被运行前,关键核心代码是被加密的,无法被静态分析。所以为了解决带有SMC的逆向题,通常做法是:

1.动态调试解密被加密代码段后,从内存中dump下来,并通过反编译软件静态分析;

2.在动态调试的过程中解密核心代码后,直接动态分析。

CTF中的SMC实例

首先在OD中文搜索引擎中找到了“Try Again”:

双击“Try Again”进入主程序,向上找到段头,并在scanf处下断:

scanf下方是一处记录字符串长度的循环,并把字符串长度和0x1C相比较,不相等则打印“Try Again”,所以flag的字符串为0x1C即28。

输入28个字符后接着向下单步分析:

这里在跳转过来后将最后一位与0x7D即字符’}’比较,不是则退出程序。

这里将解密后的地址存进eax,并通过call eax来运行到解密后的代码。

到这一行后F7步入:

这里判断前五位是不是分别为0x42, 0x55, 0x50, 0x54, 0x7B,即“BUPT{”。

这里通过call edx调用下一层解密的代码。

将edi + ecx处的字符异或0xCC与输入的{}中的前四位相比较,得知前四位为:

The_

这里的循环把{}内之后的8位的base64与一段标准base64比较,记下对照的base64转码即可,得到中间8位为:

realCtF_

通过call ecx再次进入一个解密后的代码段:

此处循环将edi + esi处的字符拿出来减一,与输入的{}中的最后十位比较,记录[edi + esi] – 1代表的字符即可。得到最后一段flag:

just_B3g!n

Jarvis OJ: 软件密码破解-1 Writeup

在OD中文搜索引擎顶部找到“你赢了!”字样:

双击进入主程序:

向上找到段头push ebp,并下断:

F9并输入“123123”运行到断点,不断F8,遇到一个关键代码段:

循环前将eax即字符串首字母的地址付给edx。

此处的循环作用是,eax从输入字符串从字符串头部开始,每次加两个地址单元。由于输入的字符串是UNICODE编码,一个字符占两字节,所以是每次指向下一个字符的地址,直到’\0’。

循环出来之后eax是字符串结尾的’\0’的地址,sub eax, ebx求出UNICODE编码下的字符串所占字节数。sar eax, 1将求出来的字节数右移一位,即除二,得到字符串长度。

得到字符串长度后与0xE比较,大于则跳出。于是输入一组长度为14的字符串重新调试:

遇到另一个关键代码段。循环将字符串与ecx + eax的地址位上的数据异或,记录下每一次循环中dl的值:

接下来是对字符串与特定数据进行比较:

这里要注意小端序,将处理后的字符串与1B 1C 17 46 F4 FD 20 30 B7 0C 8E 7E 78 DE比较,如果一致则打印flag与“你赢了!”。

写脚本跑出这一串对照数据经过逆处理的结果:

由于是UNICODE编码,把每一位用&# ;套起来,在线转码:

粘贴到程序里试一下:

Flag get√

Bugku: file Writeup

查壳后显示无壳,拖进IDA:

运行程序时传递的第一个参数为一个文件名,并打开该文件。圈出来的部分判断输入的数据是否是正确的KEY:

可以发现并没有用到encode()的返回值v11和v12,所以encode()就是个摆在那里打扰分析思路的。

根据异或的可逆性,v14[k] = k ^ flllag[k] ^ v13[k]。现在我们只缺v13数组中是哪些元素了,分析sub_400EB9():

sub_400EB9()的返回值根据sub_400E6A()来定,跟进分析sub_400E6A():

这里把传入的某个元素判断是否符合某个区间,然后分别返回不同的值。该函数传进来的是sttr_home[]字符串中的元素,主函数中双击该字符串:

获取了sttr_home的元素后写个脚本跑出v13[],脚本如下:

#include <cstdio>
char str[110] = "664e06226625425d562e766e042d422c072c45692d125c7e6552606954646643";
int jdg(int id){
    if(str[id] >= '0' && str[id] <= '9')
        return str[id] - '0';
    if(str[id] >= 'A' && str[id] <= 'F')
        return str[id] - '7';
    if(str[id] < 'a' && str[id] > 'f')
        return 0xFFFFFFFFLL;
    return str[id] - 'W';
}
int calc(int x, int y){
    return 16 * jdg(x) + jdg(y);
}
int main(){
    for(int i = 0;i < 64;i += 2){
        printf("%d, ", calc(i, i + 1));
    }
    return 0;
}

接着写出根据v14[k] = k ^ flllag[k] ^ v13[k]写出相应脚本跑出KEY,并把KEY存到文件中,代码如下:

接着用gcc编译并运行后,把a.txt作为参数传给file运行:

把a.txt的MD5在线计算一下:

把MD5加上flag{}就OK了。

Bugku: Take The Maze Writeup

首先拿进PEID里查一下有没有壳:

找到主函数,F5出伪代码:

可以看出输入的KEY为24位由0-9,a-f构成的字符串,且需要根据sub_45E593()的返回值确定是否为正确KEY。其他函数先放下,先分析一下sub_45E593():

多个if对应多个处理函数,且根据dlru初步猜测是迷宫问题。先来看看这个byte_541168存着什么:

该数组存的是”delru0123456789″,在回过头分析四个if上面的switch语句:

可以根据两次的自加操作判断,输入的数据两两为一组。而且drc的值被用于在下面的if语句中判断是byte_541168[]前五个中的哪一个字符,所以drc就决定了迷宫的走向。stp是朝着byte_541168[drc]方向行走的步数。

点开四个if对应的函数分别分析一下:

从这个函数可以推测出这个迷宫一行有26个元素。根据中pos == 311则return true,而311 == 11 * 26 + 25,再加上每一行的列标号从零开始,所以相当于从地图的左上角走到地图的(12, 25)的位置,即左上角走到右下角。

而且在上图向下走的函数中,往下走能否可行是根据dword_540548[i] ^ dword_540068[i]的值来确定的,所以可以直接根据四个方向函数中的数组地址写出IDC脚本来判断某个节点是否可以往某个特定的方向走。IDC脚本如下:

auto i;
for(i = 0;i <= 311; ++i){
    if(Dword(0x540548 + i * 4) ^ Dword(0x540068 + i * 4))
        Message(".");
    else
        Message("D");
        
    if(Dword(0x5404DC + i * 4) ^ Dword(0x53FFFC + i * 4))
        Message(".");
    else
        Message("L");        
        
    if(Dword(0x5404E4 + i * 4) ^ Dword(0x540004 + i * 4))
        Message(".");
    else
        Message("R");
    
    if(Dword(0x540478 + i * 4) ^ Dword(0x53FF98 + i * 4))
        Message(".");
    else
        Message("U");
    
    Message("  ");
    if(!((i + 1) % 26))
        Message("\n\n");
}
return 0;

在IDA中执行效果如下:

放到记事本里走一遍迷宫:

手动走迷宫走出来的字符串为06360836063b0839073e0639,结果输到程序里发现还是错误的KEY,返回到主函数检查一下有没有加密函数:

v5因为地址和v4紧挨着,所以v5其实就是v4[16],所以v5 ^= 1就相当于v4[16] ^= 1。这是加密的第一部分,分析一下疑似为加密函数的sub_45C748():

看不太懂这是什么神奇加密,移步OD碰下运气。

令输入的字符串为24个“1”,步过这加密函数后它变成了这样:

右下角的框框高亮部分就是经过加密函数的样子。

再试验一组24个“0”,发现其实是按位异或了一下,python脚本如下:

a = list("06360836063b0839073e0639")
a[16] = chr(ord(a[16]) ^ 1)
for i in range(24):
    print chr(ord(a[i])^i),

跑出来结果如下:

去掉空格就是真正的KEY了,输进程序里面:

工作目录下便生成了一个.png文件,点开发现是个二维码:

扫出来:

把之前解出来的KEY后面加上Docupa就是zsctf{}中括号里的内容啦!

浅析树堆Treap

Treap浅析

Treap作为二叉排序树处理算法之一,首先得清楚二叉排序树是什么。对于一棵树的任意一节点,若该节点的左子树的所有节点的关键字都小于该节点的关键字,且该节点的右子树的所有节点的关键字都大于该节点的关键字,则这棵树是一棵二叉排序树。

Treap在每一个节点中有两个最关键的元素——weight和value

value是在创建这个新节点时赋予该节点的数值大小,Treap利用每个节点的value值将整棵树维持成一个二叉排序树。

weight是在创建这个新节点时赋予该节点的伪随机数,Treap利用每个节点的weight值将整棵树维持成一个最小堆(或最大堆)

看似不相容的二叉排序树和堆的结合却正是Treap的关键之处。如果用递增(或递减)数列只是对单纯的二叉排序树进行插入操作的话可以想见会变成这种情况:

此时一棵二叉搜索树就退化成了数链,每次对树上进行查询都会退化成O(N)。而利用随机数的随机性把二叉树维护成一个堆,就可以尽量使一条不严格数链维护成一棵伪平衡树。

那Treap是如何同时维护堆和二叉搜索树的呢?这就涉及到旋转操作

Treap涉及两种旋转操作:左旋和右旋。这里用最小堆举例子(懒得用电脑画图(逃:

利用代码看一下左、右旋代码的实现:

1.左旋:

void lt(int &k){
    int tmp = t[k].r;
    t[k].r = t[tmp].l;
    t[tmp].l = k;
    t[tmp].size = t[k].size;
    t[k].size = t[t[k].l].size + t[t[k].r].size + t[k].cnt;
    k = tmp;
}

2.右旋:

void rt(int &k){
    int tmp = t[k].l;
    t[k].l = t[tmp].r;
    t[tmp].r = k;
    t[tmp].size = t[k].size;
    t[k].size = t[t[k].r].size + t[t[k].l].size + t[k].cnt;
    k = tmp;
}

除了旋转之外还有许多其他的操作,结合代码看一下:

插入节点:

void Insert(int &k,int num){
    if(!k){//如果这是一个没有被创建过的新的节点就创建一个新的节点
        k = ++size;
        t[k].wt = rand();//为该新节点赋予一个随机值weight
        t[k].val = num;//为该节点赋予一个数值大小value
        t[k].cnt = t[k].size = 1;
        return ;
    }
    ++t[k].size;//插入了一个新节点,所以路径上每个结点的子树大小++
    if(num == t[k].val){//如果这个数值被添加到树中过,就把那个节点处的cnt++
        ++t[k].cnt;
        return ;
    }
    if(num < t[k].val){//如果要被插入的数值比当前结点数值小,向左子树寻找
        Insert(t[k].l,num);
        if(t[t[k].l].wt < t[k].wt)//如果左右孩子其中一个不满足最小堆,即其中一个小于父亲节点,则通过旋转使其满足最小堆
            rt(k);
    }
    else{//如果要被插入的数值比当前结点数值大,向右子树寻找
        Insert(t[k].r,num);
        if(t[t[k].r].wt < t[k].wt)//维护最小堆
            lt(k);
}

删除节点:

void Delete(int &k,int num){
     if(!k)
         return ;
     if(t[k].val == num){
         if(t[k].cnt > 1){//如果某个数值被插入2次及以上,在节点处cnt--即可。
             --t[k].cnt;
             --t[k].size;
             return ;
         }
         else if(!(t[k].l * t[k].r)){//如果那个数值只被插入了一次且左右孩子至少有一个为空,则直接把不为空的孩子接到父亲节点上。
             k = t[k].l + t[k].r;
             return ;
         }
         else{//如果两个孩子都不为空,则把两个孩子中weight较小的旋转到父亲节点,把原来的要删除的节点一直旋转成叶子节点或只有一个非空孩子的节点。
             if(t[t[k].l].wt <= t[t[k].r].wt){
                 rt(k);
                 Delete(k,num);
             }
             else{
                 lt(k);
                 Delete(k,num);
             }
         }
     }
     else{
         --t[k].size;//经过的路径size全都--
         if(num < t[k].val)//判断接下来寻找num位置的走向
             Delete(t[k].l,num);
         else
             Delete(t[k].r,num);
     }
}

求序列中某一数值在数列中的排名:

int Rank(int &k,int num){
    if(!k)
        return 0;
    if(t[k].val == num)
        return t[t[k].l].size + 1;//若与当前结点相等,左节点size+1就是排名,防止t[k].cnt影响排名
    else if(t[k].val > num)
        return Rank(t[k].l,num);
    else
        return Rank(t[k].r,num) + t[t[k].l].size + t[k].cnt;//递归到右子树返回的是在右子树之内的排名,要加上父节点的cnt和左孩子的size
}

求序列中第k大数值:

int Search(int &k,int num){
    if(!k)
        return 0;
    if(num <= t[t[k].l].size)
        return Search(t[k].l,num);
    else if(num <= t[t[k].l].size + t[k].cnt)//如果排名属于(左孩子size,左孩子size + 当前结点cnt]区间内,则第k大数就是该节点的数值大小。
        return t[k].val;
    else
        return Search(t[k].r,num - t[t[k].l].size - t[k].cnt);//进行右子树的递归,排名需剪掉左子树的size和当前结点cnt,这样才能保证在右子树找到正确结果。
}

求前序及后序:

int Pre(int &k,int num){
    if(!k)
        return -2147483648;//返回极小值避免对下方max函数产生影响
    if(t[k].val >= num)
        return Pre(t[k].l,num);
    else
        return max(t[k].val,Pre(t[k].r,num));//如果当前结点数值小于num,则在该节点右子树寻找比该节点数值更大的节点,后序同理
}
int Nex(int &k,int num){
    if(!k)
        return 2147483647;
    if(t[k].val <= num)
        return Nex(t[k].r,num);
    else
        return min(t[k].val,Nex(t[k].l,num));
}

浅析欧拉筛

欧拉筛

算法简介

由于每个大于等于2的合数必定存在一个最小的质因数,所以只要筛去每个质数的倍数就相当于筛去了所有合数。但欧拉筛相比埃氏筛最大的优化就在于欧拉筛保证每个合数只被筛了一次,且是被其最小的质因数筛去的,所以欧拉筛的时间复杂度可以达到O(N)

而如何保证每个合数都只被最小质因数筛去呢?让我们先来看一看欧拉筛的实现:

n = input()
Del = [0] * (n + 1)
prime = []
for a in range(2,n + 1):
    if Del[a] == 0:
        prime.append(a)
    for b in prime:
        if a * b > n: break
        Del[a * b] = 1
        if a % b == 0: break
print prime

算法其他部分和埃氏筛思路类似,在此就不再赘述。而核心就在于这句:

if a % b == 0: break

当a % b == 0时,b为a的一个质因子,所以a = K * b。令K = a / b,则用质数数组的接下来某个质数b’去筛a * b’的时候,a * b’ == K * b * b’,因而b和b’都是a * b’的质因子。由于b < b’,故a * b’的最小质因数是b而不是b’。如果不break就会用非最小质因数b’筛完之后,再当a’ == K * b’时用b又筛一遍,提高了复杂度。所以当a % b == 0时,后续的a * b’只需让循环中接下来的某一个a’ == (a / b) * b’时用b筛掉即可,既保证了每个数都被其最小质因数筛去,也保证了每个数都只被筛一次。

利用欧拉筛求最小质因数

根据【算法简介】中的介绍,每个非质数都被其最小质因数筛去,所以只要在被筛去的时候记录一下被哪个质数筛去,这样就的到了最小质因数,相当于是欧拉筛的“副产品”。python实现如下:

n = input("")
Del = [0] * (n + 1)
Son = [0] * (n + 1)
prime = []
for a in range(2,n + 1):
    if Del[a] == 0:
        prime.append(a)
        Son[a] = a
    for b in prime:
        if a * b > n: break
        Del[a * b] = 1
        Son[a * b] = b
        if a % b == 0: break
print prime;
for a in range(2,n + 1):
    print a,"->",Son[a];

Bugku: Mountain Climbing Writeup

拿到题首先熟练地查个壳再脱个壳。

脱壳之后熟练地双击感受一下出题者的恶意:

根据字面意思得知,是要根据一系列的操作来得到收益最大值,于是用ida打开并f5出来研究出题者是想让我们如何操作:

76和82分别是“L”和“R”的ASCII码值,所以联想到操作只有左移和右移。在来看看这段代码的其他部分:

这一部分相当于利用伪随机数构造了一个直角三角形的数表。由于是伪随机数,只要随机数种子srand()的值一样,构造出来的数表也是一样的。这里的随机数种子是srand(0xCu)也就是srand(12),自行写脚本构造出来一个一样的随机数表:

这样就很明了了,题目意图是让我们从三角形数表的“山顶”开始一步步往下走,每次选择上一个节点的左子节点或右子节点下山,找出路线上所有数字和最大的那一条路线。于是利用随便一种搜索算法搜最优路线即可,这里用深度优先搜索举个例子:

#include <cstdio>
#include <ctime>
#include <windows.h>
using namespace std;
int mt[100][100];
int save[30],ans[30];
int MAXN = -1;
void dfs(int h,int l,int sum){
    sum += mt[h][l];
    if(h == 20){
        if(sum >= MAXN){
            MAXN = sum;
            memcpy(ans,save,sizeof(save));
        }
        return ;
    }
    save[h] = 0;
    dfs(h + 1,l,sum);
    save[h] = 1;
    dfs(h + 1,l + 1,sum);
}
int main(){
    srand(12);
    for(int i = 1;i <= 20;++i)
        for(int j = 1;j <= i;++j)
            mt[i][j] = rand() % 100000;
    dfs(1,1,0);
    for(int i = 1;i <= 19;++i)
        if(ans[i])
            printf("R");
        else printf("L");    
    return 0;
}

当我把搜索到的最优解输进去之后…

嗯???error是什么情况???在反复确认搜索脚本无误后决定打开ollydbg一探究竟。在我试验性地输入字符串LLLLLLLLLLRRRRRRRRR后,字符串被原封不动的保存下来:

而当我调试经过004114F这个函数过后,我输入的字符串发生了有规律的改变:

再试验几个由“H”和“V”构成的字符串后发现,004114F这个加密函数是将偶数位的L与H互换,偶数位的R与V互换。于是将原来深搜的结果进行相应的转换,便是flag中括号里的内容了。