首页
论坛
专栏
课程

[调试逆向] [原创]UltraISO注册算法&keygen分析(已算出一组注册码)

2016-1-31 18:57 15129

[调试逆向] [原创]UltraISO注册算法&keygen分析(已算出一组注册码)

2016-1-31 18:57
15129
这次注册算法有点难度,涉及到简单的密码学知识,但是我觉得很有意思.

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

[公告]安全测试和项目外包请将项目需求发到看雪企服平台:https://qifu.kanxue.com

上传的附件:
最新回复 (38)
影子不寂寞 2016-1-31 20:44
2
0
精彩文章,学习了。
arlequim 2016-1-31 21:14
3
0
Marvelous proof of crypto knowledge. Need to study a little more
jjjackup 2016-1-31 21:31
4
0
感谢分享啊
pendan2001 4 2016-1-31 21:31
5
0
52pojie一份,看雪一份,精彩继续顶起,呵呵。。。
Nisy 5 2016-1-31 22:49
6
0
学习了,大赞 ~
SnowRen 2016-2-1 00:03
7
0
版本号应该是:UltraISO Premium Edition Version 9.6.5.3237
numbugger 2016-2-1 00:58
8
0
精彩文章
Sam.com 2016-2-1 02:02
9
0
太厉害了~~
Sam.com 2016-2-1 02:09
10
0
PoCUtraISOKeyGen.exe输入用户名后就出错了Win7 64位
xed 2016-2-1 10:40
11
0
分析得很详细。
qqlinhai 2016-2-1 11:03
12
0
膜拜大神~
wxq 2016-2-1 12:03
13
0
强大,支持一下。
阿扁鱼 2016-2-1 12:53
14
0
强大呀,膜拜下.....好文章
qyc 4 2016-2-1 13:22
15
0
学习了,非常不错的分析
地狱怪客 2 2016-2-1 13:44
16
0
太牛叉了呀( ⊙ o ⊙ )!
geekcat 2016-2-1 16:13
17
0
学习了
谢谢分享
treefly 1 2016-2-1 23:30
18
0
学习了,算法分析的很细致
JackJoker 2016-2-3 09:12
19
0
一篇精彩帖子引出了一批老会员,精彩
极度靓仔 2016-2-3 18:41
20
0
一个字:牛。
kx001 2016-2-4 10:12
21
0
太厉害了,必须赞一个
ahappyboy 2016-2-4 10:46
22
0
分析得很精彩!!!
HotVC 2016-2-5 09:07
23
0
弱弱的问句 IDR 是什么··
红绡枫叶 6 2016-2-5 11:02
24
0
IDR (Interactive Delphi Reconstructor) – a decompiler of executable files (EXE) and dynamic libraries (DLL), written in Delphi and executed in Windows32 environment.

http://kpnc.org/idr32/en/index.htm
孟贤 2016-2-5 17:30
25
0
好屌哦.
Maomao 2016-2-8 21:43
26
0
楼主的RSA算法之精通,惊叹!
xie风腾 2016-2-8 21:55
27
0
来学习了哟 多谢分享
StartAoA 2016-2-10 21:33
28
0
有步猪头三之后尘~~~~ 牛叉!!!!
绿林科技 2016-2-11 15:46
29
0
goog job
DLDLIS 2016-2-12 15:53
30
0
分析得很仔细啊。
doomit 2016-2-12 21:41
31
0
好厉害,算法大神!数学大神!
zrj99 1 2016-4-4 16:47
32
0
膜拜!佩服!致敬!
底层劳动者 2018-2-20 12:29
33
0
2012年就写了个UltraISO的注册机。白名单,内置10000多个名单,算出了几个自己用的:
喜鹊                      722ECFFF88A21C66
小鸟依人        7CB8-029C-FAB8-AC98
乌龟                      48680C6DD60BF252
老不死的          F17D053D6B8E621
MD5不能逆向是个问题,算一个码,要算很久
AperOdry 2018-2-20 15:53
34
0
mark
rlyt 2018-2-24 10:20
35
0
算出来一组:
pediy
3629-9B3F-141E-CAA7
jeffli 2019-3-9 00:07
36
0
感谢分享! 有没有考虑过UltraISO的官方是如何产生注册码的呢? 按照逆向出来的算法, 想要产生合法的注册码也会很慢, 不知道有没有忽略的地方? 
VirtualCC 2019-10-14 19:01
37
0
我猜测大概是这样,官方先通过算法,生成足够多的注册码,然后再卖咯!
mb_phyjrmwy 2天前
38
0
楼主,私信个联系方式呗。
hgzyyl 2天前
39
0
精彩文章,学习了。
游客
登录 | 注册 方可回帖
返回