UXXXXISO注册算法&keygen分析(已经算出来注册码)
本帖最后由 ubuntu 于 2019-6-6 18:58 编辑这次注册算法有点难度,涉及到简单的密码学知识,但是我觉得很有意思.
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, ; 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 , eax
UnPackEr:00401902 xor edx, edx
UnPackEr:00401904 mov , edx
UnPackEr:00401907 xor ecx, ecx
UnPackEr:00401909 mov , ecx
UnPackEr:0040190C xor eax, eax
UnPackEr:0040190E mov , eax
UnPackEr:00401911 xor edx, edx
UnPackEr:00401913 mov , 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 != check_str6 &&
operated_regcode != '4')
{
if (operated_regcode != check_str6 &&
operated_regcode != check_str6)
{
if (operated_regcode == check_str6 ||
operated_regcode == check_str6)
{
flag += 4;
if (operated_regcode < 'a')
seat_c = operated_regcode - '0';
else
seat_c = operated_regcode - 'W';
seat_c *= 16;
if (operated_regcode < 'a')
seat_c += operated_regcode - '0';
else
seat_c += operated_regcode - 'W';
seat_c -= 32;
if (operated_regcode < 'a')
seat_num = operated_regcode - '0';
else
seat_num = operated_regcode - 'W';
seat_num *= 16;
if (operated_regcode < 'a')
seat_num += operated_regcode - '0';
else
seat_num += operated_regcode - 'W';
seat_num -= 32;
seat_num += seat_c << 6;
}
}
else
{
flag += 4;
if (operated_regcode < 97)
seat_num = operated_regcode - '0';
else
seat_num = operated_regcode - 'W';
seat_num *= 16;
if (operated_regcode < 97)
seat_num += operated_regcode - '0';
else
seat_num += operated_regcode - 'W';
seat_num -= 32;
}
}
else
{
++flag;
if (operated_regcode == check_str6 || operated_regcode == '6')
++flag;
if (operated_regcode == '5')
++flag;
if (operated_regcode == '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 < '2' || operated_regcode > '2') && (operated_regcode < 'd' || operated_regcode > 'd'))
--flag;
if (operated_regcode != 'a' && operated_regcode != 'c' && operated_regcode != '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, 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);
}
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==4|5
m==5|6
m==2|d
m==a|b|c
m==5
m==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, 7, 0xd76aa478);
FF(d, a, b, c, msg, 12, 0xe8c7b756);
FF(c, d, a, b, msg, 17, 0x242070db);
FF(b, c, d, a, msg, 22, 0xc1bdceee);
FF(a, b, c, d, msg, 7, 0xf57c0faf);
FF(d, a, b, c, msg, 12, 0x4787c62a);
FF(c, d, a, b, msg, 17, 0xa8304613);
FF(b, c, d, a, msg, 22, 0xfd469501);
FF(a, b, c, d, msg, 7, 0x698098d8);
FF(d, a, b, c, msg, 12, 0x8b44f7af);
FF(c, d, a, b, msg, 17, 0xffff5bb1);
FF(b, c, d, a, msg, 22, 0x895cd7be);
FF(a, b, c, d, msg, 7, 0x6b901122);
FF(d, a, b, c, msg, 12, 0xfd987193);
FF(c, d, a, b, msg, 17, 0xa679438e);
FF(b, c, d, a, msg, 22, 0x49b40821);
GG(a, b, c, d, msg, 5, 0xf61e2562);
GG(d, a, b, c, msg, 9, 0xc040b340);
GG(c, d, a, b, msg, 14, 0x265e5a51);
GG(b, c, d, a, msg, 20, 0xe9b6c7aa);
GG(a, b, c, d, msg, 5, 0xd62f105d);
GG(d, a, b, c, msg, 9, 0x02441453);
GG(c, d, a, b, msg, 14, 0xd8a1e681);
GG(b, c, d, a, msg, 20, 0xe7d3fbc8);
GG(a, b, c, d, msg, 5, 0x21e1cde6);
GG(d, a, b, c, msg, 9, 0xc33707d6);
GG(c, d, a, b, msg, 14, 0xf4d50d87);
GG(b, c, d, a, msg, 20, 0x455a14ed);
GG(a, b, c, d, msg, 5, 0xa9e3e905);
GG(d, a, b, c, msg, 9, 0xfcefa3f8);
GG(c, d, a, b, msg, 14, 0x676f02d9);
GG(b, c, d, a, msg, 20, 0x8d2a4c8a);
HH(a, b, c, d, msg, 4, 0xfffa3942);
HH(d, a, b, c, msg, 11, 0x8771f681);
HH(c, d, a, b, msg, 16, 0x6d9d6122);
HH(b, c, d, a, msg, 23, 0xfde5380c);
HH(a, b, c, d, msg, 4, 0xa4beea44);
HH(d, a, b, c, msg, 11, 0x4bdecfa9);
HH(c, d, a, b, msg, 16, 0xf6bb4b60);
HH(b, c, d, a, msg, 23, 0xbebfbc70);
HH(a, b, c, d, msg, 4, 0x289b7ec6);
HH(d, a, b, c, msg, 11, 0xeaa127fa);
HH(c, d, a, b, msg, 16, 0xd4ef3085);
HH(b, c, d, a, msg, 23, 0x04881d05);
HH(a, b, c, d, msg, 4, 0xd9d4d039);
HH(d, a, b, c, msg, 11, 0xe6db99e5);
HH(c, d, a, b, msg, 16, 0x1fa27cf8);
HH(b, c, d, a, msg, 23, 0xc4ac5665);
II(a, b, c, d, msg, 6, 0xf4292244);
II(d, a, b, c, msg, 10, 0x432aff97);
II(c, d, a, b, msg, 15, 0xab9423a7);
II(b, c, d, a, msg, 21, 0xfc93a039);
II(a, b, c, d, msg, 6, 0x655b59c3);
II(d, a, b, c, msg, 10, 0x8f0ccc92);
II(c, d, a, b, msg, 15, 0xffeff47d);
II(b, c, d, a, msg, 21, 0x85845dd1);
II(a, b, c, d, msg, 6, 0x6fa87e4f);
II(d, a, b, c, msg, 10, 0xfe2ce6e0);
II(c, d, a, b, msg, 15, 0xa3014314);
II(b, c, d, a, msg, 21, 0x4e0811a1);
II(a, b, c, d, msg, 6, 0xf7537e82);
II(d, a, b, c, msg, 10, 0xbd3af235);
II(c, d, a, b, msg, 15, 0x2ad7d2bb);
II(b, c, d, a, msg, 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_res0x58F0709D5591682F
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__ voidmul_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 = mod n
mod n
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检测程序.
所有源代码到github上:
https://github.com/yufengzjj/PoCUltraISOKeyGen.git
概念验证keygen界面:
还原的注册算法检测程序:
已算出来的几组注册码:
REGISTRATION NAME:52pojie
REGISTRATION CODE:2A2F-811D-0402-38B9
REGISTRATION NAME:HMBS
REGISTRATION CODE:6469-582B-AB0E-C845
Registration name: bige
Registration code: 8058-EF0A-1CC2-DB80
红绡枫叶 发表于 2016-1-31 19:31
这keygen并没有实用价值,因为找不到注册算法的逆算法,只是高速随机碰撞
昨天手机没能细看，原来如此，这也非常好了！ 本帖最后由 红绡枫叶 于 2016-4-25 15:37 编辑
红客鄙哥 发表于 2016-4-25 11:51
CPU基本占用80%以上，GPU只占用28%左右，因为我是双芯卡，看了一下算法只用到了一个GPU的50%左右，另一个 ...
的确,我设计的算法只使用一个GPU,对于多GPU没考虑.我电脑配置也只有那个样子,如果有需要,我可能会添加支持.并且GPU算法我忽略了数据传输性能损耗,我的机器能力有限,没办法做完整的性能测试.有兴趣也可以去github把源码下下来自己修改. 大神请接收我的膜拜 谢谢分享。学习下 大神感谢分享 感谢分享啊 赞，以前一直都用一个公开的key，这下有keygen了，成品发一份到原创区吧！ 跟随大牛的脚步学习 Hmily 发表于 2016-1-31 19:26
赞，以前一直都用一个公开的key，这下有keygen了，成品发一份到原创区吧！
这keygen并没有实用价值,因为找不到注册算法的逆算法,只是高速随机碰撞 这次总算靠前了,非常感谢楼主的算法分析,膜拜大牛. 第一页，围观，顶帖，支持！