[原创]UltraISO注册算法&keygen分析(已算出一组注册码)
这次注册算法有点难度,涉及到简单的密码学知识,但是我觉得很有意思.
UltraISO Premium Edition Version 9.6.5.3237
Delphi 6写的,加的有ASPack(2.12)的压缩壳.简单脱壳就不说了.
用IDR生成map文件给IDA用.
1.注册算法分析
首先还是找到验证算法在哪里.
一开始弹出的要注册的界面,就从这里开始吧.
在IDR里面找到那个界面,信息如下:
object frmStartup: TfrmStartup
那么在程序启动时候加载了他,然后在IDA里看到WINMAIN根据一个全局变量判断是否
显示该界面.
mov ecx, ds:var_time UnPackEr:0040308D mov eax, ds:check_time UnPackEr:00403092 cmp ecx, eax UnPackEr:00403094 jz short loc_4030AF UnPackEr:00403096 mov edx, ds:TApplication UnPackEr:0040309C mov eax, [edx] ; DWORD UnPackEr:0040309E mov ecx, ds:frmStartup ; DWORD 未注册显示的窗口 UnPackEr:004030A4 mov edx, ds:off_702798 ; DWORD UnPackEr:004030AA call TApplication_CreateForm
因此查看交叉引用到了
UnPackEr:004018F4 push ebp ; UfrmMain.sub_004018F4 UnPackEr:004018F5 mov ebp, esp UnPackEr:004018F7 add esp, 0FFFFFB38h UnPackEr:004018FD xor eax, eax UnPackEr:004018FF mov [ebp+a2], eax UnPackEr:00401902 xor edx, edx UnPackEr:00401904 mov [ebp+var_8], edx UnPackEr:00401907 xor ecx, ecx UnPackEr:00401909 mov [ebp+a1], ecx UnPackEr:0040190C xor eax, eax UnPackEr:0040190E mov [ebp+var_10], eax UnPackEr:00401911 xor edx, edx UnPackEr:00401913 mov [ebp+a4], edx
.....
这个call 004018F4 就是算法.具体的验证,自己做吧.
我不想列汇编代码了.只大致说说.
这个算法用到了大整数运算库freelip.而我是怎么知道的(静态链接)...
原因是我看到了这样的字符串:"in zhsread, second argument",运气如此之佳.
当然还有一个MD5的运算函数,要辨别很简单,也可以用Hash&Crypto Detctor扫描.
大整数运算库用来做原始的RSA-64运算.
然后我还原了一下注册算法:
static char modulus_n[] = "A70F8F62AA6E97D1";
static char op_str5[] = "10001";
static char check_str6[] = "55776B";
long* a = nullptr;
long* b = nullptr;
long* c = nullptr;
long* d = nullptr;
int flag = 0;
std::string operated_regcode;
operated_regcode.resize(56);
int seat_num = 0;
int seat_c = 0;
std::string regcode;
std::string name;
name.resize(32);
std::cout << "Registration Name: " << std::endl;
std::cin.getline(const_cast<char *>(name.c_str()),name.size());
name.resize(strlen(name.c_str()));
std::cout << "Registration Code: " << std::endl;
std::cin >> regcode;
size_t pos;
while ( pos = regcode.find("-"), pos!= std::string::npos)
{
regcode.replace(pos,1,"");
}
HASH hasher;
zhsread(const_cast<char*>(regcode.c_str()), &a);
zhsread(modulus_n, &c);
zhsread(op_str5, &b);
zexpmod(a, b, c, &d);//d=(a^b)%c //对注册码进行RSA加密后放到d
zhswrite(const_cast<char*>(operated_regcode.c_str()), d);
std::cout << "RSA-64 encrypted registration code: " << operated_regcode << std::endl;
hasher.lowerStr(const_cast<char*>(operated_regcode.c_str()));
//一下是对RSA加密后的注册码进行各种检测看是否符合规则.
if (operated_regcode[0] != check_str6[0] &&
operated_regcode[0] != '4')
{
if (operated_regcode[0] != check_str6[2] &&
operated_regcode[1] != check_str6[3])
{
if (operated_regcode[0] == check_str6[4] ||
operated_regcode[1] == check_str6[5])
{
flag += 4;
if (operated_regcode[14] < 'a')
seat_c = operated_regcode[14] - '0';
else
seat_c = operated_regcode[14] - 'W';
seat_c *= 16;
if (operated_regcode[15] < 'a')
seat_c += operated_regcode[15] - '0';
else
seat_c += operated_regcode[15] - 'W';
seat_c -= 32;
if (operated_regcode[8] < 'a')
seat_num = operated_regcode[8] - '0';
else
seat_num = operated_regcode[8] - 'W';
seat_num *= 16;
if (operated_regcode[9] < 'a')
seat_num += operated_regcode[9] - '0';
else
seat_num += operated_regcode[9] - 'W';
seat_num -= 32;
seat_num += seat_c << 6;
}
}
else
{
flag += 4;
if (operated_regcode[8] < 97)
seat_num = operated_regcode[8] - '0';
else
seat_num = operated_regcode[8] - 'W';
seat_num *= 16;
if (operated_regcode[9] < 97)
seat_num += operated_regcode[9] - '0';
else
seat_num += operated_regcode[9] - 'W';
seat_num -= 32;
}
}
else
{
++flag;
if (operated_regcode[1] == check_str6[1] || operated_regcode[1] == '6')
++flag;
if (operated_regcode[8] == '5')
++flag;
if (operated_regcode[9] == '3')
++flag;
}
std::string composite_str = "UTRISO" + name + regcode;
std::string composite_md5 = hasher(composite_str.c_str(), "MD5");
hasher.upperStr(const_cast<char*>(composite_md5.c_str()));
std::cout << "composite UTRISO,name,regcode md5: " << composite_md5 << std::endl;
unsigned int comp_md5_len;
const unsigned char* hex_composite_md5 = hasher.hash(composite_str.c_str(), "MD5", comp_md5_len);
if ((operated_regcode[6] < '2' || operated_regcode[6] > '2') && (operated_regcode[6] < 'd' || operated_regcode[6] > 'd'))
--flag;
if (operated_regcode[7] != 'a' && operated_regcode[7] != 'c' && operated_regcode[7] != 'b')
--flag;
flag -= 2;
//一下是对"UTRISO" + name + regcode计算出来的MD5前为位进行搜索,看是否存在
//于数据库中...这一项最难满足了
int len_data = 52413;
int i = 0;
int index = 0;
do
{
index = (len_data + i) / 2;
int result = memcmp(&data[6 * index], hex_composite_md5, 6);
if (result <= 0)
{
if (result >= 0)
{
flag -= 2;
if (flag == 0)
{
//success
std::cout << "matched key check data at offset " << 6 * index << std::endl;
}
break;
}
i = index + 1;
}
else
{
len_data = index - 1;
}
} while (i <= len_data);
std::cout << "last compared data: ";
for (int i = 0; i < 6; i++)
{
printf("%02X", data[6 * index + i]);
}
std::cout << std::endl;
std::string check_data_md5 = hasher(reinterpret_cast<const char*>(data), "MD5", 314484);
hasher.upperStr(const_cast<char*>(check_data_md5.c_str()));
std::cout << "key check data md5: " << check_data_md5 << std::endl;
if (flag == 0)
{
std::cout << "correct registration!" << std::endl;
}
else
{
std::cout << "wrong registration!" << std::endl;
}
FREESPACE(a);
FREESPACE(b);
FREESPACE(c);
FREESPACE(d);
我添加了一下额外的输出信息帮助我写keygen.
算法的流程如下:
用RSA加密注册码,得到密文m,
m必须满足
m[0]==4|5
m[1]==5|6
m[6]==2|d
m[7]==a|b|c
m[8]==5
m[9]==3
m总共16位.
然后连接"UTRISO",用户名,注册码 得到新字符串k.
计算k的MD5值,并且取MD5值前6位与已存在的
数据比较(0x0064C0C8处,数据的MD5:B2C2A396BE3864C4210519A8303FD1E5),有相同的就正确.
以上验证是用一个标志flag控制最终注册码是否正确.
另外,他没释放大整数运算使用的内存...我在最后添加了.
2.keygen分析
我想keygen分析是最有意思的了.
RSA模数的分解:
在还原的时候知道了他使用的RSA公钥对:
(e,n):(10001,A70F8F62AA6E97D1).
对于64位大小的n,分解简直就是秒秒钟的事情.用RSATool分解得到私钥对:
(d,n):(A7CAD9177AE95A9,A70F8F62AA6E97D1).
有了私钥对,那么第一个验证规则的逆算法就被解决了.
第二个MD5的规则验证可就棘手了.我抱着尝试的态度去查找文献,希望有在已知MD5的前6位时,
逆向推导出对应的字符串,查了所有的能找到的资料,似乎这不可能.
最多的,是构造不同内容拥有相同MD5值的算法.最先提出的人当然是王小云教授了.
给一个MD5碰撞的例子:http://www.mscs.dal.ca/~selinger/md5collision/
为什么王小云教授最先提出,国内却没人继续做深入的研究?
那我也只能碰撞了.
3.注册码碰撞算法设计分析.
要知道RSA的模幂运算是最慢的了,这个我得小心设计以达到最快.
在CPU上,最快的大整数模幂运算库绝对是GMP,我就采用他了.
虽然说MD5运算也算快,但是我们注册码的碰撞空间可是
2*2*16*16*16*16*2*3*16*16*16*16*16*16 = 3*2^43.
所以我也不敢小觑.因此我也设计了最简单的512位的MD5(还有其他的原因)运算算法.
只能计算512位的MD5算法:
#define shift(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
#define FF(a ,b ,c ,d ,Mj ,s ,ti) a = b + (shift((a + F(b, c, d) + Mj + ti) , s))
#define GG(a, b, c, d, Mj, s, ti) a = b + (shift((a + G(b, c, d) + Mj + ti) , s))
#define HH(a, b, c, d, Mj, s, ti) a = b + (shift((a + H(b, c, d) + Mj + ti) , s))
#define II(a, b, c, d, Mj, s, ti) a = b + (shift((a + I(b, c, d) + Mj + ti) , s))
#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476
typedef unsigned long long ull;
typedef unsigned int uint;
typedef unsigned char uchar;
//msg must be padded 512 bit.
extern inline ull md5_512(uint* msg)
{
uint a = A, b = B, c = C, d = D;
FF(a, b, c, d, msg[0], 7, 0xd76aa478);
FF(d, a, b, c, msg[1], 12, 0xe8c7b756);
FF(c, d, a, b, msg[2], 17, 0x242070db);
FF(b, c, d, a, msg[3], 22, 0xc1bdceee);
FF(a, b, c, d, msg[4], 7, 0xf57c0faf);
FF(d, a, b, c, msg[5], 12, 0x4787c62a);
FF(c, d, a, b, msg[6], 17, 0xa8304613);
FF(b, c, d, a, msg[7], 22, 0xfd469501);
FF(a, b, c, d, msg[8], 7, 0x698098d8);
FF(d, a, b, c, msg[9], 12, 0x8b44f7af);
FF(c, d, a, b, msg[10], 17, 0xffff5bb1);
FF(b, c, d, a, msg[11], 22, 0x895cd7be);
FF(a, b, c, d, msg[12], 7, 0x6b901122);
FF(d, a, b, c, msg[13], 12, 0xfd987193);
FF(c, d, a, b, msg[14], 17, 0xa679438e);
FF(b, c, d, a, msg[15], 22, 0x49b40821);
GG(a, b, c, d, msg[1], 5, 0xf61e2562);
GG(d, a, b, c, msg[6], 9, 0xc040b340);
GG(c, d, a, b, msg[11], 14, 0x265e5a51);
GG(b, c, d, a, msg[0], 20, 0xe9b6c7aa);
GG(a, b, c, d, msg[5], 5, 0xd62f105d);
GG(d, a, b, c, msg[10], 9, 0x02441453);
GG(c, d, a, b, msg[15], 14, 0xd8a1e681);
GG(b, c, d, a, msg[4], 20, 0xe7d3fbc8);
GG(a, b, c, d, msg[9], 5, 0x21e1cde6);
GG(d, a, b, c, msg[14], 9, 0xc33707d6);
GG(c, d, a, b, msg[3], 14, 0xf4d50d87);
GG(b, c, d, a, msg[8], 20, 0x455a14ed);
GG(a, b, c, d, msg[13], 5, 0xa9e3e905);
GG(d, a, b, c, msg[2], 9, 0xfcefa3f8);
GG(c, d, a, b, msg[7], 14, 0x676f02d9);
GG(b, c, d, a, msg[12], 20, 0x8d2a4c8a);
HH(a, b, c, d, msg[5], 4, 0xfffa3942);
HH(d, a, b, c, msg[8], 11, 0x8771f681);
HH(c, d, a, b, msg[11], 16, 0x6d9d6122);
HH(b, c, d, a, msg[14], 23, 0xfde5380c);
HH(a, b, c, d, msg[1], 4, 0xa4beea44);
HH(d, a, b, c, msg[4], 11, 0x4bdecfa9);
HH(c, d, a, b, msg[7], 16, 0xf6bb4b60);
HH(b, c, d, a, msg[10], 23, 0xbebfbc70);
HH(a, b, c, d, msg[13], 4, 0x289b7ec6);
HH(d, a, b, c, msg[0], 11, 0xeaa127fa);
HH(c, d, a, b, msg[3], 16, 0xd4ef3085);
HH(b, c, d, a, msg[6], 23, 0x04881d05);
HH(a, b, c, d, msg[9], 4, 0xd9d4d039);
HH(d, a, b, c, msg[12], 11, 0xe6db99e5);
HH(c, d, a, b, msg[15], 16, 0x1fa27cf8);
HH(b, c, d, a, msg[2], 23, 0xc4ac5665);
II(a, b, c, d, msg[0], 6, 0xf4292244);
II(d, a, b, c, msg[7], 10, 0x432aff97);
II(c, d, a, b, msg[14], 15, 0xab9423a7);
II(b, c, d, a, msg[5], 21, 0xfc93a039);
II(a, b, c, d, msg[12], 6, 0x655b59c3);
II(d, a, b, c, msg[3], 10, 0x8f0ccc92);
II(c, d, a, b, msg[10], 15, 0xffeff47d);
II(b, c, d, a, msg[1], 21, 0x85845dd1);
II(a, b, c, d, msg[8], 6, 0x6fa87e4f);
II(d, a, b, c, msg[15], 10, 0xfe2ce6e0);
II(c, d, a, b, msg[6], 15, 0xa3014314);
II(b, c, d, a, msg[13], 21, 0x4e0811a1);
II(a, b, c, d, msg[4], 6, 0xf7537e82);
II(d, a, b, c, msg[11], 10, 0xbd3af235);
II(c, d, a, b, msg[2], 15, 0x2ad7d2bb);
II(b, c, d, a, msg[9], 21, 0xeb86d391);
a = a + A;
b = b + B;
c = c + C;
d = d + D;
return (ull(b) << 32) | a;
}计算512位的MD5算法设计出来,是需要自己对要计算的数据进行填充的...
为了尽快加速RSA的运算,我也设计了64位的RSA运算,没有任何依赖库,
好让能够在GPU上跑.
GPU的64位RSA运算算法:
#define m_res 0x58F0709D5591682F
typedef unsigned long long ull;
__device__ __inline__ void add_mod(ull &a, ull b, ull m)
{
b = a + b;
if (b < a)
{
a = (b%m + m_res) % m;
}
else
{
a = b%m;
}
}
__device__ __inline__ void mul_mod(ull &a, ull b, ull m)
{
ull tmp = a%m;
a = 0;
while (b)
{
if (b & 1)
add_mod(a, tmp, m);
add_mod(tmp, tmp, m);
b >>= 1;
}
}
__device__ __inline__ ull exp_mod(ull c, ull e, ull n)
{
c %= n;
ull result = 1;
while (e > 0)
{
if (e & 1)
{
mul_mod(result, c, n);//result = (result*c) % n;
}
e >>= 1;
mul_mod(c, c, n);//c = (c*c) % n;
}
return result;
}设计GPU的RSA很有意思,我得说说.由于是64位的RSA运算,刚好能够用64位寄存器加速
运算,所以我才用上面蒙哥马利幂模运算(exp_mod)和快速模乘(mul_mod)运算.
在计算模加运算时候,中间数据可能会溢出,但是最终运算结果在溢出的情况下也可以准确.因此对于
中间数据的溢出处理就很重要.在add_mod中使用了m_res=0x58F0709D5591682F这个来对加法
溢出进行处理,得到准确的模加运算结果.
加速RSA运算的还是有很多方法的,其中用孙子剩余定理可以简化RSA运算中的幂的大小.
这个定理用在GPU中是再合适不过啊.
因此有如下计算:
密钥的模数n分解得到的两个质数p,q为
p= F513E783
q= AE818F1B
上面已经得到私钥d了:
d= A7CAD9177AE95A9
q^-1 mod p = 8764AA17
p^-1 mod q = 4E19A5F7
为p,q的乘法逆元
d1=d mod (p-1) = 58C5D3F7
d2=d mod(q-1) = AC3A102B
Cp=m^d1 mod p
Cq=m^d2 mod q
decryption = [Cp*(q^-1 mod p)*q+Cq*(p^-1 mod q)*p] mod n
=[Cp*8764AA17*AE818F1B+Cq*4E19A5F7*F513E783] mod n
=[Cp*5C4AF104DA37C96D+Cq*4AC49E5DD036CE65] mod A70F8F62AA6E97D1
最终的解密运算就变成了模乘模加运算,而模幂运算从64位降到了32位.
具体的RSA的中国剩余定理的优化分析,看这里:
http://bbs.pediy.com/showthread.php?t=89434
现在是CPU+GPU做RSA+MD5的碰撞运算,测试了一下,运算速度,
在
Intel(R) Core(TM) i7-4700HQ CPU @ 2.40GHz +
NVIDIA GeForce GT 745M
下的碰撞速度是200万次/秒 看起来很快,但是一算,要跑完得花3665小时约152天...
为了增加keygen的实用程度,我在碰撞的时候使用了随机算法
如果你运气足够好,那就很快算出来一组可用的注册码...
只能说,good luck!
最后提供一组可用的注册码:
Registration name: Home
Registration code: 4BA9-0D54-214A-C938
Registration name: Steve Olson
Registration code: 2BEC-ED28-82BB-95D7
Registration name: Christopher Wydler
Registration code: 424F-ED23-7C0A-D75B
附件有概念验证keygen和还原了的等效key检测程序.
PoCUtraISOKeyGen&CheckUltraISO.zip
所有源代码到github上:
https://github.com/yufengzjj/PoCUltraISOKeyGen.git
概念验证keygen界面:
还原的注册算法检测程序:
.
已经有幸运的人算出一组可用的注册码:
Registration name: bige
Registration code: 8058-EF0A-1CC2-DB80
