Wprowadzenie
Ten esej składa się z przewodnika po CRC i opisu sposobu na jego odwrócenie. Wielu reverserów nie zna dokładnych zasad, na jakich funkcjonuje CRC a prawie nikt nie wie jak go odwrócić, choć wiedza ta może być bardzo użyteczna. Najpierw przewodnik nauczy cię jak ogólnie obliczyć CRC, możesz użyć go do ochrony danych. Potem, część traktująca o odwracaniu nauczy cię (głównie) jak odwracać CRC-32 - możesz tego użyć do złamania zabezpieczeń CRC niektórych programów (np. antywirusów). Wydaje się, że istnieją programy, które mogą "poprawić" CRC za ciebie, ale wątpię, czy tłumaczą co robią.
Chciałbym cię ostrzec, że w eseju tym znajduje się dużo matematyki. Nie zrobi to nikomu krzywdy, a przeciętny koder/Reverser zrozumie to bardzo dobrze. Dlaczego? Cóż. Jeżeli nie wiesz dlaczego używa się matematyki w CRC, proponuję kliknąć przycisk z X w prawym górnym rogu tego ekranu. Zakładam więc, że czytelnik zna arytmetykę binarną.
Część 1: Przewodnik po CRC, co to jest i jak to obliczyć
Cyclic Redundancy Code lub CRC
Wszyscy znamy CRC. Nawet jeżeli sobie nie przypominasz, przypomnisz sobie gdy pomyślisz o tych wkurzających komunikatach, które wyświetlają RAR, ZIP i inne kompresory kiedy plik jest uszkodzony z powodu wadliwego połączenia lub tych !@#$% dyskietek. CRC to wartość obliczona z kawałka danych, na przykład dla każdego pliku w czasie kompresji. Kiedy archiwizer rozpakowuje ów plik, odczytuje CRC i sprawdza go z nowo obliczonym CRC rozpakowanego pliku. Kiedy oba CRC pokrywają się, istnieje duża szansa, że pliki są identyczne. Przy CRC-32 szansa na to, że nie zostanie wykryta zmiana w danych wynosi 1/2 ^ 32.
Wielu ludzi sądzi, że CRC to po prostu skrót od Cyclic Redundancy Check (cykliczne sprawdzenie nadmiaru). Jeżeli CRC to rzeczywiście skrót tego terminu, wielu ludzi używa go niewłaściwie. Jeżeli by tak było, nie można by powiedzieć "CRC tego programu to 12345678". Ludzie mówią też zawsze, że jakiś program ma test CRC, nie Cyclic Redundancy Check check (sprawdzenie cyklicznego sprawdzenia nadmiaru). Wniosek: CRC znaczy Cyclic Redundancy Code (cykliczny kod nadmiaru a NIE Cyclic Redundancy Check (cykliczne sprawdzenie nadmiaru).
Jak dokonuje się tego obliczenia? Cóż, punktem wyjścia jest uznanie pliku za jeden duży łańcuch bitów podzielonych przez jakąś liczbę, dzielenie przez którą da resztę, mianowicie CRC! Działanie to zawsze daje resztę (może nią być zero), która jest najwyżej o jeden bit mniejsza niż dzielna (inaczej wciąż znajduje się w niej dzielnik). (9/3=3 reszta=0; (9+2)/3=3 reszta=2)
Tylko że tutaj, dzielenie przez bity wykonywane jest nieco inaczej. Dzielenie to powtarzane odejmowanie (x razy) liczby (dzielnika) od liczby, którą chcemy podzielić, co prowadzi do otrzymania reszty. Jeżeli chcemy otrzymać liczbę wyjściową, mnożymy przez dzielnik lub dodajemy dzielnik x razy do siebie a potem do wyniku dodajemy resztę.
Obliczenie CRC używa specjalnego sposobu na odejmowanie i dodawanie, tj. nowej "arytmetyki". Podczas obliczeń, dla obliczenia każdego bitu carry jest "zapominane". Przyjrzyjmy się dwóm przykładom, numer 1 to zwykłe odejmowanie, numery dwa i trzy są specjalne.
-+
(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
W przykładzie pierwszym(1), drugą kolumnę od prawej można by rozwinąć do 0-1=-1, a więc bit jest "pożyczany" z sąsiadującego bitu, co daje następujące odejmowanie (10+0)-1=1. (sposób podobny do odejmowania na papierze, odejmowania decymalnego)
Przykłady specjalne (2 i 3)
1+1 normalnie dałoby wynik 10, gdzie "1" jest carry, który "transportuje" wartość do obliczeń do następnego bitu. Ta wartość zostaje zapomniana.
Przypadek specjalny 0-1 normalnie miałby wartość "-1", co miałoby wpływ na sąsiadujący bit (patrz przykład 1). Ta wartość także zostaje zapomniana. Jeżeli wiesz coś o programowaniu, to wygląda, lub nawet lepiej powiedzieć, to jest operacja XOR.
Teraz przyjrzyjmy się przykładowi dzielenia:
To normalna arytmetyka:
1001/11110001101 13 9/12013
1001 - 09 -|
---- -- |
1100 30 |
1001 - 27 -
---- --
0110 3 -> reszta
0000 -
----
1100
1001 -
----
011 -> 3, reszta
W arytmetyce CRC:
1001/11110001110 9/12014 reszta 6
1001 -
----
1100
1001 -
----
1010
1001 -
----
0110
0000 -
----
110 -> reszta
(przykład 3)
Wynik dzielenia nie jest ważny, i nie warto go pamiętać, ponieważ wynosi on tylko kilka bitów mniej niż łańcuch bitów, z którego chciałeś obliczyć CRC. Ważna jest reszta! To ona mówi coś ważnego o oryginalnym pliku. To jest w zasadzie CRC!
Przejście do prawdziwych obliczeń CRC
By wykonać obliczenie CRC musimy wybrać dzielnik, od teraz będziemy go nazywać poly. Szerokość W poly to pozycja najwyższego bitu, a więc szerokość poly 1001 to 3, a nie 4. Zauważ, że najwyższym bitem jest zawsze jedynka, kiedy wybierasz więc szerokość poly musisz wybrać wartość tylko dla niższych bitów szerokości(W).
Jeżeli chcemy obliczyć CRC dla łańcucha bitów, musimy mieć pewność, że wszystkie bity zostaną przetworzone. Dlatego też musimy dodać do W bitów 0 do końca łańcucha. W przypadku przykładu 3, moglibyśmy powiedzieć, że łańcuch bitów to 1111. Przyjrzyjmy się nieco większemu przykładowi:
Poly = 10011, szerokość W=4
Łańcuch bitów + W zer = 110101101 + 0000
10011/1101011010000110000101 (nieważny jest dla nas wynik)
10011|||||||| -
-----||||||||
10011|||||||
10011||||||| -
-----|||||||
00001||||||
00000|||||| -
-----||||||
00010|||||
00000||||| -
-----|||||
00101||||
00000|||| -
-----||||
01010|||
00000||| -
-----|||
10100||
10011|| -
-----||
01110|
00000| -
-----|
11100
10011 -
-----
1111 -> reszta -> CRC!
(przykład 4)
Trzeba tu podkreślić dwie ważne rzeczy:
1. Tylko gdy najwyższy bit łańcucha ma wartość 1 wykonujemy na nim operację XOR w połączeniu z poly, w innym wypadku jedynie "przesuwamy" łańcuch bitów o jeden bit w lewo.
2. Efektem operacji XOR jest to, co zostało zXORowane z niższymi bitami szerokości W, ponieważ najwyższy bit zawsze będzie wynosił 0.
Przejście do algorytmu bazującego na tablicach
Wszyscy powinniście zrozumieć, że algorytm bazujący na obliczeniach binarnych będzie bardzo wolny i nieefektywny. Dużo bardziej wydajnie byłoby liczyć na bajtach. Ale wtedy możemy przyjąć poly tylko o szerokości wielokrotności 8 bitów (8 bitów to bajt). Przedstawmy to na przykładowym poly o szerokości 32 (W=32):
3 2 1 0 bajt
+---+---+---+---+
Pop! <--| | | | |<-- łańcuch bitów z dodanym W bitów, w tym wypadku 32
+---+---+---+---+
1<--- 32 bits ---> to jest poly, 4*8 bitów
(element 1)
To jest rejestr, którego używasz do chwilowego przechowywania CRC, nazywam go od tej chwili rejestrem CRC lub po prostu rejestrem. Przesuwasz bity do łańcucha bitów na prawo, a z łańcucha na lewo. Kiedy bit został usunięty z łańcucha a strona lewa jest równa 1, cały rejestr zostaje poddany operacji XOR przez niższe W bitów poly (w tym wypadku 32). Tak naprawdę jest to dokładnie taka sama operacja jak przedstawione wyżej dzielenie.
A co gdybyśmy (jak już mówiłem) przesunęli całą grupę bitów jednocześnie. Spójrz na przykład 8 bitowego CRC, gdzie przesunięto 4 bity za jednym razem:
Rejestr tuż przed przesunięciem: 10110100
Potem 4 bity (z góry) zostają usunięte z łańcucha z lewej strony, podczas gdy 4 nowe bity zostają dodane do łańcucha na prawą stronę. W tym wypadku 1011 zostaje usunięte a 1101 (nowe) zostaje dodane.
Potem sytuacja wygląda następująco:
8 bitowy rejestr CRC: 01001101
4 górne bity właśnie usunięte: 1011
używamy tego poly: 101011100, szerokość W=8
Teraz liczymy normalnie nową wartość rejestru.
Góra Rejestr
---- --------
1011 01001101 górne bity i rejestr
1010 11100 + (*1) Poly jest poddawane operacji XOR na pozycji 3 górnych bitów (bo tam znajduje się jedynka)
-------------
0001 10101101 wynik operacji XOR
Teraz wciąż mamy jedynkę w bicie na pozycji zero bitów górnych:
0001 10101101 poprzedni rezultat
1 01011100+ (*2) Poly jest poddawane operacji XOR na pozycji 0 górnych bitów (bo tam znajduje się jedynka)
-------------
0000 11110001 wynik drugiej operacji XOR
^^^^
Teraz górne bity to same zera, więc nie trzeba znów wykonywać operacji XOR na poly dla tej sekwencji górnych bitów.
Taką samą wartość rejestru otrzymuje się najpierw poddawszy operacji XOR (*1) z (*2) a wynik z rejestrem. Wynika to ze standardowej własności XOR:
(a XOR b) XOR c = a XOR (b XOR c)
1010 11100 poly na pozycji 3 górnych bitów
1 01011100+ poly poddane operacji XOR na pozycji 0 górnych bitów
-------------
1011 10111100 (*3) rezultat operacji XOR
Rezultat (*3) jest poddawany operacji XOR z rejestrem
1011 10111100
1011 01001101+ górne bity i rejestr
-------------
0000 11110001
Widzisz? Wynik jest taki sam! Teraz (*3) jest ważny, ponieważ z górnymi bitami 1010, w podanych warunkach, zawsze powiązana jest wartość (*3)=10111100 (tylko niższe W=8 bitów). Dzięki temu możesz obliczyć wartości XOR dla każdej kombinacji bitów górnych zanim zaczniesz dalsze obliczenia. Zauważ, że górne bity zawsze otrzymują zero po jednym powtórzeniu, dzieje się tak dlatego, że prowadzi do tego kombinacja operacji XOR.
Teraz wracamy do elementu 1. Dla każdej wartości górnego bajtu (8 bitów), który właśnie został przesunięty, możemy wcześniej obliczyć wartość. W tym wypadku byłaby to tablica składająca się z 256(2^8) elementów dwuwyrazowych (32 bity). (tablica CRC32 znajduje się w załączniku)
W pseudo-języku nasz algorytm wygląda tak:
While (łańcuch bajtów nie jest wyczerpany)
Begin
Top = górny bajt rejestru
Register = rejestr przesunięty o 8 bitów w lewo i poddany operacji XOR nowym bajtem z łańcucha
Register = rejestr poddany operacji XOR wartością Top z wcześniej obliczonej tablicy wyników
End
Bezpośredni algorytm tablicowy
Algorytm zaproponowany powyżej może zostać zoptymalizowany. Bajty z łańcucha bajtów nie muszą podróżować przez cały rejestr nim zostaną użyte. Za pomocą tego algorytmu możemy bezpośrednio poddać operacji XOR bajt z łańcucha bajtów z bajtem przesuniętym z rejestru. Wynik wskazuje na wartość z tabeli wartości, która zostanie poddana operacji XOR z rejestrem.
Nie wiem dokładnie dlaczego operacje te dają ten sam rezultat (ma to coś wspólnego z własnością XOR), ale ma to jedną wielką zaletę - nie musisz dodawać bajtów/bitów 0 do łańcucha bajtów. (jeżeli ktoś wie dlaczego, proszę powiedzcie mi :)
Spróbujmy zobrazować ten algorytm:
+----< łańcuch bajtów (lub plik)
|
v 3 2 1 0 bajt
| +---+---+---+---+
XOR---<| | | | | rejestr
| +---+---+---+---+
| |
| XOR
| ^
v +---+---|---+---+
| | | | | | tabela wyników
| +---+---+---+---+
+--->-: : : : :
+---+---+---+---+
| | | | |
+---+---+---+---+
(element 2)
"Odbity" bezpośredni algorytm tablicowy
By jeszcze skomplikować sprawę istnieje "odbita" wersja tego algorytmu. W "odbitym" rejestrze/wartości bity są zamieniane miejscami względem centrum. Na przykład 0111011001 jest odbiciem 1001101110.
Wymyślono to z powodu UART (chip wykonujący seryjne IO), który wysyła każdy bajt z najmniej istotnym bitem (bit 0) jako pierwsze a najbardziej istotny bit (bit 7) ostatni, co jest odwróceniem normalnej sytuacji.
Zamiast więc odwracać każdy bajt przed jego obróbką, każdy inny jest odwracany. Zaletą takiej operacji jest to, iż daje to kod o zmniejszonej objętości w implementacji. A więc, w tablicy obliczeniowej, bity zostają przesunięte w prawo a poly zostaje odwrócone. Podczas obliczania CRC rejestr zostaje przesunięty w prawo i (oczywiście) wykorzystuje się odwróconą tabelę.
łańcuch bajtów (lub plik) -->---+
| 1. Każdy element tablicy zostaje odwrócony
bajt 3 2 1 0 V 2. Wyjściowy rejestr zostaje odwrócony
+---+---+---+---+ | 3. Bajty z łańcucha bajtów nie zostają odwrócone,
| | | | |>---XOR ponieważ wszystko inne zostało.
+---+---+---+---+ |
| |
XOR V
^ |
+---+---|---+---+ |
| | | | | | Tabela wyników
+---+---+---+---+ |
: : : : : <---+
+---+---+---+---+
| | | | |
+---+---+---+---+
(element 3)
Nasz algortym:
1. Przesunąć rejestr on jeden bajt w prawo
2. Poddać operacji XOR górny bajt który został właśnie usunięty z nowym bajtem z łańcucha bajtów by otrzymać index do tablicy ([0,255])
3. Za pomocą operacji XOR wprowadzić wartość z tablicy do rejestru
4. Jeżeli zostało więcej bajtów do przetworzenia: patrz punkt 1
Kilka implementacji w assemblerze
Oto standard CRC-32:
Nazwa : "CRC-32"
Szerokość : 32
Poly : 04C11DB7
Wartość początkowa : FFFFFFFF
Odwrócony : Tak
XOR out with : FFFFFFFF
Jako bonus dla ciekawskich, standard CRC-16: :)
Nazwa : "CRC-16"
Szerokość : 16
Poly : 8005
Wartość początkowa : 0000
Odwrócony : Tak
XOR out with : 0000
"XOR out with" to wartość którą poddaje się operacji XOR z ostateczną wartością rejestru przed otrzymaniem (jako wynik) ostatecznego CRC.
Istnieją także odwrócone poly dla CRC ale są on nieistotne dla tego przewodnika. Spójrz na moje odniesienia jeżeli chcesz dowiedzieć się więcej.
Dla implementacji assemblerowej używam 32 bitowego kodu w 16 bitowym trybie DOSowym... a więc zobaczysz nieco pomieszanego 32 i 16 bitowego kodu... łatwo to przekonwertować w pełny 32 bitowy kod. Zauważ że implementacja assemblerowa została przetestowana i działa, natomiast kod Java i języka C są wnioskami płynącymi z poprzedniego kodu.
Ok. Oto implementacja w assemblerze obliczająca wartości tabeli CRC-32:
xor ebx, ebx ;ebx=0, ponieważ zostanie on użyty jako wskaźnik
InitTableLoop:
xor eax, eax ;eax=0, ponieważ na początku musi równać się 0
mov al, bl ;8 niższych bitów ebx zostaje skopiowane do 8 niższych bitów eax
;generate entry
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
Notes: - crctable to tablica 256 wartości dwuwyrazowych
- eax zostaje przesunięty w prawo, ponieważ CRC-32 używa odwróconego algorytmu
- dlatego też najniższe 8 bitów jest przetwarzanych...
To samo w Javie lub C (int ma 32 bity):
for (int bx=0; bx<256; bx++){
int eax=0;
eax=eax&0xFFFFFF00+bx&0xFF; // the "mov al,bl" instruction
for (int cx=0; cx<8; cx++){
if (eax&&0x1) {
eax>>=1;
eax^=poly;
}
else eax>>=1;
}
crctable[bx]=eax;
}
Implementacja dla obliczeń CRC-32 z użyciem tabeli:
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
Notes: - ds:si wskazuje na bufor gdzie znajdują się bajty do przetworzenia
- cx zawiera ilość bajtów do przetworzenia
- eax zawiera obecny CRC
- crctable to tabela obliczona za pomocą powyższego kodu
- wyjściowa wartość CRC jest taka sama jak w przypadku CRC-32: FFFFFFFF
- po końcowych wyliczeniach CRC poddawany jest operacji XOR z: FFFFFFFF
co oznacza to samo co NOTacja.
W Javie lub języku C wygląda to tak:
for (int cx=0; cx>=8;) {
eax^=crcTable[ebx];
}
eax^=0xFFFFFFFF;
A więc wylądowaliśmy na końcu pierwszej części: przewodnika po CRC. Jeżeli chcesz lepiej poznać tajniki CRC sugeruję, byś przeczytał napisany przeze mnie dokument, do którego adres znajdziesz na końcu tego dokumentu.
Ok. A teraz przejdźmy do najbardziej interesującej części tego dokumentu: odwracania CRC
Częśc 2: Odwracanie CRC
Kiedy myślałem nad sposobem by odwrócić CRC ... kilkakrotnie utknąłem. Próbowałem "dezaktywować" CRC poprzez taką sekwencję bajtów, żeby potem nie miało już znaczenia jakie bajty umieściłbyś po nim. Nie potrafiłem tego zrobić... Potem zdałem sobie sprawę z tego, że to nigdy nie mogło działać w ten sposób, ponieważ algorytm CRC jest zbudowany w taki sposób, że nieważne, który bit zostanie zmieniony, kompletny CRC zawsze (cóż...prawie zawsze) zmienia się drastycznie. Spróbuj sam (z pomocą jakiegoś prostego programu CRC)... :)
Zdałem sobie sprawę z tego, że mogę tylko poprawić CRC po bajtach które chciałem zmienić. A więc mogłem stworzyć taką sekwencję bajtów, która przekształciłaby CRC w cokolwiek bym chciał.
Zobrazujmy ten pomysł:
Zlepek bajtów: 01234567890123456789012345678901234567890123456789012
Chcesz zmienić od ^ tego bajtu do ^ tego bajtu
To pozycje od 9 do 26
Potrzebujemy także 4 dodatkowych bajtów (do pozycji 30 ^) dla sekwencji bajtów, która przywróci CRC do jego oryginalnej wartości po zmienionych bajtach.
Gdy liczysz CRC-32 wszystko idzie gładko aż do bajtu na pozycji 9, w zlepku zmienianych bajtów CRC zmienia się radyklanie od tej pozycji. Nawet po przekroczeniu pozycji 26, gdzie bajty nie zostają już zmienione, nigdy nie odzyskasz oryginalnego CRC. NIE! Kiedy przeczytasz resztę tego eseju będziesz wiedział jak to zrobić.
W skrócie musisz postąpić tak gdy zmieniasz zlepek bajtów zatrzymując oryginalny CRC:
1. Obliczyć CRC do pozycji 9 i zapisać tą wartość.
2. Liczyć dalej aż do pozycji 27 i dla dalszych 4 dodatkowych bajtów i zapisać wynik.
3. Użyć wartości z punktu 1 do obliczenia CRC nowych bajtów i 4 dodatkowych bajtów (powinno być 27-9+4=22 bajty) i zapisać wynik.
4. Teraz mamy nową wartość CRC, ale chcemy by CRC było starym CRC. Używamy odwróconego algorytmu do obliczenia dodatkowych 4 bajtów.
Potrafimy wykonać obliczenia z punktów 1-3, teraz nauczymy się tych z punktu 4.
Odwracanie CRC-16
Pomyślałem, że żeby ułatwić wam sprawę, najpierw pokażę jak obliczyć odwrotność CRC-16. Ok. Jesteśmy w pewnym punkcie po zmianie kodu, kiedy chcemy przywrócić CRC jego oryginalną wartość. Znamy oryginalny CRC (obliczony przed zmienieniem danych) i obecny rejestr CRC. Chcemy obliczyć 2bajtowy łańcuch który zmienia obecny rejestr CRC na oryginalny CRC. Wpierw obliczamy "normalnie" CRC nieznanych 2 bajtów nadając im nazwę X i Y, a za wartość rejestru przyjmujemy a1 a0, jedynym elementem, który nie jest zmienną jest zero (00). :) Spójrzmy na nasz najnowszy algorytm CRC (element 3), by lepiej zrozumieć o czym mowa.
Ok., zaczynamy:
Weźmy 2bajtowy łańcuch "X Y". Bajty przetwarzane są od lewej strony.
Za rejestr przyjmijmy a1 a0.
Zamiast "operacja XOR" pisać będziemy "+" (tak jak w przewodniku).
Przetwarzamy pierwszy bajt, X:
a0+X to jest obliczony górny bajt (1)
b1 b0 sekwencja tabeli na którą wskazuje górny bajt
00 a1 rejestr przesunięty w prawo
00+b1 a1+b0 poprzednie 2 wiersze poddane operacji XOR ze sobą
Teraz wartość rejestru to: (b1) (a1+b0)
Przetwarzamy drugi bajt, Y:
(a1+b0)+Y to jest obliczony górny bajt (2)
c1 c0 sekwencja tabeli na którą wskazuje górny bajt
00 b1 rejestr przesunięty w prawo
00+c1 b1+c0 poprzednie 2 wiersze poddane operacji XOR ze sobą
Teraz wartość rejestru to: (c1) (b1+c0)
Pokażę to w trochę inny sposób:
a0 + X =(1) wskazuje na b1 b0 w tabeli
a1 + b0 + Y =(2) wskazuje na c1 c0 w tabeli
b1 + c0=d0 nowy niski bajt rejestru
c1=d1 nowy górny bajt rejestru
(1) (2)
Wow! Niech ta informacja popracuje nad tobą przez chwilę... :)
Nie bój się - zaraz omówimy przykład na konkretnej wartości
A co gdybyś chciał żeby rejestr był jakimś d1 d0 (oryginalny CRC) I znałbyś wartość rejestru przed transformacją (a więc a1 a0)... jakie 2 bajty lub jakie X i Y musiałbyś przepuścić przez obliczenia CRC?
Ok. Zaczniemy pracę od końca i cofniemy się do początku. d0 musi być równe b1+c0 a d1 musi być równe c1... Ale już słyszę jak mówisz: "Skąd do cholery wziąć wartość bajtów b1 i c0???" Czy muszę przypominać ci o tabeli? Możesz po prostu sprawdzić wartość wyrażeń c0 c1 w tabeli ponieważ znasz c1. Dlatego bardzo ważne jest, by wyrobić sobie nawyk patrzenia w tabelę. Jeżeli znalazłeś wartość, zapamiętaj index do tej wartości, ponieważ w ten sposób znajdziesz nieznane górne bajty np. (1)&(2)!
A więc teraz gdy znalazłeś c1 c0, skąd wziąć b1 b0? Jeżeli b1+c0=d0 to b1=d0+c0! Teraz spójrz w tabelę by otrzymać wartość b1 b0. Teraz znamy wszystko co potrzebne do obliczenia X & Y! Fajnie, nie?
a1+b0+Y=(2) więc Y=a1+b0+(2)
a0+X=(1) więc X=a0+(1)
Konkretny przykład dla CRC-16
Przyjrzyjmy się przykładowi z konkretnymi wartościami:
-rejestr przed: (a1=)DE (a0=)AD
-poszukiwany rejestr: (d1=)12 (d0=)34
Odnajdź w tabeli pozycję zaczynającą się od 12 w tabeli CRC-16 w załaczniku.
- Chodzi o pozycję 38h mającą wartość 12c0. Spróbuj znaleźć inną pozycję zaczynającą się od 12. Nie możesz znaleźć innej bo obliczyliśmy każdą pozycję dla każdej możliwej wartości górnego bajtu a to daje 256 warości, zapamiętaj!
Teraz wiemy że (2)=38, c1=12 a c0=c0, a więc b1=c0+34=F4, teraz odnajdź w tabeli pozycję B1 zaczynającą się od F4.
-To pozycja 4Fh zaczynająca się od wartości F441.
Teraz wiemy, że (1)=4F, b1=F4 a b0=41. Teraz znamy wszystkie potrzebne wartości by móc obliczyć X i Y a więc bierzemy się do tego:
Y=a1+b0+(2)=DE+41+38=A7
X=a0+(1) =AD+4F =E2
Wniosek: by zmienić rejestr CRC-16 z DEAD na 1234 potrzebujemy bajtów E2 i A7 (w tej kolejności).
Widzisz, by odwrócić CRC musisz sobie "obliczyć drogę powrotną" i zapamiętywać otrzymywane po drodze wyniki. Kiedy programujesz tabelę w asemblerze, pamiętaj że intel zapisuje wartości od końca w formacie Little-Endian. Teraz pewnie rozumiesz jak odwrócić CRC-16 ... teraz CRC-32.
Odwracanie CRC-32
Omówiliśmy już CRC-16, CRC-32 jest tak samo łatwy do odwrócenia (lub tak samo trudny). Teraz pracujemy z 4 zamiast 2 bajtów. Podczas czytania zerkaj i porównuj to z wersją dla 16bit.
Weźmy 4bajtowy łańcuch X Y Z W, bajty bierzemy z lewej strony.
Za rejestr przyjmijmy a3 a2 a1 a0
Zauważ, że a3 jest najważniejszym bajtem a a0 najmniej ważnym.
Przetwarzamy pierwszy bajt, X:
a0+X to jest obliczony górny bajt (1)
b3 b2 b1 b0 sekwencja tabeli na którą wskazuje górny bajt
00 a3 a2 a1 rejestr przesunięty w prawo
00+b3 a3+b2 a2+b1 a1+b0 poprzednie 2 wiersze poddane operacji XOR ze sobą
Teraz rejestr to: (b3) (a3+b2) (a2+b1) (a1+b0)
Przetwarzamy drugi bajt, Y:
(a1+b0)+Y to jest obliczony górny bajt (2)
c3 c2 c1 c0 sekwencja tabeli na którą wskazuje górny bajt
00 b3 a3+b2 a2+b1 rejestr przesunięty w prawo
00+c3 b3+c2 a3+b2+c1 a2+b1+c0 poprzednie 2 wiersze poddane operacji XOR ze sobą
Teraz rejestr to: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)
Przetwarzamy trzeci bajt, Z:
(a2+b1+c0)+Z to jest obliczony górny bajt (3)
d3 d2 d1 d0 sekwencja tabeli na którą wskazuje górny bajt
00 c3 b3+c2 a3+b2+c1 rejestr przesunięty w prawo
00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 poprzednie 2 wiersze poddane operacji XOR ze sobą
Teraz rejestr to:: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)
Przetwarzamy czwarty bajt, W:
(a3+b2+c1+d0)+W to jest obliczony górny bajt (4)
e3 e2 e1 e0 sekwencja tabeli na którą wskazuje górny bajt
00 d3 c3+d2 b3+c2+d1 rejestr przesunięty w prawo
00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 poprzednie 2 wiersze poddane operacji XOR ze sobą
Teraz rejestr to: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)
Pokażę to na trochę inny sposób:
a0 + X =(1) wskazuje na b3 b2 b1 b0 z tabeli
a1 + b0 + Y =(2) wskazuje na c3 c2 c1 c0 z tabeli
a2 + b1 + c0 + Z =(3) wskazuje na d3 d2 d1 d0 z tabeli
a3 + b2 + c1 + d0 + W =(4) wskazuje na e4 e3 e2 e1 z tabeli
b3 + c2 + d1 + e0 =f0
c3 + d2 + e1 =f1
d3 + e2 =f2
e3 =f3
(1) (2) (3) (4)
(element 4)
Kod ten został odwrócony w taki sam spobób jak jego 16bitowa wersja. Podam teraz przykład z prawdziwymi wartościami. Jako tablicy wartości użyj tablicy CRC-32 z załącznika.
Za rejestr CRC przed - a3 a2 a1 a0 -przyjmij odpowiednio AB CD EF 66
Za rejestr CRC po - f3 f2 f1 f0 -przyjmij odpowiednio 56 33 14 78 (szukana wartość)
Zaczynamy:
Pierwszy bajt wpisu: wpis wartość
e3=f3 =56 -> 35h=(4) 56B3C423 dla e3 e2 e1 e0
d3=f2+e2 =33+B3 =E6 -> 4Fh=(3) E6635C01 dla d3 d2 d1 d0
c3=f1+e1+d2 =14+C4+63 =B3 -> F8h=(2) B3667A2E dla c3 c2 c1 c0
b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 dla b3 b2 b1 b0
Teraz mamy wszystkie potrzebne wartości, a więc
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
(ostateczne obliczenie)
Wniosek: by zmienić rejestr CRC-32 z ABCDEF66 na 56331478 potrzebujemy takiej sekwencji bajtów B8 C4 53 8E
Odwrócony algorytm dla CRC-32
Jeżeli spojrzysz na ręczne obliczenia sekwencji bajtów potrzebnych do zmiany rejestru CRC z a3 a2 a1 a0 na f3 f2 f1 f0 zobaczysz, że trudno przekształcić je w miły algorytm o małej objętości.
Spójrzmy na rozszerzoną wersję ostatecznego obliczenia:
Pozycja
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
(element 5)
To tak jak w elemencie 4, tylko niektóre wartości/bajty zostały zamienione. Ten punkt widzenia pomoże nam w wypracowaniu kompaktowego algorytmu. Co jeśli weźmiemy bufor o rozmiarach 8 bajtów, gdzie dla każdej linii którą widzisz w elemencie 5 zarezerwowany jest jeden bajt. Bajty od 0 do 3 są wypełnione a0 do a3, bajty 4 do 7 od f0 do f3. Jak wcześniej bierzemy ostatni bajt e3, który jest równy f3, i sprawdzamy jego kompletną wartość w tabeli CRC.Potem na pozycji 4 (tak jak w elemencie 5) poddajemy tą wartość (e3 e2 e1 e0) operacji XOR. Automatycznie znamy wartość d3, ponieważ poddaliśmy już operacji XOR f3 f2 f1 f0 z e3 e2 e1 e0, a f2+e2=d3. Ponieważ znamy już wartość (4) (cyfra elementarna), możemy bezpośrednio poddać ją operacji XOR na pozycję 3. Gdy znamy już wartość d3 możemy jej użyć by z tabeli odczytać wartość d3 d2 d1 d0 i poddać ją operacji XOR na poprzedniej pozycji, tj. pozycji 3. Teraz poddajemy znaleziony numer wejścia (3) operacji XOR z tym z pozycji 2. Znamy wartość c3 ponieważ znamy wartość f1+e1+d2=c3 na pozycji 5.
Robimy tak aż poddamy operacji XOR b3 b2 b1 b0 na pozycji 1. I voila! Bajty 0 do 3 z bufora teraz zawierają potrzebne nam bajty X do W!
Oto podsumowanie algorytmu:
1. W 8 bajtowym buforze, pozycje od 0 do 3 wypełnij wartościami od a0 do a3 (wartość początkowa rejestru CRC), a pozycje 4 do 7 wartościami f0 do f3 (żądana końcowa wartość rejestru CRC).
2.Weź bajt z pozycji 7 i użyj go by odczytać z tabeli pełną wartość.
3. Poddaj tą wartość (dwuwyraz) operacji XOR na pozycji 4
4. Poddaj operacji XOR numer wejścia (bajt) na pozycji 3
5. Powtórz krok 2 I 3 jeszcze 3 razy za każdym razem zmniejszając pozycję o jeden.
Implementacja odwróconego algorytmu.
Teraz czas na trochę kodu. Poniżej znajduje się implementacja odwróconego algorytmu dla CRC-32 w Asemblerze (nie jest trudno zrobić to samo dla innych języków i/lub standardów CRC). Pamiętaj, że w asemblerze (na PC"tach) dwuwyrazy są zapisywane i czytane z pamięci w odwrotnej kolejności.
Wyjściowe CRC (crcBefore) dd (?)
Żądane CRC (wantedCrc) dd (?)
Bufor (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:
-Używa się rejestrów eax, di bx
Implementacja GetTableEntry
crctable dd 256 dup (?) ;powina zostać gdzieś zdefiniowana globalnie;amp; oczywiście zainicjalizowana
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
NA wyjściu eax zawiera pozycję z tabeli, bx numer pozycji z tabeli.
Outtro
Cóż...dotarłeś do końca tego eseju. Jeżeli teraz myślisz: wow, wszystkie te programy chronione przez CRC mogą się teraż pożegnać... nic z tego. Bardzo łatwo napisać anty-anty CRC. By udało się odwrócić CRC musisz wiedzieć dokładnie od której części kodu obliczane jest CRC i jaki algorytm CRC jest do tego wykorzystywany. Powszechnym zabezpieczeniem jest używanie dwóch algorytmów CRC albo kombinacji z innym algorytmem ochrony danych.
Mam nadzieję, że to wszystko było interesujące I że tyle samo radości czerpałeś z czytania tego jak ja z pisania.
Podziękowania dla beta-testerów Douby/DREAD and Knotty Dread za komentarze odnośnie mojej pracy, które uczyniły ją jeszcze lepszą!
By zdobyć demonstracyjny program poprawiający CRC-32 odwiedź moje strony:
http://surf.to/anarchriz -> Programming -> Projects
(to wciąż wersja próbna, ale da ci dowód na prawdziwość mojego pomysłu)
Po więcej informacji od DREAD odwiedź http://dread99.cjb.net
Jeżeli wciąż masz jakieś pytania możesz do mnie napisać e-mail: anarchriz@hotmail.com lub spróbować kanałów IRC #DreaD, #Win32asm, #C.I.A i #Cracking4Newbies (w tej kolejności) na Efnet.
CYA ALL! - Anarchriz
"The system makes its morons, then despises them for their ineptitude, and
rewards its "gifted few" for their rarity." - Colin Ward
Załącznik
Tabela CRC-16
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
Tabela CRC-32
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
Odniesienia:
> Bezbolesny przewodnik po algorytmie wykrywania błędów CRC:
url: ftp://ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
(Założę się, że ten "bezbolesny przewodnik" jest bardziej bolesny niż mój "krótki";)
> Użyłem też losowego źródła algorytmu CRC-32 by lepiej zrozumieć ten algorytm.
> Link do programów obliczających CRC... hmmm poszukaj "CRC.ZIP" lub "CRC.EXE" lub czegoś podobnego w wyszukiwarce ftp na http://ftpsearch.lycos.com?form=advanced
Copyright (c) 1998,1999 by Anarchriz
(to już NAPRAWDĘ ostatnia linijka:)
Copyright (c) 2002 for the polish translation by Michał "Evangelion" Skoczyński