-
-
[原创]ctf2017第二题分析
-
2017-6-4 16:43 3342
-
感谢出题者lelfei,与第一题的简明相比,第二题明显有难度,已经让人怀疑人生:(
看这个势头,做出一题算一题……
好吧,下面开始正题
-----------
用到的工具:OD,ida,十六制的编辑器
总体上,如果没有相关的奥数知识作为背景,就需要穷举,方式一是自己编程实现;方式二工作量小一些,直接在OD里面改,缺点就是比较慢,每秒大概100~200个数,如果crackme运算效率再低点,不会编程就可以直接歇了
cm用到一种大数库,每个大数用到相关联的2张表,每表元素数0x400个,表头一个dword是个标志,下一dword是大数的长度,初始为0,后面是指针或数据了,指针寻址用,用表1的指针找到表2指针,再用表2指针确定表1数据的具体位置,大数的每一位0~9占据1个dword
程序用到的几个函数:
1.初始化
.text:004012C0 s_init1? proc near ; CODE XREF: _main+B3p .text:004012C0 ; s_mul_imd_1+29p ... .text:004012C0 push esi .text:004012C1 mov esi, ecx .text:004012C3 mov dword ptr [esi], offset off_4080C8 .text:004012C9 call ds:GetTickCount .text:004012CF mov ecx, esi .text:004012D1 mov [esi+200Ch], eax .text:004012D7 mov [esi+2008h], eax .text:004012DD call s_init0? .text:004012E2 mov eax, esi .text:004012E4 pop esi .text:004012E5 retn .text:004012E5 s_init1? endp
用缓冲区的立即数初始化
.text:004014E0 s_init_imd proc near ; CODE XREF: _main+CFp .text:004014E0 ; s_init_imd_2+29p .text:004014E0 .text:004014E0 arg_0 = dword ptr 4 .text:004014E0 .text:004014E0 push ebx .text:004014E1 push ebp .text:004014E2 mov ebp, [esp+8+arg_0] .text:004014E6 push esi .text:004014E7 push edi .text:004014E8 mov ebx, ecx .text:004014EA mov edi, ebp .text:004014EC or ecx, 0FFFFFFFFh .text:004014EF xor eax, eax .text:004014F1 xor esi, esi .text:004014F3 repne scasb .text:004014F5 not ecx .text:004014F7 dec ecx .text:004014F8 mov [ebx+4], esi .text:004014FB mov edi, ecx .text:004014FD cmp edi, esi .text:004014FF jle short loc_40152F .text:00401501 .text:00401501 loc_401501: ; CODE XREF: s_init_imd+4Dj .text:00401501 mov al, [esi+ebp] .text:00401504 cmp al, 30h .text:00401506 jl short loc_40152A .text:00401508 cmp al, 39h .text:0040150A jg short loc_40152A .text:0040150C movsx eax, al .text:0040150F sub eax, 30h .text:00401512 jz short loc_40152A .text:00401514 test esi, esi .text:00401516 jz short loc_401522 .text:00401518 mov ecx, esi .text:0040151A .text:0040151A loc_40151A: ; CODE XREF: s_init_imd+40j .text:0040151A lea eax, [eax+eax*4] .text:0040151D add eax, eax .text:0040151F dec ecx .text:00401520 jnz short loc_40151A .text:00401522 .text:00401522 loc_401522: ; CODE XREF: s_init_imd+36j .text:00401522 push eax .text:00401523 mov ecx, ebx .text:00401525 call s_save_a_digit .text:0040152A .text:0040152A loc_40152A: ; CODE XREF: s_init_imd+26j .text:0040152A ; s_init_imd+2Aj ... .text:0040152A inc esi .text:0040152B cmp esi, edi .text:0040152D jl short loc_401501 .text:0040152F .text:0040152F loc_40152F: ; CODE XREF: s_init_imd+1Fj .text:0040152F mov ecx, ebx .text:00401531 call s_adjust ; adjust data, make sure each digit occupy its position .text:00401536 pop edi .text:00401537 pop esi .text:00401538 pop ebp .text:00401539 pop ebx .text:0040153A retn 4 .text:0040153A s_init_imd endp
另一初始化函数
.text:00401350 s_init_imd_2 proc near ; CODE XREF: _main+106p .text:00401350 .text:00401350 arg_0 = dword ptr 4 .text:00401350 .text:00401350 push esi .text:00401351 mov esi, ecx .text:00401353 mov dword ptr [esi], offset off_4080C8 .text:00401359 call ds:GetTickCount .text:0040135F mov ecx, esi .text:00401361 mov [esi+200Ch], eax .text:00401367 mov [esi+2008h], eax .text:0040136D call s_init0? .text:00401372 mov eax, [esp+4+arg_0] .text:00401376 mov ecx, esi .text:00401378 push eax .text:00401379 call s_init_imd .text:0040137E mov eax, esi .text:00401380 pop esi .text:00401381 retn 4 .text:00401381 s_init_imd_2 endp .
调整函数:处理进位的情况,确保每一位置上数字均小于10
.text:00401970 ; adjust data, make sure each digit occupy its position .text:00401970 .text:00401970 s_adjust proc near ; CODE XREF: s_init_imd+51p .text:00401970 ; s_save_a_digit:loc_4015D0p ... .text:00401970 mov edx, [ecx+4] .text:00401973 push ebx ; get len .text:00401974 push ebp .text:00401975 xor ebx, ebx ...
取数据长度
.text:004013A0 s_get_len proc near ; CODE XREF: _main+154p .text:004013A0 ; _main+175p ... .text:004013A0 mov eax, [ecx+4] .text:004013A3 retn .text:004013A3 s_get_len endp
取指定位置的一位数
.text:004013B0 s_get_digit proc near ; CODE XREF: _main+184p .text:004013B0 ; _main+194p .text:004013B0 .text:004013B0 arg_0 = dword ptr 4 .text:004013B0 .text:004013B0 mov eax, [esp+arg_0] .text:004013B4 test eax, eax .text:004013B6 jl short loc_4013CB .text:004013B8 cmp eax, [ecx+4] .text:004013BB jge short loc_4013CB .text:004013BD mov eax, [ecx+eax*4+1008h] .text:004013C4 mov eax, [ecx+eax*4+8] .text:004013C8 retn 4 .text:004013CB ; --------------------------------------------------------------------------- .text:004013CB .text:004013CB loc_4013CB: ; CODE XREF: s_get_digit+6j .text:004013CB ; s_get_digit+Bj .text:004013CB or eax, 0FFFFFFFFh .text:004013CE retn 4 .text:004013CE s_get_digit endp
复制函数
.text:00401540 s_cpy proc near ; CODE XREF: s_mul_imd_1+6Cp .text:00401540 ; s_mul_imd_1+BAp ... .text:00401540 .text:00401540 arg_Len = dword ptr 4 .text:00401540 .text:00401540 push esi .text:00401541 mov esi, [esp+4+arg_Len] .text:00401545 xor edx, edx .text:00401547 mov eax, [esi+4] .text:0040154A test eax, eax .text:0040154C mov [ecx+4], eax .text:0040154F jle short loc_401579 .text:00401551 push ebx .text:00401552 push ebp .text:00401553 push edi .text:00401554 mov edi, esi .text:00401556 lea eax, [ecx+1008h] .text:0040155C sub edi, ecx .text:0040155E .text:0040155E loc_40155E: ; CODE XREF: s_cpy+34j .text:0040155E mov ebx, [edi+eax] .text:00401561 mov ebp, [eax] .text:00401563 inc edx .text:00401564 add eax, 4 .text:00401567 mov ebx, [esi+ebx*4+8] .text:0040156B mov [ecx+ebp*4+8], ebx .text:0040156F mov ebx, [ecx+4] .text:00401572 cmp edx, ebx .text:00401574 jl short loc_40155E .text:00401576 pop edi .text:00401577 pop ebp .text:00401578 pop ebx .text:00401579 .text:00401579 loc_401579: ; CODE XREF: s_cpy+Fj .text:00401579 pop esi .text:0040157A retn 4 .text:0040157A s_cpy endp
复制或相加
.text:004015E0 ; copy or add .text:004015E0 .text:004015E0 sub_4015E0 proc near ; CODE XREF: s_mul_imd_1+91p .text:004015E0 ; s_mul_v1_v2+C4p .text:004015E0 .text:004015E0 var_4 = dword ptr -4 .text:004015E0 arg_0 = dword ptr 4 .text:004015E0 .text:004015E0 push ecx .text:004015E1 mov edx, [ecx+4] .text:004015E4 push ebx .text:004015E5 push esi .text:004015E6 mov esi, [esp+0Ch+arg_0] .text:004015EA mov [esp+0Ch+var_4], edx .text:004015EE mov eax, [esi+4] .text:004015F1 cmp edx, eax
用立即数乘,注意乘法的顺序是反的,即如果你输入的是123,去乘以4,实际上是321*4=1284,结果再扭一下变成4821
.text:004016E0 ; mul imd? .text:004016E0 .text:004016E0 s_mul_imd proc near ; CODE XREF: s_mul_imd_1+80p .text:004016E0 .text:004016E0 arg_0 = dword ptr 4 .text:004016E0 .text:004016E0 push edi .text:004016E1 mov edi, [esp+4+arg_0] .text:004016E5 test edi, edi .text:004016E7 jl short loc_401726 .text:004016E9 cmp edi, 0Ah .text:004016EC jge short loc_401726 .text:004016EE mov eax, [ecx+4] .text:004016F1 xor edx, edx .text:004016F3 test eax, eax .text:004016F5 jle short loc_40171B .text:004016F7 push ebx .text:004016F8 push esi .text:004016F9 lea esi, [ecx+1008h] .text:004016FF .text:004016FF loc_4016FF: ; CODE XREF: s_mul_imd+37j .text:004016FF mov eax, [esi] .text:00401701 add esi, 4 .text:00401704 mov ebx, [ecx+eax*4+8] .text:00401708 lea eax, [ecx+eax*4+8] .text:0040170C imul ebx, edi .text:0040170F mov [eax], ebx .text:00401711 mov eax, [ecx+4] .text:00401714 inc edx .text:00401715 cmp edx, eax .text:00401717 jl short loc_4016FF .text:00401719 pop esi .text:0040171A pop ebx .text:0040171B .text:0040171B loc_40171B: ; CODE XREF: s_mul_imd+15j .text:0040171B call s_adjust ; adjust data, make sure each digit occupy its position .text:00401720 xor eax, eax .text:00401722 pop edi .text:00401723 retn 4
作了一些封装的乘法
.text:00401730 s_mul_imd_1 proc near ; CODE XREF: _main+E9p .text:00401730 ; _main+132p ... .text:00401730 .text:00401730 vAAA = byte ptr -402Ch .text:00401730 vBBB = byte ptr -201Ch .text:00401730 var_C = dword ptr -0Ch .text:00401730 var_4 = dword ptr -4 .text:00401730 arg_0 = dword ptr 4 .text:00401730 .text:00401730 push 0FFFFFFFFh .text:00401732 mov eax, large fs:0 .text:00401738 push offset loc_4075D6 .text:0040173D push eax .text:0040173E mov eax, 4020h .text:00401743 mov large fs:0, esp .text:0040174A call __alloca_probe .text:0040174F push ebx .text:00401750 push ebp .text:00401751 push esi .text:00401752 mov ebp, ecx .text:00401754 push edi .text:00401755 lea ecx, [esp+403Ch+vAAA] .text:00401759 call s_init1? .text:0040175E xor edi, edi
两个大数相乘,结果在Ecx指向的大数中
.text:00401840 s_mul_v1_v2 proc near ; CODE XREF: _main+122p .text:00401840 .text:00401840 var_4030 = dword ptr -4030h .text:00401840 vCCC = byte ptr -402Ch .text:00401840 vDDD = byte ptr -201Ch .text:00401840 var_C = dword ptr -0Ch .text:00401840 var_4 = dword ptr -4 .text:00401840 arg_0 = dword ptr 4 .text:00401840 .text:00401840 push 0FFFFFFFFh .text:00401842 mov eax, large fs:0 .text:00401848 push offset loc_4075F6 .text:0040184D push eax .text:0040184E mov eax, 4024h .text:00401853 mov large fs:0, esp .text:0040185A call __alloca_probe .text:0040185F push ebx .text:00401860 push ebp .text:00401861 push esi .text:00401862 mov esi, ecx .text:00401864 push edi .text:00401865 lea ecx, [esp+4040h+vCCC] .text:00401869 call s_init1? .text:0040186E xor edi, edi .text:00401870 lea ecx, [esp+4040h+vDDD] .text:00401877 push edi
比较大数,根据参数可以选择比较的方向
.text:004013E0 s_cmp proc near ; CODE XREF: _main+1E0p .text:004013E0 ; _main+20Ap .text:004013E0 .text:004013E0 var_4 = dword ptr -4 .text:004013E0 arg_0 = dword ptr 4 .text:004013E0 arg_4 = dword ptr 8 .text:004013E0 arg_8 = dword ptr 0Ch .text:004013E0 arg_C = dword ptr 10h .text:004013E0 arg_10 = byte ptr 14h .text:004013E0 .text:004013E0 push ecx .text:004013E1 mov edx, [esp+4+arg_C] .text:004013E5 push esi .text:004013E6 push edi .text:004013E7 mov edi, ecx .text:004013E9 mov ecx, [esp+0Ch+arg_0] .text:004013ED mov [esp+0Ch+var_4], 0 .text:004013F5 test edx, edx .text:004013F7 jle short loc_401477 .text:004013F9 mov eax, [esp+0Ch+arg_8] .text:004013FD push ebx .text:004013FE push ebp
程序的主体逻辑
先取得输入,长度应为8-20长的数字,不含0
.text:00401035 push offset aPleaseInputKey ; "Please input KEY:" .text:0040103A call sub_401BE0 .text:0040103F push offset File ; File .text:00401044 lea eax, [esp+4148h+Buf] .text:00401048 push 104h ; MaxCount .text:0040104D push eax ; Buf .text:0040104E call _fgets .text:00401053 lea edi, [esp+4150h+Buf] .text:00401057 or ecx, 0FFFFFFFFh .text:0040105A xor eax, eax .text:0040105C add esp, 18h .text:0040105F repne scasb .text:00401061 not ecx .text:00401063 add ecx, 0FFFFFFFEh .text:00401066 cmp ecx, 8 .text:00401069 jl loc_40127A .text:0040106F cmp ecx, 14h .text:00401072 jg loc_40127A
输入应为数字,不含0
.text:00401078 xor esi, esi .text:0040107A xor edx, edx .text:0040107C test ecx, ecx .text:0040107E mov [esp+ecx+4138h+Buf], al .text:00401082 jle short loc_4010AC .text:00401084 .text:00401084 loc_401084: ; CODE XREF: _main+94j .text:00401084 mov al, [esp+edx+4138h+Buf] .text:00401088 cmp al, 30h .text:0040108A jle short loc_401090 .text:0040108C cmp al, 39h .text:0040108E jle short loc_401091 .text:00401090 .text:00401090 loc_401090: ; CODE XREF: _main+8Aj .text:00401090 inc esi .text:00401091 .text:00401091 loc_401091: ; CODE XREF: _main+8Ej .text:00401091 inc edx .text:00401092 cmp edx, ecx .text:00401094 jl short loc_401084 .text:00401096 test esi, esi .text:00401098 jz short loc_4010AC .text:0040109A push offset aKeyFormatError ; "key format error...\n" .text:0040109F call sub_401BE0 .text:004010A4 add esp, 4 .text:004010A7 jmp loc_401288
以下为计算过程,设输入的数字为n,用它来初始化两个大数L1,L2
L1=L1*9
L1=L1*L2
L1=L1*9
即L1=(n*9)的平方
最后要求L1的低半部分与n相同(不含最高一位),L1的高半部分的逆序与n相同,strange.....
.text:004010AC loc_4010AC: ; CODE XREF: _main+82j .text:004010AC ; _main+98j .text:004010AC lea ecx, [esp+4138h+var_L1] .text:004010B3 call s_init1? .text:004010B8 lea ecx, [esp+4138h+Buf] ; code .text:004010B8 ; .text:004010BC mov [esp+4138h+var_4], 0 .text:004010C7 push ecx .text:004010C8 lea ecx, [esp+413Ch+var_L1] .text:004010CF call s_init_imd .text:004010D4 lea ecx, [esp+4138h+var_L1] .text:004010DB call nullsub_1 .text:004010E0 push 9 .text:004010E2 lea ecx, [esp+413Ch+var_L1] .text:004010E9 call s_mul_imd_1 .text:004010EE lea ecx, [esp+4138h+var_L1] .text:004010F5 call nullsub_1 .text:004010FA .text:004010FA loc_4010FA: ; CODE XREF: _main+22Bj .text:004010FA lea edx, [esp+4138h+Buf] .text:004010FE lea ecx, [esp+4138h+var_L2] .text:00401105 push edx .text:00401106 call s_init_imd_2 .text:0040110B lea eax, [esp+4138h+var_L2] .text:00401112 lea ecx, [esp+4138h+var_L1] .text:00401119 push eax .text:0040111A mov byte ptr [esp+413Ch+var_4], 1 .text:00401122 call s_mul_v1_v2 .text:00401127 push 9 .text:00401129 lea ecx, [esp+413Ch+var_L1] .text:00401130 mov esi, eax .text:00401132 call s_mul_imd_1 .text:00401137 lea ecx, [esp+4138h+var_L1] .text:0040113E add esi, eax .text:00401140 call nullsub_1 .text:00401145 test esi, esi .text:00401147 jnz _loc_bad .text:0040114D lea ecx, [esp+4138h+var_L1] .text:00401154 call s_get_len .text:00401159 and eax, 80000001h .text:0040115E jns short loc_401165 .text:00401160 dec eax .text:00401161 or eax, 0FFFFFFFEh .text:00401164 inc eax .text:00401165 .text:00401165 loc_401165: ; CODE XREF: _main+15Ej .text:00401165 cmp eax, 1 .text:00401168 jnz _loc_bad .text:0040116E lea ecx, [esp+4138h+var_L1] .text:00401175 call s_get_len .text:0040117A sar eax, 1 .text:0040117C push eax .text:0040117D lea ecx, [esp+413Ch+var_L1] .text:00401184 call s_get_digit .text:00401189 push 0 .text:0040118B lea ecx, [esp+413Ch+var_L2] .text:00401192 mov edi, eax .text:00401194 call s_get_digit .text:00401199 cmp edi, eax .text:0040119B lea ecx, [esp+4138h+var_L2] .text:004011A2 jnz short loc_40121C .text:004011A4 push 0 .text:004011A6 call s_get_len .text:004011AB dec eax .text:004011AC lea ecx, [esp+413Ch+var_L2] .text:004011B3 push eax .text:004011B4 push 1 .text:004011B6 call s_get_len .text:004011BB mov esi, 1 .text:004011C0 lea ecx, [esp+4144h+var_L1] .text:004011C7 sub esi, eax .text:004011C9 call s_get_len .text:004011CE add esi, eax .text:004011D0 lea ecx, [esp+4144h+var_L2] .text:004011D7 push esi .text:004011D8 push ecx .text:004011D9 lea ecx, [esp+414Ch+var_L1] .text:004011E0 call s_cmp ; cmp? .text:004011E5 push 1 .text:004011E7 lea ecx, [esp+413Ch+var_L2] .text:004011EE mov esi, eax .text:004011F0 call s_get_len .text:004011F5 dec eax .text:004011F6 lea edx, [esp+413Ch+var_L2] .text:004011FD push eax .text:004011FE push 1 .text:00401200 push 0 .text:00401202 push edx .text:00401203 lea ecx, [esp+414Ch+var_L1] .text:0040120A call s_cmp ; cmp? .text:0040120F add esi, eax .text:00401211 jz short _loc_good .text:00401213 xor esi, esi .text:00401215 .text:00401215 _loc_bad: ; CODE XREF: _main+147j .text:00401215 ; _main+168j .text:00401215 lea ecx, [esp+4138h+var_L2] .text:0040121C .text:0040121C loc_40121C: ; CODE XREF: _main+1A2j .text:0040121C mov byte ptr [esp+4138h+var_4], 0 .text:00401224 call s_set_first .text:00401229 test esi, esi .text:0040122B jz loc_4010FA .text:00401231 push offset aWrongKey___ ; "WRONG KEY...\n" .text:00401236 call sub_401BE0 .text:0040123B add esp, 4 .text:0040123E .text:0040123E loc_40123E: ; CODE XREF: _main+278j .text:0040123E lea ecx, [esp+4138h+var_L1] .text:00401245 mov [esp+4138h+var_4], 0FFFFFFFFh .text:00401250 call s_set_first .text:00401255 jmp short loc_401288 .text:00401257 ; --------------------------------------------------------------------------- .text:00401257 .text:00401257 _loc_good: ; CODE XREF: _main+211j .text:00401257 push offset aWellDone ; "WELL DONE!\n" .text:0040125C call sub_401BE0 .text:00401261 add esp, 4 .text:00401264 lea ecx, [esp+4138h+var_L2] .text:0040126B mov byte ptr [esp+4138h+var_4], 0 .text:00401273 call s_set_first .text:00401278 jmp short loc_40123E .text:0040127A ; --------------------------------------------------------------------------- .text:0040127A .text:0040127A loc_40127A: ; CODE XREF: _main+69j .text:0040127A ; _main+72j .text:0040127A push ecx .text:0040127B push offset aKeyLenErrorD__ ; "key len error[%d]...\n" .text:00401280 call sub_401BE0 .text:00401285 add esp, 8 .text:00401288 .text:00401288 loc_401288: ; CODE XREF: _main+A7j .text:00401288 ; _main+255j .text:00401288 mov ecx, [esp+4138h+var_C] .text:0040128F pop edi .text:00401290 xor eax, eax .text:00401292 pop esi .text:00401293 mov large fs:0, ecx .text:0040129A add esp, 4130h .text:004012A0 retn
改穷举我用的这里
push 104h ; MaxCount push eax ; Buf call _fgets
程序体就放在fgets里面,数据初始为11111111,借用4090C0(提示信息的位置)大概的代码是这样的:
push 104 push eax jmp 401ad0 …… …… @401ad0: nextloop: mov ebx, [4090c0] mov ecx, 0a next: lea edi, [buff] inc ebx mov [4090c0], ebx mov eax, ebx nextbit: idiv ecx test edx, edx jz maybe add dl, 30 mov [edi], dl inc edi test eax, eax jz done jmp nextbit maybe: test eax, eax jnz next done: xor dl, dl mov [edi], dl jmp back
返回时大概3、4个位置,再让它跳回401ad0,注意平衡stack,把well done处放个CC。再OD里面大概每秒100~200个数,很慢。我是晚上放在那里,早上程序提示非法操作,说明找到了…………运气比较好,如果自己会写的话肯定可以更快
上面的代码可以再优化,减少2/3的工作量,即第一次idiv时,余数是1 5 6再进行下一步,其他数就返回到下一个数
正确是注册码是:97654321
因12345679*9=111111111,再乘方得到12345678987654321,正好比较可以通过
最后附上改过的程序
[培训]《安卓高级研修班(网课)》月薪三万计划,掌握调试、分析还原ollvm、vmp的方法,定制art虚拟机自动化脱壳的方法