CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的，而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数，在CRC运算中我们称之为poly，而宽度W就是poly最高位的位置。比如poly 1001的W是3，而不是4。注意最高位总是1，当你选定一个宽度，那么你只需要选择低W各位的值。假如我们想计算一个位串的CRC码，并要保证每一位都要被处理，因此我们需要在目标位串后面加上W个0。下面举例说明CRC算法的过程。
在此例中，我们假设位串为110101101。
Poly = 10011（宽度W = 4）
Bitstring + W zeros = 110101101 0000
10011/1101011010000/110000101 （我们不关心此运算的商）
10011||||||||
-----||||||||
10011|||||||
10011|||||||
-----|||||||
00001||||||
00000||||||
-----||||||
00010|||||
00000|||||
-----|||||
00101||||
00000||||
-----||||
01010|||
00000|||
-----|||
10100||
10011||
-----||
01110|
00000|
-----|
11100
10011
-----
1111 -> 余数 -> CRC！
计算过程总结如下：
1. 只有当位串的最高位为1，我们才将它与poly做XOR运算，否则我们只是将位串左移一位。
2. 异或运算的结果实质上是被操作位串与poly的低W位进行运算的结果，因为最高位总为0。
CRC原理及其逆向破解方法：
介绍：
这篇短文包含CRC原理介绍和其逆向分析方法,很多程序员和破解者不是很清楚了解
CRC的工作原理,而且几乎没人知道如何逆向分析它的方法,事实上它是非常有用的.
首先,这篇教程教你一般如何计算CRC,你可以将它用在数据代码保护中.第二,主要是
介绍如何逆向分析CRC-32,你可以以此来分析程序中的CRC保护（象反病毒编码）.当然
有很多有效的工具用来对付CRC,但我怀疑它是否会说明原理.
我要告诉你,这篇短文里中应用了很多数学知识,这不会影响一些人,而且会被一般的
程序员与逆向分析者很好理解.为什么？那么如果你不知道数学是如何被应用在CRC中,
我建议你可以停止继续学习了.所以我假定你们（读者）都是具备二进制算术知识的.
第一部分：CRC 介绍,CRC是什么和计算CRC的方法.
循环冗余码 CRC
我们都知道CRC.甚至你没有印象,但当你想到那些来自诸如RAR,ZIP等压缩软件发给你
由于错误连接和其他一些意外原因导致的文件错误的恼人的消息时,你就会知道.CRC是块
数据的计算值,比如对每一个文件进行压缩.在一个解压缩过程中,程序会从新计算解压文件
的CRC值,并且将之与从文件中读取的CRC值进行比对,如果值相同,那么正确.在CRC-32中,
会有1/2^32的可能性发生对确认数据更改的校验错误.
很多人认为CRC就是循环冗余校验,假如CRC真的就是循环冗余校验,那么很多人都错用了
这个术语.你不能说"这个程序的CRC是12345678".人们也常说某一个程序有CRC校验,而不
说是 "循环冗余校验" 校验.结论：CRC 代表循环冗余码,而不是循环冗余校验.
计算是如何完成的呢？好,主要的想法就是将一个文件看成一个被一些数字分割的很长的
位字串,这里会有一个余数---CRC！你总会有一个余数(可以是0),它至多比除数小一.
(9/3=3 余数=0 ; (9+2)/3=3 余数=2)
(或者它本身就包含一个除数在其中).
在这里CRC计算方法与除法有一点点区别,除法就是将被减数重复的减去除数X次,然后留下
余数.如果你希望得到原值,那么你就要把除数乘上X次,然后加上余数.
CRC计算使用特殊的减法与加法完成的.也就是一种新的"算法".计算中每一位计算的进位值
被"遗忘"了.
看如下两个例子,1是普通减法,2和3是特殊的.
-+
(1) 1101 (2) 1010 1010 (3) 0+0=0 0-0=0
1010- 1111+ 1111- 0+1=1 *0-1=1
---- ---- ---- 1+0=1 1-0=1
0011 0101 0101 *1+1=0 1-1=0
在(1)中,右数第二列可以看成是0-1=-1,因此要从高位借1,就变成(10+0)-1=1.(这就象普通
的'by-paper'十进制减法).特例(2,3)中,1+1会有正常的结果10,'1'是计算后的进位.这个值
被忽略了.特殊情况0-1应该有正常结果'-1'就要退到下一位.这个值也被忽略了.假如你对编程
有一定了解,这就象,XOR 操作或者更好.
现在来看一个除法的例子:
在普通算法中:
1001/1111000\1101 13 9/120\13
1001 - 09 -|
---- -- |
1100 30 |
1001 - 27 -
---- --
0110 3 -> 余数
0000 -
----
1100
1001 -
----
011 -> 3, 余数
在CRC算法中:
1001/1111000\1110 9/120\14 余数为 6
1001 -
----
1100
1001 -
----
1010
1001 -
----
0110
0000 -
----
110 -> 余数
(例 3)
这个除法的商并不重要,也没必要去记住,因为他们仅仅是一组无关紧要的位串.真正
重要的是余数!它就是这个值,可以说比原文件还重要的值,他就是基本的CRC.
过度到真正的CRC码计算.
进行一个CRC计算我们需要选则一个除数,从现在起我们称之为"poly".宽度W就是最高位
的位置,所以这个poly 1001的W 是3,而不是4.注意最高位总是1,当你选定一个宽度,那么你只
需要选择低W各位的值.
假如我们想计算一个位串的CRC码,我们想确定每一个位都被处理过,因此,我们要在目标
位串后面加上W个0位.在此例中,我们假设位串为1111.请仔细分析下面一个例子:
Poly = 10011, 宽度 W=4
位串 Bitstring
Bitstring + W zeros = 110101101 + 0000
10011/1101011010000\110000101 (我们不关心此运算的商)
10011|||||||| -
-----||||||||
10011|||||||
10011||||||| -
-----|||||||
00001||||||
00000|||||| -
-----||||||
00010|||||
00000||||| -
-----|||||
00101||||
00000|||| -
-----||||
01010|||
00000||| -
-----|||
10100||
10011|| -
-----||
01110|
00000| -
-----|
11100
10011 -
-----
1111 -> 余数 -> the CRC!
(例 4)
重要两点声明如下:
1.只有当Bitstring的最高位为1,我们才将它与poly做XOR运算,否则我们只是将
Bitstring左移一位.
2.XOR运算的结果就是被操作位串bitstring与低W位进行XOR运算,因为最高位总为0.
算法设计:
你们都应知道基于位运算的算法是非常慢的而且效率低下.但如果将计算放在每一字节上
进行,那么效率将大大提高.不过我们只能接受poly的宽度是8的倍数(一个字节;).可以形
象的看成这样一个宽度为32的poly(W=32):
3 2 1 0 byte
+---+---+---+---+
Pop! <--| | | | |<-- bitstring with W zero bits added, in this case 32
+---+---+---+---+
1<--- 32 bits ---> this is the poly, 4*8 bits
(figure 1)
这是一个你用来存放暂时CRC结果的记存器,现在我称它为CRC记存器或者记存器.你从右
至左移动位串,当从左边移出的位是1,则整个记存器被与poly的低W位进行XOR运算.(此例
中为32).事实上,我们精确的完成了上面除法所做的事情.
移动前记存器值为:10110100
当从右边移入4位时,左边的高4位将被移出,此例中1011将被移出,而1101被移入.
情况如下:
当前8位CRC记存器 : 01001101
刚刚被移出的高4位 : 1011
我们用此poly : 101011100, 宽度 W=8
现在我们用如前介绍的方法来计算记存器的新值.
顶部 记存器
---- --------
1011 01001101 高四位和当前记存器值
1010 11100 + (*1) Poly 放在顶部最高位进行XOR运算 (因为那里是1)
-------------
0001 10101101 运算结果
现在我们仍有一位1在高4位:
0001 10101101 上一步结果
1 01011100+ (*2) Poly 放在顶部的最低位进行XOR运算 (因为那里是1)
-------------
0000 11110001 第二步运算结果
^^^^
现在顶部所有位均为0,所以我们不需要在与poly进行XOR运算
你可以得到相同的结果如果你先将(*1)与(*2)做XOR然后将结果与记存器值做XOR.
这就是标准XOR运算的特性:
(a XOR b) XOR c = a XOR (b XOR c) 由此,推出如下的运算顺序也是正确的.
1010 11100 poly (*1) 放在顶部最高位
1 01011100+ polys (*2) 放在顶部最低位
-------------
1011 10111100 (*3) XOR运算结果
The result (*3) 将(*3)与记存器的值做XOR运算
1011 10111100
1011 01001101+ 如右:
-------------
0000 11110001
你看到了吗?得到一样的结果!现在(*3)变的重要了,因为顶部为1010则(3)的值总是等于
10111100(当然是在一定的条件之下)这意味着你可以预先计算出任意顶部位结合的XOR值.
注意,顶部结果总是0,这就是组合XOR操作导致的结果.(翻译不准确,保留原文)
现在我们回到figure 1,对每一个顶部字节的值都做移出操作,我们可以预先计算出一个值.
此例中,它将是一个包含256个double word(32 bit)双字的表.(附录中CRC-32的表).
(翻译不准确,保留原文)
用伪语言表示我们的算法如下:
While (byte string is not exhausted)
Begin
Top = top_byte of register ;
Register = Register shifted 8 bits left ORred with a new byte from string ;
Register = Register XORred by value from precomputedTable at position Top ;
End
direct table算法:
上面提到的算法可以被优化.字节串中的字节在被用到之前没有必要经过整个记村器.用
这个新的算法,我们可以直接用一个字节去XOR一个字节串通过将此字节移出记存器.结果
指向预先计算的表中的一个值,这个值是用来被记存器的值做XOR运算的.
我不十分确切的知道为什么这会得到同样的结果(这需要了解XOR运算的特性),但是这又
极为便利,因为你无须在你的字节串后填充0字节/位.(如果你知道原理,请告诉我:)
让我们来实现这个算法:
+----< byte string (or file) 字节串,(或是文件)
|
v 3 2 1 0 byte 字节
| +---+---+---+---+
XOR---<| | | | | Register 记存器
| +---+---+---+---+
| |
| XOR
| ^
v +---+---|---+---+
| | | | | | Precomputed table 值表(用来进行操作)
| +---+---+---+---+
+--->-: : : : :
+---+---+---+---+
| | | | |
+---+---+---+---+
(figure 2)
'reflected' direct Table 算法:
由于这里有这样一个与之相对应的'反射'算法,事情显得复杂了.一个反射的值/记存器
就是将它的每一位以此串的中心位为标准对调形成的.例如:0111011001就是1001101110
的反射串.
他们提出'反射'是因为UART(一种操作IO的芯片)发送每一个字节时是先发最没用的0位,
最后再发最有意义的第七位.这与正常的位置是相逆的.
除了信息串不做反射以外,在进行下一步操作前,要将其于的数据都做反射处理.所以在
计算值表时,位向右移,且poly也是作过反射处理的.当然,在计算CRC时,记存器也要向右
移,而且值表也必须是反射过的.
byte string (or file) -->---+
| 1. 表中每一个入口都是反射的.
byte 3 2 1 0 V 2. 初始化记存器也是反射的.
+---+---+---+---+ | 3. 但是byte string中的数据不是反射的,
| | | | |>---XOR 因为其他的都做过反射处理了.
+---+---+---+---+ |
| |
XOR V
^ |
+---+---|---+---+ |
| | | | | | 值表
+---+---+---+---+ |
: : : : : <---+
+---+---+---+---+
| | | | |
+---+---+---+---+
(figure 3)
我们的算法如下:
1. 将记存器向右移动一个字节.
2. 将刚移出的哪个字节与byte string中的新字节做XOR运算,
得出一个指向值表table[0..255]的索引
3. 将索引所指的表值与记存器做XOR运算.
4. 如数据没有全部处理完,则跳到步骤1.
下面是这个算法的简单的可执行汇编源码:
完整的CRC-32标准所包含的内容:
Name : "CRC-32"
Width : 32
Poly : 04C11DB7
Initial value : FFFFFFFF
Reflected : True
XOR out with : FFFFFFFF
作为对你好奇心的奖励, 这里是CRC-16标准: :)
Name : "CRC-16"
Width : 16
Poly : 8005
Initial value : 0000
Reflected : True
XOR out with : 0000
'XOR out with' 是为了最终得到CRC而用来与记存器最后结果做XOR运算的值.
假如你想了解一些关于'reversed'逆向CRC poly的话,请看我的参考文章.
我是在16位DOS模式下用的32位编码,因此你会在这个程序中看到很多32位与16位混合
的编码...当然这是很容易转换成纯32位编码的.注意这个程序是经过完整测试并且能够
正常运行的.下面的Java 和 C 代码都是由这个汇编代码而来的.
底下的这段程序就是用来计算CRC-32 table的:
xor ebx, ebx ;ebx=0, 将被用做一个指针.
InitTableLoop:
xor eax, eax ;eax=0 为计算新的entry.
mov al, bl ;al<-bl
;生成入口.
xor cx, cx
entryLoop:
test eax, 1
jz no_topbit
shr eax, 1
xor eax, poly
jmp entrygoon
no_topbit:
shr eax, 1
entrygoon:
inc cx
test cx, 8
jz entryLoop
mov dword ptr[ebx*4 + crctable], eax
inc bx
test bx, 256
jz InitTableLoop
注释: - crctable 是一个包含256个dword的数组.
- 由于使用反射算法,EAX被向右移.
- 因此最低的8位被处理了.
用Java和C写的代码如下(int is 32 bit):
for (int bx=0; bx<256; bx++){
int eax=0;
eax=eax&0xFFFFFF00+bx&0xFF; // 就是 'mov al,bl' 指令
for (int cx=0; cx<8; cx++){
if (eax&&0x1) {
eax>>=1;
eax^=poly;
}
else eax>>=1;
}
crctable[bx]=eax;
}
下面的汇编代码是用来计算CRC-32的:
computeLoop:
xor ebx, ebx
xor al, [si]
mov bl, al
shr eax, 8
xor eax, dword ptr[4*ebx+crctable]
inc si
loop computeLoop
xor eax, 0FFFFFFFFh
注释: - ds:si 指向将要被处理的byte string信息流.
- cx 信息流的长度.
- eax 是当前的CRC.
- crctable是用来计算CRC的值表.
- 此例中记存器的初始值为: FFFFFFFF.
- 要将中间值与FFFFFFFFh做XOR才能得到CRC
下面是Java和C写的代码:
for (int cx=0; cx>=8;
eax^=crcTable[ebx];
}
eax^=0xFFFFFFFF;
现在我们已经完成了本文的第一部分:CRC原理部分,所以如果你希望能够对CRC做更深
的研究,那么我建议你去读在本文最后给出连接上的资料,我读了.好了,终于到了本文最
有意思的部分,CRC的逆向分析!
