-
-
[原创]抽象与衍化 PEDIY.2017.P.CTF05.Writeup
-
发表于: 2017-11-3 00:03 3520
-
基本验证机制
(1)keyval62str=input_key是以"数字大小写字母]0-9|A-Z|a-z]"为基数的62进制数，低位权在左侧（类似于小端格式）;
(2)62进制 keyval62str 表示的值转换为内部512位符号整数int512_t keyval,符号位独立于512位绝对值之外;
(3)keyval转换为18进制的字符keyval18astr,18进制基数集为[0-9|A-H];
(4)有基本一维矩阵y=x=[[0..0x2F]],基本一维变换矩阵b0,b1,b2,b3,b4,b5，其中b矩阵于y（或x）两两不等，但值集完全相同；
(4.1)b0,b1,b2,b3,b4,b5分别与y运算，生成6个基本二维变换矩阵A0,A1,A2,A3,A4,A5;
b与y到A生成算法: A[0..0x2F,0..0x2F]=0
for val in b:
A[y.index(val),b.index(val)]=1
简单描述为，以y依次为列标，b为行标，交点映射到y和b上的值相等时，交点值为1，否则为0。
如 y=[0,1,2,3],b=[3,1,0,2],则A=[[0,0,1,0],[0,1,0,0],[0,0,0,1],[1,0,0,0]]
b 3 1 0 2
y
0 0 0 1 0
1 0 1 0 0
2 0 0 0 1
3 1 0 0 0
(4.2)从低到高位权依次遍历取18进制keyval18astr的基数(字符串左到右)r18bch，
转换为对应的18进制基数值r18bval,得到i=r18bval/3,e=(r18bval%3)+1
其中i用于从A0,A1,A2,A3,A4,A5选出用于变换计算的矩阵Ai,e表示用Ai累计变换计算次数，即指数，
有 x=x*(Ai^e)
(5)特别地，应当注意到，验证的过程是先用"KanXueCrackMe2017"对x变换计算得到x_M，
再用input_key进行变换计算得到最终的x_L，最终变换要求结果y==x_L
(5.1)假定"KanXueCrackMe2017"与input_key最终转换的18进制数位分别为j,k，即
M = [A0,A1,A2,A3,A4,A5]
y=x
x_B=x
x_M=x_B*(M[i_1]^e_1)*(M[i_2]^e_2)*...*(M[i_j]^e_j) //KanXueCrackMe2017 translation
x_L=x_M*(M[i_1]^e_1)*(M[i_2]^e_2)*...*(M[i_k]^e_k) //input_key translation
y==x_L
由于y==x,即KanXueCrackMe2017产生的变换与input_key产生的变换为互逆变换，
根据矩阵的互逆原则，KanXueCrackMe2017产生变换的逆变换为
(M[i_j]^e_j).I*...*(M[i_2]^e_2).I*(M[i_1]^e_1).I
其中(M[i_j]^e_j).I表示 (M[i_j]^e_j)的逆矩阵，即input_key的变换可以表示为
(M[i_1]^e_1)*(M[i_2]^e_2)*...*(M[i_k]^e_k)==(M[i_j]^e_j).I*...*(M[i_2]^e_2).I*(M[i_1]^e_1).I
(5.2)上述绝对等式右边可以从KanXueCrackMe2017正变换反推得到，
最终问题，变成如何将右边式子化简为左边的式子的问题，
最简单的方式直接在M = [A0,A1,A2,A3,A4,A5]中中搜寻(Ai^e).I,用A(i`)^(e`)表示(Ai^e).I，
因为要确保input_key长度为0x0C,
所以还需将得到的(M[i_1]^e_1)*(M[i_2]^e_2)*...*(M[i_k]^e_k)进一步化简到满足条件。
//(6)写本文尾部才发现，看漏了 Hi_last_check_sub_40680C 也碰巧过了，看来还真是瞎蒙对了
0x01 "瞎撞"
样例到手，四百多KB，有点大（相对一般十几或几十KB而言，对十几MB的中间件还是小的）。
直上IDA同时双击运行测试，MFC，vc7静态编译链接，几百KB的成因。
IDA strings窗体没啥敏感信息;
空格切换IDA为 text模式，从上到下拉滚动条快速浏览代码和数据(一些函数表、消息表、敏感数据块初步印象),
看到一个长片区代码不像正常代码。驻足graph模式看多几眼
.text:0040754C mov [ebp+var_3A0], 9
.text:00407556 mov [ebp+var_39C], 0Ah
.text:00407560 mov [ebp+var_398], 0Bh
.text:0040756A mov [ebp+var_394], 22h
.text:00407574 mov [ebp+var_390], 23h
.text:0040757E mov [ebp+var_38C], 24h
.text:00407588 mov [ebp+var_388], 0Fh
.text:00407592 and [ebp+var_44], 0
.text:00407596 and [ebp+var_184], 0
.text:0040759D mov [ebp+var_384], 0Eh
.text:004075A7 mov [ebp+var_380], 11h
.text:004075B1 mov [ebp+var_37C], 12h
.text:004075BB mov [ebp+var_378], 13h
.text:004075C5 mov [ebp+var_374], 14h
.text:004075CF mov [ebp+var_370], 15h
.text:004075D9 mov [ebp+var_36C], 0Ch
上述片区定位在 Hi_gen_matrix_sub_407307 函数处，
一大堆局部变量赋值，99%可能不是库函数，且很可能是核心算法函数，
溯源交叉引用处
.text:0040700B call Hi_gen_matrix_sub_407307
.text:00407010 mov esi, offset aKanxuecrackme2 ; “KanXueCrackMe2017"
看到上面的字符串KanXueCrackMe2017，核心部件的可能性进一步增加，
在浏览下上下文，还有base64编码字符串"Vm0wd2QyUXlVWGw=="一类的"烟幕弹"(后知后觉),
后面一些调用的函数体流程图极具算法特征；
继续溯源该函数Hi_CheckKey_sub_406FC3的交叉引用，在Hi_respone_func_sub_4071FD函数体内
.text:004071FD Hi_respone_func_sub_4071FD proc near
.text:004071FD push esi
.text:004071FE push 1
.text:00407200 mov esi, ecx
.text:00407202 call Hi_update_true_sub_40B781
.text:00407207 mov ecx, esi
.text:00407209 call Hi_CheckKey_sub_406FC3
.text:0040720E cmp eax, 1
.text:00407211 jnz short loc_407221
.text:00407213 push 0
.text:00407215 push offset Caption ; 状态
.text:0040721A push offset word_44BE10 ; 成功
.text:0040721F jmp short loc_407243
.text:00407221 loc_407221:
.text:00407221 test eax, eax
.text:00407223 jnz short loc_407232
.text:00407225 push eax
.text:00407226 push offset Caption ; 状态
.text:0040722B push offset word_44BE18 ; 失败
.text:00407230 jmp short loc_407243
.text:00407232 loc_407232:
.text:00407232 cmp eax, 2
.text:00407235 jnz short loc_40724A
.text:00407237 push 0 ; uType
.text:00407239 push offset Caption ; 状态
.text:0040723E push offset Text ; 很遗憾，离成功还差一小步@￥@
.text:00407243 loc_407243:
.text:00407243
.text:00407243 mov ecx, esi
.text:00407245 call Hi_show_msg_sub_40B71C
.text:0040724A loc_40724A:
.text:0040724A pop esi
.text:0040724B retn
.text:0040724B Hi_respone_func_sub_4071FD endp
函数上下文有一些静态变量的引用word_44BE10，word_44BE18等，
且Caption、Text这些IDA自动识别命名告诉我们这时字符内容，
跟进，提取字节数据，解码得到相应中文，编码为UTF16（尝试得知，UTF8，gbk,463,失败，好像又是瞎撞）
再次溯源Hi_respone_func_sub_4071FD交叉引用，得到
.rdata:0044BD90 dd 111h
.rdata:0044BD94 dd 0
.rdata:0044BD98 dd 1
.rdata:0044BD9C dd 1
.rdata:0044BDA0 dd 39h
.rdata:0044BDA4 dd offset Hi_respone_func_sub_4071FD
其为消息映射表项，为Ccm_cubeDlg对话框消息映射表的一员（为何？）
[nMsg:00000112,nCode:00000000,nId:00000000,nLID:00000000,nSig:0000001E,pfn: 4066E9]
[nMsg:0000000F,nCode:00000000,nId:00000000,nLID:00000000,nSig:00000013,pfn: 40674B]
[nMsg:00000037,nCode:00000000,nId:00000000,nLID:00000000,nSig:00000028,pfn: 406805]
[nMsg:00000111,nCode:00000000,nId:00000001,nLID:00000001,nSig:00000039,pfn: 4071FD]//Hi_respone_func_sub_4071FD
[nMsg:00000111,nCode:00000000,nId:00000002,nLID:00000002,nSig:00000039,pfn: 40724C]
因为继续往上溯源，可得到Hi_Ccm_cubeDlg::getMssageMap——sub_40662D 函数
从而进一步得到对话框虚表
.rdata:0044BE44 ??_7Ccm_cubeDlg@@6B@
进一步定位到全局静态变量Ccm_cubeApp的初始化函数Initialization
.text:004064D4 push 66h //对话框资源ID
.text:004064D6 lea ecx, [ebp+var_B0]
.text:004064DC call sub_413B3A
.text:004064E1 ; try {
.text:004064E1 and [ebp+var_4], 0
.text:004064E5 push offset unk_44C15C ; Src
.text:004064EA lea ecx, [ebp+var_18]
.text:004064ED mov [ebp+var_B0], offset ??_7Ccm_cubeDlg@@6B@
进一步定位到全局静态变量Ccm_cubeApp的的虚表
0044BC04 ??_7Ccm_cubeApp@@6B@
和初始化位置
.text:004439E4 mov ecx, offset Hi_Ccm_cubeApp_45B9C0
.text:004439E9 call sub_411DA5
.text:004439EE push offset sub_443D13 ; void (__cdecl *)()
.text:004439F3 mov dword_45B9C0, offset ??_7Ccm_cubeApp
再往上追溯就是start启动后的C/C++初始化向量了。
0x02 抽象衍化-UpdateData(True)
经过瞎撞我们得到了基本脉络，但还没法确定检验细节，让我们继续;
上述分析可知Hi_respone_func_sub_4071FD为单击"验证"控件消息响应函数;
nt __thiscall Hi_respone_func_sub_4071FD(void*this){
void*v1;// esi
int result;// eax
v1=this;
Hi_update_true_sub_40B781(1);
result=Hi_CheckKey_sub_406FC3(v1);
switch(result){
case 1:
return Hi_show_msg_sub_40B71C((LPCWSTR)&word_44BE10,&Caption,0);//状态:成功
case 0:
return Hi_show_msg_sub_40B71C((LPCWSTR)&word_44BE18,&Caption,0);//状态:失败
case 2:
result=Hi_show_msg_sub_40B71C(&Text,&Caption,0);//状态:很遗憾，离成功还差一小步@￥@
break;
}
return result;
}
即校验函数Hi_CheckKey_sub_406FC3需要返回1才算成功，
如何确认Hi_update_true_sub_40B781是update函数?跟进瞧瞧。
主要两处调用
0040B79D call Hi_about_AFX_THREAD_STATE_sub_409430
...
040B7C5 call dword ptr [eax+100h] ; Hi_DDX_sub_406605
[eax+100h]调用目标计算 Hi_DDX_sub_406605 = Dword(0x100+对话框虚表:0044BE44 ??_7Ccm_cubeDlg@@6B@)
函数体部分代码如下
.text:00406609 lea esi, [ecx+98h]
.text:0040660F push esi ; int
.text:00406610 push 3E8h ; nIDDlgItem //CEDit编辑框ID
.text:00406615 push [ebp+arg_0] ; int
.text:00406618 call Hi_get_P1ItemId_toP2Textsub_415AE5
其中Hi_get_P1ItemId_toP2Textsub_415AE5部分代码如下
text:00415B08 call ds:GetWindowTextLengthW
.text:00415B0E lea ecx, [eax+1]
.text:00415B11 push ecx ; nMaxCount
.text:00415B12 mov ecx, [ebp+arg_8]
.text:00415B15 push eax
.text:00415B16 call sub_40D48E
.text:00415B1B push eax ; lpString
.text:00415B1C push edi ; hWnd
.text:00415B1D call ds:GetWindowTextW
即，如果动态调试，常用的断点GetWindowTextW，GetWindowTextA也会断到此处，
同时我们可知成员变量CString Ccm_cubeDlg.m_input_key 地址为 this.+0x98位置
至于3E8h是不是CEDit编辑框ID，觉得有必要证明的画，可以用资源编辑器查看上述得到的
对话框资源ID为66h的资源配置。
至此，我们可以基本确定为我们的UpdateData(True)函数调用，用于更新用户数据到成员变量以便处理。
0x03 抽象衍化-x,y,b,A等基本变换计算矩阵
上面的分析Hi_CheckKey_sub_406FC3命名为CheckKey应该不为过，需要返回1
函数体Hi_CheckKey_sub_406FC3有两个末端分支返回1,(其中ret.branch1为烟幕弹，后知后觉，执行逻辑觉得一切)
ret.branch1
.text:00407109 test eax, eax ; ret 0
.text:0040710B jnz short loc_407120
.text:0040710D inc eax ; ok
ret.branch2
.text:004071CA xor eax, eax
.text:004071CC inc eax
回到我们一开始"瞎撞"到的函数调用处
.text:0040700B call Hi_gen_matrix_sub_407307
.text:00407010 mov esi, offset aKanxuecrackme2 ; "KanXueCrackM
跟进Hi_gen_matrix_sub_407307，零碎的初始化实在是太长了，以至于被我们"瞎撞"到，
IDA与Windbg配合启动IDA调试，断点在函数完成开头的初始化处
...
.text:00407F3A mov [ebp+var_3D0], 2Bh
.text:00407F44 mov [ebp+var_3CC], ebx
.text:00407F4A mov edx, edi
.text:00407F4C sub ecx, edi
.text:00407F4E mov [ebp+loc_cpyP1_thenCnt], 30h //断点位置
紧接着是个小循环，次数loc_cpyP1_thenCnt=0x30,(loc_cpyP1_thenCnt被编译器复用为计数器，原为函数参数1)
.text:00407F58 loc_407F58:
.text:00407F58 mov ebx, [ecx+edx]
.text:00407F5B mov [edx], ebx
.text:00407F5D mov [edx+0C0h], ebx
.text:00407F63 add edx, eax
.text:00407F65 dec [ebp+loc_cpyP1_thenCnt]
.text:00407F6B jnz short short loc_407F58
该循环复制实现数据复制功能，
00407E38 mov edi, [ebp+loc_cpyP1_thenCnt] //此处loc_cpyP1_thenCnt为函数参数1，)
00407E3E lea ecx, ecx, [ebp+var_244]
...
00407F4A mov edx, edi
00407F4C sub ecc
参数1为Hi_CheckKey_sub_406FC3的局部变量指针，类型初步定为结构体，假定为
base_matrixes{...};
memcpy(&base_matrixes,&var_244,4*0x30)
memcpy(&base_matrixes+0xC0,&var_244,4*0x30)
即得到
base_matrixes{
.+0x00h.y cbSize:0xC0 = 0x30*4
.+0xC0h.x cbSize:0xC0 = 0x30*4
};
即x,y矩阵数据来自于局部变量var_244，地址为 loc_244 = ebp-0x244
在断点处,通过执行以下IDAPython脚本，可以得到y,x矩阵，
#------- ------- ------- ------- ------- ------- -------
def print_mat(mat_ea):
for i in xrange(0,0x30):
print "0x{:08X},".format(Dword(mat_ea+i*4)),
if (i+1)%8==0:
print ""
print_mat(loc_244)#loc_244替换为实际运行地址
#------- ------- ------- ------- ------- ------- -------
得到的x,y矩阵当做1*0x30一维向量看待
0x00000000, 0x00000001, 0x00000002, 0x00000003, 0x00000004, 0x00000005, 0x00000006, 0x00000007,
0x00000008, 0x00000009, 0x0000000A, 0x0000000B, 0x0000000C, 0x0000000D, 0x0000000E, 0x0000000F,
0x00000010, 0x00000011, 0x00000012, 0x00000013, 0x00000014, 0x00000015, 0x00000016, 0x00000017,
0x00000018, 0x00000019, 0x0000001A, 0x0000001B, 0x0000001C, 0x0000001D, 0x0000001E, 0x0000001F,
0x00000020, 0x00000021, 0x00000022, 0x00000023, 0x00000024, 0x00000025, 0x00000026, 0x00000027,
0x00000028, 0x00000029, 0x0000002A, 0x0000002B, 0x0000002C, 0x0000002D, 0x0000002E, 0x0000002F,
函数Hi_gen_matrix_sub_407307再往下就是A0,A1,A2,A3,A4,A5六个矩阵的产生，
其分别来自于局部变量b0,b1,b2,b3,b4,b5六个矩阵与x矩阵的运算，如下
base_matrixes{
.+0000h.y cbSize:0xC0 = 0x30*4; from loc_244 = ebp-0x244
.+00C0h.x cbSize:0xC0 = 0x30*4; from loc_244 = ebp-0x244
.+0180h.A0 cbSize:0x2400 = 0x30*0x30*4; from b0 = loc_3C4 = ebp-0x3C4 //00407F86 mov edx, [ebp+ecx*4+var_3C4]
.+2580h.A1 cbSize:0x2400 = 0x30*0x30*4; from b1 = loc_C4 = ebp-0xC4 //00407FBF mov edx, [ebp+ecx*4+var_C4]
.+4980h.A2 cbSize:0x2400 = 0x30*0x30*4; from b1 = loc_184 = ebp-0x184 //00407FF8 mov edx, [ebp+ecx*4+var_184]
.+6D80h.A3 cbSize:0x2400 = 0x30*0x30*4; from b1 = loc_304 = ebp-0x304 //00408031 mov edx, [ebp+ecx*4+var_304]
.+9180h.A4 cbSize:0x2400 = 0x30*0x30*4; from b1 = loc_544 = ebp-0x544 //0040806C mov edx, [ebp+ecx*4+var_544]
.+B580h.A5 cbSize:0x2400 = 0x30*0x30*4; from b1 = loc_544 = ebp-0x544 //004080A7 mov edx, [ebp+ecx*4+var_484]
};
即在断点处，我们可以执行print_mat(loc_xxx_of_b)得到b0,b1,b2,b3,b4,b5矩阵
其中loc_xxx_of_b在断点处置换为实际地址值:
ebp-0x3C4、ebp-0xC4、ebp-0x184、ebp-0x304、 ebp-0x544、 ebp-0x544
同理，我们可以在函数Hi_gen_matrix_sub_407307完成 base_matrixes 初始化后，
提取M = [A0,A1,A2,A3,A4,A5]六个基本变换矩阵的值，
这里我们断点选择在下述该函数返回位置
00407010 mov esi, offset aKanxuecrackme2 ; "KanXueCrackMe2017"
这时，由输出参数1的计算
00407004 lea eax, [ebp+var_D9F4_base_matrixes]
我们可以得到base_matrixes的实际地址 loc_base_matrixes = ebp-0xD9F4
在断点处，通过下述IDAPython脚本，我们可以一次提取 base_matrixes 的八个矩阵
为python可以直接加载导入的py脚本 base_matrixes.py
#------- ------- ------- ------- ------- ------- -------
def dumpBaseMat2File(base_matrixes_addr = 0x012F1968):
with open(r'.\base_matrixes.py','wb') as outf:#这里文件生成在IDA目录，可改成我们喜欢的目录，后面用到
wd = [i for i in xrange(0,0x30)]
#
outf.write("from numpy import *\n")
outf.write("My=array([")
for i in wd:
outf.write("0x{:08X}, ".format(Dword(base_matrixes_addr+0x00+i*4)))
outf.write('])\n\n')
#
outf.write("Mx=array([")
for i in wd:
outf.write("0x{:08X}, ".format(Dword(base_matrixes_addr+0xC0+i*4)))
outf.write('])\n\n')
#
outf.write("M0=array([")
for i in xrange(0,6):
for L in wd:
#outf.write("{:02X} ".format(wd.index(L)))
outf.write("[")
for C in wd:
outf.write("0x{:08X}, ".format(Dword(base_matrixes_addr+0x180+0x2400*i+(0x30*L+C)*4)))
outf.write('],\n ')
outf.write(' ])\n')
if i <= 4:
outf.write('M{}=array(['.format(i+1))
dumpBaseMat2File(替换为断点处的实际地址值:ebp-0xD9F4)
#------- ------- ------- ------- ------- ------- -------
#有了基本的八个矩阵 base_matrixes.py ，根据验证机制，我们就可以进行相关的破解工作，
#这部分可以在IDA以外的python环境，也可以在IDAPython进行
#cmd切换至 base_matrixes.py 所在目录，启动python，加载矩阵数据
from numpy import *
from base_matrixes import *
A0=mat(M0)
A1=mat(M1)
A2=mat(M2)
A3=mat(M3)
A4=mat(M4)
A5=mat(M5)
M=[A0,A1,A2,A3,A4,A5]
x = mat(Mx)
y = x.copy()
#------- ------- -------
ci = [chr(c) for c in xrange(ord('0'),ord('9')+1)]
cA = [chr(c) for c in xrange(ord('A'),ord('Z')+1)]
ca = [chr(c) for c in xrange(ord('a'),ord('z')+1)]
n62BaseSet = ''.join(ci+cA+ca)
def n62str2val(n62str='KanXueCrackMe2017'):
'''函数将62进制字符串转换为真值'''
global n62BaseSet
n62_radix = 62
val = 0
iWeight = 1
for n62ch in n62str:
val += (n62BaseSet.index(n62ch)*iWeight)
iWeight *= n62_radix
return val
def val2n62str(val=None):
'''函数将真值转换为62进制字符串'''
global n62BaseSet
n62_radix = 62
n62str_L2H = ''
while True:
n62str_L2H += n62BaseSet[val % n62_radix]
val = val / n62_radix
if val <= 0:
break
return n62str_L2H
#------- ------- -------
n18BaseSet = '0123456789ABCDEFGH'
def n18str2val(n18str='EDAHE450C741GH441E11BH84'):
'''函数将18进制字符串转换为真值'''
global n18BaseSet
n18_radix = 18
val = 0
iWeight = 1
for n18ch in n18str:
val += (n18BaseSet.index(n18ch)*iWeight)
iWeight *= n18_radix
return val
def val2n18str(val=None):
'''函数将真值转换为18进制字符串'''
global n18BaseSet
n18_radix = 18
n18str_L2H = ''
while True:
n18str_L2H += n18BaseSet[val % n18_radix]
val = val / n18_radix
if val <= 0:
break
return n18str_L2H
#------- ------- -------
def n18str2mits(n18str = "EDAHE450C741GH441E11BH84"):
''''
本函数将18进制字符串表示的变换展开为基本A矩阵依次相乘变换的表示方式，
以A矩阵在M中的索引表示，如A1*A0*A3*A0*A0,则返回 "10300"
这里会将Ai^e展开
'''
n18s2n = "0123456789ABCDEFGH"
mits = ""
for n18c in n18str:
v = n18s2n.index(n18c)
mi = "012345"[v/3] #得到Ai在M中的索引i
mt = (v % 3) + 1 #得到Ai指数e，即重复次数t
mit = mi*mt
mits += mit #追加
return mits
def mits2n18str(mits = "4444433555444111110422110055555111100444000033355522211"):
'''
本函数执行与n18str2mits相反的操作，
但应主要到，我们只保证得到变换计算产生等价的18进制字符串，
而不是转为原来一模一样的18进制字符串
变换等价是指：
如18进制E，其对应的i=0x0E/3=4,e=t=0x0E/3+1=3,即变换为 A4*A4*A4
表示变换的mits字符串为"444"
这时,18进制"CCC"中每个C,都表示一个A4变换，即"CCC"变换为A4*A4*A4
即18进制字符串"E"与"CCC"相对变换是等价的，但他们的真值是不一样的
这里只针对变换等价而言
实际上n18str2mits相当于展开
'''
n18_radix = 18
val = 0
iWeight = 1
for mop in mits:
val += ((int(mop)*3)*iWeight)
iWeight *= n18_radix
return val2n18str(val)
#先看看正变换'KanXueCrackMe2017'表示的矩阵乘积
tran_val = n62str2val('KanXueCrackMe2017')
tran_18str = val2n18str(tran_val)
#即得到正变换tran_18str的18进制字符串为'EDAHE450C741GH441E11BH84'
tran_mits = n18str2mits(tran_18str)
#我们得到正变换依次变换计算的矩阵在M中的索引序列tran_mits为'4444433555444111110422110055555111100444000033355522211'
#其表示tran = M[4]*M[4]*M[4]*M[4]*M[4]*M[3]*M[3]*M[5]*M[5]*M[5]*M[4]*M[4]*M[4]*M[1]*M[1]*M[1]*M[1]*M[1]*M[0]*M[4]*M[2]*M[2]*M[1]*M[1]*M[0]*M[0]*M[5]*M[5]*M[5]*M[5]*M[5]*M[1]*M[1]*M[1]*M[1]*M[0]*M[0]*M[4]*M[4]*M[4]*M[0]*M[0]*M[0]*M[0]*M[3]*M[3]*M[3]*M[5]*M[5]*M[5]*M[2]*M[2]*M[2]*M[1]*M[1]
#即tran = A4*A4*A4*A4*A4*A3*A3*A5*A5*A5*A4*A4*A4*A1*A1*A1*A1*A1*A0*A4*A2*A2*A1*A1*A0*A0*A5*A5*A5*A5*A5*A1*A1*A1*A1*A0*A0*A4*A4*A4*A0*A0*A0*A0*A3*A3*A3*A5*A5*A5*A2*A2*A2*A1*A1
#numpy中，A.I表示A的逆矩阵
#即根据矩阵的性质，上述正变换的逆变换矩阵
#tranI = A1.I*A1.I*A2.I*A2.I*A2.I*A5.I*A5.I*A5.I*A3.I*A3.I*A3.I*A0.I*A0.I*A0.I*A0.I*A4.I*A4.I*A4.I*A0.I*A0.I*A1.I*A1.I*A1.I*A1.I*A5.I*A5.I*A5.I*A5.I*A5.I*A0.I*A0.I*A1.I*A1.I*A2.I*A2.I*A4.I*A0.I*A1.I*A1.I*A1.I*A1.I*A1.I*A4.I*A4.I*A4.I*A5.I*A5.I*A5.I*A3.I*A3.I*A4.I*A4.I*A4.I*A4.I*A4.I
#应当注意到，tranI的矩阵顺序与tran相反，其根本原因是x*A1*A2*A2.I=x*A1;x*A1*A2*A2.I*A1.I=x*A1*A1.I=x;
#得到了逆变换矩阵tranI，下一步我们就要消除逆变换中的各矩阵的逆矩阵A.I
#又因为测试发现以下规律
Mits_LL = [] #Mits_LL为18进制字符能表示的同一矩阵的操作m^1=m,m^2 = m*m, m^3 = m*m*m
for m in M:
Mits_LL.append(m)
Mits_LL.append(m*m)
Mits_LL.append(m*m*m)
def get_mit(mi):
'''函数返回一个矩阵是否能用A矩阵的e次方表示，表输出表示A矩阵e次方的18进制字符值'''
global Mits_LL
for i in xrange(0,Mits_LL.__len__()):
if (mi==Mits_LL[i]).min():
#print i/3,i%3,"0123456789ABCDEFGH"[i]
print ">> A{}^{} '{}'".format(i/3,i%3+1,"0123456789ABCDEFGH"[i])
#因为我们要用A表示A.I，所以依次搜寻各矩阵的逆矩阵的A表示方法
for i in xrange(0,6):
Ai = M[i]
print "A{}.I ==".format(i),
get_mit(Ai.I
得到输出
A0.I == >> A0^3 '2'
A1.I == >> A1^3 '5'
A2.I == >> A2^3 '8'
A3.I == >> A3^3 'B'
A4.I == >> A4^3 'E'
A5.I == >> A5^3 'H'
AiI_to_n18ch = {
"0":"2",
"1":"5",
"2":"8",
"3":"B",
"4":"E",
"5":"H",
}
即矩阵A的逆矩阵A.I可以用矩阵A的三次方表示，
我们直接用对应的18进制字符表示
于是我们可以通过以下方式得到 tranI_n18str
#'4444433555444111110422110055555111100444000033355522211'[::-1] 为
#'1122255533300004440011115555500112240111114445553344444' 的意思
tranI_n18str=''
for mop in '4444433555444111110422110055555111100444000033355522211'[::-1]:#tran_mits[::-1]
tranI_n18str+=AiI_to_n18ch[mop]
#得到 tranI_n18str = '55888HHHBBB2222EEE225555HHHHH225588E255555EEEHHHBBEEEEE'
通过 keyx = val2n62str(n18str2val(tranI_n18str)) 我们就可以得到一个满足逆变换的keyx
'JImqPA7ty2rRE6Ojb2FpStfgGk8pfCsHXnsSgz6'
但长度明显太长（不等于要求的0x0C)
我们需要对tranI_n18str = '55888HHHBBB2222EEE225555HHHHH225588E255555EEEHHHBBEEEEE'化简，
即变换为矩阵运算等效的更小的18进制值，这操作需要将多个矩阵的乘积结果简化
我们定义下述函数，
#----------------------------------------
def getNm(ch,n):
v = "0123456789ABCDEFGH".index(ch)
mi = v/3
mt = (v%3)+1
#print '*'.join(["(A{}^{})".format(mi,mt) for i in xrange(0,n)])
print "{} means (A{}^{})".format(ch,mi,mt)
#print "get_mit({})".format('*'.join(["A{}".format(mi) for i in xrange(mt*n)]))
for m in xrange(2,n+1):
evalstr = "get_mit({})".format('*'.join(["A{}".format(mi) for i in xrange(mt*m)]))
print ”{}\t".format(ch*m),evalstr,
eval(evalstr)
#----------------------------------------
其用于列举出重复18进制字符代表的矩阵乘积的可能简化结果
如getNm('5',2)我们会得到输出
#----------------------------------------
5 means (A1^3)
55 get_mit(A1*A1*A1*A1*A1*A1) >> A1^2 '4'
#----------------------------------------
其表示"5"代表A1^3乘积,我们第二参数提供2,即最多连续两个55的操作，
第二行输出告诉我们"55"表示A1*A1*A1*A1*A1*A1矩阵乘积，可以用"4"表示等效操作A1^2
即
55888HHHBBB2222EEE225555HHHHH225588E255555EEEHHHBBEEEEE
可化简为
4888HHHBBB2222EEE225555HHHHH225588E255555EEEHHHBBEEEEE
我们当然可以将其他地方的两个55也替换为4进行化简，但先不急，
我们再看后面接着的3个8,执行getNm('8',3)
#----------------------------------------
8 means (A2^3)
88 get_mit(A2*A2*A2*A2*A2*A2) >> A2^2 '7'
888 get_mit(A2*A2*A2*A2*A2*A2*A2*A2*A2) >> A2^1 '6'
#----------------------------------------
即我们既可只将2个8化简为1个7，即888化简为 78 或 87
也可以直接将888化简为6，我们姑且取最大简化,将888化简为6得到
46HHHBBB2222EEE225555HHHHH225588E255555EEEHHHBBEEEEE
以此类推，将多个连续相同的18进制操作化简最终可得到以下四种情况，
为何会出现四种情况？
那是因为在化简4个2时，执行getNm('2',4)，我们得到
#----------------------------------------
2 means (A0^3)
22 get_mit(A0*A0*A0*A0*A0*A0) >> A0^2 '1'
222 get_mit(A0*A0*A0*A0*A0*A0*A0*A0*A0) >> A0^1 '0'
2222 get_mit(A0*A0*A0*A0*A0*A0*A0*A0*A0*A0*A0*A0)
#----------------------------------------
即我们最多只能将其中3个2化简为一个0，所以2222可以化简为02或20，就出现两种
同理，在化简4个5时，我们只能简化为53或35
#----------------------------------------
5 means (A1^3)
55 get_mit(A1*A1*A1*A1*A1*A1) >> A1^2 '4'
555 get_mit(A1*A1*A1*A1*A1*A1*A1*A1*A1) >> A1^1 '3'
5555 get_mit(A1*A1*A1*A1*A1*A1*A1*A1*A1*A1*A1*A1)
#----------------------------------------
46F902C135H147E25CFAE
46F902C153H147E25CFAE
46F920C135H147E25CFAE
46F920C153H147E25CFAE
至此，我们似乎发现了多解，不放拿看看对应的key是多少
执行val2n62str(n18str2val(‘46F902C135H147E25CFAE’))
得到'8UKd3rHaecSvj0F'
还是太长了，还得进一步化简
#------- ------- ------- -------
我们再定义下述函数，用于枚举多个不同18进制字符组合操作可能的化简操作
上述的getNm只针对相同的字符，实际getNm(ch,n)可以等效getNm2(ch*n)
def getNm2(chs):
Axs = []
for ch in chs:
v = "0123456789ABCDEFGH".index(ch)
mi = v/3
mt = (v%3)+1
Axs += ["A{}".format(mi) for i in xrange(0,mt)]
evalstr = "get_mit({})".format('*'.join(Axs))
print evalstr,
eval(evalstr)
#subLen表示连续字符个数
def simple_subLen(opstr='46F902C135H147E25CFAE',subLen=2):
if subLen < 2:
return
for i in xrange(0,opstr.__len__()-(subLen-1)):
print opstr[i:i+subLen],
getNm2(opstr[i:i+subLen])
print ""
#下面我们以 46F902C135H147E25CFAE 为测试对象，
测试连续两个字符能否化简，如下输出所示，化简不来
执行simple_subLen('46F902C135H147E25CFAE',2)得到
46 get_mit(A1*A1*A2)
6F get_mit(A2*A5)
F9 get_mit(A5*A3)
90 get_mit(A3*A0)
02 get_mit(A0*A0*A0*A0)
2C get_mit(A0*A0*A0*A4)
C1 get_mit(A4*A0*A0)
13 get_mit(A0*A0*A1)
35 get_mit(A1*A1*A1*A1)
5H get_mit(A1*A1*A1*A5*A5*A5)
H1 get_mit(A5*A5*A5*A0*A0)
14 get_mit(A0*A0*A1*A1)
47 get_mit(A1*A1*A2*A2)
7E get_mit(A2*A2*A4*A4*A4)
E2 get_mit(A4*A4*A4*A0*A0*A0)
25 get_mit(A0*A0*A0*A1*A1*A1)
5C get_mit(A1*A1*A1*A4)
CF get_mit(A4*A5)
FA get_mit(A5*A3*A3)
AE get_mit(A3*A3*A4*A4*A4)
我们继续测试3个字符的情形
执行simple_subLen('46F902C135H147E25CFAE',3)
46F get_mit(A1*A1*A2*A5)
6F9 get_mit(A2*A5*A3)
F90 get_mit(A5*A3*A0)
902 get_mit(A3*A0*A0*A0*A0) >> A3^1 '9'
02C get_mit(A0*A0*A0*A0*A4) >> A4^1 'C'
2C1 get_mit(A0*A0*A0*A4*A0*A0)
C13 get_mit(A4*A0*A0*A1)
135 get_mit(A0*A0*A1*A1*A1*A1) >> A0^2 '1'
35H get_mit(A1*A1*A1*A1*A5*A5*A5) >> A5^3 'H'
5H1 get_mit(A1*A1*A1*A5*A5*A5*A0*A0)
H14 get_mit(A5*A5*A5*A0*A0*A1*A1)
147 get_mit(A0*A0*A1*A1*A2*A2)
47E get_mit(A1*A1*A2*A2*A4*A4*A4)
7E2 get_mit(A2*A2*A4*A4*A4*A0*A0*A0)
E25 get_mit(A4*A4*A4*A0*A0*A0*A1*A1*A1)
25C get_mit(A0*A0*A0*A1*A1*A1*A4)
5CF get_mit(A1*A1*A1*A4*A5)
CFA get_mit(A4*A5*A3*A3)
FAE get_mit(A5*A3*A3*A4*A4*A4)
可见，在 46F902C135H147E25CFAE 三个字符有多种化简方案，
实际相邻的两种化简效果一样，即将 46F902C135H147E25CFAE 中的 902C、135H分别化简为9C、1H
得到 46F9C1H147E25CFAE ，根据上述四种可能的成因，实际四种情形都会化简为 46F9C1H147E25CFAE
这时我们得到key为
val2n62str(n18str2val('46F9C1H147E25CFAE'))
输出
'CcLaoE37J45Y'
长度为0x0C，满足条件，测试验证成功
实际破解过程到此已经结束，实际写本文的时候才发现
上面验证成功也有运气成分，为啥？
因为我们看看五个字符的化简情形simple_subLen('46F902C135H147E25CFAE',5)
46F90 get_mit(A1*A1*A2*A5*A3*A0)
6F902 get_mit(A2*A5*A3*A0*A0*A0*A0)
F902C get_mit(A5*A3*A0*A0*A0*A0*A4)
902C1 get_mit(A3*A0*A0*A0*A0*A4*A0*A0)
02C13 get_mit(A0*A0*A0*A0*A4*A0*A0*A1)
2C135 get_mit(A0*A0*A0*A4*A0*A0*A1*A1*A1*A1)
C135H get_mit(A4*A0*A0*A1*A1*A1*A1*A5*A5*A5)
135H1 get_mit(A0*A0*A1*A1*A1*A1*A5*A5*A5*A0*A0) >> A5^3 'H'
35H14 get_mit(A1*A1*A1*A1*A5*A5*A5*A0*A0*A1*A1)
5H147 get_mit(A1*A1*A1*A5*A5*A5*A0*A0*A1*A1*A2*A2)
H147E get_mit(A5*A5*A5*A0*A0*A1*A1*A2*A2*A4*A4*A4)
147E2 get_mit(A0*A0*A1*A1*A2*A2*A4*A4*A4*A0*A0*A0)
47E25 get_mit(A1*A1*A2*A2*A4*A4*A4*A0*A0*A0*A1*A1*A1)
7E25C get_mit(A2*A2*A4*A4*A4*A0*A0*A0*A1*A1*A1*A4)
E25CF get_mit(A4*A4*A4*A0*A0*A0*A1*A1*A1*A4*A5)
25CFA get_mit(A0*A0*A0*A1*A1*A1*A4*A5*A3*A3)
即 46F902C135H147E25CFAE 可化简为 46F902CH47E25CFAE
val2n62str(n18str2val(’46F902CH47E25CFAE‘))
得到的key = ’CAR2KP37J45Y‘也是0x0C长度，却提示差一点，
回看，才发现有个004071AC call Hi_last_check_sub_40680C没注意到
此函数何用？且听有没后续补充
by tritium 2017/11/3 00:03
#------- ------- ------- -------
前文再续，书接上一回，话说...
0x03 矩阵乘积的运算与62或18进制数据内部计算
函数Hi_skip_mul_thepasslock_sub_4084A3的参数1为上述base_matrixes，参数2为62进制字符串
如上分析其中参数2决定A集中的矩阵选择与选择次数，x作为递归计算因子，即作为因子计算并更新为计算结果
参数2依次为"KanXueCrackMe2017"和input_key
base_matrixes{
.+0000h.y
.+00C0h.x
.+0180h.A0
.+2580h.A1
.+4980h.A2
.+6D80h.A3
.+9180h.A4
.+B580h.A5
};
第二次调用是通过使用特权指令抛出异常的方式调用
.text:00407068 and [ebp+ms_exc.registration.TryLevel], 0
.text:0040706C mov [ebp+ms_exc.registration.TryLevel], 1
.text:00407073 int 2Dh ; Windows NT - debugging services: eax = type
.text:00407075 nop
.text:00407076 and [ebp+ms_exc.registration.TryLevel], 0
上述将TryLevel设置为1后产生异常
我们看看函数开头注册的异常处理表Hi_handler_table_stru_452D88
.text:00406FC8 push offset Hi_handler_table_stru_452D88
.text:00406FCD push offset SEH_435C00
.rdata:00452D88 Hi_handler_table_stru_452D88 dd 0FFFFFFE4h ; GSCookieOffset
.rdata:00452D88 ; DATA XREF: Hi_CheckKey_sub_406FC3+5↑o
.rdata:00452D88 dd 0 ; GSCookieXOROffset ; SEH scope table for function 406FC3
.rdata:00452D88 dd 0FFFF25E4h ; EHCookieOffset
.rdata:00452D88 dd 0 ; EHCookieXOROffset
.rdata:00452D88 dd 0FFFFFFFEh ; ScopeRecord.EnclosingLevel
.rdata:00452D88 dd offset loc_407135 ; ScopeRecord.FilterFunc
.rdata:00452D88 dd offset loc_40717D ; ScopeRecord.HandlerFunc
.rdata:00452D88 dd 0 ; ScopeRecord.EnclosingLevel
.rdata:00452D88 dd 0 ; ScopeRecord.FilterFunc
.rdata:00452D88 dd offset nullsub_1 ; ScopeRecord.HandlerFunc
即TryLevel=1的异常处理分支为 loc_40717D，这里读Hi_skip_mul_thepasslock_sub_4084A3
进行二次调用，以input_key为参数2进行逆变换
.text:0040717D loc_40717D:
.text:0040717D mov esp, [ebp+ms_exc.old_esp]
.text:00407180 lea eax, [ebp+loc_inputkey]
.text:00407183 push eax
.text:00407184 lea eax, [ebp+var_D9F4_base_matrixes]
.text:0040718A push eax
.text:0040718B call Hi_skip_mul_thepasslock_sub_4084A3
可以在下述调用int 20处断点断下，直接修改EIP到上述tryLevel=1处理分支loc_40717D即可,
00407073 int 2Dh
或在loc_40717D处理分支断点，将int 2Dh产生的异常抛回去给程序处理
#------- ------- ------- -------
int 2Dh 之后的烟幕弹是对input_key用函数 Hi_base64_b64encode_sub_4031E6
进行 0x3E8=1000次base64加密，然后要求结果等于"Vm0wd2QyUXlVWGw=="
这真的可能吗？简单测试下"Vm0wd2QyUXlVWGw=="能否进行1000次解码试试就知道。
0x04 512位绝对值的符号整数 int512_t
在矩阵变换函数 Hi_skip_mul_thepasslock_sub_4084A3 中
其调用Hi_step_62_to_18_sub_40829C函数将输入的62进制字符串转换为18进制字符串
内部中介存放真值是支持512位绝对值的符号整数 int512_t
逆向模拟的int512_t内存结构如下
#------- ------- ------- -------
#pragma pack(push)
#pragma pack(4)
union data_type_L2H{
unsigned char uc[512/(sizeof(unsigned char)*8)];
unsigned int ui[512/(sizeof(unsigned int)*8)];
}
struct int512_t{
data_type_L2H m_data;
bool m_sign;
unsigned int m_limuis;
}
#pragma pack(pop)
#------- ------- ------- -------
int512_t{
.+00h m_data cbSize:0x40
.+40h m_sign cbSize:0x01 //align 4
.+44h m_limuis cbSize:0x04 //align 4
}
int512_t相关的一些成员函数如下，命名之初，int512_t标记为 L48，0x48为sizeof(int512_t)
Hi_L48_esi_ctor_Iebx_sub_403641 //(int512_t)esi=(int)ebx 赋值
Hi_L48_ebx_eq_P1_mul_ecx_sub_4038E1 //(int512_t)ebx=(int512_t)Param1*(int512_t)ecx 乘法
Hi_L48_P1_eq_eax_add_P2_sub_40447F //(int512_t)Param1=(int512_t)eax+(int512_t)Param2 加法
Hi_L48_ecx_eq_ecx_mul_edx_retP1_sub_404669 //(int512_t)ecx*=(int512_t)edx; Param1 = ecx; 二元乘法 *=
Hi_L48_edx_eq_ecx_mod_P1_sub_403F83 //(int512_t)edx=(int512_t)ecx % (int512_t)Param1 取余，则除余
Hi_L48_edx_eq_ecx_div_P1_sub_403A78 //(int512_t)edx=(int512_t)ecx / (int512_t)Param1 取商，则除商
进入 Hi_last_check_sub_40680C分析部分，我们还可以得到
Hi_L48_esi_ctor_0_sub_403625 //构造赋值0
Hi_L48_esi_eq_eax_add_P1_sub_403764 //加法 余上述操作数不一样
Hi_L48_esi_eq_edi_sub_P1_sub_4037EB//减法
Hi_L48_ecx_eq_P1_mul_P1_sub_404D61 //平方
待续...
空置太久，事情繁多，也就没由继续，在继续下去对个人而言意义不大，
对吃瓜群众而言，想了解ECC还不如找个开源代码研究下，有闲情逸志才回来对比下，
检验函数大面积的有效代码都是为了初始化不同大数从而构建ECC参数而设。
如edi=8,ebx=1参数产生的大数
8:1 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
-----------------------------------
我们在IDA定义下述大数结构
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
赞赏
- hfs与nginx的duplicate header line冲突 1284
- [原创] 第四届“网鼎杯”网络安全大赛——赛前模拟训练（全部） 3907
- [原创] Win11 VMP 源码编译 8174
- Win11 hashcat 编译 3478
- [原创]Frida编译2022 11547
