首页
社区
课程
招聘
[原创]2015移动安全挑战赛(第二届) 安卓赛区writeup
发表于: 2015-10-21 08:23 16358

[原创]2015移动安全挑战赛(第二届) 安卓赛区writeup

2015-10-21 08:23
16358
0x1 前言

先吐个槽,时间好短,对于我们这种上班族来说,白天上班,晚上加班,半夜熬夜解题,第二天还要上班真心不容易啊。第一题是送分题,第二题挺烦人,第三题就没时间做了。算法确实耗费了很多的时间。

0x2 题目一

装入APK后,进入app,随便输入字符显示:



然后反编译AliCrackme_1.apk,进入res\values\strings.xml,发现本字符串,如下图


字面意思理解一个是成功,一个是失败,搜索"resp_success",在res\values\public.xml中搜索到

<public type="string" name="resp_success" id="0x7f040005" />


继续搜索0x7f040005,在k2015\a1\Main$1.smali中找到判断成功与失败的逻辑,即在switch分支中判断Landroid/os/Message;->what:I的值,看到函数名handleMessage,是消息处理函数,马上想到搜索send,找到字符串处理主体,在k2015\a1\Main$2$1.smali 中的run函数中找到发送消息的逻辑,如下

(代码01)
    iget-object v1, p0, Lk2015/a1/Main$2$1;->val$in:Ljava/lang/String;
	
    invoke-static {v1}, Lk2015/a1/Check;->check(Ljava/lang/String;)Z

    move-result v1
	
    if-eqz v1, :cond_0

    const/4 v1, 0x0

    :goto_0
    invoke-virtual {v3, v1}, Landroid/os/Handler;->sendEmptyMessage(I)Z
    :try_end_0
    .catch Ljava/lang/Exception; {:try_start_0 .. :try_end_0} :catch_0


此处判断check函数的返回值,如果等于0,则发送消息参数为3,否则发送原值。
看来已经接近处理核心了,找到 k2015/a1/Check中的check函数。随便上下翻了下文档,有四万多行,函数中有很多的垃圾代码,主要处理核心应该不长,那这题主要考的就是这个了。

第一点想到的是找return,return是我们要的结果,顺着这条线找应该没错。这里使用传统logcat+重打包的方法。

在10000多行的地方找到:

(代码02)
    :goto_0
	
    return v4


继续尝试搜索,只发现一处返回。再看函数的参数,只有一个字符串,那应该就是我们在手机上输入的那个字符串了,可以logcat验证。所以p0就是这个字符串。于是,新建一个方法:

(代码03)
.method public static log_string(Ljava/lang/String;)V
       .locals 5

        const-string v0, "TESTLOG"
	
        const-string v1, "START TO LOG STRING"
	
        invoke-static {v0 , v1}, Landroid/util/Log;->v(Ljava/lang/String;Ljava/lang/String;)I
	
        invoke-static {v0 , p0}, Landroid/util/Log;->v(Ljava/lang/String;Ljava/lang/String;)I
	
        const-string v0, "TESTLOG"
	
        const-string v1, "END LOG STRING"
	
        invoke-static {v0 , v1}, Landroid/util/Log;->v(Ljava/lang/String;Ljava/lang/String;)I
	
        return-void
	
.end method


在return v4 前插入

(代码04)
invoke-static {p0}, Lk2015/a1/Check;->log_string(Ljava/lang/String;)V


然后回编,没有碰到任何阻碍,签名后,装入真机,CMD中输入adb logcat -s TESTLOG:v,然后手机中输入aaaaa,发现并没有打印出任何东西,于是猜测应该是throw返回的异常,搜索throw,有20多个结果,之后再12000行左右发现THROW返回(由于我加过代码的SMALI行数和原版不一样,所以用大概行数)。

一般情况下,函数不会以异常返回,所以应该是输入的内容有问题,触发了异常,我输入的是英文,之后尝试输入中文和数字,发现纯数字打印出了p0,说明正常通过return v4返回,这种情况猜测是字符串转整形数据时错误触发的异常,答案应该是个纯数字。

继续回到return v4处,查看标签为 :goto_0, 搜索 :goto_0,发现3处,再加上本身自然流程到return v4的,总共4处,加上logcat打印结果。发现36000行左右有logcat结果,smali代码为:

(代码05)
    const-wide/32 v4, 0xf4240

    rem-long v4, v8, v4

    const-wide/32 v6, 0x1e74e

    add-long/2addr v4, v6
	
    [COLOR="Red"]cmp-long v4, v4, v10[/COLOR]

    [COLOR="Red"]if-nez v4, :cond_3[/COLOR]

    [COLOR="red"]const/4 v4, 0x1[/COLOR]

    goto/16 :goto_0



看来程序流程执行到这里返回的return v4 处。再往回看,发现是一些简单的数学运算。有long类型数据。于是添加函数:

(代码06)
.method public static log_long(J)V
	.locals 5
	
	const-string v0, "TESTLOG"
	
	const-string v1, "START TO LOG LONG"
	
	invoke-static {v0 , v1}, Landroid/util/Log;->v(Ljava/lang/String;Ljava/lang/String;)I
	
	invoke-static {p0, p1}, Ljava/lang/String;->valueOf(J)Ljava/lang/String;
	
	move-result-object v1
	
	invoke-static {v0 , v1}, Landroid/util/Log;->v(Ljava/lang/String;Ljava/lang/String;)I
	
	const-string v0, "TESTLOG"
	
	const-string v1, "END LOG LONG"
	
	invoke-static {v0 , v1}, Landroid/util/Log;->v(Ljava/lang/String;Ljava/lang/String;)I
	
	return-void
	
.end method


此函数用于logcat出long型数据。在(代码05)中,标记红色的三句是返回是/否的关键,比较v4 和 v10,如果相等,则返回正确。

继续往前看,发现 v4 是 v4和v6相加而得,而v6 则是常数0x1e74e,果断下logcat:

(代码07)
    const-wide/32 v4, 0xf4240

    rem-long v4, v8, v4

    const-wide/32 v6, 0x1e74e

    add-long/2addr v4, v6
	
    [COLOR="Red"]invoke-static {v4,v5}, Lk2015/a1/Check;->log_long(J)V

    invoke-static {v10,v11}, Lk2015/a1/Check;->log_long(J)V[/COLOR]

    cmp-long v4, v4, v10

    if-nez v4, :cond_3

    const/4 v4, 0x1

    goto/16 :goto_0



回编+签名+安装,打开CMD,输入adb  logcat -s TESTLOG:v,然后手机中输入123456出现如下图:



控制台中出现



比较的两个数出来了,然后在手机输入123457,控制台出现



变化的是后值,并且是简单的加减法,输入值加1,输出值也加1,而前值没变,是固定值。
那么推论后值底数为248207-123457 = 124750, 所以答案为520676-124750 = 395926。



0x3 题目二

3.1 java层分析

拿到题目AliCrackme_2.apk,装入APK 后,发现没什么特别的,界面是换汤不换药:



反编译APK,查看res\values\strings.xml,发现显示字符串:



搜索resp_success,在res/values/public.xml 中发现:

<public type="string" name="resp_success" id="0x7f040005" />


搜索0x7f040005,与题目1 一样,是handleMessage函数,搜索SEND关键字,在k2015/a2/c.smali中:

    iget-object v0, p0, Lk2015/a2/c;->b:Lk2015/a2/b;

    iget-object v0, v0, Lk2015/a2/b;->a:Lk2015/a2/Main;

    iget-object v3, p0, Lk2015/a2/c;->a:Ljava/lang/String;

    invoke-static {v0, v3}, Lk2015/a2/Ch;->a(Landroid/content/Context;Ljava/lang/String;)Z

    move-result v0

    if-eqz v0, :cond_0

    const/4 v0, 0x0

    :goto_0
    invoke-virtual {v2, v0}, Landroid/os/Handler;->sendEmptyMessage(I)Z




与题1类似,具有分支,根据k2015/a2/Ch;->a返回的不同结果,发送消息。在k2015/a2/Ch;->a(Landroid/content/Context;Ljava/lang/String;)Z 中,此函数为主要处理函数。函数开头很简单,获取APK签名,然后MD5,BASE64等处理,最后与给出固定值比较,如果不一样就结束,很简单的包校验,防止重打包,限于篇幅,只贴跳转点关键代码:

    [COLOR="Red"]const-string v1, "WJmkxxkkGnYbExi3dqzeaA"

    invoke-virtual {v1, v2}, Ljava/lang/String;->equals(Ljava/lang/Object;)Z[/COLOR]

    move-result v1

    if-nez v1, :cond_0

    :goto_0

    return v0


其中红色部分v1 为给出的固定值WJmkxxkkGnYbExi3dqzeaA,v2为计算值,比较是否是否相等,相等则继续执行,所以只需要吧if-nez v1, :cond_0 改为if-eqz v1, :cond_0,之后,重打包的APK就会恒定往下执行,然后来到 :cond_0 处:

	invoke-static {p1}, Lk2015/a2/Ch;->ch(Ljava/lang/String;)Z

	move-result v0

	goto :goto_0


很明显,就是通过native函数ch来进行处理答案是否正确的,下面将进入native层。

3.2  native层静态分析

找到libwbox.so,拖入IDA中静态分析一下,定位到JNI接口ch函数,跟入sub_1de0中,代码很长,在函数的末尾找到返回点:



继续往上找R9:



可以看出loc_24c8就是需要继续跟进的函数:



全部都是乱七八糟的指令,很明显是被加密,回到上一层函数R9处,继续往回看:



加红框的地方都是需要注意的地方,标记黄色的就是需要进入的函数地址,大致的意思是这里有两次mprotect为设置段权限,第一次设置可写,之后进入解密loc_24c8,解密完成后第二次mprotect设置回原来的状态,然后跳入loc_24c8执行。

既然知道了这点,那我们不需要知道解密过程,只需要动态调试到这个入口,然后dump解密后的内存就行了,再动态调试之前,我们还要确定一点就是进入loc_24c8时的参数是什么,是不是我们输入的字符串或者转变而来。看到上图中最后一个红框的下一句:

[COLOR="Red"].text:00001EB0                 ADD     R0, SP, #0x450+var_448[/COLOR]
.text:00001EB4                 MOV     R1, R4
.text:00001EB8                 BL      __aeabi_memcpy



很明显,是从r4中吧数据拷贝了过来,再往上看:

.text:00002190                 BL      mprotect
[COLOR="Red"].text:00002194                 ADD     R0, SP, #0x450+var_448[/COLOR]
.text:00002198                 BL      loc_24C8



由以上代码可知IDA中var_448就是参数,往上查找这个值,在函数的开头看到以下代码:

.text:00001DF8                 MOV     R0, R4          ; s
[COLOR="red"].text:00001DFC                 BL      strlen           ;此处为获取此函数参数字符串的长度[/COLOR]
.text:00001E00                 MOV     R2, R0
.text:00001E04                 MOV     R9, #0
[COLOR="red"].text:00001E08                 CMP     R2, #0x10   [/COLOR]     
[COLOR="red"].text:00001E0C                 BHI     loc_2460         ;比较是否大于0x10,如果小于等于0x10则继续往下执行。[/COLOR]
.text:00001E10                 MOV     R0, #3
.text:00001E14                 MOV     R3, #6
[COLOR="red"].text:00001E18                 CMP     R2, #0           ;比较长度是否大于0[/COLOR]
[COLOR="red"].text:00001E1C                 STRB    R0, [SP,#0x450+var_445]     ;此处开始往目标地址拷贝数据[/COLOR]
.text:00001E20                 MOV     R0, #2
.text:00001E24                 ORR     R3, R3, #0x700
.text:00001E28                 STRB    R0, [SP,#0x450+var_446]
.text:00001E2C                 MOV     R0, #1
.text:00001E30                 STRB    R0, [SP,#0x450+var_447]
.text:00001E34                 MOV     R0, #0
.text:00001E38                 STRB    R0, [SP,#0x450+var_448]
.text:00001E3C                 ADD     R0, SP, #0x450+var_448
.text:00001E40                 ADD     R1, R0, #4
.text:00001E44                 STRB    R3, [R1,#2]!
.text:00001E48                 MOV     R3, #7
.text:00001E4C                 STRB    R3, [R1,#1]
.text:00001E50                 MOV     R1, #5
.text:00001E54                 MOV     R3, #0xA
.text:00001E58                 STRB    R1, [SP,#0x450+var_443]
.text:00001E5C                 MOV     R1, #4
.text:00001E60                 ORR     R3, R3, #0xB00
.text:00001E64                 STRB    R1, [SP,#0x450+var_444]
.text:00001E68                 ADD     R1, R0, #8
.text:00001E6C                 ADD     R0, R0, #0xC
.text:00001E70                 STRB    R3, [R1,#2]!
......以下代码略


通过分析,先是获取输入字符串的长度,判断是否小于0x10并且大于0,如果符合条件,就往目标地址中写入数据,具体写入的流程是 目标地址为SP + 0x450 - 0x448 处开始,从0-0xf依次写入,最后的数据格式应该是:

SP + 0x450 - 0x448       00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f


3.3  native层破解反调试

为了验证是不是我们所静态分析的那样,就需要动态调试,动态调试的准备工作这里不做赘述了,google搜索或者非虫的书上已经写的很明确,直接运行程序,ida附加k2015.a2进程,发现程序立马退出,说明程序有反调试的存在,猜想是有ptrace或者检测调试器逻辑,全文搜素ptrace,发现搜索不到,那应该是调试进程的检测。

说到调试进程,那so在加载时一定会有一个建立的过程,一般是在JNI_ONLOAD中,查看输出表中并没有JNI_ONLOAD的存在,那我们只能从so加载的初始化段中寻找答案。依旧在静态分析中,按ctrl+s,调出segment界面,找到.init_array并双击跳转过去,此为初始化需要进入的段:



表中有7个地址会被依次执行,想到检测调试器,那必须符合以下几个特征:1.一般来说会在新的线程中执行。2.检测调试器必须是不停不间断的检测,那肯定具有无限循环机制。

根据以上两个特征,依次进入检查,发现只有sub_1424才有建立线程的行为:

.text:00001424                 STMFD   SP!, {R11,LR}
.text:00001428                 MOV     R11, SP
.text:0000142C                 SUB     SP, SP, #8
.text:00001430                 LDR     R0, =(_GLOBAL_OFFSET_TABLE_ - 0x1444)
.text:00001434                 LDR     R1, =(sub_1460 - 0x5D64)
.text:00001438                 MOV     R3, #0          ; arg
.text:0000143C                 ADD     R0, PC, R0 ; _GLOBAL_OFFSET_TABLE_
[COLOR="Red"].text:00001440                 ADD     R2, R1, R0 ; sub_1460 ; start_routine[/COLOR]
.text:00001444                 ADD     R0, SP, #8+newthread ; newthread
.text:00001448                 MOV     R1, #0          ; attr
.text:0000144C                 BL      pthread_create
.text:00001450                 MOV     SP, R11
.text:00001454                 LDMFD   SP!, {R11,PC}



很明显,线程执行的地址是sub_1460,继续双击查看

.text:00001460                 STMFD   SP!, {R11,LR}
.text:00001464                 MOV     R11, SP
.text:00001468
.text:00001468 loc_1468                                ; CODE XREF: sub_1460+14j
.text:00001468                 BL      sub_1284
.text:0000146C                 MOV     R0, #1          ; seconds
.text:00001470                 BL      sleep
.text:00001474                 B       loc_1468



很简单的一个无限循环,每次进入执行的是sub_1284,双击进入后,发现是一个很简单的检测调试进程的代码,先查看本进程的/proc/进程ID/status,然后找TracerPid,如果存在,那么就会执行以下指令:

.text:000013DC loc_13DC                                ; CODE XREF: sub_1284+138j
.text:000013DC                 LDR     R0, [SP,#0x310+pid] ; pid
.text:000013E0                 MOV     R1, #9          ; sig
[COLOR="red"].text:000013E4                 BL      kill[/COLOR]



执行的kill -9 PID,也难怪没收到任何信号量提示就退出。发现了这点,那就干掉这里反调试就简单了,有很多方法,我这里只是简单的NOP掉kill函数,NOP掉之后就成了这样:



想着NOP掉之后,应该可以正常调试了,重打包+执行,然后IDA附加过去,发现程序又退出了,但是退出的方法不一样:



说明是程序崩溃后退出的,那我们依旧动态调试,这次的断点是在INIT入口处,在INIT入口下断,就需要在程序启动之前进行附加,具体方法也不在赘述,网上方法也很多,我这里使用的是 am start -D启动程序等待调试器, 然后IDA附加完毕后,JDB发出调试指令激活程序:

am start -D -n k2015.a2/.Main


ida附加上去,DEBUGGER OPTION 中,勾选suspend on library load/unload

然后执行

jdb -connect com.sun.jdi.SocketAttach:hostname=127.0.0.1,port=8700


激活程序,在IDA中F9执行程序,几秒钟后出现以下对话框:



说明此时正在加载so库,点掉对话框后程序断下,按CTRL+S 查看so库加载偏移地址:



分别对INIT中的7个函数下断点:

.init_array:00005D28                 DCD sub_1424
.init_array:00005D2C                 DCD sub_1478
.init_array:00005D30                 DCD sub_2E04
.init_array:00005D34                 DCD sub_2EBC
.init_array:00005D38                 DCD sub_2F40
.init_array:00005D3C                 DCD sub_3028
.init_array:00005D40                 DCD sub_3160



单步运行,发现在sub_3160中,执行到:

.text:00003198                 MOV     R3, #0          ; arg
[COLOR="Red"].text:0000319C                 BL      clone[/COLOR]
.text:000031A0                 LDMFD   SP!, {R11,PC}


出现了段错误信号量,果断NOP掉!重打包+安装,直接IDA附加,没有出现任何错误,看来反调试已经干掉了。

3.4  native层动态分析

现在初步来说已经可以畅通无阻的动态分析了,现在我们需要对3.2节中静态分析出现的猜想进行论证,在sub_1DE0首地址进行下断点,F9运行,然后手机上随便输入123456,点击按钮,程序断下:



查看寄存器,输入字符串是否是我们起初输入的原值,在HEX VIEW中,按G,输入R0:



没错,就是123456,我们继续执行到3.2中,拷贝完字符串那步:

.text:00001EB8                 BL      __aeabi_memcpy


下断,然后F9运行:



在HEX VIEW中按G,输入R0,继续F8步过,查看此时HEX VIEW中的数据:



确实如3.2中静态分析的那样,按照3.2中分析的流程,我们对以下红色标记代码下断点:

.text:00002194                 ADD     R0, SP, #0x450+var_448
[COLOR="Red"].text:00002198                 BL      loc_24C8[/COLOR]
.text:0000219C                 MOV     R9, R0


然后F9运行,发现又出现了段错误信号量,我不知道是否是之前NOP掉clone函数的缘故,但是我们不需要关心:



点击OK后,断下的错误点:



发现在aeabi_memcpy执行后,和断点之前的那一大堆复杂的循环中,值得庆幸的是,在这一大堆复杂出错的代码中,我并没有发现var_448(拷贝时的目标内存)参与了计算,所以我想的是直接跳过,反正不影响后面关键函数的执行就行!重新开始调试,找到以下代码:

.text:00001FB0                 CMP     R7, #0
.text:00001FB4                 BEQ     loc_20A0



在调试窗口中找到此语句,下断:



此语句是是否跳入循环的关键,直接再寄存器中,把R7置0,然后再对:

.text:00002198                 BL      loc_24C8


下断点,F9运行,如预期般断到了0x2198处:



按F7跟进,发现进入后的代码已经完全解密:



直接在HEX窗口中,dump下来,然后另外复制一个so文件,用HEX工具打开(我这里用的winhex),然后将解密代码复制进去,用IDA打开,进入loc_24c8:



虽然看着有些奇怪,但是结合动态分析,倒是不影响阅读。通观全文,倒是和loc_1de0差不多,也有两次混淆循环进行反调试,回到函数的开头进行分析,直接无视那些无用循环,来到0x25fc处,这里贴上部分代码:

.text:000025FC                 MOV     R2, #0
.text:00002600                 MOV     R3, #0
.text:00002604                 ADD     R0, R0, #1
.text:00002608                 STRB    R0, [R10,#1]
.text:0000260C                 LDRB    R0, [R10,#2]
.text:00002610                 ADD     R0, R0, #2
.text:00002614                 STRB    R0, [R10,#2]
.text:00002618                 LDRB    R0, [R10,#3]
.text:0000261C                 ADD     R0, R0, #3
.text:00002620                 STRB    R0, [R10,#3]
.text:00002624                 LDRB    R0, [R10,#4]
.text:00002628                 ADD     R0, R0, #4
.text:0000262C                 STRB    R0, [R10,#4]
.text:00002630                 LDRB    R0, [R10,#5]
.text:00002634                 ADD     R0, R0, #5
.text:00002638                 STRB    R0, [R10,#5]
.text:0000263C                 LDRB    R0, [R10,#6]
.text:00002640                 ADD     R0, R0, #6
.text:00002644                 STRB    R0, [R10,#6]
.text:00002648                 LDRB    R0, [R10,#7]
.text:0000264C                 ADD     R0, R0, #7
.text:00002650                 STRB    R0, [R10,#7]
.text:00002654                 LDRB    R0, [R10,#8]


意思非常简单,对输入的16字节字符串,按照字节位置,将数据依次与位置编号进行相加,比如原值为:



相加方法为 第0位 31 + 0 = 31,第1位32 +1 = 33 第2位 33 + 2 = 35,依次类推,最终结果为:



数据初始化完毕后,按照上一层函数的方法,在关键点置零:



与上一层函数类似,还是要解密一个函数,然后跳入执行:



单步步入,发现为已经解密了的函数,依旧DUMP之,然后在IDA中查看:



依旧是类似的混淆循环,与之前的两个函数类似,限于篇幅,这里只说破解思路,第一步是找到返回值,然后顺着往上查找发现:



其中R8为返回值,这段代码的意思比较两个16字节的字符串R9 和R0,如果每个字节都相等,则R8=1,如果有不相等的字节,则R8=0,继续往上查看R9:

[COLOR="Red"].text:00001938                 ADD     R9, SP, #0x468+var_448[/COLOR]
.text:0000193C                 ADD     R0, SP, #0x468+var_458
.text:00001940                 MOV     R1, R9
[COLOR="red"].text:00001944                 BLX     R5 ; _GLOBAL_OFFSET_TABLE_[/COLOR]
.text:00001948                 LDR     R0, =0x66429849


执行的是一个函数,来处理输入的字符串,我们继续往上搜索var_458:



代码不难,只是将两个地址的值相加,我们接着前几步动态调试分析下具体情况,单步到:



和之前的函数一样,下断,然后置零,接着运行到



这处就是上面图形模式中显示的语句,分别将R8和R0两个缓冲区进行相加,通过查看HEX VIEW发现,R8为:



所以R8我们初始进入这个函数的字符串,r0为:



是固定值,我们拷贝下来这串字符串,留作后面写算法用:

1F BC DA FF E6 4C BC 44 F5 B8 13 C8 EC A8 CD BD


相加完毕后的结果:



然后继续下断点在:



这一步是关键的算法函数,如果F7单步后进入,将会发现也被解密了,这是本题的关键算法



先按F8 步过这里,查看加密后的结果:



两行数据,其中第一行16字节为加密之前的数据,第二行为加密后的16字节数据。继续往下执行,单步到:



将R7置零,继续执行:



图中截图的为静态分析中,最后比较决定r8为0或者1的部分,再往下走几步,查看r0和r9的值:

r9为:


r0为:


很明显,r9为刚刚执行完加密算法后的加密值,那么r0就为我们需要的最终答案的加密值,我们只需要根据逆算算法,求出r0的明文值就可以知道最后答案了。

3.5  native层加密算法分析

在分析进入3.4中的算法时,我的做法是先还原成c语言,然后分析通篇算法,最后根据算法原理写出解密算法。

汇编转高级语言这里不做赘述,都是实打实的苦功夫,文章的最后我附上了我写的加密算法和逆算法,这里分析下大致的算法原理。为了便于表达,首先声明一个表示方法,4字节整形数据以分号来分割4字节数据中的4个字节,比如0x1a2b3c4d,可以表示为0x1a;0x2b;0x3c;0x4d。



加密算法分为以下几个步骤

1.根据初始固定值生成常量表,我们不用关心如何生成,只需要dump数据就行,具体数据已在后面附上的代码中声明。

2.将输入的16字节字符串,分为四组,做相应的轮换后,将数据倒置(由于整数和内存的顺序相反),分别与4个初始固定值进行异或。

3.分为16步4组操作,具体过程模拟如下:

(1).将第2步的四个值设为v1,v2,v3,v4。
(2).以第一组为例
        第一步:将v1右移23位并且和0x1fe相与,得出的值作为偏移去摘要表中取出对应的两个字节s11,s12,由于此处0x1fe最后一个字节为0,那么这个偏移量恒为偶数。将s11,s12组成一个4字节数据为s11;s12;s12;(s11^s12)

        第二步:将v2右移15位并且和0x1fe相与,得出的值作为偏移去摘要表中取出对应的两个字节s21,s22,将s1,s2组成一个4字节数据为(s21^s22);s21;s22;s22

        第三步:将v3右移7位并且和0x1fe相与,得出的值作为偏移去摘要表中取出对应的两个字节s31,s32,将s1,s2组成一个4字节数据为s32;(s31^s32);s31;s32

        第四步:将v4左移1位并且和0x1fe相与,得出的值作为偏移去摘要表中取出对应的两个字节s41,s42,将s1,s2组成一个4字节数据为s42;s42;(s41^s42);s41

        最后将第一至四步的数据分别异或,然后与常数表中的数依次异或,得出一个4字节整数r1。

(3)从第一组中可以看出以不同偏移拉出的数据以滚动方式组成不同的数据。而第二、三、四组的算法都一样,只是v1,v2,v3,v4所位移的位数不一样,具体情况如下:
第一组:v1,v2,v3,v4 第二组:v2,v3,v4,v1 第三组:v3,v4,v1,v2 第四组:v4,v1,v2,v3,执行完四组操作后得出的四个4字节为r1,r2,r3,r4。

4.重复第三步骤9遍。

5.将第4步中 生成的4个4字节数据r1,r2,r3,r4,每个4字节数据分别拆开为4个字节,总共为16字节,再左移一位,分别去摘要表中取出1个字节然后通过以下规则组成4个4字节数据:
假设r1,r2,r3,r4拆成的16个单字节数据为b1 ~ b16,最终的4个4字节数据为f1,f2,f3,f4, 摘要表的表示法为static_table[xx],其中xx为位移,那么:

r1=b1;b2;b3;b4
r2=b5;b6;b7;b8
r3=b9;b10;b11;b12
r4=b13;b14;b15;b16


算法为
f1=static_table[(b1<<1)&0x1f0]; static_table[(b6<<1)&0x1f0]; static_table[(b11<<1)&0x1f0]; static_table[(b16<<1)&0x1f0]

f2=static_table[(b5<<1)&0x1f0]; static_table[(b10<<1)&0x1f0]; static_table[(b15<<1)&0x1f0]; static_table[(b4<<1)&0x1f0]

f3=static_table[(b9<<1)&0x1f0]; static_table[(b14<<1)&0x1f0]; static_table[(b3<<1)&0x1f0]; static_table[(b8<<1)&0x1f0]

f4=static_table[(b13<<1)&0x1f0]; static_table[(b2<<1)&0x1f0]; static_table[(b7<<1)&0x1f0]; static_table[(b12<<1)&0x1f0]



这四个数字f1,f2,f3,f4组成16字节的数据就是最终和答案比较的值。



算法的源码我已经附在后面的c文件中,正向算法不难理解,下面重点分析下反向解密算法,我以步骤和举例的方式呈现出来:

解密算法分析

1.通过第五步的算法,我们先要把最终的16个字节数据拆成4个4字节数据,然后转化为反序整数,这里以加密后的数据AF 96 2A 42 8E 18 B2 F6 48 1B 67 90 CA 4D 63 61 为例:



2.将4个数据分别和常量相异或(常量表我已dump在后面附上的源码中,这里就直接标识出来了,下图中间那行4个为常量,不会变):



3.将4个4字节数据拆成16个单字节数据:
0x3E 0xcc 0x26 0x88 0xc9 0xe9 0xa3 0xe1 0x7b 0x41 0x04 0x62 0x04 0xbf 0xc6 0xc0


由于加密算法第五步中,每个字节都需要左移一位,并且与0x1fe相与,相当于把最低位二进制置0,导致得出的结果恒为偶数,再观察static_table(摘要表数据,已dump在后面附上的源码中)每个字节必定能找到两个,且一奇一偶,那么我们很容易可以推想到可以利用现有的单字节,在表中的偶数位找到唯一的那个位置,然后把位置编号右移一位就是我们要的还原后的单字节,比如第一个字节0x3E的数据所在位置:



它的位置在图中红框标记的为0x1A2,0x1A2为偶数符合条件,那么第一位为0x1a2,之后的几个单字节以此类推:



根据第五步的规则,组合成4个数:

r1=f1的第一字节 ; f4的第二字节;f3 的第三字节; f2的第四字节 = 0xd1f430e0

以此类推

r2=f2的第一字节 ; f1的第二字节;f4 的第三字节; f3的第四字节 = 0x1227c7ab

r3=0x03eb231f

r4=0x30f87197


到此为止,第五步的4个初始输入值已经算出来了,接下来需要解决9次循环的第三步。

4.我们首先分析下加密算法步骤3子步骤(2)中每一步的数据组成,有以下关系



然后最后得出的数据t1,t2,t3,t4会以常数相与得到最后的r1中的四个字节,那么我们如果要反算s11 ~ s42,通过t1 ~t4之间相互异或,因为没有哪两列列可以有3个相等的值,那么最多只能求出两个值异或后的值,所以我们还需要借助摘要表才能最终求出每个单独值,将1,2列异或有以下等式:

t1^t2 = s11^(s21^s22)^s32^s42 ^ s12^s21^(s31^s32)^s42 = (s11^s12) ^ (s31) ^ (s22)   (公式1)


将公式1与第三列异或:

t1^t2^t3 = (s11^s12) ^ (s31) ^ (s22) ^ s12 ^ s22 ^ s31 ^ (s41^s42) = (s41^s42) ^ s11    (公式2)


公式2是可以求出具有未知数最少的等式,所以借助摘要表可得知,s41 ,s42为相邻的两个数,由于数据和内存的倒置关系,s11为奇位值,s41为后值(奇位),s42为前值(偶位),t1,t2,t3已知,那么就可以去表中遍历找出两个一组的数外加一个单独的偶位数,三数异或等于t1^t2^t3(条件1),同时我们还可以根据s11和s12相邻得出s12的值。这种情况会很若干种,我们还需要别的约束条件。假设找到一种组合符合(条件1),那么第一列和第四列异或有以下等式:

t1^t4 = s11 ^ (s11^s12) ^ (s21^s22)^s22 ^ s32 ^ s32 ^ s42 ^s41 = s12 ^ s21 ^ (s41 ^ s42)


继续推导出:

s21 = t1 ^ t4 ^ (s41^s42)^s12  (公式3)


在找到一种组合时右边参数全部为已知,就可以求出s21的值。

当已知s21的值时,那么就可以根据s21为奇数位,找出s21的所在位置,前一字节就是s22的值。此时,已知s21,s22,s11,s12,s41,s42,那么求出s31和s32也就不难,根据第三列有以下等式:

t3 = (s11^s12) ^ s22 ^ s31 ^ (s41 ^ s42) 


那么继续可以推导出
s31 = t3 ^ s11 ^s12 ^s22 ^ s41 ^ s42  (公式4)


再根据s31在表中为奇数位,那么前面的偶数位字节就是s32的值,此时s11 ~s42都为已知,但是在我的测试中符合以上几种条件的数值还是有很多,所以还需要加一个最基本的条件:

s11 ^ (s21^s22) ^ s32 ^ s42 = t1
s12 ^s21^(s31^s32) ^ s42 = t2
s12^s22^s31^(s41^s42) = t3
(s12^s11) ^ s22 ^ s32^ s41 = t4



即四列相与分别等于相应的那个t值。在测试中,基本不存在多种情况的问题,但是偶尔也会出现,我们先不管那种有多种值的情况,如果根据最后的答案不能解出最后的明文,我们再去考虑多种情况的问题。

至此已求出加密算法第三步骤第8轮循环后的v1的最高字节,v2的第二字节,v3的第三字节,v4的最低字节,依次类推,可以求出第8轮循环后,v1,v2,v3,v4其他位置的12个字节。这里不在赘述,具体算法请查看文章后附加的源码。

5.根据3步骤,进行重复的9次循环,可以得到加密算法从第二步进入第三步的四个4字节整数v1,v2,v3,v4。

6.分别将v1,v2,v3,v4与四个常数值进行异或,得到加密算法第二步的4个原始4字节数据。

7.将步骤6组成16字节数据,分别将每一字节减去1F BC DA FF E6 4C BC 44 F5 B8 13 C8 EC A8 CD BD 中每个字节。

8.最后将每一字节的数据减去所在字节位置的编号,得出最后的结果。

到这里为止,加密算法就完成了。我们再用我们需要解密的数据进行最后的答案解析。

3.6答案计算

根据3.4节,最后答案的密文值为

5C DA 77 2F A3 C6 3E 39 B6 F0 F3 ED 51 5A 99 86


我们开始进行逆算法。

1.分为四组分别与常数0x915a0cca,0x47f11117,0x335a63f2,0xcef2a5a1进行异或,得出四个值:
0xcd807be5  0xe4372f2e  0x85aa901f  0x9fa83c27


2.解密算法步骤3中,经过变换后
r1=0x806f96c3,r2=0xae3a6dcb,r3=0x67b2033d,r4=0x6e624e2a


3.经过解密算法步骤4中,第一次循环后的数据为:
v1=0x570b0a03 v2=0xa33211fc v3=0x5e69eda9 v4=0x7f423800


4.经过9次循环后的数据为:
v1=0xe1d28d14 v2=0x32e18ecf v3=0x886e7e6f v4=0xaf5fef5b


5.分别与四个常数0x6BCDC67A  0x6B2B7C9D  0x8DA459B1  0xAB9D0680异或得到:
o1=0x8a1f4b6e o2=0x59caf252 o3=0x05ca27de o4=0x04c2e9db


6.组成16字节数据为:
8a 1f 4b 6e 59 ca f2 52 05 ca 27 de 04 c2 e9 db


7.减去1F BC DA FF E6 4C BC 44 F5 B8 13 C8 EC A8 CD BD中的每一字节,并且减去相应的位置编号:
6b 62 6f 6c 6f 79 30 07 08 09 0a 0b 0c 0d 0e 0f


8.答案即为kboloy0。由于是明文字符串,所以并没有出现解密算法中步骤4的多种情况。最后附上解密成功截图:



0x4后记

总算熬了一夜写完了writeup,我也不知道是不是应该这样写,因为从来没写过,代码写的很粗糙,文章中如果有出错的地方,请各位多多包涵,谢谢!

[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

上传的附件:
收藏
免费 0
支持
分享
最新回复 (4)
雪    币: 729
活跃值: (1306)
能力值: ( LV9,RANK:160 )
在线值:
发帖
回帖
粉丝
2
我只看了第一题的 题解。感觉楼主的题解 简单明了。实在是厉害。赞赞赞。
2015-10-28 18:38
0
雪    币: 729
活跃值: (1306)
能力值: ( LV9,RANK:160 )
在线值:
发帖
回帖
粉丝
3
我看了一遍 解题二,虽然我没有。跑一遍运行出结果,但是感觉,写的真不错。。。。赞赞赞。
2015-10-29 12:45
0
雪    币: 18
活跃值: (1059)
能力值: ( LV7,RANK:110 )
在线值:
发帖
回帖
粉丝
4
学习学习.
2015-10-29 13:04
0
雪    币: 274
活跃值: (88)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
2015-10-29 22:24
0
游客
登录 | 注册 方可回帖
返回
//