CRC原理及其逆向分析方法
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的逆向分析!
------------------------------------------------------------------------------------
第二部分 CRC的逆向分析:
? 我遇到了很多障礙,當我思考如何破解CRC時.我試圖使用一些特殊順序的字節使CRC無效.
但我沒有做到...后來我意識到這種方法是行不同的,因為CRC內建了一些處理過程,無論你
改變任何位它都不會出問題,真正的CRC就是在不斷變化的,總是在變化的.找一些CRC程序,
你可以自己嘗試一下.?
? 現在我知道我只能'糾正'在CRC后面的那些我想改變的字節.所以我要構造一個字節序列,
它可以將CRC轉化成任何我想要的樣子!?
具體實現這個想法
一個字節串????? 01234567890123456789012345678901234567890123456789012
You want to change from? ^? this byte to? ^? this one.
就是位置9->26.
同時我們需要額外的4個字節用來在最后恢復原始字節串.
? 當你計算CRC-32時,從0-8都沒有問題,直到第9位,修補過的字節串會使CRC發生根本的改變.
即使當走過了第26位,以后的字節都沒有改變,你也不可能在得到原始的CRC了,不可能了!你讀
過后面的段落時就會明白為什么.間而言之,當你修改一個字節串時,要保證CRC不變.?
1. 計算并保存從1~9位的CRC.
2. 繼續計算直到第27位還有額外的4字節并保存結果.
3. 用1的值來計算新的字節串和額外4字節的CRC(對應patch后的新的CRC值),并將之保存.
4. 現在我們得到了一個新的CRC,但是我們希望將它還原成原先的CRC,所以我們用逆向算法
?? 來計算那額外的4字節.
1~3就是實際的情況,下面你將學到最關鍵的部分4.
'反轉'CRC-16
? 我想,先來介紹計算逆CRC-16對于你來說會簡單些.好的,我們現在處在一個恰當的位置,
在以修改代碼后面,就是你想將CRC還原的地方.我們知道原始的CRC(是在patch代碼之前計
算出來的)還有這個當前的記存器值.現在我們的目的就是計算可以改變當前記存器值到原
始記存器值的兩個字節.首先,我們用正常的方法計算這兩個未知字節的CRC.我們設他們為
X,Y.設記存器為a1,a0,只有0不能用來作為變量(00).:)在來看一下我們的CRC算法,figure
3,更好的理解下面我要做的.
好,我們開始:
用這兩字節串'X Y' 字節是從左邊開始被處理的.
記存器現在是a1 a0.
用'+'來表示XOR運算(和第一部分中用的一樣)
處理第一個字節, X:
a0+X??????????? 這是頂部字節的計算結果 (1)
b1 b0?????????? 這是(1)在表中索引對象.
00 a1?????????? 向右移動記存器.
00+b1 a1+b0???? 上面兩行對應位做XOR運算.
現在記存器為: (b1) (a1+b0)
處理第二個字, Y:
(a1+b0)+Y?????? 此輪頂部字節的計算結果(2)
c1 c0?????????? 這是(2)在表中的索引對象.
00 b1?????????? 向右移動記存器.
00+c1 b1+c0???? 上面兩行對應位做XOR運算.
最后記存器就是: (c1) (b1+c0)
我用一點不同的方法來表示:
a0 + X????? =(1)? 在表中指向b1 b0.
a1 + b0 + Y =(2)? 在表中指向c1 c0.
???? b1 + c0=d0?? 記存器中新的低位字節.
????????? c1=d1?? 記存器中新的高位字節.
??? (1)? (2)
Wow! 請大家暫時記住上面的信息:)
別著急, 下面給出一個有具體值的例子.
?
? 如果你想要的記存器的值是d1 d0(是原始的CRC),而且你知道在變換之前的記存器的值
(a1 a0)...那么你將要送如什么樣的2個字節進記存器來做CRC計算呢??
? 好了,現在我們的工作應該從幕后走到臺前來了.d0一定是bi+c0,并且d1一定是c1...
但是這到底是怎么回事,我聽到你這樣問了,你能知道b1和c0的值嗎???你還記得哪個值表
嗎?你只需要在表中查找c0 c1這個字的值就可以了因為你知道c1.所以你需要編寫一個查
找程序.假如你找到了這個值,一定要記住這個值的索引,因為這就是找出未知的兩個頂部
字節,舉例來說:(1)和(2)!
? 所以,現在你找到了c1 c0,那么如何來得到b1 b0呢?如果b1+c0=d0那么b1=d0+c0!如前所
述,現在你用哪個查找程序在表中查b1 b0的值.現在我們得到了所有計算X和Y所需要的值.
Cool huh??
a1+b0+Y=(2) so Y=a1+b0+(2)
a0+X=(1)??? so X=a0+(1)
實例.
讓我們來看看這個具體值的例子:
-register before: (a1=)DE (a0=)AD
-wanted register: (d1=)12 (d0=)34
在附錄的CRC-16的表中查找以12開頭值的入口.這里入口38h的值為12C0.試這找一找是否還
有以12開頭的值的入口.你不可能在找到的,因為我們計算每一中頂部字節組合而得的值的
入口,一共是256個值,記住!
現在我們知道(2)=38,c1=12,c0=C0,所以b1=C0+34=F4,現在查找以F4開頭的b1的入口.這里
入口4Fh的值是F441.
我們還知道? (1)=4F,b1=F4,b0=41,現在所有我們需要的都已經清楚了,接下來我們計算X,Y.
Y=a1+b0+(2)=DE+41+38=A7
X=a0+(1)?? =AD+4F?? =E2
結論:將CRC 記存器的值從 DEAD 變為 1234 我們需要這兩個字節 E2 A7 (以此順序).
? 你看,破解CRC校驗你需要反向計算,還有要記住的就是計算過程中的值.當你在用匯編編寫
查找表程序時,要注意intel在小模式中是反向存儲值的.現在你可能已經明白如何去破解這個
CRC-16了...下面介紹如何在CRC-32中實現.
破解 CRC-32
現在我們來看CRC-32,和CRC-16是一樣容易的(可能一樣的不容易你認為).這里你操作的對象
是4個字節的而不是2字節的.繼續向下看,將它與上面CRC-16版本做對比.
設4字節串 X? Y? Z? W? , 從左邊開始處理.
設記存器為? a3 a2 a1 a0
注意a3是MSB,而a0是LSB
處理第一個字節, X:
a0+X??????????????????? 這是頂部字節的計算結果(1).
b3??? b2??? b1??? b0??? 這是(1)在表中索引對象序列.
00??? a3??? a2??? a1??? 右移記存器.
00+b3 a3+b2 a2+b1 a1+b0 上面兩行對應位做XOR運算.
現在記存器是: (b3) (a3+b2) (a2+b1) (a1+b0)
Processing second byte, Y:
(a1+b0)+Y?????????????????????? 這是頂部字節的計算結果(2).
c3??? c2??? c1?????? c0???????? 這是(2)在表中索引對象序列.
00??? b3??? a3+b2??? a2+b1????? 右移記存器.
00+c3 b3+c2 a3+b2+c1 a2+b1+c0?? 上面兩行對應位做XOR運算.
現在記存器是: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)
Processing third byte, Z:
(a2+b1+c0)+Z???????????????????? 這是頂部字節的計算結果(3).
d3??? d2??? d1?????? d0????????? 這是(3)在表中索引對象序列.
00??? c3??? b3+c2??? a3+b2+c1??? 右移記存器.
00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 上面兩行對應位做XOR運算.
現在記存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)
Processing fourth byte, W:
(a3+b2+c1+d0)+W????????????????? 這是頂部字節的計算結果(4).
e3??? e2??? e1?????? e0????????? 這是(4)在表中索引對象序列.
00??? d3??? c3+d2??? b3+c2+d1??? 右移記存器.
00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 上面兩行對應位做XOR運算.
最后,記存器為: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)
我用一個不同一點的方法來表示:
a0 + X????????????????? =(1)? 在表中指向 b3 b2 b1 b0?
a1 + b0 + Y???????????? =(2)? 在表中指向 c3 c2 c1 c0?
a2 + b1 + c0 + Z??????? =(3)? 在表中指向 d3 d2 d1 d0?
a3 + b2 + c1 + d0 + W?? =(4)? 在表中指向 e4 e3 e2 e1?
???? b3 + c2 + d1 + e0? =f0
????????? c3 + d2 + e1? =f1
?????????????? d3 + e2? =f2
??????????????????? e3? =f3
??? (1)? (2)? (3)? (4)
(figure 4)
這里是用的與CRC-16同樣的方法來實現的,我會給出一個具體值的例子.查找用附錄中
CRC-32的值表.
Take for CRC register before, a3 a2 a1 a0 -> AB CD EF 66
Take for CRC register after,? f3 f2 f1 f0 -> 56 33 14 78 (wanted value)
我們開始:
First byte of entries??????????? entry?? value
e3=f3???????????????????? =56 -> 35h=(4) 56B3C423 for e3 e2 e1 e0
d3=f2+e2????? =33+B3????? =E6 -> 4Fh=(3) E6635C01 for d3 d2 d1 d0
c3=f1+e1+d2?? =14+C4+63?? =B3 -> F8h=(2) B3667A2E for c3 c2 c1 c0
b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 for b3 b2 b1 b0
Now we have all needed values, then
X=(1)+???????? a0=???????? DE+66=B8
Y=(2)+????? b0+a1=????? F8+D3+EF=C4
Z=(3)+?? c0+b1+a2=?? 4F+2E+FF+CD=53
W=(4)+d0+c1+b2+a3=35+01+7A+6B+AB=8E
(final computation)
結論:要將 CRC-32 的記存器的值從 ABCDEF66 改變到 56331478 我們需要這樣一個字節
序列: B8 C4 53 8E
CRC-32的破解算法
? 假如你考慮手動計算這個可以還原CRC記存器的字節序列,那么這將很難變成一個
簡潔的算法.?
?
看看下面這個最后計算的附加版本:
??????????????????????????? Position
X =(1) +??????????????? a0???? 0
Y =(2) +?????????? b0 + a1???? 1
Z =(3) +????? c0 + b1 + a2???? 2
W =(4) + d0 + c1 + b2 + a3???? 3
f0= e0 + d1 + c2 + b3????????? 4
f1= e1 + d2 + c3?????????????? 5
f2= e2 + d3??????????????????? 6
f3= e3???????????????????????? 7
(figure 5)
?
? 它就等同于figure 4,只不過是一些值/字節被交換了.這種方法可以幫助我們構造一個
簡潔的算法.這里我們用一個8字節的緩沖區,0-3位我們放置a0到a3,4-7位我們放置f0到
f3.象以前一樣,我們用這個已知值e3(由figure 5中得知)在表中查出(e3 e2 e1 e0),并且
象圖5(figure 5)中所示,將它們放到第4位(position 4),我們馬上得到了d3的值.因為f2=
e2+d3,所以f2+e2=d3.又因為(4)已知(入口值),我們照樣把它也放到位置3.然后在用d3查表
得到(d3 d2 d1 d0),同上也將他們放到圖中所述位置.同樣,由于有f1+e1+d2=c3在位置5上.
? 我們繼續做直到將b3 b2 b1 b0放到位置1,對了，就是它!? Et voila!
此時,緩沖區的第3-第0字節中已經包含全部元素,用來計算X~W!?
算法總結如下:
1.對于這個8字節的緩沖區,0~3字節放入a0...a3(CRC記存器起始值),4~7字節放入f0...f3
? (目標記存器的值).
2.取出位置7的已知值,查表得到相應值.
3.將查出值放如圖5相應位置,其實就是做XOR運算.(為了直觀,可以擬定此圖)
4.將入口字節放入圖中.也是做XOR運算.
5.繼續做2,3兩步3次,同時每次降低1個位置 position 5 to 4, 4 to 3 and so on.
算法的實現:
? 現在是時候給出代碼了.下面就是用匯編寫成的可執行的CRC-32算法(用其他語言也一樣
簡單,對于其他的CRC-32標準也一樣).注意在匯編中(計算機里)雙字在讀寫操作中順序都是
反著的.就是逆向順序.
crcBefore?????? dd (?)
wantedCrc?????? dd (?)
buffer????????? db 8 dup (?)
??????? mov???? eax, dword ptr[crcBefore] ;/*
??????? mov???? dword ptr[buffer], eax
??????? mov???? eax, dword ptr[wantedCrc] ; Step 1
??????? mov???? dword ptr[buffer+4], eax? ;*/
??????? mov???? di, 4
computeReverseLoop:
??????? mov???? al, byte ptr[buffer+di+3] ;/*
??????? call?? GetTableEntry????????????? ; Step 2 */
??????? xor???? dword ptr[buffer+di], eax ; Step 3
??????? xor???? byte ptr[buffer+di-1], bl ; Step 4
??????? dec???? di??????????????????????? ;/*
??????? jnz??? computeReverseLoop???????? ; Step 5 */
Notes:
-Registers eax, di bx are used
Implementation of GetTableEntry
crctable??????? dd 256 dup (?)?????? ;should be defined globally somewhere & initialized of course
??????? mov???? bx, offset crctable-1
getTableEntryLoop:
??????? add???? bx, 4??????????????? ;points to (crctable-1)+k*4 (k:1..256)
??????? cmp???? [bx], al???????????? ;must always find the value somewhere
??????? jne???? getTableEntryLoop
??????? sub???? bx, 3
??????? mov???? eax, [bx]
??????? sub???? bx, offset crctable
??????? shr???? bx, 2
??????? ret
On return eax contains a table entry, bx contains the entry number.
Outtro
? 好了...你終于讀到了本文的結尾.假如你認為從此不管對什么樣的CRC保護都可以說bye
bye了,那么你錯了,不是的!很容易就可以寫出對付破解CRC的代碼的.想要成功的破解CRC
你需要知道在一個保護中,到底使用的是那一種CRC算法,并且要知道CRC的具體的計算位置.
比如說這里一種簡單的對策就是使用2種不同的CRC算法,或者可以結合其他的數據保護算法
共同使用.
? 無論如何...我希望所有這里所介紹的內容都是受人關注的,并且我希望你(讀者)可以很
高興的讀著篇文章,就象我很高興寫一樣.???
???????????
翻譯過程中難免有錯誤,不當之處,請見諒.????????????? 譯者:? arbiter
??????????????????????????????????????????????????? 2001-2-8 22:41
???????????????????????????????????????????????????
???????????????????????????????????????????????????
???????????????????????????????????????????????????
Fnx go out to the beta-testers Douby/DREAD and Knotty Dread for the good
comments on my work which made it even better!
For a sample CRC-32 correcting patcher program visit my webpages:
??? http://surf.to/anarchriz? -> Programming -> Projects
(it's still a preview but will give you a proof of my idea)
For more info on DREAD visit http://dread99.cjb.net
If you still have questions you can mail me at anarchriz@hotmail.com,
or try the channels #DreaD, #Win32asm, #C.I.A and #Cracking4Newbies (in that
order) on EFnet (on IRC).
CYA ALL! - Anarchriz
"The system makes its morons, then despises them for their ineptitude, and
rewards its 'gifted few' for their rarity." - Colin Ward
附錄:
CRC-16 Table
? 00h?? 0000 C0C1 C181 0140 C301 03C0 0280 C241
? 08h?? C601 06C0 0780 C741 0500 C5C1 C481 0440
? 10h?? CC01 0CC0 0D80 CD41 0F00 CFC1 CE81 0E40
? 18h?? 0A00 CAC1 CB81 0B40 C901 09C0 0880 C841
? 20h?? D801 18C0 1980 D941 1B00 DBC1 DA81 1A40
? 28h?? 1E00 DEC1 DF81 1F40 DD01 1DC0 1C80 DC41
? 30h?? 1400 D4C1 D581 1540 D701 17C0 1680 D641
? 38h?? D201 12C0 1380 D341 1100 D1C1 D081 1040
? 40h?? F001 30C0 3180 F141 3300 F3C1 F281 3240
? 48h?? 3600 F6C1 F781 3740 F501 35C0 3480 F441
? 50h?? 3C00 FCC1 FD81 3D40 FF01 3FC0 3E80 FE41
? 58h?? FA01 3AC0 3B80 FB41 3900 F9C1 F881 3840
? 60h?? 2800 E8C1 E981 2940 EB01 2BC0 2A80 EA41
? 68h?? EE01 2EC0 2F80 EF41 2D00 EDC1 EC81 2C40
? 70h?? E401 24C0 2580 E541 2700 E7C1 E681 2640
? 78h?? 2200 E2C1 E381 2340 E101 21C0 2080 E041
? 80h?? A001 60C0 6180 A141 6300 A3C1 A281 6240
? 88h?? 6600 A6C1 A781 6740 A501 65C0 6480 A441
? 90h?? 6C00 ACC1 AD81 6D40 AF01 6FC0 6E80 AE41
? 98h?? AA01 6AC0 6B80 AB41 6900 A9C1 A881 6840
? A0h?? 7800 B8C1 B981 7940 BB01 7BC0 7A80 BA41
? A8h?? BE01 7EC0 7F80 BF41 7D00 BDC1 BC81 7C40
? B0h?? B401 74C0 7580 B541 7700 B7C1 B681 7640
? B8h?? 7200 B2C1 B381 7340 B101 71C0 7080 B041
? C0h?? 5000 90C1 9181 5140 9301 53C0 5280 9241
? C8h?? 9601 56C0 5780 9741 5500 95C1 9481 5440
? D0h?? 9C01 5CC0 5D80 9D41 5F00 9FC1 9E81 5E40
? D8h?? 5A00 9AC1 9B81 5B40 9901 59C0 5880 9841
? E0h?? 8801 48C0 4980 8941 4B00 8BC1 8A81 4A40
? E8h?? 4E00 8EC1 8F81 4F40 8D01 4DC0 4C80 8C41
? F0h?? 4400 84C1 8581 4540 8701 47C0 4680 8641
? F8h?? 8201 42C0 4380 8341 4100 81C1 8081 4040
CRC-32 Table
? 00h?? 00000000 77073096 EE0E612C 990951BA
? 04h?? 076DC419 706AF48F E963A535 9E6495A3
? 08h?? 0EDB8832 79DCB8A4 E0D5E91E 97D2D988
? 0Ch?? 09B64C2B 7EB17CBD E7B82D07 90BF1D91
? 10h?? 1DB71064 6AB020F2 F3B97148 84BE41DE
? 14h?? 1ADAD47D 6DDDE4EB F4D4B551 83D385C7
? 18h?? 136C9856 646BA8C0 FD62F97A 8A65C9EC
? 1Ch?? 14015C4F 63066CD9 FA0F3D63 8D080DF5
? 20h?? 3B6E20C8 4C69105E D56041E4 A2677172
? 24h?? 3C03E4D1 4B04D447 D20D85FD A50AB56B
? 28h?? 35B5A8FA 42B2986C DBBBC9D6 ACBCF940
? 2Ch?? 32D86CE3 45DF5C75 DCD60DCF ABD13D59
? 30h?? 26D930AC 51DE003A C8D75180 BFD06116
? 34h?? 21B4F4B5 56B3C423 CFBA9599 B8BDA50F
? 38h?? 2802B89E 5F058808 C60CD9B2 B10BE924
? 3Ch?? 2F6F7C87 58684C11 C1611DAB B6662D3D
? 40h?? 76DC4190 01DB7106 98D220BC EFD5102A
? 44h?? 71B18589 06B6B51F 9FBFE4A5 E8B8D433
? 48h?? 7807C9A2 0F00F934 9609A88E E10E9818
? 4Ch?? 7F6A0DBB 086D3D2D 91646C97 E6635C01
? 50h?? 6B6B51F4 1C6C6162 856530D8 F262004E
? 54h?? 6C0695ED 1B01A57B 8208F4C1 F50FC457
? 58h?? 65B0D9C6 12B7E950 8BBEB8EA FCB9887C
? 5Ch?? 62DD1DDF 15DA2D49 8CD37CF3 FBD44C65
? 60h?? 4DB26158 3AB551CE A3BC0074 D4BB30E2
? 64h?? 4ADFA541 3DD895D7 A4D1C46D D3D6F4FB
? 68h?? 4369E96A 346ED9FC AD678846 DA60B8D0
? 6Ch?? 44042D73 33031DE5 AA0A4C5F DD0D7CC9
? 70h?? 5005713C 270241AA BE0B1010 C90C2086
? 74h?? 5768B525 206F85B3 B966D409 CE61E49F
? 78h?? 5EDEF90E 29D9C998 B0D09822 C7D7A8B4
? 7Ch?? 59B33D17 2EB40D81 B7BD5C3B C0BA6CAD
? 80h?? EDB88320 9ABFB3B6 03B6E20C 74B1D29A
? 84h?? EAD54739 9DD277AF 04DB2615 73DC1683
? 88h?? E3630B12 94643B84 0D6D6A3E 7A6A5AA8
? 8Ch?? E40ECF0B 9309FF9D 0A00AE27 7D079EB1
? 90h?? F00F9344 8708A3D2 1E01F268 6906C2FE
? 94h?? F762575D 806567CB 196C3671 6E6B06E7
? 98h?? FED41B76 89D32BE0 10DA7A5A 67DD4ACC
? 9Ch?? F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5
? A0h?? D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252
? A4h?? D1BB67F1 A6BC5767 3FB506DD 48B2364B
? A8h?? D80D2BDA AF0A1B4C 36034AF6 41047A60
? ACh?? DF60EFC3 A867DF55 316E8EEF 4669BE79
? B0h?? CB61B38C BC66831A 256FD2A0 5268E236
? B4h?? CC0C7795 BB0B4703 220216B9 5505262F
? B8h?? C5BA3BBE B2BD0B28 2BB45A92 5CB36A04
? BCh?? C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D
? C0h?? 9B64C2B0 EC63F226 756AA39C 026D930A
? C4h?? 9C0906A9 EB0E363F 72076785 05005713
? C8h?? 95BF4A82 E2B87A14 7BB12BAE 0CB61B38
? CCh?? 92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21
? D0h?? 86D3D2D4 F1D4E242 68DDB3F8 1FDA836E
? D4h?? 81BE16CD F6B9265B 6FB077E1 18B74777
? D8h?? 88085AE6 FF0F6A70 66063BCA 11010B5C
? DCh?? 8F659EFF F862AE69 616BFFD3 166CCF45
? E0h?? A00AE278 D70DD2EE 4E048354 3903B3C2
? E4h?? A7672661 D06016F7 4969474D 3E6E77DB
? E8h?? AED16A4A D9D65ADC 40DF0B66 37D83BF0
? ECh?? A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9
? F0h?? BDBDF21C CABAC28A 53B39330 24B4A3A6
? F4h?? BAD03605 CDD70693 54DE5729 23D967BF
? F8h?? B3667A2E C4614AB8 5D681B02 2A6F2B94
? FCh?? B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D
參考:
> A painless guide to CRC error detection algorithm
? url: ftp://ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
? (I bet this 'painless guide' is more painfull then my 'short' one ;)
> I also used a random source of a CRC-32 algorithm to understand the algorithm
?? better.
> Link to crc calculation progs... hmmm search for 'CRC.ZIP' or 'CRC.EXE' or something
alike at ftpsearch (http://ftpsearch.lycos.com?form=advanced)
Copyright (c) 1998,1999 by Anarchriz
(this is REALLY the last line :)
轉載于:https://www.cnblogs.com/MaxWoods/archive/2006/03/03/342298.html
總結
以上是生活随笔為你收集整理的CRC原理及其逆向分析方法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Docker 阿里云镜像加速
- 下一篇： 坦克轮胎温度多少正常范围