CRC32 算法分析、逆向（附源码）
前几天发了个工具CRC32编辑器：
http://bbs.pediy.com/showthread.php?t=119765&highlight=
有些朋友不知道什么用途
1，让自己的好看点（自我安慰）
2，遇到校验的可能有用，自己写程序的时候也能用用
现在略微整理下算法和分析过程，拿出来共享和交流。
下面是我的全分析过程.
' ******************** CRC验证 ********************
'返回验证码 二进制 串
Public Function CRC32(ByRef bArrayIn() As Byte, ByVal lLen As Long) As Long
Dim lCurPos As Long
Dim lTemp As Long
Dim crcTable(0 To 255) As Long
Dim i As Long, x As Long, crc As Long
Const Limit = &HEDB88320
For i = 0 To 255
crc = i
For x = 0 To 7
If crc And 1 Then
crc = (((crc And &HFFFFFFFE) \ 2) And &H7FFFFFFF) Xor Limit
Else
crc = ((crc And &HFFFFFFFE) \ 2) And &H7FFFFFFF
End If
Next x
crcTable(i) = crc
Next i
'以上初始化 出来一个表(是固定的)
If lLen < 0 Then Exit Function
lTemp = &HFFFFFFFF
For lCurPos = 0 To lLen
lTemp = (((lTemp And &HFFFFFF00) \ &H100) And &HFFFFFF) Xor (crcTable((lTemp And 255) Xor bArrayIn(lCurPos)))
'前三位*3 xor 表(第四位*1 xor 新字节*1)*4
Next lCurPos
'取反输出结果 -->结果取其十六进制标记就是我们常见的CRC32了
CRC32 = lTemp Xor &HFFFFFFFF
End Function
关键部分就再循环,他做了什么呢
它每次加入一个新字节,和先前计算的结果4字节进行计算
先前由(高到底): A1 A2 A3 A4
新加入的字节: B(n)
计算结果 : C1 C2 C3 C4
计算方式:(注意 ^ 为 异或计算)
┌→A1 A2 A3 A4 →A4 ^ B(n)
│
│ 00 A1 A2 A3 X
│ ^ ^ ^ ^ ↓(查表)
│ T1 T2 T3 T4 ←←T(X)
│ ↓ ↓ ↓ ↓
└─T1 C2 C4 C4
↓ ↓ ↓ ↓(最后一次完成后取反)
R1 R2 R3 R4 ;CRC32 结果
新值C经过一次计算后,他的最高位C1没变,是查表的最高位T1
那么这个表T1的值是不是唯一的呢,我们把表打印出来(见文章末尾),看一下
可喜的是,最高位(00-FF)都是一对一得关系,从00到FF没有重复,那么逆向推导就成为可能了
现在我们知道了文件得CRC32,
那么就知道最后一次循环后得值(取反可得),这个值得最高位,就是它最后一次查表的值
由于这个表和查表是一一对应关系,我们可以知道两点
1. T1 可以得到 T(X) 也就是 T1 T2 T3 T4
2. T1 可以得到 X 也就是 A4 ^ B(n)
由 T(X) 和 C 我们可以得到 A1 A2 A3 ,这是倒数第一次循环计算的高位3字节,
用同样的方法我们可以得到
倒数第二次循环计算的高位2字节
倒数第三次循环计算的高位1字节
倒数第四次循环计算的高位0字节 (也就是说4次这样的循环计算后,再前面的结果就是任意的了)
一次循环,会模糊掉一个字节位的crc32校验,4次循环会模糊掉四字节的CRC32校验
这样只要指定最后4个字节,我们就可以达到修改出任意CRC32
现在,我们要把一个CRC校验文件添加4字节
CE037B28 转换为 09635B62
(这也是我最初的实验，很痛苦；计算试了几次没成功，从算法上看又可行，因为自己一没注意就计算错了)
CE037B28 -> 09635B62 ;目的CRC
'取反
31FC84D7 -> F69CA49D
↓↓↓↓
↓9CA49D
F6B9265B D5 {表} F6查表→D5（X的值）
↓↓↓↓ ↓ →F6B9265B（T的值）
F62582C6 ↓
去掉最高位 F6 ↓
; 向高位移动
2582C6[*D5] ; N1 xor old1 =x1
2582C6[^D5];
82C6 [^D5]
25 6FD2 A0 B2 {表}
25 ED14 [^D5^A0]
ED14 [^D5^A0] [^B2]
EDB88320 =80 {表}
AC[^D5^A0^83][^A5^20][^6D]
AC BC F9 40 2B {表}
[^D5^A0^83^BC][^B2^20^F9][^80^40][^2B]
31 FC 84 D7 ；与原来的31FC84D7再次异或
7B 97 44 FC ；这是最后添加的4个字节
为什么到最后要这样再异或一次呢，
因为A^B=C → A^C=B → B^C=A
原来CRC取反 A1 A2 A3 A4 A
修改4字节CRC取反 B1 B2 B3 B4 B
目的CRC取反 C1 C2 C3 C4 C
要的到A^B=C 我们已知A，C 异或一下就得到我们需要的B了，虽然还需要经过一段运算
认真的读者会发现，CRC32逆运算更容易得到想要的CRC的值，而正运算几乎是不可能的，
因为我们每加一新数据时候，只能确定CRC4字节中的1字节，而其他字节都会有影响的。
=========================================
问题二：
如何在文件中任意部分覆盖4字节得到想要的CRC值呢，假定一个文件长度为len，覆盖位置offset，文件最后CRC结果为d（取反结果为D）
首先我们想，如果覆盖掉最后4字节的话，
我们只需要先计算文件前面 len-4 字节CRC，再添加4字节就行了，这个很简单。
如果在文件中央，
我们要使文件最后的CRC满足条件D，而我们可以控制的地方只有（offset~offset+3）4字节区域，
分成3部分：
前部分，覆盖部分（4字节），后面部分
前部分：CRC可以计算出来
后面部分，如果知道最终的目标CRC，又知道它每一次计算的B（n），
那么倒数任何次的A1 A2 A3 A4 ，T1 T2 T3 T4，X，C1 C2 C3 C4都可以计算出来的，
计算方法和我们上面分析的 X 是不可以确定的，用他 X ^ B（n） 就得出A4了
那么我们 覆盖掉这4字节的任务就是这样了，后面部分要达到CRC结果为D的，那到覆盖部分的尾端时候需要的为C，
而前面覆盖部分可以直接计算得到结果A，覆盖部分只要把A调整为C（而不是直接调整为D）
思路好了，我附上原代码吧，知道大家都喜欢这个
- 标 题：CRC32 算法分析、逆向（附源码）
- 作 者：瞧红尘
- 时 间：2010-09-08 01:10:24
- 链 接：http://bbs.pediy.com/showthread.php?t=120018