【文章标题】: 一个KeygenMe的算法分析
【文章作者】: yqzouguo
【作者声明】: 只是感兴趣，没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
这个KM使用了几个算法，BASE60、RSA、CRC32。都是很经典的算法。
通过分别计算输入的用户名和序列号，验证是否满足某关系，来验证注册。
一、算法分析
1.使用字符串搜索，很容易就找到关键函数
0040178A . E8 21FEFFFF call 004015B0 ; 关键函数，F7跟进
0040178F . 83C4 04 add esp, 4
00401792 . 85C0 test eax, eax
00401794 . 74 43 je short 004017D9
00401796 . 6A 00 push 0 ; /Style = MB_OK|MB_APPLMODAL
00401798 . 68 BC604000 push 004060BC ; |very good job
0040179D . 68 A8604000 push 004060A8 ; |serial is good! =)
004017A2 . 56 push esi ; |hOwner
004017A3 . FF15 A4504000 call dword ptr [<&USER32.MessageBoxA>>; \MessageBoxA
首先，记着这里保存了4个常量，待会会用到
004015E9 |. C74424 2C D1E>mov dword ptr [esp+2C], 3196E9D1 ; |
004015F1 |. C74424 30 298>mov dword ptr [esp+30], A6838B29 ; |
004015F9 |. C74424 34 787>mov dword ptr [esp+34], 223E7B78 ; |
00401601 |. C74424 38 206>mov dword ptr [esp+38], 10B36420 ; |
记为 cont[4]={3196E9D1,A6838B29,223E7B78,10B36420}
2.序列号计算部分
0040162C |> /8A8C34 640100>/mov cl, byte ptr [esp+esi+164] ; 取序列号一位
00401633 |. |8D8434 640100>|lea eax, dword ptr [esp+esi+164] ; 序列号给eax
0040163A |. |80F9 26 |cmp cl, 26 ; 是否为26h （&）
0040163D |. |75 07 |jnz short 00401646 ; 是 则不做处理
0040163F |. |C607 00 |mov byte ptr [edi], 0
00401642 |. |47 |inc edi
00401643 |. |46 |inc esi
00401644 |. |EB 15 |jmp short 0040165B
00401646 |> |50 |push eax ; 序列号入栈
00401647 |. |E8 A4FEFFFF |call 004014F0 ; Base60编码，算出一个值x
0040164C |. |50 |push eax ; x入栈
0040164D |. |E8 AEFDFFFF |call 00401400 ; 根据值 x 进一步计算，这个call里有两个算法
00401652 |. |83C4 08 |add esp, 8
00401655 |. |8807 |mov byte ptr [edi], al ; 保存上一个函数计算的结果
00401657 |. |47 |inc edi ; 指向下一个位置
00401658 |. |83C6 04 |add esi, 4 ; 计数器+4
0040165B |> |3BF3 |cmp esi, ebx ; 序列号是否处理完
0040165D |.^\7C CD \jl short 0040162C ; 没有，则继续处理
2.1 序列号的每4个字符一组，base60编码，算出X。
call 004014F0
{
004014FF |. 8B11 mov edx, dword ptr [ecx] ; 取4个字符
00401501 |. 884424 07 mov byte ptr [esp+7], al
00401505 |. 884424 08 mov byte ptr [esp+8], al
00401509 |. 56 push esi
0040150A |. 8D4424 08 lea eax, dword ptr [esp+8]
0040150E |. 57 push edi
0040150F |. 50 push eax
00401510 |. 895424 10 mov dword ptr [esp+10], edx
00401514 |. E8 87390000 call 00404EA0 ; 反转4个字符
00401519 |. 83C4 04 add esp, 4
0040151C |. 33F6 xor esi, esi ; esi为局部变量，保存计算结果。初值为0
0040151E |. 8D7C24 0F lea edi, dword ptr [esp+F]
00401522 |. BB 04000000 mov ebx, 4 ; 局部变量 i=4
00401527 |> 0FBE0F /movsx ecx, byte ptr [edi] ; 取第i个字符
0040152A |. 51 |push ecx
0040152B |. E8 A0FFFFFF |call 004014D0 ; 查看该字符位标准字符串中的第j位
00401530 |. 99 |cdq ; 扩展
00401531 |. B9 3C000000 |mov ecx, 3C ; ecx=3C（60）
00401536 |. 83C4 04 |add esp, 4
00401539 |. F7F9 |idiv ecx ; j/3C
0040153B |. 8D0476 |lea eax, dword ptr [esi+esi*2] ; eax=3*esi
0040153E |. 4F |dec edi ; 指向前一个字符
0040153F |. 4B |dec ebx ; i--
00401540 |. 8D0480 |lea eax, dword ptr [eax+eax*4] ; eax=5*eax
00401543 |. 8D3482 |lea esi, dword ptr [edx+eax*4] ; esi=edx+4*eax,edx为该字符的位置/3C的商
00401546 |.^ 75 DF \jnz short 00401527 ; 循环，直到4个字符都计算完
}
使用字符表 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx 进行编码
2.2 将X进一步计算，该函数使用两种算法加密
call 00401400
{
00401416 |. E8 35000000 call 00401450 ; 第一处，RSA算法
0040141B |. 83C4 0C add esp, 0C ; 加密后的值为Y
0040141E |. 8BE8 mov ebp, eax
00401420 |. BF 01000000 mov edi, 1
00401425 |. 33DB xor ebx, ebx ; 以下为第二个算法
00401427 |. B9 80604000 mov ecx, 00406080 ; 此处调用一个数组
0040142C |> 8B31 /mov esi, dword ptr [ecx] ; a[i]
0040142E |. 8BC5 |mov eax, ebp
00401430 |. 33D2 |xor edx, edx ; edx清0
00401432 |. F7F6 |div esi ; Y/a[i]
00401434 |. 85D2 |test edx, edx ; 余数是否为0
00401436 |. 75 04 |jnz short 0040143C ; 若为0，则进行运算
00401438 |. 0BDF |or ebx, edi ; b=b|c (b=0，c初值为1）
0040143A |. 8BE8 |mov ebp, eax ; t=y
0040143C |> 83C1 04 |add ecx, 4 ; 指向数组的下一个元素
0040143F |. 03FF |add edi, edi ; c=2c
00401441 |. 81F9 A0604000 |cmp ecx, 004060A0
00401447 |.^ 7C E3 \jl short 0040142C
}
①RSA算法
跟踪后，可发现
e = 49EFA9h
n = 9401D7h
Y=X^e % n
②第二个算法，使用数组，进行计算
a[8]={2,3,5,7,11,13,16,19} （该数组在406080h处）
使用两个局部变量
b=0 c=1
for(i=0;i<8;i++)
{
if(!Y%a[i])
{
b=b|c;
Y=Y/a[i];
}
c+=c;
}
return (BYTE)b;
这里的b将组成一个4DWORD的数组，为形成最后的值做准备。
2.3 以下形成一个长128bits的值
这里用到了前面保存的常量数组 cont[4]
0040165F |> \8B5424 2C mov edx, dword ptr [esp+2C] ; 取出上一算法的计算结果
00401663 |. 8B4424 30 mov eax, dword ptr [esp+30] ; 保存到新变量中
00401667 |. 8B4C24 34 mov ecx, dword ptr [esp+34] ; 这个值长4个DWORD
0040166B |. 895424 0C mov dword ptr [esp+C], edx ; P0
0040166F |. 8B5424 38 mov edx, dword ptr [esp+38]
00401673 |. 894424 10 mov dword ptr [esp+10], eax ; P1
00401677 |. 894C24 14 mov dword ptr [esp+14], ecx ; P2
0040167B |. 895424 18 mov dword ptr [esp+18], edx ; P3
0040167F |. 33C0 xor eax, eax ; eax为计数器
00401681 |> 8B7404 1C /mov esi, dword ptr [esp+eax+1C] ; 取出前面保存的常量，c=cont[i]
00401685 |. 83C0 04 |add eax, 4 ; 指向下一个常量,i++
00401688 |. 81F6 AE78D516 |xor esi, 16D578AE ; c=c^16D578AEh
0040168E |. 83F8 10 |cmp eax, 10
00401691 |. 897404 18 |mov dword ptr [esp+eax+18], esi ; 保存回原数组
00401695 |.^ 7C EA \jl short 00401681
00401697 |. 8D4424 1C lea eax, dword ptr [esp+1C] ; 计算后的常量 cont[0]
0040169B |. 8D4C24 0C lea ecx, dword ptr [esp+C] ; P0
0040169F |. 50 push eax ; 两个参数入栈
004016A0 |. 51 push ecx
004016A1 |. E8 AAF9FFFF call 00401050
2.4
004016A1 |. E8 AAF9FFFF call 00401050
这个函数涉及到伽罗瓦域
在这个域中，定义了两种运算
*加法，为异或运算
00401000 /$ 8B4424 04 mov eax, dword ptr [esp+4]
00401004 |. 8B4C24 08 mov ecx, dword ptr [esp+8]
00401008 |. 33C1 xor eax, ecx
*乘法，比较复杂
00401010 /$ 8B5424 04 mov edx, dword ptr [esp+4]
00401014 |. 53 push ebx
00401015 |. 8B5C24 0C mov ebx, dword ptr [esp+C]
00401019 |. 56 push esi
0040101A |. 33C0 xor eax, eax
0040101C |. BE 13000000 mov esi, 13
00401021 |> F6C3 01 /test bl, 1
00401024 |. 74 02 |je short 00401028
00401026 |. 33C2 |xor eax, edx
00401028 |> 8BCA |mov ecx, edx
0040102A |. 03D2 |add edx, edx
0040102C |. 81E1 00000400 |and ecx, 40000
00401032 |. 85C9 |test ecx, ecx
00401034 |. 74 06 |je short 0040103C
00401036 |. 81F2 27000800 |xor edx, 80027
0040103C |> D1EB |shr ebx, 1
0040103E |. 4E |dec esi
0040103F |.^ 75 E0 \jnz short 00401021
00401041 |. 5E pop esi
00401042 |. 5B pop ebx
函数其余部分，都使用这两个运算。下面是一个switch结果，具体请看代码。
3.验证部分
128bits分成4个DWORD
3.1 验证一
004016BA |. E8 A1FEFFFF call 00401560 ; CRC32
004016BF |. 8BF0 mov esi, eax ; eax=CRC32(name)
004016C1 |. 8B4424 1C mov eax, dword ptr [esp+1C] ; dw0
004016C5 |. 68 FFFF0700 push 7FFFF
004016CA |. 68 65260000 push 2665
004016CF |. 50 push eax
004016D0 |. 81E6 FFFF0700 and esi, 7FFFF
004016D6 |. E8 75FDFFFF call 00401450 ; RSA(dw0,2665h,7FFFFh)
004016DB |. 83C4 1C add esp, 1C
004016DE |. 3BC6 cmp eax, esi
004016E0 |. 75 4C jnz short 0040172E
所以，DW0^2665h≡CRC32(name) & 7FFFFh (mod 7FFFFh)
3.2 验证二
004016E2 |. 8B4C24 10 mov ecx, dword ptr [esp+10] ; dw1
004016E6 |. 33D2 xor edx, edx
004016E8 |. 8BC1 mov eax, ecx ; dw1
004016EA |. C1E0 05 shl eax, 5 ; dw1<<5
004016ED |. 03C1 add eax, ecx ; eax=dw1<<5+dw1
004016EF |. B9 BBFF0700 mov ecx, 7FFBB ; ecx=7FFBBh
004016F4 |. 8D0440 lea eax, dword ptr [eax+eax*2] ; eax=3*eax
004016F7 |. F7F1 div ecx ; eax/7FFBBh
004016F9 |. B9 09000000 mov ecx, 9 ; ecx=9
004016FE |. 8BC2 mov eax, edx
00401700 |. 33D2 xor edx, edx
00401702 |. F7F1 div ecx ; eax要能被9整除
00401704 |. 85D2 test edx, edx
00401706 |. 75 26 jnz short 0040172E
所以，(DW1<<5+DW1)*3%7FFBBh%9==0
即，((DW1*99)%7FFBBh)%9==0
3.3 验证三
00401708 |. 8B5424 18 mov edx, dword ptr [esp+18] ; DW3
0040170C |. 8B7C24 14 mov edi, dword ptr [esp+14] ; DW2
00401710 |. 8B4424 60 mov eax, dword ptr [esp+60] ; DWORD(name)
00401714 |. 33D7 xor edx, edi ; DW3^DW2
00401716 |. 25 FFFF0700 and eax, 7FFFF ; DWORD(name) & 7FFFFh
0040171B |. 3BD0 cmp edx, eax
0040171D |. 75 0F jnz short 0040172E
所以，DW3^DW2==DWORD(name) & 7FFFFh.
二、注册机
1.首先要算出4个DWORD的值，分别满足
DW0^2665h≡CRC32(name) & 7FFFFh (mod 7FFFFh)
((DW1*99)%7FFBBh)%9==0
DW3^DW2==DWORD(name) & 7FFFFh
DW2 DW3中一个可以随机生成
有了这4个DWORD后，对第一部分讨论的各个算法进行逆运算，即可求出序列号。
2.给出两组序列号
pediy
04bS0Pvt0Pw70Pw90QJU0QNl0QQD0QQE0g460lLZ0lLf0lLg1Emm1Eoj1EpD1EpK
yqzouguo
00Bg00fi00fk00fl01GvNecGNecLNecNNeehNfofNfpFNfpJOChUOPlYOPlaOPlb
同一用户名对应的序列号不唯一。
--------------------------------------------------------------------------------
【经验总结】
俺菜鸟一个，花了很多时间才弄清整个流程。
这个KM的思路就是序列号分块计算，每块用到不同的算法。
由于时间有限，自己写的注册机没有调试完，符上一外国人写的注册机。
学无止境，你我共勉。
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!
[注意]看雪招聘，专注安全领域的专业人才平台！
