《一个软件调试的确定与不确定的心得》的心得

小试锋芒 · 发表于 2015-4-28 15:21:32

抽时间拜读了GG大神的的大作《一个软件调试的确定与不确定的心得》，文中，GG大神得出了这样的推论：

推测1.
31位的字符串是从32位中按照某种规律剔除掉了1位。同理，30位的字符串是剔除了2位。
推测2.
31和30位的字符串剔除掉了数字0或者某种规律上的数字0。

为了弄清楚这个问题，我们必须回到MD5算法的具体运算过程上来。
那么，我们还是首先来了解下MD5吧。

Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。

MD5功能：
输入任意长度的信息，经过处理，输出为128位的信息（数字指纹）；
不同的输入得到的不同的结果（唯一性）；
根据128位的输出结果不可能反推出输入的信息（不可逆）；

MD5用途：
1、防止被篡改：
1）比如发送一个电子文档，发送前，我先得到MD5的输出结果a。然后在对方收到电子文档后，对方也得到一个MD5的输出结

果b。如果a与b一样就代表中途未被篡改。2）比如我提供文件下载，为了防止不法分子在安装程序中添加木马，我可以在网站上

公布由安装文件得到的MD5输出结果。3）SVN在检测文件是否在CheckOut后被修改过，也是用到了MD5.

MD5算法过程：
对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列

的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

   第一步、填充：如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的

方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)；

   第二步、记录信息长度：用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为

N*512+448+64=(N+1)*512位。

   第三步、装入标准的幻数（四个整数）：标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=(FEDCBA98)

16，D=(76543210)16）。如果在程序中定义应该是（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。有点

晕哈，其实想一想就明白了。

   第四步、四轮循环运算：循环的次数是分组的个数（N+1）

   1）将每一512字节细分成16个小组，每个小组64位（8个字节）

   2）先认识四个线性函数(&是与,|是或,~是非,^是异或)
  F(X,Y,Z)=(X&Y)|((~X)&Z)
  G(X,Y,Z)=(X&Z)|(Y&(~Z))
  H(X,Y,Z)=X^Y^Z
  I(X,Y,Z)=Y^(X|(~Z))

3）设Mj表示消息的第j个子分组（从0到15），<<<s表示循环左移s位，则四种操作为：
  FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)
  GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<<<s)
  HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<<<s)
  II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<<<s)

4）四轮运算
第一轮
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)

第二轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)

5）每轮循环后，将A，B，C，D分别加上a，b，c，d，然后进入下一循环。

看完上面的，晕吧，我们简单点整理如下：

MD5算法：
第一步：增加填充
增加padding使得数据长度（bit为单位）模512为448。如果数据长度正好是模512为448，增加512个填充bit，也就是说填充的个

数为1-512。第一个bit为1，其余全部为0。

第二步：补足长度
将数据长度转换为64bit的数值，如果长度超过64bit所能表示的数据长度的范围，值保留最后64bit，增加到前面填充的数据后

面，使得最后的数据为512bit的整数倍。也就是32bit的16倍的整数倍。在RFC1321中，32bit称为一个word。

第三步：初始化变量：
用到4个变量，分别为A、B、C、D，均为32bit长。初始化为：
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10

第四步：数据处理：
首先定义4个辅助函数：
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
其中：XY表示按位与，X v Y表示按位或，not(X)表示按位取反。xor表示按位异或。

函数中的X、Y、Z均为32bit。

定义一个需要用到的数组：T(i),i取值1-64,T(i)等于abs(sin(i))的4294967296倍的整数部分,i为弧度。
假设前三步处理后的数据长度为32*16*Nbit
第五步：输出：
最后得到的ABCD为输出结果，共128bit。A为低位，D为高位。

还复杂了，再简单点？可以！

MD5算法：

一、补位
二、补数据长度
三、初始化MD5参数
四、处理位操作函数
五、主要变换过程
六、输出结果

好了，码字工作和科普工作结束了，回到我们的主题上来。有兴趣的朋友可以根据整个算法流程在od里跟踪下，也花不了多少时间，这里篇幅有限，只能说重点。GG在文中提到注册码也就是假码在OD里经过一系列的运算，得到一个长的字符串，该字符串长度有时候是32位，有时候是31位，甚至更少，问题的关键就出在了上面说的MD5算法的第六步上，也就是输出结果上。

我手头上MD5源码（delphi版本）的输出函数是通过如下方式来实现：

function MD5Print(D: MD5Digest): string;
var
I: byte;
const
Digits: array[0..15] of char =
('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
begin
Result := '';
for I := 0 to 15 do Result := Result + Digits[(D[I] shr 4) and $0f] + Digits[D[I] and $0f];
end;

复制代码

通过OD里的跟踪，发现该作者的实现并非采用这个方式：

00408A50 / 08C9 or cl,cl
00408A52 |. 75 17 jnz short AtomicAl.00408A6B
00408A54 |. 09C0 or eax,eax
00408A56 |. 79 0E jns short AtomicAl.00408A66
00408A58 |. F7D8 neg eax
00408A5A |. E8 07000000 call AtomicAl.00408A66
00408A5F |. B0 2D mov al,0x2D
00408A61 |. 41 inc ecx
00408A62 |. 4E dec esi
00408A63 |. 8806 mov byte ptr ds:[esi],al
00408A65 |. C3 retn
00408A66 |nbsp; B9 0A000000 mov ecx,0xA
00408A6B |> 52 push edx
00408A6C |. 56 push esi
00408A6D |> 31D2 /xor edx,edx
00408A6F |. F7F1 |div ecx
00408A71 |. 4E |dec esi
00408A72 |. 80C2 30 |add dl,0x30
00408A75 |. 80FA 3A |cmp dl,0x3A
00408A78 |. 72 03 |jb short AtomicAl.00408A7D
00408A7A |. 80C2 07 |add dl,0x7
00408A7D |> 8816 |mov byte ptr ds:[esi],dl
00408A7F |. 09C0 |or eax,eax
00408A81 |.^ 75 EA \jnz short AtomicAl.00408A6D
00408A83 |. 59 pop ecx
00408A84 |. 5A pop edx
00408A85 |. 29F1 sub ecx,esi
00408A87 |. 29CA sub edx,ecx
00408A89 |. 76 10 jbe short AtomicAl.00408A9B
00408A8B |. 01D1 add ecx,edx
00408A8D |. B0 30 mov al,0x30
00408A8F |. 29D6 sub esi,edx
00408A91 |. EB 03 jmp short AtomicAl.00408A96
00408A93 |> 880432 /mov byte ptr ds:[edx+esi],al
00408A96 |> 4A dec edx
00408A97 |.^ 75 FA \jnz short AtomicAl.00408A93
00408A99 |. 8806 mov byte ptr ds:[esi],al
00408A9B \> C3 retn

复制代码

为了更好的理解这段函数的功能，我以注册码12345-12345-12345-12345为例，用PYG密码工具算出来标准的MD5结果是：
8620AD0858B57265404EB2727A871ECC，而在OD里的结果却是8620AD858B57265404EB2727A871ECC，是31位的，仔细观察，可以发现中间少了一个0，也就是在输出的过程中，0x86输出为字符串"86"，0x20输出为字符串“20”，0xAD输出为字符串“AD”，0x08输出为字符串“8”，而标准的MD5算法中，0x08输出为字符串“08”，所以作者在这里并没有对首位为0的数字在输出的过程中进行处理，而采取了丢弃的动作。这也就导致结果有的是32位，有的是31位。
说的具体点，0x86输出为字符串"86"的过程是 0x86 mod 0xA 得到余数0x6 商是0x8 ,0x6判断下是否为0-9，如果是则0x6+0x30 得到 0x36 ，也就是字符“6”ascii的值，接下来把商0x8 mod 0xA 得到余数0x8，判断是否为0-9，如果是则0x8+0x30,得到0x38，也就是字符“8”ascii的值。最后把“8”和“6”连接起来就是输出结果“86”0x08输出为字符串“08”的过程是0x08 mod 0xA得到余数0x8 商是0x0，0x8判断下是否为0-9，如果是则0x8+0x30 得到 0x38 ，也就是字符“8”ascii的值，但是这里要注意，作者用一个

00408A7F |. 09C0 |or eax,eax

复制代码

命令来判断商是否为0，如果为0就不继续了，所以接下来的0就忽略了！最后就只有一个字符“8”而不是“08”。这也就是GG大神所说的“剔除”了奇数位上0了。

综上所述，GG大神在最后的推测是正确的。

   最后，我们再找个例子来验证下我们的推测。比如表中的第某组：9AC9D23576E1AC62FD1CCA5ED1B28615。
         观察了下，没有数字0存在，而且长度正好是32位，说明99.9999%的可能性是MD5;
   再看这一组有0存在的：FA9B48813EDF8A6DE3C12A90B9F7F0FF，有数字0存在，长度也等于32位。而且，数字0只在偶数位上！
   那么这也间接说明了我的推测是正确的。
   这些内置字符串应该是MD5后的结果、且MD5结果中（32位）的奇数位置上的数字0被剔除掉了。

GGLHY · 发表于 2015-4-28 15:34:26

好强悍~~~{:soso_e179:}对MD5的具体实现过程作了分析。猛啊~

我没有去跟踪MD5的具体过程，只是根据附表猜测了一下。感谢兄弟的解答！{:soso_e181:}

wgz001 · 发表于 2015-4-28 16:00:15

沙发开始本来是我的，但是权限是255，抢不到　{:soso_e101:}

tree_fly · 发表于 2015-4-28 18:43:48

楼主对MD5加密分析如此透彻，关键是对GG大神的热情很是羡慕哈@GGLHY

wzgangwzgang · 发表于 2015-4-29 08:55:55

只能看热闹，太复杂了，模拜！！！

Dxer · 发表于 2015-4-29 13:04:33

wgz001 发表于 2015-4-28 16:00
沙发开始本来是我的，但是权限是255，抢不到　

权限255 那是为了GG大哥能坐上沙发而准备的。

很羡慕你们这群算法大婶{:soso_e109:} 终有一天我也会。o(∩_∩)o

wgz001 · 发表于 2015-4-29 13:33:08

Dxer 发表于 2015-4-29 13:04
权限255 那是为了GG大哥能坐上沙发而准备的。

很羡慕你们这群算法大婶终有一天我也会 ...

是的，我看好你　{:soso_e182:}

LoBv · 发表于 2015-7-28 20:38:50

虽然没有看懂，但是仍然给楼主一个大大的赞

		自动登录	找回密码
密码			加入我们

[原创] 《一个软件调试的确定与不确定的心得》的心得

评分

点评

点评

点评