-
-
[原创]设计一种注册验证算法模型，欢迎各位来深入探讨
-
发表于: 2007-4-24 18:52
-
先废话两句，
（1）这种模型不打算出DEMO，看的懂的可以自己去实现，看不懂的可以交流，如果交流后还是不懂那么没办法了，就当作是没看过。
（2）非常欢迎各位针对这个模型本身的应用性、安全性进行更深入的探讨！
（3）没了。。。
///////////////////////////////////////////////////////////////////////////////
这里我不打算单独介绍这种模型的优点，很多因素结合到下面的模型中介绍。直蹦主题！
///////////////////////////////////////////////////////////////////////////////
(注1：对称加密算法以DES为例，密钥8个字节，刚好64位大整数)
一、设计指标：算法强度、稳定性、动态性、可扩展性
二、设计原则：
[1] 要保证解密流程无漏洞，这里的解密是软件自身进行注册验证的流程，在这个过程Crack并不会得到任何有意义的数据，因为软件没有任何的正确性验证。对于这类算法，Crack除了暴力枚举外，恐怕没有第二条路。
[2] 作为软件的作者，希望写注册机比较方便。算法有了，强度有了，如果连自己都写不出注册机，或者逆向算法太难写，拿什么给用户。免费软件多好，不用搞这么多事。
三、设计思路（设计过程中的思维方式）：
只要按照经典注册验证算法模型来设计，不出意外原则[1]是可以保证的。剩下的就是什么样的算法实现简单，有可以很方便的写逆向算法。
我首先想到的是乘法和除法，或许大伙会以为这些运算太简单，不可靠，其实并不是这样。
（1）在不考虑Mask时流程是这样（此时D 就是对称加密算法中的密钥）：
A = Hash ( UserName ) ;
B = Y ( Password ) ;
D = Hash(UserName) * Y(Password) ；
写注册机时E、UserName和hash算法都已知，就可以知道B和Password。
初看还真没什么问题，算法也超简单。事实上这里有个很大的问题，你能保证E是合数吗？如果你说选取密钥（D）的时候可以选合数，那么难道你的软件里只有一个或者几个合法的用户?而且这里的还涉及到大整数分解的问题，这还是数学中的一个难题。
在应用注册验证算法时，以（用户名—密码）这个形式来说，有一个很重要的原则是，对于输入的任意合法用户名必定有密码。( 说明下，Password = f ( UserName )这一类在在中间过程有比较验证的算法没有任何意义 ）
现在的要求很明确：对于任意一个密钥，能够写出注册机。显然这在没有Mask的情况下是无法实现的，对于任意的A，并不能始终被D整除。
（2）引入Mask变换?
[1] Mask是什么？
Mask其实就是个掩码值，从整数角度来说，Mask的值是低x位有效。例如低5位有效，那么mask=31；如果低3位有效，那么mask=7。这个值可以自由选定，一般情况下不要超过16位，也就是Mask<=0xFFFF.关于选取Mask的因素，稍后介绍。这里以8为例，即Mask=255。
[2] 什么是Mask变换（假设变换前的值为P，Mask=256）？
Mask1变换：P & (~Mask)，即过滤P的低8位
Mask2变换：P & Mask，即取P的低8位
[3] 为什么D要进行Mask1变换（在这里不考虑Mask2）?
——消除密钥分解因子的确定性。
首先要明确一点，引入Mask变换后，D不再是密钥，真正的密钥是E。
对于一个E，因子总是确定的。而因子对应于这里的UserName和Password，这样UserName和Password就具有了确定性。对于任何A，需要找到B与之对应，使得Mask1(A*B) = E。换句话说，把D=A*B的低8位舍去结果为E。于是对于任意的合法用户名，总有密码与之对应，那么密钥的确定性就不存在了。
E = Mask1(D) = Mask1(A*B) —————— （1）
[4] 为什么A要进行Mask2变换 ?
——确保UserName和Password配对存在的必然性
愿望总是良好的，希望（1）总能够成立。那么先分析下（1）成立的条件：
当D在[E，E+Mask]范围时，E=Mask1(D)总能成立；D=A*B，也就是说只要保证A*B也在这个区间就可以了。那么对于任何一个A，是否能够找到对应的B呢？
有两种情况：
如果A > Mask，最多有1个B，可能不存在B
如果A <= Mask，有 ( （Mask+1） / A + 1 )>=2 个B，即解必然存在
显然不能采用第一中情况，如果输入用户名，密码出不来，那就笑话了。
很自然我们应该保证第二情况始终成立，于是Mask2就可以满足这个要求，自然也就实现了UserName和Password配对存在的必然性。
四、安全特性分析和选取Mask的因素：
[1] 密钥空间（稳定性）
这里我们选用的DES作为对称加密算法，密钥64位。假设Mask为低n位，
Mask2变换是过滤低n位，那么密钥E的低n位始终为0；
C <= Mask即低n位有效，B为32位整数 ，那么E的低（32+n）有效
由于E为64位密钥，也就是说要废弃高端的（32-n）位。由此两点，可以看出原本64位密钥，引入Mask后只有32位有效。图示如下：
显然，对于任意的Mask，密钥空间具有高度的稳定性。中间有效的32位就像一个滑动窗口，根据不同的Mask可以自由移动。这种稳定性对于密码学算法来说是至关重要的。
对于Cracker来说，Mask的值是就是已知的，暴力枚举密钥32位即可；对于普通选手，Mask是未知的，那么需要的是32倍的时间。从总体来说，时间复杂度是O（2^32）。
[2] 解空间（即UserName和Password配对空间）（不唯一）
由于C=Mask2(A) <= Mask ==〉一个UserName对应((Mask+1)/A+1)>=2个Password。例如Mask=255，C=64，那么有5个Password；如果C=1，那么就有257个密码；如果Mask再大，那么这个值就是非常恐怖的。为了不让Password泛滥，我们需要对Mark2变换作一些额外的处理来控制C的值域。至于具体如何处理，会在下个部分“算法的可扩展性”中稍作介绍。
另外，如果A为0，那么C为0，此时就无解，这种情况也需要作特殊处理。（btw:如果取了个用户名，其Hash散列值为0，多少有点RPWT
)
总体来说，对于一个UserName存在多个Password，如果对于Mask2变换进行处理，那么可以控制Password的数量在较小的范围。
另外有个比较重要的特性是，对于同一个UserName所对应的多个Passwod总是连续的，如果说找到一个Password的话，那么其他的几个就在相临的位置。或许有人会说，这个特性不好，我倒是不这么认为。宝藏总是藏在某一个特别隐蔽的地方，而不会把宝藏分成x份找x个地方藏。所以严重支持“宝藏原理”，如果有能力到达这个位置的，宝藏随你取，这里也是一样，如果谁有能力找到一个Password，那么再送你几个也何妨。
五、模型的可扩展性
限定扩展的范围：本模型的核心思想是充分利用“乘法和除法”。其他的诸如Hash，DES等在这个模型中都是次要的东西，仅仅是一个点上的细致的东西。
[1] 密钥空间的拓展和大整数除法
密钥空间，对于一个算法的可靠性来说是个非常重要的指标。在这个模型，我以64位为例并非随便选的，选取的密钥长度的标准是“大整数除法” 算法的性能。从我个人来说，对于“大整数除法”还没能想到一个高效的算法。一些大整数库到有相关的算法，然而我不愿意在这个算法中引入这么个模块，当然如果有人愿意这么做也无妨。如果能够很好的解决“大整数除法”这个问题，那么密钥的长度可以任意长，而且mask的可调范围以及A，B，C等值域也将随之大大扩展。
我设计的初衷也是基于“大整数除法”的情况下，而当我无法实现时，退而求其次。在32位平台，支持的64位整数的运算，所以我选取的密钥为64位，在不需要额外处理高精度大整数算法的情况下充分利用系统所提供的功能；在64位平台时，如果直接支持128或者更高位数的运算，此时的选取标准就是选取系统默认支持运算的最大位数作为密钥的长度。
为什么“大整数除法”这个算法可以成为这个模型的一个瓶颈？因为写注册机时需要用到这个算法。正如设计原则第2点中所说，软件的作者必须要能够写注册机。
已知 UserName 和 Key 求 Password，转化下问题为已知 A、E 求 B ，那么B的值域为[ E / Mask2(A) , ( E + Mask ) / Mask2(A) ]，(注：低段向上取整，高端向下取整）。现在Mask2(A)=C为一个比较小的整数，但若Mask为256位的整数，那么就不能这样用除法直接进行运算了。
事实上，这里有个比较好的改进算法。
对于这个模型中A和B来说，他们都是32位整数，处于同等地位，对称式的。扩展下，让A和B为任意位的整数，而Mask的值为32位以内，求B的值域时被除数是A的Mask2变换值即C，又不是A，所以只需要限制Mask即可。于是我们的密钥长度在理论上就不受限制，只有保证A和B的位数和不超过密钥的长度即可。如果你一定要超过也没关系，只是在某些情况下会无解。
（注：网络有一些关于大整数除法的资料，需要用到牛顿插值等数值计算方法，有待证实）
[2] 扩展Mask变换（关于Mask变换的原理请参考前文）
在示例中Mask变换是采用简单的’&’和’~’操作实现，在变换中可以进行相应的控制即可控制Password数量。现在的Mask2变换中取的是低8位的，那么稍作修改即成为滑动窗口式；也可以在C上直接加一个固定的值，只要不超Mask即可。
[3] 散列算法的选取
在本例中使用的是CRC32，刚好32位，如果位数更多的话，可以使用MD5等算法，这里的安全性要求不是很高，能够让字符串转化为整数值（任意位数）即可。
[4] Y变换
字符串与整数的对应。字符串可由‘a’-‘z’，‘A’-‘Z’和‘0’-‘9’组成。Y变换可以为26进制，36进制，52进制，62进制等，也可以是其他任何的映射关系，根据需要而定。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
脑算
 得密钥空间的扩展password-Y->B，这个流程只是UI中的字符串与内部处理的大整数的一个转换 设计的时候就是当作已知的来处理 “解密出原始数据的过程中,加入过滤机制”，指密钥过滤？ |
|
|
|
|
|
|
