金山杯第一阶段第一题分析
原始文件没有加壳，使用IDA加载文件，并手动加载Sig文件Microsoft VisualC 2-8/net runtime。
程序入口点代码为
.text:00400522 public start
.text:00400522 start proc near
.text:00400522 push 0 ; lpModuleName
.text:00400524 call GetModuleHandleA
.text:0040052A push 0 ; dwInitParam
.text:0040052C push offset DialogFunc ; lpDialogFunc
.text:00400531 push 0 ; hWndParent
.text:00400533 push 65h ; lpTemplateName
.text:00400535 push eax ; hInstance
.text:00400536 call DialogBoxParamA ; Create a modal dialog box from a
.text:00400536 ; dialog box template resource
.text:0040053C retn
.text:0040053C start endp
整个程序只有一个Dialog，处理函数为400437处的DialogFunc,Dialog的处理函数原形为
INT_PTR CALLBACK DialogProc( HWND hwndDlg,
UINT uMsg,
WPARAM wParam,
LPARAM lParam
);
对照原形修改400437处对应函数参数设定。以下对程序DialogFunc的代码进行详细的分析
.text:00400437 DialogFunc proc near ; DATA XREF: start+A o
.text:00400437
.text:00400437 var_1018= dword ptr -1018h
.text:00400437 String= byte ptr -14h
.text:00400437 hwndDlg= dword ptr 8
.text:00400437 uMsg= dword ptr 0Ch
.text:00400437 wParam= dword ptr 10h
.text:00400437 lParam= dword ptr 14h
.text:00400437
.text:00400437 push ebp
.text:00400438 mov ebp, esp
.text:0040043A mov eax, 1018h
.text:0040043F call __alloca_probe ;在栈上分配局部变量空间
.text:00400444 and [ebp+String], 0 ；初始化String为0,[ebp-14h]
.text:00400448 push ebx
.text:00400449 push esi
.text:0040044A push edi
.text:0040044B xor eax, eax
.text:0040044D lea edi, [ebp-13h] ;IDA未能识别出的变量,[ebp-13h]
.text:00400450 stosd ;edi指向的4个字节初始化为0
.text:00400451 stosd ;edi指向的4个字节初始化为0
.text:00400452 and byte ptr [ebp+var_1018], 0 ;初始化var_1018第一个字节为0
.text:00400452 ;[ebp-1018h]
.text:00400459 mov ecx, 400h ;设置00400476处stosd指令的执行次数
.text:0040045E stosd ;edi指向的4个字节初始化为0
.text:0040045F stosd ;edi指向的4个字节初始化为0
.text:00400460 xor eax, eax
.text:00400462 cmp [ebp+uMsg], 111h;判断消息是否是WM_COMMAND
.text:00400469 lea edi, [ebp+var_1018+1] ;edi指向var_1018第2个字节
.text:0040046F mov ebx, 13572468h ;设置ebx初始值
.text:00400474 rep stosd ;填充var_1018+1开始的4096字节为0
.text:00400476 jnz loc_400519 ;消息不是WM_COMMAND
根据这一段分析的变量初始化，可以知道var_1018为一个长度为4097字节的字节数组，String为一个长度为17字节的字节数组，并且以上两个数组的内容都被初始化为0，因此修改IDA分析结果中的对应局部变量为指定长度的字节数组。
继续向下进行
.text:00400493 mov esi, GetDlgItemTextA
.text:00400499 lea eax, [ebp+String]
.text:0040049C push 10h ; nMaxCount 最大长度
.text:0040049E push eax ; lpString 缓存指针
.text:0040049F push 3E9h ; nIDDlgItem 输入用户名的Edit
.text:004004A4 push [ebp+hwndDlg] ; hDlg
.text:004004A7 call esi ; GetDlgItemTextA
.text:004004A9 test eax, eax
.text:004004AB jz short loc_400519 ;取得的长度为0则跳
.text:004004AD lea eax, [ebp+var_1018]
.text:004004B3 push 1000h ; nMaxCount最大长度
.text:004004B8 push eax ; lpString 缓存指针
.text:004004B9 push 3EAh ; nIDDlgItem输入注册号的Edit
.text:004004BE push [ebp+hwndDlg] ; hDlg
.text:004004C1 call esi ; GetDlgItemTextA
.text:004004C3 test eax, eax
.text:004004C5 jz short loc_400519 ;取得的长度为0则跳
分析过这一段之后可以知道String为用户名字符串的数组，var_1018为注册号的数组，修改变量的名字为szName和szKey。
.text:004004C7 lea edi, [ebp+szName] ;edi指向szName
.text:004004CA or ecx, 0FFFFFFFFh
.text:004004CD xor eax, eax
.text:004004CF xor edx, edx
.text:004004D1 repne scasb
.text:004004D3 not ecx
.text:004004D5 dec ecx ;以上代码为计算szName长度
.text:004004D6 test ecx, ecx
.text:004004D8 jle short loc_4004FD
.text:004004DA
.text:004004DA loc_4004DA: ; CODE XREF: DialogFunc+C4 j
.text:004004DA movsx eax, byte ptr [ebp+edx+szName];保留符号位扩展字节为双字
.text:004004DF add eax, ebx
.text:004004E1 imul eax, 3721273h
.text:004004E7 add eax, 24681357h
.text:004004EC mov esi, eax
.text:004004EE shl esi, 19h ;左移0x19位
.text:004004F1 sar eax, 7 ;算术右移0x7位
.text:004004F4 or esi, eax
.text:004004F6 inc edx
.text:004004F7 cmp edx, ecx
.text:004004F9 mov ebx, esi
.text:004004FB jl short loc_4004DA ;继续计算下一个字节
这个部分代码的功能是循环计算szName的每个字节生成一个32位的双字，这部分代码转换为C代码为：
//初始值
int iNameKey=0x13572468;
for (i = 0;i < strlen(szName);i++)
{
j=((iNameKey + szName[i]) * 0x3721273) + 0x24681357;
//有符号整数右移，SAR
iNameKey=(j >> 7) | (j << 0x19);
}
继续
.text:004004FD loc_4004FD: ; CODE XREF: DialogFunc+A1 j
.text:004004FD lea eax, [ebp+szKey]
.text:00400503 push eax ;指向szKey的指针
.text:00400504 push ebx ;iNameKey
.text:00400505 call sub_4002CC ;关键比较调用
.text:0040050A pop ecx
.text:0040050B pop ecx
.text:0040050C jmp short loc_400519;调到函数结束
这部分没什么可说的，继续进入sub_402CC
.text:004002CC push ebp
.text:004002CD mov ebp, esp
.text:004002CF sub esp, 128h
.text:004002D5 and byte ptr [ebp+var_24], 0 ;设置var_24的第一个字节为0,
.text:004002D9 push ebx
.text:004002DA push esi
.text:004002DB push edi
.text:004002DC xor eax, eax
.text:004002DE lea edi, [ebp+var_24+1] ;edi指向var24+1处
.text:004002E1 stosd ; edi处4个字节为0,edi=edi+4
.text:004002E2 and [ebp+Text], 0 ;设置Text第一字节为0,ebp-0x128
.text:004002E9 push 40h
.text:004002EB stosd ; edi处4个字节为0,edi=edi+4
.text:004002EC stosb ; edi处1个字节为0,edi=edi+1
.text:004002ED pop ecx ;设置4002FA处指令stosd执行次数
.text:004002EE xor eax, eax
.text:004002F0 lea edi, [ebp-127h] ;edi指向ebp-0x127,即Text+1处
.text:004002F6 or [ebp+var_C], 0FFh ;设置var_c的第一字节为0xFF
.text:004002FA rep stosd ;设置edi指向的256字节为0
.text:004002FC or [ebp+var_18], 0FFh ;设置var_18的第一字节为0xFF
.text:00400300 or ecx, 0FFFFFFFFh
.text:00400303 stosw ; 设置edi指向的2字节为0,edi=edi+2
.text:00400305 stosb ; 设置edi指向的1字节为0,edi=edi+1
.text:00400306 mov edi, [ebp+lpszKey];edi指向输入的注册号
.text:00400309 xor eax, eax
.text:0040030B repne scasb
.text:0040030D not ecx
.text:0040030F push 1
.text:00400311 dec ecx ;取得注册号长度保存在ecx中
.text:00400312 pop ebx ;设置ebx为1
.text:00400313 mov byte ptr [ebp-0Bh], 63h;IDA未正确分析出的变量,数组第二个字节
.text:00400317 mov [ebp+var_A], 0FBh
.text:0040031B mov [ebp+var_9], 9Ah
.text:0040031F mov [ebp+var_8], 3
.text:00400323 mov [ebp+var_7], 0A3h
.text:00400327 mov [ebp+var_6], 0DAh
.text:0040032B mov [ebp+var_5], 72h
.text:0040032F mov [ebp+var_4], 0FEh
.text:00400333 mov [ebp+var_3], 0C9h
.text:00400337 mov [ebp+var_2], 0B7h
.text:0040033B mov byte ptr [ebp-17h], 6Ah;IDA未正确分析出的变量,数组第二个字节
.text:0040033F mov [ebp+var_16], 0D1h
.text:00400343 mov [ebp+var_15], 0D2h
.text:00400347 mov [ebp+var_14], 4Eh
.text:0040034B mov [ebp+var_13], 82h
.text:0040034F mov [ebp+var_12], 0DAh
.text:00400353 mov [ebp+var_11], 72h
.text:00400357 mov [ebp+var_10], 0FEh
.text:0040035B mov [ebp+var_F], 0C9h
.text:0040035F mov [ebp+var_E], 0B7h
这部分代码也是完成局部变量的初始化过程，分析后可以知道Text为260字节的字节数组，var_24为10字节的字节数组，var_C和var_18是两个11字节的字节数组，第一个字节为0xFF，结合后面对这两个变量的引用，可以分析出这两个数组中保存的是编码后的注册成功和注册失败字符串，引用位置和解码函数如下：
.text:004003FC lea eax, [ebp+MsgText]
.text:00400402 push eax
.text:00400403 lea eax, [ebp+szOK] ;注册成功字符串
.text:00400406
.text:00400406 loc_400406: ; CODE XREF: TestKey+169 j
.text:00400406 push eax
.text:00400407 call sub_400240 ;字符串解码函数，简单的XOR
.text:0040040C pop ecx
.text:0040040D lea eax, [ebp+MsgText]
.text:00400413 pop ecx
.text:00400414 push 0 ; uType
.text:00400416 push offset Caption ; lpCaption
.text:0040041B push eax ; lpText
.text:0040041C push 0 ; hWnd
.text:0040041E call MessageBoxA ;显示提示
.text:00400424 pop edi
.text:00400425 mov eax, ebx
.text:00400427 pop esi
.text:00400428 pop ebx
.text:00400429 leave
.text:0040042A retn
.text:0040042B ; ---------------------------------------------------------------------------
.text:0040042B
.text:0040042B loc_40042B: ; CODE XREF: TestKey+C2 j
.text:0040042B ; TestKey+CA j ...
.text:0040042B lea eax, [ebp+MsgText]
.text:00400431 push eax
.text:00400432 lea eax, [ebp+szFail] ;注册失败字符串
.text:00400435 jmp short loc_400406
修改对应的变量名称后继续分析
.text:00400363 mov esi, ecx ;ecx为注册号长度，保存到esi中
.text:00400365 mov edi, ebx ;ebx为1，循环控制变量初始值为1
.text:00400367
.text:00400367 loc_400367: ; CODE XREF: TestKey+AC j
.text:00400367 mov eax, [ebp+iNameKey]
.text:0040036A mov ecx, edi
.text:0040036C shr eax, cl
.text:0040036E and al, bl
.text:00400370 mov byte ptr [ebp+edi+var_24], al;设置字节数组的对应位置
.text:00400374 inc edi
.text:00400375 cmp edi, 9
.text:00400378 jl short loc_400367 ;循环控制变量小于9则继续进行循环
.text:0040037A xor edi, edi ;清空edi
.text:0040037C mov byte ptr [ebp+var_24+9], bl;设置字节数组的第九位为1
此部分功能为保存iNameKey的二进制1至8位到var_24数组的1-8位，并设置var_24数组的第9位为1，对应C语言代码如下
//根据由Name计算出的DWORD，初始化Bit数组
abyBits[0]=0;
for (i = 1;i < 9;i++)
{
//无符号数右移 shr
abyBits[i] = ((DWORD)iNameKey >> (i)) & 1;
}
abyBits[9]=1;
继续向下来到最核心的判断部分
.text:0040037F test esi, esi
.text:00400381 jle short loc_4003EE;注册号长度小于等于0则跳
.text:00400383
.text:00400383 loc_400383: ; CODE XREF: TestKey+120 j
.text:00400383 mov eax, [ebp+lpszKey] ;eax指向注册号
.text:00400386 mov al, [edi+eax] ;取注册号的第edi个字节,edi初始值为0
.text:00400389 cmp al, 30h
.text:0040038B mov [ebp+var_1], al ;保存注册号当前要处理的字节到var_1
.text:0040038E jl loc_40042B ;小于’0’则跳
.text:00400394 cmp al, 39h
.text:00400396 jg loc_40042B ;大于’9’则跳
.text:0040039C mov eax, edi
.text:0040039E push 1Fh
.text:004003A0 cdq
.text:004003A1 pop ecx
.text:004003A2 idiv ecx ;循环控制变量除31(0x1F)
.text:004003A2 ;余数保存在edx中
.text:004003A4 mov eax, [ebp+iNameKey]
.text:004003A7 push 0Ah
.text:004003A9 mov ecx, edx ;余数赋给ecx
.text:004003AB xor edx, edx
.text:004003AD shr eax, cl ;iNameKey逻辑右移cl位
.text:004003AF pop ecx
.text:004003B0 div ecx ;右移后的结果除10(0x0A)
.text:004003B0 ;余数保存在edx
.text:004003B2 movsx eax, [ebp+var_1] ;扩展var1到32位
.text:004003B6 lea eax, [edx+eax-30h] ;eax=扩展后的var1+余数-30
.text:004003BA xor edx, edx
.text:004003BC div ecx ;eax除10(0x0A),余数可能为0到9
.text:004003BE cmp edx, ebx ;余数是否为1
.text:004003C0 jnz short loc_4003C7 ;不是则跳
.text:004003C2 xor byte ptr [ebp+var_24+1], bl;edx为1时,var_24数组第一字节
.text:004003C2 ;xor 1,即翻转状态
.text:004003C5 jmp short loc_4003E9
.text:004003C7 ; ---------------------------------------------------------------------------
.text:004003C7
.text:004003C7 loc_4003C7: ; CODE XREF: TestKey+F4 j
.text:004003C7 cmp byte ptr [ebp+edx+MsgText+103h], bl;当edx为0时,会越界判
.text:004003C7 ;断MsgText的最后一个
.text:004003C7 ;字节是否为1,其与情况
.text:004003C7 ;判断var_24数组中的前
.text:004003C7 ;一个字节(edx-1)是否为
.text:004003C7 ;1
.text:004003CB jnz short loc_40042B;不是1则跳到注册失败,MsgText最后一个字节为0
.text:004003CB ; 所以edx不能为0
.text:004003CD lea eax, [edx-2] ;内嵌循环控制变量终止值eax=edx-2
.text:004003D0 mov ecx, ebx ; 内嵌循环控制变量初始时化为1
.text:004003D2 cmp eax, ebx ;eax和1比较
.text:004003D4 jl short loc_4003E1;小于1则跳,即如果edx=2则跳去直接执行翻转
.text:004003D6
.text:004003D6 loc_4003D6: ; CODE XREF: TestKey+113 j
.text:004003D6 cmp byte ptr [ebp+ecx+var_24], bl;判断数组var24的ecx位置字节
.text:004003DA jz short loc_40042B ;为1则跳去失败
.text:004003DC inc ecx ;内嵌循环控制变量加1
.text:004003DD cmp ecx, eax ;是否到了循环终止值
.text:004003DF jle short loc_4003D6 ;不是则继续
.text:004003E1
.text:004003E1 loc_4003E1: ; CODE XREF: TestKey+108 j
.text:004003E1 xor byte ptr [ebp+edx+var_24], bl;翻转数组var_24的edx位置字
.text:004003E1 ;节
.text:004003E5 lea eax, [ebp+edx+var_24]
.text:004003E9
.text:004003E9 loc_4003E9: ; CODE XREF: TestKey+F9 j
.text:004003E9 inc edi;外部循环控制变量加1
.text:004003EA cmp edi, esi;判断是否到了注册号的长度
.text:004003EC jl short loc_400383;没到则继续循环
.text:004003EE
.text:004003EE loc_4003EE: ; CODE XREF: TestKey+B5 j
.text:004003EE mov eax, ebx;初始化eax为1,eax为验证循环控制变量
.text:004003F0
.text:004003F0 loc_4003F0: ; CODE XREF: TestKey+12E j
.text:004003F0 cmp byte ptr [ebp+eax+var_24], bl;判断var_24的eax字节
.text:004003F4 jz short loc_40042B;为1则跳到注册失败
.text:004003F6 inc eax;验证循环控制变量加1
.text:004003F7 cmp eax, 0Ah;是已经判断了9个字节
.text:004003FA jl short loc_4003F0;不是则继续循环
这部分是整个算法的核心部分，所以代码比较长，逻辑也比较复杂。整理后的描述如下：
1、 保存由用户名计算出的32位iNameKey的1至8位到数组var_24的1-8位置，并设置var_24的0位置为0,9位置为1。
2、 对注册号的每个字符进行变换生成一个位置序号,生成算法为
1) 当前处理的字符在注册号中的位置对31取余作为iNameKey右移的位数
2) iNameKey右移后的结果对10取余后加上当前处理字符的ASCII码-0x30
3) 第2步的结果再对10取余作为位置序号
3、 根据位置序号进行判断，如果符合要求就对var_24数组中的对应位置字节进行xor 1，即翻转原始值，如果不符合要求则跳去失败，判断是否符合要求的条件如下
1) 如果位置序号为1，直接进行反转。
2) 如果为其他位置，则首先判断此位置的前一位是否为1，如果是1则符合，继续进行条件3的判断，否则不符合条件，失败。
3) 位置序号如果等于2，则成功，进行翻转，如果位置序号大于2，则还要判断数组的第1位到(序号-2)位是否都是0，如果都是0则符合条件，进行翻转，否则，跳去失败。
4、 循环处完注册号的每一个字节后，var_24数组中的每个字节必须都是0才能注册成功
因此，整个问题变为找到一个位置序列，使用上面的3中的规则顺序处理此序列里的每个数字后var_24数组中原来为的1的位置都变成0，此序列必须满足的条件是，当前处理的序号如果是1，则可以直接进行翻转，如果不是1则需要当前序号的前一位是1而且第一位到此序号-2位都是0才可以进行翻转，所以设置var_24数组中任一位为0的问题就会变成设置它的前一位为1的问题。
举例子说，要设置数组0 0 0 0 0 0 0 0 1的第 9位为1则需要先设置第8位由0变为1，即把数组变为0 0 0 0 0 0 0 1 1，而要使数组第8位由0变为1则需要第7位为1，这是典型的递归求解问题。
求解的方法是只要从数组的成员1开始，对数组的每一字节调用设置为0的递归函数，并记录下翻转顺序就可以得到满足条件的位置序列，生成算法如下：
1) 设置数组中某一位为指定值的递归算法，此函数并未判断第1位到第iPos-2位是否全为0，因此使用时需要调用者保证第1位到第iPos-2位已经为0。
void SetBitValue(PBYTE abyBits,int iPos,BYTE byValue,char *szKey)
{
//abyBits为原始字节数组,iPos为需要设置的位置,byValue为要设置成的值
//szKey用来保存翻转位置序列
char szIndex[2]={0,0};
if (abyBits[iPos] != byValue)
{
if (iPos == 1)
{
//是第一位则直接设置
abyBits[iPos] = byValue;
//添加位置编号到szKey
itoa(iPos,szIndex,10);
strncat(szKey,szIndex,4096);
}
else
{
//其他位
//设置前一位为1
SetBitValue(abyBits,iPos-1,1,szKey);
//设置目的位值
abyBits[iPos] = byValue;
//添加位置编号到szKey
itoa(iPos,szIndex,10);
strncat(szKey,szIndex,4096);
//设置前一位为0
SetBitValue(abyBits,iPos-1,0,szKey);
}
}
}
2) 循环处理数组中的每个位置代码
//计算翻转顺序串
for (i = 1;i < 10;i++)
{
if (abyBits[i] == 1)
{
//由第一位开始按顺序进行处理，保证处理第i位时第1位到第i-2位为0
//此处也可以由第二位开始处理
SetBitValue(abyBits,i,0,szKey);
}
}
得到此翻转序列后，需要对此序列中的每个位置编号根据上面的规则2进行逆运算得到最终的注册号，算法如下：
//初始化偏移数组
for (i = 0;i < 31;i++)
{
//无符号数右移 shr
abyKeyTable[i] = (((DWORD)iNameKey) >> i) % 10;
}
//由翻转顺序串和偏移数组循环计算，得到最终结果
for (i = 0;i < strlen(szKey);i++)
{
szKey[i]=(((szKey[i]-0x30) + 10 - abyKeyTable[i % 31]) % 10) + 0x30;
}
总结：
1、本题的难度主要在于看懂注册号的验证过程，抽象出问题，并找到解决问题的方法。此题是经典的9连环问题，如果之前接触过此类问题，会降低很大难度，如果没接触过，就会在整理算法逻辑上多花一些时间。
2、能完成注册的位置序列并不唯一，所以对应一个用户名的注册号也可以有很多个。
3、以上代码都已经过验证可用但并未进行任何优化。
[课程]Android-CTF解题方法汇总！
不懂,坐地上支持!
