首页
论坛
专栏
课程

[翻译]如何破解 RSA-1024?―― Asprotect 1.0/1.1/1.11c前半篇

2006-11-19 17:28 10960

[翻译]如何破解 RSA-1024?―― Asprotect 1.0/1.1/1.11c前半篇

2006-11-19 17:28
10960
希望我没大错误。


标题:如何破解 RSA-1024?―― Asprotect 1.0/1.1/1.11c

作者:Amenesia//TKM!(翻译:forgot/iPB)

0. 译注
========

        结论如何无所谓,关键是学习研究弱点攻击的方法。
一些代码我调整了缩进,用 notepad 排版,并加入一点注释。
	精力有限,只翻译前半部分,后面基本一样。

1. 引子
=======

        为学习基础知识,我决定研究一些著名的壳及其弱点。

首先是被Recca早在几年前就发现的弱点的ASProtect。我们知

道Recca曾经利用随机数生成器的弱点破解了ASProtect的注册

方案,现在一起看看吧……

2. Asprotect 1.0/1.1 [固定密钥]
===============================

        创建一个项目的时候会产生一些参数并保存在projec

t_name.aspr 文件中。其中比较重要的是用base64算法编码的

A,D,E和N(从右至左保存)。

-------------------------------------------------------
        A = INDtrZliM4t...0czFJpN42UQ==

        D = U2atlST1lQ...kHcbIGwJU8=

        E = EQAAAAAA...AAAAAAAA=

        N = X7lD2zsvq3QW...ha6mOrdvULEAM8=
-------------------------------------------------------

        然后计算注册密钥:

-------------------------------------------------------
        1 - H1 = RipeMD-160(A)

        2 - H2 = MD5(注册信息―H1)

        3 - Key = RSA(D,N, [H2―注册信息―H1])
-------------------------------------------------------

        密钥看起来像这个样子:

-------------------------------------------------------
        PYgt/87koSvbYPluc+/crrilfWI+ssZSU7UhgCLmK3D1C+x+
        EX9n7ukwM5sKmI+nsH66V7L28BFTziNz5DOPLRHAqnI11wN5
        Nd/dm0Esw20mm66V7L28BFTziNz55DOP4kzt+bie/rW4grgG
        +e8/hsIuotMqUXguWKBnOXsoQ89Kg92T0MkB4FCZYuZQo=
-------------------------------------------------------

        这个注册方案似乎很安全。

2.1 如何产生D,N和E?
====================

        这个过程在 RSAVR.dll 实现:

-------------------------------------------------------
        1   -   产生两个素数P和Q(512位)
        1.1 -   产生一个512位随机数
        1.2 -   找到最接近它的下一个素数(很慢)
        2   -   计算 N = P * Q
        3   -   计算 D = E^(-1)phi(N)(E = 17)
-------------------------------------------------------

        所以如果我们能找到P和Q就能分解N。

(译注:^求次方,phi应该是欧拉函数)

2.2 如何产生P和Q?
=================

-------------------------------------------------------
        unsigned long _rand()
        {
        //随机化seed
                Seed *= 214013;
                Seed += 2531011;
                return( ((Seed >> 16) & 0x7FFF) );
        }

        unsigned long RandInt()
        {
        //产生一个随机数
                for ( i=0; i<4; i++)
                {
                        rval = ((rval << 8) +_ rand());
                }
                return(rval);
        }

        //计算 seed!!!关键!!!
        Seed = (time() + ThreadId()) xor TickCount();

        //计算P
        for ( ri=0; ri<16; ri++)
        {
                BigNumber1[ri] = RandInt();
        }
        BigNumber1[ri] = BigNumber1[ri] xor C0000000h;

        P = nextPrime(BigNumber1);
        //计算Q
        for ( ri=0; ri<16; ri++)
        {
                BigNumber2[ri] = RandInt();
        }
        BigNumber2[ri] = BigNumber2[ri] xor C0000000h;

        Q = nextPrime(BigNumber2);
-------------------------------------------------------

        因此若我们能猜到(time() + ThreadId()) xor Tick
Count()的值就能获得P和Q。

(译注:nextPrime() 求离参数最近的下一个素数。)

2.3 攻击
========

        不知Recca是怎么找那个seed的,似乎蛮力攻击是唯
一的方法(有 2^32 种可能):

-------------------------------------------------------
        1 - 选择一个 seed
        2 - 计算 BigNumber1 和 BigNumber2
        3 - 寻找P = nextPrime(BigNumber1)
                Q = nextPrime(BigNumber2)
        4 - 若 N != P * Q 则换另外的 seed
-------------------------------------------------------

        不过素数测试花费的时间是可怕的,尝试2^32个不同
的 seed 几乎不可能。

2.3.1 缩小范围
==============

        第一个改进方法是基于 ThreadId 和 TickCount 通
常很小的事实。所以 seed 高位一般都是 time() 值。因此,
我们可以只考察接近软件发布日期的 seed。

(译注:忍不住赞)

2.3.2 改进算法
==============

        素数测试很慢,我们不得不找一个并不计算 P 和 Q
值的情况下就能检测是否是正确 seed 的算法。窍门就是修改
nextPrime() 函数使之只计算 BigNumber1 和 BigNumber2 的
低位双字。

        P = BigNumber1 + Delta1 (Delta1 <= 2^64)
        Q = BigNumber2 + Delta2 (Delta2 <= 2^64)
        N = P * Q = (BigNumber1 + Delta1) * (BigNumber2 + Delta2)
        N = BigNumber1 * BigNumber2 + Delta3 (Delta3 <= 2^(512+64+2))
        因此:N高位 = BigNumber1高位 * BigNumber2高位

(译注:Delta是增量,因为 nextPrime 是下一个素数,因此
是数后面加一个增量,至于Delta的范围,我还没想去证明。)

        算法:
-------------------------------------------------------
        1 - 选择一个 seed
        2 - 计算 BigNumber1高位 和 BigNumber2高位
        3 - 若 N高位 != BigNumber1高位 * BigNumber2高位
            换另外的 seed
        4 - 计算 BigNumber1 和 BigNumber2(避免冲撞值)
        5 - 计算 P = nextPrime( BigNumber1 )
                 Q = nextPrime( BigNumber2 )
        6 - 若 N! = P * Q 换另外的 seed
-------------------------------------------------------

2.4 例子
========

        ASProtect 1.1 用它自己加壳,再难找到更好的例子
啦。检查一下我们的的算法是否有效。

        N 和 E 保存在被加密的程序中:

        N = EB1D4EADA4815F6277519791BFFA8B4C0B872D1C436515AB
        D9572B22BF6A03FECB4E5CC49AF1EE35C31344617A1210663056
        90529B9CE7F13ED2D37CD7034A3EDD096853EC61243BCCAC5A58
        800B0330A4DD85E9AA237F2F2AE60CA049B1D2777B2E0C5FF51E
        058382A86C3EC12F7AB41642022772FF2A2D3DBA704725702199

        E = 17

        ASProtect 在 2000 10月 发布,所以我们选择 39000000h
作为最小的 seed。我们找到了一个冲撞值 398BBB72h,一分钟后找
到 399BACC4h(花了一小时检测 2^32 种可能):

        D = l8F1EGKSQWCw9Et5klCpkm9/TIQFw0xOxibd+bQNndzGYoIX
        4PmHXcdZtN3VWRQfuYS/cLeEf0i+kG3Cd7kaqKCkBO3xiAFgZMf
        vW8D+bov+AfjDICITq5/Lhex7PykLGtUNnH8LSsmIDSWqldwX3Q
        9o8U4HcJSjSJIfS4bumc=


....



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

最新回复 (14)
forgot 26 2006-11-19 17:32
2
0
心得:我认为一个关键的思想是对信息的特征考察。
girl 1 2006-11-19 18:11
3
0
支持继续挖掘好东西
冷血书生 28 2006-11-19 20:39
4
0
继续~~
kanxue 8 2006-11-19 21:55
5
0
forgot好样的
海风月影 17 2006-11-20 19:26
6
0
看来随机数还不能简单地取时间
加个HASH呢?(生成seed的时候把系统时间调到2099年)
readyu 9 2006-11-21 23:06
7
0
有其它方法,比如取2次击键的间隔,取鼠标的移动。

最初由 海风月影 发布
看来随机数还不能简单地取时间
加个HASH呢?(生成seed的时候把系统时间调到2099年)
zhucheba 2007-1-12 18:06
8
0
期待继续。。
soychino 2007-1-18 02:31
9
0
recca强人一个!!!
linhanshi 2007-1-23 14:41
10
0
sustain.
少学点 2007-1-25 20:07
11
0
支持在支持在支持
子毅澜 2007-1-30 19:58
12
0
谢谢分享!
Jayki 2007-2-21 09:19
13
0
最初由 海风月影 发布
看来随机数还不能简单地取时间
加个HASH呢?(生成seed的时候把系统时间调到2099年)

好狠,不过会有人这样做么?
forgot 26 2007-2-21 15:19
14
0
跑一遍鼠标xy就可以了
ktstar 2007-3-3 01:18
15
0
支持,楼主好样的
游客
登录 | 注册 方可回帖
返回