UXXXXISO注册算法&keygen分析(已经算出来注册码)

红绡枫叶 · 发表于 2016-1-31 18:59

本帖最后由 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根据一个全局变量判断是否
显示该界面.

[Asm] 纯文本查看 复制代码

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

因此查看交叉引用到了

[Asm] 纯文本查看 复制代码

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运算.

然后我还原了一下注册算法:

[C++] 纯文本查看 复制代码

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算法:

[C++] 纯文本查看 复制代码

#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运算算法:

[C] 纯文本查看 复制代码

#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 (2.1 MB, 下载次数: 1753)
所有源代码到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

Hmily · 发表于 2016-2-1 10:43

红绡枫叶发表于 2016-1-31 19:31
这keygen并没有实用价值,因为找不到注册算法的逆算法,只是高速随机碰撞

昨天手机没能细看，原来如此，这也非常好了！

红绡枫叶 · 发表于 2016-4-25 15:30

本帖最后由红绡枫叶于 2016-4-25 15:37 编辑

红客鄙哥发表于 2016-4-25 11:51
CPU基本占用80%以上，GPU只占用28%左右，因为我是双芯卡，看了一下算法只用到了一个GPU的50%左右，另一个 ...

的确,我设计的算法只使用一个GPU,对于多GPU没考虑.我电脑配置也只有那个样子,如果有需要,我可能会添加支持.并且GPU算法我忽略了数据传输性能损耗,我的机器能力有限,没办法做完整的性能测试.有兴趣也可以去github把源码下下来自己修改.

沙滩上de水瓶 · 发表于 2016-1-31 19:05

大神请接收我的膜拜

hidekill · 发表于 2016-1-31 19:09

谢谢分享。学习下

wakichie · 发表于 2016-1-31 19:10

大神感谢分享

dxlxh20150521 · 发表于 2016-1-31 19:15

感谢分享啊

Hmily · 发表于 2016-1-31 19:26

赞，以前一直都用一个公开的key，这下有keygen了，成品发一份到原创区吧！

wgz001 · 发表于 2016-1-31 19:28

跟随大牛的脚步学习

红绡枫叶 · 发表于 2016-1-31 19:31

Hmily 发表于 2016-1-31 19:26
赞，以前一直都用一个公开的key，这下有keygen了，成品发一份到原创区吧！

这keygen并没有实用价值,因为找不到注册算法的逆算法,只是高速随机碰撞

xq811028 · 发表于 2016-1-31 19:33

这次总算靠前了,非常感谢楼主的算法分析,膜拜大牛.

一生情独醉 · 发表于 2016-1-31 19:52

第一页，围观，顶帖，支持！

帐号		自动登录	找回密码
密码			注册[Register]

[原创] UXXXXISO注册算法&keygen分析(已经算出来注册码)

免费评分

本帖被以下淘专辑推荐:

点评