Speed Video Splitter算法分析兼RSA实例教程 By:happytown
标 题: 【原创】Speed Video Splitter算法分析兼RSA实例教程作 者: happytown
时 间: 2007-01-10,15:56
链 接: http://bbs.pediy.com/showthread.php?threadid=37738
【文章标题】: 【原创】Speed Video Splitter 2.4.29算法分析兼RSA实例教程
【文章作者】: HappyTown
【作者主页】: www.pediy.com
【软件名称】: Speed Video Splitter
【下载地址】: http://www.newhua.com/soft/40143.htm
【加壳方式】: 无
【保护方式】: RSA-252
【编写语言】: VC6
【使用工具】: OD + IDA + DAMN_HashCalc + RSATool
【操作平台】: WinXP
【软件介绍】: Speed Video Splitter is a small video splitter tool. It also has very fast speed like Speed Video Converter. You can split all supported video files by setting the startting and stopping time.
Speed Video Splitter supports various video formats, such as AVI(Divx,xDiv), MPEG-4, mpeg(vcd,svcd,dvd compatible), wmv, asf, Quick Time, VOB, DAT.
【作者声明】: 只是感兴趣，没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
到华军软件园随便下载了个软件，没想到居然是RSA保护。可能是我平常只注意了分析CrackMe，而对具体的商用程序玩得太少的缘故吧；也有可能是现在大家都注意到用公钥算法保护自己的软件了（这可是件值得高兴的事情，呵呵）。
1. PEiD告诉我们这个程序是用VC6编写的，kanal插件得不到任何有用的东西。
2. IDA没帮上什么忙，没能识别出大数库的库函数。但我们还是导出了map文件。
3. 程序中的BigCreate，Bytes2Big，powmod等标签是我自己手动加上的。如果大家见过不少大数库，那么对本程序所使用的库函数进行猜测应该不是件很难的事。
4. 我们将尝试用几种不同的思路来破解这个程序的保护。
=====================
方法一：做出注册机，这是最完美的方式了。
=====================
输入
User name:happ
Registration code(sn):11111111-22222222-33333333-44444444-55555555-66666663-77777777-88888888
输入成这种格式的原因，后面我会解释。
0040BE79|.>mov dword ptr , C95841DF ;//n
0040BE81|.>mov dword ptr , 717AE412
0040BE89|.>mov dword ptr , F015E3AC
0040BE91|.>mov dword ptr , 1127EB1
0040BE99|.>mov dword ptr , 1D455E89
0040BEA1|.>mov dword ptr , 5375F151
0040BEA9|.>mov dword ptr , D34D4B6E
0040BEB1|.>mov dword ptr , 88C5F181 ;\\
0040BEB9|.>call <??0CString@@QAE@PBD@Z> ;jmp 到 MFC42.#537_CString::CString
0040BEBE|.>mov ecx, ;sn
0040BEC5|.>mov dword ptr , 0
0040BED0|.>push ecx
0040BED1|.>lea ecx,
0040BED5|.>call <??0CString@@QAE@PBD@Z> ;jmp 到 MFC42.#537_CString::CString
0040BEDA|.>mov edx, ;name
0040BEDE|.>mov esi, [<&MSVCRT._mbscmp>] ;msvcrt._mbscmp
0040BEE4|.>push 0042219C ; /s2 = ""
0040BEE9|.>push edx ; |s1
0040BEEA|.>mov byte ptr , 1 ; |
0040BEF2|.>call esi ; \_mbscmp
0040BEF4|.>add esp, 8
0040BEF7|.>test eax, eax
0040BEF9|.>je 0040C10E
0040BEFF|.>mov eax,
0040BF03|.>push 0042219C
0040BF08|.>push eax ;sn
0040BF09|.>call esi
0040BF0B|.>add esp, 8
0040BF0E|.>test eax, eax
0040BF10|.>je 0040C10E
上面初始化了n，同时检测用户输入的信息是否为空。
0040BF16|.>push edi
0040BF17|.>push 0
0040BF19|.>lea ecx,
0040BF1D|.>call <BigCreate>
0040BF22|.>push 0
0040BF24|.>lea ecx,
0040BF28|.>mov byte ptr , 2
0040BF30|.>call <BigCreate>
0040BF35|.>mov bl, 3
0040BF37|.>push 10001 ;e=0x10001，看到这个数，大家可能都很敏感。
0040BF3C|.>lea ecx,
0040BF40|.>mov , bl
0040BF47|.>call <BigCreate>
0040BF4C|.>lea ecx,
0040BF50|.>mov byte ptr , 4
0040BF58|.>push ecx
0040BF59|.>lea ecx,
0040BF5D|.>call 0040D6B0
0040BF62|.>lea ecx,
0040BF66|.>mov , bl
0040BF6D|.>call 0040D700
0040BF72|.>lea edx,
0040BF76|.>push 8 ;8个DWORD
0040BF78|.>push edx ;n
0040BF79|.>lea ecx,
0040BF7D|.>call <Bytes2Big>
0040BF82|.>mov ecx, 8
0040BF87|.>xor eax, eax
0040BF89|.>lea edi,
0040BF8D|.>lea edx,
0040BF91|.>rep stos dword ptr es:
0040BF93|.>lea eax,
0040BF97|.>lea ecx,
0040BF9B|.>push eax ;0
0040BF9C|.>push ecx ;0
0040BF9D|.>lea eax,
0040BFA1|.>push edx ;0
0040BFA2|.>lea ecx,
0040BFA6|.>push eax ;0
0040BFA7|.>lea edx,
0040BFAB|.>push ecx ;0
0040BFAC|.>lea eax,
0040BFB0|.>push edx
0040BFB1|.>mov edx,
0040BFB5|.>lea ecx,
0040BFB9|.>push eax
0040BFBA|.>push ecx ;下面的format告诉了我们注册码的格式
0040BFBB|.>push 00421ED0 ; |format = "%08lX-%08lX-%08lX-%08lX-%08lX-%08lX-%08lX-%08lX",LF,""
0040BFC0|.>push edx ; |s = "11111111-22222222-33333333-44444444-55555555-66666663-77777777-88888888"
0040BFC1|.>call [<&MSVCRT.sscanf>] ; \sscanf
上面初始化了常数e和一些大数，同时格式化取得我们输入的注册码，这些都是很明显的事情。
0040BFC7|.>mov eax, ;55555555
0040BFCB|.>mov ecx, ;44444444
0040BFCF|.>mov edi, ;33333333
0040BFD3|.>mov edx, ;22222222
0040BFD7|.>add eax, ecx ;55555555 + 44444444 =99999999
0040BFD9|.>mov ecx, ;88888888
0040BFDD|.>add eax, edi ;99999999 + 33333333 = cccccccc
0040BFDF|.>mov edi, ;77777777
0040BFE3|.>add eax, edx ;cccccccc + 22222222 =eeeeeeee
0040BFE5|.>mov edx, ;66666663
0040BFE9|.>xor ecx, eax ;88888888 xor eeeeeeee = 66666666 '
0040BFEB|.>mov eax, ;11111111
0040BFEF|.>add esp, 28
0040BFF2|.>add edx, eax ;11111111 + 66666663 = 77777774
0040BFF4|.>mov , ecx ;66666666
0040BFF8|.>xor edi, edx ;77777777 xor 77777774 = 3
0040BFFA|.>push 0
0040BFFC|.>lea ecx,
0040C000|.>mov , edi
0040C004|.>call <BigCreate>
0040C009|.>lea ecx,
0040C00D|.>push 8
0040C00F|.>push ecx ;sn' = 1111111122222222333333334444444455555555636666660300000066666666
0040C010|.>lea ecx,
0040C014|.>mov byte ptr , 5
0040C01C|.>call <Bytes2Big>
一阵眼花缭乱的运算之后，得到了一个核心参数sn'。呵呵，好戏开始了。
0040C021|.>lea edx,
0040C025|.>lea eax,
0040C029|.>push edx ;sn'
0040C02A|.>push eax
0040C02B|.>lea ecx,
0040C02F|.>call <powmod> ;c =sn' ^ 10001 (mod n)
还是跟进去看一下这个powmod函数：
{
004068F0 >/$>push ecx ;n
004068F1|.>mov eax,
004068F5|.>push esi
004068F6|.>mov esi,
004068FA|.>push ecx ;n
004068FB|.>add ecx, 8
004068FE|.>mov dword ptr , 0
00406906|.>push ecx ;10001
00406907|.>push eax ;sn'
00406908|.>push esi ;计算结果存在此处
00406909|.>call <_powmod> ;c =sn' ^ 10001 (mod n)
0040690E|.>add esp, 10
00406911|.>mov eax, esi
00406913|.>pop esi
00406914|.>pop ecx
00406915\.>retn 8
}
这里要着重说明的是大数在内存中存放的格式。在我的机器上（应该和绝大多数的PC一样吧），n表示为：
00E949B0DF 41 58 C9 12 E4 7A 71 AC E3 15 F0 B1 7E 12 01逜X?鋤q?鸨~
00E949C089 5E 45 1D 51 F1 75 53 6E 4B 4D D3 81 F1 C5 88塣E Q駏SnKM觼衽
可以看出，它是Little Endian方式。
0040C034|.>mov ecx, 8
0040C039|.>xor eax, eax
0040C03B|.>lea edi,
0040C03F|.>push 8
0040C041|.>rep stos dword ptr es:
0040C043|.>lea ecx,
0040C047|.>mov byte ptr , 6
0040C04F|.>push ecx
0040C050|.>lea ecx,
0040C054|.>call <copy>
0040C059|.>mov ecx, 8
0040C05E|.>xor eax, eax
0040C060|.>lea edi,
0040C067|.>rep stos dword ptr es:
0040C069|.>pop edi
0040C06A|>>/mov dl, ;//就是由于下面这段循环导致写注册机时name要反转
0040C06E|.>|mov cl,
0040C072|.>|mov , dl
0040C076|.>|mov edx,
0040C07A|.>|mov , cl
0040C07E|.>|mov cl,
0040C082|.>|shr edx, 8
0040C085|.>|mov , dl
0040C089|.>|mov , cl
0040C08D|.>|add eax, 4
0040C090|.>|cmp eax, 20
0040C093|.>\jl short 0040C06A ;\\convert c
0040C095|.>lea edx,
0040C099|.>lea ecx,
0040C09D|.>push edx ;c
0040C09E|.>call <??0CString@@QAE@PBD@Z> ;jmp 到 MFC42.#537_CString::CString
0040C0A3|.>mov eax,
0040C0A7|.>mov ecx,
0040C0AB|.>push eax ;c
0040C0AC|.>push ecx ;name
0040C0AD|.>call esi ;msvcrt._mbscmp
0040C0AF|.>add esp, 8
0040C0B2|.>lea ecx,
0040C0B6|.>test eax, eax
0040C0B8|.>mov byte ptr , 6
0040C0C0| >je 0040C14C ;判断注册成功与否
对于 convert c 的循环的解释请参考下面的注册机。现在只需明白0040C0AD处比较的是RSA计算的结果和name即可。看过《加密与解密II》P208~211的那个RSA例子的应该很容易就能明白这个比较。
好了，整理一下程序验证的思路：
(1) 先是眼花缭乱的一段运算得到sn'；
(2) 计算 c = sn'^ e (mod n)；
(3) 比较 c和name。
为了仔细分析那段眼花缭乱的运算，我们不妨作如下标记：
11111111-22222222-33333333-44444444-55555555-66666663-77777777-88888888
sn_1 sn_2 sn_3 sn_4 sn_5 sn_6 sn_7 sn_8
sn'采用同样的分法。
OK，分析那段运算的算法：
Δ = (sn_5 + sn_4 + sn_3 + sn_2) xor sn_8
δ = (sn_1 + sn_6) xor sn_7
很明显，该算法可逆。
那么：
sn'=sn_1-sn_2-sn_3-sn_4-sn_5-sn_6-δ-Δ
我们已经明白了程序验证注册的完整过程，下面是RSATool计算出来的RSA参数（花了我4个多小时）：
=======================================================
n=p*q:
88C5F181D34D4B6E5375F1511D455E8901127EB1F015E3AC717AE412C95841DF
p:
92D9586271DFD8D47C9AE783DED37E9F
q:
EE6F5C9077D0A54887558B9CA262B4C1
e:
10001
d:
7AAB6636F5681EDE3D96CBAFDF9BE6F38A66563EB122E21AE8B94121DC164781
========================================================
该写注册机了，由于论坛不方便上传编译好的程序，所以我仅给出注册机的源代码，用到了miracl库：
//KeyGen for
//Cracked by
//RSA-252 inside
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <miracl.h>
#define MAXLEN 500
int main()
{
int i=0, iNameLen=0, k=0;
unsigned char Name = {0};
unsigned char name = {0};
unsigned int sn_;
unsigned int *p, *p1;
big n,d,bTemp,bName;
miracl *mip = mirsys(0x500, 0x10);
n = mirvar(0);
d = mirvar(0);
bTemp = mirvar(0);
bName = mirvar(0);
mip->IOBASE = 16;
cinstr(n, "88C5F181D34D4B6E5375F1511D455E8901127EB1F015E3AC717AE412C95841DF");
cinstr(d, "7AAB6636F5681EDE3D96CBAFDF9BE6F38A66563EB122E21AE8B94121DC164781");
printf("\t\tKeyGen for \n");
printf("\t\t Cracked by 2007-01-09\n\n");
//get name and reverse name
again:
printf("Enter your name:");//支持中文
scanf("%s", Name);
iNameLen = lstrlen(Name);
//name长度最好不要大于等于32位，因为当超过n时会导致违背RSA算法
if(iNameLen >=32)
{
printf("\tWarning! Too long name.\n");
goto again;
}
k = iNameLen / 4;
p = &Name;
p1 = &name;
p1 = p1 + k;
for(i=0; i<=k; i++)//反转name
{
*p1 = *(p+i);
p1--;
}
bytes_to_big((k+1)*4, name, bName);//因为反转的缘故，所以即使name的长度为1，也要取4字节
//RSA
powmod(bName, d, n, bTemp);
//get sn
p = (unsigned int)bTemp;
p = p + 3;
for(i=0; i<8; i++)
{
sn_ = *p;
p++;
}
//xor and print Registration code
sn_ = (sn_ + sn_ + sn_ + sn_) ^ sn_;
sn_ = (sn_ + sn_) ^ sn_;
printf("Registration code:\n");
for(i=0; i<8; i++)
{
printf("%08X", sn_);
if (i != 7)
{
printf("-");
}
}
//kill miracl
mirkill(n); mirkill(d); mirkill(bName); mirkill(bTemp);mirexit();
printf("\n\n\n\n");
system("pause");
return 0;
}
给出几组可用的注册码供大家检测：
username=happ
registercode=43CF62F0-884A07EF-46355D15-9213A3DE-1E7BB37C-2C6182E1-DD729E6A-5DC99194
username=happytown
registercode=BC4AADFF-49A152A2-FBC551F1-DD3665C7-53DC6132-B8F3E443-94BEAB2E-597DC5E9
username=看雪学院
registercode=204B1562-C15498F6-6401CB00-5C4193E1-D36331E8-CC966A50-C92E7322-7C2C3B43
=====================
方法二：不写注册机，也不更改程序，却可以通过验证（该方法仅作为一种思路本是可行的，但在该程序中未通过）
=====================
聪明的你肯定发现了注册信息存放在软件目录下的Settings.ini文件中。
我们再看一遍下面这段代码：
0040C0AB|.>push eax ;c
0040C0AC|.>push ecx ;name
0040C0AD|.>call esi ;msvcrt._mbscmp
0040C0AF|.>add esp, 8
0040C0B2|.>lea ecx,
0040C0B6|.>test eax, eax
0040C0B8|.>mov byte ptr , 6
0040C0C0| >je 0040C14C ;判断注册成功与否
呵呵，在Settings.ini中把我们输入的 name 改成 c 是否可行呢？试试看吧，不过不能用记事本和UE之类的软件来改，而要用Hex Workshop和WinHex之类的软件来改。还是以方法一的输入为例。
这是经过计算后的c:
003F45E077 21 7D 67 CB 4B 46 C3 1A EA A5 E9 0B B6 F2 8Cw!}g薑F?辚?厄
003F45F096 EA C0 A3 A5 0C 64 20 71 B9 F6 C4 7B 9E D6 D4栮溃?d q滚?#123;炛
003F4600E0 E3 12 00 00 00 00 00 00 00 00 00 00 00 00 00嚆.............
因为_mbscmp比较时遇到00才算字符串结束，所以Settings.ini中的name也需要包含c后面的E0 E3 12。
但有意思的是在程序中总是把name中后面的12没有读出来，就差一个字节，导致验证失败，手动修改内存添上当然可以通过验证。我始终没有检查出为什么会漏掉这个12。但这一思路应该在某些软件上有效。
=====================
方法三：爆破，直接更改0040C0C0| >je 0040C14C的je为jne即可。
=====================
这时，真正的注册码倒不能验证通过了。直接改为jmp算了。
=====================
方法四：用RSATool生成一组 n，d 替换掉程序原来的 n 和 d。
=====================
这样就不用花时间计算 d，可以用自己的 n 和 d 直接写注册机。当 n 特别大而难以分解时，会很凑效。具体的我就不做了，大家可以试试。
--------------------------------------------------------------------------------
【经验总结】
还是那句老话，我始终认为一题多解是个很好的学习方法。
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!
2007年01月09日 16:27:25 :L
这几种思路很有学习价值` 方法二和四太好了/:D 以后又可以偷懒了 学习破解关键学习思路:victory: 学习中……支持！！！！
晕
看了半天,偶以前从来没有正式研究过算法,今天开了眼了,一会研究一下, 注册名：网游难民注册码：D5D0739C-13028C4D-BBAF92FB-E2C6D900-8543F17D-D36CBA21-0788C9FA-50106753 虽然我看不懂但还是支持~ 学习思路。
页:
[1]
2